Package: GstKopplungNegaMaxMultithreading

GstKopplungNegaMaxMultithreading

name	instruction	branch	complexity	line	method
GstKopplungNegaMaxMultithreading()	M: 3 C: 0 0%	M: 0 C: 0 100%	M: 1 C: 0 0%	M: 1 C: 0 0%	M: 1 C: 0 0%
calculateBestMove(IKopplung, State, int)	M: 138 C: 0 0%	M: 12 C: 0 0%	M: 7 C: 0 0%	M: 30 C: 0 0%	M: 1 C: 0 0%
lambda$calculateBestMove$0(IKopplung, State, Integer)	M: 13 C: 0 0%	M: 0 C: 0 100%	M: 1 C: 0 0%	M: 2 C: 0 0%	M: 1 C: 0 0%
negamax(IKopplung, State, Integer, Integer, Integer)	M: 105 C: 0 0%	M: 14 C: 0 0%	M: 8 C: 0 0%	M: 17 C: 0 0%	M: 1 C: 0 0%
simulateMove(IKopplung, State, Move)	M: 17 C: 0 0%	M: 0 C: 0 100%	M: 1 C: 0 0%	M: 5 C: 0 0%	M: 1 C: 0 0%

Coverage

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