Performance

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

List of applied optimizations

  • Search algorithms:
  • 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.