Method: getBestMove(State, Player)

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: public class Minimax<P extends Player<P>, S extends State<P, S>, M extends Move<P, S>> {
11:
12: private final int maxDepth;
13: private final MinimaxStrategy<P, S, M> strategy;
14: private final P opponent;
15:
16: public Minimax(final MinimaxStrategy<P, S, M> strategy, final int maxDepth, final P opponent) {
17: this.strategy = strategy;
18: this.maxDepth = maxDepth;
19: this.opponent = opponent;
20: }
21:
22: public M getBestMove(S state, final P player) throws GameException {
23: final List<M> possibleMoves = this.strategy.getPossibleMoves(state);
24:• if (possibleMoves.isEmpty()) {
25: return null;
26: }
27:
28: int bestScore = Integer.MIN_VALUE;
29: M bestMove = null;
30:• for (final M move : possibleMoves) {
31: final S stateCopy = state.deepCopy();
32: move.applyTo(stateCopy, player);
33: stateCopy.nextTurn();
34: final int score = -negamax(stateCopy, player, this.maxDepth, Integer.MIN_VALUE, Integer.MAX_VALUE, false);
35: System.out.println("score Move: " + score + " for " + move.toString());
36:• if (score > bestScore) {
37: bestScore = score;
38: bestMove = move;
39: }
40: }
41: System.out.println("ALL MOVES EVALUATED, best Score: " + bestScore);
42: return bestMove;
43: }
44:
45: /**
46: * negamax algorithm.
47: *
48: * @param state of game
49: * @param player player
50: * @param depth maxdepth of game tree
51: * @param alpha lower bound of range for ab-pruning
52: * @param beta upper bound for pruning
53: * @param isMaximising whether the minimizing player or maximising players turn
54: * @return score of individual path.
55: * @throws GameException
56: */
57: private int negamax(S state, final P player, final int depth, final int alpha, final int beta,
58: final boolean isMaximising) throws GameException {
59: int newAlpha = alpha;
60: final int newBeta = beta;
61:
62: final int evaluation = this.strategy.evaluate(state, player, depth);
63: if (depth == 0 || Math.abs(evaluation) > 0 || this.strategy.getPossibleMoves(state).isEmpty()) {
64: return evaluation * (isMaximising ? 1 : -1);
65: }
66:
67: int bestValue = Integer.MIN_VALUE;
68: //System.out.println("isMaximising: " + isMaximising + " ------------------");
69: for (final M move : this.strategy.getPossibleMoves(state)) {
70: final S stateCopy = state.deepCopy();
71: move.applyTo(stateCopy, isMaximising ? player : this.opponent);
72: stateCopy.nextTurn();
73: //System.out.println(move.toString());
74: final int value = -negamax(stateCopy, player, depth - 1, -newBeta,
75: -newAlpha, !isMaximising);
76: //System.out.println("negamx value: " + value);
77: bestValue = Math.max(bestValue, value);
78: newAlpha = Math.max(newAlpha, bestValue);
79:
80: if (newAlpha >= newBeta) {
81: break;
82: }
83:
84: }
85:
86: return bestValue;
87: }
88: }