Pentago Is a First-Player Win 136
First time accepted submitter jwpeterson writes "Like chess and go, pentago is a two player, deterministic, perfect knowledge, zero sum game: there is no random or hidden state, and the goal of the two players is to make the other player lose (or at least tie). Unlike chess and go, pentago is small enough for a computer to play perfectly: with symmetries removed, there are a mere 3,009,081,623,421,558 (3e15) possible positions. Thus, with the help of several hours on 98304 threads of Edison, a Cray supercomputer at NERSC, pentago is now strongly solved. 'Strongly' means that perfect play is efficiently computable for any position. For example, the first player wins."
Comparison to Chess? (Score:5, Interesting)
Out of curiousity, does anybody know what the number for chess that compares to the 3e15 number for pentago is? In other words, how much "bigger" is chess?
A rough approx. is 10^60 moves (Score:2, Interesting)
Assuming the game goes for at least 30 moves, and that each player has roughly 10 options per move you get 10^(2*30). 10 options times 30 moves * 2 (there are two players, so two moves per "move").
Re:Comparison to Chess? (Score:3, Interesting)
Go on 9x9 is very similar to Chess neurologically: it's a tactics game. I'm bad at it. I hate chess for emotional-political reasons: it is technically inferior to Go, being that it is tactical, and thus I cannot stomach nor can I support wasting my time on such an inefficient pursuit. Someone has been reasoning, correctly, that I should practice Chess to gain additional, non-domain tactical exercise so as to improve my Go playing. I have been, incorrectly, resistant.
Go in 13x13 is strategically different to Go in 19x19. On a 13x13 board, abstract strategy and tactics both apply simultaneously: control of a corner exerts strong influence over another corner, and you can develop very quickly. Strategic moves must also be tactical.
Go in 19x19 is, early on, strategic: the stretch of influence is too big, and only vague tactical considerations are helpful because of too much variation. Early play accounts for strategy alone: it accounts for providing a position that has strong but non-specific tactical value for all variations. As the board develops, tactical situations arise: the strategy employed provides a variety of tactical responses to tactical approaches. This exercises, both separately and conjointly, the full utilization of abstract strategic thinking and logical tactical computation.
Thus Go 9x9 and Chess are both tactical calculation; Go 13x13 is strategic-tactical or tactical depending on position, weakly exercising abstract reasoning and more strongly exercising tactical calculation; and Go 19x19 exercises the full breadth of abstract strategic thinking, blended thinking (including feedback looping tactics into strategic impact and strategy into tactical options), and direct tactical thinking (when the immediate position is only a win-lose proposition, not a resultant strategic position proposition).
I am better at Go 13x13 because I can cover the weaknesses in my abilities while abusing the weaknesses in my opponent's abilities. It is an easy game for me because I start with the option of using whichever mode of thinking I'm better at in the current position, and retain that until it's too late to really swing the game. 9x9 relies on tactical calculation, while 19x19 relies on effective use of the greatest breadth of mental skills based on what's on the board more than what I feel like I can handle at the time; I like 19x19 because it forces me to grow and learn.
Computational analysis is not relevant for wide-play of Go because it's impossible and there are other, more abstract ways to do this. There are even computer algorithms to analyze influence and use this to analyze strategic strengths and weaknesses, then analyze those areas of the board to analyze the strategic position. Humans are better at it, but direct computation isn't the only way to approach the problem.