aima.core.search.adversarial

Class AlphaBetaSearch<STATE,ACTION,PLAYER>

java.lang.Object

aima.core.search.adversarial.AlphaBetaSearch<STATE,ACTION,PLAYER>

Type Parameters:

STATE - Type which is used for states in the game.

ACTION - Type which is used for actions in the game.

PLAYER - Type which is used for players in the game.

All Implemented Interfaces:

AdversarialSearch<STATE,ACTION>

public class AlphaBetaSearch<STATE,ACTION,PLAYER>
extends java.lang.Object
implements AdversarialSearch<STATE,ACTION>

Artificial Intelligence A Modern Approach (3rd Ed.): Page 173.

 
 function ALPHA-BETA-SEARCH(state) returns an action
   v = MAX-VALUE(state, -infinity, +infinity)
   return the action in ACTIONS(state) with value v
   
 function MAX-VALUE(state, alpha, beta) returns a utility value
   if TERMINAL-TEST(state) then return UTILITY(state)
   v = -infinity
   for each a in ACTIONS(state) do
     v = MAX(v, MIN-VALUE(RESULT(s, a), alpha, beta))
     if v >= beta then return v
     alpha = MAX(alpha, v)
   return v
   
 function MIN-VALUE(state, alpha, beta) returns a utility value
   if TERMINAL-TEST(state) then return UTILITY(state)
   v = infinity
   for each a in ACTIONS(state) do
     v = MIN(v, MAX-VALUE(RESULT(s,a), alpha, beta))
     if v <= alpha then return v
     beta = MIN(beta, v)
   return v
 
 

Figure 5.7 The alpha-beta search algorithm. Notice that these routines are the same as the MINIMAX functions in Figure 5.3, except for the two lines in each of MIN-VALUE and MAX-VALUE that maintain alpha and beta (and the bookkeeping to pass these parameters along).

Author:

Ruediger Lunde

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	METRICS_NODES_EXPANDED

Constructor Summary

Constructors

Constructor and Description
AlphaBetaSearch(Game<STATE,ACTION,PLAYER> game)

Method Summary

Modifier and Type	Method and Description
static <STATE,ACTION,PLAYER> AlphaBetaSearch<STATE,ACTION,PLAYER>	createFor(Game<STATE,ACTION,PLAYER> game) Creates a new search object for a given game.
Metrics	getMetrics() Returns all the metrics of the search.
ACTION	makeDecision(STATE state) Returns the action which appears to be the best at the given state.
double	maxValue(STATE state, PLAYER player, double alpha, double beta)
double	minValue(STATE state, PLAYER player, double alpha, double beta)

Methods inherited from class java.lang.Object

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

Field Detail

METRICS_NODES_EXPANDED

public static final java.lang.String METRICS_NODES_EXPANDED

See Also:

Constant Field Values

Constructor Detail

AlphaBetaSearch

public AlphaBetaSearch(Game<STATE,ACTION,PLAYER> game)

Method Detail

createFor

public static <STATE,ACTION,PLAYER> AlphaBetaSearch<STATE,ACTION,PLAYER> createFor(Game<STATE,ACTION,PLAYER> game)

Creates a new search object for a given game.

makeDecision

public ACTION makeDecision(STATE state)

Description copied from interface: AdversarialSearch

Returns the action which appears to be the best at the given state.

Specified by:

makeDecision in interface AdversarialSearch<STATE,ACTION>

maxValue

public double maxValue(STATE state,
                       PLAYER player,
                       double alpha,
                       double beta)

minValue

public double minValue(STATE state,
                       PLAYER player,
                       double alpha,
                       double beta)

getMetrics

public Metrics getMetrics()

Description copied from interface: AdversarialSearch

Returns all the metrics of the search.

Specified by:

getMetrics in interface AdversarialSearch<STATE,ACTION>

Returns:

all the metrics of the search.