Extreme AI for Torque? GORE Rule Interpreter for Games
by Alex Rice · in Torque Game Engine · 07/09/2005 (12:31 pm) · 28 replies
This post is kind of a preview I guess of something I hope will pan out for me and for the GG community as well. Also I want to see if anyone had the same idea and prevent duplications of effort. ;-)
What is a rule-based production (expert) system and why would you use it in game development?
Consider 1 of infinite scenarios: You are writing a capture the flag game, and there is a computer-play mode with AI. Your team and the computer's team each have many bots. Hundreds of them on each side. Not only do the bots try to capture the flag, but they also interact (physics compliments of TGE and T2D) but also interact based logically via health, team alliances, and even mood. They get into little scrums off on the sideline. This is chaos. Every step of the similation, every bot needs to evaluate it's surroundings and make a next move. This is a many to many pattern matching problem.
Consider coding this, or something like this, with Torquescript- as you iterate through each of the hundreds of bots with a for loop, testing conditions, your frames-per-second drops through the floor. You simply cannot solve this problem (efficiently) with a procedural programming style. It doesn't matter if you are coding in C, C++ or in a scripting language like Torquescript. It's HOW you are solving the problem.
A rule based production system maintains a tree of facts/objects and rules. Rules are inferences of the form IF CONDITION THEN ACTION. Rules get activated as facts change over time. When you run the next step in the simulation, the production system has practically already determined which rule to fire.
CLIPS anecdote
I ran into this many to many pattern matching problem once and into dead end because I was using a for-loop to test all conditions. Even though I was using a relatively fast compiled BASIC dialect still it was slow as hell because of my approach to the problem and that's how I encountered CLIPS. It was a godsend for that project. This was not in a game development context, but still it's some experience embedding expert systems into C applications.
CLIPS R/2, a proprietary system, also looks like it could be useful for games but I'm not sure
GORE: A Lightweight Rule Interpreter for Games
So I was fascinated when I ran across these whitepapers from Neil Madden from U. of Nottingham. www.cs.nott.ac.uk/~nem/
What Madden has apparently done is taken the RETE algorithm from CLIPS and optimized it for small-footprint embedded game environments. He says it's going to be released soon (summer 2005?) under a BSD license and he had not heard of Torque but I turned him on to it. My goal is to evaluate his system and see if I can hack a TorqueScript binding for GORE. He says it will ship with a TCL binding and he intends to add more language bindings in the future. I haven't seen his code yet, but I've got my fingers crossed.
What is a rule-based production (expert) system and why would you use it in game development?
Consider 1 of infinite scenarios: You are writing a capture the flag game, and there is a computer-play mode with AI. Your team and the computer's team each have many bots. Hundreds of them on each side. Not only do the bots try to capture the flag, but they also interact (physics compliments of TGE and T2D) but also interact based logically via health, team alliances, and even mood. They get into little scrums off on the sideline. This is chaos. Every step of the similation, every bot needs to evaluate it's surroundings and make a next move. This is a many to many pattern matching problem.
Consider coding this, or something like this, with Torquescript- as you iterate through each of the hundreds of bots with a for loop, testing conditions, your frames-per-second drops through the floor. You simply cannot solve this problem (efficiently) with a procedural programming style. It doesn't matter if you are coding in C, C++ or in a scripting language like Torquescript. It's HOW you are solving the problem.
A rule based production system maintains a tree of facts/objects and rules. Rules are inferences of the form IF CONDITION THEN ACTION. Rules get activated as facts change over time. When you run the next step in the simulation, the production system has practically already determined which rule to fire.
CLIPS anecdote
I ran into this many to many pattern matching problem once and into dead end because I was using a for-loop to test all conditions. Even though I was using a relatively fast compiled BASIC dialect still it was slow as hell because of my approach to the problem and that's how I encountered CLIPS. It was a godsend for that project. This was not in a game development context, but still it's some experience embedding expert systems into C applications.
CLIPS R/2, a proprietary system, also looks like it could be useful for games but I'm not sure
GORE: A Lightweight Rule Interpreter for Games
So I was fascinated when I ran across these whitepapers from Neil Madden from U. of Nottingham. www.cs.nott.ac.uk/~nem/
Quote:
* Neil Madden (2003). "Optimising RETE for low-memory, multiagent systems" in Proceedings of Game-On 2003: 4th International Conference on Intelligent Games and Simulation, pages 7781, London, November 2003.
* Neil Madden (2003). "A Lightweight Rule Interpreter for Games." Undergraduate dissertation, University of Nottingham, 2003.
What Madden has apparently done is taken the RETE algorithm from CLIPS and optimized it for small-footprint embedded game environments. He says it's going to be released soon (summer 2005?) under a BSD license and he had not heard of Torque but I turned him on to it. My goal is to evaluate his system and see if I can hack a TorqueScript binding for GORE. He says it will ship with a TCL binding and he intends to add more language bindings in the future. I haven't seen his code yet, but I've got my fingers crossed.
About the author
#2
1) Have you considered switch statements?
2) Have you considered OOP and the ability to change scope throughout a program.
3) Have you considered optimised data, structuring, and proccessing?
4) Have you considered AI based on cause and effect as per the bots rather than the environment as a whole?
These are things that I take into consideration when I focus on AI and the limits of using persistant rules with static values.
Just something to think about is all. I'll get back after checking out the sites you've mentioned.
- Ronixus
07/09/2005 (1:21 pm)
I've yet to look at the sites you've provided though from reading your original post I have some things I feel I should mention...1) Have you considered switch statements?
2) Have you considered OOP and the ability to change scope throughout a program.
3) Have you considered optimised data, structuring, and proccessing?
4) Have you considered AI based on cause and effect as per the bots rather than the environment as a whole?
These are things that I take into consideration when I focus on AI and the limits of using persistant rules with static values.
Just something to think about is all. I'll get back after checking out the sites you've mentioned.
- Ronixus
#3
07/09/2005 (1:23 pm)
@Roxnius [edit: Ronixus]- have you ever programmed a rule based production system? It's really a paradigm shift and personally I felt rather liberated from the constraints of procedural programming.
#4
07/09/2005 (1:25 pm)
Also CLIPS has a history going back 20-30 years since it was created by NASA and put in the public domain. Lots of good reading material there, in addition to the two .pdf whitepapers on Madden's homepage listed above.
#5
07/09/2005 (1:30 pm)
See also www.ghg.net/clips/WhatIsCLIPS.html for answers to FAQsQuote:What is CLIPS?
What are Expert Systems?
The History of CLIPS
#6
AFAIK the best general-purpose AI/ML technique for games would be decision trees. Famous programs for building and optimising trees from training examples are ID3 and C4.5. It's also possible to use fuzzy logic with decision trees. The trees are very easy to implement (in C or whatever) once built, and very fast to query.
07/19/2005 (10:43 am)
I've never studied expert systems in any depth, but my understanding is that real-time control is not at all what they were intended for. The classic application is on line (as opposed to real time or batch) diagnosis, e.g. medical.AFAIK the best general-purpose AI/ML technique for games would be decision trees. Famous programs for building and optimising trees from training examples are ID3 and C4.5. It's also possible to use fuzzy logic with decision trees. The trees are very easy to implement (in C or whatever) once built, and very fast to query.
#7
But I think you are incorrect about what these expert system tools are intended for. I know what you are talking about the classic "medical expert" and all that.
It is a common application of rule-based production systems to be used in control environments where the system being controlled is realtime. (i.e. not running on a realtime OS, but solving a time bound control problem nonetheless)
CLIPS was developed at NASA for control systems in addition to expert systems (space vehicles launch) and CLIPS was developed precisely because the old Lisp-based systems did not perform well enough. There are some CLIPS systems for learning that are for controlling machines and factories, etc.
So in general it's not true that these tools are only use for classical diagnosis types of apps. But in particular, the GORE system is being tuned specificially for gaming development. There is precedent for this also. Some quotes from the white paper on Neil Madden's page which I linked to above:
07/19/2005 (5:50 pm)
@Andrew- the info about ID3 and C4.5 is very interesting- thanks!But I think you are incorrect about what these expert system tools are intended for. I know what you are talking about the classic "medical expert" and all that.
It is a common application of rule-based production systems to be used in control environments where the system being controlled is realtime. (i.e. not running on a realtime OS, but solving a time bound control problem nonetheless)
CLIPS was developed at NASA for control systems in addition to expert systems (space vehicles launch) and CLIPS was developed precisely because the old Lisp-based systems did not perform well enough. There are some CLIPS systems for learning that are for controlling machines and factories, etc.
So in general it's not true that these tools are only use for classical diagnosis types of apps. But in particular, the GORE system is being tuned specificially for gaming development. There is precedent for this also. Some quotes from the white paper on Neil Madden's page which I linked to above:
#8
www.cs.bris.ac.uk/home/marshall/publications/WrightMarshall2000b.pdf
Wright and Marshall work for Sony Computer Entertainment Europe. I think RC++ is a commercial product at this point - not sure.
07/19/2005 (5:50 pm)
Continued...Quote:... game AI, in contrast to rendering code and other game code, is distinguished
by employing a high density of predicates on rapidly changing
game state, and a high density of operations that can change game state.?
I. Wright and J. Marshall ??RC++: a rule based language for game AI?
www.cs.bris.ac.uk/home/marshall/publications/WrightMarshall2000b.pdf
Wright and Marshall work for Sony Computer Entertainment Europe. I think RC++ is a commercial product at this point - not sure.
#9
But again thanks for the info about decision trees! I am a big fan of fuzzy logic. There is a fuzzy extension for CLIPS also but I've never used it.
07/19/2005 (5:51 pm)
Continued...Quote:
Rule-based systems solve the problem of adapting to new situations as the RHS actions of a rule are typically very short (usually just asserting new facts, or performing some simple action). This means that time spent doing one thing is very short, and the
bot can adapt quickly to new information. The second problem, of how to decide which rule to run at any time is solved by the matching mechanism which can quickly determine which rules are satisfed by the current contents of working memory, and by the confict resolution strategy. These mechanisms are implemented in a highlyoptimised fashion which ensures that the minimum of comparisons are performed every cycle to determine which rules are satisfied. As a further advantage of rule-based approaches, it is reasonably easy to describe quite complicated behavioural patterns in the form of rules which act on facts about the environment. For instance, see the work done on adding anticipation to Quake bots[3].
But again thanks for the info about decision trees! I am a big fan of fuzzy logic. There is a fuzzy extension for CLIPS also but I've never used it.
#10
I can see a substantial advantage rule based systems have in programming; directly giving them instructions. All the ML techniques I've studied, including decision trees, require (potentially large) sets of examples from which to learn. Generating these examples for a game bot is a challenge in itself.
WRT fuzzy logic, you may wish to learn about Jim Baldwin's Mass Assignments theory, and his language Fril. C4.5 has been extended with mass assignments, I forget the details.
07/19/2005 (7:34 pm)
OK, should I ever try to build bots I shall have to learn about these systems. I'll be interested to see how CPU intensive GORE is.I can see a substantial advantage rule based systems have in programming; directly giving them instructions. All the ML techniques I've studied, including decision trees, require (potentially large) sets of examples from which to learn. Generating these examples for a game bot is a challenge in itself.
WRT fuzzy logic, you may wish to learn about Jim Baldwin's Mass Assignments theory, and his language Fril. C4.5 has been extended with mass assignments, I forget the details.
#11
07/19/2005 (9:04 pm)
@Andrew - exactly and once you kind of get the feel for rule based programming is that you just start describing the ontology of the system and don't worry about how to create training data, or how even how to connect the rules together or how to decide which rule to fire at what time- the working memory and pattern matching engine takes care of all that. I am really psyched about GORE - I hope it gets released soon
#12
07/19/2005 (9:37 pm)
Writing an AI as a set of IF statements? good lord, give me OOP over that any day.
#13
Think of rule based programming not simple IF-Statements but rather as conditional rules with precedent and antecedent clauses. Moreover these statements ARE NOT embedded in a procedural control control flow, therefore they are not really If-statements in the sense you are thinking of them. Rather they are considered en-masse in the working memory and get activated or fired by the pattern match engine when all the relevant conditions are met.
CLIPS actually does an object oriented syntax (called COOL i think), and even if you don't use the OOP, regular CLIPS has highly structured objects called facts which are templated and instantiated. Kind of like C structs. I think the GORE probably won't have OOP and that's fine too because the real power is in the pattern matching engine and the rule language, not in OO inheritance.
07/19/2005 (9:53 pm)
@Jason- Don't dismiss, out of hand, rule based programming / expert systems just based on what you are reading in this thread... if you are curious, and require AI or bots or very complex logic in your game, then you should at a minimum read the white paper and the dissertation from Neil Madden.Think of rule based programming not simple IF-Statements but rather as conditional rules with precedent and antecedent clauses. Moreover these statements ARE NOT embedded in a procedural control control flow, therefore they are not really If-statements in the sense you are thinking of them. Rather they are considered en-masse in the working memory and get activated or fired by the pattern match engine when all the relevant conditions are met.
CLIPS actually does an object oriented syntax (called COOL i think), and even if you don't use the OOP, regular CLIPS has highly structured objects called facts which are templated and instantiated. Kind of like C structs. I think the GORE probably won't have OOP and that's fine too because the real power is in the pattern matching engine and the rule language, not in OO inheritance.
#14
07/19/2005 (10:10 pm)
So just to emphasize: object oriented programming is totally compatible with rule based expert systems, e.g. CLIPS/COOL. The question is not OO vs non-OO, the question is how to find and activate/fire the correct fact+rule (or object+method) in the correct context at the correct time in your game or simulation. And that gets really hard the more complex logic, the faster changing game state, the more bots or actors in the game.
#15
Anyway, sounds interesting. when i get to the AI part of my project, i'll be sure to read the whitepaper :)
07/19/2005 (11:30 pm)
If you are saying using IF's for simplicity's purposes (which it seems you are) that's fine. just as long as you plan in implementing things at least as functions, so you can get good'ol recursion working for you.Anyway, sounds interesting. when i get to the AI part of my project, i'll be sure to read the whitepaper :)
#16
09/24/2005 (11:55 pm)
I have been communicating with the GORE developer and unfortunately release has been postponed. Hopefully in late 2005 we will see a release of this toolkit.
#17
09/25/2005 (12:59 pm)
Hope he delivers, you seem to really hold this tech in high esteem Alex :)
#18
09/25/2005 (1:02 pm)
@Jason - yeah I have my fingers crossed. I have to admit I have not seen any actual code, just his white paper and disseration about GORE !!
#19
So I am implementing the RETE/UL algorithm in Torquescript. Maybe in a few months I can post some code and demo...
Alex
10/29/2005 (7:54 pm)
Update: GORE developer Neil Madden still has not released anything ... and from our correspondence it doesn't sound like he is able to put much work into it. Too bad.So I am implementing the RETE/UL algorithm in Torquescript. Maybe in a few months I can post some code and demo...
Alex
#20
10/29/2005 (11:10 pm)
Hey Alex, I missed this thread the first time around, but good luck on your project! It sounds like a really cool addition to torque. 
Torque Owner Alex Rice
Default Studio Name
But in general it's an appealing way to program because you can incrementally build up a description of your world, an ontology, using facts and rules. Hence "expert system". You are the expert of your game and you can describe it elegantly using rules :-)