Artificial Intelligence for Games by Ian Millington & John Funge

Author:Ian Millington & John Funge [Millington, Ian & Funge, John]
Language: eng
Format: epub, mobi
Tags: Art, Digital, Computers, Desktop Applications, Design & Graphics
ISBN: 9780123747310
Google: 1OJ8EhvuPXAC
Amazon: 0123747317
Publisher: CRC Press
Published: 2009-08-06T04:00:00+00:00

454 Chapter 5 Decision Making

ing ?person-1))

ver

y ?person-1))

adio (held-b

(r

(?person-1 (health <15)) (?person-2 (health >45))

(?person-2 (is-co

Bindings:

Bindings:

None

A

?person-2 = Captain

Bindings:

Bindings:

Bindings:

(?person-1 = Johnson,

?person-1 = Whisker

None

?person-2 = Captain) OR

(?person-1 = Sale,

?person-2 = Whisker)

B

C

Bindings:

Bindings:

None

None

Swap Radio rule

Change Backup rule

Figure 5.51

Rete in mid-update

On the Website

The pseudo-code of Rete is many pages long and doesn’t make the algorithm any clearer for its

complexity. We decided not to include it here and waste several pages with difficult-to-follow

code. A full source code implementation is provided on the website, with lots of comments, that

we’d recommend you work through.

Library

The Rule-Based System program on the website allows you to play with a simple rule-based

system and database. It is a command line program that allows you to add facts to the database

using the simple LISP syntax shown above.You can run a rule set against it to see how matches are

processed. The Rete can be viewed at any time, and the program gives lots of feedback on which

nodes in the Rete are being processed and the variable bindings they are passing on.

Program

Performance

Rete approaches O( nmp) in time, where n is the number of rules, m is the number of clauses per rule, and p is the number of facts in the database. If a large number of wild card matches is

possible, then the process of unifying the bindings in the join node can take over the performance.

In most practical systems, however, this isn’t a major issue.

5.8 Rule-Based Systems

455

ing ?person-1))

ver

y ?person-1))

adio (held-b

(r

(?person-1 (health <15)) (?person-2 (health >45))

(?person-2 (is-co

Bindings:

Bindings:

?person-1 = Sale

A

?person-2 = Whisker OR

?person-2 = Captain

Bindings:

Bindings:

Bindings:

(?person-1 = Johnson,

?person-1 = Whisker

None

?person-2 = Captain) OR

(?person-1 = Sale,

?person-2 = Whisker)

B

C

Bindings:

(?person-1 = Sale,

Bindings:

?person-2 = Whisker) OR

Bindings:

None

(?person-1 = Sale,

?person-1 = Sale

?person-2 = Captain)

?person-2 = Whisker

Swap Radio rule

Change Backup rule

Figure 5.52

Rete after-update

Rete is O( nmq) in memory, where q is the number of different wild-card matches per pattern.

This is significantly higher than the basic rule matching system we developed first. In addition, in

order to take advantage of the fast update, we need to keep the data between iterations. It is this

high memory usage that gives the speed advantage.

5.8.9 Extensions

The ubiquity of rule-based systems in early AI research led to a whole host of different extensions,

modifications, and optimizations. Each area in which a rule-based system was applied (such as

language understanding, controlling industrial processes, diagnosing faults in machinery, and

many others) has its own set of common tricks.

Very few of these are directly usable in games development. Given that rule-based systems are

only needed in a minority of AI scenarios, we’ll safely ignore most of them here. We’d recommend

Expert Systems: Principles and Programming [Giarratano and Riley, 1998], for more background

on industrial uses. It comes with a copy of CLIPS, a reasonably general expert system shell.

There are two extensions that are widespread enough to be worth mentioning. The first man-

ages huge rule-based systems and is of direct use to games developers. The second is justification,

widely used in expert systems and useful to game developers when debugging their AI code.

456 Chapter 5 Decision Making

We could fill an entire book on algorithms for rule-based systems. Given their niche status in

game development, we will limit this section to a brief overview of each extension.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.