Yinsh

The Engine - AI modules

4.1 Game Tree Search

This engine calculates the game upto a certain depth using alpha beta pruning (first-depth search) and returns the best move to play. To speed up, the heuristics of the AI player are used combined with move ordening, so the most interesting moves are evaluated first and pruning can be done faster. This technique provides a significant speedup, given the great amount of possible moves each turn (40-80). The heuristics also allow to give a much better understanding about the game situation and the best move to return, since rings are only scored after around 28-35 moves.

Moreover, a module was written for deep game calculation which would queue calculated boards (in order to decrease i/o transfers) and store them into a SQL database using transposition tables. Although this technique allows a much deeper game tree calculation than the working memory allows, it is significantly slower due to harddisk i/o limits.

To give an idea about the complexity of the game: after alternately placing the black and white rings on the board, the next amount of positions are possible:

Figure 4.1

When concidering symmetries, approximately 8 × 1013 different starting positions remain at hand. Concidering that every position consumes 85 bytes, this would mean around 6 000 terabytes are needed to only store these starting positions, not even talking about the computation time. Since a game usually lasts around 60-70 moves, this means calculating the game tree beforehand is - at this moment - a crazy idea. Therefore, the use of rotation and transposition tables will only have a slight influence on the speedup of the engine, and a good alpha beta pruning technique is much more important.

The tree search could be enhanced using iterative deepening search in stead of depth-first search, since the depth can then be increased if enough time is left. Also, multithreading tree search by creating as many threads as there are branches at the first ply would improve the performance a lot. Each thread could then handle its branch as it would be a tree on its own, allowing full capacity of CPUs like dual cores or quadcores. If the threads would inform each other about their progress, this even means the pruning degree might almost be the same as without multithreading. Such an implementation was programmed by Kalle Fischer, and appropriate AIs can be found in the download version.

 

4.2 Heuristics Trainer

An evolutionary algorithm was developed to train the heuristics of the AIs:

In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions "live" (see also fitness function). Evolution of the population then takes place after the repeated application of the above operators. Artificial evolution (AE) describes a process involving individual evolutionary algorithms; EAs are individual components that participate in an AE.External Link

Here, a chromosome is represented by an array containing parameters (weights) of the heuristic calculator used by the AI which has to be trained.
First, an initial population is created, containing a certain number of default and randomly generated chromosomes.
Next, the fitness of each one of these chromosomes is calculated by simulating a certain number of games where the adapted AI (using the new weights) plays against a trainer AI (using the default heuristics of the training AI). The trainer AI has some specific behaviour that allows to have variation in the several simulated games, since a typical AI might actually always play exactly the same move in the same situation. Therefore, each time the trainer will play one of the 3 most opitmal computed moves, with a higher chance of playing the better moves.
A roulette wheel technique then decides what candidates are selected (with or without mutation or crossover) into the new generation.
This procedure keeps on running until the a certain number of generations have passed, after which the fittest chromosome out of all generations is returned.

Training an AI can be very simple by using the GUI. When the AI which has to be trained is selected, the procedure will start and inform the user about the progress and the results. A lot of parameters of the algorithm can be specified in the yinsh.properties file.

Figure 4.2

Figure 4.3

 

The following parameters are configurable for the evolution algorithm:

To allow intermediate pauses between evolutions, a module was written that exports the population into an XML file. This allows the continuation of an earlier started training after a computer crash or when time limits didn't allow a larger generation limit. This tool was created by the aid of JDOM, a Java- based solution for accessing, manipulating, and outputting XML data from Java code.
Every time a population is generated and evaluated, it is stored into the XML file, together with some information about the fitness and the used heuristic calculator. This makes sure the generation file could not accidentally be used by another player, who uses different parameters for his heuristic calculator.

Figure 4.4
Fig 4.1: the interface to train an AI

 

This XML-file can look as follows:

<?xml version="1.0" encoding="UTF-8"?>
<generation id="2" heuristicPlayer="class players.AI_BasicPlayer">
<chromosome fitness="144.0">
<parameter0>2.0</parameter0>
<parameter1>0.2</parameter1>
</chromosome>

...
</generation>

It is clear that the storage of a generation is fully dynamic. There is no limit on the amount of parameters or chromosomes to store. The only requirement is that whenever an AI wants to load a previous generation, its heuristic calculator use the same parameters as defined in the XML file.

 

<<< Previous | Index | Next >>>