Giter Club home page Giter Club logo

estr-metasquares's Introduction

ESTR-MetaSquares - The Unbeatable AI (Maybe)

Sample game

A console-based AI for MetaSquares, a two-player game originally created by Scott Kim. This project was developed for the ESTR1002 course at CUHK.

The AI uprising is here, and it starts with MetaSquares. ๐Ÿค–

๐Ÿš€ How to build and run

  1. Execute the build task defined in tasks.json.
  2. Execute the run task defined in tasks.json.

It should be noted that the build task, by default, has -DR_LOCAL defined, which means that the program will run in local debug mode. To run the program in production mode, remove -DR_LOCAL from the build task.

๐ŸŽฎ How to play

  1. Choose a game mode: 1 for human vs human, 2 for human vs AI, 3 for AI vs Human.
  2. To make a move, enter the coordinates of the piece you want to place in the format xy, where x is the row number and y is the column number. For example, to place a piece at the bottom-left corner, enter 81.
  3. Players take turns placing a piece on the board. Blue goes first because, well, someone has to.
  4. Players earn points when they form the four corners of a square. The score is calculated by the area of the square. The squares can also be slanted, like your life choices.
  5. The game ends when a player scores more than 150 points and has at least 15 points more than the other player, or when the board is full.
  6. You can read the rules further online if you want, or don't; I am not your mom.

๐Ÿ’ช How to train the AI

  1. This program was tested on Python 3.12.0.

  2. Install the dependencies by running pip install -r requirements.txt.

  3. Make necessary changes to config.py to configure the training process.

  4. This project was configured to run on Google Compute Engine. The machine I used was c2d-highcpu-8. As of now, Google Compute provides $300 free credits for new users. Yay.

  5. Run start.sh on your Bash terminal to start the training process.

  6. The program logs the training progress to Google Logging, so you can keep track using the Google Cloud app. If you want, you can also set up logging alerts to notify you when the training is complete for a generation. Here are the log queries I used:

    resource.type="gce_instance"
    log_name="projects/{YOUR-PROJECT-NAME}/logs/Genetic_AI"
    textPayload=~"GENERATION (\d+) COMPLETE"
    
    resource.type="gce_instance"
    log_name="projects/{YOUR-PROJECT-NAME}/logs/Genetic_AI"
    textPayload=~"GENERATION (\d+) STARTED"
    
    resource.type="gce_instance"
    log_name="projects/{YOUR-PROJECT-NAME}/logs/Genetic_AI"
    severity="ERROR"
    
  7. Each generation dataset is dumped to the ./training_data folder. A stats.log file is also created, showing a sorted score of the AIs in the generation.

  8. To load a particular generation and resume training, change START_GENERATION in config.py to the generation number you want to load. The program will automatically load the most recent dump of that generation. At no point are the dumps ever overwritten. If you want to use an older training of the same generation, you can rename the recent dump, move it to another folder, or delete it. The last file in the below code is loaded:

    files = sorted(
            Path.glob(
                Path(config.TRANING_LOCATION),
                "gen_{}_dataset_[0-9]*.pickle".format(gen),
            )
        )
  9. A restart.bool file is also created when training starts. Changing the value of this file to true will restart the program after the current generation is complete. This is useful if you made changes to the repo and you want to update it when the generation ends, which can sometimes happen when you are asleep. This script resets and pulls the latest changes from the Git repo, so make sure you commit your changes you want to keep before restarting.

  10. To see the win-loss table, execute the Visualize.py script to visualize the training dump. The dump specified in config.py will be visualized.

๐Ÿง  AI strategies

1. ๐Ÿค Minimax

Minimax is a recursive algorithm used to find the best move for a player, assuming that the opponent plays optimally. It is a depth-first search algorithm that searches the entire game tree. As MetaSquares is a very complex game, one must imagine Sisyphus calculating ~64! possible games. Thus, we limit how far we search into the game by defining a maxDepth.

2. ๐Ÿง‘โ€๐ŸŒพ Alpha-beta pruning

Alpha-beta pruning is an optimization to the minimax algorithm. It prunes unnecessary branches in the game tree using a garden trimmer. I would suggest this video by Sebastian Lague to learn more.

3. ๐Ÿ“ˆ Heuristics

Heuristics are used to evaluate the board state. Each move is assigned a score based on the board state. Moves are then sorted by their score during the minimax algorithm, making the AB pruning more effective. Additionally, a strong heuristic allows the minimax algorithm to operate with a smaller branching factor, enabling deeper exploration of the game tree. (Branching factor is the number of moves evaluated at each node in the game tree) The following sections will explain the heuristics used in this project.

3.1 Possible Squares

This heuristic evaluates the number of possible squares that can be formed by the current player for each move. The opponents' pieces are excluded from the calculation. The more possible squares that can be formed by a move, the better.

3.2 Possible Score

This heuristic evaluates the score of all possible squares that can be formed by the current player for each move. The opponents' pieces are excluded from the calculation. The higher the score of the possible squares that can be formed by a move, the better.

3.3 Pattern Squares

This heuristic uses a mathematically proven pattern that gives the highest score in 20-24 moves of one player. Most games don't go on for that long. The research paper I used can be found here. In summary, a lattice structure of moves gives the highest score. Below is an illustration of the pattern:

Pattern

The image was collected from anysquare.de, which was mentioned in the research paper but has long been taken down. The image was collected using the Wayback Machine.

This heuristic calculates the number of squares that can be formed by the current player for each move in the pattern. The more squares that can be formed by a move, the better. The pattern is rotated to get the best score.

3.4 Pattern Score

This heuristic calculates the score of the squares that can be formed by the current player for each move in the pattern. The higher the score of the squares that can be formed by a move, the better. The pattern is rotated to get the best score.

3.5 My Squares

This heuristic calculates the squares that can be formed using existing pieces. The score is the number of pieces of the square already on the board, squared. i.e., if a square has 3 pieces completed and 1 piece missing, the missing piece gets a score of 9.

3.6 My score

This heuristic calculates the score of the squares that can be formed using existing pieces. The score is the score of the possible square, multiplied by the number of pieces of the square already on the board. i.e., if a square has 2 pieces completed and 2 pieces missing, and the area of the possible square is 4, the two missing pieces get a score of 4*2=8.

3.7 Opponent Squares

Same as above but for the opponent.

3.8 Opponent Score

Same as above but for the opponent.

3.9 Killer Heuristics

This heuristic is assigned when searching the game tree. Each score found calculated by the minimax algorithm is assigned to a table. The table can later be used to sort the moves. This is useful because the moves that have been deterministically calculated to have high scores can be evaluated before the "possible" good moves as calculated by the normal heuristics from above.

3.10 Killer Decay Constant

This constant is used to decay the killer heuristics table. The table is decayed by multiplying each score by this constant. This ensures that consistently good moves receive a high score, while moves that are good only in certain situations receive a lower score.

3.11 Depth

This is the depth of the minimax algorithm. The higher the depth, the more moves are evaluated. A high depth means the AI plays like Hikaru.

3.12 Dlogb Constant

This is the time constant. The complexity of the bottleneck (the minimax algorithm) is O(b^d), where b is the branching factor and d is the depth. Decreasing this constant means that the AI will take less time to make a move, but it also means it will evaluate fewer moves.

4. ๐Ÿงฌ Genetic Algorithm

The genetic algorithm is used to train the AI. The AI is represented by a list of weights, indicating the importance of each heuristic. The genetic algorithm finds the best weights for the AI. I suggest watching the two video series by Code Bullet to better understand this algorithm: Part 1 and Part 2.

๐Ÿƒโ€โ™‚๏ธ Performance

The AI has been tested against the following AIs:

  1. Pencil and Paper Games MetaSquares AI
  2. Metasquarer build 73
  3. AnySquare 0.925 - collected from the Wayback Machine
  4. MetaGenius - using default settings. I am not entirely sure how the program works; it seems that you can train the AI in this program. So it may not be a fair comparison as the AI may not be trained.
  5. Squares - The New MetaSquares Game

These are all the AIs that I was able to find, and my AI beat all of them every time. I also placed first in the AI tournament held by the course :)

๐Ÿ”ฎ Future of the Project

This AI is nowhere near perfect and is definitely beatable, but it is already very strong and beat all of the AIs I was able to find. So it may be safe to say that it is currently the best AI to date (because the rest are outdated due to a lack of popularity of the game hehe). So, I currently don't have a motivation to keep working on this project as of now. You may try to beat it yourself and let me know if you are able to do so :) Feel free to open an issue or make pull requests if you have any questions or suggestions. I personally will probably not be working on this project anymore, but I will try to answer any questions you may have.

estr-metasquares's People

Contributors

fieryrms avatar

Stargazers

 avatar Ray_Amidst avatar  avatar  avatar

Watchers

 avatar

estr-metasquares's Issues

restart.bool doesnt work like i thought it would

expected:
when restart.bool is set to true, the python stops execution, restart.sh pulls origin and executes start.sh to start the program

observed:
the file does pull and restart, but the nohup.out file is not created when start.sh is run, thus I cannot see live logs unless its through google logging.

KillerHeuristics implementation wrong

The AI doesnt seem to prefer having a high weight for killerheuristics like i expected it to. Most probably the implementation is wrong. Or maybe it doesnt make any difference in the training.

breeding method 1 not giving strong AIs

seeing the visualization, you can see that breeding method one is performing terribly, need to find a better way to breed. I found out so late that it would not be worth the effort to fix anymore.

AI training never seems to settle on a particular Weight

None of the AIs in any generation were able to beat all of the AIs. The weights of the top AI change dramatically in a span of 2-3 generations, and often its an AI you wouldn't expect to perform well. Then in the following generation, that AI is suddenly performing very bad. I expected the AIs to eventually settle at a well rounded AI who is able to get draws against stronger AIs.

My suspicions is that the AIs may have developed a couple of strategies, and each strategy can beat one other, but not every strategy, a non-transitive relationship, much like rock paper scissors. So as the number of one strategy increases, another strategy then beat all those AIs and gets a high position. A visual example could be this meme.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.