Interesting positions, Warren! http://library.msri.org/books/Book29/files/schaeffer.pdf quotes Allis' 1994 definition of three levels of solving the game: 1) 'Ultra-weakly solved': the game-theoretic value of the opening position has been determined 2) 'Weakly solved': the game is ultra-weakly solved and a a strategy exists for achieving the game-theoretic value from the opening position, assuming reasonable computing resources 3) 'Strongly solved': For all possible positions, a strategy is known for determining the game-theoretic value, assuming reasonable computing resources One might criticise the definitions for including the word 'reasonable' but I don't really see any alternative. Allis cited the game of Hex as ultra-weakly solved but not weakly-solved. Nim and Tic-tac-toe are strongly solved. http://en.wikipedia.org/wiki/Solved_game gives other examples. Jonathan claimed on 2007-04-29 to have weakly solved Checkers, finding the opening position to be drawn and determining a strategy for both players to do so. For a game to be 'weakly solved' but not 'strongly solved', the proof must rely on the fact that some positions cannot be reached by 'minimaxing' play from the opening position. It would be interesting to hear Jonathan's own response to your position ... but I think he will say that - backing up your position to previous positions ... White would have easily won from those positions (by what is today a not very deep computer-search of the options). That is to say, if White is playing for the win, White would not have got itself into your position from a previous position. Nice try though! Guy Message: 1 Date: Sat, 2 Jun 2012 11:38:13 -0400 From: Warren Smith <warren.wds@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Checkers "solved"? Think so. Message-ID: <CAAJP7Y29d9C-EBivmmc+zPDFd46BqvfQSqymwT02EpwO=KJthQ@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Perhaps this has some amusement value. Can these examples be made even more dramatic than they are? ---- Here is a checkers position I created to annoy Jonathan Schaefer, leader of the "chinook" project which solved the game of checkers (forced draw). View in constant-width font. .W.W.W.W W.W.W.w. .w.w.w.. ........ ...b.... ........ ...W.... ........ W=white king, w=white checker, white is moving North. White to move. ?In this position, white has 8 kings plus 4 checkers, while black has only a single checker. Nevertheless, black soon wins the game. Here's basically the same thing backed up a little to make it a bit more amusing, black to move and win: .W.W.W.W W.W.W.w. .w.w.... ..b...B. .......B ........ ...W.w.. ........ In view of this, should the Chinook team still contend they solved checkers? I took a look at their paper in Science and it looks to me like they really did solve checkers. Their strategy was to use chinook search + heuristic evaluator + perfect endgame tables. ? They assumed (perhaps falsely) that a heuristic eval > X was a "win" and a heuristic eval < -X was a "loss." They then pseudo-solved the game. ?Then they increased the value of X and did it again. ?They only claimed a full proof once X had increased all the way to a genuine win. ? So this kind of counterexample shows you need to go a pretty long way and cannot cheat by using too-small X... but the chinook team claims not to have cheated (although I think their initial efforts had cheated in this way). Warren D. Smith http://RangeVoting.org