Slashdot Mirror
Pentago Is a First-Player Win
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."
I was lucky enough to have a lecturer at university who was actively working on solving Go. Professor Wilfred Hodges at QMW, University of London.
It was his talk about the complexity of the game of Go on my induction day that convinced me to go to that university, and I was able to have him as a course lecturer for certain related courses later on (graph theory).
He is a typical, mad-haired, Einsteinian-looking sandals-in-winter professor, and he gave a marvellous intro to Go, complexity and the work he was doing.
All everyone else took away was that he showed photos of himself at a Go convention (on 35mm film). But I thought it was brilliant, and it made me teach myself Go.
I hope he's still working on it. Judging by the website I've found for him, he's busy with a LOT of other areas of mathematics than Game Theory, though.
But I'll never forget the mental "Woah" I got when he explained how much more complicated 19x19 Go was than Chess, even though the rules are vastly simpler.
Apparently there is no decent Go computer player in the world that can beat more than an average Go human player.
Go isn't complex. Go is very simple. It's just large. Go is a perimeter game and is really no more complex than Othello. A simple neural net (I hate that fucking term) algorithm trained against average Go-playing humans will end up being average at playing Go. The people who are fascinated by Go's "complexity" are only trying to solve it in bulk with traditional alpha-beta minimax schemes. Such approaches are not well-suited to Go because the score of any given board means very little since it can be completely flipped in a few moves. A game like Chess, on the other hand, is somewhat suited to alpha-beta minimax because pieces are removed as the game goes on and we can weight the pieces. A king is the end-game, a queen is always more important than a bishop, almost always more important than a rook or pawn, usually more important than a knight, etc.