Solved! Computer Scientists at University of Alberta Win Checkers

[siddharth]

Game over. Computer scientists at the University of Alberta have solved checkers, the popular board game with a history that dates back to 3,000 B.C.

After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten. Completed in late April this year, the program, Chinook, may be played to a draw but will never be defeated.

(http://www.physorg.com/news104073048.html)

I wonder how long till chess is solved.

 

[humanino]

I wonder how long till chess is solved.

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.

 

[mgb_phys]

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).

 

[humanino]

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.

 

[Knavish]

I don't believe chess can be "solved." Strategy--which fundamentally rests on psychology--appears to be an essential element of it.

 

[K.J.Healey]

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.

 

[Jimmy Snyder]

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.

 

[scorpa]

Yay U of A :)

 

[SpitfireAce]

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?

 

[Jimmy Snyder]

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?

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.

 

[Danger]

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'.

 

[dontdisturbmycircles]

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? ), 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.

Yay U of A :)

I second that!

 

[Danger]

I second that!

Thirded here. Although Cowtown and Edmunchuk have an outstanding rivalry, I can't deny that the academic environments are both awesome.