-
Notifications
You must be signed in to change notification settings - Fork 791
/
MinimaxSearch.java
108 lines (97 loc) · 3.6 KB
/
MinimaxSearch.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
package aima.core.search.adversarial;
import aima.core.search.framework.Metrics;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): page 169.<br>
* <p>
* <pre>
* <code>
* 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
* </code>
* </pre>
* <p>
* 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).
*
* @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 MinimaxSearch<S, A, P> implements AdversarialSearch<S, A> {
public final static String METRICS_NODES_EXPANDED = "nodesExpanded";
private Game<S, A, P> game;
private Metrics metrics = new Metrics();
/**
* Creates a new search object for a given game.
*/
public static <S, A, P> MinimaxSearch<S, A, P> createFor(Game<S, A, P> game) {
return new MinimaxSearch<>(game);
}
public MinimaxSearch(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);
if (value > resultValue) {
result = action;
resultValue = value;
}
}
return result;
}
// Note: This version looks cleaner but expands almost twice as much nodes (Comparator...)
// @Override
// public A makeDecision(S state) {
// metrics = new Metrics();
// P player = game.getPlayer(state);
// return game.getActions(state).stream()
// .max(Comparator.comparing(action -> minValue(game.getResult(state, action), player)))
// .orElse(null);
// }
public double maxValue(S state, P player) { // returns an utility value
metrics.incrementInt(METRICS_NODES_EXPANDED);
if (game.isTerminal(state))
return game.getUtility(state, player);
return game.getActions(state).stream()
.mapToDouble(action -> minValue(game.getResult(state, action), player))
.max().orElse(Double.NEGATIVE_INFINITY);
}
public double minValue(S state, P player) { // returns an utility value
metrics.incrementInt(METRICS_NODES_EXPANDED);
if (game.isTerminal(state))
return game.getUtility(state, player);
return game.getActions(state).stream()
.mapToDouble(action -> maxValue(game.getResult(state, action), player))
.min().orElse(Double.POSITIVE_INFINITY);
}
@Override
public Metrics getMetrics() {
return metrics;
}
}