Pentago Is a First-Player Win

Posted by timothy on Thursday January 23, 2014 @05:34AM from the heads-I-win-tails-you-lose dept.

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."

3 of 136 comments (clear)

Min score:

Reason:

Sort:

Re:different than tic tac toe or connect 4? by mrchaotica · 2014-01-23 05:48 · Score: 4, Informative

No, tic-tac-toe is always a tie.

--
"[Regarding the 'cloud,'] ownership was what made America different than Russia." -- Woz
Re:Comparison to Chess? by vux984 · 2014-01-23 05:50 · Score: 5, Informative

chess
state space complexity 10^47
go
9x9 - 10^38
13x13 - 10^79
19x19 - 10^171
Re:Comparison to Chess? by Anonymous Coward · 2014-01-23 05:58 · Score: 4, Informative

According to the summary, 3e15 is the number of possible positions. The number of possible positions in chess is around 4e46.
http://en.wikipedia.org/wiki/Shannon_number