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.public class MinimaxSearch<STATE,ACTION,PLAYER> extends java.lang.Object implements AdversarialSearch<STATE,ACTION>
function MINIMAX-DECISION(state) returns an action
return argmax_[a in ACTIONS(s)] MIN-VALUE(RESULT(state, a))
function MAX-VALUE(state) 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)))
return v
function MIN-VALUE(state) 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)))
return v
Figure 5.3 An algorithm for calculating minimax decisions. It returns the
action corresponding to the best possible move, that is, the move that leads
to the outcome with the best utility, under the assumption that the opponent
plays to minimize utility. The functions MAX-VALUE and MIN-VALUE go through
the whole game tree, all the way to the leaves, to determine the backed-up
value of a state. The notation argmax_[a in S] f(a) computes the element a of
set S that has the maximum value of f(a).Modifier and Type | Field and Description |
---|---|
static java.lang.String |
METRICS_NODES_EXPANDED |
Constructor and Description |
---|
MinimaxSearch(Game<STATE,ACTION,PLAYER> game) |
Modifier and Type | Method and Description |
---|---|
static <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 |
minValue(STATE state,
PLAYER player) |
public static final java.lang.String METRICS_NODES_EXPANDED
public static <STATE,ACTION,PLAYER> MinimaxSearch<STATE,ACTION,PLAYER> createFor(Game<STATE,ACTION,PLAYER> game)
public ACTION makeDecision(STATE state)
AdversarialSearch
makeDecision
in interface AdversarialSearch<STATE,ACTION>
public Metrics getMetrics()
AdversarialSearch
getMetrics
in interface AdversarialSearch<STATE,ACTION>