Checkers program unbeatable by humans, other computers

by John Bardinelli { Jul 21st 2007 at 1:29PM }

The computer program Chinook has been vanquishing human opponents in checkers for over ten years. Now, scientists at the University of Alberta (Chinook's home) say they have improved the program so that it can never lose. EVAR! No opponent, whether human, bacterium, or computer, can win when facing Chinook. In other words, checkers can be retired to the Pit of Practically Useless Games along with tic-tac-toe. The strategy behind checkers (which has over 500 billion possible board combinations) has been solved.

If you're a masochist, you can play against Chinook online. Only 24 games can be active at once, so you'll have to wait your turn to lose like a little baby.

Tags: checkers, chinook

Reader Comments (Page 1 of 1)

eelb @ Jul 21st 2007 1:38PM

if nothing can lose or draw against chinook, then what happens when chinook plays itself? or does chinook always get the first go?

Hirsbrunner @ Jul 21st 2007 1:43PM

Good question. Does getting to go first ultimately decide the outcome? Or does it matter?

If not, I'd like to see the game between two independent Chinooks. THE ULTIMATE CHECKERS SHOWDOWN! On pay-per-view. ORDER NOW!

Joe S. @ Jul 21st 2007 1:45PM

The main idea when "solving" a game is to be at the point where you will never lose in the game. Coming to a draw is consistent with that idea; nobody wins, but at least you didn't lose. If Chinook played itself, assuming it has solved checkers as stated, it would draw every time.

comtar @ Jul 21st 2007 1:53PM

The only way to win is not to play.

Rare Hare @ Jul 21st 2007 9:58PM

@comtar: It's impossible to win something without playing, man. That doesn't make sense.

k0sm0s @ Jul 22nd 2007 6:08AM

Chinook vs chuck norris, who would win?

Chuck Norris. He took only one turn.

faceless coward @ Jul 22nd 2007 9:36PM

Yeah, right. One look at a checker board and Chuck Norris would be in bed with a throbbing headache, sucking his thumb and crying himself to sleep.

Anthony M @ Jul 21st 2007 1:41PM

From the article:

"Any opponent, human or computer, no matter how skilled, can at best achieve a draw."

Gregory Kimball @ Jul 21st 2007 1:42PM

First Checkers, then Chess, and finally the human race. Once they have our board games, there is no escape.

Noshino @ Jul 21st 2007 1:50PM

NOOO! WE CAN'T LET THEM LEARN MONOPOLY!! or Life...NOO!!

Kye @ Jul 21st 2007 1:42PM

I bet I could beat it. been playing checkers with old people since I can remember. Whats this website? Let me go crash their internets.

Admiral_Mike @ Jul 21st 2007 1:48PM

I won't be impressed until it beats a guy at pokemans

joe @ Jul 21st 2007 1:58PM

Actually, checkers has more than 500 billion billion possible outcomes. Das alot

Anonim @ Jul 21st 2007 2:01PM

Short or long scale?

3cubedminus3squared @ Jul 21st 2007 2:02PM

I just got done playing it.
At first we were neck and neck, then out of nowhere it starts kicking my ass.
I lost, but at least I only left him with three pieces.

Markusdragon @ Jul 21st 2007 2:06PM

Damn. I almost beat it (until it used my own tactics against me D:

rockeranimefreak @ Jul 21st 2007 2:12PM

hmm but can it beat me in Street Fighter??:P

Fernando Rocker @ Jul 21st 2007 2:21PM

Speaking of this... in what game do you guys thinks you are unbeateble?

For my part... Im very good in Mario Kart Double Dash, very good, and I can avoid blue shells.

Guitar Hero (five stars in every song in expert, excpet the last tree song with 4 stars)

Smash Bros (not expert in Smash, but above the average).

Kye @ Jul 21st 2007 2:31PM

Mario kart 64. Simply must be the world's best as EVERYONE who has ever challenged me has failed miserably. At one point, if I got any weapon, even 1 banana everyone near me would jump off the track cuz I wouldn't miss. I only recognise one near-equal and thats the guy I practiced (sometimes over 8) hours a day with for years.

Street fighter. Not the best but you gotta be shit hot to beat me.

James Bond: Agent Under Fire. NGC. If you try to even understand my skillz you'll probably end up retarted.

Not being arrogant, but I am very good at those games.

Fernando Rocker @ Jul 21st 2007 2:34PM

Kye... its going to be interesting play against you in Mario Kart Wii =)

Kye @ Jul 21st 2007 3:04PM

Disclaimer:

I have logged hundreds of hours on MK64.
The same level of skill will no be transferred to MKWii. Besides, I had ALOT more free time back then.

But still, I welcome your challenge.

Intentless @ Jul 21st 2007 5:46PM

I find it better to be a challenge in all games than to be the best in one.... cept my one buddy that it doesn't matter... give him a game and he will dominate it...

Charles @ Jul 22nd 2007 8:30AM

Puzzle Fighter - I learned by watching this guy in the arcade who seemed to never lose and by (me) spending way too many quarters in machine. It's been one of my prized possessions since its release on the PS1.

Quakeulf @ Jul 21st 2007 2:21PM

Let's see it try the Japanese game "Go", or "Shogi".

hvnlysoldr @ Jul 21st 2007 3:26PM

Correct. There are currently no good Go computer programs. If checkers has 500 billion and that's determined by 64 squares, how many moves and combinations and chains are possible in Go with many more squares?

Skunk @ Jul 21st 2007 2:39PM

I just had to say this with that watermark up ahead

ALL YOU BASE ARE BELONG TO US

Kye @ Jul 21st 2007 3:08PM

OK Chinook just whooped my ass. But I'm going in with an offensive strategy this time.

Poisoned Al @ Jul 21st 2007 3:12PM

What, you are FORCED to make jumps in the US version? No wonder it has been cracked. If it could beat English checkers I would be more impressed.

Gambit @ Jul 21st 2007 3:23PM

Indeed. I never played like that (having to jump a piece) the whole time I was growing up. Then when I was in high-school a guy I was playing with was like, you have to jump that, and I said WTF, since when!

hvnlysoldr @ Jul 21st 2007 3:27PM

I had always played it the err English way. You totally screw people up if you have to force them to jump.

Rare Hare @ Jul 21st 2007 10:02PM

Forced jumps are most definitely fucktarded.

k0sm0s @ Jul 22nd 2007 4:11AM

hmm, i thought forced jumps are a general rule.. we always played by that rule

ps. love the picture XD.. all your checkers are belong to us

Kye @ Jul 21st 2007 4:00PM

You think that's hard. try playing it the (certain parts of the) Caribbean way. Where if you don't take a piece when you have a chance, you loose yours!

Anyways, I my offensive strategy was reckless. I lost even worse.
I concede defeat. *tear*
Now, where's that weekly webcomic wrapup?

mike @ Jul 21st 2007 4:38PM

game like checkers which can teoretically be played perfectly, can be conqured like it now has. The computer can caluculate every move that is possible and every outcome, so it can never lose. Take a look at the game tic-tac-toe. Thats a simple game that you yourself (no computer needed) can calculate very possible move ever, ensuring that no matter what, you only tie or win. Even in games like chess, they too will someday be mastered by a computer where it is no longer possible for any other computer or human to beat it. Only tie and lose. Our computers are just not there yet for a game like chess, but they will one day.

Now take a game like MK64 mentioned above. No matter how could you are (computer or human), You will never become a champ where you can claim that you can NEVER lose. the reason for this is because of factors of chance in the game, which are the item boxes. They are random thus providing a random outcome. However, if the item boxes were not random, it would be be possible to program a computer to play the game and calculate every poistion and point in space and movement to enure that it never loses (although I dont think todays computers could handle that). But witht he element of chance, it will never be broken. Same reason monopoly and life wont be broken ever. Im sure computer can be made to be near unbeatable in these types of games, but not like this were theyc an never lose.

hvnlysoldr @ Jul 21st 2007 4:54PM

Do it like Data. He beat the ultimate tactician by not trying to win but instead drawing or delaying. Completely infuriating the tactician who only had the motivation to win and expected the same from Data.

Rare Hare @ Jul 21st 2007 10:05PM

Data is such a badass.

Bluebreaker @ Jul 21st 2007 8:01PM

@hvnlysoldr

I remember that episode. I don't think it work against Chinook though. They should pit Deep Blue and Chinook in a puzzle game deathmatch though.

Arturo @ Jul 21st 2007 10:54PM

I remember reading about this in my local paper. They said if it played it self it would always conclude to a draw because to play perfectly is to avoid defeat and if they both do that without mistakes there is no winner.

Heliophage @ Jul 22nd 2007 12:12AM

I got it down to 1v1, king v king. I think I can be proud of that, seeing as how I'm playing against a *perfect* checkers player.

fush @ Jul 22nd 2007 2:44PM

This is stupid. All they did is start at each end game scenario and work backwards to find all the possibilities and the best move at every point.

There is no ingeniously designed algorithm, only a big database which it asks at every moment, "okay, what do I do now?"

John @ Jul 22nd 2007 3:23PM

I was actually following one of the games going on late last night and Chinook actually lost the game. Its opponent had 6 kings as compared to chinook's 2 kings and Chinook got owned.

They probably attribute its loss to a glitch huh? The game was #16 and its opponent was "abc Qwerty." Maybe it was another program?

Zachary @ Jul 23rd 2007 1:17AM

As a University of Alberta computing science graduate student, I would like to clarify a few things regarding the Chinook program:

1) When playing Chinook online at www.cs.ualberta.ca/~chinook, you are prompted to select one of three difficulty levels; novice, amateur or intermediate. The names themselves imply that the program is not running at full strength when you play it. The program is, however, still fairly competitive even at these lower levels.

To clarify, you will NOT be playing against a perfect computer program through the website.

2) In checkers, if someone plays perfectly then they can never lose. However, this is NOT true for all combinatorial games. For example, it is well known that a perfect computer program can always force a win if it starts in the game connect four (check it out on Wikipedia). Thus, if a perfect computer program played itself in connect four, the first player would win and the second player would lose.

If you are in a position where the other player can force a win, then even perfect play can't break you out of that disadvantage. You can only hope that the player who is forcing you to lose will blunder.

3) One does not need to check EVERY possible sequence of moves to solve a game like checkers. Algorithms exist that examine only a fraction of the possible moves and still produce the correct answer. A simple example is if a winning move is found, then other moves don't need to be considered. However, this idea can be extended much further than this. I invite the more technically-minded to Google the alpha-beta pruning algorithm.

And, sorry to single you out 'fush', I take exception to calling this result "stupid". You should take care to read how the result is presented on the website. It is not a simple database. The notion of storing the entire sequence of moves in a perfect play in a database is ludicrous given our current technology. And if there was such a database, how do you think it would be generated? Obviously using some "ingeniously designed algorithm"! Many entries in the database refer to the fact that a search had to be carried out to prove the result... sounds like an algorithm to me! Please take care to respect the hard work of others before you sound off.

Bluebreaker @ Jul 23rd 2007 7:07AM

Um, just out of sheer curiosty what was the point in trying to make the ultimate checkers program in the first place?

Zachary @ Jul 23rd 2007 8:54AM

I can't speak for the personal reasons of Jonathan Schaeffer or any of the other authors, but there are a few obvious reasons. In developing the program, numerous research papers were published along the way. Much can be learned from the Chinook program in how to build a robust AI program. Academic applications aside, it's just a neat result to know that computers can solve checkers and such results often get a fair bit of mainstream attention. The fact that this result appeared in joystiq.com is a testament to this.