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 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: 1366
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: 1002: "Game AIs"

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

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



That's the forward-linking part.

Remember, you're typing at somebody whose "first computer" required rooms full of air conditioning to support it, so getting from here to 10^30 GB of storage doesn't sound like such a leap to me. Far more likely than personal jet packs.
* 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 TranquilFury » Thu Jan 12, 2012 1:01 am UTC

Dschingis wrote: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

The idea here isn't to create the illusion of a human opponent, it's asking whether, given the same potential information as a human player, and an interface it is capable of using, can the AI win against a good human following the rules of the game? At the moment, even the maphacking AIs in starcraft can't beat top human players, though they can force a human player to play differently(for example, it's ill advised to go storm tech against the greentea ai).
TranquilFury
 
Posts: 126
Joined: Thu Oct 15, 2009 1:24 am UTC

Re: 1002: "Game AIs"

Postby ConMan » Thu Jan 12, 2012 1:29 am UTC

just john wrote:
ConMan wrote:
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.



That's the forward-linking part.

Remember, you're typing at somebody whose "first computer" required rooms full of air conditioning to support it, so getting from here to 10^30 GB of storage doesn't sound like such a leap to me. Far more likely than personal jet packs.

I admire your optimism. I'm not saying it can't happen, but I think the numbers are bigger than you expect. First, I'll correct myself and say that I meant to write 10^30 TB (this assumes that you could store about 10 boards in 1KB), which is then 10^27 PB. Modern personal hard drives are getting close to the 1 PB mark these days, so I'll use that as the starting point. If we assume that Moore's Law applies to hard drive space (and there's evidence that it used to, but isn't doing so well any more), then how long does it take, at the rate of doubling every 18 months, to get from 1 to 10^27? Pretty simply, it's 18 months * lg 10^27, which is about 134 years. Of course, you could always start from a different point, say 1 EB (so about 1000 PB, which I'm sure some commercial storage is on the order of). In which case, you can knock about 15 years off that estimate.

As for forward-linking, let's assume that it takes a single flop to check everything you need about a single game - so to generate the moves, make sure they're valid, and determine who wins (and that this is the only thing you need to do to determine the best move at any given board state). We're now looking at 10^120 flops, or 10^105 petaflops. Currently, Folding@Home is apparently clocking up something approaching 10 petaflops. Again, assuming Moore's Law applies to the calculations performed by a similar network, then I figure it as taking about 517 years to calculate all 10^120 calculations. Best get started.
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: 1366
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: 1002: "Game AIs"

Postby OP Tipping » Thu Jan 12, 2012 1:41 am UTC

I don't see why, theoretically, a computer couldn't beat humans at Mao, especially if the computer was the experienced player and the humans were being introduced to the game.

Calvinball might be the clincher.
OP Tipping
 
Posts: 83
Joined: Thu Dec 13, 2007 6:23 am UTC

Re: 1002: "Game AIs"

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

ConMan wrote:
just john wrote:
ConMan wrote:
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.



That's the forward-linking part.

Remember, you're typing at somebody whose "first computer" required rooms full of air conditioning to support it, so getting from here to 10^30 GB of storage doesn't sound like such a leap to me. Far more likely than personal jet packs.

I admire your optimism. I'm not saying it can't happen, but I think the numbers are bigger than you expect. First, I'll correct myself and say that I meant to write 10^30 TB (this assumes that you could store about 10 boards in 1KB), which is then 10^27 PB. Modern personal hard drives are getting close to the 1 PB mark these days, so I'll use that as the starting point. If we assume that Moore's Law applies to hard drive space (and there's evidence that it used to, but isn't doing so well any more), then how long does it take, at the rate of doubling every 18 months, to get from 1 to 10^27? Pretty simply, it's 18 months * lg 10^27, which is about 134 years. Of course, you could always start from a different point, say 1 EB (so about 1000 PB, which I'm sure some commercial storage is on the order of). In which case, you can knock about 15 years off that estimate.

As for forward-linking, let's assume that it takes a single flop to check everything you need about a single game - so to generate the moves, make sure they're valid, and determine who wins (and that this is the only thing you need to do to determine the best move at any given board state). We're now looking at 10^120 flops, or 10^105 petaflops. Currently, Folding@Home is apparently clocking up something approaching 10 petaflops. Again, assuming Moore's Law applies to the calculations performed by a similar network, then I figure it as taking about 517 years to calculate all 10^120 calculations. Best get started.


Yupper. Better than having this damn game taking up space in my head.

So, are you trying to say personal jet packs will happen within the next half-millenium? I think not.

Edited to add: No, the forward-linking is only for the NEXT move, no more. Once it's done to all boards in your data set, THEN you have your tool built.
* 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 Eternal Density » Thu Jan 12, 2012 1:50 am UTC

muntoo wrote:[*]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...
Only if you have to start from scratch.

[edit] I had to look up Calvinball
User avatar
Eternal Density
 
Posts: 3533
Joined: Thu Oct 02, 2008 12:37 am UTC
Location: The Hotdog Cart

Re: 1002: "Game AIs"

Postby ConMan » Thu Jan 12, 2012 2:32 am UTC

OP Tipping wrote:I don't see why, theoretically, a computer couldn't beat humans at Mao, especially if the computer was the experienced player and the humans were being introduced to the game.

Calvinball might be the clincher.

You don't think the computer may struggle a bit just interpreting the new rules, particularly if they don't follow any particular format? Unless you explicitly code each new rule for the AI, it's going to have to work it out from some kind of context.
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: 1366
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: 1002: "Game AIs"

Postby CorruptUser » Thu Jan 12, 2012 3:17 am UTC

Computers would win Calvinball instantly, every time. They'd just do nothing but declare that the other person stepped in a "silent-zone" and are unable to make new rules until they leave said zone, oh and they are not allowed to leave said zone.

Boring but practical.

Of course, there could be rules that the loser of the previous game gets to make up 1 rule before the next game, that rule being 'no silent zones'.
User avatar
CorruptUser
 
Posts: 5835
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: 1002: "Game AIs"

Postby ashley » Thu Jan 12, 2012 3:21 am UTC

just john wrote:Remember, you're typing at somebody whose "first computer" required rooms full of air conditioning to support it, so getting from here to 10^30 GB of storage doesn't sound like such a leap to me. Far more likely than personal jet packs.


you obviously have no idea how big of a number that is. that's about 10^40 bits of data. there's about 10^50 atoms on earth.

and you can already buy personal jet packs.
ashley
 
Posts: 4
Joined: Wed Dec 14, 2011 9:14 pm UTC

Re: 1002: "Game AIs"

Postby ashley » Thu Jan 12, 2012 3:27 am UTC

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.


let's see... 10^110 TB =~ 10^123 bits of data, and there's about 10^80 atoms in the universe, so how many universes would we need to store this data?

and are we (along with a bunch of other universes) just part of some chess simulation (think 13th floor, but different)?
ashley
 
Posts: 4
Joined: Wed Dec 14, 2011 9:14 pm UTC

Re: 1002: "Game AIs"

Postby serrath » Thu Jan 12, 2012 3:27 am UTC

Has anyone noticed that global thermonuclear war is notably absent from this list?

Perhaps there just isn't enough data of humans vs. computers in global thermonuclear war. We should try to obtain some...
serrath
 
Posts: 54
Joined: Mon Mar 31, 2008 4:50 am UTC

Re: 1002: "Game AIs"

Postby Tyrannosaur » Thu Jan 12, 2012 3:57 am UTC

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


...burn! Haha exactly what I was thinking- it's relatively easy to make a human.
djessop wrote:The t-shirt should read "There are 11 types of people in the world, those who understand binary, those who don't and those who insist the number above is pronounced as eleven no matter what base you're in".
User avatar
Tyrannosaur
 
Posts: 106
Joined: Thu Sep 02, 2010 5:39 am UTC

Re: 1002: "Game AIs"

Postby neoliminal » Thu Jan 12, 2012 4:54 am UTC

Cosmic Encounter ftw. (The old version, not the new version.)

I find myself strangely attracted to Go as a computer problem. Perhaps because I think it needs a fresh start or perhaps because I'm reading the final chapter of Hikaru no Go.

Or maybe I've been staring at my avatar too long.

Also, I wonder if computers would win at Nothing Beats Rock?
Last edited by neoliminal on Thu Jan 12, 2012 4:55 am UTC, edited 1 time in total.
http://www.goodreads.com/book/show/13451873-unselected
Read My Book. Cost less than coffee. Will probabaly keep you awake longer.
User avatar
neoliminal
 
Posts: 612
Joined: Wed Feb 18, 2009 6:39 pm UTC

Re: 1002: "Game AIs"

Postby Mostlynormal » Thu Jan 12, 2012 4:54 am UTC

I think anyone who thinks they can talk about chess being "solved" either knkows very little about chess or just hasn't thought it through enough. Even if we could muster the computing power to completely brute force the game of chess, would chess be "solved"? Of course not. Maybe a computer managed to perform a bunch of calculations that resembled chess moves, but what does that mean? The computer can't understand chess. No human could read its output. In fact, no AI on a level of intelligence anywhere near comparable to a human's could read it.

Also, I think it's demeaning that these over glorified search engines called chess AIs are taken seriously. They can't really play chess. Chess is not about looking eight or something moves ahead. Chess is about strategy and positions and much more subtle things. I don't doubt that someday we will be able to teach a program to play chess. By that time, though, it would also be able to pass the Turing test.
Mostlynormal
 
Posts: 32
Joined: Sat May 15, 2010 1:53 am UTC

Re: 1002: "Game AIs"

Postby Slesh » Thu Jan 12, 2012 5:00 am UTC

Which means they can pull of some crazy micro tricks.


I just went to find the link to that one before I saw it had been posted. With that kind of exploitative micro, I really can't see a human standing any chance against an AI that makes decent strategic choices. There are similar videos for medivac drops (http://www.youtube.com/watch?v=0EYH-csTttw) and marine splitting (http://www.youtube.com/watch?v=DXUOWXidcY0).
I also remember seeing an AI that could mimic player build orders, remembering and repeating them in future games, around a year ago when I was playing sc2.

If there were an apm cap for the AI, however, it wouldn't be quite so easy.
Slesh
 
Posts: 3
Joined: Thu Jan 12, 2012 4:35 am UTC

Re: 1002: "Game AIs"

Postby Alsadius » Thu Jan 12, 2012 5:11 am UTC

I disagree with the placement of Snakes and Ladders. Computers are capable of beating top humans even today.
User avatar
Alsadius
 
Posts: 81
Joined: Thu Jun 14, 2007 2:14 am UTC

Re: 1002: "Game AIs"

Postby Someguy945 » Thu Jan 12, 2012 5:18 am UTC

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.

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


"A somewhat realistic speed" is subjective, but I think we can quantify it in a way that is undoubtedly fair: The computer should be forced to send commands only by moving robotic arms to control a standard mouse and keyboard.

I think it would even be fine for these robotic arms to have extra "fingers" (for example, the keyboard hand could have a finger over every key at all times) - this is just a natural advantage of being a robot. As long as all input comes through mouse and keyboard, it's legit.
User avatar
Someguy945
 
Posts: 176
Joined: Fri Jul 22, 2011 5:09 am UTC

Re: 1002: "Game AIs"

Postby ConMan » Thu Jan 12, 2012 5:30 am UTC

Alsadius wrote:I disagree with the placement of Snakes and Ladders. Computers are capable of beating top humans even today.

But not consistently. In fact, I'd argue that a human player will beat a computer about as often as the reverse.
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: 1366
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: 1002: "Game AIs"

Postby pmwalk » Thu Jan 12, 2012 6:05 am UTC

I was kind of disappointed The Game wasn't somewhere on the list. Although I have to say, Calvinball is pretty difficult. Still, I spent quite awhile trying to decide where The Game should sit in the chart before I realized I'd lost at least 5 times, and decided to give up on trying to place it.
pmwalk
 
Posts: 2
Joined: Thu Jan 12, 2012 5:56 am UTC
Location: Pittsburgh, PA

Re: 1002: "Game AIs"

Postby TranquilFury » Thu Jan 12, 2012 7:00 am UTC

Someguy945 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.

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


"A somewhat realistic speed" is subjective, but I think we can quantify it in a way that is undoubtedly fair: The computer should be forced to send commands only by moving robotic arms to control a standard mouse and keyboard.

I think it would even be fine for these robotic arms to have extra "fingers" (for example, the keyboard hand could have a finger over every key at all times) - this is just a natural advantage of being a robot. As long as all input comes through mouse and keyboard, it's legit.
Pointless handicap for the AI player, Humans are allowed to use their own keyboard and mouse, it's fair for an AI to be allowed to interact with the game with the virtual equivalent(the bot output is interpreted by the game in the format of cursor position, mouseclicks, and keypresses. While the bot input is the game's graphics and sound or an equivalent representation of the same information). The point I'm trying to make here is that we should ignore the trivial bits, and focus on the part of the problem that makes it hard, which is the timings, decision making, risk taking, and the ability to work from limited information.
TranquilFury
 
Posts: 126
Joined: Thu Oct 15, 2009 1:24 am UTC

Re: 1002: "Game AIs"

Postby Showsni » Thu Jan 12, 2012 7:05 am UTC

It's really easy to make an AI that wins the Game. I could do that on my calculator!

Step 1. Inform calculator that is is now playing the game. Then wipe the memory.
Step 2. Periodically check calculator's memory. Nope, it still hasn't remembered it's playing the game.

As for Mao, since new rules are limited only by the creativity of whoever's playing, the computer would need to be programmed to take anything into account. I could add a rule that you pick a card up unless you call out the sum of the card played two turns ago, the current minute in time and the number of fingers I'm holding up. And then take a shot. Of course, the computer could add rules that are practically impossible for a human to work out...
Showsni
 
Posts: 23
Joined: Wed Sep 14, 2011 9:09 pm UTC

Re: 1002: "Game AIs"

Postby Tolangardh » Thu Jan 12, 2012 7:28 am UTC

In 2002 at the World Bridge Championships, Bill Gates said that "There's no imminent prospect of bridge software being able to play at human levels."

I don't know if he's changed his assessment, but I doubt that the bridge bots are much better now than they were then.
Tolangardh
 
Posts: 1
Joined: Thu Jan 12, 2012 7:24 am UTC

Re: 1002: "Game AIs"

Postby Proginoskes » Thu Jan 12, 2012 9:04 am UTC

That result about checkers isn't exactly right. The result that was proved was that if both sides play perfectly, then the game is a draw. In the paper itself the authors say that they don't have a method for winning in any arbitrary line of play. (That is, the problem of winning a game where a mistake has been made, hasn't been solved.)
User avatar
Proginoskes
 
Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: 1002: "Game AIs"

Postby wagner » Thu Jan 12, 2012 9:21 am UTC

niky wrote:It doesn't have to squint to see a camouflaged human against a like colored background


I can't count the number of times I lost agents in Syndicate trying to figure out how to use the clone shield, before reading the manual and discovering it was only for online multiplayer.
wagner
 
Posts: 22
Joined: Tue Oct 06, 2009 3:18 pm UTC

Re: 1002: "Game AIs"

Postby AvatarIII » Thu Jan 12, 2012 9:42 am UTC

Tolangardh wrote:In 2002 at the World Bridge Championships, Bill Gates said that "There's no imminent prospect of bridge software being able to play at human levels."

I don't know if he's changed his assessment, but I doubt that the bridge bots are much better now than they were then.


that was almost a decade ago, and it only took about 1 decade between computers first beating top humans and top humans last beating computers.
it's anecdotal, but it does go to show how fast computers evolve when it comes to winning games.
User avatar
AvatarIII
 
Posts: 2101
Joined: Fri Apr 08, 2011 12:28 pm UTC
Location: W.Sussex, UK

Re: 1002: "Game AIs"

Postby wagner » Thu Jan 12, 2012 9:45 am UTC

Stilgar wrote:there are tricks that make some units more powerful by constantly micromanaging it which is simply impossible for humans. For example you can watch what the top AI does with mutalisks (it moves them nonstop in range and out of range of the enemy and no mutalisk gets damaged too much).


Why can't humans do this? If you're going to allow a bot to micromanage individual units to that degree, why can't humans be allowed to run similar subroutines? I'm talking about real programming with feedback and conditionals, not just dumb keypress macros. Why not provide an interface to allow the gamer to program more advanced behaviors for units besides the basic guard/retreat/attack? Let the gamer concern themselves with the larger scale strategies and tactics, and while intelligent agents the gamer writes ahead of time handle the lower level stuff. I don't want to be screwed over on a high level match merely because the other person is that fraction of a second faster at positioning new construction than I am.
wagner
 
Posts: 22
Joined: Tue Oct 06, 2009 3:18 pm UTC

Re: 1002: "Game AIs"

Postby meerta » Thu Jan 12, 2012 10:56 am UTC

Mostlynormal wrote:I think anyone who thinks they can talk about chess being "solved" either knkows very little about chess or just hasn't thought it through enough. Even if we could muster the computing power to completely brute force the game of chess, would chess be "solved"? Of course not. Maybe a computer managed to perform a bunch of calculations that resembled chess moves, but what does that mean? The computer can't understand chess. No human could read its output. In fact, no AI on a level of intelligence anywhere near comparable to a human's could read it.

Also, I think it's demeaning that these over glorified search engines called chess AIs are taken seriously. They can't really play chess. Chess is not about looking eight or something moves ahead. Chess is about strategy and positions and much more subtle things. I don't doubt that someday we will be able to teach a program to play chess. By that time, though, it would also be able to pass the Turing test.


Well, they play chesss, by the rules, and that is playing chess. And if they can beat Kramnik then to all intents and purposes they are masters of strategy. They play differently, sure, and they don't know they're playing, but what is meant by "solving" a game is exactly what has happened in the case of Connect 4, draughts/checkers, and so on.
meerta
 
Posts: 47
Joined: Mon Aug 10, 2009 11:25 am UTC

Re: 1002: "Game AIs"

Postby Klear » Thu Jan 12, 2012 11:18 am UTC

ashley 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.


let's see... 10^110 TB =~ 10^123 bits of data, and there's about 10^80 atoms in the universe, so how many universes would we need to store this data?

and are we (along with a bunch of other universes) just part of some chess simulation (think 13th floor, but different)?


According to this, the universe can store approximately 10^120 bits of data, so... what, 1000 universes?

These are both approximations, though. Maybe it fits exactly and the universe IS used to store all possible games of chess.

Edit: It seems like mankind has to choose here - either we will use the universe to solve chess, or to run a simulation of the universe...
User avatar
Klear
 
Posts: 1562
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1002: "Game AIs"

Postby SirMustapha » Thu Jan 12, 2012 11:23 am UTC

Mostlynormal wrote:I think anyone who thinks they can talk about chess being "solved" either knkows very little about chess or just hasn't thought it through enough. Even if we could muster the computing power to completely brute force the game of chess, would chess be "solved"? Of course not. Maybe a computer managed to perform a bunch of calculations that resembled chess moves, but what does that mean? The computer can't understand chess. No human could read its output. In fact, no AI on a level of intelligence anywhere near comparable to a human's could read it.

Also, I think it's demeaning that these over glorified search engines called chess AIs are taken seriously. They can't really play chess. Chess is not about looking eight or something moves ahead. Chess is about strategy and positions and much more subtle things. I don't doubt that someday we will be able to teach a program to play chess. By that time, though, it would also be able to pass the Turing test.


Weird: I remember reading a post almost exactly the same as this, in another thread, quite some time ago. I'm pretty sure it wasn't you, though, because of your post count. That's a very crazy déjà vu. The fallacy here is that, well, "playing a game" is effectively all about following the rules and, in most cases, trying to win. EVERYTHING ELSE is optional and subjective. Everything. If a computer follows the rules and is able to make moves, then it plays chess -- and if it consistently beats the world's top human players, then, well, there are no arguments against facts. Only whining.
User avatar
SirMustapha
 
Posts: 1303
Joined: Mon Jul 21, 2008 6:07 pm UTC

Re: 1002: "Game AIs"

Postby Stilgar » Thu Jan 12, 2012 11:45 am UTC

wagner wrote:
Stilgar wrote:there are tricks that make some units more powerful by constantly micromanaging it which is simply impossible for humans. For example you can watch what the top AI does with mutalisks (it moves them nonstop in range and out of range of the enemy and no mutalisk gets damaged too much).


Why can't humans do this? If you're going to allow a bot to micromanage individual units to that degree, why can't humans be allowed to run similar subroutines? I'm talking about real programming with feedback and conditionals, not just dumb keypress macros. Why not provide an interface to allow the gamer to program more advanced behaviors for units besides the basic guard/retreat/attack? Let the gamer concern themselves with the larger scale strategies and tactics, and while intelligent agents the gamer writes ahead of time handle the lower level stuff. I don't want to be screwed over on a high level match merely because the other person is that fraction of a second faster at positioning new construction than I am.


OK but then what is the difference between a human and a program? After all the AI that micromanages the mutas was built by humans too.

BTW the micro of the mutas is relatively hard computational problem. They calculate "forces" that push the unit in different directions and the sum of the vectors determines the direction in which the unit should move. You cannot really do this in real time as human and it would definitely qualify as part of the tactics.
Stilgar
 
Posts: 7
Joined: Wed Jan 11, 2012 12:34 pm UTC

Re: 1002: "Game AIs"

Postby Klear » Thu Jan 12, 2012 11:53 am UTC

SirMustapha wrote:
Mostlynormal wrote:I think anyone who thinks they can talk about chess being "solved" either knkows very little about chess or just hasn't thought it through enough. Even if we could muster the computing power to completely brute force the game of chess, would chess be "solved"? Of course not. Maybe a computer managed to perform a bunch of calculations that resembled chess moves, but what does that mean? The computer can't understand chess. No human could read its output. In fact, no AI on a level of intelligence anywhere near comparable to a human's could read it.

Also, I think it's demeaning that these over glorified search engines called chess AIs are taken seriously. They can't really play chess. Chess is not about looking eight or something moves ahead. Chess is about strategy and positions and much more subtle things. I don't doubt that someday we will be able to teach a program to play chess. By that time, though, it would also be able to pass the Turing test.


Weird: I remember reading a post almost exactly the same as this, in another thread, quite some time ago. I'm pretty sure it wasn't you, though, because of your post count. That's a very crazy déjà vu. The fallacy here is that, well, "playing a game" is effectively all about following the rules and, in most cases, trying to win. EVERYTHING ELSE is optional and subjective. Everything. If a computer follows the rules and is able to make moves, then it plays chess -- and if it consistently beats the world's top human players, then, well, there are no arguments against facts. Only whining.


Actually, playing a game is about having fun. Everything else, including the need for rules and win conditions is optional and subjective.
User avatar
Klear
 
Posts: 1562
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1002: "Game AIs"

Postby TranquilFury » Thu Jan 12, 2012 12:17 pm UTC

wagner wrote:
Stilgar wrote:there are tricks that make some units more powerful by constantly micromanaging it which is simply impossible for humans. For example you can watch what the top AI does with mutalisks (it moves them nonstop in range and out of range of the enemy and no mutalisk gets damaged too much).


Why can't humans do this? If you're going to allow a bot to micromanage individual units to that degree, why can't humans be allowed to run similar subroutines? I'm talking about real programming with feedback and conditionals, not just dumb keypress macros. Why not provide an interface to allow the gamer to program more advanced behaviors for units besides the basic guard/retreat/attack? Let the gamer concern themselves with the larger scale strategies and tactics, and while intelligent agents the gamer writes ahead of time handle the lower level stuff. I don't want to be screwed over on a high level match merely because the other person is that fraction of a second faster at positioning new construction than I am.
I would enjoy a game with trainable AI like that, but stilgar was, I believe, talking about this: http://www.youtube.com/watch?v=nNpy8Wnv ... re=related
Humans pros do micromanage mutalisks too, but in different situations with different methods, a human will typically have a control group of 11 mutalisks+ 1 overlord and can effectively use it against non-splash units with range greater than muta, which the ai sucks at, here's Jaedong: http://www.youtube.com/watch?v=o1MVOqrm4qc

Yes a human player will take more damage against splash, but that's not why human players go muta. Human players go muta for the map control and time, when there's a muta threat your opponent can't really move out of his base, which lets you macro and/or tech much more safely, and shuts down a lot of harrass type plays.
Current AI in starcraft basically operates under the mindset of:
"hope he doesn't kill me before I get the one unit I know how to use well" then
"ok, i finally got the unit I know how to use well, I hope my opponent makes a mistake now so I can kill him before he out techs me".
TranquilFury
 
Posts: 126
Joined: Thu Oct 15, 2009 1:24 am UTC

Re: 1002: "Game AIs"

Postby TranquilFury » Thu Jan 12, 2012 12:19 pm UTC

Klear wrote:Actually, playing a game is about having fun. Everything else, including the need for rules and win conditions is optional and subjective.

Depends what your reason for playing the game is, a lot of people make their living from starcraft, especially in korea.
TranquilFury
 
Posts: 126
Joined: Thu Oct 15, 2009 1:24 am UTC

Re: 1002: "Game AIs"

Postby Chunes » Thu Jan 12, 2012 12:27 pm UTC

What I'd like to see is an AI that can beat NetHack.

It's a task yet to be accomplished even remotely adequately, much less at human levels (speed runs, conducts, etc.)
Chunes
 
Posts: 1
Joined: Thu Jan 12, 2012 12:25 pm UTC

Re: 1002: "Game AIs"

Postby Stilgar » Thu Jan 12, 2012 12:36 pm UTC

TranquilFury wrote:
Klear wrote:Actually, playing a game is about having fun. Everything else, including the need for rules and win conditions is optional and subjective.

Depends what your reason for playing the game is, a lot of people make their living from starcraft, especially in korea.


I once watched an interview with Veselin Topalov ( world chess champion in 2005 - http://en.wikipedia.org/wiki/Veselin_Topalov ) and he was asked if he considered chess to be a game, an art or a sport. He said that for the masses chess is just a game, for amateurs that really understand high-level games it is an art and for him it is a sport because he plays for results.
Stilgar
 
Posts: 7
Joined: Wed Jan 11, 2012 12:34 pm UTC

Re: 1002: "Game AIs"

Postby Klear » Thu Jan 12, 2012 12:51 pm UTC

Stilgar wrote:
TranquilFury wrote:
Klear wrote:Actually, playing a game is about having fun. Everything else, including the need for rules and win conditions is optional and subjective.

Depends what your reason for playing the game is, a lot of people make their living from starcraft, especially in korea.


I once watched an interview with Veselin Topalov ( world chess champion in 2005 - http://en.wikipedia.org/wiki/Veselin_Topalov ) and he was asked if he considered chess to be a game, an art or a sport. He said that for the masses chess is just a game, for amateurs that really understand high-level games it is an art and for him it is a sport because he plays for results.


Exactly. IMO (and obvioulsy your definition may vary) a game is played for pleasure. If you do it for money or whatever, it stops being a game.
User avatar
Klear
 
Posts: 1562
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1002: "Game AIs"

Postby threedognice » Thu Jan 12, 2012 12:55 pm UTC

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

Computer AI is still AI, inside the game or not.

Whole idea is ridiculous no matter how you look at it. On one hand you are creating a program that is crippled to the point where it behaves like a human, and at the same time you are trying to create AI powerful enough to defeat a real player. Absolute bloody nonsense.
threedognice
 
Posts: 15
Joined: Mon Dec 19, 2011 10:07 am UTC

Re: 1002: "Game AIs"

Postby meerta » Thu Jan 12, 2012 1:06 pm UTC

Klear wrote:
Stilgar wrote:
TranquilFury wrote:
Klear wrote:Actually, playing a game is about having fun. Everything else, including the need for rules and win conditions is optional and subjective.

Depends what your reason for playing the game is, a lot of people make their living from starcraft, especially in korea.


I once watched an interview with Veselin Topalov ( world chess champion in 2005 - http://en.wikipedia.org/wiki/Veselin_Topalov ) and he was asked if he considered chess to be a game, an art or a sport. He said that for the masses chess is just a game, for amateurs that really understand high-level games it is an art and for him it is a sport because he plays for results.


Exactly. IMO (and obvioulsy your definition may vary) a game is played for pleasure. If you do it for money or whatever, it stops being a game.


That premise pretty much undermines half this comic, and very stipulative about how we use the word "game" to boot.
meerta
 
Posts: 47
Joined: Mon Aug 10, 2009 11:25 am UTC

Re: 1002: "Game AIs"

Postby Stilgar » Thu Jan 12, 2012 1:10 pm UTC

The comic obviously uses the mathematical definition of "game" ( http://en.wikipedia.org/wiki/Mathematical_game )
Stilgar
 
Posts: 7
Joined: Wed Jan 11, 2012 12:34 pm UTC

PreviousNext

Return to Individual XKCD Comic Threads

Who is online

Users browsing this forum: BlitzGirl, ggh, jpk, l3q0tj2sw, mscha, OmniLiquid and 10 guests