Package: Minimax

Minimax

name	instruction	branch	complexity	line	method
Minimax(MinimaxStrategy, int, Player)	M: 0 C: 12 100%	M: 0 C: 0 100%	M: 0 C: 1 100%	M: 0 C: 5 100%	M: 0 C: 1 100%
getBestMove(State, Player)	M: 2 C: 62 97%	M: 1 C: 5 83%	M: 1 C: 3 75%	M: 1 C: 16 94%	M: 0 C: 1 100%
negamax(State, Player, int, int, int, boolean)	M: 0 C: 92 100%	M: 1 C: 15 94%	M: 1 C: 8 89%	M: 0 C: 17 100%	M: 0 C: 1 100%

Coverage

1: package de.fhdw.gaming.ipspiel24.minimax;
2:
3: import java.util.List;
4:
5: import de.fhdw.gaming.core.domain.GameException;
6: import de.fhdw.gaming.core.domain.Move;
7: import de.fhdw.gaming.core.domain.Player;
8: import de.fhdw.gaming.core.domain.State;
9:
10: /**
11: * TODO missing comment.
12: *
13: * @param <P> TODO
14: * @param <S> TODO
15: * @param <M> TODO
16: */
17: public class Minimax<P extends Player<P>, S extends State<P, S>, M extends Move<P, S>> {
18:
19: /**
20: * TODO missing comment.
21: */
22: private final int maxDepth;
23: /**
24: * TODO missing comment.
25: */
26: private final MinimaxStrategy<P, S, M> strategy;
27: /**
28: * TODO missing comment.
29: */
30: private final P opponent;
31:
32: /**
33: * TODO missing comment.
34: *
35: * @param strategy TODO
36: * @param maxDepth TODO
37: * @param opponent TODO
38: */
39: public Minimax(final MinimaxStrategy<P, S, M> strategy, final int maxDepth, final P opponent) {
40: this.strategy = strategy;
41: this.maxDepth = maxDepth;
42: this.opponent = opponent;
43: }
44:
45: /**
46: * TODO missing comment.
47: *
48: * @param state TODO
49: * @param player TODO
50: */
51: public M getBestMove(final S state, final P player) throws GameException {
52: final List<M> possibleMoves = this.strategy.getPossibleMoves(state);
53:• if (possibleMoves.isEmpty()) {
54: return null;
55: }
56:
57: int bestScore = Integer.MIN_VALUE + 1;
58: M bestMove = null;
59:• for (final M move : possibleMoves) {
60: final S stateCopy = state.deepCopy();
61: move.applyTo(stateCopy, player);
62: stateCopy.nextTurn();
63: final int score = -this.negamax(stateCopy, player, this.maxDepth, Integer.MIN_VALUE + 1, Integer.MAX_VALUE,
64: false);
65: System.out.println("score Move: " + score + " for " + move.toString());
66:• if (score > bestScore) {
67: bestScore = score;
68: bestMove = move;
69: }
70: }
71: System.out.println("ALL MOVES EVALUATED, best Score: " + bestScore);
72: return bestMove;
73: }
74:
75: /**
76: * negamax algorithm.
77: *
78: * @param state of game
79: * @param player player
80: * @param depth maxdepth of game tree
81: * @param alpha lower bound of range for ab-pruning
82: * @param beta upper bound for pruning
83: * @param isMaximising whether the minimizing player or maximising players turn
84: * @return score of individual path.
85: * @throws GameException
86: */
87: private int negamax(final S state, final P player, final int depth, final int alpha, final int beta,
88: final boolean isMaximising) throws GameException {
89: int newAlpha = alpha;
90: final int newBeta = beta;
91:
92: final int evaluation = this.strategy.evaluate(state, player, depth);
93:• if (depth == 0 || Math.abs(evaluation) > 0 || this.strategy.getPossibleMoves(state).isEmpty()) {
94:• return evaluation * (isMaximising ? 1 : -1);
95: }
96:
97: int bestValue = Integer.MIN_VALUE + 1;
98: // System.out.println("isMaximising: " + isMaximising + " ------------------");
99:• for (final M move : this.strategy.getPossibleMoves(state)) {
100: final S stateCopy = state.deepCopy();
101:• move.applyTo(stateCopy, isMaximising ? player : this.opponent);
102: stateCopy.nextTurn();
103: // System.out.println(move.toString());
104:• final int value = -this.negamax(stateCopy, player, depth - 1, -newBeta,
105: -newAlpha, !isMaximising);
106: // System.out.println("negamx value: " + value);
107: bestValue = Math.max(bestValue, value);
108: newAlpha = Math.max(newAlpha, bestValue);
109:
110:• if (newAlpha >= newBeta) {
111: break;
112: }
113:
114: }
115:
116: return bestValue;
117: }
118: }