1002: "Game AIs"

[VectorZero]

*two penalty cards to Randall, Jared, xkiQ, shirosuzume, TomRobbins, pareidolon, ribis and pbnjstowell*

Jack Of Spades

Spades

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

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.

That's not even cheating by my standards, cheating would be having full map information without scouting, or getting more resources than the human player. If you go look at the BW ai competitions(which are currently better than any sc2 ai), even though they are able to execute mutalisk micro better than any human, the decisions on when to engage and disengage are extremely bad.

[ocean_soul]

I think d&d may be even further down than Calvin ball. This of course depends on the GM...

[hailthefish]

Glad to see there ACTUALLY ARE other human beings who have played Mao.



And other than the rule generation portion, a computer that could beat top humans at Mao wouldn't be THAT hard. It just wouldn't be fair because computers don't randomly have the urge to talk.

[lly]

Glad to see there ACTUALLY ARE other human beings who have played Mao.

This was, approximately, my response >_>

Then I found out there was a wikipedia page for it. I guess I shouldn't be surprised.

[ribis]

*two penalty cards to Randall, Jared, xkiQ, shirosuzume, TomRobbins, pareidolon, ribis and pbnjstowell*

Jack Of Spades

Spades

Thank you sir, may I have another?

And other than the rule generation portion, a computer that could beat top humans at Mao wouldn't be THAT hard. It just wouldn't be fair because computers don't randomly have the urge to talk.

Ignoring Turing-test compliance, control of rule generation would ensure a swift AI victory; on every play, it could demand heavy math with (say) the face value of the card and the time of day as factors. Of course, it would remain as vulnerable as any given Chairman to ending the game wearing all its players' drinks...

[BlitzGirl]

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

I was also disappointed.

Thirded. Including Tic-Tac-Toe but omitting Global Thermonuclear War? *shakes head*

[Erinaceus]

What about backgammon? TD-gammon (a temporal-difference-learning algorithm for backgammon) was developed in 1992, and has actually created strategies that were unknown before.

[Nomic]

Where's Nomic Randall? Shame....

Edited out spam link. -Lanicita

I'm right here.

Calvinball is basically a variant of Nomic, isn't it? Altough without players taking turns to alter the rules and instead just shouting whatever they come up.

[xatm092]

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!

At Bath University in the UK there's a bunch of us in the table top society who often play "Bath 5-card talking Mao". I would explain our specific set of rules, but the only rule I'm allowed to tell you is this one.

[noodle]

Being a regular reader, I'm assuming Randall that you actually believe that there is nothing a human could do that an AI couldn't do better. Both UTMs yeah?

However, I find it interesting that there are rarely discussions centered around the computational methods of human computing engines. They are totally and utterly associate in the methods, and hence experienced based.

For example, to compare any computer playing chess with a human is quite unfair - most human chess masters have been (self-)programmed for many hours a day for decades to become the chess masters they are. No computer in existence has ever had that amount of programming (associative or otherwise) over that period of time. Even accounting for the relatively slow processing speed of the human computing engine.

[orangedragonfire]

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

No, it's not. Why do people always get the formulation of this wrong? There are other rules, so "There is only one rule" is a lie. Also, you can tell people that you are not allowed to talk about the other rules, so "You can't tell the rules" is wrong too. Instead, the usual way of combining this into an elegant statement is:

The only rule you can speak of is this one.


/edit: congratulations to xatm092 for getting this right before I even wrote my post

/edit 2: Given that there are quite a few people interested in Mao here, I wonder whether it would be feasible to play Mao on this forum?

[zdanee]

Being a mediocre Go player I still can beat pretty much any Go-bots you throw at me. Most of the time I give handicap stones to the bot. Still a long time till a computer will beat a Korean grandpa in Go.

[synp]

What about Bridge?

Seems like a computer should be able to win at Bridge, but I think they still lose to even enthusiast humans.

[AvatarIII]

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

No, it's not. Why do people always get the formulation of this wrong? There are other rules, so "There is only one rule" is a lie. Also, you can tell people that you are not allowed to talk about the other rules, so "You can't tell the rules" is wrong too. Instead, the usual way of combining this into an elegant statement is:

The only rule you can speak of is this one.


/edit: congratulations to xatm092 for getting this right before I even wrote my post

/edit 2: Given that there are quite a few people interested in Mao here, I wonder whether it would be feasible to play Mao on this forum?

question: how do you prevent new players from breaking the rules without knowing? you can't tell them that they have broken a rule, because that would be telling them a rule.

Spoiler:

as far as i can tell, it is essentially Uno though

[petz]

question: how do you prevent new players from breaking the rules without knowing? you can't tell them that they have broken a rule, because that would be telling them a rule.

Sure, you can. Tell them, they did something wrong, but don't tell them what.

[AvatarIII]

question: how do you prevent new players from breaking the rules without knowing? you can't tell them that they have broken a rule, because that would be telling them a rule.

Sure, you can. Tell them, they did something wrong, but don't tell them what.

I suppose that makes sense.

[Stilgar]

Can someone confirm that an AI team in Counter-Strike can win against a top team in actual 5 vs 5 tournament style game? I kind of doubt it especially if the human team tweaks tactics specifically to counter the AI team.

[Maurog]

Must be some helluva tactics to counter the "get into line of sight, shoot faster than humans, never miss" strategy the AI team will be employing.

[Stilgar]

True but even if the AI does not miss 2-3 human players will shoot it with at most 1 person lost. Plus, there are granades, planting bombs and camping them, etc.

[AvatarIII]

iComic JK recently and i just found this strip

http://comicjk.com/comic.php/356

bit of a coincidence that it mentions Mao, and until today i had never heard of it, and I read both comics today.

also in the comments section Calvinball is mentioned.

[hyperpape]

It's worth noting that Go AI has gotten very good in just the past few years. On 9x9 boards, they are competitive with professionals. On 19x19 boards, they are still a good bit weaker than that, but stronger than most players will ever reach, even with pretty serious study. It's hard to say where things are going--there's still steady progress, but we don't know if it will soon plateau or whether it'll continue towards professional strength.

When I started playing, 6 or 7 years ago, I could say that I might one day be stronger than any computer program in existence. That ship has long since sailed.

See http://www.computer-go.info/h-c/index.html, http://senseis.xmp.net/?ZenGoProgram

[DukeTwicep]

I don't think there is a winner or loser in "7 minutes in heaven", not from the game rules I've read on the net, but I guess that if you refuse to kiss you might be out. I can't see how a computer would be able to lose at this though, just program the damn computer to never refuse, but of course program it to refuse when the other part doesn't want to. I'd say it's out of the question that you're out if you kiss someone against their will.

And Calvinball, I can't see any humans "winning" at this game. Doesn't seem like there Is a winning move. Saying computers can't win at this game is pretty hypocritical as you can't expect anyone else to win at it either (if I'm correct). Regarding the word "outplay" I'd say it's irrelevant in this game, the game doesn't seem logically consistent.

Regarding the difficulty "computers may never outplay humans". Does that mean that Randall believes that we will never invent AI's that are equal and/or better than humans? I'd have put it as "no computer winner in the next 50 years". Or put emphasis on the word "may" instead (semantics, I know).

Regarding those who think it's unfair that the computers can do so much with so little time, I assume you want AI's that can replace human competition so that you can play single-player instead of multi-player? Of course, there's not much use in having computers compete with humans just to see who is the fastest or strongest. Games are supposed to be fun or competitive, and I guess that's why we have men-only football/sprinting/jumping/etc. as well as the women-only counterparts, it wouldn't be fair to put them in the same game as men are genetically better than women at these sort of things (and women are better than men in many other ways).

[rileyrulesu]

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.

It doesn't matter, the best AI's are still nowhere near top humans here is the annual starcraft AI competition, and while I'm not sure they have actually played against top players, by just watching the matches you can tell they're not very good. While they may have unlimited APM, they are nowhere near smart enough to have the decision making nessecary to beat top players.

[niky]

The thing with ultra-strong video game AI is it has the advantage of perfect knowledge of the playing field and perfect knowledge of the positions of all enemy players. It doesn't have to squint to see a camouflaged human against a like colored background, it doesn't have to guess which direction those footsteps are coming from (poorly scripted bots in CS1 would look directly at the source of footsteps behind walls, and they don't miss... not even with grenades... but even with that...

True but even if the AI does not miss 2-3 human players will shoot it with at most 1 person lost. Plus, there are granades, planting bombs and camping them, etc.

The nuances of team-play are difficult to program into bots without relying on pre-set scripts. And even with those pre-set scripts, the bots eventually become predictable (but then, this is true of most mid-level players, anyway). On a map with enough alternative lines of attack, a human team with enough shooting skill can dominate an all AI team. Even better, a human-led AI team can dominate an all AI team.

I believe at the highest level of StarCraft, as long as the AI doesn't have full knowledge of the map and unit positions, a human player can still outplay it. Even an insane level of micromanagement (which would simply allow for easier targetting of large units in swarms of attackers) will not make up for basically faulty tactics.

[Louis XIV]

I don't think there is a winner or loser in "7 minutes in heaven"...

This reminds me the Doctor Who quote "Biting is excellent: It's like kissing, only there's a winner."
So maybe we should consider a variant of "7 minutes in heaven" where kissing is replaced by biting.

[Schumi]

I had to look up seven minutes in heaven.

I had to look up nearly everything else!

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?"

Yes. That's the joke.

[TheSingingNerd]

Depending on how you interpret Calvinball rules, it may be possibly that humans can remain competitive forever.

If rule making is turn based, then any game where you get to make the first rule, make this a rule: "Non-humans may not make rules." In which case, you can then proceed to decide what defines winning at your leisure. If the "no rule may ever be used twice" applies to all games of Calvinball ever, you can subtly change this rule an infinite amount of times to something like "Non-humans and people named Colin Firth may not make new rules" etc. Of course, if the computer is allowed to go first, then it should be able to make a similar rule against humans. So at best you're winning 50% of one-on-one games.

If it isn't turn based, and its just "whoever says something first gets to make a rule", then a fairly basic AI could instantly make the first rule before a human had a chance to think, rendering it 100% winnable by AI.

Furthermore, if there was an android capable of passing an IRL turing test who was willing to lie about being AI, then they could beat this method of winning as well.

[AvatarIII]

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?"

Yes. That's the joke.

that's what i figured too, and guess that's why it is put directly between "computers can sometimes beat top humans" and "computers may never be able to beat humans"

[Stilgar]

I believe at the highest level of StarCraft, as long as the AI doesn't have full knowledge of the map and unit positions, a human player can still outplay it. Even an insane level of micromanagement (which would simply allow for easier targetting of large units in swarms of attackers) will not make up for basically faulty tactics.

The comic is correct in that the AI cannot do it yet but it will be able to do it eventually. The StarCraft I AIs employ a decent level of tactics and strategies copied from normal players and there are trickses 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). Another example will be splitting units against banelings or against tanks. The AI may be able to win with inferior strategies and tactics by virtue of making some units stronger than they are designed to be and thus introducing imbalance in the game. Of course there is a limit of how inferior the strategies and tactics might be but given extensive research the strategies and tactics will in fact become good enough.

[Purge]

I thought that Honda Realdoll won against David Carradine back in June 2009.

[qwrrty]

I'm still trying to find the perfect algorithm for GHOST.

[strix99]

The on game that heard about recently on NPR that was computationally difficult was Solitare, it's currently unknown how many shuffels of the deck there are that are winnable. It's not possible to win every game of Solitare some shuffles of the deck are un-winnable, the only way for a computer to "win" is to compute all possible 52! shuffels of a deck, after I heard this story I did some quick napkin math and figured you could easily eliminate somewhere around 12! to 8! (can't remember exactly what I came up with and have no desire to work it out again) possible shuffels as definitively unwinnible, but even 52! - 12! is still a pretty big universe. Now it's not a game you can compete against a human in so it doesn't match what was going on in this comic but an interesting problem.

[FrobozzWizard]

I was surprised to see a complete lack of mention of any of the mancala games, which have a wide following in Africa.

As far as Starcraft is concerned, the best AIs, such as the Berkeley Overmind, are competitive with professional players right now.

[Stilgar]

I was surprised to see a complete lack of mention of any of the mancala games, which have a wide following in Africa.

As far as Starcraft is concerned, the best AIs, such as the Berkeley Overmind, are competitive with professional players right now.

No, right now they are not. They are competitive with high level amateur players (which is still pretty impressive) but not with professional players.

[jonadab]

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

Calvinball is completely impossible, because the primary skill required is creative thought. Most humans are not creative enough to play it well. Calvinball is also a particularly unusual case, because the rules are not fixed.

Mao also doesn't have fixed rules per se, but they only change accidentally, after the manner of the message in the telephone game. The players don't change the rules during the course of one game of Mao, and only the player who is teaching the game to the others could even potentially change them. I suspect that if an interface could be worked out to allow humans to play Mao with one another via the internet, a computer player could probably be constructed that could hold its own. It would be an interesting programming exercise, but I can't think of any reason it couldn't be done. The "learning" that the game requires is essentially just memorization. Computers are terribly bad at certain other kinds of learning, but they can handle memorization just fine (better than humans, I daresay), if you program them to do so.

Incidentally, I once adapted the basic principle of Calvinball into a card game. A group of us played it two or three times. It worked surprisingly well. There's absolutely no way a computer could have been programmed to even participate, much less to win.

If I'm not mistaken, Snakes and ladders has no strategy.

That would be my assessment as well.

The other games would be satisfied by any system that satisfactorily passes the Turing test

The general-case Turing test is generally assumed to be AI Complete. I don't know whether this has been satisfactorily proven, but I'm certain it hasn't been disproven.

and as far as I know, there's no reason to think a future system couldn't at least PASS as human

In limited cases, it's already been done -- but only in limited cases. The computer can pass as a particularly unintelligent human (e.g., mentally retarded child) or as a human that the "judges" wouldn't be able to interact with in any meaningful way (e.g., a human who doesn't know any language the "judges" know) or as an uncooperative human who refuses to play the game straight (provided the competing human is similarly deficient). The computer can also pass if the "judges" are remarkably bad at what they're doing.

But if the judges play the game straight (try to carry on an actual conversation) and the human participants are regular people off the street, the whole thing doesn't take very long. Computers fundamentally aren't smart enough to participate in a normal human conversation, because they don't understand any of what's being said. It becomes obvious rather quickly.

Actually, such an AI might just outperform in Mao and Calvinball using perfect, faster recall and procedural rule generation.

Mao, yes. Calvinball is impossible. Perfect, faster recall doesn't help AT ALL in Calvinball, because the whole point is to AVOID being bound by your opponent's rules, by strategically creating rules that favor you. Any kind of "procedural rule generation" that a computer can be programmed to do is going to fall flat on its face against a moderately clever human player. Furthermore, no strategy can be pre-programmed, because all the strategy is in what rules you make, and the only permanent rule is that you can't make the same rules twice. Pre-programmed strategy of any sort could only be used once, ever. Calvinball is quite possibly the pathologically worst possible game for AI.

Games that have a lot more strategy than tactics are almost as bad. If you study a lot of game AI, you'll notice something: in games that play to a computer's strengths (chess, blackjack, Scrabble, hangman), the AI consistently has to be programmed with difficulty levels, so that if you set it to easier it can back off a little and let the humans feel like they can compete. Because otherwise, the humans can't compete. In games that are complex and have a lot of long-term strategy (e.g., the Civilization series), the AI has to be programmed to "cheat" (i.e., to have advantages the human players aren't permitted, like always being able to see what their opponents are doing even though the humans can only see within a certain radius of their own units) and still presents only a moderate challenge to human players -- playing against a human in such games is MUCH more difficult than playing against the AI. Granted, the AI for these games is seldom as good as it theoretically could be. But even if the world's top AI researchers poured decades into the problem, the computer would never be able to compete effectively against an even moderately skilled human player.

(On the other end of the scale, the best games for AI are probably ones that involve a combination of rapid memorization and the ability to act quickly. Dutch Blitz springs to mind immediately. If there were a non-turn-based "Speed Scrabble", where you can play as fast as you can come up with plays, it would take me about five minutes to program an AI no human player could ever touch.)

[AvatarIII]

The on game that heard about recently on NPR that was computationally difficult was Solitare, it's currently unknown how many shuffels of the deck there are that are winnable. It's not possible to win every game of Solitare some shuffles of the deck are un-winnable, the only way for a computer to "win" is to compute all possible 52! shuffels of a deck, after I heard this story I did some quick napkin math and figured you could easily eliminate somewhere around 12! to 8! (can't remember exactly what I came up with and have no desire to work it out again) possible shuffels as definitively unwinnible, but even 52! - 12! is still a pretty big universe. Now it's not a game you can compete against a human in so it doesn't match what was going on in this comic but an interesting problem.

in case you are wondering, because I was, there are 80,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (That's an 8 with 67 zeros after it, aka 80 unvigintillion (US), or 80 undecillion (Eu)) possible different orders for 52 cars to be shuffled into.

[BentFranklin]

If aliens came to Earth, the only game of ours I think we could get them interested in would be Go, and I think they would really like it. No other game quite captures the scale problem (forest vs. trees) like Go.

[cathyc]

Important omissions are bridge and backgammon, they should both be on the list, maybe as humans might always be better than....

[meerta]

Actually I don't think you should say even now that chess computers are consistently beating the top humans, not as conclusively as one would like to be able to say it at least. The last of these matches was between Vladimir Kramnik and Deep Fritz in 2006, with four draws, and two wins to the computer.

But it appears Kramnik missed a win in the the first game, and in the second game, from a probably winning position, he made probably the biggest blunder ever made by a World Champion, missing checkmate by Deep Fritz on its next move!

Considering the brute processing power of Deep Fritz, and taking into account the mistakes, it doesn't feel like a conclusive loss for humanity, which is astonishing.