Introduction

Game Theory is a general study of games. Many of these games are solved without rigirious computation (for example, where impartial combinatorial games are solved by generalizing the game to Nim).

However, computation is still important in mathematics as it helps mathematicians find underlying patterns to build said heuristics.

That is the purpose of game-solver. It helps solve various games, and allows users to play against the AI, analyze the game tree, and more. It allows programmers to derive the God's algorithm for any game, as well as derive meaningful statistics about the game. By utilizing powerful tree traversal algorithms and modern machine learning heuristics, we hope to lower the computational bar in combinatorial game theory research.

The goal of game-solver is not to make an estimated AI, like Stockfish or AlphaZero. The goal of this is to make a perfect AI. If you want to make an estimated AI, it may be a better idea to use general reinforcement learning instead.

As of now, game-solver can only solve 2-player perfect information games. However, the goal is to eventually support more players and imperfect information games.

Capabilities

This library is not meant to serve as a substitute for complex game engines (go, chess).

The thing it does right is God's algorithm computation, to find perfect, full play for generic games.

Features

game-solver comes with a number of library features:

Core game-solver, which allows for a full game tree search
reinforcement, which allows for trained move ordering for faster alpha-beta pruning.

Reinforcement Learning

TODO

Performance

game-solver takes performance seriously - any possible generic performance that can be applied should be applied.

List of applied optimizations

Search algorithms:
- Negamax (for 2-player zero-sum games)
  - Principal Variation Search (more popularly known as NegaScout)
- Alpha-Beta Pruning (ignores suboptimal branches, depends on move order)
  - Iterative Deepening
  - Null window search
Memoization via Transposition Tables.
- Both lower bound and upper bound
- (Parallelization only):
  - Concurrent memory-based HashMap cache via moka.
    - TODO: Use depth-first cache removal
- xxHash for fast hashing.
  - If you want to use xxHash without parallelization, pass it to your hashmap by using hasher: std::hash::BuildHasherDefault<xxhash_rust::XxHash64>.
  - You can disable xxhash by removing the xxhash feature.
    - More information about why you may want to do this can be found in the hashing section
ML-based move ordering with candle
Parallelization with rayon
- Note that this is under the rayon feature flag.
- TODO: Use Lazy SMP (currently this is using naive parallelization on the move_scores level)

Optimizing your own Games

The Rust Performance Book gives great general optimizations, but there are also important steps you can make when working with games.

Always remember to compile with --release.

Move Ordering

This is the most important algorithm-based optimization.. Making sure your Game#possible_moves function guesses what the best moves are first can save a lot of time, since there are multiple tree-pruning related optimizations that benefit from good moves being chosen first.

You can also use game-solver's reinforcement learning method, which is highly recommended as it saves time on manual implementation.

If possible, try to "guess" the score of a move, and sort the moves by that score.

Efficient Bitboards

Use efficient bitboards - you can look at the examples for inspiration, but make sure your board representation is fast, and preferably doesn't need allocation.

Good starting points:

BitVec for bool-only arrays
ndarray for nd arrays (instead of Vec<Vec<...>>)

Hashing

Transposition tables require hashing to store the game board as a key and retrieve it later for efficiency.

Since the type of game board is not known, game-solver uses the fastest general-purpose hash function available: xxHash. However, if you know your game board can be hashed faster, you can provide your own hasher to the transposition table.

For example, in Chess, the most common way to hash a board is to use a Zobrist Hash. This can be generalized to any type of board, aka Tabulation Hashing.

Solving Games