Auto balancing Decision trees aka Resource Trees I

Today were gonna talk about a process for decision making that you can use for higher level Ai functions in games. Basically this method can handle purchases, tech level up. In some case even goal selection for a computer opponent. I will discuss this in the context of trying to make an Ai for an RTS game but the same principles will hold for a turn based strategy game and depending on context in a lot of other games too.
So the basic idea here is the following. Computers are really good at managing tree structures we have tons of efficient algorithms that works well with them and we can search in them easily. This however is not just limited to existing algorithms, basically any kinda of data is normally easy to analyze if you can represent it as a tree.

This comes from the fact that when you represent data as a tree you have already performed a divide and conquer on that data to divide it into smaller parts. Those making the code to crunch the data for each node of the tree a lot simpler than if you had to crunch all that data in one piece.


Today were gonna talk about a process for decision making that you can use for higher level Ai functions in games. Basically this method can handle purchases, tech level up. In some case even goal selection for a computer opponent. I will discuss this in the context of trying to make an Ai for an RTS game but the same principles will hold for a turn based strategy game and depending on context in a lot of other games too.

So the basic idea here is the following. Computers are really good at managing tree structures we have tons of efficient algorithms that works well with them and we can search in them easily. This however is not just limited to existing algorithms, basically any kinda of data is normally easy to analyze if you can represent it as a tree.

This comes from the fact that when you represent data as a tree you have already performed a divide and conquer on that data to divide it into smaller parts. Those making the code to crunch the data for each node of the tree a lot simpler than if you had to crunch all that data in one piece.

This allows us to solve quite complex problems by dividing them into several simple problems instead. especially inside the field of AI the problems we want to solve are always complex but they can almost always be modeled in many small but simple parts. Then you just has to have the processing power to crunch through them. So if we manage to break down and restructure our data in such a way we have a significantly better chance of implementing a working algorithm.

So with the background out of the way lets look at our algorithm for balancing strategic decisions by utilizing a the possibilities in multi connected directed graphs to propagate simple values into complex results. The basic idea is the same as of a neural network whee the end result is much more complex than the sum of it's part. But this contains no funky human based simulation or reasoning. Just clever use of tree structures.

But the actual algorithm is just one of the pillars of this technique, the design of your tree structure is vital to getting a good result out of this technique. Pretty much like most things in AI where it is the implementation and not the algorithm that matters.

The gist of the idea is that if you build a tree structure that contains all the resources that are possible to attain in the game then you can depending on how this data is propagated around in the tree get different calculations and  evaluations.

The above structure represent a simple tree from a fictive RTS game. It has 2 economical recourses spice and gold.  It also have two types of units infantry and cavalry.

The interesting part of these is that using this tree structure allows us to calculate the relations between the different part  for example we can easily calculate how much of our economy that is defendant on spice vs gold.   Or how much of our total resources are in troops compared to how much is in economics. This tree is obviously way to simple to allow us to see the true strength of the concept so before we go down and look at this case in detail and  walk you through how the algorithm works let's take a look at a slightly more complex example first.

While this tree still is really simple it starts to look a little more like the complexity you would face using this technique in reality. An interesting point to note is that some nodes have multiple parents in the tree which mean that they contribute to multiple categories in the tree. So their values will add upwards on multiple occasions.

For example  as an infantry unit is usable to booth attack and defense it contributes to both of those categories. And a tower is booth a building and a defensive unit so it  contributes to booth of these. When you create a tree like this and try to actually map out all the relations that exists in a game then it will become quite complex. But the beauty is that you can map up really complex relations with a system like this

These complex branches are the principle the algorithm is based on  because with them you can map up all the complex relation ships that occurs in reality (or get close enough to fake it at least). A problem is that as you can see the tree very quickly grows complex and becomes hard to grasp. This is sadly an unavoidable effect of trying to map out those complex relations but you can get quite far by being intelligent about how you design your trees.

 A good  start is to think of every part of the tree seperately and look at which nodes this node is connected to. So rather than trying to solve the big problems of making sure everything in the tree seems proper you just make sure that every node is connected to the other nodes like it should be and this in the end creates the tree structure for you. Divide and conquer is a powerful tool indeed and you can make it work for yourself too.

Thanks to the advanced connections that this will create we can model complex behaviours down to a simple comparision of values that are propagated from the nodes. For example it would have been quite easy to get a realistic balance between military and civilian priorities by just looking at the values at those nodes in the graph. You can also control those propagations by using weights on the connections for example you can say that a Tower adds to military with 70% of it's current value but it adds to buildings with 50%. There is no need for these values to add up to a total 100% since you can balance this out by lowering the value for a tower to begin with (but it might be easier to just keep it to 100% in total for most people).

The goal of all of this is that in the end for every node you can calculate the percentage of that node that is contributed by this child. Then in the AI personality you can have goal percentage values that represents what it would like this contribution to be. And the Ai can then work to purchase units or perform actions that will help to steer those values towards the goal values.

This allows for an easy way of making sure than at AI keeps a balance in it's behavior in regards to how different ares should be weighted towards each other in priority and thanks to the complex tree structure it can also create a pretty accurate view of the current situation. And thanks to the fact that the percentage values are personality based it's easy to create different Ai personalities with quite different behaviors by changing those values.

The 0.7 number here on the link means that the AI wants 70% of the value of total resources to come from troops and the 0.3 on economics means he wants 30% of the total resources  to come from economics. And from the troops he wants 30% of the points to come from infantry and 60% from cavalry and the lat 10% seems to have gone missing :) well in Economics the numbers adds up at least and thats what we will be using for our example so.

So we now have numbers on what kind of percentages the Ai wants to have but we also needs values on what kind of numbers it has right now. Because as we mentioned before the goal of the AI is to make the real numbers match these numbers as closely as possible. To achieve this we start at the root node and traverse the tree and in every branch we select to traverse the node which has the real percentage which is most below it's wanted percentage. And if you reach a leaf node you purchase that kind of unit or perform it's type of action or try to aquire that sort of resource or basically what ever you need to do to increase the value of that node.

So in this diagram we add in the base values for each node this is calculated differently depending on what kind of data the node contains. For units you can use a value that is depending on the units strength multiplied with the number of units of that type. For resources the resource amount currently in your treasury. You can basically handle any kind of value you want here. How much of the map you have scouted etc. It doesn't matter to the system the important point is that the value means what you are trying to represent and that the end result you perform of that node is selected can icnrease that value.

So the way to resolve this all is to create a recursive algorithm we call GetValue which calls it's childrens GetValue functions and adds it all together and return that value. This functions allows us to calculate the value of any node we call it on.

This will propagate the values up through the tree towards the root. So that you at each position can se the values at that specific point. This is a good time to remind you that there is nothing built into the system that forces a child to propagate all it's value to it's parent it could be multiplied by a factor if you find that suitable to what you are trying to achieve. There are no limits to this it's all about which way maps easier to your way of thinking.

So to make it all work we first add in the values we calculated for the leaf nodes.  which we have done in the diagram above. And then we run the algorithm to calculate the values for the parent nodes.

As you can see we have propagated the values from all the leaf nodes upwards one step. We have also removed the goal values we had earlier trying to make the image clearer. We only kept them for the first 2 links. So Troops has a value of 1000 as that is what infantry+Cavalry equals and economics got a value of 100. This makes the total amount of resources in the system 1100.

To calculate which child node from the root node we should traverse down we have to calculate their contribution to the value of the node.  and then compare that to the personality value for the AI.
in the first case we can make a quick calculate 1000/1100 is 0.91 which is 91 % and 100/1100 is 0.09 which means 9%. So 9% of our resources are spend in economics and 91% of them are spent on troops. The code to perform these calculations are quite simple to write down but we'll look at the code just in case. To make sure everybody can follow the process.

 totalValue=0;

for(i=0;i
{
  totalValue+=mychilds[i].GetValue();
}

for(i=0;i
{
  myChildContribution[0]=mychilds[i].GetValue()/totalValue;
}

 This code follows a common patter for this algorithm. Since no node can know if it is the root node or not every node will have to assume it's the root node and perform the calculation sby adding togetehr all it's children to get it's own total value and after that get their comparative differences.
But this simple code gets us their percentage values so that we can start using them.

 If we for each child runs the formula of Current Value- Goal Value we get their difference value ( Positive differences are shown in green and negative are shown in red). What we are looking for is the child with the lowest difference because that is what we want the most in our attempt to balance the values. So in the case of our diagram we have focused way to much on troop sand let our Economics lag behind so we need to correct for this and perform actions that improve our Economics.

 So we step through the tree to the economics node, when we do that we discover that it isn't a lead node but has nodes under itself so we repeat the process for this node too.

By now we should look a bit at the functions of a node. The progress we have done so far call for a couple of functions.

float GetValue();
Recursively calculates the total value of all contributions to the node throughout the entire tree.

float GetGoalValue();
Returns the personality base goal percentage for the node.

bool Act();
This is the code called at the root to make the tree do something. This is the code that caluculates the child contributions as above and decide which one has the lowest value. Then it calls Act on that Child. If you call Act on a leaf node it will perform some kind of action to increase the value of that node we will cover this in more detail later.

So what has happened so far is that we called Act on the Root node.
It called get value on it's children that called Get Value on it's children and so on. And used this to calculate the differences. After it have decided that we needed more Economy it called Act on the Economy node.

That's all for now, in the next post we are going to finish our example and also look closely at the different kinds of nodes in the tree and the concept of managers which is what ties this all together.