Checkers is Solved
I spent a few of the last 24 hours on buses reading game theory books. And today, I found out a neat result connected to my reading: someone has recently (with the aid of vast computational power) “solved” checkers. Specifically, if either plays “perfectly”, they can at least guarantee a draw; neither player has a winning strategy.
Previously “solved” games that are not absurdly obscure:
- Connect Four (1988) : there is a winning strategy for the first player
- Tic-tac-toe (folklore) : neither player has a winning strategy
- 4×4x4 3D Tic-tac-toe (1994) : there is a winning strategy for the first player
- Go-moku (1993) : there is a winning strategy for the first player
- 9 men’s morris (1993) : there is a winning strategy for the first player
on September 7, 2007 on 1:24 pm
I’m surprised to find out that you will be lecturing game theory. I hope this is going to be an easy course
I was doing a bit of reading on solved games as well. Specifically Victor Allis solved Connect Four, 4×4x4 tic-tac-toe and Gomoku (connect 5) using essentially three techniques:
board isomorphism to reduce search space
proof-number search to heuristically select the best move when multiple choices are possible
and a end-game search which involves one player forcing the other player to block winning conditions until a trap is formed (so in the case of 4×4x4 tic-tac-toes, it would be that the first player forcing the game by making 3-in-a-row until he proceed to make double 3s and win the game). It works slightly differently in Go-moku. Although I believe Allis wasn’t the first one to solve 4×4x4. The first computer aided solution (Allis claimed that it had deficiencies) was by Patenishik (sp) in 1988. In fact, Checkers were solved by the UofAlberta team in much the same way: it relied on an excellent opening-book, proof-number search midway, and a 10-ply end game database.
Lastly, many of these games are weakly solved. The result guarentees a first-player win/draw starting from the initial position. However, it is still interesting to know who would win given a particular board configuration (in particular, Go-moku or 4×4x4 tic-tac-toe). I have always being fascinated by such an idea at least on the latter (Go-moku is too complicated for me
as well as writing a solver for connect-4 — Hopeuflly I’ll find some time later on to do that!
on September 7, 2007 on 1:31 pm
I am indeed teaching the course… although it will bear only theoretical resemblance to this checker-solving stuff (e.g., any such sentence will begin with “in principle”) and hopefully it won’t be underwhelmingly easy.
I’ve never heard of proof-number before, if you see this can you fill me in?
on September 7, 2007 on 2:03 pm
You can just Google the name. proof-number search or pn-search (improved variation of best-first search). There are at least five different variations with different trade-offs — very confusing. I tried to implement one version in the 4×4x4 tic-tac-toe game, but I haven’t gotten it to work properly