Solved! Computer Scientists at University of Alberta Win Checkers

  • Thread starter siddharth
  • Start date
In summary, after 18-and-a-half years of research and sifting through 500 billion billion checkers positions, computer scientists at the University of Alberta have successfully solved checkers, creating a program, Chinook, that cannot be beaten. The program may only result in a draw, but it will never be defeated. While this is a significant breakthrough in database design and game theory, it is unlikely that a similar method can be applied to more complex games like chess. However, with the increasing speed and capabilities of computers, it is not impossible to see chess being solved in the future.
  • #1
siddharth
Homework Helper
Gold Member
1,143
0
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.
 
Physics news on Phys.org
  • #2
siddharth said:
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.
 
  • #3
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).
 
  • #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.
 
  • #5
I don't believe chess can be "solved." Strategy--which fundamentally rests on psychology--appears to be an essential element of it.
 
  • #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.
 
  • #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.
 
  • #8
Yay U of A :)
 
  • #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?
 
  • #10
SpitfireAce said:
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.
 
  • #11
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'.
 
  • #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.

scorpa said:
Yay U of A :)

I second that! :biggrin:
 
Last edited:
  • #13
dontdisturbmycircles said:
I second that! :biggrin:

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

1. How did the computer scientists at University of Alberta win at checkers?

The computer scientists at University of Alberta used a combination of artificial intelligence algorithms and machine learning techniques to develop a program called Chinook that was able to defeat the world champion checkers player.

2. What makes this achievement significant?

This achievement is significant because it demonstrates the power of artificial intelligence and its ability to solve complex problems. It also has implications for other fields such as medicine, finance, and transportation.

3. How long did it take for the computer scientists to develop this program?

The development of Chinook began in 1989 and the program was able to defeat the world champion player in 2007, a total of 18 years.

4. What is the potential impact of this achievement?

This achievement has the potential to revolutionize the field of computer science and artificial intelligence. It also has practical applications in various industries such as gaming, finance, and healthcare.

5. What are the future implications of this achievement?

This achievement opens up new possibilities for solving complex problems and improving decision-making processes through the use of artificial intelligence. It also raises ethical and societal questions about the role of machines in decision-making and the potential impact on human employment.

Similar threads

  • Computing and Technology
Replies
4
Views
921
  • STEM Academic Advising
Replies
6
Views
1K
  • General Discussion
Replies
4
Views
2K
Replies
10
Views
2K
  • STEM Career Guidance
Replies
15
Views
4K
Replies
17
Views
36K
Replies
21
Views
3K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
2K
Back
Top