• entries
106
796
• views
139,434

# Checkers Solved

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.

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

I, for one, welcome our checkers-playing overlords...

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

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.

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.

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?

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

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.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.