One more game you cannot win...

July 19, 2007 7:02 PM

For nearly two decades, fifty computers have been running day and night on an extremely complex problem. Today, scientists from the University of Alberta announced the result of all that work - they have solved the game of checkers. Chinook, the computer program they developed, can never be beaten - try for yourself. While checkers is the most complicated game to be solved so far, it is not the only one. You can play a perfect game of tic-tac-toe, of course, but also connect four, and a 6x6 board of the game othello. Chess players are already thinking ahead to when their game is solved, with Advanced Chess being Gary Kasparov's answer. The hardest game to completely solve might be Go, which may not be solved until 2100.
posted by blahblahblah (76 comments total)

Argh, beaten to the main story by a few minutes, but the rest of the post on solvable games is undoubled and unbowed, for what its worth.
posted by blahblahblah at 7:04 PM on July 19, 2007

Even if it's better than the first, it's still a double.
posted by mds35 at 7:06 PM on July 19, 2007

Your post is better than his.
posted by Aloysius Bear at 7:06 PM on July 19, 2007

Yeah, beaten by a bit, but higher quality. Just post it as a comment?
posted by a robot made out of meat at 7:07 PM on July 19, 2007

One more game you cannot win.
posted by ColdChef at 7:09 PM on July 19, 2007 [4 favorites has favorites]

Since when were we a first past the post system? This is a good post.
posted by absalom at 7:11 PM on July 19, 2007 [3 favorites has favorites]

It's amazing that it was solved twice within half an hour. Only on Metafilter, the place celebrities go to die repeatedly.
posted by acetonic at 7:12 PM on July 19, 2007 [3 favorites has favorites]

This is an excellent post. I am going to favorite it.

Now that the Canadians have solved checkers, now they should try to solve Trouble. It's Pop-O-Matic.
posted by Slap Factory at 7:12 PM on July 19, 2007 [1 favorite has favorites]

What a completely unhelpful thing to do to advance the state of AI. It's a database.
posted by blacklite at 7:15 PM on July 19, 2007

I vote to keep this one.
posted by Samuel Farrow at 7:21 PM on July 19, 2007

I should be gracious and say I don't mind if mine is deleted because this is clearly superior! I'm told this will increase my standing with the elusive game-theory-nerd demographic.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:21 PM on July 19, 2007 [3 favorites has favorites]

What a completely unhelpful thing to do to advance the state of AI. It's a database.

Actually, that's still useful.

Schaeffer notes that his research has implications beyond the checkers board. The same algorithms his team writes to solve games could be helpful in searching other databases, such as vast lists of biological information because, as he says, "At the core, they both reduce to the same fundamental problem: large, compressed data sets that have to be accessed quickly."
posted by danb at 7:23 PM on July 19, 2007

Uh, I beat it. Guess they have to start over?
posted by notmydesk at 7:30 PM on July 19, 2007

As much as draughts is a silly game (read: I'm crap at it), I can't help but think of these blokes as spoilsports.
posted by pompomtom at 7:43 PM on July 19, 2007

"The program on this site is the champion but it has been reduced in strength to allow you to "have a chance" at drawing. This program does not include the solution to checkers. If you are good enough, you might even win! Good luck!"

It's a scaled down version...still fun though!
posted by Bistle at 7:44 PM on July 19, 2007

What a completely unhelpful thing to do to advance the state of AI. It's a database.

True, but when databases were initially developed, that was AI. As they became widely used, folks muttered, "but that's just bookkeeping. That can't be AI." Then expert systems came along, and that was AI. And the response was, "but that's just rule chaining and boolean logic. That can't possibly be AI, either." Then back-propagation neural nets were developed. "But that's just hill climbing. You can't expect us to believe that that's AI." Fuzzy logic? "Fudged expert systems." Genetic algorithms? "Eh, hmm, nah, doesn't sit right."

So nothing will ever advance the state of AI, because once a technology becomes well-studied enough, it's considered banal and thus no longer what we're currently arrogating as AI. And that's the story of why I ditched academia and got a real job.
posted by phooky at 7:47 PM on July 19, 2007 [8 favorites has favorites]

Is anyone working on Connect Four?
posted by mds35 at 7:53 PM on July 19, 2007

^ mds35, from the post.
posted by churl at 7:56 PM on July 19, 2007

The only winning move is not to post.
posted by Poolio at 8:05 PM on July 19, 2007 [2 favorites has favorites]

This is a great example of a superior post. I hope most sincerely that it won't be deleted; the prior should go, if any.
posted by Malor at 8:18 PM on July 19, 2007

I don't believe that Go will ever be "solved". The problem space is too big; I think it exceeds certain hard physical limits inherent in the physical universe. (Which is to say, I don't think there are enough atoms in the universe to store all the intermediate data which would be needed in order to solve the game of Go.)
posted by Steven C. Den Beste at 8:21 PM on July 19, 2007

After losing to Chinok for the 100th time, I smashed my computer in rage screaming, "King this jerkwad." Suprisingly Chinok was not prepared for this move, which I learned from my kid brother when I was 12 and he was 7. Now all I have to do is wait for mom to tell chinok to let me win for once.
posted by humanfont at 8:43 PM on July 19, 2007 [1 favorite has favorites]

Contrarily, I think Go will be solved eventually. Not in the next year or so, but eventually, within our lifetimes even.
posted by edgeways at 8:44 PM on July 19, 2007

How about a game of global thermonuclear war?
posted by papakwanz at 8:44 PM on July 19, 2007

50 Computers? 20 years?!

Were they using Commodore 64s or something?
posted by uncanny hengeman at 8:55 PM on July 19, 2007 [3 favorites has favorites]

I think it exceeds certain hard physical limits inherent in the physical universe.. I don't think there are enough atoms in the universe to store all the intermediate data

A quantum bit can hold more information than an atomic bit.
posted by stbalbach at 8:58 PM on July 19, 2007

Don't bother posting, pretty soon they'll have a computer that does THAT better, and faster than you too.
posted by blue_beetle at 9:09 PM on July 19, 2007

Go is unsolvable.

Think about it. You play Go on a 19x19 board (none of that pussy 9x9 or 12x12 crap). There are three possibilities for each spot - black, white, and blank. This means that there are 3^361 possible boards, minus the number of boards that could never exist because they would be contradictory.

Chess, on the other hand, is played on an 8x8 board, with 33^64 possibble boards, minus the contradictories.

If you have Mathematica or some program like it, have it compute 3^361, and then have it compute 13^64. You will see that 3^361 is nearly 2 times longer than 13^64. Not bigger. Longer.
posted by Afroblanco at 9:14 PM on July 19, 2007 [1 favorite has favorites]

"Chinook is BusyStalling"

Fixed that for you, punk-ass.
posted by Alvy Ampersand at 9:15 PM on July 19, 2007

(oops, where I wrote 13^64, it should say 33^64)
posted by Afroblanco at 9:15 PM on July 19, 2007

Don't bother posting, pretty soon they'll have a computer that does THAT better, and faster than you too.

What do you mean "soon", meatpuppet?

Daisy, Daaaisy.....
posted by loquacious at 9:17 PM on July 19, 2007

just wait until they come up with a computer that masters dating
posted by pyramid termite at 9:19 PM on July 19, 2007

just wait until they come up with a computer that masters dating

They already did.
posted by Afroblanco at 9:22 PM on July 19, 2007

Ahem...
posted by Steven C. Den Beste at 9:24 PM on July 19, 2007

My machines have been computing since 1999. Soon I will have solved mefi snark.
posted by jouke at 9:34 PM on July 19, 2007

Contrarily, I think Go will be solved eventually. Not in the next year or so, but eventually, within our lifetimes even.
posted by edgeways at 10:44 PM on July 19 [+] [!]

Anything other than unbridled optimism (not that there's anything wrong with that!) behind that belief?
posted by BaxterG4 at 9:40 PM on July 19, 2007

I was hoping that the post would have a mention of what happens when Chinook plays against Chinook, but no such luck. Does it go to a draw, or does the first player always win? Does it play the same way each time?

I'm working on a new 8x8 game that plays a little differently from either Checkers or Chess, by way of cleverly and strategically fighting for territory with your pieces. I'd hops that it could never be solved, but I strongly doubt that I'm that smart.
posted by Navelgazer at 9:53 PM on July 19, 2007

I don't think there are enough atoms in the universe to store all the intermediate data which would be needed in order to solve the game of Go.

How much data do you think can be stored per atom?

It's a lot more than you seem to be assuming.
posted by -harlequin- at 10:14 PM on July 19, 2007

For posterity, the reverse double.
posted by cortex at 10:22 PM on July 19, 2007

x|_|_
_|_|_
 | |

posted by Mr. President Dr. Steve Elvis America at 10:26 PM on July 19, 2007 [2 favorites has favorites]

Excuse me, but I'm using my atoms. You can't use them to store your Go game.
posted by five fresh fish at 10:27 PM on July 19, 2007

Harlequin, you'd need to store about 10^50 board positions per atom. I don't believe that is possible.
posted by Steven C. Den Beste at 10:31 PM on July 19, 2007 [1 favorite has favorites]

Besides which, we don't have access to the entire mass of the universe, and we still won't have by 2100.
posted by Steven C. Den Beste at 10:32 PM on July 19, 2007

This means that there are 3^361 possible boards, minus the number of boards that could never exist because they would be contradictory.

Can't you ignore 3/4 of those?
posted by Mr. President Dr. Steve Elvis America at 10:34 PM on July 19, 2007 [1 favorite has favorites]

This is an interesting exercise in computing, but to me it really just seems analogous to painting a white space black, or vice-versa. There are much better uses of long term large scale computing projects, like mapping how the retina works or something. Just fleshing out a variable table is kind of weak.
posted by Burhanistan at 10:34 PM on July 19, 2007

According to blahblahblah's last link, Go has approx. 10^100 board positions - does this mean that a google is pronounced Go-ogle?
posted by birdsquared at 11:01 PM on July 19, 2007

The key is always to find scenarios that are either strategically equivalent or exceedingly unlikely. That's what they did with Chinook to Checkers, and that's what they'll do to Go and Chess.
posted by effugas at 11:10 PM on July 19, 2007

Can't you ignore 3/4 of those?

With reflections, you can in fact ignore 11/12 of those right off the bat, but Big Number divided by wee number still equals Big Number.

If we solve Go, it's almost certainly not going to be by brute force, but by very clever algorithms, and very subtle proofs. Or, alternately, by finding a wormhole to another universe, conquering it, and forcing them to run Go-solving code on their atoms.

Go has been solved on a 5x5 board. I don't know if anyone has taken a serious crack at a 7x7 board. More on solving Go from Sensei's library.
posted by phooky at 11:13 PM on July 19, 2007

Navelgazer: Considering how easy it is to draw in English draughts I suspect Chinook vs Chinook leads to a draw. And as for your game design being solvable, if it is a you go I go game with no hidden information and no post setup randomness, the game is solvable.
posted by aspo at 11:21 PM on July 19, 2007

This is from 9 years ago, but it's still a great account - American pro Janice Kim spots the world-champion go program 25 stones, wins.
posted by ormondsacker at 11:41 PM on July 19, 2007 [1 favorite has favorites]

x|_|_
_|0|_
_|_|_
posted by Afroblanco at 11:43 PM on July 19, 2007

x|_|_
_|0|_
x|_|_
posted by blueberry at 12:06 AM on July 20, 2007

x|_|_
_|0|_
X|_|_
posted by ormondsacker at 12:06 AM on July 20, 2007

Oop, double.

x|_|_
0|0|_
X|_|_
posted by ormondsacker at 12:07 AM on July 20, 2007

x|_|_

0|0|_

X|X|_


...bugger
posted by Justinian at 12:16 AM on July 20, 2007 [1 favorite has favorites]

Mornington Crescent!
posted by ormondsacker at 12:18 AM on July 20, 2007 [1 favorite has favorites]

phooky: If we solve Go, it's almost certainly not going to be by brute force, but by very clever algorithms, and very subtle proofs. Or, alternately, by finding a wormhole to another universe, conquering it, and forcing them to run Go-solving code on their atoms.

My bet is on the DMT elves.
posted by peeedro at 12:28 AM on July 20, 2007 [2 favorites has favorites]

Phew. Looks like Chutes and Ladders is okay until the sexy projects are done.
posted by Twang at 1:50 AM on July 20, 2007

It is said that upcoming nanostorage will be able to hold all the data generated in the 21st century in about 100 kg of storage.

I wouldn't predicate a "no-Go" surmise based on storage limitations.
posted by Twang at 1:54 AM on July 20, 2007

How does that predicted amount of data compare with all the possible positions in Go though, twang? Or anyone else, for that matter. Do those predictions include all the information in the massive Go database tower, in the shadow of which we will all live in fear?
posted by howfar at 2:19 AM on July 20, 2007

To arrive at a rough estimate of "all the data generated in the 21st century", lets assume we record everything that everyone sees and hears, 24/7. 30 frames per second for a century gives 3.15*10^9 frames. Call it 5k per frame, gives 14.69Tb for a century of video. Multiply by 6 billion people gives about 82*10^21 bytes (I think).

Afroblanco gives us a figure of 3^361 boards (actually larger as we can't encode 1 Go board as 1 byte) - that's still 2*10^150 times larger than a video archive 600 billion hours long.
posted by Leon at 4:46 AM on July 20, 2007

To give you a hint about the size of the Go problem and why it can't be solved by brute force: current estimates place the number of atoms IN THE UNIVERSE at 10^80 to 10^90.

The universe has existed for about 10^18 seconds, give or take one order of magnitude.


Therefore, even if we ran a calculation using every atom in the universe representing a state, at 1000 calculations a second, we'd still only access AT MAX 10^120 states.

This is stil 10^240 less than the number of go positions.
posted by lalochezia at 7:08 AM on July 20, 2007

BTW that assumes we can run the calculation continuously for another length-of the-universe time period.

It also assumes quite a few other things. I leave these to the readers (and this writers) addled imagination.
posted by lalochezia at 7:10 AM on July 20, 2007

Chess players are already thinking ahead to when their game is solved

I don't see why that would be an issue. Even if chess is solved, surely the solution will be far too complex for a human to memorize. Why wouldn't humans still play chess? We still have foot races, after all, despite the fact that machines which can go much faster than any human on foot are commonplace.
posted by DevilsAdvocate at 7:38 AM on July 20, 2007

x|_|_

0|0|_

X|X|X

Yea baby! Still the champ!
posted by filchyboy at 9:58 AM on July 20, 2007

_|_|_

_|Horse parts|_

_|_|_
posted by Smedleyman at 11:56 AM on July 20, 2007

This is silly optimism speaking, but just because we don't know them yet doesn't mean there aren't ways in which the problem space can be pruned to a manageable size. I leave producing examples of things possible today that the foremost thinkers of times past would have thought impossible as an exercise to the reader.
posted by juv3nal at 12:57 PM on July 20, 2007

While the naive go brute force implentation may not be viable, that doesn't mean go is not solveable. Of those 3^361 you are not only counting illegal go possitions, you also counting cullable boards. You don't need to store games that lead to obvious defeat (that's not optimal play), and part of solving go is devising better ways to cull the search tree. Is this possible without running out of atoms in the universe (or taking so much time that universe ends before the caluclations end)? I don't know. But I know that people who say it can't are naively assuming, well, a naive solution.
posted by aspo at 1:58 PM on July 20, 2007

Yea baby! Still the champ!

Hold on there, champ. X went twice in a row.

x|_|_
0|0|0
X|X|_
posted by nevercalm at 4:40 PM on July 20, 2007

[pushes board off the table]

Ha! X wins again by default!
posted by five fresh fish at 5:21 PM on July 20, 2007

You people suck at tick tack toe.

from

x|_|_
_|0|_
_|_|_

you go

x|_|_
_|0|_
_|_|x

X wins.
posted by Arturus at 11:26 PM on July 20, 2007

No it doesn't.

x|0|_
_|0|_
_|_|x

Draw.
posted by Silune at 11:53 PM on July 20, 2007

This is silly optimism speaking, but just because we don't know them yet doesn't mean there aren't ways in which the problem space can be pruned to a manageable size.

While the naive go brute force implentation may not be viable, that doesn't mean go is not solveable. Of those 3^361 you are not only counting illegal go possitions, you also counting cullable boards. You don't need to store games that lead to obvious defeat (that's not optimal play), and part of solving go is devising better ways to cull the search tree.

I think we're running into confusion about words. There's a difference between playing really well and playing perfectly. Things like "tree pruning" are very useful if you're trying to create a strong computer player, but they're not if you're trying to "solve" the game.

Tree pruning is based on heuristics. But heuristics are sometimes wrong. (As the old joke goes, if a heuristic was never wrong it would be an algorithm.) If you prune the tree you can reduce it to manageable size (maybe) but you may also be discarding an obscure and apparently stupid move which is actually brilliant. If you're trying to play strong, that's OK. You don't need the absolute best move, you just need a really good one. But if you're trying to play God's game, you can't take the chance that your tree-pruning heuristic might be throwing away a needle with all the hay.

"Solving the game" means is that the computer player would be perfect. It means that in any board position, the computer player will always make the very best move available. That's what they just did for Checkers. (Or so they claim.)

The other skeptics and I did not express an opinion that a powerful computer Go player is impossible. What we said was that a perfect player was impossible. We didn't say that a computer Go player won't ever be decent. What we said was that it won't ever be perfect. That's because the numbers are just too large.

As mentioned, there are 3^361 possible combinations of spaces, white stones, and black stones. That's a really big number: 1.74 * 10^172.

Also as mentioned, many of those are either illegal or nonsensical or represent rotations and mirrors of other boards.

Suppose that it turns out that only one out of ever trillion trillion trillion of those possible boards makes sense. Out of every 10^36 board positions we only need to keep and consider one.

Then we'd still have to process more than 10^136 board positions.

Suppose every atom in the universe was a computer assigned to the job. Suppose that the compute job began with the beginning of the universe, and the job just finished about five minutes ago.

If there are 10^70 atoms in the universe, and if the universe is 13.5 billion years (4.26*10^17 seconds) then each of those atom-computers would have had to process more than 10^48 board positions every second.

The word "impossible" has multiple meanings. "Solving" Go isn't impossible in the sense that doing so would embody a logical contradiction or violate the laws of physics. But it is impossible in the sense that it isn't going to happen. The problem is just too large.

Playing a strong game, on the other hand, is an entirely different matter. It's a fundamentally tough problem because the approach which was used for Chess can't be applied to Go, but there may be some other approach available that works. But no matter what it is, and even if it ends up being better than any human, it won't be perfect. The game of Go won't ever be "solved".
posted by Steven C. Den Beste at 12:23 AM on July 21, 2007

But we can't be quite that certain, Steven. This argument is good and instructive, yes:

Suppose that it turns out that only one out of ever trillion trillion trillion of those possible boards makes sense. Out of every 10^36 board positions we only need to keep and consider one.

Then we'd still have to process more than 10^136 board positions.

But it disregards the possibility that we might find a way to restructure and reduce the computational problem by greater than a factor of 10^36. How to do that is the million dollar question, and I don't think there's anything controversial about suggestion that it's likely we'll never figure it out—but there isn't any existing proof that we can't, as far as I know.

What if we find some brilliant way to effectively characterize a board position as a collection of boardlets, such that the problem can be reduced by an order of 10^120? What if we can prove symmetrical or regional or logical propositions about boardlets that so shockingly reduce the scope of the search that we're no longer needing every atom of the universe for a billions of years just to model a computation?

It's a hard problem. It could easily remain an unsolved problem—it might even be proved to be unsolvable in principle, and that would be an interesting result. But I don't see how it's true at this time to state the unsolvability of Go as a certainty.
posted by cortex at 8:16 AM on July 21, 2007

Cortex, as a moderately competent Go player, I express my opinion that what you say will not happen.
posted by Steven C. Den Beste at 8:44 AM on July 21, 2007

Hell, as a really novice Go player, I express your opinion that what I say will not happen. But there's a difference between "won't" and "likely won't", and if you're going to get down to the hard nuts of problem reducibility it's a difference that needs to be established.
posted by cortex at 8:51 AM on July 21, 2007