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
#22
I wrote a paper a few years ago outlining a techique that uses Fuzzy Cognitive Maps based on several subject matter experts (SMEs) opinions on concept relationship pairs (a kind of 'causality') that uses a basic genetic algorithm to automatically generate a 'concensus' between the SMEs.
http://www.scs.org/getDoc.cfm?id=2617
I am using this technique at my day job, although it is a wee bit different from this intial writing. However the basics are the same.
10/30/2005 (6:10 am)
The thing about rule based systems is that you have to create rules for every eventuality that the AI entity may encounter. Conditions can likely arise that the developer hadn't written a rule for resulting in either something comical or infinate looping type conditions (oscillating between two states). I have seen this mostly with Finite State Machines, but I have also witnessed it with SOAR and Chi's COGNET. For small problem spaces rules based is OK, but are combinatorally complex when you want interactive agents that behave 'intelligently'.I wrote a paper a few years ago outlining a techique that uses Fuzzy Cognitive Maps based on several subject matter experts (SMEs) opinions on concept relationship pairs (a kind of 'causality') that uses a basic genetic algorithm to automatically generate a 'concensus' between the SMEs.
http://www.scs.org/getDoc.cfm?id=2617
I am using this technique at my day job, although it is a wee bit different from this intial writing. However the basics are the same.
#23
10/30/2005 (7:29 am)
Scott- thanks for the reference I will definitely read that. I am still a huge fan of rule based systems. I want to build an expert system. Instead of interviewing an domain expert (like a doctor or architect) the expert is myself- because I know how I want my
#24
Anyways I have read several Bart Kosko books so I am intrigued by your Fuzzy Cognitive Maps paper. have you tried implementing any of these techniques in Torquescript?
10/30/2005 (7:30 am)
Oops hit Submit accidentally...Anyways I have read several Bart Kosko books so I am intrigued by your Fuzzy Cognitive Maps paper. have you tried implementing any of these techniques in Torquescript?
#25
10/30/2005 (7:39 am)
No, I haven't used it in Torquescript. You too can be a SME, what is good about having at least three is that the bias will center around a derived concensus rather than just one person's bias. I liken it to breeding a thoroughbred race horse.
#26
In the RETE algoritm there is a working memory that maintains a network of rule activations which makes it pretty high performance and adaptable to changes in the simulation.
10/30/2005 (8:21 am)
Scott, I am going to dig out some of my math books from college for the matrix stuff, Can you tell me if the FCM method in your paper has a Working Memory? i.e. for the 5 concepts would you have to test all concepts at every step of the simulation (would be a problem for large # of concepts). Or is the causality matrix also doubling as the working memory of the game? In the RETE algoritm there is a working memory that maintains a network of rule activations which makes it pretty high performance and adaptable to changes in the simulation.
#27
10/30/2005 (8:47 am)
Yes, each concept has a degree of activiation that each contribute to the resulting behavior. The neat thing is that sometimes interesting, and unpredicted, behavior arises.
#28
10/30/2005 (7:28 pm)
@Scott- thanks! Your white paper on FCMs is really helpful for me. FCMs are also appealing because of the simplicity of doing some matrix math to get the next state in the system instead of a complex of nodes and linked lists in the RETE algorithm. 
Torque Owner Jason Swearingen