1002: "Game AIs"

[richP]

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"... )

You're forgetting that WOPR proved that Global Thermonuclear War* is just a derivative form of tic-tac-toe.

* Just noticed that I can't type that phrase without the full line "no, I want to play global, thermo, nuclear, war" running through my head.

[jonas]

Where would tape measure extending go in this table?

[dragondave]

Sadly, I'm pretty sure autonomous combat drones win quite handily at both Calvinball and Seven minutes in heaven.
At least, the other players certainly lose.

[DennyMo]

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!

When I learned this game in the 80's, we called it "Maumau". No wonder I didn't know what Randall was talking about...

Also, love that you included CalvinBall on the list.

[enumerated powers]

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

I was also disappointed.

Well it WAS in the mouse-over title text of http://xkcd.com/696/.

[asliceofpi]

Man, it has been years since I've even thought about Mao, let alone played it. That was one of the most malicious card games we played in high school, second only to Egyptian Rat Screw. (Most of the time, we were hooked on Bridge, Euchre, and Spades... but even nerds need a break now and then.)

Now I need to introduce my new card-playing circle to this game... this should be fun.

[shapenaji]

As a go fanboy,

I must say I was a little bothered by the "But focused R&D can change this". Go has HAD focused R&D for a while.
But at the end of the day, it's really not a problem of R&D, the top programs now have tied themselves to moore's law. (They're all Markov Chain Monte Carlo simulators)

They're at 4 dan - 5 dan KGS/EGF right now, so the comment made earlier in the thread about mediocre players beating the best bots is not really true anymore.

The top bots play... odd, it is immediately apparent how little "expert knowledge" is actually encoded. I'm 4d-5d myself, and while I have not yet lost to the top bots, I look forward to the paradigm shift of the introduction of a new style of play.


Unrelated, but I love Mao (Or as we called it, Mauii, back in DC 1998) I miss that game, can't get anyone to play it anymore.

[Felstaff]

Pawns can't move that way, you stupid arm!

[Dschingis]

First of all I love this comic <3

And I registered here, to clear up a little bit about gaming AI. And about ppl complaining about the (huge) cheating of AI.

Yes the gaming AIs are cheating but in most cases the AI cheats were ppl don't think there is a cheat and vice versa (eg. SC2 maphacking might not be cheating - i don't know it really).

And if you want to get a feeling about the Gaming AI I suggest this the Google Tech talk from Soren Johnson (the AI dev from Civ 3 & 4)
http://www.youtube.com/watch?v=IJcuQQ1eWWI

[benmoreassynt]

I definitely think Mornington Crescent would pose some challenges for AI. Could Deep Blue manage the Cockfosters triple reverse lateral retreat move to Theydon Bois, as first illustrated by Stovold under the Putney Reformed interpretation of the original Pimlico rules?

[need4speed]

Mornington Crescent

Well, Calvinball is basically Mornington Crescent. (depending on your implementation).
But I think more readers would know what the fsck Calvinball is.

Also, it would have been "fun" to mention "The Stock Market" as a game. Seeing as how, algorithmic trading now accounts for a large percentage of market volume, that might imply that AI has "won" that game, as well.

[TheEngineer]

What about Cow Tipping

[bmonk]

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

Then you need to change the rules!

[dp2]

And since computers are easier to create than humans...

That's only because if you know how to make computers, you don't often have the opportunity to make humans.

[philsov]

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?

Chess Boxing also comes to mind. All one needs to do is survive for four minutes in speed chess (milking the timer all the same) and then you have three minutes to penetrate the computer's likely Tungsten Carbide shell and you win.

[melthengylf]

"Mao" is a very popular game among argentinian math olympics OMA, along with "La Mafia" (I think it's also known as Werefolf), "El Capitalista" (apparently known as Asshole) and "24".

[aegiswings]

Gee Willikers, he mentioned Mao!!

I remember playing that back in 1996 or at CTY summer camp in PA. I then taught it to everyone I met at another summer camp at RPI. Well, by teach, I meant I let them play it with me until they figured it out.

[cynicalbastard]

And since computers are easier to create than humans...

I would beg to differ, also - I enjoy the process of creating humans a lot more.
Both are difficult to accomplish alone though... ( try soldering together a cpu)

edit: Ah - dp2 already noticed...

[Steve the Pocket]

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"

First comment and already thinking of better jokes than the comic itself. Granted, I wouldn't have gotten the reference, but obscure references are what XKCD has always been about.

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.

So would a computer also have to be looking at a physical chess board with a camera and interpreting the positions of the pieces? Granted, that wouldn't be all that hard to do, but it still seems like unnecessary complication.

As for the mouse thing, the bots in Team Fortress 2 actually have a "virtual mouse" that they have to work with, and have to pick it up and move it to the other end of the "mousepad" when it runs out of room.

[srimech]

First thing I thought of was Rock, Paper, Scissors.

Can't post a url, but worth a google, it looks like computers have humans beaten on this one.

[Cousj001]

The AI won't win at Mornington Crescent. Ever. Even using Simple & Easy rules, although maybe they could win at Heppingdon's Open.

The AI always wins at Dwarf Fortress.

[threedognice]

Computer AI in Starcraft is nothing more than a training dummy. It is made to test builds.

Playing against AI in video games like Starcraft is like playing a game of chess with a chessboard. Who cares how smart the chessboard is? I mean, IT’S A FREAKING CHESSBOARD

[forbiddenSpell]

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?

Chess Boxing also comes to mind. All one needs to do is survive for four minutes in speed chess (milking the timer all the same) and then you have three minutes to penetrate the computer's likely Tungsten Carbide shell and you win.

Unless the computer is a warforged. All it needs to do is survive for four minutes in speed chess (milking the timer all the same) and then it has three minutes to penetrate your certainly flesh and blood shell and it wins.

[PCal]

When it comes down to it wouldn't mao be the same as shoots and ladders or maybe war assuming both players AI and computer have all knowledge of the rules coming in because there is only so many legal plays you can make with your hand often only one. I guess you could put alot of number crunching in to determining if its better to put down your 4 or 6 of spades but would that even be helpful without knowing your opponents hands. But due to the amount of luck required to win it doesn't seem like a game a computer could win consistently at. Making a computer that comes in with no knowledge of the rules and learns them, because its just pattern recognition, wouldn't be to hard a task i would think though.

[Sprocket]

01.11.2012 Randall Munroe makes us all think of Ken Jennings as a sexual being.
You bastard.

[just john]

How close is chess to being solved?

(I used to be my high school's chess wiz, right after the first Fischer/Spassky matches, and I'd love to see that obsession finally put to rest.)

[Trebla]

Computer AI in Starcraft is nothing more than a training dummy. It is made to test builds.

Playing against AI in video games like Starcraft is like playing a game of chess with a chessboard. Who cares how smart the chessboard is? I mean, IT’S A FREAKING CHESSBOARD

As has been pointed out, the comic isn't referring to the computer AI in StarCraft, it's referring to third party AIs that have been written to perform competitively. I can't vouch for how well they stand up to top end players, apparently they do well early on but fall apart in late game strategy.

So would a computer also have to be looking at a physical chess board with a camera and interpreting the positions of the pieces? Granted, that wouldn't be all that hard to do, but it still seems like unnecessary complication.

Saying the AI is winning because it can interact with the game faster is like saying AI is "smart" enough to win at Arm Wrestling... While the computer may be better... it's not fully a function of the AI when you enforce different physical limitations on the two sides. Seems like a difficult thing to measure to me.

[Роберт]

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.

So would a computer also have to be looking at a physical chess board with a camera and interpreting the positions of the pieces? Granted, that wouldn't be all that hard to do, but it still seems like unnecessary complication.

Chess is all about strategy. It's not about who can look at the chess board and determine what happened faster. It's turn based.

I would want a bot for something like counter-strike to only be given the information the user is given, nothing more. Otherwise it seems like the AI is given an advantage.

[meerta]

How close is chess to being solved?

(I used to be my high school's chess wiz, right after the first Fischer/Spassky matches, and I'd love to see that obsession finally put to rest.)

We're not at the point where we can say it can be solved. (Like I posted above, computers still don't beat the top players consistently.)

[DavidMTaylor]

Just a quick point of order on the status of "Jeopardy" ...

Ken Jennings, the reigning top human player at Jeopardy, as brilliant and entertaining as he is on a daily basis (@KenJennings), was demolished by Skynet IBM Watson in an epic competition. Jeopardy has been conquered for inhuman-kind.

http://en.wikipedia.org/wiki/Ken_Jennings#IBM_Challenge

[djfatsostupid]

I don't disagree that computers are fully capable of beating humans at Starcraft given intense R&D (and possibly slightly better computers), but I really disagree with where it was placed in that category. I don't think computers are on the cusp of being better than humans at Starcraft, I think they have a really long way to go.

I'm also far from convinced that they have better micro. Maybe they can do perfect marine splits against banelings but can they do the ideal marine split against banelings taking into account that if they split in a perfect way to lose no marines it would involve moving some marines off to a position where they would get picked off by some nearby roaches? Micro cannot be handled by simple algorithms, it is fast clicks *and* very complicated decision making. As other posters have noted, where computers really fall flat against humans at this point is deciding when to engage. Against the best humans their "perfect" micro algorithms would be rapidly dissected and conquered because they are essentially a number of tiny decisions about when to engage.

[Coyne]

I was very pleased to see Calvinball included in the games. Up with Calvinball; down with computers!

[CalvertdeGrey]

I did notice that the game "Diplomacy" was not on the list. The game was created in 1959 and computer versions of the game were made in 1984, 1999 and 2005. The AIs written for different computer versions were completely incapable of defeating even beginner players, much less top level players. The Diplomacy Artificial Intelligence Development Environment (DAIDE) project is attempting to correct this deficiency with varying degrees of success. It will be very interesting to see how the project progresses.

[jalohones]

I definitely think Mornington Crescent would pose some challenges for AI. Could Deep Blue manage the Cockfosters triple reverse lateral retreat move to Theydon Bois, as first illustrated by Stovold under the Putney Reformed interpretation of the original Pimlico rules?

Well no, but Deep Blue is the wrong machine for the job. Mornington Crescent is better played by the University of London's new specialised AI: Bethnal Green.

[Jabberwocky]

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!

I played it for several hours at a Speech meet in NW Indiana, in, hm... 2001? I remember writing down all the rules I had figured out, and then promptly losing that paper. Now I have no idea how to play it. Apparently it's one of those games with a million regional variations, so unless you have someone to teach you...

Also, I consistently forget how to play Euchre, so I'm not sure Mao is the kind of game I should be relearning at this point. XD

[just john]

How close is chess to being solved?

(I used to be my high school's chess wiz, right after the first Fischer/Spassky matches, and I'd love to see that obsession finally put to rest.)

We're not at the point where we can say it can be solved. (Like I posted above, computers still don't beat the top players consistently.)

There are a finite number of possible board positions. That leads me to think the game can be solved, given sufficient horsepower and time.

The ultra brute-force methodology of generating every possible game board and linking each one to the board(s) that could have preceded the board before this move, as well as to all boards that could result from the next move would not be the prettiest solution ever, but it would do all the heavy lifting of solving the game.

Horsepower and time. And clever pruning of duplicate paths.

[ConMan]

How close is chess to being solved?

(I used to be my high school's chess wiz, right after the first Fischer/Spassky matches, and I'd love to see that obsession finally put to rest.)

We're not at the point where we can say it can be solved. (Like I posted above, computers still don't beat the top players consistently.)

There are a finite number of possible board positions. That leads me to think the game can be solved, given sufficient horsepower and time.

The ultra brute-force methodology of generating every possible game board and linking each one to the board(s) that could have preceded the board before this move, as well as to all boards that could result from the next move would not be the prettiest solution ever, but it would do all the heavy lifting of solving the game.

Horsepower and time. And clever pruning of duplicate paths.

Which is true. But do you know just how much horsepower and time? Claude Shannon calculated an approximation of how many possible games of chess there are, and got an answer on the order of 10^120. Assuming each of those games takes up ~1KB of space, you're talking about 10^110 TB of data. This is not a manageable amount of data, and some serious theory is needed to reduce that space to something usable.

[just john]

How close is chess to being solved?

(I used to be my high school's chess wiz, right after the first Fischer/Spassky matches, and I'd love to see that obsession finally put to rest.)

We're not at the point where we can say it can be solved. (Like I posted above, computers still don't beat the top players consistently.)

There are a finite number of possible board positions. That leads me to think the game can be solved, given sufficient horsepower and time.

The ultra brute-force methodology of generating every possible game board and linking each one to the board(s) that could have preceded the board before this move, as well as to all boards that could result from the next move would not be the prettiest solution ever, but it would do all the heavy lifting of solving the game.

Horsepower and time. And clever pruning of duplicate paths.

Which is true. But do you know just how much horsepower and time? Claude Shannon calculated an approximation of how many possible games of chess there are, and got an answer on the order of 10^120. Assuming each of those games takes up ~1KB of space, you're talking about 10^110 TB of data. This is not a manageable amount of data, and some serious theory is needed to reduce that space to something usable.

That's possible games. I betcha a no-prize that the number of possible game boards may be lower, especially when unreachable ones are pruned.

[kgrizzly]

Cathy mentioned that backgammon was omitted from the strip. The best AIs beat the professionals fairly reliably. Not necessarily in every single game, since the dice do introduce an element of chance, but over the course of a decently long match. This was accomplished by Shannon and improved upon by Berliner, IIRC, one of the early successes of AI gaming.

[ConMan]

Which is true. But do you know just how much horsepower and time? Claude Shannon calculated an approximation of how many possible games of chess there are, and got an answer on the order of 10^120. Assuming each of those games takes up ~1KB of space, you're talking about 10^110 TB of data. This is not a manageable amount of data, and some serious theory is needed to reduce that space to something usable.

That's possible games. I betcha a no-prize that the number of possible game boards may be lower, especially when unreachable ones are pruned.

Well, sure. In the same paper, Shannon put an upper bound on the number of possible boards as 10^43. Which means you're still looking at something like 10^30 GB of storage just for the boards. And you still need to find some way of going from "this is the state of the board" to "this is the best possible move" - which means you're going to have to find some way of investigating those 10^120 possible games to determine which ones lead to favourable outcomes.