3 ms·
There 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 rul
by wtallis 13y ago
There 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