Package: GstKopplungNegaMax

GstKopplungNegaMax

name	instruction	branch	complexity	line	method
GstKopplungNegaMax()	M: 0 C: 3 100%	M: 0 C: 0 100%	M: 0 C: 1 100%	M: 0 C: 1 100%	M: 0 C: 1 100%
calculateBestMove(IKopplung, State, int)	M: 3 C: 103 97%	M: 4 C: 8 67%	M: 4 C: 3 43%	M: 2 C: 25 93%	M: 0 C: 1 100%
negamax(IKopplung, State, Integer, Integer, Integer)	M: 0 C: 105 100%	M: 1 C: 13 93%	M: 1 C: 7 88%	M: 0 C: 17 100%	M: 0 C: 1 100%
simulateMove(IKopplung, State, Move)	M: 0 C: 17 100%	M: 0 C: 0 100%	M: 0 C: 1 100%	M: 0 C: 5 100%	M: 0 C: 1 100%

Coverage

1: package de.fhdw.gaming.ipspiel23.gst.strategies.impl;
2:
3: import java.util.Collection;
4: import java.util.Optional;
5:
6: import de.fhdw.gaming.core.domain.GameException;
7: import de.fhdw.gaming.core.domain.Move;
8: import de.fhdw.gaming.core.domain.Player;
9: import de.fhdw.gaming.core.domain.State;
10: import de.fhdw.gaming.ipspiel23.gst.domain.IKopplung;
11: import de.fhdw.gaming.ipspiel23.gst.strategies.domain.IGstKopplungsMiniMaxStrategy;
12:
13: /**
14: * An implementation of the IGstKopplungsMiniMaxStrategy interface using the
15: * NegaMax algorithm with alpha beta pruning and Time based Iterative Deepening.
16: *
17: * @param <P> The type of player in the game.
18: * @param <S> The type of state in the game.
19: * @author borkowitz
20: */
21: public class GstKopplungNegaMax<P extends Player<P>, S extends State<P, S>>
22: implements IGstKopplungsMiniMaxStrategy<P, S> {
23:
24: /**
25: * Calculates the best move for the current player of a Game in a given Game state using the NegaMax algorithm.
26: * Too complex, but not easily simplifyable. Warning suppressed.
27: *
28: * @param kopplung The game object representing the specific game being played.
29: * @param state The current state of the game.
30: * @param maximumComputationTime The maximum computation time allowed for calculating the move.
31: * @return An optional containing the calculated best move, or empty if no move is available.
32: */
33: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
34: @Override
35: public Optional<Move<P, S>> calculateBestMove(final IKopplung<P, S> kopplung, final S state, // NOPMD by Dave on
36: // 26.06.23, 22:57
37: final int maximumComputationTime) {
38: Optional<Move<P, S>> bestMove = Optional.empty();
39: try {
40:
41: final Long startTime = System.currentTimeMillis();
42: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
43:
44:• if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
45:
46: for (int i = 0;; i++) {
47: Integer bestMoveScore = Integer.MIN_VALUE;
48:
49:
50: Optional<Move<P, S>> iterationBestMove = Optional.empty();
51: Integer iterationBestMoveScore = Integer.MIN_VALUE;
52:
53:• if ((System.currentTimeMillis() - startTime) > (maximumComputationTime / 2)) {
54: break;
55: }
56:
57:• for (final Move<P, S> move : possiblesMovesOptional.get()) {
58:
59: final S copiedState = state.deepCopy();
60: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
61: move.applyTo(copiedState, currentPlayer);
62: copiedState.nextTurn();
63:
64: final Integer moveScore = -this.negamax(kopplung, copiedState, i, Integer.MIN_VALUE,
65: Integer.MAX_VALUE);
66:
67:
68:• if (moveScore > iterationBestMoveScore) {
69:
70: iterationBestMove = Optional.of(move);
71: iterationBestMoveScore = moveScore;
72: }
73: }
74:
75:• if (iterationBestMoveScore > bestMoveScore) {
76: bestMove = iterationBestMove;
77: bestMoveScore = iterationBestMoveScore;
78: }
79: }
80: }
81: return bestMove;
82: } catch (final Exception e) {
83:
84: return bestMove;
85: }
86:
87: }
88:
89: /**
90: * Extracted.
91: *
92: * @param kopplung
93: * @param state
94: * @param move
95: * @return
96: * @throws GameException
97: */
98: private S simulateMove(final IKopplung<P, S> kopplung, final S state, final Move<P, S> move) throws GameException {
99: final S copiedState = state.deepCopy();
100: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
101: move.applyTo(copiedState, currentPlayer);
102: copiedState.nextTurn();
103: return copiedState;
104: }
105:
106: /**
107: * Performs the NegaMax algorithm to evaluate the score of a Game state.
108: * Too complex, but not easily simplifyable. Warning suppressed.
109: *
110: * @param kopplung The game object representing the specific game being played.
111: * @param state The current state of the game.
112: * @param depth The current depth of the algorithm.
113: * @param alpha The alpha value for alpha-beta pruning.
114: * @param beta The beta value for alpha-beta pruning.
115: * @return The evaluated score of the state.
116: * @throws Exception
117: */
118: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
119:
120: private Integer negamax(final IKopplung<P, S> kopplung, final S state, final Integer depth, final Integer alpha,
121: final Integer beta) throws GameException {
122:
123:
124:• if (depth == 0 || kopplung.getIsGameOver(state).get()) {
125:
126: return kopplung.evalState(state).get();
127: }
128:
129: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
130:• if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
131:
132: Integer score = Integer.MIN_VALUE;
133: Integer modAlpha = alpha;
134:• for (final Move<P, S> move : possiblesMovesOptional.get()) {
135:
136: final S copiedState = this.simulateMove(kopplung, state, move);
137:
138: final Integer childScore = -this.negamax(kopplung, copiedState, depth - 1, -beta, -modAlpha);
139:• if (childScore > score) {
140:
141: score = childScore - depth;
142: }
143: modAlpha = Math.max(modAlpha, score);
144:• if (modAlpha >= beta) {
145:
146: break;
147: }
148:
149: }
150:
151: return score;
152: }
153:
154: throw new GameException("Something went wrong with Negamax");
155:
156: }
157:
158: }