Escallier Pierre

Project dedicated site: http://jneutron.axan.org/

Overview

Neutron is a board game (like draughts) which is played by two players.
The board is divided in 25 square (5*5). On two opposite edge are 5 red balls and 5 blue balls. In the middle is the neutron ball.

Rules

The game is turn based and for each turn player first move the neutron and one of his balls.
Balls are moved in any direction (including diagonals) but always go as far as possible (untill they meet the board edge or another ball).
The player who bring the neutron on one of his balls starting position win the game.
If the player cannot move the neutron when he has to, he loss the game.
The same when a player is forced to move the neutron on the opponent starting line.
Finally, the starting player does not move the neutron on the first game move.

Anecdote

I discovered this game at the summer 2003 in a wood game stall of a night market.
I played all the night against a friend of mine with few success so I decided to program a player that might be better than me.
At this time I did not really know about artificial intelligence nor games algorithms but I had the feeling that it must exist a generic solution to this kind of game.
Indeed, after some googling I learned about the MiniMax algorithm, which is famous for this kind of boardgames.

Making of

I was impatient to see the MiniMax algorithm working so I first choose to use Borland C++ Builder which let me code user interface very quickly.
Here is a preview the UML class diagram at this time.
This first version can be download here : Neutron – C++ beta version.
However, the current version has been rebuilt using JAVA, and is available at GoogleCode. Moreover, it has its own dedicated website (only in French at the moment): http://jneutron.axan.org/.

Next versions

The Neutron game is my first approach with artificial intelligence. In next updates I am willing to try another algorithm that tend to replace the MiniMax one in new games: The UCT algorithm, which is said to have particular good results with the game of GO.
Finally, I would like to try more algorithms that I red about and particularly the machine learning technics like decision trees and neural networks.

MiniMax

The MiniMax algorithm suppose that for each move the player makes the ideal move.

Assuming a function called Evaluate(Gameboard) which take a gameboard (that is to say a given game state) as input and outputs a score which tend to +∞ if the cpu win, and -∞ if it loose.
Then we just need to be able to predict all the possible states (new gameboard) from a given gameboard and we’ll be able to write:

INPUTS: Gameboard, given gameboard.
		 Player, current player turn.
		 Depth, current algorithm depth.
OUTPUTS: Move, move to play.
RETURN: Given gameboard score.

MiniMax(Gameboard, Player, Depth)
BEGIN

   IF (Depth = max_depth) OR (IsAEndGameBoard(Gameboard)) THEN
      RETURN Evaluate(Gameboard)
   ENDIF

   IF Player = ME ALORS
      Score ← -∞
   ELSE
      Score ← +∞
   ENDIF

   FOR each possibles moves of GameBoard DO
      new_gameboard ← ApplyMove(Gameboard, current_move)
      new_score ← MiniMax( new_gameboard, InvertTurn(Player), Depth + 1 )
      IF Player = ME THEN
         Score ← Max( Score, new_score )
      ELSE
         Score ← Min( Score, new_score )
      ENDIF
      IF Score = new_score THEN
         Move ← current_move
      ENDIF
   ENDFOR

   RETURN Score
END

In a perfect world computers would be able to run through the whole tree of possibles moves and the Evaluate() function would just need to check the ending game conditions. The max_depth would also tend to +∞.
Unfortunately, run through the tree of possibles moves for 5 ou 6 generation already takes a long times (somes dozens of seconds).

Luckily, there is a MiniMax algorithm enhancement called MiniMax.αβ (alpha beta). This enhancement deals with the tree running process which can be stopped when values become irrelevent.
We need two more variables called α and β on each node which will be used to estimate the node score.

The α of a node is a minimal estimation of the node score. It is equal to the leaves score and is initialized to -∞ anywhere else. On the player nodes it is maintained to the maximal value amongst already stepped sons nodes, and to the α value of father node on cpu nodes.

The β of a node is a maximal estimation of the node score. It is equal to the leaves score and is initialized to +∞ anywhere else. On the cpu nodes it is maintained to the minimal value amongst already stepped sons nodes, and to the β value of father node on player nodes.

INPUTS: Gameboard, given gameboard.
		 Player, current player turn.
		 Depth, current algorithm depth.
		 A, α value.
		 B, β value.
OUTPUTS: Move, move to play.
RETURN: Given gameboard score.

AlphaBeta(Gameboard, Player, Depth, A, B)
BEGIN

   IF (Depth = max_depth) OR (IsAEndGameBoard(Gameboard)) THEN
      RETURN Evaluate(Gameboard)
   ENDIF

   Alpha ← -∞
   Beta ← +∞

   IF Player = ME THEN

      FOR each possibles moves of GameBoard DO
         new_gameboard ← ApplyMove(Gameboard, current_move)
         Val ← AlphaBeta( new_gameboard, InvertTurn(Player), Depth + 1, Max(A, Alpha), B)
         Alpha ← Max(Alpha, Val)
         IF (Alpha = Val) AND (Depth = 1) THEN
            Move ← current_move
         ENDIF
         IF Alpha ≥ B THEN BREAK_LOOP // β cutoff
      ENDFOR
      RETURN Alpha

   ELSE

      FOR each possibles moves of GameBoard DO
         new_gameboard ← ApplyMove(Gameboard, current_move)
         Val ← AlphaBeta( new_gameboard, InvertTurn(Player), Depth + 1, A, Min(B, Beta) )
         Beta ← Min(Beta, Val)
         IF (Beta = Val) AND (Depth = 1) THEN
            Move ← current_move
         ENDIF
         IF Beta ≤ A THEN BREAK_LOOP // α cutoff
      ENDFOR
      RETURN Beta

   ENDIF
END