obelisk

This repository contains the source code to train and evaluate an artificial intelligence for a board game called "Obelisk in Space" (see the game's rules). The technologies used for this project are:

• Monte carlo integration
• Genetical evolution
• Deep learning (approx. 30000 parameters)
• Heuristical evaluation
• Some multithreading

Rules

The game of Obelisk in Space is played with a variable amount of players. The objective is to construct 10 obelisks. Every player starts with 1 obelisk, 1 barrack, 1 soldier and 1 wall. If a player reaches 0 obelisks, they lose.

Each turn, every player takes a decision, in secret. The decisions are collected by a game master and are then performed at the same time, at the end of the turn. The decisions that one can make are:

• Build a wall, adds 1 to the number of walls
• Build a barrack, adds 1 to the number of barracks
• Build an obelisk, adds 1 to the number of barracks
• Recruit, adds n to the number of soldiers, where n is the number of barracks, the soldiers are busy and cannot defend
• Skip, adds 1 to the number of soldiers, but the soldiers are available to defend
• Defend, temporarily doubles the defense effect of walls, lasts for two turns
• Attack player, attacks a player with the entire army, which cannot defend during that turn:
  • If there are more than 1 player attacking the same player, then players fight before sieging the target player. The player with the highest force comes on top, and loses as many soldiers as the 2nd strongest player attacking
  • If two players attack each other mutually, their forces fight each other in space and the strongest proceeds to siege the other with their remaining forces
  • The attacking player loses as many soldiers as the defender has walls (or twice as many if they were defending)
  • The attacking player's soldiers and the defender's soldiers fight each other, killing as many opponent soldiers as they have soldiers
  • If the attacking player still has soldiers left, they can proceed to raid the opponent and steal one of their obelisks

These rules are formalized in src/lib.rs, and you can find unit tests for different scenarios in that module.

Installation and running

Clone this repository and build it:

git clone https://github.com/adri326/obelisk && cd obelisk
cargo build --release

Then, you can run one of the tools with cargo run --release --bin <tool>. The available tools are:

• genetic, creates and runs a genetic simulation of organisms, whose genome is the sequence of actions that they'll take in the game. The hyperparameters can be tuned in src/bin/genetic.rs. The final population is stored in target/out.json
• generate_training, takes the population outputted by genetic and simulates games with monte carlo integration, using the distribution of moves in the organisms as the probability function for the action of every player. The best moves for these simulated games are stored in target/train-last.json. The settings for this simulation can be found in src/bin/generate_training.json Depending on the number of games and the requested accuracy, this step can take a few hours to complete.
• evaluate, takes a trained and converted model and runs it with monte carlo to evaluate a position. The input position is specified in two files:
  • players.json, containing the names, values and previous actions of every player
  • constraints.json, containing a list of action that you can optionally force player to take on their first move, in order to explore scenarios
  • as argument (passed after -- after the name of the tool), the number of samples to run for; standard deviation is proportional to the inverse square root of the number of samples, so quadrupling the number of samples only halves the stddev.

Some python scripts are included to train the DNN using tensorflow. You will need to install a few dependencies beforehand: numpy, bidict, tensorflow and tf2onnx

• train.py trains a model using the data generated by generate_training. The default hyperparameters are able to reach a categorical crossentropy loss of ~1.7 and an accuracy of ~40%. The model is used as part of a monte carlo simulation, so the low accuracy isn't a concern, but the speed for evaluating the model is.
• convert.py converts the trained model to an onnx file, which is required for evaluate

Results

I have yet to compare the predictions of the AI with the actions of human players, but the AI seems to perform best in the mid- and end-game. It struggles with predicting advantageous attacks, but is able to predict the moves of humans when they don't attack.

Trained models

TODO