Believable Stupidity In Game AI 378
Gamasutra is running a feature written by Mick West, co-founder of Neversoft, about creating game AI that is dumb enough to defeat, yet intelligent enough that its "mistakes" are similar to those a real player would make, thus preserving the illusion that the AI is not just throwing the game.
"The simplest way to introduce stupidity into AI is to reduce the amount of computation that it's allowed to perform. Chess AI generally performs billions of calculations when deciding what move to make. ... The problem with this approach is that it decreases the realism of the AI player. When you reduce the amount of computation, the AI will begin to make incredibly stupid mistakes — mistakes that are so stupid, no human would ever make them. The artificial nature of the game will then become apparent, which destroys the illusion of playing against a real opponent. ... By reducing the amount of computation, we create an AI opponent that is trying to win, but has been crippled in a way that leads to unrealistic gameplay."
Re:Cheating AI (Score:5, Informative)
The solution I found fascinating:
So the idea is that the AI needs to calculate precisely where you are, and then rather than hit you if the preferences are set to "hard" or miss you on the "easy" setting, probabilistically make a decision based on what a weaker or stronger human player would do. It's was a great read!
Re:Interesting thought (Score:5, Informative)
That's not what I got out of the article.
What I took away was have your opponent play it's strongest, but make exploitable situations for the player. Make a pool shot so they human starts in a good position. Make a chess move that, while beneficial, opening a big possible hole for the player to exploit. Make the FPS bot run for cover at the wrong moment, but not randomly/suicidally.
(those are all from the article)
Basically make the AI make human like mistakes (mistakes in strategy) instead of "computer like" mistakes (just lowering their accuracy, not looking far ahead, etc).
Re:Interesting thought (Score:5, Informative)
Actually, he is saying the opposite. He is saying that by reducing the number of calculations per second, you create an unrealistic opponent. Instead, you must do additional calculations to model the mistakes that a human would make. Our problem is not that we don't do enough calculations, but that we make mistakes in our calculations. We are inaccurate, we jump to conclusions, we get excited, or calculate one branch of the tree very deeply while ignoring another one. Those types of things are tough for computers to do.
Re:Deep Blue (Score:5, Informative)
Well, I don't know Kasparov and I'm not a history expert, but I'm willing to bet that because he beat Deep Blue in 1996, he just figured he could do it again with no problem. He probably underestimated how much Deep Blue had improved, but that's just my speculation.
I don't know Kasparov's motivations for playing Deep Blue at all, honestly. Beating Deep Blue wouldn't have won him any fame ("Oh look, he beat a computer. Computers suck at chess anyway."), but losing would look bad for him. He had nothing to gain and plenty to lose. I know after he lost the match, he demanded a rematch, but IBM refused and put Deep Blue out of commission. IBM had nothing to gain by beating Kasparov again, and their stocks had already started going up when the news got out that they had beaten the grandmaster (to their great pleasure, history did indeed forget the shady details I mentioned before, just as they hoped).
Re:Deep Blue (Score:5, Informative)
At the time that Deep Blue was being used, there was more of a focus on brute force search than tricky AI game play. Deep blue searched an average of 130 million nodes a second using a iterative-deepening alpaha-beta search, sometimes able to look 40 moves ahead. IBM declined a rematch after that game, but thanks to improvements in AI, a standard desktop PC running improved search algorithms is now a suitable match for even a grandmaster.
Deep blue also contained an 'opening book' of 4000 positions and 700,000 grandmaster games indexed.
Source: Artificial Intelligence A Modern Approach: Russell, Norwig
Re:Deep Blue (Score:3, Informative)
In the AI research community, Deep Blue isn't even seen as interesting. It was all about "beat Kasparov", and contributed little (if anything) to the field of AI.
It just showed that if you had deep enough pockets you could buy hardware to do enough conventional AI calculations to compete on a search problem.
Agreed. In fact, Deep Blue had plenty of reasons to be uninteresting. The biggest one is that Deep Blue wasn't even that clever, it was just really, really powerful (11.38 gigaflops) at the time. All it did was brute force its way through a lot of moves (up to 40 plies!) and pick the best one. It wasn't exceptionally clever about the way it calculated the moves.
Re:Statitics (Score:3, Informative)
I think the problem they were discussing is that if you use that probability model, then there is a 2% chance that the computer will make such a totally boneheaded move that goes way beyond what any normal player would commit as a mistake. Like in chess swooping in with the queen to take a pawn and immediately be captured by the adjacent pawn, for no tactical advantage. If you are relying on pure probability to determine what mistake the computer makes, it will occasionally produce grossly unlikely mistakes.
Re:Statitics (Score:3, Informative)
Shooting accuracy is easy and has been standard in bot AI since forever.
Re:Cheating AI (Score:2, Informative)
But at least that's in its own world. The AI knows everything 'cuz it can see everything. In the real world... they aren't as well blessed.
That, and the AI controls the world in which it lives.
Re:Deep Blue and Stocks (Score:3, Informative)
First off, the market shows little rationality to begin with. However, a bit of an upward trend in a research & development corporation which has shown that their R&D is successful seems reasonable. The theory being that what they learned from Deep Blue could be used in other applications - and they're right. IBM has taken that technology deep inside various Life Sciences research: genomes, protein folding, etc., are all benefiting from the research that went into Deep Blue.
Re:F.E.A.R. (Score:3, Informative)
FEAR gained it's AI from using a planner to string actions together to reach some kind of goal.
It's not the waypoints or scripted events that make it special, every shooter has those.
In short a character in FEAR consists of a set of actions (shoot, dodge, open door, jump through window, etc..., etc...) and a set of goals (kill player, survive, stay in cover).
Each action has a number of pre- and post-conditions, just like functions have in (formal) programming. Actions also have a cost. A searching algorithm tries to combine actions until a goal has been reached.
The incredible advantage of such a system is that you don't have to script each and every event, nor have to think of everything the player might do or have to consider every possible combination of actions.
The characters have no preconception of what the player is going to do or how to react to it. Their reactions are based on events in the environment and the actions available to them.
If the environment changes the AI will find the most appropriate reaction.
Turn Based Strategy games (Score:2, Informative)
Here you do not need accuracy or to control multiple units at the same time or to compute a million moves ahead!
In these games on hard difficulty the computer gets the same initial resources as the player and plays to the best of its ability.
On impossible difficuly the player starts with a penalty in resources and again the computer plays at its best.
And still it's not impossible to defeat the AI.
To balance the sometimes less stellar AI the computer will sometimes cheat (i.e. get more money/resources, see more than they should, etc).
These types of AIs are as smart as the programmers that designed them: no matter how many CPU cycles they get, they still need to understand the game mechanics and apply them as a human would do!
Re:No Human? (Score:2, Informative)
Re:Cheating AI (Score:3, Informative)
Need for Speed, isn't a simulator, it's arcade. Although more recently with Carbon, and Undercover, a lot of the cars are day-to-day drivers, but you can still plow into a wall and drive away, and excluding cop spikes, you wont get a flat tire or blow an engine (except maybe in the drag races).
Simulators, like GTR/Race/Evo [gtr-game.com], Live For Speed [lfs.net], rFactor [rfactor.net] or TORCS [sourceforge.net] either come with, or are available [simracingworld.com] as downloads [nogripracing.com] after, normal day to day cars, likewise most flying sims have Cessna's and ultra-lights which some people do use daily/weekly/monthly...
And generally most people with a bit of extra cash (usually couple hundred dollars, sometimes they go on insurance + per-lap basis), who lives near a race track, can go race their car, someone elses car, and depending on the track, rent a car, which sometimes does include Ferrari's et al.