fourwin
Class fourMiniMax

java.lang.Object
  extended by fourwin.FourPlayer
      extended by fourwin.fourMiniMax

public class fourMiniMax
extends FourPlayer

Implements the MiniMax algorithm with Alpha-Beta pruning to find the robot's next move based on the current situation. See Maximize() method for details about the algorithm.

Version:
V1.1 20.12.2009
Author:
Marcel, Sebastian
See Also:
FourPlayer, Maximize(int, int, PlayingField, int, int)

Field Summary
private  int moves
          Is used to count the number of precalculated moves
private  byte nextMove
          Is set by the algorithm to determine the next move to be done.
private  byte opponentColorValue
          Deprecated. 
private  byte treeDepth
          Sets the maximum depth in the tree of possible moves.
 
Fields inherited from class fourwin.FourPlayer
color, colorValue, opponentID, playerID
 
Constructor Summary
fourMiniMax()
          Constructor to create an AI object using Alpha-Beta pruning with default search depth.
fourMiniMax(int treeDepth)
          Constructor to create an AI player using Alpha-Beta pruning with specified search depth.
 
Method Summary
private  int IntSignum(int value)
          Deprecated. 
private  int Maximize(int levelsToGo, int levels, PlayingField board, int alpha, int beta)
          Describes a maximizing node in the tree of possible moves.
private  int Minimize(int levelsToGo, int levels, PlayingField board, int alpha, int beta)
          Describes a minimizing node in the tree of possible moves.
 PlayingField move(PlayingField board)
           
 
Methods inherited from class fourwin.FourPlayer
getColor
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nextMove

private byte nextMove
Is set by the algorithm to determine the next move to be done. Is set to -1 to indicate an invalid value


opponentColorValue

@Deprecated
private byte opponentColorValue
Deprecated. 

treeDepth

private byte treeDepth
Sets the maximum depth in the tree of possible moves.


moves

private int moves
Is used to count the number of precalculated moves

Constructor Detail

fourMiniMax

public fourMiniMax()
Constructor to create an AI object using Alpha-Beta pruning with default search depth.


fourMiniMax

public fourMiniMax(int treeDepth)
Constructor to create an AI player using Alpha-Beta pruning with specified search depth.

Parameters:
treeDepth - Determines the depth of the tree of possible moves.
Method Detail

move

public PlayingField move(PlayingField board)
Specified by:
move in class FourPlayer

Maximize

private int Maximize(int levelsToGo,
                     int levels,
                     PlayingField board,
                     int alpha,
                     int beta)

Describes a maximizing node in the tree of possible moves.

It is the maximizing method of the MiniMax algorithm. It searches the maximum value from the next level in the tree of moves. Alpha-Beta pruning is used to cut the tree if it's branches cannot affect the final result.

If the maximum search depth is reached the method uses the Evaluate() method of PlayingField to get an evaluation value which is higher for better initial situations for the AI player.

The maximum of this value is searched in the tree to perform the best move which is possible. Every second level is an opponent move which means that the evaluated value is minimized in that levels. Because of that the alpha-beta pruning allows to cut needless branches if the higher value would be ignored by a minimizing node.

The method is called alternating with the Minimize method to build the tree of moves. Every call of Maximize() or Minimize() is equivalent to another level in the tree in the current branch.

First the two methods define the possible moves and iterate through them simulating the move by using the insertChip() method of PlayingField. The maximum or minimum of the evaluated value at the end of the tree is searched. After all moves has been simulated, the chips are removed from the board.

Parameters:
levelsToGo - Remaining search depth
levels - total search depth
board - current board situation.
alpha - Is set by the algorithm itself. Use lowest possible value in initial call.
beta - Is set by the algorithm itself. Use highest possible value in initial call.
Returns:
Evaluation value of the next level.
See Also:
Minimize(int, int, PlayingField, int, int), PlayingField.Evaluate(int), PlayingField.getPossibleMoves()

Minimize

private int Minimize(int levelsToGo,
                     int levels,
                     PlayingField board,
                     int alpha,
                     int beta)

Describes a minimizing node in the tree of possible moves.

The documentation of Maximize() describes the whole algorithm including the Minimize method. Please read the Maximize() documentation.

Parameters:
levelsToGo - Remaining search depth
levels - total search depth
board - current board situation.
alpha -
beta -
Returns:
Evaluation value of the next level.
See Also:
Maximize(int, int, PlayingField, int, int)

IntSignum

@Deprecated
private int IntSignum(int value)
Deprecated. 

Signum function for integer values. Is deprecated. Please use Integer.signum() instead!

Parameters:
value -
Returns:
1 for positive values, -1 for negative values and 0 if value is zero.