Implementation of an Connect-Four AI using the MCTS algorithm.
The installation pre-requisites are as follows:
As explained here, on Linux the xcb platform plugin is used. It provides basic features to run against X11. To install the following development libraries run the following command::
sudo apt-get install libfontconfig1-dev libfreetype6-dev libx11-dev libx11-xcb-dev libxext-dev libxfixes-dev libxi-dev libxrender-dev libxcb1-dev libxcb-cursor-dev libxcb-glx0-dev libxcb-keysyms1-dev libxcb-image0-dev libxcb-shm0-dev libxcb-icccm4-dev libxcb-sync-dev libxcb-xfixes0-dev libxcb-shape0-dev libxcb-randr0-dev libxcb-render-util0-dev libxcb-util-dev libxcb-xinerama0-dev libxcb-xkb-dev libxkbcommon-dev libxkbcommon-x11-devTo compile this project with the tests and the game itself execute the following commands:
mkdir -p build
cd build
conan install .. --output-folder=. --build=missing --profile:build=../conan-profile.txt --profile:host=../conan-profile.txt
cmake .. -DCMAKE_TOOLCHAIN_FILE=conan_toolchain.cmake -DCMAKE_BUILD_TYPE=Release
cmake --build . -j 4To clean, use the following:
cmake --build . --target cleanTo execute the tests do the following:
../bin/MCTS_ConnectFour_testsTo execute the game do the following:
../bin/MCTS_ConnectFourTo clear all the whole conan cache, use the following command:
../bin/MCTS_ConnectFourThe algorithm works by finding the next best move the AI can do. It does that by book-keeping information about a search tree (here called: game tree). The root of that tree is the enemies turn and current state of the board. The connections from that root to childNodes are the moves the current player can do.
MCTS process:
- expand all childNodes from the root and assign a very large random initial UCTB-value
- Repeat an iteration of Selection, Expansion, Simulation and Backpropagation as many times (here set to 10,000, but a time treshold can be chosen too)
- Select an action to perfom (here: most visited robust childNode from root)
Shows what the iteration in step 2. has to do (from wikipedia with CC BY-SA 4.0 licence).
Steps are explained below:
Selection:
The MCTS tries to traverses through the game tree always following paths with highest UCTB - doesn't matter whether enemy nodes or personal ones, because it needs to take into account that the enemy is also tries to maximize its winrate. This traversal stops, when some unexpanded Leaf-Nodes (L) is found.
Expansion:
Expand one or more Leaf-Nodes (L), unless leaf-node L ended the game.
Simulation:
Simulate a playout until game ended in a WIN / LOOSE / DRAW.
Backpropagation:
Increase visit count of every node along the followed path until the root node is reached (included) and do the following for those nodes:
- DRAW => every nodes along the path is increased by Value::DRAW
- WIN => every AI node along the path is increased by Value::WIN, whereas every enemy node is increased by Value::LOOSE
- LOOSE => every AI node along the path is increased by Value::LOOSE, whereas every enemy node is increased by Value::WIN
Shows the class structure and assoziation between the classes used. Including signal and slots for the QT-based GUI.
In this project I used a rather simple GUI design consisting of a TableView. When you click in a non-empty column for edit and click somewhere else again, the TableView receives an update and it's going to place your token in that column. When it's not your turn, you cannot place any tokens. The game is stopped when a modal dialog pops up, indicating the winner.
- https://dke.maastrichtuniversity.nl/m.winands/documents/pMCTS.pdf
- https://de.slideshare.net/ftgaic/mcts-ai
- http://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/
- https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
