The spectrum of Human-Computer competition

January 11, 2012 11:55 AM

A recent XKCD comic charted the difficulty of various games for computers, from Tic Tac Toe and Nim being solved for all positions, to computers mastering the physical game of Beirut and mental game of chess (the 2006 Deep Fritz vs Vladimir Kramnikin games, previously). There are other games that are basic on the face, but whose potentials for move combinations is so vast as to be beyond the scope of computers. Marion Tinsley was the last great human checkers player, matching off against Chinook in the last 6 games of his life, each ending in a draw (previously). Checkers was finally solved in 2007 (Google quickview; original PDF), and is largest game that has been solved to date, at 8x8. Solving Othello might be possible, if the decision tree were truncated, as the 10x10 board game tree complexity is very huge. The 19x19 Go board is is often noted as one of the primary reasons why a strong program is hard to create, though some programs are getting better at optimizing move evaluations. More: computerized gaming solutions previously, and the Wikipedia page for solved games.
posted by filthy light thief (57 comments total)

I was introduced to Arimaa via MetaFilter and I thought, at first glance, that it looked kind of stupid. But then I came back and gave it a more serious look years later and it's really an excellent game, and it's excellent at making computers look stupid.
posted by Wolfdog at 11:58 AM on January 11 [3 favorites]

Oh come on, no love for Calvinball?
posted by Old'n'Busted at 11:59 AM on January 11

He missed Global Themonuclear War
posted by iotic at 11:59 AM on January 11 [4 favorites]

Is the snakes and ladders position a joke? I recall it being random.
posted by mad bomber what bombs at midnight at 12:01 PM on January 11 [1 favorite]

Where's Starcraft in this compendium?
posted by sourbrew at 12:04 PM on January 11

Oh I see it made the comic but not your post, for shame!
posted by sourbrew at 12:05 PM on January 11

the snakes and ladders position

That's one I've never tried.

also, great post.
posted by kiltedtaco at 12:05 PM on January 11 [4 favorites]

Starcraft is in "computers still lose to top humans," right below jeopardy.
posted by You Can't Tip a Buick at 12:06 PM on January 11

Did anyone RTF XKCD comic ? (ok, global thermal nuclear war isn't there.. ).

(I had to google a few, some are joke options and some are not ..)
posted by k5.user at 12:06 PM on January 11

Is the snakes and ladders position a joke? I recall it being random.

Right, that's why computers can't beat humans at it.
posted by jedicus at 12:07 PM on January 11 [4 favorites]

Is the snakes and ladders position a joke? I recall it being random.

Snakes and Ladders is entirely random, so a computer can never have the advantage over a human or vice versa.

mcbain.jpg
posted by Faint of Butt at 12:07 PM on January 11

Yes, but can computers win The Most Dangerous Game?
posted by backseatpilot at 12:10 PM on January 11 [2 favorites]

Wow, I had to track down some more ::hiccup:: info on the "beer pong robot," as we apparently reside in the same town. It is no joke, apparently.
posted by obscurator at 12:11 PM on January 11

For those who want to know more about any game not linked above, it's probably mentioned in the XKCD comic-specific forum post (where you can also read the alt text, for those who don't have a cursor to hover over the image).
posted by filthy light thief at 12:11 PM on January 11

And the Wiki page on solved games is pretty interesting, for those who want a few more rabbit holes to tumble down.
posted by filthy light thief at 12:12 PM on January 11

The Game. I have lost it, and so have you.
posted by Mister Fabulous at 12:14 PM on January 11 [2 favorites]

I have such a strange deep love for XKCD, it's like my subconscious writes a comic.
posted by Blake at 12:15 PM on January 11 [1 favorite]

Call me when computers beat humans at Diplomacy.

/speaking of Dip, anyone fancy a game?
posted by the man of twists and turns at 12:15 PM on January 11 [1 favorite]

But how are they at Robo Rally?
posted by drezdn at 12:20 PM on January 11 [2 favorites]

/speaking of Dip, anyone fancy a game?

Dude, do you want everybody on Metafilter to hate everybody else on Metafilter forever?
posted by kmz at 12:21 PM on January 11 [6 favorites]

Snakes and Ladders is entirely random, so a computer can never have the advantage over a human or vice versa.

mcbain.jpg

That joke is terrible. It needs to be taken out and replaced with a funnier joke.
posted by mad bomber what bombs at midnight at 12:22 PM on January 11

Checkers was finally solved in 2007 (Google quickview; original PDF), and is largest game that has been solved to date, at 8x8.

It seems to me that checkers is 4x8.
posted by CaseyB at 12:23 PM on January 11 [2 favorites]

I personally think Poker in the XKCD chart should be closer to the "Hard" side of the scale than Go. Probably the most popular form of poker at the moment is No Limit Texas Hold 'Em with a table of at least 5 players, and in my opinion at least it's much more likely for people to be able to understand the important information in that context than computers. A lot of playing at a high level in poker is understanding how your opponents think, and unlike more deterministic games like chess there's no way to brute force your way around that by coming up with a move that works no matter what your opponent's plan is. Computers may be able to solve more simplified versions of the game like limit poker with two players, but that's on the same level as being able to solve simplified versions of Go that have reduced board sizes.
posted by burnmp3s at 12:23 PM on January 11 [1 favorite]

That joke is terrible. It needs to be taken out and replaced with a funnier joke.

I don't understand your comment. What joke are you referring to?
posted by kmz at 12:24 PM on January 11

The Game. I have lost it, and so have you.

If losing the game is the same as feeling a bit irritated by crap memes, yeah I find I do lose that game whenever it's mentioned.
posted by iotic at 12:30 PM on January 11 [5 favorites]

Faint of Butt: mcbain.jpg

mad bomber what bombs at midnight: That joke is terrible. It needs to be taken out and replaced with a funnier joke.

kmz: I don't understand your comment. What joke are you referring to?

Did you ever notice how men always leave the toilet seat up? That's the joke. (source)
posted by filthy light thief at 12:37 PM on January 11 [1 favorite]

Whoops. Didn't notice the McBain part. *Nelson laughs at self*
posted by kmz at 12:38 PM on January 11

The thing about computers solving poker like chess is that all the chesspieces are known and accounted for - so the permutations can be solved rationally. The fact that you can't do that with poker is kind of the whole point of the game. It's called "gambling" for a reason.
posted by bicyclefish at 12:49 PM on January 11

Eschaton?
posted by MtDewd at 12:58 PM on January 11 [1 favorite]

I've found every computer I've ever faced to be wholly unprepared unprepared for the "This Game is Stupid" declaration followed by the "Throwing All the Pieces on the Floor Gambit."
posted by drezdn at 1:03 PM on January 11 [7 favorites]

No Morpion Solitaire?
posted by everichon at 1:04 PM on January 11

drezdn: I also find the 'Set off the EMP' or 'Unplug the computer' gambit to be quite effective.
posted by Pink Fuzzy Bunny at 1:07 PM on January 11 [1 favorite]

My computer still falls for "52 Card Pickup".
posted by Xoebe at 1:08 PM on January 11 [2 favorites]

Dr. Sbaitso is not very good at 20 questions, either.
posted by backseatpilot at 1:19 PM on January 11 [1 favorite]

I once challenged my computer to a game of "sit around messing about on the internet." Thus far we're still deadlocked.
posted by Panjandrum at 1:20 PM on January 11 [3 favorites]

No computer yet built can beat my son in the "every goddamn time he throws the dice it rolls off the fucking table and then, once he picks it up off the floor, he has to carefully count every space he moves even though at his math level it should be perfectly goddamn obvious where his piece is going to end up" aspect of most games.
posted by bondcliff at 1:21 PM on January 11 [2 favorites]

The thing about computers solving poker like chess is that all the chesspieces are known and accounted for - so the permutations can be solved rationally. The fact that you can't do that with poker is kind of the whole point of the game. It's called "gambling" for a reason.

The gambling aspect is more due to the non-deterministic properties of the game, in that the eventual winning hand is determined entirely by random chance and in general no decisions a player makes in the game (other than conceding) will affect that. But that's not necessarily what makes poker hard to write AI for. Scrabble for instance has top AI program that can consistently beat championship players, even though the letters are handed out randomly and concealed by each player very similar to the way cards are handled in poker.

What I think makes poker so difficult to evaluate is that you almost never get perfect information about the state of the game at any time where it actually matters. Sometimes you get to see a showdown that gives you perfect information about two or more of the players for the hand that just happened, but it's not at all trivial to take that information and apply it to future hands (even though that's what human players do). There is a lot of analytical thinking that separates a top poker player from an amateur when it comes to evaluating the state of the game, and I think trying to replicate that evaluation is in an entirely different league than a simple exhaustive search and evaluation of every possible decision available of the sort used in current top chess/Scrabble/Go/whatever AI.
posted by burnmp3s at 1:24 PM on January 11 [2 favorites]

He's wrong about Calvinball.

Once my computers got past DOS 3.3 and Mac OS 6, they were able to start games of Calvinball spontaneously and as long as I'd stay at the computer they'd keep beating me.

For me against Windows 7 or OSX 10.7 -- it's like me against a team that makes its own rules every few minutes.

Like? Hell, they _do_ make the rules.
posted by hank at 1:31 PM on January 11

Surely it's going to be a long time before a computer can compete at Mornington Crescent.

Even a simple Paddington switchback maneuver will throw the best current AI systems off entirely. And if you're using the revised token valuation rules, then forget it. How can a machine ever hope to assess a Morebury shuffle exchange longer than a couple of turns? The permutations must be nearly infinite.
posted by CaseyB at 1:32 PM on January 11 [10 favorites]

drezdn: I also find the 'Set off the EMP' or 'Unplug the computer' gambit to be quite effective.

I don't think you would appreciate it if the computer tried the 'electrocute the human' maneuver.
posted by knave at 1:39 PM on January 11 [3 favorites]

Surely it's going to be a long time before a computer can compete at Mornington Crescent.

I don't know. I hear the Soviets are working on a secret MC program that can even defeat Dr. Chesterton and other grandmasters. I believe its codenamed 'Markov'...?

(and by the soviets I mean: cortex )
posted by Potomac Avenue at 2:41 PM on January 11

Xoebe: My computer still falls for "52 Card Pickup".

On the other hand, my shop vac is getting pretty good at this. If the two were to combine their powers, they could be nigh unstoppable.
posted by filthy light thief at 3:28 PM on January 11 [2 favorites]

it will be an awesome day

it will be a beautiful day

ray kurzweil will sing and dance

when computers finally beat humans at

vampire: the masquerade
posted by Sticherbeast at 3:41 PM on January 11 [2 favorites]

Well there's always the south Kensington gambit to counter the Paddington switchback, which the AI should know if it's well trained in advance, but I agree it would be unlikely to come up with that on its own.

At least with poker you could work on the basis of statistical analysis of prior games, combined with card counting to predict what action the opponent is most likely to take, especially if given time to adapt to individual player styles - humans are much more predictable than we think - so given enough horse power and a big enough data set, I bet they could calculate the odds better than a person. Long way off before it can process a live video streaming to spot tells though.

There's no way any AI will be able to predict a game based on prior knowledge, even with a beginners variant like the Oxbridge bypass or the Schweizmann-Smith routing option. Its not like a database of past games will help predict an Elephant and Castle passing maneuver before its used.

My problem is my French wife prefers Mornington Croissant, and it's just not the same. Allowing gares du nord transit will always feel like cheating to me.
posted by ArkhanJG at 4:12 PM on January 11

Dude, do you want everybody on Metafilter to hate everybody else on Metafilter forever?

I do! I do!
posted by eyeballkid at 4:29 PM on January 11 [1 favorite]

No limit poker actually has pretty limited choices. Bet, Raise, Fold...if bet, then how much. Limit poker omits the "how much" question. The problem is that choosing which action is the right one that makes money in the long run, is difficult.

The thing about poker, is that if I could program a world-class playing poker program, I wouldn't tell anyone! Because as soon as I did, it would get banned from playing online. A world class poker program is potentially more lucrative than any of the other game playing programs, because it can potentially win tens of millions of dollars playing online.

It is the ultimate Turing Test. Am I playing a human or a bot? I feel that online poker has at most a ten year window before you won't be able to beat the bots. As soon as bots are recognized as beating the world's best poker players, only an idiot would play online poker any more.
posted by Xoc at 6:56 PM on January 11

xkcd: "Difficulty of Various Games for Computers"

Who the hell thinks that "Seven Minutes in Heaven" is a competition? OR a game?
posted by AsYouKnow Bob at 7:31 PM on January 11

MtDewd: From the description Eschaton is theoretically very winnable by computers, especially if played in the controlled conditions of the Lung. A lot of the game is already defined in game-theoretic terms and requires no small amount of extremely computer friendly calculation from its players, in addition to the possession of a deadly-accurate lob. A single person could probably play Eschaton against AI opponents cobbled together from a laptop, a Roomba, and an Arduino-controlled Lob-ster, perhaps.
posted by Jon Mitchell at 8:16 PM on January 11

Who the hell thinks that "Seven Minutes in Heaven" is a competition? OR a game?

You'll change your tune when a hot girl turns you down and instead goes home with your iPhone after having spent seven minutes in the closet with each of you.
posted by straight at 9:37 PM on January 11 [1 favorite]

AsYouKnow Bob: Who the hell thinks that "Seven Minutes in Heaven" is a competition? OR a game?

The alt.text reads: The top computer champion at Seven Minutes in Heaven is a Honda-built Realdoll, but to date it has been unable to outperform the human Seven Minutes in Heaven champion, Ken Jennings.
posted by filthy light thief at 10:28 PM on January 11

For what it's worth.

Anyway, he seems like a genuinely nice guy, but I won't guess at his skills behind closed doors.
posted by filthy light thief at 10:31 PM on January 11

Call me when computers beat humans at Diplomacy.

The game Diplomacy challenges you to convince six other players simultaneously that you are sincere and trustworthy, when all the while each of them knows for a fact that you're trying to deceive them. It's the strongest form of the Turing test that I can imagine. Why anyone would want to build an AI that's a brilliant strategist, an accomplished liar and which hates us all is beyond me.
posted by justsomebodythatyouusedtoknow at 11:46 PM on January 11 [3 favorites]

when computers finally beat humans at vampire: the masquerade

*programs computer to sulk because life is just so hard and it's just not fair that Lestat hasn't come for it yet because out of all the players it's most surely the most deserving of a life of never-ending debauchery and murder because it's so mysterious and complicated and nobody understands it*

*compiles*

All good!

*programs computer to generate random numbers between 1 and 10*

*compiles*

4
4
4
4
4
posted by obiwanwasabi at 2:18 AM on January 12 [1 favorite]

No limit poker actually has pretty limited choices. Bet, Raise, Fold...if bet, then how much. Limit poker omits the "how much" question. The problem is that choosing which action is the right one that makes money in the long run, is difficult.

I think the thing that makes no limit worse from an AI perspective is that increases of variance of importance between individual hands dramatically. With limit poker you could probably create a blind-stealing focused AI that would make money by trying to win pots that are statistically unlikely to be taken by other players. The edge might not be much for any given hand, but over time it could whittle away at players. With no limit, any hand could possibly be for all of your chips, and the few big pots that are won that way end up being very important. Although on the other hand no limit makes automated pushbot strategies possible, where the AI only goes all in and exploits human player's tenancies to call with a statistically worse hand, but that strategy would not really work against players who can recognize the strategy being used.

The thing about poker, is that if I could program a world-class playing poker program, I wouldn't tell anyone! Because as soon as I did, it would get banned from playing online. A world class poker program is potentially more lucrative than any of the other game playing programs, because it can potentially win tens of millions of dollars playing online.

On the other hand it's unlikely that you will go straight from having no AI to an AI that beats top human players. Once you have one that beats average human players, you could probably make a lot of money selling the bot to players than you would by trying to make millions off of using it yourself.

I feel that online poker has at most a ten year window before you won't be able to beat the bots. As soon as bots are recognized as beating the world's best poker players, only an idiot would play online poker any more.

I doubt it will happen that quickly. But yes even if online poker sites added captchas and whatnot to detect actual bot players, there would be no reasonable way to prevent people from feeding the game state into some sort of analyzer app and making decisions based on the output.
posted by burnmp3s at 7:35 AM on January 12

mad bomber what bombs at midnight: "Is the snakes and ladders position a joke? I recall it being random."

You'll notice it's on the line between the two categories "still loses to top human players" and "may never outplay humans." I suppose which side it's on depends on your interpretation of luck I suppose. You come up with a better joke.
posted by pwnguin at 8:23 AM on January 12

Seven Minutes In Heaven

We're working on it, we're working on it! And really, once I finish the holodeck, do you think I would tell you about it right away? (Note to self: always flush the cache...)
posted by Theta States at 10:16 AM on January 12

You really shouldn't. You'll upset the natural balance of good yeasts and bacteria.
posted by obiwanwasabi at 11:23 PM on January 12