4
\$\begingroup\$

I have this GitHub repository. It implements the command-line version of the Connect Four game. The AI bot is implemented via Alpha-beta pruning.

Code

com.github.coderodde.game.zerosum.impl.AlphaBetaPruningSearchEngine.java:

package com.github.coderodde.game.zerosum.impl;

import com.github.coderodde.game.zerosum.PlayerType;
import com.github.coderodde.game.zerosum.GameState;
import com.github.coderodde.game.zerosum.HeuristicFunction;
import com.github.coderodde.game.zerosum.SearchEngine;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">
 * Alpha-beta pruning</a> algorithm for making a move.
 * 
 * @param <S> the game state type.
 * 
 * @version 1.0.0 (Jun 5, 2024)
 * @since 1.0.0 (Jun 5, 2024)
 */
public final class AlphaBetaPruningSearchEngine<S extends GameState<S>>
        implements SearchEngine<S> {

    private S bestMoveState;
    private final HeuristicFunction<S> heuristicFunction;
    
    public AlphaBetaPruningSearchEngine(
            final HeuristicFunction<S> heuristicFunction,
            final double minimizingPlayerVictoryScore,
            final double maximizingPlayerVictoryScore) {
        
        this.heuristicFunction = heuristicFunction;
    }
    
    @Override
    public S search(final S root, final int depth) {
        bestMoveState = null;
        
        alphaBetaRootImpl(root, 
                          depth,
                          Double.NEGATIVE_INFINITY, 
                          Double.POSITIVE_INFINITY);
        
        return bestMoveState;
    }
    
    private void alphaBetaRootImpl(final S root, 
                                   final int depth,
                                   double alpha,
                                   double beta) {
        bestMoveState = null;
        
        // The first turn belongs to AI/the maximizing player:
        double tentativeValue = Double.NEGATIVE_INFINITY;
        
        for (final S child : root.expand(PlayerType.MAXIMIZING_PLAYER)) {
            double value = alphaBetaImpl(child,
                                         depth - 1,
                                         Double.NEGATIVE_INFINITY,
                                         Double.POSITIVE_INFINITY,
                                         PlayerType.MINIMIZING_PLAYER);
            
            if (tentativeValue < value) {
                tentativeValue = value;
                bestMoveState = child;
            }
            
            if (value > beta) {
                break;
            }

            alpha = Math.max(alpha, value);
        }
    }
    
    private double alphaBetaImpl(final S state,
                                 final int depth, 
                                 double alpha,
                                 double beta,
                                 final PlayerType playerType) {
        
        if (depth == 0 || state.isTerminal()) {
            return heuristicFunction.evaluate(state, depth);
        }
        
        if (playerType == PlayerType.MAXIMIZING_PLAYER) {
            double value = Double.NEGATIVE_INFINITY;
            
            for (final S child : state.expand(playerType)) {
                value = Math.max(
                        value,
                        alphaBetaImpl(
                                child, 
                                depth - 1,
                                alpha,
                                beta,
                                PlayerType.MINIMIZING_PLAYER));
                
                if (value > beta) {
                    break;
                }
                
                alpha = Math.max(alpha, value);
            }
                
            return value;
        } else {
            double value = Double.POSITIVE_INFINITY;
            
            for (final S child : state.expand(playerType)) {
                value = Math.min(
                        value, 
                        alphaBetaImpl(
                                child, 
                                depth - 1, 
                                alpha, 
                                beta, 
                                PlayerType.MAXIMIZING_PLAYER));
                
                if (value < alpha) {
                    break;
                }
                
                beta = Math.min(beta, value);
            }
            
            return value;
        }
    }   
}

com.github.coderodde.game.connect4.ConnectFour.java:

package com.github.coderodde.game.connect4;

import com.github.coderodde.game.zerosum.HeuristicFunction;
import com.github.coderodde.game.zerosum.PlayerType;
import com.github.coderodde.game.zerosum.impl.AlphaBetaPruningSearchEngine;
import java.util.Scanner;
import com.github.coderodde.game.zerosum.SearchEngine;

/**
 * This class implements the REPL for playring Connect Four against an AI bot.
 * 
 * @version 1.0.0 (Jun 5, 2024)
 * @since 1.0.0 (Jun 5, 2024)
 */
public class ConnectFour {
    
    private static final double MINIMUM_PLAYER_VICTORY_SCORE = +1E6;
    private static final double MAXIMUM_PLAYER_VICTORY_SCORE = -1E6;
    private static final int DEFAULT_DEPTH = 8;
    private static final int MINIMUM_DEPTH = 1;

    public static void main(String[] args) {
        final int depth = parseDepth(args);
        
        System.out.printf(">>> Using search depth: %d.\n", depth);
        
        final Scanner scanner = new Scanner(System.in);
        final HeuristicFunction<ConnectFourBoard> heuristicFunction = 
                new ConnectFourHeuristicFunction();
        
        final SearchEngine<ConnectFourBoard> bot = 
                new AlphaBetaPruningSearchEngine<>(
                        heuristicFunction, 
                        MINIMUM_PLAYER_VICTORY_SCORE, 
                        MAXIMUM_PLAYER_VICTORY_SCORE);
        
        ConnectFourBoard currentBoard = new ConnectFourBoard();
        
        while (true) {
            System.out.println(currentBoard);
            
            final String command = scanner.next().trim();
            
            if (command.equals("quit") || command.equals("q")) {
                return;
            }
            
            int column;
            
            try {
                column = Integer.parseInt(command);
            } catch (final NumberFormatException ex) {
                System.out.printf(">>> Command \"%s\" not recognized.\n",
                                  command);
                continue;
            }
            
            if (0 < column && column <= ConnectFourBoard.COLUMNS) {
                column--; // 1-based indexing to 0-based.
                
                currentBoard = 
                        currentBoard.makePly(
                                column,
                                PlayerType.MINIMIZING_PLAYER);
                
                long startTime = System.currentTimeMillis();
                
                final ConnectFourBoard nextConnectFourBoard = 
                        bot.search(currentBoard, depth);
                
                long endTime = System.currentTimeMillis();
                
                System.out.printf(">>> AI took %d milliseconds.\n",
                                  endTime - startTime);
                
                if (nextConnectFourBoard != null) {
                    currentBoard = nextConnectFourBoard;
                }
                
                if (currentBoard.isWinningFor(PlayerType.MINIMIZING_PLAYER)) {
                    System.out.println(">>> You won!");
                    System.out.println(currentBoard);
                    return;
                }
                
                if (currentBoard.isWinningFor(PlayerType.MAXIMIZING_PLAYER)) {
                    System.out.println(">>> AI won!");
                    System.out.println(currentBoard);
                    return;
                }
                
                if (currentBoard.isTie()) {
                    System.out.println(">>> It's a tie!");
                    System.out.println(currentBoard);
                    return;
                }
                
                System.out.println(">>> Board after AI's move:");
            }
        }
    }
    
    /**
     * Attempts to read the search depth from the {@code args}. If not present,
     * returns the default depth.
     * 
     * @param args the array of command line arguments.
     * 
     * @return the search depth to use.
     */
    private static int parseDepth(final String[] args) {
        if (args.length == 0) {
            return DEFAULT_DEPTH;
        }
        
        int depth;
        
        try {
            depth = Integer.parseInt(args[0]);
        } catch (final NumberFormatException ex) {
            return DEFAULT_DEPTH;
        }
        
        return Math.max(depth, MINIMUM_DEPTH);
    }
}

com.github.coderodde.game.connect4.ConnectFourBoard.java:

package com.github.coderodde.game.connect4;

import com.github.coderodde.game.zerosum.PlayerType;
import com.github.coderodde.game.zerosum.GameState;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * This class implements a board that corresponds to a game state in the game
 * search tree.
 * 
 * @version 1.0.0 (Jun 5, 2024)
 * @since 1.0.0 (Jun 5, 2024)
 */
public class ConnectFourBoard implements GameState<ConnectFourBoard> {

    static final int ROWS = 6;
    static final int COLUMNS = 7;
    static final int VICTORY_LENGTH = 4;
    
    final PlayerType[][] boardData = new PlayerType[ROWS][COLUMNS];
    
    public ConnectFourBoard(final PlayerType[][] boardData) {
        for (int y = 0; y < ROWS; y++) {
            this.boardData[y] = Arrays.copyOf(boardData[y], COLUMNS);
        }
    }
    
    public ConnectFourBoard() {
        
    }
    
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        
        for (int y = 0; y < ROWS; y++) {
            // Build the row:
            for (int x = 0; x < COLUMNS; x++) {
                sb.append("|");
                sb.append(getCellChar(boardData[y][x]));
            }
            
            sb.append("|\n");
        }
        
        sb.append("+-+-+-+-+-+-+-+\n");
        sb.append(" 1 2 3 4 5 6 7");
        
        return sb.toString();
    }
    
    @Override
    public List<ConnectFourBoard> expand(final PlayerType playerType) {
        final List<ConnectFourBoard> children = new ArrayList<>(COLUMNS);
        
        for (int x = 0; x < COLUMNS; x++) {
            if (notFullAtX(x)) {
                children.add(dropAtX(x, playerType));
            }
        }
        
        return children;
    }
    
    @Override
    public boolean isWinningFor(final PlayerType playerType) {
        if (isTerminalHorizontal(playerType)) {
            return true;
        }
        
        if (isTerminalVertical(playerType)) {
            return true;
        }
        
        if (isTerminalAscendingDiagonal(playerType)) {
            return true;
        }
        
        if (isTerminalDescendingDiagonal(playerType)) {
            return true;
        }
        
        return false;
    }
    
    @Override
    public boolean isTie() {
        for (int x = 0; x < COLUMNS; x++) {
            if (boardData[0][x] == null) {
                return false;
            }
        }
        
        return true;
    }
    
    
    
    public ConnectFourBoard makePly(final int x, final PlayerType playerType) {
        return dropAtX(x, playerType);
    }
    
    private boolean isTerminalHorizontal(final PlayerType playerType) {
        int lastX = COLUMNS - VICTORY_LENGTH;
        
        for (int y = ROWS - 1; y >= 0; y--) {
            horizontalCheck:
            for (int x = 0; x <= lastX; x++) {
                for (int i = x; i < x + VICTORY_LENGTH; i++) {
                    if (boardData[y][i] != playerType) {
                        continue horizontalCheck;
                    }
                }
                
                return true;
            }
        }
        
        return false;
    }
    
    private boolean isTerminalVertical(final PlayerType playerType) {
        int lastY = ROWS - VICTORY_LENGTH;
        
        for (int x = 0; x < COLUMNS; x++) {
            verticalCheck:
            for (int y = 0; y <= lastY; y++) {
                for (int i = y; i < y + VICTORY_LENGTH; i++) {
                    if (boardData[i][x] != playerType) {
                        continue verticalCheck;
                    }
                }
                
                return true;
            }
        }
        
        return false;
    }
    
    private boolean isTerminalAscendingDiagonal(final PlayerType playerType) {
        int lastX = COLUMNS - VICTORY_LENGTH;
        int lastY = ROWS - VICTORY_LENGTH + 1;
        
        for (int y = ROWS - 1; y >= lastY; y--) {
            diagonalCheck:
            for (int x = 0; x <= lastX; x++) {
                for (int i = 0; i < VICTORY_LENGTH; i++) {
                    if (boardData[y - i][x + i] != playerType) {
                        continue diagonalCheck;
                    }
                }
                
                return true;
            }
        }
        
        return false;
    }
    
    private boolean isTerminalDescendingDiagonal(final PlayerType playerType) {
        int lastX = VICTORY_LENGTH - 1;
        int lastY = ROWS - VICTORY_LENGTH + 1;
        
        for (int y = ROWS - 1; y >= lastY; y--) {
            diagonalCheck:
            for (int x = lastX; x < COLUMNS; x++) {
                for (int i = 0; i < VICTORY_LENGTH; i++) {
                    if (boardData[y - i][x - i] != playerType) {
                        continue diagonalCheck;
                    }
                }
                
                return true;
            }
        }
        
        return false;
    }
    
    private boolean notFullAtX(final int x) {
        return boardData[0][x] == null;
    }
    
    private ConnectFourBoard dropAtX(final int x, final PlayerType playerType) {
        final ConnectFourBoard nextBoard = new ConnectFourBoard();
        
        for (int y = 0; y < ROWS; y++) {
            nextBoard.boardData[y] = Arrays.copyOf(this.boardData[y], COLUMNS);
        }
        
        for (int y = ROWS - 1; y >= 0; y--) {
            if (nextBoard.boardData[y][x] == null) {
                nextBoard.boardData[y][x] = playerType;
                return nextBoard;
            }
        }
        
        throw new IllegalStateException("Should not get here.");
    }
    
    private static char getCellChar(final PlayerType playerType) {
        if (playerType == null) {
            return '.';
        }
        
        switch (playerType) {
            case MAXIMIZING_PLAYER:
                return 'O';
                
            case MINIMIZING_PLAYER:
                return 'X';
                
            default:
                throw new IllegalStateException("Should not get here.");
        }
    }
}

com.github.coderodde.game.connect4.ConnectFourHeuristicFunction.java:

package com.github.coderodde.game.connect4;

import static com.github.coderodde.game.connect4.ConnectFourBoard.COLUMNS;
import static com.github.coderodde.game.connect4.ConnectFourBoard.ROWS;
import com.github.coderodde.game.zerosum.HeuristicFunction;
import com.github.coderodde.game.zerosum.PlayerType;

/**
 * This class implements a heuristic function for the Connect Four game.
 * 
 * @version 1.0.0 (Jun 5, 2024)
 * @since 1.0.0 (Jun 5, 2024)
 */
public final class ConnectFourHeuristicFunction 
        implements HeuristicFunction<ConnectFourBoard> {
    
    private static final double TWO_BLOCKS_SCORE = 1.0;
    private static final double THREE_BLOCKS_SCORE = 10.0;
    private static final double MINIMIZING_PLAYER_VICTORY_SCORE = -10E6;
    private static final double MAXIMIZING_PLAYER_VICTORY_SCORE = +10E6;

    @Override
    public double evaluate(final ConnectFourBoard state, final int depth) {
        if (state.isWinningFor(PlayerType.MINIMIZING_PLAYER)) {
            return MINIMIZING_PLAYER_VICTORY_SCORE + depth;
        }
        
        if (state.isWinningFor(PlayerType.MAXIMIZING_PLAYER)) {
            return MAXIMIZING_PLAYER_VICTORY_SCORE - depth;
        }
        
        return evaluate2(state) + evaluate3(state);
    }
    
    private static double evaluate2(final ConnectFourBoard state) {
        return evaluate2Horizontal(state) +
               evaluate2Vertical(state) + 
               evaluate2Ascending(state) +
               evaluate2Descending(state);
    }
    
    private static double evaluate3(final ConnectFourBoard state) {
        return evaluate3Horizontal(state) +
               evaluate3Vertical(state) + 
               evaluate3Ascending(state) +
               evaluate3Descending(state);
    }
    
    private static double evaluate2Horizontal(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = 0; y < ROWS; y++) {
            for (int x = 0; x < COLUMNS - 1; x++) {
                if (state.boardData[y][x] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y][x + 1] == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += TWO_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y][x + 1] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= TWO_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate2Vertical(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = 0; y < ROWS - 1; y++) {
            for (int x = 0; x < COLUMNS; x++) {
                if (state.boardData[y][x] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y + 1][x] == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += TWO_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y + 1][x] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= TWO_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate2Ascending(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = ROWS - 1; y > 0; y--) {
            for (int x = 0; x < COLUMNS - 1; x++) {
                if (state.boardData[y][x] 
                        == PlayerType.MAXIMIZING_PLAYER 
                        &&
                    state.boardData[y - 1][x + 1] 
                        == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += TWO_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y - 1][x + 1] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= TWO_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate2Descending(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = ROWS - 1; y > 0; y--) {
            for (int x = 1; x < COLUMNS; x++) {
                if (state.boardData[y][x] 
                        == PlayerType.MAXIMIZING_PLAYER 
                        &&
                    state.boardData[y - 1][x - 1] 
                        == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += TWO_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y - 1][x - 1] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= TWO_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate3Horizontal(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = 0; y < ROWS; y++) {
            for (int x = 0; x < COLUMNS - 2; x++) {
                if (state.boardData[y][x] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y][x + 1] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y][x + 2] == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += THREE_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y][x + 1] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y][x + 2]
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= THREE_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate3Vertical(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = 0; y < ROWS - 2; y++) {
            for (int x = 0; x < COLUMNS; x++) {
                if (state.boardData[y][x] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y + 1][x] == PlayerType.MAXIMIZING_PLAYER &&
                    state.boardData[y + 2][x] == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += THREE_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y + 1][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y + 2][x] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= THREE_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate3Ascending(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = ROWS - 1; y > 1; y--) {
            for (int x = 0; x < COLUMNS - 2; x++) {
                if (state.boardData[y][x] 
                        == PlayerType.MAXIMIZING_PLAYER 
                        &&
                    state.boardData[y - 1][x + 1] 
                        == PlayerType.MAXIMIZING_PLAYER
                        &&
                    state.boardData[y - 2][x + 2] 
                        == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += THREE_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y - 1][x + 1] 
                        == PlayerType.MINIMIZING_PLAYER
                        && 
                        state.boardData[y - 2][x + 2] 
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= THREE_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
    
    private static double evaluate3Descending(final ConnectFourBoard state) {
        double sum = 0.0;
        
        for (int y = ROWS - 1; y > 1; y--) {
            for (int x = 2; x < COLUMNS; x++) {
                if (state.boardData[y][x] 
                        == PlayerType.MAXIMIZING_PLAYER 
                        &&
                    state.boardData[y - 1][x - 1] 
                        == PlayerType.MAXIMIZING_PLAYER
                        &&
                    state.boardData[y - 2][x - 2] 
                        == PlayerType.MAXIMIZING_PLAYER) {
                    
                    sum += THREE_BLOCKS_SCORE;
                } else if (state.boardData[y][x] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y - 1][x - 1] 
                        == PlayerType.MINIMIZING_PLAYER
                        &&
                        state.boardData[y - 2][x - 2]
                        == PlayerType.MINIMIZING_PLAYER) {
                    
                    sum -= THREE_BLOCKS_SCORE;
                }
            }
        }
        
        return sum;
    }
}

My game experience

My AI seems to be rather competitive:

>>> Using search depth: 8.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
4
>>> AI took 1008 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|O|.|X|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
4
>>> AI took 787 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
4
>>> AI took 593 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
6
>>> AI took 672 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|.|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
2
>>> AI took 963 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|.|O|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|.|.|.|
|.|O|.|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
5
>>> AI took 1185 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|.|O|.|.|.|
|.|O|.|X|O|.|.|
|.|O|.|X|X|.|.|
|.|O|.|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
6
>>> AI took 1363 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|.|O|.|.|.|
|.|O|.|X|O|O|.|
|.|O|.|X|X|X|.|
|.|O|.|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
5
>>> AI took 745 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|.|O|X|.|.|
|.|O|.|X|O|O|.|
|.|O|.|X|X|X|.|
|O|O|.|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
3
>>> AI took 417 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|.|O|X|.|.|
|.|O|.|X|O|O|.|
|.|O|O|X|X|X|.|
|O|O|X|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
3
>>> AI took 460 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|X|O|O|X|.|.|
|.|O|X|X|O|O|.|
|.|O|O|X|X|X|.|
|O|O|X|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
4
>>> AI took 523 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|.|O|X|.|.|.|
|.|X|O|O|X|.|.|
|.|O|X|X|O|O|.|
|.|O|O|X|X|X|.|
|O|O|X|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
1
>>> AI took 188 milliseconds.
>>> Board after AI's move:
|.|.|.|.|.|.|.|
|.|O|O|X|.|.|.|
|.|X|O|O|X|.|.|
|.|O|X|X|O|O|.|
|X|O|O|X|X|X|.|
|O|O|X|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
3
>>> AI took 26 milliseconds.
>>> AI won!
|.|O|X|.|.|.|.|
|.|O|O|X|.|.|.|
|.|X|O|O|X|.|.|
|.|O|X|X|O|O|.|
|X|O|O|X|X|X|.|
|O|O|X|X|O|X|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7

Critique request

Please, tell me anything that comes to mind. Especially, I would like to hear whether my Alpha-beta pruning is correctly implemented. Also, perhaps you could comment on the heuristic function.

\$\endgroup\$
6
  • \$\begingroup\$ Is makePly a typo for makePlay? \$\endgroup\$
    – Toby Speight
    Commented Jun 6 at 6:04
  • 2
    \$\begingroup\$ @TobySpeight I assume it's en.wikipedia.org/wiki/Ply_(game_theory) \$\endgroup\$
    – ggorlen
    Commented Jun 6 at 16:27
  • \$\begingroup\$ Thanks @ggorlen. \$\endgroup\$
    – Toby Speight
    Commented Jun 6 at 16:38
  • 1
    \$\begingroup\$ For the heuristic, I have had success in the past by not necessarily looking for 3 pieces in a row, but rather looking for 4 consecutive spots in a row that contain only your pieces and empty spaces. e.g. |X|X|.|X|.|.|.| is just as much of a threat as |X|X|X|.|.|.|.|. Specifically, I iterate through all sequences of 4 spots, and assign them a score of 0 if they contain pieces from both players (since that means neither of them can score there), or a positive/negative score for my/opponent's pieces, with magnitude exponentially relative to the number of pieces. \$\endgroup\$
    – The Guy with The Hat
    Commented Jun 7 at 0:04
  • \$\begingroup\$ @TheGuywithTheHat that comment is a great observation, and really deserves to be an answer in itself - perhaps exactly as you wrote that. A review doesn't need to be long to be valuable and worthy of upvotes. \$\endgroup\$
    – Toby Speight
    Commented Jun 7 at 7:47

3 Answers 3

Reset to default
4
\$\begingroup\$

I don't have time right now for a full review (and my Java is 20 years out of date anyway), but I do think we could improve the structure somewhat.

At present, the human player is tightly coupled into the main() function. Consider extracting the interaction so that a console player has the same interface as the machine player, making it easier to support alternative configurations - we might like to pit two algorithms against each other, or to host a human-to-human game (perhaps implementing a GUI or network interface for one or both players).

One other thing does jump out. The array-of-arrays board representation means you need separate functions to assess horizontal, vertical and leading/trailing diagonal lines. This becomes much simpler if we use a simple array to store a rasterised representation (so that instead of array[row][col] we use array[row * width + col] - obviously we could write an accessor function to simplify). With that modification, lines of cells are reached from an initial index simply by adding 1 (horizontal), width (vertical), width + 1 (leading diagonal) or width - 1 (trailing diagonal), so we can have a single function that can be used with different stride values.

If you do this, do take care to correctly identify the valid start points for all directions (particularly the diagonals).

We shouldn't need separate functions for rows of 2, 3 and 4 - pass the length value as a parameter and return the number of instances found - the caller can then convert to a heuristic score based on that.

I don't see any unit tests. If we had good unit tests, particularly of the low-level run-counting functions, then that would help us refactor the code with confidence to reduce the duplication and make the code easier to maintain. Remember the test-driven development cycle - Red ⟶ Green ⟶ Reduce.

\$\endgroup\$
3
  • \$\begingroup\$ Nice one! Also, could you comment on ConnectFourHeuristicFunction.evaluate()? Do I add/subtract depth correctly? \$\endgroup\$
    – coderodde
    Commented Jun 6 at 9:20
  • \$\begingroup\$ I see nothing obviously incorrect - but as I said, I'm very rusty in this language. \$\endgroup\$
    – Toby Speight
    Commented Jun 6 at 12:14
  • 1
    \$\begingroup\$ @coderodde Adding or subtracting depth doesn't really matter there, right? It looks like just a polite way for the AI to prefer a short forced win over a long forced win if it finds two of them. \$\endgroup\$
    – amalloy
    Commented Jun 6 at 20:58
4
\$\begingroup\$

Heuristic

For the heuristic, I have had success in the past by not necessarily looking for 3 consecutive pieces, but rather looking for partially complete sequences of 4. For example, the row |X|X|.|X|.|.|.| is just as much of a threat as |X|X|X|.|.|.|.|, and probably deserves to be scored similarly. The former only has 2 consecutive pieces, but both rows have exactly one open spot that player X can fill to get 4 consecutive.

Specifically, I iterate through all sequences of 4 spots (in a 7x6 board there are always 24 horizontal, 21 vertical, and 24 diagonal), and assign each a score based on what it contains. If the sequence contains pieces from both player X and O, neither of them can win there, so it is given a score of 0. If it contains pieces from only one player, then we can assign it a score based on how much of a threat it is: 1 X and 3 empties is a pretty small threat, 2 Xs and 2 empties is a medium threat, and 3 Xs and 1 empty is quite a large threat.

By taking the sum of the scores of each line where a player could win, with positive score for X and negative for O, we get a pretty good evaluation of how good the board state is for player X.

\$\endgroup\$
2
\$\begingroup\$

Algorithm Feedback

You have chosen to make the game state immutable. This makes the code referentially transparent and therefore easy to reason about, but it also causes a quite significant part of the runtime to be spent copying board states.

The alternative would be a mutable game state. This would be harder to implement correctly, as you would have to do and undo moves when entering/leaving a recursion step, but it would allow you to reuse most of the board state, and also most of the heuristic evaluation, as you walk the tree of possible moves, allowing a deeper recursion, and therefore a stronger AI, at the same computational expense.

Which of these approaches is better would likely require some benchmarking. For a game with a comparatively small game state, an immutable state might be fast enough.

Minmax vs Negamax

Minmax requires separate branches for the maximizing and minimizing player. An often used implementation trick that avoids this is the Negamax algorithm.

Heuristic Function

The heuristic function is very readable, but also very copy-pastey. In particular, having wholly separate methods for each combination of length and direction seems very redundant. Now, I realize that abstracting over direction is a bit hard (though possible), but surely you could take care of all lengths in the same method? Something like:

char last = ' ';
int runLength = 0;
for (char x : line) {
  if (x == last) {
    runLength++;
  } else {
    score += value[runLength] * playerSign(last);
    
    last = x;
    runLength = 1;
  }
}

Btw, your heuristic function sees value in runs that can never be completed. For instance, if we have a run like OXX O, it thinks XX promising, even though there isn't enough room to complete XXXX. It may be better to look at each homogeneous 4 tuple. This would also recognize XX X as having just as much potential as XXX .

Decomposition

Overall, I like the way you break down the problem into smaller and smaller parts, who have clear names and communicate through expressive method calls and immutable data types.

However, sometimes the top-down decomposition style makes you miss commonalities in the implementation that you could have exploited to reuse code and reduce the overall size of your program. For instance, you have separated the check for victory and the check for near-victories into separate methods of separate classes, since one is called as part of checking for victory, while the other is called as part of the heuristic evaluation. However, the actual implementation is very similar. In both cases, we are casting rays through the grid, and seek uninterrupted runs of like-colored pieces. That is, I would have identified this ray-casting-and-run-counting as a concern of its own, implemented that once, and used it for both victory-checking and heuristic evaluation.

\$\endgroup\$
2
  • \$\begingroup\$ See my answer for how to abstract over directions. I've implemented such a thing sometime in the last few years (albeit it in C++); however, I've completely forgotten what it was for, so I'm not able to dig it up - sorry! \$\endgroup\$
    – Toby Speight
    Commented Jun 7 at 7:38
  • \$\begingroup\$ I meant to explicitly mention your last point about run-length 4 check being basically the same as the run-length 3/2 checks, but forgot to do so, leaving it implicit. They should all be condensed into a single parameterised function, probably a member of the board class. Thank you for drawing attention to that better than I managed! \$\endgroup\$
    – Toby Speight
    Commented Jun 7 at 7:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.