42 project: Gomoku

AI bot that plays the game of Gomoku.

The goal of the project was to implement a bot that could beat human players at the game of Gomoku with additional rules of capture and no double free threes (cf. project description).
We implemented minimax, alpha-beta pruning, MTD-f and Monte Carlo Tree Search.
The main constraint was to use less than 0.5s per move. Given these constraints, the depth of our search tree can go up to 5-6 with the simplest heuristic or 2-3 with a more complex heuristic.

Quick Start

make

Try to Beat our Bot

python -m gomoku

Additional Arguments

  -h, --help            show this help message and exit
  -b BOARD, --board BOARD
                        Text file which represent a board state.
  -d, --debug           Enable terminal mode.
  -H HEURISTIC, --heuristic HEURISTIC
                        Heuristic function.
  -D {1,2,3,4,5,6,7,8,9,10}, --depth {1,2,3,4,5,6,7,8,9,10}
                        Depth of the search tree for Minimax Agents
  -p1 {human,minimax,alpha_beta,alpha_beta_memory,alpha_beta_basic,mtdf}, --player1 {human,minimax,alpha_beta,alpha_beta_memory,alpha_beta_basic,mtdf}
                        Choose Player 1 behaviour.
  -p2 {human,minimax,alpha_beta,alpha_beta_memory,alpha_beta_basic,mtdf}, --player2 {human,minimax,alpha_beta,alpha_beta_memory,alpha_beta_basic,mtdf}
                        Choose Player 2 behaviour.
  -s SCRIPT, --script SCRIPT
                        Text file to test sequence of moves.
  -c COMPETITION, --competition COMPETITION
                        Enable competition mode (max time to play).

Development Setup

make dev

The project uses PEP8 coding style and flake8 (see setup.cfg).

Unit tests

make test

Release History

0.1
- Project is mostly finished. MCTS bot is still in development, but alpha beta & mtdf work fine.

Authors

Michaël Trazzi – @MichaelTrazzi – mtrazzi@student.42.fr

Kevin Costa – @kcosta42 – kcosta@student.42.fr

License

Distributed under the MIT license. See LICENSE for more information.

Context

This project took roughly 200 pomodoros (~100h) between December 2019 and January 2020, as a coding project for the Algorithmic/AI branch of 42.

mtrazzi/gomoku