Jump to content
  • entries
    106
  • comments
    796
  • views
    139,434

Checkers Solved

Sign in to follow this  
vdub_bobby

839 views

TOOK THEM 18 YEARS, but they did it: they solved checkers.

The game of checkers has roughly 500 billion billion possible positions (5 x 10^20). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw.

Thought Zach, especially, would be interested in this. :)

Sign in to follow this  


8 Comments


Recommended Comments

Its good to know that the game is perfectly balanced. If you lose, you know its because you made more mistakes than your opponent.

Share this comment


Link to comment

Hm... how does this work? At the beginning for example, are all openings equal, or is there already a "perfect" opening required?

Share this comment


Link to comment
Hm... how does this work? At the beginning for example, are all openings equal, or is there already a "perfect" opening required?

Why would you need to know that when using Brute Force? ;)

 

BTW: I suppose when they had started 1 year later, that would have solved the game just one week later. ;)

Share this comment


Link to comment
Hm... how does this work? At the beginning for example, are all openings equal, or is there already a "perfect" opening required?

Why would you need to know that when using Brute Force? ;)

 

Uihjah, I was actually confusing checkers with chess ;)

 

Anyway, my question was still answered here:

 

Hierfür ließen die Informatiker Spielstellungen mit 10 Spielsteinen und weniger zusammen mit den 19 relevantesten Spieleröffnungen auf dem Brett analysieren, wobei sie über 39 Billionen Stellungen untersuchen mussten.

 

So they only computed endgames of 10 pieces and less for the most relevant openings.

Share this comment


Link to comment

I am indeed interested to hear about this. It's interesting that checkers was so much more difficult to solve than Connect-4, even though for non-perfect play it's easier to compute heuristics for checkers. In checkers you can just count pieces to get a pretty good idea who's ahead. In Connect 4 you have to search for patterns. On the other hand, it is the search for patterns that makes Connect-4 easier to solve completely.

 

I wonder how much longer until we see unbeatable checkers on home computers?

Share this comment


Link to comment
I wonder how much longer until we see unbeatable checkers on home computers?

 

In the meantime you can already play against unbeatable "Nine Men's Morris" computer players ;)

Share this comment


Link to comment
I wonder how much longer until we see unbeatable checkers on home computers?

 

What would be the point? One of the reasons I think 4x4x4 tic-tac-toe was a popular computer game was that while it is winnable by the first player (and the computer versions I've seen let the human go first) eking out a win isn't easy (unlike 3x3x3 tic-tac-toe where moving to the center makes the game an easy win for the first player; disallowing the first player from moving to the center but letting the second player go there makes it an easy win for the second player).

 

I suspect the decisions to release both Stellar Track and 3D Tic Tac Toe were based upon the popularity of the underlying mainframe computer games.

Share this comment


Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...