Selection Approach

The first problem faced was the definition of a proper fitness function. The first solution was to use base teams as a benchmark to play with the ones randomly created and then evaluate the final score of each game. Based on that, the best teams would be chosen and then evolved. Knowing that the generation of good teams in the initial stages of evolution is highly improbable, it would be extremely difficult to evaluate, among lots of losses, which ones are the best teams.

Because of that reason, a co-evolution technique was used. In this approach, a championship was made (where teams from the same generation played against each other). The “winners”, then are chosen and evolved.

To perform the evolution itself, new teams were created based on the biology concepts of crossing over, mutation and reproduction.

Mutation

Mutation consists in randomly making changes in a player’s sub-tree, generating a new team with a different behavior.

Figura3a: Sample of a sub-tree of a player before the mutation takes place

Figura3b: Player’s sub-tree after the mutation

As we can see in the example above, after the mutation, a different decision tree has been generated, resulting in a new behavior for the “mutant player”.

Crossing-Over

Crossing-Over consists in exchanging behaviors amongst players of the same team, aiming in propagating and recombining well-formed strategies.

To perform this operation, a given player’s sub-tree is exchanged with another branch from a different player, resulting in the creation of different teams. To successfully perform crossing-over, the root node of both of the sub-trees selected should be compatible with their new parent node.

Reproduction

The reproduction is a concept very similar to the Crossing-Over and has the same purpose of it. To perform reproduction, two different teams should be chosen randomly. After that, two distinct situations can happen: the exchange of players amongst them or the exchange of sub-trees between players from these different teams.

Evolution

In each step of the evolutionary process only half of the teams survived. The other half that we needed to “complete” the generation was created with the operations of mutation, reproduction and crossing-over.

Amongst all of the teams generated by these operations, half were generated by mutation, a quarter by reproduction and the other quarter by crossing-over.