Tuesday, May 18, 2010

Auto balancing Decision trees aka Resource Trees II

Just continuing from last time.

So after we called Act on the economy node it checks that it isn't a leaf node and therefore it checks it resources.

Just continuing from last time.

So after we called Act on the economy node it checks that it isn't a leaf node and therefore it checks it resources.

So we want to have 60% of our economic resources in spice and 40% in gold. These values might have important meanings because what kind of resources the AI tries to collect decides what kind of units etc it can afford to buy.  These values are what makes up your AI characters personalities. However currently they are fixed so they can't really adapt to what happens. We will look at the possibility of building an AI that uses a resource tree but also adapts to what happens in the field and weigh all of these factors into it's decision.

 And the current factors are 0.5 as we currently have booth 50 spice and 50 gold. Again this is gained simply by running the contribution formula from above.

Running the completed formula shows that spice has a difference of -0.1 and gold has a difference of +0.1  which means spice has the lowest difference so we call Act on Spice.

The current node is a leaf node. This means that the tree has deduced that the most important thing for the AI according to it's personality is to collect more spice. Now that the AI has a goal the rest of the AI can kick in and start to collect the spice.

This shows an issue with the naive implementation of the tree If I run through the tree again it will make the same decision. So I can't use the tree as it is now to aquire a secondary goal. a Way to solve this is to add another function to the tree that we can call Try() if a node is already selected as a target Try() returns false if a try returns false you disregard that node when calculating contribution. This is an imperfect system however.  As It would still select economy as a secondary goal only it will select Gold this time.

So by now I hope that the basic algorithm is pretty clear to you, but the question as always is how to implement it in a simple and flexible way.

It feels really obvious that we need a Node class since the tree is consisting of nodes and traverses nodes to select an goal. But it seems we have basically two kind of nodes, nodes that select which of it's child nodes to traverse too and the nodes that sets a goal. So it seems logical that we will have to use some kind of hierarchy here.

So we decide for a base class called DecisionTreeNode it provides the interface for the structure.
bool Act();
float GetValue();
float GetGoalValue();

Inheriting from this one we add a class called DecisionTreeNode_Branching. This is a node that doesn't do anything except selecting what node to call Act on. All non leaf nodes must be branching nodes.  So now we have a way to select what nodes that should set a goal or perform an action.

So we also needs a node type that can handle the leaf nodes. A lead node both has to be able to get the value of it's resource and set a goal or perform an action that aquires more of that resource. So it manages the resource. Therefore we call It DecinsionTreNode_Managing.

 GetGoalValue is missing here but it's only because of clarity and also because well you can place it elsewhere.

The quick study notices that under DecisionTree_managing we have a class called a manager. This is because every resource will need it's own special code for how to aquire it and measure it's current value so if we tried to place that code in the decisiontree we will get a lot of different nodes Instead we introduce a new interface class called a manager. It has only the Act and GetValue Functions. And a managing node has a pointer to it's manager. This neatly decouples the tree from the resource it manages so that you can have the manager anywhere in the program and the only connection is through the pointer.

The flow of the program will be as follows. We call act on our root node which for obvious reasons needs to be a branching node. It goes through all it's childs and calls Getvalue on them and then calculates it's total sum and the contribution for each of them.  and then it calls Act on the child node with the lowest Contribution-Goal. This is the behavior of a branching node.

When GetValue is called on a node it iterates all it's children and calls GetValue on them and add together the result and returns it This behavior continues until you hit a leaf node. This is because this is how a branching node works. But a leaf node is a managing node so it instead calls it's manager and return that value.

So GetValue on a managing node returns the manager Value and calling Act on a managing node calls Act on it's manager.

I should mention by now that this flow and these functions are a bare bone implementation. And you would probably like to extend it with extra functions like Try() Which checks if it is even possible so you don't spend time evaluating nodes that does nothing

An important part is that you want a way to pass information about the state of the world to the parts of the tree. There are numerous ways to do this. One really simple way is to have the manager access all the information it needs about the world but this creates a huge data dependency. So I would prefer that you pass a struct to the tree with the necessary information even though the only nodes using this information are the managers it means that the part of the system collecting the data doesn't need to know about the manager.

A good example of information to pass id enemy damage vs a type. For exampel is the enemy has 10 anti ground units and 0 anti air units you want to build aircraft if you send this data to the manager then the GetGoalValue can be modified based on ths information to increase the weight of that resource (yes this adds a GetGoalValue to the manager  not much to do about it) There are others ways to place it. What's is important is that these values doesn't propagate upwards but even so it allows your Ai to make well informed decisions based on actual battlefield information by just crunching simple data in a tree structure.

Just to make this clear you need an inheritance hierarchy on the managers and you need to find a way to represent it's value to send upwards. But this works quite well even for complex things like scouting.