net.sf.genethello.applet.gametheory
Class GameTheory

java.lang.Object
  net.sf.genethello.applet.gametheory.GameTheory

Direct Known Subclasses:

Brain

public abstract class GameTheory
extends java.lang.Object

A framework for running algorithms of game theory (minimax type) to search best move for a two players zero-sum game. It contains several famous minimax type algorithms.

Author:

Administrator

Field Summary

protected Move	bestmove Best move found so far.
protected Board	board Board used in the game.
protected int	depth Thinking depth.
protected int[]	historyTable Array of integer to hold history table. To use this feature, the following should be done: Declares historyTable to be size of 2 * possible valid moves.
protected int	moveLength Number of valid moves.
protected int	step Current step of game.
protected boolean	timesUp Terminates searching process if time's up is true.
protected long	transpositionMaxIndex Maximum index of transposition table, should be (power of two) - 1, so that the size is power of two.
protected TranspositionTable[]	transpositionTable Array of TranspositionTable to hold transposition table. To use this feature, the following should be done: Declares transpositionMaxIndex to be (power of two) - 1 somewhere in program initialization. e.g.
protected boolean	unquiet Does quiescence search if true.

Constructor Summary

GameTheory()
Creates a new instance of GameTheory

Method Summary

protected int	_AlphaBetaFailSoftTransposition(int d, int alpha, int beta) Recursive portion of AlphaBetaFailSoftTransposition algorithm.
int	AlphaBetaFailSoftTransposition(int d, int alpha, int beta) Searches game tree using AlphaBetaFailSoft algorithm and transposition table.
abstract void	DoMove(int i) Does i-th move from valid moves.
protected abstract void	DoMove(Move mv) Does move mv.
abstract int	Eval() Evaluates leaf position from current player's standpoint.
abstract void	Generate() Generates valid moves of next board position.
Move	getBestmove() Gets best move.
abstract Move	getMove(int i) Gets i-th move from valid moves.
int	IterativeMTD() Searches game tree using Memory-enhanced Test Driver algorithm and transposition table with iterative deepening.
int	MTD(int d, int f) /** Searches game tree using Memory-enhanced Test Driver algorithm and transposition table.
protected abstract void	PrintBoard() Prints board position to standard output.
protected abstract void	PrintMove(Move mv) Prints move to standard output.
void	setDepth(int depth) Sets the depth.
void	setStep(int step) Sets current step of game simulation.
abstract void	UndoGenerate() Retracts generated valid moves and puts board back to previous position.
abstract void	UndoMove() Undo last move.

Methods inherited from class java.lang.Object

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

Field Detail

historyTable

protected int[] historyTable

Array of integer to hold history table.

To use this feature, the following should be done:

• Declares historyTable to be size of 2 * possible valid moves. historyTable= new int[2 * Constants.SQNUM];

transpositionTable

protected TranspositionTable[] transpositionTable

Array of TranspositionTable to hold transposition table.

To use this feature, the following should be done:

• Declares transpositionMaxIndex to be (power of two) - 1 somewhere in program initialization.
  e.g. transpositionMaxIndex = (long) (Math.pow(2, 20) - 1);
• Declares array of transpositionTable with size transpositionMaxIndex + 1
  e.g. transpositionTable = new TranspositionTable[(int) transpositionMaxIndex + 1];
• Defines and declares zobristKey
  e.g. private long zobristKey = 0;
• Defines and initializes zobrist values used to construct zobristKey.
  e.g. (in case of othello game)
  zobrist values for each color in each square:
  private long[][] zsquares = new long[Constants.SQNUM][2];
  

    Random rnd = new Random();
    for (int i = 0; i < Constants.SQNUM; i++) {
        for (int j = 0; j < 2; j++) {
            zsquares[i][j] = rnd.nextLong();
        }
    }

  zobrist values for each color having turn to move
  private long[] zturn = new long[2];

    zturn[0] = rnd.nextLong();
    zturn[1] = rnd.nextLong();
    zobristKey = 0;

• Updates zobristKey according to board position and turn using ^ (XOR) operator, tipically inside the implementation of methods Generate, UndoGenerate, DoMove, UndoMove of class GameTheory.
  e.g. (in case of othello game)
  zobristKey ^= zsquares[index][turn];
zobristKey ^= zturn[turn];
• Implements this method
  e.g. return zobristKey;

transpositionMaxIndex

protected long transpositionMaxIndex

Maximum index of transposition table, should be (power of two) - 1, so that the size is power of two.

depth

protected int depth

Thinking depth.

board

protected Board board

Board used in the game.

bestmove

protected Move bestmove

Best move found so far.

moveLength

protected int moveLength

Number of valid moves.

step

protected int step

Current step of game.

unquiet

protected boolean unquiet

Does quiescence search if true.

timesUp

protected boolean timesUp

Terminates searching process if time's up is true.

Constructor Detail

GameTheory

public GameTheory()

Creates a new instance of GameTheory

Method Detail

AlphaBetaFailSoftTransposition

public int AlphaBetaFailSoftTransposition(int d,
                                          int alpha,
                                          int beta)

Searches game tree using AlphaBetaFailSoft algorithm and transposition table. Array transposition table need to be created beforehand.

  (* Initial call *)
  AlphaBetaFailSoftTransposition(depth, -infinity, +infinity)
 

Parameters:

d - depth

alpha - lower bound of expected value of the tree

beta - upper bound of expected value of the tree

Returns:

evaluation value

_AlphaBetaFailSoftTransposition

protected int _AlphaBetaFailSoftTransposition(int d,
                                              int alpha,
                                              int beta)

Recursive portion of AlphaBetaFailSoftTransposition algorithm.

Parameters:

d - depth

alpha - lower bound of expected value of the tree

beta - upper bound of expected value of the tree

Returns:

evaluation value

MTD

public int MTD(int d,
               int f)

/** Searches game tree using Memory-enhanced Test Driver algorithm and transposition table. Array transposition table need to be created beforehand.

  (* Initial call *)
  MTD(depth, 0)
 

Parameters:

d - depth

f - first guess of expected value of the tree

Returns:

evaluation value

IterativeMTD

public int IterativeMTD()

Searches game tree using Memory-enhanced Test Driver algorithm and transposition table with iterative deepening. Array transposition table need to be created beforehand.

  (* Initial call *)
  IterativeMTD()
 

Returns:

evaluation value

Eval

public abstract int Eval()

Evaluates leaf position from current player's standpoint.

Returns:

evaluation value

Generate

public abstract void Generate()

Generates valid moves of next board position.

UndoGenerate

public abstract void UndoGenerate()

Retracts generated valid moves and puts board back to previous position.

DoMove

public abstract void DoMove(int i)

Does i-th move from valid moves.

Parameters:

i - move index

DoMove

protected abstract void DoMove(Move mv)

Does move mv.

Parameters:

mv - move

UndoMove

public abstract void UndoMove()

Undo last move.

getMove

public abstract Move getMove(int i)

Gets i-th move from valid moves.

Parameters:

i - move index

Returns:

move

setDepth

public void setDepth(int depth)

Sets the depth.

Parameters:

depth - depth

getBestmove

public Move getBestmove()

Gets best move.

Returns:

best move

setStep

public void setStep(int step)

Sets current step of game simulation.

Parameters:

step - current step

PrintBoard

protected abstract void PrintBoard()

Prints board position to standard output. Useful for debugging.

PrintMove

protected abstract void PrintMove(Move mv)

Prints move to standard output. Useful for debugging.