5 ms·
> Combinatorically, Go is considered pretty much the most complex game in existence Is that considering "game" to include only traditional turn-based board gam
by baddox 13y ago
> Combinatorically, Go is considered pretty much the most complex game in existence
Is that considering "game" to include only traditional turn-based board games? Presumably it would be trivial to make a video game that's vastly more complex (at least in terms of tree or state space complexity) than Go. Any real-time strategy game should quality.
- wtallis 13y agoThere are plenty of deterministic games more complex than Go, even turn-based ones. But Go is still a clear outlier due to its age and the simplicity of its rules - it's completely obvious how to enumerate the game tree. Things like a real-time strategy game aren't really a fair comparison, since they are designed to approximate a continuous game space-time as opposed to the discrete board and moves of Go. You can inflate the game tree complexity just by switching from single-precision to double-precision, but that doesn't really make the game any harder.
- baddox 13y ago> You can inflate the game tree complexity just by switching from single-precision to double-precision, but that doesn't really make the game any harder. I think that absolutely makes the game significantly harder, just like playing Go on a smaller board is easier than Go on a larger board.
- jim-greer 13y agoHmm, would you say that poker is harder if you can raise from $10 to $50.00001 instead of $50?
- wtallis 13y agoOnly if you're brute-forcing the game. Something like smaller time steps and more precise positioning for a RTS will usually only slightly alter the optimal strategies, rather than change them to be unrecognizable, because the size of units and buildings and obstacles won't have changed so things like route finding will be basically unchanged in result and execution time. Almost everything being optimized would be locally convex at the scale of the new degrees of precision, so nothing would get exponentially harder.
- baddox 13y agoIn some cases I think you're right, but depending on the game I could see there being potential emergent chaos from even the slightest variations in positioning.
- jessriedel 13y agoThis depends on whether the game outcomes tend to vary smoothly with each step, or not. If you have a computer play computer ping (which will be smooth), then increasing precision has minimal effect.
- tromp 13y agoBut Go can still be surprisingly hard on tiny board sizes. There are, for instance, 386,356,909,593 possible 2x2 games. (under the positional superko rule which says you cannot repeat any earlier position.)
- thinkpad20 13y agoHow is this possible? Every game that I can imagine on a 2x2 board ends in about 5 or 6 moves. It seems there'd be 4 x 3 x 2 choices for the first 3 moves. Then the fourth move would capture two pieces, leaving two spaces open, so up to 48. I don't think I quite have the whole picture, but either way I can't possibly fathom how it could reach a number like you've given. What's the source of that?
- NhanH 13y agoThe longest 2x2 game possible seems to be 46 [1]. I can't find the source for the number given by tromp either. But considering that log_2(386,356,909,593) = ~ 38 and log_3(386,356,909,593) = ~24. If the board can have a branching factor of 2.5 on average for a game length of 30 moves, the number seems reasonable. There are 81 possible states (counting illegal states), and seems to be about 50 legal states. And I'd imagine any given state on a 2x2 board would easily have more than 2 possible moves :-). [1]: http://senseis.xmp.net/?LongestPossibleGame#toc6 http://senseis.xmp.net/?LongestPossibleGame#toc6
- MichaelGG 13y agoAre top RTS games like Starcraft hard for AI? I know the default AI isn't strong, but is Starcraft in theory difficult to trounce humans? I spoke to an ex-pro player and he asserted AI could never get close, but I don't see why. It seems like being able to do precise calculations and a near infinite APM could be a significant advantage.
- T-hawk 13y agoWhat makes AI difficult in these games is pattern recognition of higher level strategic abstractions. A human player can recognize that placing a Go stone or a Terran command center projects some power in regions around that spot. The human can use intuitive pattern matching to assess when he has a superior force in an area and can push to a decisive tactical victory, even if the human isn't quantifying every move in precise terms. An AI must quantify every bit of power projection somehow, which becomes impossible with present computing resources in games whose possible state space quickly explodes into 10^10 or more possibilities. It's actually a similar problem to computer vision. Identifying a battle front from the current state of a war game and recognizing the tactical possibilities is similar to edge detection in a photograph and recognizing objects. Humans do that essentially with highly parallel computations and lookups by billions of neurons. Until we get billion-core CPUs and billion-ported RAM, AIs will not have the same capability. Source: I've done some development on AI for Civilization. It sits somewhere between Go and Starcraft in AI capabilities. Civilization is turn-based like Go, but the state space explodes far more quickly like Starcraft when you have 100 units which can each make a dozen moves in 100! different orders on a turn. (In Civ, the order on which units act each turn is extremely important, where workers lay down railroads for other units to move, or where you attack a city with artillery before the ground pounders.)
- baddox 13y agoNow that I think about it, the more interesting and challenging strategic factor in Starcraft is probably the fact that it's not a perfect information game. That's probably a big part why AIs are really good at isolated parts of Starcraft (like executing build orders in the first couple minutes of the game, or micromanaging armies in controlled situations), but really bad at actually playing a normal game and winning.
- mcv 13y agoA real time strategy game with go's strategic depth would be totally unplayable for any human.