Game AI - hard or easy?

[Don]

I tend to think of game AI being very easy in implementation if there's no concern about being fair. For example in a FPS it is trivial to have an AI that gets a headshot every time. It'd be pretty trivial to have a fighter game AI that beats you every single time if it just reads your inputs. I remember interview with SSI (make of Panzer General) developers and they say it'd be pretty easy to have an AI that can play at least as well as any human player in the PG series. If you look at a game like Starcraft, the highest difficulty AI is artifcially crippled either by design or by accident or they'd absolutely clown stomp just about any human player.

Yet if you look at the general AIs in games it's pretty clear a lot of time you get the opposite effect where human players can trivially clown stomp the AI that is supposed to be on the hardest setting. While it is not productive to have an AI that never loses, it's pretty strange to see a tough AI that is trivially beaten. One can argue that maybe stuff today is more complicated, but I don't think the depth of games themselves have become any more complicated compare to the past. It's not like Civ 5 takes 100 times the time to master compared to Civ 1. The same strategy you used in Civ 1 is still pretty effective on Civ 5, and your computer is certainly more than 100 times powerful now than it was in Civ 1 in terms of computing power, so even if games have become more complicated it doesn't explain why AI isn't doing better.

I remember seeing somewhere says problems are very easy if you have the right tool to do it. Division was thought to be very difficult until the long division notation was invented. If you think about it, how would you do division without the long division notation? It'd actually be very, very tough! You hear stuff like emergent behavior or genetic alogrithms or neural networks, and yet the AI back in Panzer General almost surely never had any of such concepts and yet it was an adequate challenge for even the best human players. It almost certainly just find the unit each of its unit can maximize damage to and iterated them through a priority list. So maybe the new AIs are doing it wrong by using the wrong tools. Do you really need a neural network to learn that unit A counters unit B if unit A only exists to counter B? Lurkers for example counter M&M in regular Starcraft. That's what they were designed for and you shouldn't need a neural network to learn this. When a player bought Brood Wars they certainly didn't need to experiment pointlessly to come up with this.

Now obviously the hardest part of the AI is make something that is challenging but still beatable, but a lot of games seem to have an AI where it doesn't even feel like they're able to make it challenging even if they tried. You don't want something like say TIE Fighter Super Ace AI where you can dogfight a single T/D for 30 minutes without hitting it, but also don't want your Super Ace AI put up as much resistance as the rookie setting either.

[Zeus]

It's easy to make an opponent that's impossible, that'll kick your ass in a heartbeat. Look at the game XIII, it was insane. It's finding the balance between too easy and too hard, too predictable and too random (so it's not "realistic"), and making it seem unscripted that's incredibly hard. Hasn't been done yet, IMO, but they are getting better at it

[Don]

Yeah but you see some games where they genuinely tried to make the AI hard and it ends up being a joke. Civilization 5 comes to mind (though all the Civ series have very bad combat AI) but there are more examples than that I'm sure. Now the AI might have problem with big picture stuff (which is why computer sucks at Go) but there are some stuff that should be absolutely trivial to have well defined benchmarks for AI. For example nobody can out APM (Action Per Minute) a computer on Starcraft 2. It'd be easy to make a computer that can do insane stuff, and then scale it back to something reasonable, like say limit itself to an equivalent of a 300 APM human, or make one mistake every 20 actions. Of course it won't be that easy but you get the general idea. Yet it's strange when you see say a RTS where the AI apparently tries to beat you at microing and then cannot, even though it is literally capable of controlling every single unit at the same time!

Back in college a friend and I tried to do a neural network that learns how to play Tic Tac Toe and it actually got dumber over time and ends up losing more than 50% of the game against an opponent that played purely randoml. So I am aware that more advanced AI concept can be pretty tough, but again why would you need a neural network to learn Tic Tac Toe? We started with an engine where the AI does NOT know what is the winning criteria for Tic-Tac-Toe (but it'll be told when it won or lost, obviously), so it's just placing tiles at random and then readjust the weights based on the outcome. I don't see a reason why you'd have to do that for most games. There's no point for a FPS AI to learn that 'headshot is the best shot'. It can simply be told this is the best shot. All the humans know this and you don't need to fake it. I think the AI guys try to hard to make AI 'learn' something, even though if you look at most games, humans don't exactly learn very much, which is why GameFAQs is so popular. Certainly, we don't need to learn stuff like 'Unit X, which is designed to be a hard counter to Y, counters Y'. If you see them go with X and Y is a hard counter, you don't have to pretend you have to learn it and neither does the computer. It's sort of like sa, blocking is a hard counter to a dragon punch. You don't have to learn this through some fake network stuff. There are places for more advanced learning technique but you don't need that to learn things that should be self-evident, and wonder if that's what trips up the AI.

[SineSwiper]

It's easy to make an opponent that's impossible, that'll kick your ass in a heartbeat. Look at the game XIII, it was insane. It's finding the balance between too easy and too hard, too predictable and too random (so it's not "realistic"), and making it seem unscripted that's incredibly hard. Hasn't been done yet, IMO, but they are getting better at it

Depends on the game. There's a perfect AI for Scrabble, Checkers, and Chess isn't that far behind. But that took a while to develop.

Of course, it depends on if you're talking about AIs that cheat. Cheating AIs is still cheating. They shouldn't be developed and every effort should be made to keep AIs from cheating. (Rubberbanding hurts racing games, for example.)

[Don]

The best Chess AI will purposely make a bad move and then try to play from behind to win without holding back, because if it didn't do that you'd never be able to beat it (on the highest setting anyway). Obviously there are various degree of success of faking difficulty agianst an opponent that can always beat you, but I think it's a pretty spectcular failure if an opponent that is supposed to always beat you fails to be challenging at all. It'd be like if you always beat computer AI on highest difficulty on a FPS even though there is no reason why you'd ever win against them.

[SineSwiper]

The best Chess AI will purposely make a bad move and then try to play from behind to win without holding back, because if it didn't do that you'd never be able to beat it (on the highest setting anyway). Obviously there are various degree of success of faking difficulty agianst an opponent that can always beat you, but I think it's a pretty spectcular failure if an opponent that is supposed to always beat you fails to be challenging at all. It'd be like if you always beat computer AI on highest difficulty on a FPS even though there is no reason why you'd ever win against them.

Really? Because it seems like if a Chess AI made a bad move, a grandmaster would be able to take full advantage of it.

[Don]

The top Chess programs are significantly better than the best human players now (saw some reports where the computer won starting with 3 less pieces against a grandmaster) so they have to do that or they'd never lose, and what's the point to play against an AI where even a grandmaster cannot win? Of course it might get lame in its own way once you realize the computer is giving you a handicap, but it's probably still better than an auto-lose.

A good parallel from this is the original Starcraft 1 AI. It is programmed to attack in waves. There's really no reason why it should attack in waves instead of just moving all the units up at the same time. It is certainly more than capable of controlling 200 supply worth of unit at the same time. It does that because otherwise it'd be too overwhelming.

Faking incompetence is probably as much an art as science, but on the other spectrum there's also AI that are just bad and not faking it, which is why it's rather puzzling. Almost every game I can think of, you can have AI slap the human easy if it's willing to even cheat a little bit, and some games it wouldn't even need to do that (FPS, for example).

[Kupek]

For a good explanation of a game that's harder to make a good AI for than chess, check out this article: Cracking Go

Now that's AI research. Their only goal is to win. But I think Don is more concerned with AI in videogames which have the goal of being a fun opponent for the player. While getting an AI to win Go is hard, there's still an objective evaluation: did you win or lose? But there's no objective evaluation for an AI being "fun" - which is what I think Don is getting at. Figuring out an AI that is fun is different than figuring out an AI that will win.

[Lox]

Creating a "fun" game just in general is a difficult task. Creating "fun" AI is very hard. You can't define functional requirements to make something fun.

For example, does making the AI respond to gunfire within .5 seconds make the game more fun then, say, 1.5 seconds? That's an impossible question to answer and why I like the idea of building games within a rapid process. You can see if something seems fun early on and account for it and make adjustments.

[Don]

I think the issue with Go is that there might not be a very good model of what contributes to winning in that game. Hikaru no Go has a pretty accurate description of that when Hikaru was wondering if he's winning or losing even though he already lost the game. If you look at a game like Chess there's generally no ambiguity to when you're losing. If you're playing against say, Kasparov, it'd be rather obvious in a few moves that you're about to get owned. Like I said it might be an issue of where the answer requires a model that does not exist yet, similar to how long division makes division trivial even though it was considered a very hard problem prior to that.

But generally speaking games are not anywhere near as complicated as Go or even Chess. It's tempting to say take a fighting game, you got 20 moves plus movement, you can do one every second, so the complexity must be like 30^100 and no way a computer can figure that out. Of course you can trivially have a computer just react to your moves and beat you up (Shin Akuma comes to mind) easily. Most games have very shallow pruning, and I think a prerequisite for an enjoyable AI is that it must be able to beat you every time. Due to the nature of AI you must have an AI that can always beat you to end up with an interesting AI (one that beats you some of the time) since you can scale down from always-win to sometimes-win, but you can't scale up from never-win to sometimes-win.

I'm actually more interested in why there are the 'never-win' AIs in the first place, especially when it looks like the AI isn't trying to achieve that. It's fine if you say the AI controlling a grunt in a FPS is in a 'never-win' state. I'm guessing developers simply don't take AI very seriously, which is why you can see even fairly simple games having AI make ridiculous mistakes. I guess it's related to the fact that multiplayer is ubiquitious and it's far easier to hook someone up online to match them with their living counterpart than trying to simulate an artificial foe.

[kali o.]

Don writes too much, I couldn't be bothered to read it. Based on the title of the thread though, I'll reaffirm my position that AI is just a poor substitute for players (and probably always will be).

One thing that has always surprised/confused me is that MMO's haven't worked in "taking-over" monster AI yet...by that I mean allow players to "possess" monsters/mobs. How they could work it in to the game (ie: give mob possession tangible rewards) is a matter of debate, but I think it would be pretty cool to be grinding out boar kills, and then suddenly find 6 of those boars got possessed and banded together...and they are now creeping up behind ya.

[Lox]

but I think it would be pretty cool to be grinding out boar kills, and then suddenly find 6 of those boars got possessed and banded together...and they are now creeping up behind ya.

That would be pretty cool. Heck, I'd love to see stuff like that in games like Gears of War. Let my friends (or maybe even random players) jump in and control the enemies in my normal campaign and give me more of a challenge. It might not be something I enable all the time, but it could be really cool.

[Don]

There's a few games that tried to do what Kali suggested but if you're in the standard mob strong player weak model then say you possessed as random elite mob (don't even need to be a boss) in WoW all you do is charge toward their healer and kill them and you win easy.

Now if you're a mob with comparable power as players you'll just lose badly because there are usually more players than mobs. If you have to organize say 5 boars together to win then you're really looking at PvP with predefined characters. Now some games manage to get that done successfully but the implementation of good PvP is certainly not easy.

I think a major hurdle to AI is that if you play against the computer and you win exactly 50% of the time, you might feel that means you suck because you expect to beat the computer. On the other hand if you play someone who is exactly as skilled as you, of course you wouldn't be very surprised if you win exactly 50% of the time. It's like people expect to win PvE 100% of the time (or pretty close to it) while people usually only expect to win PvP about 50% of the time.

[SineSwiper]

For a good explanation of a game that's harder to make a good AI for than chess, check out this article: Cracking Go

Now that's AI research. Their only goal is to win. But I think Don is more concerned with AI in videogames which have the goal of being a fun opponent for the player. While getting an AI to win Go is hard, there's still an objective evaluation: did you win or lose? But there's no objective evaluation for an AI being "fun" - which is what I think Don is getting at. Figuring out an AI that is fun is different than figuring out an AI that will win.

I think the best way to make a game "fun" is to balance the AI to human reactions and thought processes as much as possible. In other words, a chess AI can compute thousands of combinations 10 moves away. A real person can't do that. So, adjust the AI to work closer to an evenly match opponent. In a fighting game, don't give the AI a 0.0001 reaction time to block a move, or immediately detect a combo with the first hit.

After all, think about how fun multiplayer games are. Since you are playing against the real thing, it doesn't feel like an opponent that cheats, either by inhuman reaction times or actual cheating. Nor does it look like you are trying to outsmart a flawed AI model.

Don writes too much, I couldn't be bothered to read it. Based on the title of the thread though, I'll reaffirm my position that AI is just a poor substitute for players (and probably always will be).

One thing that has always surprised/confused me is that MMO's haven't worked in "taking-over" monster AI yet...by that I mean allow players to "possess" monsters/mobs. How they could work it in to the game (ie: give mob possession tangible rewards) is a matter of debate, but I think it would be pretty cool to be grinding out boar kills, and then suddenly find 6 of those boars got possessed and banded together...and they are now creeping up behind ya.

Both Asheron's Call and Jumpgate have this, but it's usually the developers themselves, and both of these are low population games, so they have the time to do this sort of thing.

Having said that, I do like the fact that in Crackdown 2, people can just jump into your game and help out. Sure, it's not an MMO and it's friendlies, but it's a similar concept that should be adopted in more games.

[Shellie]

In LOTRO, you can play in "Monster Play" mode which is the PVP for the game. A special area that can be accessed by regular players (Free Peoples or Freeps), and by Monster Players, or Creeps. You can play as a Warg, Spider, Orc..and some other LOTR type mobs. Your Creep levels up, gains skills, does quests, etc. Its an awesome and very unique part of the game. There are a few people that ONLY Monster Play.

Its a lot of fun to play a Warg, stealth in a pack on a target, lacerate their legs and stun them so the rest of the Creeps can go in for the attack.

[Kupek]

I think the best way to make a game "fun" is to balance the AI to human reactions and thought processes as much as possible. In other words, a chess AI can compute thousands of combinations 10 moves away. A real person can't do that. So, adjust the AI to work closer to an evenly match opponent. In a fighting game, don't give the AI a 0.0001 reaction time to block a move, or immediately detect a combo with the first hit.

Easy to say, hard to do. The first attempts at building AI that could beat humans in chess tried to mimic how (we thought) humans played chess. They didn't get very far. We're basically sophisticated pattern matchers. The successful chess programs aren't pattern matchers; they generate huge decision trees with good heuristics for which branches to go down. It's brute force over recognition.

What this implies: there won't necessarily be a one-to-one correspondence between complexity in the AI program and sophistication in the human player.

[Don]

LOTRO's monster play sounds more like preset PVP characters. EQ had the ability to just possess a random mob (you don't get to pick which, so you might end up in a zone with no people) for a short while and because it's a mob strong player weak model game, the mob generally can defeat players quite easily and it's really not that fun that boar you've been owning now just trains 10 more of its friends to kill you in 3 seconds. I've never heard of a MMORPG where you're actually able to play as a regular strength NPC mob and not have it open to an abuse one way or another, and it's tough because mobs by definition aren't supposed to be balanced versus players (usually a lot weaker, or a lot stronger, but almost never equal).

Mimicing human is tough for computer to do due to reasons Kupek mentioned, and if a computer can't beat humans at their own game it isn't going to be challenging. Since computer can clearly repeat anything with 100% certainty, if it can win at all it must be able to win all the time, so for there to be challenge it is a prereq that the AI can win 100% of the time (or it won't be able to win at all), and it's just not clear if an AI can ever beat human by copying human behavior. Like I said I did a neural network to train computer how to play Tic Tac Toe and it got dumber over time. I'm sure I screwed up big somewhere but the point is that computer just isn't very good at copying the human style of learning.

But I think you can get a good simulation of difficulty by taking an auto-win AI and scale it back appropriately. I'm sure Street Fighter AI can easily beat you every single time if it wanted to, but they make mistakes even on the highest difficulty, presumably on purpose, so you can eventually win. I'm guessing the AI will go something like, 'Do the right thing 95% of the time' on the max difficulty setting and that's a reasonable challenge.

An exact opposite would be the Mortal Kombat AI where they'll just walk up to you, and the moment you hit a button they'll sweep you and cancel your move. Yes they're still winnable but you definitely feel like the AI is cheating so it gets frustrating.

If you look at the AI in say, Panzer General, it very rarely makes any mistake at all. It is handicapped by the fact that its units do not get experience (in a meaningful timeframe) and can't overstrength, and it is generally pretty passive on any mission it's in a defensive role, but beyond those broad limitations, it is not going to pull any punches on you. It will pretty much always attack in an optimal way. It always scouts correctly, and so on. But it's beatable because it starts off in a (sometimes significantly) worse position than the player.