State of Computer Game AI

irix writes "Interesting point and counter-point about how far game AI has come along. " Or not, as the case maybe. There are times that I'm really impressed with how well computer games can "reason" things out, like Dungeon Keeper for example, and others', like the original Starcraft where I just shake my head. My biggest complaint still comes in how "not-smart" games are with just moving characters in the most efficent path on the screen - if they could just get my movement right, I'd be so happy, I'd scream.

Marathon

Those mac people here probably remember the first doom-clone for the Mac called "Marathon" which became a trilogy of games (Marathon 2 was released for Win95 as a sort of experiment, but didn't do so well, partially because it overlapped with Quake's release).

One of the features that it boasted (and that I would believe I experienced) was an adaptable AI, where as you continue to play, the behavior of the aliens would vary to match your style. For example, if you liked to hide around a corner, then peak into a room to shoot the aliens, then go back, you'd find the aliens later in the game would be more agressive about charging you. If you were more agressive, and charged into a horde, you'd be faced later with more long range attacks and mobile aliens. (This was better implemented in the final 2 games of the series).

Again, there's still some rules base here for the AI to develop from, but it was a refreshing change from Doom/Quake (and of late, Unreal) where the monster behavior was constant through the game, and made the latter parts of the game boring. Half-life, as mentioned above, still suffers from this somewhat, but this is partially aided by the numerous types of terrain/locale that the player experiences before the game is over that it becomes hard to tell if the monsters are behavior the same throughout, or are responding to the changes in the environment.

(BTW, the folks that made Marathon, Bungie, have continued to pump out games, including the popular Myth (and Myth 2 which is reported an excellent AI), and the soon to be delieved Oni, another FPS from leaked info.)

Also, another aspect that doesn't seem to have been addressed here is how well bots for Quake or Half-Life or Unreal have been programmed. I know that I've found the learning potentials of several Quake bots to be outstanding, although it only lasts for that single DM play. Surprisingly, these are mostly written by the 3rd-party players, and not any game companies themselves. Maybe they ought to have a chat and improve the AIs in current games....?

AI API's needed

And the current state of game AI is why they should all have an API that I can program my own AI to because I can do it better (or at least what I want).

If you've played Civ2 perhaps you can sympathise with the brain dead behaviour of "Automate settler" which irrigates evrything including the forests you were counting on for shield production.

AI API's would also make way for AI contests. I'd love to see a few more of those.

Gripe #2 on current state of game AI: cheating! Game programmers know that at some point the human learns and the computer has stayed the same so to up the difficulty the computer has to cheat. Civ again: building units becomes cheaper for the AI than the human, and the subjects ruled become more agreeable and easier to please requiring less expenditures freeing up effort for smashing the human.

As said in the counter-point, rule based AI is a dead end. With the exception of if the computer can generate new rules and learn. Learning must be the next step for game AI and I wish (as per gripe #1) that I could write some for some of the games I like.

AI limitations

The ability of an AI to play a game well depends on the complexity of the game. The complexity of a game depends on how many possible moves there are at each turn, and how many possible game states there can be. For example:

Tic-tac-toe: very easy -- the machine can examine the whole game-tree on each move, and *always* make the best possible move (which will result in a tie if the human also makes the best possible move).

Checkers: more complex, but a deep search can be conducted, and a move database can be used to help matters also. There are some *excellent* (practically unbeatable) checkers programs in existence. And there are incredibly good human players also.

Chess: quite a bit more complex than checkers. The number of possible states for a Chess game is hopelessly huge. To create a grandmaster-comparable Chess engine, you employ tactics like:

o hardware acceleration of time-critical search code
o move database for opening and end-games (tricky part is the middle game)
o heuristics developed with the assistance of Chess grandmasters
o a big-ass computer (lots-o-CPUs and memory bandwidth)
o a very nice search engine of course ;-)

It's important to note that adding more computing power doesn't help matters as much as you may think. For example, suppose you increase the computing power by a factor of 10. In a game where the number of possible moves is 10, this would enable you to see *one* (1) move further into the future. If you wanted to see two moves further into the future you'd need *100* times the computing power. This is over-simplifying things a bit, but you see my point.

Now consider a computer game like a flight simulator or a real-time sim like StarCraft. The complexity of games like this is so massivley f'ing huge that you can't cope with the problem by using a simple min/max search -- you *must* rely *heavily* on heuristics (e.g. if...then...) to make an AI that will perform better than a monkey. A lot of AIs are given artificial assistance (e.g. they "cheat") so that they won't be easily defeated by a competent human player.