Unangband monster AI - part one (History and Context)

(This article is in six parts: parts one, two, three, four, five and six, and is also available as a PDF).

Unangband monster artificial intelligence routines have evolved from the Sangband and Oangband's so-called 4GAI which is short-hand for Leon Marrick and Bahman Rabii's "4th generation Artificial Intelligence". It's a set of common functions and algorithms used across a number of Angband variants: in addition to Sangband and Oangband (and FAAngband), its been adopted separately by NPPAngband and Unangband, both versions of which have evolved in different directions.

Its called 4th generation, because it's the fourth major evolution of the monster AI routines in Angband's history. Leon Marrick has written extensively about it in the comprehensive design manual.

I'm going to quote the development history liberally from this manual as the original is a text document which likely won't format well in your browser. The history is interesting reading and written with Leon Marrick's usual mix of enthusiasm and iconoclasm:

History: Standing on the shoulders of giants

The history of coding monster intelligence ("monster AI") in Moria and Angband is a long one. You will not be reading the true history here; the following is one man's (i.e. LM's) opinion and viewpoint on previous AIs. If you don't disagree with me at least once in the next six paragraphs, you need to learn more about this subject!


The First Generation:

The first generation AI was mostly the work of Robert Koeneke. Each turn, a monster would attempt to cast a spell, if it had any. If it passed the spell frequency test, it would pick a spell at random. Although a primitive method, choosing spells at random had the great advantage of keeping the monster true to character. Not only was every spell guaranteed to be used, but monster designers could tweak the frequency of, say, harassment spells against attack spells by changing the number of each.
Monsters that didn't cast spells entered the movement code. This involved choosing a direction that best approached the character, plus the two directions that flanked it on either side, for a total of five possible directions. The monster would then try these five choices in order, testing any doors or glyphs, moving as soon as it found a grid it could enter or succeeded in clearing. Again, to say that this was crude is less important than to note that, in the conditions of Moria, it worked acceptably.
The young Angband added many spells and new features, but made few changes to this basic system. However, at or before version 2.6.2, intelligent monsters were made to cast better spells if desperate, and the first monster terror code appeared.

The Second Generation:

When Ben Harrison took over, things started to change. First came a massive code cleanup. David Reeve Sward contributed the basic monster learning system we still use today; by storing information about character resists and immunities, monsters could learn to probe for missing resists - and then exploit them cruelly! William Tanksley came up with a way for monsters to target the character, which allowed them to track their enemies down in a realistic, limited fashion. Ben Harrison introduced the famous monster flow, which stored the route distance from the player up to a range of 32 every time the player moved. Although extremely CPU-intensive, and criticized as giving monsters too much of an advantage over the player, the monster flow code made such a difference to monster intelligence as to become almost indispensable. It eventually replaced the monster tracking code. This, then, is the suite of features of the second generation of monster AIs, and the common possession of all modern Angbands.

The Third Generation:

When the Keldon Jones AI came out, it caused a sensation. Monsters stopped killing each other off with magic missiles, Zephyr Hounds starting luring the player into rooms, orcs started to surround the player, and monsters chose spells according to their tactical situation so cleverly that some of them became nearly unkillable. It took a while, but eventually almost every major variant and Standard Angband adopted this code with greater or lesser modifications. The best word on the Keldon Jones AI is that of Greg Wooledge, explaining why he included this code in his variant: "I simply couldn't stand watching the novice rangers act like Keystone Kops any longer.".

The Fourth Generation:

But the Keldon Jones AI was by no means perfect. For starters, it was extremely slow. In addition, this system made many monsters act out of character by discriminating against certain classes of spells or by making monsters suppress their most useful attack, and was difficult to fine-turn, either by the monster designer or the coder. Because of this, Standard Angband, Angband/64, Drangband, Oangband, and Zangband all made significant improvements at one point or another.

In the minds of Bahman Rabii and Leon Marrick, the work appearing in Oangband (remember, that's short for Opinion-Angband) 0.5.1 and 0.5.2 is the first of these efforts to go decisively beyond the level of the third generation, and merit the title:

"The Fourth Generation AI".

The manual is full of implementation details and notes for Angband variant writers, and is probably useful for most other roguelike developers as well.

NPPAngband has evolved the 4GAI in a number of interesting ways, with a primary focus on getting the correct route across multiple different types of terrain. Jeff Greene and Diego Gonzalez adopted parts of the Unangband terrain code, and decided to extend the existing flow code to use multiple per-terrain flows with varying movement costs based on the type of terrain and the 'native-ness' of the creature to the terrain it is planning a route through. More than enough improvements to the 4GAI were done to justify the moniker of "4.5GAI" when looking at the NPPAngband source code (unfortunately not available to browse online).

Increasing the different types of terrain complicates a lot of the monster AI route finding, because it is no longer possible to guarantee that the route the player and the monster takes is the same. It also exponentially increases the number of routes to be computed based on the number of different types of terrain restrictions. For instance, the shortest route may require that a monster swim through lava, then fly over a chasm, then open a door. Up to eight flows would have to be computed in this instance, based on the combinations of lava-nativeness or lack of nativeness, and ability or lack of ability to fly and open doors. Efficiencies can of course be gained by noting which monsters on a level have these capabilities.

However, in the long run, I've decided the effort to handle these combinations is probably not worth it. Even with perfect path finding, the player may be able to freeze the water, preventing a swimming monster swimming through it. Or a door may be opened or bashed down by a monster capable of doing so, thus allowing other monsters through that may be not so capable. The dynamic flow should pick up and allow the monsters to notice the changes, but in the mean time, they may have moved down a less efficient route, taking them away from the player. And the most interesting monster is one that is walking towards the player, trying to attack, as opposed to one that is moving away.

So I've decided to stick with the existing 4GAI 'flow-by-scent' and 'flow-by-noise' approximations, even if I have yet to adopt the 4GAI noise-making routines. They are good enough approximations for the moment, and have a credible real-world explanation for how the monster finds the player. And I will do some route-finding improvements at some point. I've tentatively sketched out extending flow scent to have a separate 'scent through water' flow, that monsters may or may not be able to take advantage of. And I definitely want smarter fleeing routines, and improved ability to escape hazardous terrain.

I'd also like the ability for monsters to try and 'sneak up' on the player without them being invisible - the current Unangband implementation just doesn't work very well on this account. I've developed some currently commented out code for the monster equivalent to the player running algorithm, to try to get monsters moving between rooms in an interesting fashion. But, as the denizens of rec.games.roguelike.development note: if the player can't see it, it isn't worth it.

More coming in part two.