The most common Artificial Intelligence approaches are used to optimize a strategy that has been previously hand-coded. These strategies are, usually, already known to be optimal.

Sometimes, there is not a known optimal strategy that can be used to solve a given problem. In these cases, instead of trying to optimize a fixed strategy that we don’t even know whether it will bring good results or not, would be desirable if we could search for it using the computer and that is exactly the aim of genetic programming, which is an evolutionary technique based on Darwinian concepts of natural selection.

We have decided to use a genetic programming approach to develop the artificial intelligence of a 2D soccer team because, as we know, a “winning strategy” for these games hasn’t been found yet. In our genetic programming approach we’ve generated a “population” of teams. Our goal was to develop a decision tree to each one of the team’s players.

Decision Tree

“if-else” Structure – Binary Tree

In our implementation each terminal node is an action the player can take (e.g. kick the ball). Non-terminal nodes are the ones that represent the situations of the game (e.g. player has the ball).

In the example above, the left leaf is a terminal node and represents an action the player takes only when his parent node, the non-terminal “Player has the Ball” is true. The other branch represents an action taken by the player when he does not have the ball. As we can see, these decision trees can be directly mapped to an “if-else” code.

Compatibility List

Even with this simple approach, there were incompatible elements, so a verification of compatibility between the nodes was necessary. If a player doesn’t have the Ball, for example, it doesn’t make any sense to give him an order to kick or run with it.

To check whether a node could be inserted or not to a branch of a tree, a list of compatibilities was added to each node. In this list, every possible children of the given node is present, in such a way that only the nodes in this list can be added as a child. This approach, however, is not enough to solve the problem, because undesirable combinations, like the one shown in Figure 2, would still happen. In this Figure, if the player has the ball and is near his own goal an order to Mark will be given, but that is not desirable since he will leave the ball behind.

A possible solution can be: when adding a new node, would be done a search in the tree to check if the new node would be compatible with his “ancestors”. However, this solution would be much expensive in the computational point of view, besides in this program a lot of trees would be generated, so this solution was discarded. The adopted solution was to modify the list of compatibilities of each node in the moment it is inserted in a branch. At this moment, the node inherits the list of compatibilities of its father and makes an intersection with its own list of compatibilities (the original), producing a new list.

The nodes that represent the “false” statement don’t need to have any relation of coherence with their parents. For that reason the generation of these nodes and its compatibility list is made using their grandfather’s.

This solution produced teams a lot more coherent. Besides it limited the size of the trees, preventing them to grow infinitely, and reduced their size which accelerated the evolution process.

Initial Nodes

We have decided to build the trees always with the same initial nodes. This approach was possible because there were four nodes which represented all the possible situations in the game, they were: “Player with the ball”, “Team with the ball”, “Opponent team with the ball”, “Nobody with the ball”.

For these initial nodes, there weren’t any children in the false condition, because if we do so, we would be in the problem of more than one different action to the same game state.

This made the trees become much more coherent, accelerating the evolutionary process. Also, it forced the players to do something in every state of the game.