3 ms·
But 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
by tromp 13y ago
But 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