Checkers Solved
News that Checkers (aka "Draughts") has been solved by brute force computer analysis. I have a feeling that we're coming to the end of the era of long-lasting games that are based on complete, perfect information with no randomness. (Meaning that maybe games need to have incomplete, hidden information and/or randomness to avoid being completely solved.)
That said, maybe Chess is still safe for a while. I heard somewhere (lost the source, sorry) that if every particle in the universe could somehow be used to compute one operation per second and that all the particles in the universe were used in a massively parallel computer that analyzed all possible positions in Chess, it would take longer than the current estimated age of the universe to finish. So yeah, pretty long.
--Sirlin
July 20th, 2007 at 8:14 am
I would think that Backgammon will fall soon as well. I remember doing some calculations a few years ago that indicated that it was feasible to store all possible backgammon positions.
July 20th, 2007 at 9:39 am
I think that last estimate about Chess was probably made up… maybe if you take into account all possible board positions, even illegal ones, but I don’t believe Chess is supposed to have that many actual possibilities. Go is of course a different story. If Chess ever does fall as a broken game, I’m willing to bet children will still be able to beat the best Go computers. Heck, I’ve not even met a Go bot that could get past mirror Go. I would strongly urge any Chess players(or anyone interested in a, um… how did he put it… “games that are based on complete, perfect information with no randomness”) to check out Go. Chess, to me, feels like two people were playing Go, and quit halfway through, and have left you to clean up after them. I don’t know why I’m making this comment… I guess to advertise for Go. I do that a lot. I guess I might as well go ahead and advertise for the kgs server: http://www.gokgs.com/ . They’ve got a java client you can launch from the website. It’s a great server as long as you don’t like talking(public chats are heavily censored, and you will get banned for talking about anything that isn’t Go). Anyway, if anyone wants an introduction to the game and some training matches, just send me a message at KevinJRussell@GMail.com , I’ll be glad to teach you.
July 20th, 2007 at 9:48 am
This is the saddest day since I learned how to do that in Tic Tac Toe…
July 20th, 2007 at 8:16 pm
I expect that Backgammon will fall soon also. It might actually be smaller than checkers.
July 20th, 2007 at 9:00 pm
Honestly I find games of complete information more interesting. Situations in Street Fighter where the challenge is to select the best solution to a problem from a variety of options, force your opponent into situations where even their most viable option is weak, and psychologically limit the ability of your opponent to accurately recognize the best option at any given time are more interesting to me than simple guessing game situations, which, while definitely requiring skill over the long term, can in any individual instance be determined more by luck.
July 20th, 2007 at 10:19 pm
NateTG,
Backgammon does not fall into this category of game as it involves dice and therefore contains a random element. I conjecture that there are more possible games of Backgammon than there are of chess (this is a complete guess on my part with only 5 seconds of thought, so, please prove me wrong (; )
July 20th, 2007 at 11:56 pm
Tenebrae - AFAIK Backgammon is not guaranteed to terminate, so the number of games is potentially infinite.
However, the number of possible backgammon positions is finite:
18,528,584,051,601,162,496
That’s roughly 2^64:
18,446,744,073,709,551,616
That’s about 9000 Googles in data - and much larger than those five billion checkers positions. So, with Moore and Kryler’s laws, I guess it’s about 20-30 years out.
July 21st, 2007 at 6:52 am
On first glance, it doesn’t seem obvious how having randomness would, by itself, make a game harder to “solve”.
Hidden information is more promising direction for solution-avoidance. But only certain types of hidden information. Chess where every square contains a face down card, half of which give you an extra turn when you land on them, isn’t harder to solve in a meaningful way.
The type of hidden information that adds insolubility is the kind contained in simultaneous moves. When you have to make a decision whose value is determined by the decision your opponent is going to make at the same time. The real important hidden information is the information hidden in your opponent’s head. This is where any brute force approach will fall short - the strangely loopy process of applying judgment to judge the judgment of other judgers, to analyze the analysis of other analyzers, to algorithmically evaluate the evaluative algorithms of… well I guess you get the idea.
In a word: Yomi.
July 21st, 2007 at 9:32 am
I think you can brute force simultaneous moves; you search through strategies until you find one which is optimal against a strategy optimal against itself (such a strategy always exists, and if it loses the game then every strategy loses). Its certainly more computationally intensive, but the only difficulty is if there are infinitely many essentially different viable mixed strategies, which is not normally the case in actual games and might never be the case.
The kind of hidden information in bridge (ie, your own past decisions are hidden from yourself) also adds a lot of computational complexity.
I don’t think Chess or Go or perhaps even Checkers will be broken as a competitive game if computers know how to play. I do think Checkers was already pretty broken at high levels though (I am told there are players who draw essentially every game?)
July 21st, 2007 at 11:23 am
To Animate Dreams:
You have no clue what you’re talking about; your thinly-veiled advertisement for Go play and training was preceded by a number of comments showing a complete lack of understanding of chess.
I have the title of expert at chess (rating 2030), and looking at the massive strides computers have made in playing ability in the last twenty years, I think that in twenty more years, humans will no longer be able to win against them.
Fifty years from now, I’d be shocked if the game wasn’t completely solved.
July 26th, 2007 at 2:18 pm
To Mark James:
His comments were not derogatory towards chess, nor do they show a lack of understanding of chess. His advertisement for Go is quite well justified, and just a matter of opinion. Just because someone likes their toy more than yours is not a slight on you personally. I recommend you give Go a try, and see why he, and myself, like it better. A few of my personal reasons: (note: I’m capiltalizing ‘Go’ so it isn’t confused with the verb go, not pretentiousness.)
1. Rules are simple. Chess has a lot of set rules (each pieces movements, en passant, castle, check) in a small (8×8) space, but in Go you have two very simple rules in a larger (19×19 standard, 13×13 and 9×9 are also played) space. The former leads to a few quickly discovered rules (forking, pinning, and opening patterns) while the latter leads to many, ever increasing in complexity situations (ladders, seki, live vs dead shapes, attacking a shape in a life or death situation, joseki). The overall games are more organic, and studying the game gives far more opportunities for the student to learn something that is usable in every game. I love ‘a-ha!’ moments, and Go provides more of them for me.
2. Balance. White has an obvious and very serious advantage; everything else in chess is completely equal, except for the initiative white gets by moving first. Black has the same advantage by being able to go first, but this is balanced out by the 5.5 point penalty to the final score. By balanced out, I mean the records of thousands of professional games show the black winning percentage to be within less than 1/2 of 1% of the white winning percentage, and I’m really not sure which side is getting the fraction of a percentage more wins. Winning percentage was just over 1% higher for white when the penalty was 6.5. (my numbers on this may be wrong. If you like, I’ll cite some specific numbers. The point is, there is no counterbalance in chess to white’s initiative advantage, while there is in Go.)
3. Handicap. Playing against weaker opponents in chess doesn’t have any set or measureable way of handicapping. You can remove some of the stronger player’s pieces in the beginning of the game, but there is no measure of how or which or what the effect is. Without even a specific pawn on the stronger players side, it becomes an entirely different game for the stronger player, and for the attacking player. You’re changing the core of the game, and any tactics learned by either player would be of very limited use in a real game. You could let the weaker player move X number of times before you move, but letting them move more than 3 times gives them an instant win by playing fool’s mate. Go doesn’t have these problems. A weaker player gets X number of stones initiative in a set formation (where 1
July 26th, 2007 at 2:33 pm
(sorry, it got cut off)
(where 1
July 26th, 2007 at 3:24 pm
(last time, swear. My bad.)
(where 1
July 26th, 2007 at 3:28 pm
Sirlin, it seems the comments cut off at a ‘greater than’ symbol. FYI.
(where x is 2 through 9 inclusive). The game doesn’t change for either player; the tactics and moves are the same, allowing both players to play their best in an enjoyable, and even, game. Each stone advantage given to the weaker player equates to roughly a 10 point handicap; so if I won over an opponent in an even match by 40 points, letting them have a 4 stone handicap in the next game would make the game far more even. Each stone is also considered one rank’s difference. A 20 kyu player against a 15 kyu player could expect a 5 stone handicap.
Barring trying Go, may I recommend you look into shogi? It’s quite a bit harder to get into than Go, and frankly, a lot harder to get good information on unless you speak Japanese. But it’s well worth the effort. The playfield is larger (9×9 versus chess’s 8×8), the piece movements are more varied, and captured pieces can be placed on the board under your control (in lieu of a normal movement). The overall gameplay is far more varied than your usual chess matches, but at it’s core, it is chess.
In the end, all that matters is that you enjoy whatever you play. There is no need to get defensive because others don’t consider your favorite their favorite. Try ‘em all.
July 26th, 2007 at 10:43 pm
Rock paper scissors will never be solved.
We’re in luck.
Oh and by the way, i’ve heard that one of the best Poker (Texas hol’em) gamers are currently trying to win against a computer. Or vice versa, depends on your opinion. (I’m with the computer)
July 28th, 2007 at 7:02 am
The professional players won. It seems like it was a close match though. You can the check the details of the match here: http://www.poker-academy.com/man-machine/results.php
July 28th, 2007 at 3:05 pm
Is it bad that I can’t stand classical perfect information games? I’ve always admired the intellectual virtuosity that surrounds them, but in the actual playing I always find them incredibly dull, so that any purported depth of play is just a high summit in the distance, little more than a backdrop.
It reminds me of a spelling bee, or a pi-memorizing competition. Certainly I can appreciate it, and certainly I could devote a great deal of time to becoming better in a very real way, but I have to wonder why? I don’t want to memorize board patterns or plot moves turns and turns ahead or do any of these masterful feats that the greatest Chess and Go players seem capable of. The whole idea toys with notion of why people play games, but I have a hard time conceiving of why anyone other than those with a predisposition for the mechanisms of Chess or Go would want to play them. Not particularly different from a competition to memorize digits of pi - I can’t see why anyone other than those with immense capability to memorize linear strings of digits would bother. For the most part they don’t.
It’s frustrating though because as a fan of games I feel tantalized by some kind of intellectual Shangri-La that I will never achieve because I lack the discipline, skill, and basic desire to be any good at the greatest of games.
Occasionally I see Go players taunt Chess players that their game is more complex and rigorous, and that Go will eventually surpass Chess. And you know, that kind of complexity brinksmanship makes me feel weirdly uncomfortable. Is our destiny to all struggle to barely learn intermediate level Super-Go-Chess, which is so complex only savants can play it at a high level?
We all have our favorite games, I suppose. I kind of just wish I cared about Go or Chess, seeing as how they seem to have a monopoly on prestige. Give me dice or a deck, and no Russian/Japanese masters whose eyes can etch stone.
September 5th, 2007 at 3:30 pm
I wasn’t aware Go had such close win % between the colors. Does anyone have references for white and black win %s in a specific country/league?
March 6th, 2008 at 8:24 am
<strong>Free Computer Security Software - A Leaking Seal!</strong>
There is nothing wrong with taking less than adequate measures to prevent a bigger damage to anything you treasure if you have financial or other constraints, as long as this is done temporarily over a short time. Similar reasoning applies when it come…