/
AlphaBetaSearch.java
111 lines (101 loc) · 3.81 KB
/
AlphaBetaSearch.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package aima.core.search.adversarial;
import aima.core.search.framework.Metrics;
/**
* Artificial Intelligence A Modern Approach (3rd Ed.): Page 173.<br>
* <p>
* <pre>
* <code>
* 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
* </code>
* </pre>
* <p>
* 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).
*
* @param <S> Type which is used for states in the game.
* @param <A> Type which is used for actions in the game.
* @param <P> Type which is used for players in the game.
* @author Ruediger Lunde
*/
public class AlphaBetaSearch<S, A, P> implements AdversarialSearch<S, A> {
public final static String METRICS_NODES_EXPANDED = "nodesExpanded";
Game<S, A, P> game;
private Metrics metrics = new Metrics();
/**
* Creates a new search object for a given game.
*/
public static <STATE, ACTION, PLAYER> AlphaBetaSearch<STATE, ACTION, PLAYER> createFor(
Game<STATE, ACTION, PLAYER> game) {
return new AlphaBetaSearch<STATE, ACTION, PLAYER>(game);
}
public AlphaBetaSearch(Game<S, A, P> game) {
this.game = game;
}
@Override
public A makeDecision(S state) {
metrics = new Metrics();
A result = null;
double resultValue = Double.NEGATIVE_INFINITY;
P player = game.getPlayer(state);
for (A action : game.getActions(state)) {
double value = minValue(game.getResult(state, action), player, resultValue, Double.POSITIVE_INFINITY);
if (value > resultValue) {
result = action;
resultValue = value;
}
}
return result;
}
public double maxValue(S state, P player, double alpha, double beta) {
metrics.incrementInt(METRICS_NODES_EXPANDED);
if (game.isTerminal(state))
return game.getUtility(state, player);
double value = Double.NEGATIVE_INFINITY;
for (A action : game.getActions(state)) {
value = Math.max(value, minValue(game.getResult(state, action), player, alpha, beta));
if (value >= beta)
return value;
alpha = Math.max(alpha, value);
}
return value;
}
public double minValue(S state, P player, double alpha, double beta) {
metrics.incrementInt(METRICS_NODES_EXPANDED);
if (game.isTerminal(state))
return game.getUtility(state, player);
double value = Double.POSITIVE_INFINITY;
for (A action : game.getActions(state)) {
value = Math.min(value, maxValue(game.getResult(state, action), player, alpha, beta));
if (value <= alpha)
return value;
beta = Math.min(beta, value);
}
return value;
}
@Override
public Metrics getMetrics() {
return metrics;
}
}