1002: "Game AIs"

[Jared the Great]

Alt Text: "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."

Mao is a video game? Can't find it on Wikipedia.

[glasnt]

Aw, was waiting to see "Kickboxing" in the bottom section, as per the proverb:

"If you can't beat your computer at chess, try kickboxing"

Hi Jared The Great, how are you?

[xkiQ]

Mao is a video game? Can't find it on Wikipedia.

The comic doesn't say only video games. http://en.wikipedia.org/wiki/Mao_(card_game)

[rhomboidal]

I'd love to see Calvinball as an exhibition sport at the next Summer/Winter Olympics. Or even better, the ONLY sport at the next Summer/Winter Olympics.

[mania]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

[muntoo]

Bunch of random thoughts going through my head:

• I am watching Artificial Intelligence in English class. GOOMHR...
• I don't think there are many World Champion matches against IBM Chess Supercomputers anymore...
• Jeopardy is in the middle of "can beat" and "can't beat"...
• Computers have a higher probability of winning against humans in a Snakes and Ladders tournament if there are more computers than humans. And since computers are easier to create than humans...
• Every one of my bullets is ending with '...'...

[haroldthecur]

Snakes & Ladders =

Missing:
- connect 4
- war

-Harold

[Ideas sleep furiously.]

I loved the inclusion of Calvin Ball in this.
Randall you rascall.

[Capt.Awesome]

This is easily one of the best comics to date. Although, I can never seem to win at CalvinBall... even if it is against a computer

[ken_jennings]

NEXT!

[DVC]

I had to look up seven minutes in heaven.

[torontoraptor]

Aw, was waiting to see "Kickboxing" in the bottom section, as per the proverb:

"If you can't beat your computer at chess, try kickboxing"

Hi Jared The Great, how are you?

Hi glasnt! If we can teach a computer to even understand calvinball, I'd consider it a massive win for humanity.

[shirosuzume]

Do you know how long I've been looking for somebody else that's heard of Mao? And here I had come to the conclusion that it only existed in Washington DC, in 1994, among the people who were there with me.

It's not a video game, it's a card game. A lovely, lovely, awesome card game. There is only one rule: You can't tell the rules. Muahahahaha....

Now I must find more people... there must be more!

[jpk]

I'd love to see Calvinball as an exhibition sport at the next Summer/Winter Olympics. Or even better, the ONLY sport at the next Summer/Winter Olympics.

Sure, why not? All other sports are a subset of Calvinball, so it would be perfectly fair.

[TomRobbins]

I remember that game Mao. Stupid girls at the pool wouldn't tell me the rules.

[Sir_Read-a-Lot]

I remember that game Mao. Stupid girls at the pool wouldn't tell me the rules.

I should hope so!



This reminds me strongly of a previous comic: http://xkcd.com/696/. I'm guessing that computers are never going to beat us at Strip Poohsticks either.

[pareidolon]

Hmm, I'm already thinking of ways you could program a computer to play Mao. That would actually be a very good project for a college thing-people-make-projects-for.

As for Snakes & Ladders, it's very simple.
Need to roll 4 to win game... ... ... COMPUTER ROLLS 4.

[ribis]

Uh, what, exactly, would stop a future computer from performing at just as well as a human at any of the bottom items?

If I'm not mistaken, Snakes and ladders has no strategy. Never played it, but isn't it just, "roll the dice, move as indicated, take a snake/ladder if applicable?"

The other games would be satisfied by any system that satisfactorily passes the Turing test, and as far as I know, there's no reason to think a future system couldn't at least PASS as human (setting aside any strong/weak AI or philosophical zombie rhetoric). Actually, such an AI might just outperform in Mao and Calvinball using perfect, faster recall and procedural rule generation. Additionally, a Turing-test-qualified android could at least match a human at Seven Minutes in Heaven (it's "Seven Minutes," not "Until Death Do Ye Part"). Heck, I'll say it could theoretically outperform there, because it could be programmed to never kiss and tell...

[from canada]

A calvin and hobbes reference?

randall you fucking genius!! Is there anything you can't do over and over again and still think it's funny when it's absolutely pathetic and an obvious attempt at nostagia pandering

fuck

[karanj]

Hmm, I'm already thinking of ways you could program a computer to play Mao. That would actually be a very good project for a college thing-people-make-projects-for.

Yes! and just having done the Stanford A.I. course, I'd be classifying it as a partially observable but deterministic problem that'd be perfect for an unsupervised learning algorithm...

[CuBr]

In case anyone is curious, the chess games referred to are Deep Blue vs. Kasparov and Ponomariov vs. Fritz.

EDIT: Suddenly [url] is working again...

[Harry Voyager]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

Well, the first wave of "neural" interfaces have started to show up. Granted they're still not much more than a key-mapped EKG machine, but they're still out there, and will likely develop the way all the rest of computer technology has.

[cyanyoshi]

Not sure about all of you guys, but my greatest hope is to see the day when a computer program can consistently beat the greatest humans at go (kind of like chess, currently). That is truly the day that AI will have been perfected.

[standingwave]

The comic doesn't say only video games. http://en.wikipedia.org/wiki/Mao_(card_game)

LOL! Sounds like it's related to Fizzbin.

[NotAllThere]

Not sure about all of you guys, but my greatest hope is to see the day when a computer program can consistently beat the greatest humans at go (kind of like chess, currently). That is truly the day that AI will have been perfected.

Not it won't. It might win at go, but it'll probably be crap at noughts and crosses. For AI to be perfected, it must be general intelligence.

@haroldthecur - Connect Four isn't missing.

I reckon a computer can beat a human master player of Durak.

[penguinoid]

Am I the only person disappointed that "Global Thermonuclear War" was unaccountably left out? I think WOPR figured it out, eventually...

(I realise the answer to the above question is almost certainly "yes"... )

[niky]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

I was thinking about this... Counterstrike is an interesting question, because the computer already knows where everyone and everything is, and AI players have to be designed to "not see" players behind them, to "not know" where players they can't "hear" or "see" are and to not shoot inhumanly quickly.

Given that, AI in most videogames of this type are very poor tacticians, and easy to trap in pincer movements and the like in team-play.

Starcraft still falls barely into "computers lose to top humans" because of the strategy aspect. You can learn to think around AI strategy, and limited unit speed and build speed, combined with good button mapping and very quick fingers will allow a good Starcraft player to outplay the AI on a level playing field.

Then again, most computer games of this type don't have the AI processing power of Deep Blue... it would be interesting to see if they could ever build a computer that would thoroughly dominate he best human players in a purely strategic turn-based war-game on a one-on-one basis.

[hellcatv]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

I have a friend who wrote a starcraft AI that sits as a graphics driver and a mouse driver and plays by the rules.

http://graphics.stanford.edu/~mdfisher/D3D9Interceptor.html
specifically
http://graphics.stanford.edu/~mdfisher/GameAIs.html

It's an interesting read, and it can beat humans--with enough research it could beat them easily I'm sure.

[ribis]

I was thinking about this... Counterstrike is an interesting question, because the computer already knows where everyone and everything is, and AI players have to be designed to "not see" players behind them, to "not know" where players they can't "hear" or "see" are and to not shoot inhumanly quickly.

Given that, AI in most videogames of this type are very poor tacticians, and easy to trap in pincer movements and the like in team-play.

Starcraft still falls barely into "computers lose to top humans" because of the strategy aspect. You can learn to think around AI strategy, and limited unit speed and build speed, combined with good button mapping and very quick fingers will allow a good Starcraft player to outplay the AI on a level playing field.

Then again, most computer games of this type don't have the AI processing power of Deep Blue... it would be interesting to see if they could ever build a computer that would thoroughly dominate he best human players in a purely strategic turn-based war-game on a one-on-one basis.

Some games are less amenable to AI dominance. Compare vanilla Counterstrike to Quake, TF2, or Unreal Tournament -- the advantage granted by on-demand headshots decreases the more that overall victory depends on map control, complex movement, and the tactical use of powerful-but-situational weapons. Nevertheless, this mostly amounts to a Chess < Arimaa advantage favoring humans in the short run, AI in the long run.

[Eheq]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

I was thinking about this... Counterstrike is an interesting question, because the computer already knows where everyone and everything is, and AI players have to be designed to "not see" players behind them, to "not know" where players they can't "hear" or "see" are and to not shoot inhumanly quickly.

Given that, AI in most videogames of this type are very poor tacticians, and easy to trap in pincer movements and the like in team-play.

Starcraft still falls barely into "computers lose to top humans" because of the strategy aspect. You can learn to think around AI strategy, and limited unit speed and build speed, combined with good button mapping and very quick fingers will allow a good Starcraft player to outplay the AI on a level playing field.

Then again, most computer games of this type don't have the AI processing power of Deep Blue... it would be interesting to see if they could ever build a computer that would thoroughly dominate he best human players in a purely strategic turn-based war-game on a one-on-one basis.

As I understand it, the AI for Starcraft isn't particularly good compared to an experienced human. They get around it by giving the highest difficulty AI (Insane) 7 minerals per worker trip to a normal player's 5. This should be a nearly insurmountable advantage, but top humans can still win.

I think it would still be a quite significant challenge to program an AI that could compete with tournament players, even given the advantage of total simultaneous unit control map wide. Hell, the standard strategies for Brood War were still being developed years after release, so it would be quite a challenge for the programmers to keep up with the appropriate counter strategies.

[TranquilFury]

I would say starcraft is a more difficult problem than poker for AI, because starcraft includes the risk, tradeoffs, and bluffs that make poker a hard problem, but also requires you to infer intent from minimal information. The ai advantage of thousands of actions per minute does not outweigh predictability and gullibility. It would take years of collaboration between professional starcraft players and the people that code the bots for there to be any hope of an AI winning a tournament, and much of that work would have to be repeated every time there's a new map or a shift in popular strategies. Starcraft 2 would be even harder for AI, because there's less marginal advantage to perfect control, and the mechanics are easier, which reduces the macro advantage of an AI as well.

[TranquilFury]

Personally I would not accept a computer winning a game of counterstrike/starcraft versus a human as fair unless it was interpreting the images and sending the appropriate mouse/keyboard commands, at a somewhat realistic speed.

Particularly starcraft, it's just not "fair" that the computer can have an interface that so much beats ours - having full access to the whole gamestate at once. Being able to control units at opposite ends of the map simultaneously... etc. Likewise for counterstrike, the AI shouldn't be able to simply go off the gamestate to know that it can in theory see "you", it should have to deal with the same few pixels of information that we have to.

Imo, I suppose. But surely I can't be the only one thinking this...

I have a friend who wrote a starcraft AI that sits as a graphics driver and a mouse driver and plays by the rules.

http://graphics.stanford.edu/~mdfisher/ ... eptor.html
specifically
http://graphics.stanford.edu/~mdfisher/GameAIs.html

It's an interesting read, and it can beat humans--with enough research it could beat them easily I'm sure.

BAD humans. When was the last time you saw an AI beat flash in brood war? Hell, I could probably beat any AI in sc2, so long as it doesn't have a resource/maphack advantage. (perfectly ok for it to issue orders directly, rather than mouse driver, and also ok for it to have automatically parsed input for whatever is within it's units' vision)

[mbklein]

EDIT: Suddenly [url] is working again...

Perhaps because you've suddenly reached the 5-post threshold the allows you to use the [url] tag?

[Tass]

Then again, most computer games of this type don't have the AI processing power of Deep Blue...

Deep blue is 15 years old. A high-end home computer can match its processing power.

Edit: After some research I must correct that. Apparently even a low-end home computer can match the power that deep blue had. (Though of course less effort may have gone into making the AI and most games would use most of their resources on running the game rather than on the AI's. Deep blue was specifically designed to play chess and nothing else.)

[Eheq]

I would say starcraft is a more difficult problem than poker for AI, because starcraft includes the risk, tradeoffs, and bluffs that make poker a hard problem, but also requires you to infer intent from minimal information. The ai advantage of thousands of actions per minute does not outweigh predictability and gullibility. It would take years of collaboration between professional starcraft players and the people that code the bots for there to be any hope of an AI winning a tournament, and much of that work would have to be repeated every time there's a new map or a shift in popular strategies. Starcraft 2 would be even harder for AI, because there's less marginal advantage to perfect control, and the mechanics are easier, which reduces the macro advantage of an AI as well.

Just what I was thinking. Likely, the easiest method would be teaching the AI to "cheat" by doing things a human player can't do very efficiently, like mount multiple simultaneous attacks with intensive micro. If one or two build orders and attack strategies can be put together that just bypass Blizzards efforts to balance the game, it avoids having to program an AI that isn't super gullible in a situation with trillions of possible courses of action.

[Ben's Brook]

AGEOD games, for example. I've been playing Revolution under Siege a lot, and the one thing I noticed was varying levels of AI. The allied Siberian Whites can outmatch the Communist AI for a while, but not forever. The Green AI is just playing stupid, boiling down to "Where is a city that I can attack with an enormous doomstack of partisans?"

And the Communist AI opponent is very so so. For example, I was advancing in the Ukraine and encountered an 80k strong Army + Corps under Trotsky. Perturbed by the sudden appearance of the bossman himself with friends, I grabbed Mai-Mai from the other end of the Ukraine to reinforce Denikin. At this point, both armies basically sat, glaring at each other. I couldn't attack him because of his entrenchment bonus, and he couldn't attack me because of my superior generals. So, I finally got the French expeditionary Force, bringing the total up to 138k troops to attack Trotsky's 80k army. The turn the expeditionary force arrived, Trotsky disappeared into thin air, using his railline northward to escape to Moscow, redeploying his second corp off to Siberia and sending his other corp god knows where.

Fast-forward three months, and I see Trotsky march down to grab undefended Kursk. I didn't have any intel on his size, so I grab both Mai-Mai and Denikin (around 100k soldiers due to additional reinforcement), and march them to Kursk. When they arrive, I discover that Trotsky has simply come along with only a small division worth of soldiers. 41 casualties to 10k dead Soviets(as it turns out, even a master like Trotsky can't beat Denikin + 100k). Trotsky was wounded and disappeared off to Moscow.

Compare that to other games where I've been stymied by Stalin, Kalnin, and Sorokin constantly.

[Camquin]

Mornington Crescent

[pbnjstowell]

Am I the only person disappointed that "Global Thermonuclear War" was unaccountably left out?

I was also disappointed.


@shirosuzume I've heard of Mao too! But I thought the same thing, only for my group of friends in Washington State in about 1997.

[phlip]

As I understand it, the AI for Starcraft isn't particularly good compared to an experienced human. They get around it by giving the highest difficulty AI (Insane) 7 minerals per worker trip to a normal player's 5. This should be a nearly insurmountable advantage, but top humans can still win.

You're talking about the supplied in-game AI, though... which is not the same thing as an AI designed to win the game. The AI that ships with the game is designed to be fun to play against, not to win all the time. And it's also quite simplistic, as it was built by people experienced in making games, as opposed to people experienced in making AIs.

But a built-to-win AI opponent has quite insane micro, since it'll micro each unit individually at speed (the ingame AI could do this, but doesn't, because that's not fun to play against). Which means they can pull of some crazy micro trickses. It's just the long-game strategy that needs a lot of work at this point.

[Condor70]

As for Snakes & Ladders, it's very simple.
Need to roll 4 to win game... ... ... COMPUTER ROLLS 4.

I would expect that of a computer that uses Randall's Random Number generator (http://xkcd.com/221/).

ps. I'm missing Rubiks Cube, solved July 2010 (http://cube20.org/). Or is the cube considered a teaching device and not a game?