sandy.game.core
Class DecisionEngine

java.lang.Object
  |
  +--sandy.game.core.DecisionEngine

class DecisionEngine

extends java.lang.Object

This class is used to help the computer find the best possible move in a given board situation. This DecisionEngine is build in a very generic way not taking into assumption any game in particular. However this decision engine does make some assumptions on the game board, so all the game specific boards should extend from the GameBoard class provided in the code package.

This Engine treats every game as a GameTree and tries to apply the MINI_MAX algorithm with Alpha-Beta pruning as a performance enhancer. By changing the currentPerspective of this decision engine, it can be effectively used to suggest the human player for better moves.

This engine operates on a variable number of evaluation policies, which are registered by the computer player in a game specific manner. A evaluation policy is essentially a piece of logic which evaluates a specified game board in a given state and returns the goodness of the state, in simpler terms.. it tries to evaluate how good is this state for me. Goodness increses in the positive scale.

      function AlphaBetaMM( N, A, B)
      # N = A Node in the game tree
      # A = value of alpha.
      # B = value of bets.
      begin
       if N is a leaf then
          return evaluateBoard ;
       if N is a Min node then
         For all successor Ni of N loop
           B = Min{ B, AlphaBetaMM(Ni, A, B)};
           if A >= B then
             Return A
           fi
         end For
         Return Beta;
       else
         For each successor Ni of N loop
           A = Max{ A, AlphaBetaMM(Ni, A, B)};
           if A >= B then
             Return B
           fi
         end For
         Return A;
      end AlphaBetaMM
 

Field Summary

private int	currentPerspective
private java.util.Vector	evaluationPolicies This vector contains a list of all the registered evaluation policies.
private GameBoard	gameBoard This is the game board on which this decision engine will operate.
private int	maxDepthOfSearch

Constructor Summary

DecisionEngine(GameBoard gameBoard)
The constructor, which taken in a gameBoard instance.

Method Summary

private double	evaluateGameBoard(int perspective, GameBoard scratchBoard)
Move	getBestMove() This functions returns the best move for the given scenario.
int	getCurrentPerspective()
GameBoard	getGameBoard()
private double	getSubtreeEvaluation(int treeDepth, double alpha, double beta, GameBoard scratchBoard) This function gets the subtree evaluation by using MINIMAX and AlphaBeta pruning algorithms.
void	registerEvaluationPolicy(EvaluationPolicy policy)
void	setCurrentPerspective(int perspective)
void	setGameBoard(GameBoard gameBoard)
void	setMaxDepthOfSearch(int depth)
void	unRegisterEvaluationPolicy(EvaluationPolicy policy)

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

gameBoard

private GameBoard gameBoard

This is the game board on which this decision engine will operate.

evaluationPolicies

private java.util.Vector evaluationPolicies

This vector contains a list of all the registered evaluation policies.

currentPerspective

private int currentPerspective

maxDepthOfSearch

private int maxDepthOfSearch

Constructor Detail

DecisionEngine

public DecisionEngine(GameBoard gameBoard)

The constructor, which taken in a gameBoard instance.

Method Detail

getBestMove

public Move getBestMove()

This functions returns the best move for the given scenario.

getSubtreeEvaluation

private double getSubtreeEvaluation(int treeDepth,
                                    double alpha,
                                    double beta,
                                    GameBoard scratchBoard)

This function gets the subtree evaluation by using MINIMAX and AlphaBeta pruning algorithms. When treeDepth % 2 == 0 its the computers turn to play and when its 1 its the opponents turn to play.

      function AlphaBetaMM( N, A, B)
      # N = A Node in the game tree
      # A = value of alpha.
      # B = value of bets.
      begin
       if N is a leaf then
          return evaluateBoard ;
       if N is a Min node then
         For all successor Ni of N loop
           B = Min{ B, AlphaBetaMM(Ni, A, B)};
           if A >= B then
             Return A
           fi
         end For
         Return Beta;
       else
         For each successor Ni of N loop
           A = Max{ A, AlphaBetaMM(Ni, A, B)};
           if A >= B then
             Return B
           fi
         end For
         Return A;
      end AlphaBetaMM
 

Parameters:

treeDepth - The depth of tree to evaluate.

alpha - The alpha value.

beta - The beta value.

evaluateGameBoard

private double evaluateGameBoard(int perspective,
                                 GameBoard scratchBoard)

setMaxDepthOfSearch

public void setMaxDepthOfSearch(int depth)

getGameBoard

public GameBoard getGameBoard()

setGameBoard

public void setGameBoard(GameBoard gameBoard)

registerEvaluationPolicy

public void registerEvaluationPolicy(EvaluationPolicy policy)

unRegisterEvaluationPolicy

public void unRegisterEvaluationPolicy(EvaluationPolicy policy)

getCurrentPerspective

public int getCurrentPerspective()

setCurrentPerspective

public void setCurrentPerspective(int perspective)