5D Chess Engine

An open source C++ engine based on Monte Carlo tree search (MCTS) for the game '5D Chess With Multiverse Time Travel', featuring fast checkmate detection and customized MCTS tree design.

Besides the 5duci engine, this project also includes a web interface which allows analyzing 5D Chess positions online. Moreover, it provides python and javascript bindings that allows access of game logic from different programming languages.

Try it online!

Visit https://ftxi.github.io/5dchess_engine/.

Features

This project is written in a serious language for chess-programming. The target for it has shift from early stage goal of providing fast performance for basic game logic such as move generation and checkmate detection, which can be then used as a solid foundation for a competent 5d chess bot, to actually improving the bot. In fact, the plans for the near future is to try out different modifications of MCTS and figure out which is the correct direction.

This program supports reading arbitary 5d chess variant specified by 5dfen. For moves, it supports long algebraic notation (which looks like (0T13)b6b5 for physical moves and (-1T19)e8(0T18)f8 for superphysical moves) or simplified 5dpgn notation specified in docs/pgn-bnf.txt.

The storage of a game state is based on bitboards. As a result, all boards are hard-coded to be no larger than 8x8.

Currently, the engine implements move generation and check detection using coroutine-based generators. Thus it won't work on compilers pre-C++20.

For checkmate detection and action generation, this program implements the hypercuboid algorithm. The hypercuboid algorithm is also utilized in core/fine_tree.h for generating semimoves. This ensures that the branching factor of the search tree does not explode exponentially with the number of timelines.

This program supports tree shaped traversal.

Usage

The CMake program and a modern C++ complier (C++ 20 or newer) is required. On MacOS, Xcode is enough. On windows, I suggest Visual Studio Community version 2022.

There are a number of ways to use the program:

1. Use the static webpage hosted on github pages. See Try it online above.
2. Use the command-line engine and tools. No dependencies other than cmake and a C++ compiler. See Build command-line programs.
3. Build python module and host a graphics interface server via python. Requires a python runtime with flask and flask_socketio installed. See Build Python Module.
4. Build javascript module and host the static webpage same as the online version. See Build WASM.

Build command-line programs

mkdir build
cd build
cmake .. -DENGINE=on -DTOOLS=on -DCMAKE_BUILD_TYPE=Release
cmake --build .

The performance of this code depends significantly on compiler optimizations. Without optimization, the plain (unoptimized) version may run x6 ~ x7 times slower compared to the same code compiled with -O3 optimization. The flag -DCMAKE_BUILD_TYPE=Release above is used to enable optimizations.

The engine is built as build/5dchess, and the general command-line utility is built as build/5dtools. For commands that consume a game, provide 5DPGN on standard input and press Control-D to complete it. Current utility commands include:

• print: print the final state of the game
• count [<policy>] [<max>]: display number of available moves capped by <max>
• all [<policy>] [<max>]: display all legal moves capped by <max>
• checkmate [<policy>]: determine whether the final state is checkmate/stalemate
• diff: compare the output of two algorithms.
• perftest [<policy>]: on each intermediate state, print 1 if it is checkmate/stalemate, 0 otherwise
• rollout [options]: run and report random rollout simulations
• replay-log <log> [seed]: replay and time a protocol failure log

Build the tests independently with -DTEST=on. With none of ENGINE, TOOLS, TEST, PYMODULE, or EMMODULE enabled, CMake builds only the core C++ library.

Engines and autoplay

There are six engines: mcts, zero, linear, linear-trained, flat-uct, and monkey; they communicate using the 5DUCI protocol. zero is MCTS with a constant-zero default policy. The two Linear engines evaluate inconclusive rollout positions with the same bounded 64-feature model: linear uses hand-written weights and linear-trained uses a frozen experimental profile. See Linear evaluation features. flat-uct evaluates each legal root action with repeated random rollouts and chooses with the adversarial UCT rule, without expanding a search tree. Search engines accept an optional unsigned 32-bit seed using --seed or -s, for example 5dchess flat-uct --seed 1234. MCTS, both Linear engines, and flat-UCT also accept --rollout-max-actions (or -r) to shorten each default-policy rollout from its default limit of 200 actions, for example 5dchess linear --rollout-max-actions 40. The same limit can be changed through 5DUCI with setoption name rollout-max-actions value 40. A rollout that reaches the limit is scored as a draw by MCTS and flat-UCT; Linear evaluates the final rollout position instead. Setting the limit to zero disables rollout entirely. The shared UCT implementation is in src/engine/uct.h and src/engine/uct.cpp. To create an engine, derive the engine class in src/engine/uci.h. You must implement initialize() and find_best_move(), then start its mainloop() with an io_handler.

To play a match between two engines, first build the Python module (run cmake with -DPYMODULE=on), then run autoplay.py with the two engines specified as arguments. Example:

python autoplay.py --white "./build/5dchess mcts" --black "./build/5dchess monkey"

Autoplay records standard PGN match headers. Use --event and --site to name a standalone run; both default to Autoplay and Local. In a series, Round is the one-based game number.

For a compact 10-game flat-UCT/MCTS protocol smoke test, use:

python autoplay.py --white "./build/5dchess flat-uct --seed 11 --rollout-max-actions 2" --black "./build/5dchess mcts --seed 29 --rollout-max-actions 2" --movetime 20 --max-actions 2 --games 10

Autoplay metrics include engine_score: flat-UCT's selected-action rollout win rate, or MCTS's average score along the selected principal path. MCTS also fills engine_scores with the colon-separated score for each path node. Both engines report iterations and ips (iterations per second) in the CSV metrics. Use --help for more information on how to set a starting game, time controls, or a multi-game series.

For persistent Elo ratings across many registered engines, manual result reporting, automatic opponent selection, and concurrent games, see Elo registry and concurrent matchmaker. The pure elo.py tool never launches an engine; elo_matchmaker.py optionally automates its scheduled matches through autoplay.py.

Coding with IDE

It is possible to run the c++ part of the code without interacting with python or web interface at all. It also makes sense to use a modern programming IDE:

mkdir build-xcode
cd build-xcode
cmake .. -DTEST=on -GXcode

On Windows, the last line should be:

cmake .. -DTEST=on -G"Visual Studio 17 2022"

Build Python Module

IMPORTANT NOTE This module rely on two separate submodules. It is impossible to build the python library without them. Make sure use

git clone --recurse-submodules <link-to-this-repo>

to download both this repository and the necessary submodules.

If interaction with the graphics interface is preferred, please install flask and flask_socketio via pip.

mkdir build
cd build
cmake .. -DPYMODULE=on -DCMAKE_BUILD_TYPE=Release
cmake --build .

To use it, go to the base directory of this project and run host.py. Then, visit http://127.0.0.1:5000 with your favourite browser.

Build WASM

Requires emscripten.

mkdir build-wasm
cd build-wasm
emcmake cmake .. -DEMMODULE=on -DCMAKE_BUILD_TYPE=Release
cmake --build .

The static website is generated in the /build-wasm/ui/. Note that simply double-clicking index.html will likely fail to initialize the JavaScript components due to CORS (Cross-Origin Resource Sharing) restrictions enforced by modern browsers when using the file:// protocol.

To run the application correctly, you must serve the directory via a local web server. Use one of the following methods from within the build-wasm/ folder:

If you have python installed:

python -m http.server 8080 --directory ui/

If the emsdk is already sourced in your environment:

emrun ui/

If you prefer darkhttpd:

darkhttpd ui/

Disclaimer

All resources inside this project are either open source online or created by myself. It does not use any source code, copied directly or decompiled, from the 5D Chess With Multiverse Time Travel by Thunkspace, LLC. The original game is a commercial product and I have no affiliation with the developer.

Documentation

For more details on the structure of this repository, please read this page.

TODOs

• Move weighting for default policy
• Move ordering for tree policy
• Progressive widening
• Learned weights for the linear engine
• UCT/PUCT switch