I have been toying around with the idear of how to make an "intelligent" computer player for a while. Taking the example game screen below (slightly altered image), I'll explain some rules and possible options for the player.
This image shows a state of the game board. Assuming that it is currently the "Yellow" player's turn, they have the following options:
1) Split the 99 troops up onto three squares, creating a defensive perimiter.
2) Move the 99 troops to a single square, preparing to attack.
3) Leave the troops where they are, to protect the resource node that they are sitting on. (a resource node will create more troops at the beginning of the owner's round).
Working through the problem in my head over the last few days, I realised that the computer is not smart enough to identify any one of these strategies, let alone decide which is best. Therefore, we will need to come up with some other set of generic pre-defined rules for it to decide which move to take.
In order to get the computer to identify which moves it will take, I was thinking about a few different strategies. The first that came to mind was a "brute force" method. This method would entail the computer listing all of it's possible moves, then all moves that could stem from this initial move (would need to be restricted to a certan depth), calculating the validity of the move using a points system. Unfortunately, like most brute force methods, this method would require too many calculations with a O(6n^D) (i think)complexity.
The next thing I though of was to map opponents troops, and get the computer to "move" it's troops towards the opponent. Unfortunately for this method, it would require the computer to calculate a path to each of the enemy troops, and decide on which ones to head towards. Not quite well thought out enough, but it did lead to a good enough google search :).
The google search identified a method known as Influence Mapping, that may be able to lend some intelligence to my compuer player. Basically, you start with a map of the important cells, and calculate their influence on the other cells. This is kind of where I was heading with the troop mapping, but lends it's self to allowing additional strategies to be implemented, such as defensive, offensive, or even "collect resource nodes". The neat thing about influence mapping is that it will allow the computer to identify a path for it to follow. For example, supposing an influence map based on the troop positions of the computer's opponents, the following influence map would be produced:
So, the movement that the computer would take in this case is fairly clear. It would move all 99 units to the next node marked 17, then the following turn (assuming that the state remained similar), it would probably move to the one marked 18, then 19, then attack the one node that has 20 opposing troops.
I'm sure that I haven't figured out all of the problems associated with this method, but it does seem to go a long way towards having a relatively intelligent computer player to combat. It would also give me the ability to allow the computer to have various different "strategies", based on which nodes get given the initial points.
