1002: "Game AIs"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Magistrates, Prelates, Moderators General

Re: 1002: "Game AIs"

Postby richP » Wed Jan 11, 2012 3:34 pm UTC

penguinoid wrote: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.
richP
 
Posts: 90
Joined: Wed Aug 17, 2011 3:28 pm UTC

Re: 1002: "Game AIs"

Postby jonas » Wed Jan 11, 2012 3:40 pm UTC

Where would tape measure extending go in this table?
jonas
 
Posts: 37
Joined: Mon Mar 26, 2007 6:12 pm UTC

Re: 1002: "Game AIs"

Postby dragondave » Wed Jan 11, 2012 3:46 pm UTC

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.
dragondave
 
Posts: 22
Joined: Fri Nov 14, 2008 8:46 pm UTC

Re: 1002: "Game AIs"

Postby DennyMo » Wed Jan 11, 2012 3:57 pm UTC

shirosuzume wrote: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.
DennyMo
 
Posts: 25
Joined: Fri Apr 23, 2010 10:50 am UTC

Re: 1002: "Game AIs"

Postby enumerated powers » Wed Jan 11, 2012 4:02 pm UTC

pbnjstowell wrote:
penguinoid wrote: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/.
User avatar
enumerated powers
 
Posts: 48
Joined: Fri Dec 17, 2010 10:22 pm UTC
Location: Dayton Ohio USA

Re: 1002: "Game AIs"

Postby asliceofpi » Wed Jan 11, 2012 4:17 pm UTC

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. :D
User avatar
asliceofpi
 
Posts: 21
Joined: Mon Jan 08, 2007 7:42 am UTC
Location: USA

Re: 1002: "Game AIs"

Postby shapenaji » Wed Jan 11, 2012 4:21 pm UTC

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.
shapenaji
 
Posts: 2
Joined: Wed Jan 11, 2012 4:07 pm UTC

Re: 1002: "Game AIs"

Postby Felstaff » Wed Jan 11, 2012 4:21 pm UTC

Pawns can't move that way, you stupid arm!
Image
Habent sua fata libelli et balli
User avatar
Felstaff
Occam's Taser
 
Posts: 4945
Joined: Fri Feb 01, 2008 7:10 pm UTC
Location: ¢ ₪ ¿ ¶ § ∴ ® © ™ ؟ ¡ ‽ æ Þ ° ₰ ₤ ಡಢ

Re: 1002: "Game AIs"

Postby Dschingis » Wed Jan 11, 2012 4:25 pm UTC

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
Dschingis
 
Posts: 1
Joined: Wed Jan 11, 2012 4:14 pm UTC

Re: 1002: "Game AIs"

Postby benmoreassynt » Wed Jan 11, 2012 4:27 pm UTC

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?
benmoreassynt
 
Posts: 4
Joined: Mon May 09, 2011 4:38 pm UTC

Re: 1002: "Game AIs"

Postby need4speed » Wed Jan 11, 2012 4:29 pm UTC

Camquin wrote: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.
need4speed
 
Posts: 5
Joined: Fri Nov 18, 2011 6:22 pm UTC

Re: 1002: "Game AIs"

Postby TheEngineer » Wed Jan 11, 2012 4:59 pm UTC

What about Cow Tipping
TheEngineer
 
Posts: 20
Joined: Wed Nov 24, 2010 2:40 pm UTC

Re: 1002: "Game AIs"

Postby bmonk » Wed Jan 11, 2012 5:00 pm UTC

Capt.Awesome wrote: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!
"The position was well put indeed in a famous speech by Jzbl to the graduates of the Central Saturnian University, when he said that it was a source of great pride to him that although hardly anybody knew anything any longer, everybody now knew how to find out everything."
User avatar
bmonk
 
Posts: 622
Joined: Thu Feb 18, 2010 10:14 pm UTC

Re: 1002: "Game AIs"

Postby dp2 » Wed Jan 11, 2012 5:41 pm UTC

muntoo wrote: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.
dp2
 
Posts: 293
Joined: Wed Aug 18, 2010 3:06 pm UTC

Re: 1002: "Game AIs"

Postby philsov » Wed Jan 11, 2012 6:03 pm UTC

glasnt wrote: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.
The time and seasons go on, but all the rhymes and reasons are wrong
I know I'll discover after its all said and done I should've been a nun.
User avatar
philsov
Not a fan of Diane Kruger
 
Posts: 1350
Joined: Sat Sep 20, 2008 7:58 pm UTC
Location: Texas

Re: 1002: "Game AIs"

Postby melthengylf » Wed Jan 11, 2012 6:13 pm UTC

"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".
melthengylf
 
Posts: 26
Joined: Sat Jun 13, 2009 10:45 pm UTC

Re: 1002: "Game AIs"

Postby aegiswings » Wed Jan 11, 2012 6:34 pm UTC

Oh me yarm, 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.
aegiswings
 
Posts: 16
Joined: Fri Dec 05, 2008 6:10 pm UTC

Re: 1002: "Game AIs"

Postby cynicalbastard » Wed Jan 11, 2012 6:39 pm UTC

muntoo wrote: 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...
Poo-tee-weet?
cynicalbastard
 
Posts: 18
Joined: Wed May 27, 2009 8:08 pm UTC

Re: 1002: "Game AIs"

Postby Steve the Pocket » Wed Jan 11, 2012 6:46 pm UTC

glasnt wrote: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.

mania wrote: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.
cephalopod9 wrote:Only on Xkcd can you start a topic involving Hitler and people spend the better part of half a dozen pages arguing about the quality of Operating Systems.

Baige.
User avatar
Steve the Pocket
 
Posts: 459
Joined: Mon Apr 23, 2007 4:02 am UTC
Location: Going downtuuu in a Luleelurah!

Re: 1002: "Game AIs"

Postby srimech » Wed Jan 11, 2012 6:59 pm UTC

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.
srimech
 
Posts: 1
Joined: Wed Jan 11, 2012 6:43 pm UTC

Re: 1002: "Game AIs"

Postby Cousj001 » Wed Jan 11, 2012 7:11 pm UTC

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.
Magic is real, unless declared integer.
Cousj001
 
Posts: 25
Joined: Wed Aug 31, 2011 10:55 am UTC

Re: 1002: "Game AIs"

Postby threedognice » Wed Jan 11, 2012 7:23 pm UTC

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
threedognice
 
Posts: 15
Joined: Mon Dec 19, 2011 10:07 am UTC

Re: 1002: "Game AIs"

Postby forbiddenSpell » Wed Jan 11, 2012 7:58 pm UTC

philsov wrote:
glasnt wrote: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.
forbiddenSpell
 
Posts: 15
Joined: Sat Oct 29, 2011 4:44 pm UTC

Re: 1002: "Game AIs"

Postby PCal » Wed Jan 11, 2012 8:09 pm UTC

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.
PCal
 
Posts: 60
Joined: Mon Jun 15, 2009 1:00 am UTC

Re: 1002: "Game AIs"

Postby Sprocket » Wed Jan 11, 2012 8:11 pm UTC

01.11.2012 Randall Munroe makes us all think of Ken Jennings as a sexual being.
You bastard.
"She’s a free spirit, a wind-rider, she’s at one with nature, and walks with the kodama eidolons”
ImageImage Image Image
User avatar
Sprocket
Seymour
 
Posts: 5742
Joined: Mon Mar 26, 2007 6:04 pm UTC
Location: impaled on Beck's boney hips.

Re: 1002: "Game AIs"

Postby just john » Wed Jan 11, 2012 8:52 pm UTC

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.)
* Radio Free Entropy: http://just-john.com/jjMusic
User avatar
just john
 
Posts: 60
Joined: Thu Nov 08, 2007 2:11 pm UTC
Location: Poughkeepsie, NY

Re: 1002: "Game AIs"

Postby Trebla » Wed Jan 11, 2012 9:10 pm UTC

threedognice wrote: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.

someone else wrote: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.
Trebla
 
Posts: 251
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: 1002: "Game AIs"

Postby Роберт » Wed Jan 11, 2012 9:55 pm UTC

Steve the Pocket wrote:
mania wrote: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.
The Great Hippo wrote:[T]he way we treat suspected terrorists genuinely terrifies me.
Роберт
 
Posts: 4301
Joined: Wed May 14, 2008 1:56 am UTC

Re: 1002: "Game AIs"

Postby meerta » Wed Jan 11, 2012 10:21 pm UTC

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.)
meerta
 
Posts: 47
Joined: Mon Aug 10, 2009 11:25 am UTC

Re: 1002: "Game AIs"

Postby DavidMTaylor » Wed Jan 11, 2012 10:44 pm UTC

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
DavidMTaylor
 
Posts: 1
Joined: Wed Jan 11, 2012 10:31 pm UTC

Re: 1002: "Game AIs"

Postby djfatsostupid » Wed Jan 11, 2012 10:47 pm UTC

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.
djfatsostupid
 
Posts: 8
Joined: Fri Apr 09, 2010 3:07 pm UTC

Re: 1002: "Game AIs"

Postby Coyne » Wed Jan 11, 2012 11:18 pm UTC

I was very pleased to see Calvinball included in the games. Up with Calvinball; down with computers!
User avatar
Coyne
 
Posts: 385
Joined: Fri Dec 18, 2009 12:07 am UTC

Re: 1002: "Game AIs"

Postby CalvertdeGrey » Wed Jan 11, 2012 11:27 pm UTC

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.
CalvertdeGrey
 
Posts: 1
Joined: Wed Jan 11, 2012 11:20 pm UTC

Re: 1002: "Game AIs"

Postby jalohones » Wed Jan 11, 2012 11:28 pm UTC

benmoreassynt wrote: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.
User avatar
jalohones
 
Posts: 58
Joined: Wed Feb 23, 2011 5:12 am UTC

Re: 1002: "Game AIs"

Postby Jabberwocky » Wed Jan 11, 2012 11:33 pm UTC

shirosuzume wrote: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
Jabberwocky
 
Posts: 10
Joined: Sat Jul 04, 2009 5:52 am UTC

Re: 1002: "Game AIs"

Postby just john » Thu Jan 12, 2012 12:07 am UTC

meerta wrote:
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.
* Radio Free Entropy: http://just-john.com/jjMusic
User avatar
just john
 
Posts: 60
Joined: Thu Nov 08, 2007 2:11 pm UTC
Location: Poughkeepsie, NY

Re: 1002: "Game AIs"

Postby ConMan » Thu Jan 12, 2012 12:33 am UTC

just john wrote:
meerta wrote:
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.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1405
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: 1002: "Game AIs"

Postby just john » Thu Jan 12, 2012 12:37 am UTC

ConMan wrote:
just john wrote:
meerta wrote:
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.
* Radio Free Entropy: http://just-john.com/jjMusic
User avatar
just john
 
Posts: 60
Joined: Thu Nov 08, 2007 2:11 pm UTC
Location: Poughkeepsie, NY

Re: 1002: "Game AIs"

Postby kgrizzly » Thu Jan 12, 2012 12:42 am UTC

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.
kgrizzly
 
Posts: 30
Joined: Sat Aug 09, 2008 9:55 am UTC

Re: 1002: "Game AIs"

Postby ConMan » Thu Jan 12, 2012 12:53 am UTC

just john wrote:
ConMan wrote: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.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1405
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

PreviousNext

Return to Individual XKCD Comic Threads

Who is online

Users browsing this forum: BlitzGirl, broarbape, Google [Bot], speising, Yahoo [Bot] and 27 guests