Mark Gritter (markgritter) wrote,
Mark Gritter

Yay for brute force!

Checkers has been solved by Jonathan Schaeffer of the University of Alberta. Article to appear in Science in 2007. (I have on my shelf an earlier paper on this work, from 1996.)

He has provided an online version of the proof--- you can query the endgame database and step through the games that the proof examined.

18 years of work to solve Checkers. The cost of computing halves every two years, following Moore's Law. Supposed that Schaeffer had a more-or-less constant research budget with which he leased computing power every two years, and that he was running continuously for those 18 years. That would mean that half the work got done in the last two-year period, and that the result could be reproduced for the same annual cost in just two more years!

More and more games are becoming feasible to solve. I think within a ten-year time window it will become feasible to start solving complete poker games. (Poker is somewhat harder because it is not perfect-information, but that only adds an order of magnitude or two. On the other hand, the number of decision points is typically much lower than other games.) Limit A-5 single draw lowball is probably the most tractable game to solve; I think if somebody with a research budget went after it we could see a result within 5-10 years.

In fact, I have been thinking of approaching KCL and A-5 in the same way I have looked at CP. Intsead of solving the game for the complete set of five-card hands, we can pick a substantial subsample and solve the game, then extend that solution for hands of interest in near-real time. (This would be more of a practical solution than a theoretical one, admittedly.)

(I am in no way dismissing the mental effort that went into solving the game. But the basic approach is pretty straightforward--- build and endgame database, figure out what positions in the start and midgame are equivalent or dominated, and then brute-force through the relevant positions until you hit the endgames.)
Tags: games, geek, poker, programming, theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment