Package: Minimax

Minimax

name	instruction	branch	complexity	line	method
Minimax(MinimaxStrategy, int, Player)	M: 0 C: 15 100%	M: 0 C: 0 100%	M: 0 C: 1 100%	M: 0 C: 6 100%	M: 0 C: 1 100%
getBestMove(State, Player)	M: 2 C: 51 96%	M: 1 C: 5 83%	M: 1 C: 3 75%	M: 1 C: 14 93%	M: 0 C: 1 100%
negamax(State, Player, int, int, int, boolean)	M: 0 C: 96 100%	M: 0 C: 16 100%	M: 0 C: 9 100%	M: 0 C: 18 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: * Minimax Class, needs to be implemented by Strategy.
12: *
13: * @param <P> Generic Player, special Player needs to be passed at implementation
14: * @param <S> Generic State, special State needs to be passed at implementation
15: * @param <M> Generic Move, special Move needs to be passed at implementation
16: */
17: public class Minimax<P extends Player<P>, S extends State<P, S>, M extends Move<P, S>> {
18:
19: /**
20: * Max depth of Minimax Tree.
21: */
22: private final int maxDepth;
23: /**
24: * Strategy that implements MinimaxStrategy.
25: */
26: private final MinimaxStrategy<P, S, M> strategy;
27: /**
28: * Opponent of player that uses minimax.
29: */
30: private final P opponent;
31:
32: /**
33: * score where abs(score) > endScore means definitive End of Game. e.g. a win.
34: */
35: private final int endScore = 10000;
36:
37: /**
38: * Minimax class.
39: *
40: * @param strategy MinimaxStrategy that is implemented. Pass instance.
41: * @param maxDepth maximum depth of minimax tree, larger values = move computation effort.
42: * @param opponent opponent of minimax player
43: */
44: public Minimax(final MinimaxStrategy<P, S, M> strategy, final int maxDepth, final P opponent) {
45: this.strategy = strategy;
46: this.maxDepth = maxDepth;
47: this.opponent = opponent;
48: }
49:
50: /**
51: * returns best move for given game state.
52: *
53: * @param state State of the game.
54: * @param player Active Player.
55: */
56: public M getBestMove(final S state, final P player) throws GameException {
57:
58: final List<M> possibleMoves = this.strategy.getPossibleMoves(state);
59:• if (possibleMoves.isEmpty()) {
60: return null;
61: }
62:
63: int bestScore = Integer.MIN_VALUE + 1;
64: M bestMove = null;
65:• for (final M move : possibleMoves) {
66: final S stateCopy = state.deepCopy();
67: move.applyTo(stateCopy, player);
68: stateCopy.nextTurn();
69: final int score = -this.negamax(stateCopy, player, 0, Integer.MIN_VALUE + 1, Integer.MAX_VALUE,
70: false);
71:• if (score > bestScore) {
72: bestScore = score;
73: bestMove = move;
74: }
75: }
76: return bestMove;
77: }
78:
79: /**
80: * negamax algorithm.
81: *
82: * @param state of game
83: * @param player player
84: * @param depth maximum depth of game tree
85: * @param alpha lower bound of range for ab-pruning
86: * @param beta upper bound for pruning
87: * @param isMaximising whether the minimising player or maximising players turn
88: * @return score of individual path.
89: * @throws GameException
90: */
91: private int negamax(final S state, final P player, final int depth, final int alpha, final int beta,
92: final boolean isMaximising) throws GameException {
93:
94: int newAlpha = alpha;
95: final int newBeta = beta;
96: final int evaluation = this.strategy.evaluate(state, player, depth);
97: final List<M> possibleMoves = this.strategy.getPossibleMoves(state);
98:
99:• if (depth == this.maxDepth || possibleMoves.isEmpty() || evaluation > this.endScore) {
100:• return evaluation * (isMaximising ? 1 : -1);
101: }
102:
103: int bestValue = Integer.MIN_VALUE + 1;
104:• for (final M move : possibleMoves) {
105:
106: final S stateCopy = state.deepCopy();
107:• move.applyTo(stateCopy, isMaximising ? player : this.opponent);
108: stateCopy.nextTurn();
109:• final int value = -this.negamax(stateCopy, player, depth + 1, -newBeta,
110: -newAlpha, !isMaximising);
111: bestValue = Math.max(bestValue, value);
112: newAlpha = Math.max(newAlpha, bestValue);
113:
114:• if (newAlpha >= newBeta) {
115: break;
116: }
117:
118: }
119:
120: return bestValue;
121: }
122:
123: }