Class AlphaBeta

java.lang.Object

ubc.team09.search.TimeConstrained

ubc.team09.search.AlphaBeta

All Implemented Interfaces:

SearchMethod

public class AlphaBeta
extends TimeConstrained
implements SearchMethod

Alpha-Beta Search

This function implements minimax search with α-β pruning, iterative deepening, and the History heuristic (a generalization of the Killer heuristic).

As this algorithm uses iterative deepening, it will continue running until its time limit runs out to find the best result. To set a specific time limit, run setTimeLimit or setTimeLimitMs.

Example

Assume that board and heuristic are already defined.

SearchMethod alphaBeta = new AlphaBeta(board, heuristic, C.WHITE);
alphaBeta.setTimeLimit(10); // 10 seconds per search
alphaBeta.setShowOutput(true); // `false` by default

// Then, whenever the boardstate changes,
alphaBeta.setBoard(board);
int move = alphaBeta.search();

Configuration options like the time limit and the maximizing player color will be preserved between search calls. The only thing you need to remember to update is the board state.

Remarks

The move output of a search function is an encoded integer. To get details about the move from this integer, use the methods from the Move class. The most relevant ones are:

• Move.arrow(int) to get the position index of the arrow being fired in this move,
• Move.start(int) to get the starting position of the queen that we want to move, and
• Move.end(int) to get the position we want to move the queen to.

See Also

• (Wikipedia) Iterative deepening.
• Schaeffer, J. The History Heuristic and Alpha-Beta Search Enhancements in Practice.

Constructor Summary

Constructors

Constructor	Description
AlphaBeta()
AlphaBeta(State initialState, HeuristicMethod heuristic, byte maximizingPlayer)

Method Summary

Modifier and Type	Method	Description
int	search()	Conducts a search of the game tree and yields the best move.
void	setBoard(State state)	The board state to search from.
void	setColor(byte color)	Indicates which player we want the search to find the ideal move for.
void	setHeuristic(HeuristicMethod heuristic)
void	setMaxDepth(int maxDepth)
void	setShowOutput(boolean showOutput)	Indicates that you want the search to print feedback to the console.

Methods inherited from class TimeConstrained

checkTime, checkTimeOccasionally, setTimeLimit, setTimeLimitMs, startTimer

Methods inherited from class Object

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

Methods inherited from interface SearchMethod

setTimeLimit, setTimeLimitMs

Constructor Details

AlphaBeta

public AlphaBeta(State initialState,
 HeuristicMethod heuristic,
 byte maximizingPlayer)

AlphaBeta

public AlphaBeta()

Method Details

setShowOutput

public void setShowOutput(boolean showOutput)

Description copied from interface: SearchMethod

Indicates that you want the search to print feedback to the console.

Specified by:

setShowOutput in interface SearchMethod

setHeuristic

public void setHeuristic(HeuristicMethod heuristic)

setBoard

public void setBoard(State state)

Description copied from interface: SearchMethod

The board state to search from.

Specified by:

setBoard in interface SearchMethod

setColor

public void setColor(byte color)

Description copied from interface: SearchMethod

Indicates which player we want the search to find the ideal move for.

Example

SearchMethod ab = new AlphaBeta();
ab.setColor(C.WHITE); // or C.BLACK.

See C

Specified by:

setColor in interface SearchMethod

setMaxDepth

public void setMaxDepth(int maxDepth)

search

public int search()

Description copied from interface: SearchMethod

Conducts a search of the game tree and yields the best move.

The move will be encoded as an int. See Move for information about how to use such a value.

Specified by:

search in interface SearchMethod