The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case

I Wright, J Marshall

Research output: Contribution to journalArticle (Academic Journal)peer-review

Abstract

Some behaviours of computer game agents can be naturally expressed as collections of rules and knowledge bases. General purpose rule-based languages provide high-level constructs for expressing complex conditional behaviour. We examine the runtime kernel of RC++, a rule-based language developed for game AI, to explore the costs associated with adopting general-purpose, rule-based approaches for computer game production. The kernel of RC++ is the RETE* algorithm, an extension of the RETE algorithm with better time characteristics, but also able to exhibit the beneficial properties of TREAT (a low memory cost alternative to RETE) when required. RETE* achieves this functionality and performance by employing (i) asymmetric deletion, (ii) dual tokens, and (iii) a dynamic beta-memory cut mechanism. The dynamic beta cut allows the RETE/TREAT trade-off to be exploited by users. Theoretical and empirical performance comparisons for RETE, TREAT and RETE* are provided. The implications for the utility of rule-based programming for the computer games industry is discussed, and we conclude that there is still some way to go before rule-based programming can be employed in the game-making process.
Translated title of the contributionThe execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case
Original languageEnglish
Pages (from-to)36 - 48
Number of pages12
JournalInternational Journal of Intelligent Games and Simulation
Volume2(1)
Publication statusPublished - Feb 2003

Fingerprint Dive into the research topics of 'The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case'. Together they form a unique fingerprint.

Cite this