Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Checkers anyone?

  1. Jul 20, 2007 #1


    User Avatar
    Homework Helper
    Gold Member


    I wonder how long till chess is solved.
  2. jcsd
  3. Jul 20, 2007 #2
    I feel it is very unfair to compare chess to checkers. Checkers is very symmetrical with all pieces doing the same moves. This symmetry is badly broken in chess. Checkers has been "solved" by brute force, analyzing all possible positions on the board and their results, then forming a database. I am not sure they used that symmetry when the completed there database, but it would be quite a surprise if they did not.
  4. Jul 20, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    It's really more of a breakthrough in database design than game theory - being able to quickly search through a vast database of previously checked positions is invaluable for things like protein structure and combi-chem.
    Doing it first with checkers is just a way of getting public interest (and funding).
  5. Jul 20, 2007 #4
    It would be a true breakthrough in game theory if somebody could design a software to beat GO players. In that case, neither database, nor systematic search of possible next moves can help.
  6. Jul 20, 2007 #5
    I don't believe chess can be "solved." Strategy--which fundamentally rests on psychology--appears to be an essential element of it.
  7. Jul 20, 2007 #6
    Oh, it MUST be able to be solved by its very nature IMO. There are a finite number of possible games. Though that number is quite massive, nearly beyond comprehension, so long as it is finite it is solvable.

    If you read it, the way they solved checkers was working backword from one final piece and finding all the possibilities. Then they pretty much noticed that at 10 pieces left, they had every possible solution mapped out and it was possible to ALWAYS draw or win if you played correctly.

    I assume the same could be done with chess, its just merely more rules and more moves.

    So of course it then becomes not a matter of whether or not it CAN be solved, but whether or not, as an intelligent, computer-desiging species we are ABLE to solve it.
  8. Jul 20, 2007 #7
    It is significant that they found that the perfectly played game is a draw. If they had found otherwise, I believe it would have taken a lot of the drama out of the game.

    If a game is such that there are only finitely many positions possible, then the game is theoretically solvable. This includes chess and go. However, the number may be so large as to make it impractical. If the program is to check each one of the possible positions, then chess and go are unsolvable in this sense for there are simply too many positions. The checkers solution did not involve inspecting every position. It may be that chess and/or go can be solved without looking at every position too.
  9. Jul 20, 2007 #8
    Yay U of A :)
  10. Jul 20, 2007 #9
    when they say the program can analyze 500,000,000,000 positions... I'm guessing this is every possibility in checkers... is this the same method that programmers have used to create incredibly strong comps like Deep Blue, by programming in as many positions as possible?
  11. Jul 20, 2007 #10
    The article states that they did not evaluate every possibility. Deep Blue does not evaluate every possible possition to make its moves. It cannot because there are too many to evaluate.
  12. Jul 20, 2007 #11


    User Avatar
    Gold Member

    I wonder if the chess thing might be better tackled by a quantum computer. It seems to be closer to human in its manner of 'thinking'.
  13. Jul 20, 2007 #12
    I cannot pull up the OP's article for some reason.

    I think it is very important to realize that they only 'solved' the game of checkers after there are only 10 pieces left on the board(http://www.usatoday.com/tech/science/mathscience/2007-07-19-checkers-solved_N.htm?csp=34). Which still leaves a tremendous amount of possibilities to be worked through(I mean that solving the game with only 10 pieces on the board is still a huge feat). But I think it is clear that with chess as opposed to checkers, there are many many ways to end up with 10 pieces on the board and since each piece tends to have much more freedom than a checker(is that the correct term? :rolleyes:), the possibilities are much greater in number. It took 19 years to solve to a depth of the moves available with 10 pieces left on the board. It's not even fathomable to do that with chess, at least not soon (in my opinion). Not to mention that there are many ways to win a game of chess when there are many more than 10 pieces left on the board, which complicates things A LOT.

    But with computers getting faster and faster, they are able to calculate so many moves so fast that tactically they can beat any of the top players on a very regular basis. Strategically they are not as good yet though.

    I really don't believe we will see chess 'solved' any time during my life time. But I try to never say never.

    I second that! :biggrin:
    Last edited: Jul 21, 2007
  14. Jul 21, 2007 #13


    User Avatar
    Gold Member

    Thirded here. Although Cowtown and Edmunchuk have an outstanding rivalry, I can't deny that the academic environments are both awesome.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook