colinlefter / monte-carlo-tree-search-amazons Goto Github PK

An advanced AI game playing agent for the Game of the Amazons leveraging a custom Monte Carlo Tree Search algorithm alongside the UCT heuristic. Built as part of the course project for COSC 322 at UBC.

Java 100.00%

monte-carlo-tree-search-amazons's Introduction

COSC-322-Group-Project

monte-carlo-tree-search-amazons's People

Contributors

Stargazers

Watchers

monte-carlo-tree-search-amazons's Issues

uctValue

public class UCT {
    public static double uctValue(
      int totalVisit, double nodeWinScore, int nodeVisit) {
        if (nodeVisit == 0) {
            return Integer.MAX_VALUE;
        }
        return ((double) nodeWinScore / (double) nodeVisit) 
          + 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit);
    }

    public static Node findBestNodeWithUCT(Node node) {
        int parentVisit = node.getState().getVisitCount();
        return Collections.max(
          node.getChildArray(),
          Comparator.comparing(c -> uctValue(parentVisit, 
            c.getState().getWinScore(), c.getState().getVisitCount())));
    }
}

findNextMove

public class MonteCarloTreeSearch {
    static final int WIN_SCORE = 10;
    int level;
    int opponent;

    public Board findNextMove(Board board, int playerNo) {
        // define an end time which will act as a terminating condition

        opponent = 3 - playerNo;
        Tree tree = new Tree();
        Node rootNode = tree.getRoot();
        rootNode.getState().setBoard(board);
        rootNode.getState().setPlayerNo(opponent);

        while (System.currentTimeMillis() < end) {
            Node promisingNode = selectPromisingNode(rootNode);
            if (promisingNode.getState().getBoard().checkStatus() 
              == Board.IN_PROGRESS) {
                expandNode(promisingNode);
            }
            Node nodeToExplore = promisingNode;
            if (promisingNode.getChildArray().size() > 0) {
                nodeToExplore = promisingNode.getRandomChildNode();
            }
            int playoutResult = simulateRandomPlayout(nodeToExplore);
            backPropogation(nodeToExplore, playoutResult);
        }

        Node winnerNode = rootNode.getChildWithMaxScore();
        tree.setRoot(winnerNode);
        return winnerNode.getState().getBoard();
    }
}

simulatedGameTest

@Test
void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw() {
    Board board = new Board();
    int player = Board.P1;
    int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE;
    for (int i = 0; i < totalMoves; i++) {
        board = mcts.findNextMove(board, player);
        if (board.checkStatus() != -1) {
            break;
        }
        player = 3 - player;
    }
    int winStatus = board.checkStatus();
 
    assertEquals(winStatus, Board.DRAW);
}

Lab 01 (Warmup 1) Procedure

About the project

The template project provided is a Maven project. Maven is a build automation tool used primarily for Java projects. That means the project has dependencies that need to be installed in order to interact with the project files and utilize the ygraph.ai.smartfox.games API. In order to do that, you need to:

Part 1: Install Apache Maven

Install Apache Maven from the Apache Maven Project website
Unzip the downloaded archive to a directory on your system, for example, C:\apache-maven.
Add Maven to the PATH

Part 1.1: Adding Maven to the PATH:

Windows:

Right-click on 'This PC' or 'My Computer' and choose 'Properties'.
Click on 'Advanced system settings'.
In the 'System Properties' window, click on the 'Environment Variables' button.
In the 'Environment Variables' window, select the 'Path' variable in the 'System variables' section and click 'Edit'.
Add the path to the bin directory of the Maven installation (e.g., C:\apache-maven\bin) to the list of values.
Click 'OK' to close all dialog boxes.
Open a new command prompt and type mvn -v to verify that Maven is correctly installed. It should display the Maven version, the Java version, and the path to the Java home.

MacOS

Download Maven:

Visit the Apache Maven Project website and download the latest Maven version. Choose the binary tar.gz archive (e.g., apache-maven-3.9.6-bin.tar.gz).
Extract the Archive: You can extract the tar.gz file using the terminal. Navigate to the directory where the downloaded file is located and use the tar command: tar -xvf apache-maven-3.9.6-bin.tar.gz. This will extract Maven into a folder like apache-maven-3.9.6.
Move Maven to a Permanent Location: You might want to move the Maven directory to a more permanent location. For example:
sudo mv apache-maven-3.9.6 /opt/ /opt/ is a common directory for this kind of software on Unix systems, but you can choose another location if you prefer.
Add Maven to the PATH: Right click on the bin folder in the apache-maven-3.9.6 folder, hold option and select copy "bin" as path name. Then, open your terminal and enter open -e ~/.zshrc. In that file, paste the following:

path=('input_path_to_bin_folder' $path)
export PATH

Reload Your Shell Configuration: Close and reopen your terminal.
Verify Installation: To check if Maven was installed successfully, open a new terminal window and run: mvn -v. This should display the installed version of Maven, along with the Java version and the path to the Java home. Remember, the file you need to edit (~/.bash_profile, ~/.bashrc, ~/.zshrc, etc.) depends on the shell you are using. If you're using a recent version of macOS, it's likely using Zsh by default, so you would edit ~/.zshrc instead of ~/.bash_profile.

Part 2: After Setting up Maven

In the project's root directory, run mvn clean install
Compile and run the project: run mvn exec:java -D"exec.mainClass=ubc.cosc322.COSC322Test" -D"exec.args=testRunG4 testG4"

For subsequent tests: After making changes anywhere in the project, run mvn compile and then the command listed in step 2 above

Note: the segment D"exec.args=testRunG4 testG4" requires two parameters--a username and password, but these can be anything for now.

Project Resources

NOTE: You must be connected to UBC wifi or use the UBC VPN for the connection to the server to be successful.

Insights from Games

Competition bot (last stable release:

The crash happens whenever a queen gets replaced with an arrow (i.e. an arrow is shot at a queen)
Likely happening when a queen is completely boxed except for being able to move diagonally (often times when a queen is completely boxed but one tile where it can move diagonally)

Experimental bot (Jarod + Colin):

A new MCTS was being created on each move as we added the object under send move
Both MAX_DEPTH and UPPER_TIME_LIMIT have no influence on the duration of a move

Board functionality

Class variables
performMove
checkStatus
getEmptyPositions

public class Board {
    int[][] boardValues;
    public static final int DEFAULT_BOARD_SIZE = 3;
    public static final int IN_PROGRESS = -1;
    public static final int DRAW = 0;
    public static final int P1 = 1;
    public static final int P2 = 2;
    
    // getters and setters
    public void performMove(int player, Position p) {
        this.totalMoves++;
        boardValues[p.getX()][p.getY()] = player;
    }

    public int checkStatus() {
        /* Evaluate whether the game is won and return winner.
           If it is draw return 0 else return -1 */         
    }

    public List<Position> getEmptyPositions() {
        int size = this.boardValues.length;
        List<Position> emptyPositions = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (boardValues[i][j] == 0)
                    emptyPositions.add(new Position(i, j));
            }
        }
        return emptyPositions;
    }
}

simulateRandomPlayout

private int simulateRandomPlayout(Node node) {
    Node tempNode = new Node(node);
    State tempState = tempNode.getState();
    int boardStatus = tempState.getBoard().checkStatus();
    if (boardStatus == opponent) {
        tempNode.getParent().getState().setWinScore(Integer.MIN_VALUE);
        return boardStatus;
    }
    while (boardStatus == Board.IN_PROGRESS) {
        tempState.togglePlayer();
        tempState.randomPlay();
        boardStatus = tempState.getBoard().checkStatus();
    }
    return boardStatus;
}

findBestNodeWithUCT

public class UCT {
    public static double uctValue(
      int totalVisit, double nodeWinScore, int nodeVisit) {
        if (nodeVisit == 0) {
            return Integer.MAX_VALUE;
        }
        return ((double) nodeWinScore / (double) nodeVisit) 
          + 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit);
    }

    public static Node findBestNodeWithUCT(Node node) {
        int parentVisit = node.getState().getVisitCount();
        return Collections.max(
          node.getChildArray(),
          Comparator.comparing(c -> uctValue(parentVisit, 
            c.getState().getWinScore(), c.getState().getVisitCount())));
    }
}

backPropogation

private void backPropogation(Node nodeToExplore, int playerNo) {
    Node tempNode = nodeToExplore;
    while (tempNode != null) {
        tempNode.getState().incrementVisit();
        if (tempNode.getState().getPlayerNo() == playerNo) {
            tempNode.getState().addScore(WIN_SCORE);
        }
        tempNode = tempNode.getParent();
    }
}

MCTS Principles

Analyzes the most promising moves, expanding the search tree based on random sampling of the search space
Application is based no many playouts—in each playout, the game is played out to the very end by selecting moves at random
Final game result of each playout is then used to assign eights to the nodes in the game tree so that better nodes are more likely to be chosen in future playouts

Fix issues with board not syncing across AI/human boards

Running the HumanPlayer and AIPlayer in Isolation, in Parallel

Initial steps

If this is the first time you are using maven/have just cloned this project, be sure to run mvn install first.

Next steps

In Intellij, open up a new terminal and execute mvn compile. Then, right click on the terminal and select "Split Right". On the left terminal, run the HumanPlayer agent via the following:

mvn exec:java -D"exec.mainClass=ubc.cosc322.HumanPlayerTest" -D"exec.args=HumanPlayer humanPass"

In the right terminal, run the AI player agent via the following:

mvn exec:java -D"exec.mainClass=ubc.cosc322.AIPlayerTest" -D"exec.args=AIPlayer aiPass"

Implement random moves test

Current Issues and Findings

~~The board for the human player and the AI player should be flipped (i.e. if the human player is black, their queens should be at the bottom and the AI should have white queens at the bottom~~
1. This is actually a good thing as it is easier to see how things play out when the board is not mirrored
~~When initialising an AI player and a human player, when the human player starts by making a move, the board of the AI player is inconsistent with where the human has placed their queen~~
1. Now fixed
When the human player is initialised and it is time for them to make a move, they can keep making moves indefinitely (we need to somehow let the server know that they have completed their move and that it is time for the AI to make a move)
1. UPDATE: Turns out the AI has been making moves all along in response to the human player, but the board is just simply not being updated for the human player? In addition, when the human player makes a move, that move is visible for the human player but not for the AI player. Clearly the problem has something to do with the game board state not being updated correctly.

Deep look into issue 3

When the human player makes a move, the dart position gets rendered across both boards, but the moved human player's queen disappears on the AI's board. It is still there on the human's board.
Although it appears that the human player can keep making moves indefinitely, it turns out that the AI is making random moves after the human player makes a move (terminal shows that), but that the AI's moves are not being registered on the board (not being displayed)

selectPromisingNode

private Node selectPromisingNode(Node rootNode) {
    Node node = rootNode;
    while (node.getChildArray().size() != 0) {
        node = UCT.findBestNodeWithUCT(node);
    }
    return node;
}

Amazons Rules

Each Amazon can move like a chess queen
- Technical considerations: you need to define what a legal move is for your AI. Right now, the AI can actually move wherever as there is nothing blocking it from making an illegal move. We need to define those constraints. Approach: maintain 8 pointers to all 4 furthest edges that can be reached from the current position for each queen (while accounting for tiles that have been hit by arrows). That means each each queen has 8 pointers that are [x, y] pairs associated with it. When a queen makes a move, we need to update all 8 pointers by running a linear search until the edge of the board (or a burned tile) in a clockwise direction. We do this every time we need to make a move, as the board will be updated after the opponent makes a move
After the Amazon moves, it needs to fire an arrow. The arrow can also move like a chess queen. The square where the arrow lands is burned off the board. That square cannot be occupied and no amazon can go past it (jump over it)
- Technical considerations: the above legal moves check algorithm would account for burned tiles
The game ends when the opponent cannot move anywhere anymore. That player who is unable to move is the player that loses. OR the player who did the last legal move is the winner (if both of you end up being stuck, then the the player who last made a move wins)

expandNode

private void expandNode(Node node) {
    List<State> possibleStates = node.getState().getAllPossibleStates();
    possibleStates.forEach(state -> {
        Node newNode = new Node(state);
        newNode.setParent(node);
        newNode.getState().setPlayerNo(node.getState().getOpponent());
        node.getChildArray().add(newNode);
    });
}