Content of file GstKopplungNegaMaxMultithreading.java
package de.fhdw.gaming.ipspiel23.gst.strategies.impl;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Optional;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicReference;
import de.fhdw.gaming.core.domain.GameException;
import de.fhdw.gaming.core.domain.Move;
import de.fhdw.gaming.core.domain.Player;
import de.fhdw.gaming.core.domain.State;
import de.fhdw.gaming.ipspiel23.gst.domain.IKopplung;
import de.fhdw.gaming.ipspiel23.gst.strategies.domain.IGstKopplungsMiniMaxStrategy;
/**
* An implementation of the IGstKopplungsMiniMaxStrategy interface using the
* NegaMax algorithm with alpha beta pruning and Time based Iterative Deepening.
*
* @param <P> The type of player in the game.
* @param <S> The type of state in the game.
* @author borkowitz
*/
public class GstKopplungNegaMaxMultithreading<P extends Player<P>, S extends State<P, S>>
implements IGstKopplungsMiniMaxStrategy<P, S> {
/**
* Calculates the best move for the current player of a Game in a given Game state using the NegaMax algorithm.
* Too complex, but not easily simplifyable. Warning suppressed.
*
* @param kopplung The game object representing the specific game being played.
* @param state The current state of the game.
* @param maximumComputationTime The maximum computation time allowed for calculating the move.
* @return An optional containing the calculated best move, or empty if no move is available.
*/
@SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
@Override
public Optional<Move<P, S>> calculateBestMove(final IKopplung<P, S> kopplung, final S state, // NOPMD by Dave on
// 26.06.23, 22:57
final int maximumComputationTime) {
Optional<Move<P, S>> bestMove = Optional.empty();
final AtomicReference<Integer> bestMoveScore = new AtomicReference<>(Integer.MIN_VALUE);
final ExecutorService executorService = Executors
.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
try {
final Long startTime = System.currentTimeMillis();
final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
if (possiblesMovesOptional.isPresent() && !possiblesMovesOptional.get().isEmpty()) {
for (int i = 0;; i++) {
final Integer depth = i;
if ((System.currentTimeMillis() - startTime) > (maximumComputationTime / 2)) {
break;
}
final List<Future<Integer>> futures = new ArrayList<>();
final List<Move<P, S>> moves = new ArrayList<>(possiblesMovesOptional.get());
for (final Move<P, S> move : moves) {
final S copiedState = state.deepCopy();
final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
move.applyTo(copiedState, currentPlayer);
copiedState.nextTurn();
futures.add(executorService.submit(
() -> -this.negamax(kopplung, copiedState, depth, Integer.MIN_VALUE,
Integer.MAX_VALUE)));
}
for (final Future<Integer> future : futures) {
final Integer moveScore = future.get(); // Wait for all threads to complete
if (moveScore > bestMoveScore.get()) {
bestMoveScore.set(moveScore);
bestMove = Optional.of(moves.get(futures.indexOf(future)));
}
}
}
}
// System.out.println(bestMove);
return bestMove;
} catch (final Exception e) {
e.printStackTrace();
Avoid printStackTrace(); use a logger call instead.
Avoid printStackTrace(); use a logger call instead.
class Foo {
void bar() {
try {
// do something
} catch (Exception e) {
e.printStackTrace();
}
}
}
return bestMove;
} finally {
executorService.shutdown();
}
}
/**
* Extracted.
*
* @param kopplung
* @param state
* @param move
* @return
* @throws GameException
*/
private S simulateMove(final IKopplung<P, S> kopplung, final S state, final Move<P, S> move) throws GameException {
final S copiedState = state.deepCopy();
final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
move.applyTo(copiedState, currentPlayer);
copiedState.nextTurn();
return copiedState;
}
/**
* Performs the NegaMax algorithm to evaluate the score of a Game state.
* Too complex, but not easily simplifyable. Warning suppressed.
*
* @param kopplung The game object representing the specific game being played.
* @param state The current state of the game.
* @param depth The current depth of the algorithm.
* @param alpha The alpha value for alpha-beta pruning.
* @param beta The beta value for alpha-beta pruning.
* @return The evaluated score of the state.
* @throws Exception
*/
@SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
private Integer negamax(final IKopplung<P, S> kopplung, final S state, final Integer depth, final Integer alpha,
final Integer beta) throws GameException {
final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
if (depth == 0 || kopplung.getIsGameOver(state).get()) {
return kopplung.evalState(state).get();
}
if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
Integer score = Integer.MIN_VALUE;
Integer modAlpha = alpha;
for (final Move<P, S> move : possiblesMovesOptional.get()) {
final S copiedState = this.simulateMove(kopplung, state, move);
final Integer childScore = -this.negamax(kopplung, copiedState, depth - 1, -beta, -modAlpha);
if (childScore > score) {
score = childScore - depth;
}
modAlpha = Math.max(modAlpha, score);
if (modAlpha >= beta) {
break;
}
}
return score;
}
throw new GameException("Something went wrong with Negamax");
}
}