Checkers was weakly solved 2007: a question
Moderator: Ras
-
Jouni
- Posts: 3715
- Joined: Wed Mar 08, 2006 8:15 pm
- Full name: Jouni Uski
Checkers was weakly solved 2007: a question
Has anybody verified result so far? With current hardware it should be possible using home PC in hours/days or not? Only 10exp20 positions possible.
Jouni
-
Ajedrecista
- Posts: 2145
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Checkers was weakly solved in 2007: a question.
Hello Jouni:
I am not aware of a formal verification.
5e+20 is more less the search space complexity of the game. As far as I remember, the solution was not to check each possible position, but generate 10-man EGDB (endgame databases), then prove that starting from the standard starting position, Chinook could find a path to a drawn position of an EGDB from a set of openings (the 3-move restriction, widely used nowadays). I do not know if all the 3-move openings were tested; GAYP style (go as you please, play whatever you want from the start) should be proven drawn by Chinook.
I can be wrong in some details, but the key idea was finding drawing paths from the opening book to the EGDB. There is an excellent book from the project leader, Jonathan Schaeffer, titled One Jump Ahead: Computer Perfection at Checkers, which describes the whole project over the years.
Regards from Spain.
Ajedrecista.
I am not aware of a formal verification.
5e+20 is more less the search space complexity of the game. As far as I remember, the solution was not to check each possible position, but generate 10-man EGDB (endgame databases), then prove that starting from the standard starting position, Chinook could find a path to a drawn position of an EGDB from a set of openings (the 3-move restriction, widely used nowadays). I do not know if all the 3-move openings were tested; GAYP style (go as you please, play whatever you want from the start) should be proven drawn by Chinook.
I can be wrong in some details, but the key idea was finding drawing paths from the opening book to the EGDB. There is an excellent book from the project leader, Jonathan Schaeffer, titled One Jump Ahead: Computer Perfection at Checkers, which describes the whole project over the years.
Regards from Spain.
Ajedrecista.