I have a couple of projects:

- GameAI
- ConnectFour

`GameAI`

implements a couple of algorithms: Minimax, Alpha-beta pruning and Alpha-beta pruning with state ordering.

The actual game tree search algorithms seems to be in order, yet when I play against the bot connected to such an algorithm, it acts rather dumb. My best guess is that the problem lies in the evalutation function. Here is my code:´

`net.coderodde.zerosum.ai.impl.AlphaBetaPruningGameEngine`

`package net.coderodde.zerosum.ai.impl; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import net.coderodde.zerosum.ai.EvaluatorFunction; import net.coderodde.zerosum.ai.GameEngine; import net.coderodde.zerosum.ai.State; /** * This class implements the * <a href="https://en.wikipedia.org/wiki/Minimax">Minimax</a> algorithm for * zero-sum two-player games. * * @param <S> the game state type. * @param <P> the player color type. * @author Rodion "rodde" Efremov * @version 1.6 (May 26, 2019) */ public final class AlphaBetaPruningGameEngine<S extends State<S>, P extends Enum<P>> extends GameEngine<S, P> { /** * Stores the terminal node or a node at the depth zero with the best value * so far, which belongs to the maximizing player moves. */ private S bestTerminalMaximizingState; /** * Stores the value of {@code bestTerminalMaximizingState}. */ private double bestTerminalMaximizingStateValue; /** * Stores the terminal node or a node at the depth zero with the best value * so far, which belongs to the minimizing player moves. */ private S bestTerminalMinimizingState; /** * Stores the value of {@code bestTerminalMinimizingState}. */ private double bestTerminalMinimizingStateValue; /** * Indicates whether we are computing a next ply for the minimizing player * or not. If not, we are computing a next ply for the maximizing player. */ private boolean makingPlyForMinimizingPlayer; /** * Maps each visited state to its parent state. */ private final Map<S, S> parents = new HashMap<>(); /** * Constructs this minimax game engine. * @param evaluatorFunction the evaluator function. * @param depth the search depth. */ public AlphaBetaPruningGameEngine(EvaluatorFunction<S> evaluatorFunction, int depth) { super(evaluatorFunction, depth, Integer.MAX_VALUE); } /** * {@inheritDoc } */ @Override public S makePly(S state, P minimizingPlayer, P maximizingPlayer, P initialPlayer) { // Reset the best known values: bestTerminalMaximizingStateValue = Double.NEGATIVE_INFINITY; bestTerminalMinimizingStateValue = Double.POSITIVE_INFINITY; makingPlyForMinimizingPlayer = initialPlayer != minimizingPlayer; // Do the game tree search: makePlyImpl(state, depth, Double.NEGATIVE_INFINITY, // intial alpha Double.POSITIVE_INFINITY, // intial beta minimizingPlayer, maximizingPlayer, initialPlayer); // Find the next game state starting from 'state': S returnState = inferBestState( initialPlayer == minimizingPlayer ? bestTerminalMinimizingState : bestTerminalMaximizingState); // Release the resources: parents.clear(); bestTerminalMaximizingState = null; bestTerminalMinimizingState = null; // We are done with a single move: return returnState; } private S inferBestState(S bestTerminalState) { List<S> statePath = new ArrayList<>(); S state = bestTerminalState; while (state != null) { statePath.add(state); state = parents.get(state); } if (statePath.size() == 1) { // The root node is terminal. Return null: return null; } // Return the second upmost state: Collections.<S>reverse(statePath); return statePath.get(1); } /** * Performs a single step down the game tree branch. * * @param state the starting state. * @param depth the maximum depth of the game tree. * @param minimizingPlayer the minimizing player. * @param maximizingPlayer the maximizing player. * @param currentPlayer the current player. * @return the value of the best ply. */ private double makePlyImpl(S state, int depth, double alpha, double beta, P minimizingPlayer, P maximizingPlayer, P currentPlayer) { if (depth == 0 || state.isTerminal()) { double value = evaluatorFunction.evaluate(state); if (!makingPlyForMinimizingPlayer) { if (bestTerminalMinimizingStateValue > value) { bestTerminalMinimizingStateValue = value; bestTerminalMinimizingState = state; } } else { if (bestTerminalMaximizingStateValue < value) { bestTerminalMaximizingStateValue = value; bestTerminalMaximizingState = state; } } return value; } if (currentPlayer == maximizingPlayer) { double value = Double.NEGATIVE_INFINITY; for (S child : state.children()) { value = Math.max( value, makePlyImpl(child, depth - 1, alpha, beta, minimizingPlayer, maximizingPlayer, minimizingPlayer)); parents.put(child, state); alpha = Math.max(alpha, value); if (alpha >= beta) { break; } } return value; } else { // Here, 'initialPlayer == minimizingPlayer'. double value = Double.POSITIVE_INFINITY; for (S child : state.children()) { value = Math.min( value, makePlyImpl(child, depth - 1, alpha, beta, minimizingPlayer, maximizingPlayer, maximizingPlayer)); parents.put(child, state); beta = Math.min(beta, value); if (alpha >= beta) { break; } } return value; } } } `

`net.coderodde.games.connect.four.impl.BruteForceConnectFourStateEvaluatorFunction`

`package net.coderodde.games.connect.four.impl; import net.coderodde.games.connect.four.ConnectFourState; import net.coderodde.games.connect.four.PlayerColor; import net.coderodde.zerosum.ai.EvaluatorFunction; /** * This class implements the default Connect Four state evaluator. The white * player wants to maximize, the red player wants to minimize. * * @author Rodion "rodde" Efremov * @version 1.6 (May 24, 2019) */ public final class BruteForceConnectFourStateEvaluatorFunction implements EvaluatorFunction<ConnectFourState> { private static final double NEGATIVE_WIN_VALUE = -1e6; private static final double POSITIVE_WIN_VALUE = 1e6; private static final double BASE_VALUE = 1e1; /** * The weight matrix. Maps each position to its weight. We need this in * order to */ private final double[][] weightMatrix; /** * The winning length. */ private final int winningLength; /** * Constructs the default heuristic function for Connect Four game states. * * @param width the game board width. * @param height the game board height. * @param maxWeight the maximum weight in the weight matrix. * @param winningPatternLength the winning pattern length. */ public BruteForceConnectFourStateEvaluatorFunction(final int width, final int height, final double maxWeight, final int winningPatternLength) { this.weightMatrix = getWeightMatrix(width, height, maxWeight); this.winningLength = winningPatternLength; } /** * Evaluates the given input {@code state} and returns the estimate. * @param state the state to estimate. * @return the estimate. */ @Override public double evaluate(ConnectFourState state) { // 'minimizingPatternCounts[i]' gives the number of patterns of // length 'i': int[] minnimizingPatternCounts = new int[state.getWinningLength() + 1]; int[] maximizingPatternCounts = new int[minnimizingPatternCounts.length]; // Do not consider patterns of length one! for (int targetLength = 2; targetLength <= winningLength; targetLength++) { int count = findRedPatternCount(state, targetLength); if (count == 0) { // Once here, it is not possible to find patterns of larger // length than targetLength: break; } minnimizingPatternCounts[targetLength] = count; } for (int targetLength = 2; targetLength <= state.getWinningLength(); targetLength++) { int count = findWhitePatternCount(state, targetLength); if (count == 0) { // Once here, it is not possible to find patterns of larger // length than targetLength: break; } maximizingPatternCounts[targetLength] = count; } double score = computeBaseScore(minnimizingPatternCounts, maximizingPatternCounts); return score + getWeights(weightMatrix, state); } /** * Finds the number of red patterns of length {@code targetLength}. * @param state the target state. * @param targetLength the length of the pattern to find. * @return the number of red patterns of length {@code targetLength}. */ private static final int findRedPatternCount(ConnectFourState state, int targetLength) { return findPatternCount(state, targetLength, PlayerColor.MINIMIZING_PLAYER); } /** * Finds the number of white patterns of length {@code targetLength}. * @param state the target state. * @param targetLength the length of the pattern to find. * @return the number of white patterns of length {@code targetLength}. */ private static final int findWhitePatternCount(ConnectFourState state, int targetLength) { return findPatternCount(state, targetLength, PlayerColor.MAXIMIZING_PLAYER); } /** * Implements the target pattern counting function for both the player * colors. * @param state the state to search. * @param targetLength the length of the patterns to count. * @param playerColor the target player color. * @return the number of patterns of length {@code targetLength} and color * {@code playerColor}. */ private static final int findPatternCount(ConnectFourState state, int targetLength, PlayerColor playerColor) { int count = 0; count += findHorizontalPatternCount(state, targetLength, playerColor); count += findVerticalPatternCount(state, targetLength, playerColor); count += findAscendingDiagonalPatternCount(state, targetLength, playerColor); count += findDescendingDiagonalPatternCount(state, targetLength, playerColor); return count; } /** * Scans the input state for diagonal <b>descending</b> patterns and * returns the number of such patterns. * @param state the target state. * @param patternLength the target pattern length. * @param playerColor the target player color. * @return the number of patterns. */ private static final int findDescendingDiagonalPatternCount(ConnectFourState state, int patternLength, PlayerColor playerColor) { int patternCount = 0; for (int y = 0; y < state.getWinningLength() - 1; y++) { inner: for (int x = 0; x <= state.getWidth() - state.getWinningLength(); x++) { for (int i = 0; i < patternLength; i++) { if (state.readCell(x + i, y + i) != playerColor) { continue inner; } } patternCount++; } } return patternCount; } /** * Scans the input state for diagonal <b>ascending</b> patterns and returns * the number of such patterns. * @param state the target state. * @param patternLength the target pattern length. * @param playerColor the target player color. * @return the number of patterns. */ private static final int findAscendingDiagonalPatternCount(ConnectFourState state, int patternLength, PlayerColor playerColor) { int patternCount = 0; for (int y = state.getHeight() - 1; y > state.getHeight() - state.getWinningLength(); y--) { inner: for (int x = 0; x <= state.getWidth() - state.getWinningLength(); x++) { for (int i = 0; i < patternLength; i++) { if (state.readCell(x + i, y - i) != playerColor) { continue inner; } } patternCount++; } } return patternCount; } /** * Scans the input state for diagonal <b>horizontal</b> patterns and returns * the number of such patterns. * @param state the target state. * @param patternLength the target pattern length. * @param playerColor the target player color. * @return the number of patterns. */ private static final int findHorizontalPatternCount( ConnectFourState state, int patternLength, PlayerColor playerColor) { int patternCount = 0; for (int y = state.getHeight() - 1; y >= 0; y--) { inner: for (int x = 0; x <= state.getWidth() - patternLength; x++) { if (state.readCell(x, y) == null) { continue inner; } for (int i = 0; i < patternLength; i++) { if (state.readCell(x + i, y) != playerColor) { continue inner; } } patternCount++; } } return patternCount; } /** * Scans the input state for diagonal <b>vertical</b> patterns and returns * the number of such patterns. * @param state the target state. * @param patternLength the target pattern length. * @param playerColor the target player color. * @return the number of patterns. */ private static final int findVerticalPatternCount(ConnectFourState state, int patternLength, PlayerColor playerColor) { int patternCount = 0; outer: for (int x = 0; x < state.getWidth(); x++) { inner: for (int y = state.getHeight() - 1; y > state.getHeight() - state.getWinningLength(); y--) { if (state.readCell(x, y) == null) { continue outer; } for (int i = 0; i < patternLength; i++) { if (state.readCell(x, y - i) != playerColor) { continue inner; } } patternCount++; } } return patternCount; } /** * Gets the state weight. We use this in order to discourage the positions * that are close to borders/far away from the center of the game board. * @param weightMatrix the weighting matrix. * @param state the state to weight. * @return the state weight. */ private static final double getWeights(final double[][] weightMatrix, final ConnectFourState state) { double score = 0.0; outer: for (int x = 0; x < state.getWidth(); x++) { for (int y = state.getHeight() - 1; y >= 0; y--) { PlayerColor playerColor = state.readCell(x, y); if (playerColor == null) { continue outer; } if (playerColor == PlayerColor.MINIMIZING_PLAYER) { score -= weightMatrix[y][x]; } else { score += weightMatrix[y][x]; } } } return score; } /** * Computes the base scorer that relies on number of patterns. For example, * {@code redPatternCounts[i]} will denote the number of patterns of length * [@code i}. * @param minimizingPatternCounts the pattern count map for red patterns. * @param maximizingPatternCounts the pattern count map for white patterns. * @return the base estimate. */ private static final double computeBaseScore( int[] minimizingPatternCounts, int[] maximizingPatternCounts) { final int winningLength = minimizingPatternCounts.length - 1; double value = 0.0; if (minimizingPatternCounts[winningLength] != 0) { value = NEGATIVE_WIN_VALUE; } if (maximizingPatternCounts[winningLength] != 0) { value = POSITIVE_WIN_VALUE; } for (int length = 2; length < minimizingPatternCounts.length; length++) { int minimizingCount = minimizingPatternCounts[length]; value -= minimizingCount * Math.pow(BASE_VALUE, length); int maximizingCount = maximizingPatternCounts[length]; value += maximizingCount * Math.pow(BASE_VALUE, length); } return value; } /** * Computes the weight matrix. The closer the entry in the board is to the * center of the board, the closer the weight of that position will be to * {@code maxWeight}. * * @param width the width of the matrix. * @param height the height of the matrix. * @param maxWeight the maximum weight. The minimum weight will be always * 1.0. * @return the weight matrix. */ private static final double[][] getWeightMatrix(final int width, final int height, final double maxWeight) { final double[][] weightMatrix = new double[height][width]; for (int y = 0; y < weightMatrix.length; y++) { for (int x = 0; x < weightMatrix[0].length; x++) { int left = x; int right = weightMatrix[0].length - x - 1; int top = y; int bottom = weightMatrix.length - y - 1; int horizontalDifference = Math.abs(left - right); int verticalDifference = Math.abs(top - bottom); weightMatrix[y][x] = 1.0 + (maxWeight - 1.0) / (horizontalDifference + verticalDifference); } } return weightMatrix; } } `

**Critique request**

Any comments on my code?