Yinsh
The Engine - details
3.1 Game Virtualisation
To allow the creation of intelligent agents, the game knowledge should be completely programmed in such a way that each agent will be aware of his environment and knows how to behave. For this purpose, an engine has been created which allows to play games given 2 virtual players.
To use this engine, every player needs to implement from a specific interface called YPlayer. This will make sure they are notified on a game event (eg when a turn needs to be played) and provided by the valid actions. Every player also should instantiate a heuristic engine (implementing from YHeuristics), which will have to calculate the heuristic values for the boards. This heuristic calculator will be used to generate the game tree (if the player chooses to use this technique), so it is important that a good heuristic function is written. If no alpha beta tree is implemented, the heuristic calculator can be used to determine the strength of each move and to select the best one (without looking ahead). To help the creation of interesting heuristics, an evolution algorithm was evolved which will be discussed later on.
As an example, an AI that plays random moves: AI_Random.
Every game contains the following information:
- The current board
- A list of all previous boards
- A list of all played moves
- The players playing the game
Because the game virtualisation is completely object-oriented, simulating games is very time consuming. It takes around 67 seconds to simulate 500 games of Random AI against Basic AI (see later), which is not a lot (if you know that some players managed to simulate around 100000 games in the same time during the competition). Therefore, it is not a good idea to implement this module for purposes such as Monte Carlo.
Furthermore, the whole engine (with GUI) consumes around 43000K private bytes from the virtual Java memory, with peaks around 50000K private bytes. This amount is reasonable for a GUI and saves enough memory for several AI techniques.
Figure 3.1 and 3.2 - javaw.exe memory usage for the YINSH engine (user game against Thomas AI)
3.2 The board
The game board can be represented very simple in a XY-co-ordinate system. The position a1 then corresponds to (0,0) and the position k11 to (10,10). All moves can be done along the x- and y-axis with an extra line of movement along y = x + a. The valid lines of movement are marked by black lines.
Figure 3.3 - The original YINSH board
Figure 3.4 - the YINSH board as represented in the engine.
Every board contains the following information:
- The board occupation
- The phase of the game (ring placement, ring movement, end)
It is clear each board has 85 valid and 15 null positions if we store the board in a 10x10 matrix. Null positions can never be occupied since they do represent an invalid board location (eg a1). All the other locations can be classified in 3 types: empty, ring and marker.
To allow a fast and small representation of each gameboard, a hashing function was written. This function converts the whole gameboard into a hash of 85 bytes (1 byte per location). This technique is however not optimal: using one byte to represent each boardlocation allows todiscriminate 128 different situations for each one of them. In YINSH there are not 128, but only 5 possible situations: empty, white ring, black ring white marker and black marker. This means the minimal amount of bytes to represent a gameboad would be 3*85/8 = 32 bytes, since 3 bits can already distinguish 5 combinations. The decision was made to use 1 byte/location because Java does not have the bit as a primary datatype.We can conclude that using 85 bytes to represent a gameboard is a huge improvement compared to storing the boards as objects or strings (85*128 bytes) in the memory. This favours tree search techniques such as alpha beta, where memory and computation time are an important issue.
Another important factor was the recognition of similar boards. A typical YINSH board has 5 possible rotations, and 3 axes of mirroring. Although this being said, only one rotation is very simple to implement using the given board representation: (this maps a1 to k11 and a5 to k7)
- x' = 10-x
- y' = 10-y
It is clear that the recognition of all these situations might provide the better results in the start of the game, but slow down the game later on since the complex calculations. Therefore, only one type of rotation was calculated.
3.3 AI Plugins & Move Simulation
To initialize a game, 2 players should be created. These players have to implement the YPlayer-interface to make sure the game can communicate with them. Earlier, an example of a random player was provided.
To create a more interesting AI, the YHeuristics-interface should be implemented. This requires the developer to define some methods that calculate the heuristic value for a gameboard and return the parameters which can be trained. When running the application, the user can then choose to train the parameters of his AI with an evolution algorithm (which will be discussed later on).
Therefore, a more interesting AI would look like this:
This AI player basically simulates all valid moves and plays the move that provides the board with the best heuristic value (provided by BasicHeuristics). The simulation engine can be called by YSimulation, which only requires a gameboard and a move as input. It then calculates all possible outcomes and returns a list of resulted game boards.
AI players that are compiled and put in /bin/players will be detected and loaded automatically (as long as an empty constructor exists for that AI). The same counts for the heuristics.