search

RedBedHed / Homura

Development repo for Homura, A UCI Chess engine
MIT License
3 stars 0 forks source link

readme

Homura (炎)

UCI Hybrid Chess Engine

#

"I'll do it over. No matter how many times it takes. I'll re-live it over and over again. I will find the way out... The one path that will save you from a destiny of despair."
- Akemi Homura

Index

  1. Introduction
  2. Search
  3. Experimentation
  4. Rollout Alpha-Beta
  5. Search Techniques
  6. Strength
  7. Move Generation
  8. UCI
  9. Build Homura
  10. Play Homura

Introduction

Homura is a UCI Chess Engine that I maintain as a hobby. Homura started as an undergraduate honors thesis project for which I read many papers and found inspiration in many engines, including Stockfish, Leela, Drofa, Scorpio, Fruit, CPW-Engine, PeSTO, Blunder, Mantissa, Stormphrax, and Leorik. Homura derives from some of the ideas used in these engines— most notably PeSTO.

Search

Homura uses a hybrid search algorithm that combines Dr. Bojun Huang's Alpha-Beta rollout algorithm with the traditional backtracking Alpha-Beta. All PV nodes are searched via rollout, while the remaining nodes are searched with backtracking and a null window. The rollout portion of the algorithm probes the transposition table each time that it enters a node, and its tree policy is a combination of leftmost and greedy selection.

Homura's algorithm— as a combination of novel and classical algorithms— searches the game tree in a different and exciting way. It also seems to outperform my backtracking search in matches administered by cutechess-cli.

Experimentation With Classical MCTS

I initially experimented with the classical Monte Carlo Tree Search algorithm. I spent months trying to write a strong MCTS engine on my laptop, without the help of deep neural networks. I found this task to be insurmountable— at least with a UCT-based tree policy and short alpha-beta simulations. In desparation, I tried a greedier tree policy and deeper alpha-beta search. This showed some promise, and led me to attempt a full-scale classical search. I found that the classical search was much stronger than anything I had tried previously. This prompted me to do more research into the shortcomings of the MCTS algorithm when it comes to Chess. The general consensus is that classical MCTS simply lacks the tactical awareness to excel at Chess without a great deal of help. At around the same time, I found out about the Dr. Huang paper through Scorpio, which led me to begin work on the algorithm that Homura currently uses.

Algorithm 4 by Dr. Huang

The Rollout Paradigm is a general algorithmic paradigm that involves searching a game tree in iterations. Each iteration— called a rollout— starts at the root and executes a line of play to some depth, performing some variation of the phases commonly associated with MCTS. These algorithms build the tree in memory as they complete each rollout, storing information to be used by their tree policy in subsequent rollouts. Classical MCTS is the flagship algorithm of this paradigm. However, while MCTS takes a very cautious and selective approach to search, expanding one node per rollout, not all rollout algorithms are limited to this strategy.

Algorithm 4— Huang's Alpha-Beta rollout algorithm— still relies on the four common MCTS phases. However, the order and quantity of expansions per rollout may differ.

An Alpha-Beta rollout to depth 3

Each node contains bounds 𝛼, 𝛽, 𝑉-, and 𝑉+. The search initializes 𝛼 and 𝑉- to negative infinity and 𝛽 and 𝑉+ to positive infinity.

  1. Selection and Expansion

    The Selection step is intertwined with the Expansion step. At the beginning of a rollout, the search sends a depth-limited probe from the root node out into the tree, expanding as needed and selecting a child at each intermediate node. During each selection, the search filters children according to their 𝛼 and 𝛽 bounds which it updates using 𝑉-, 𝑉+, and the 𝛼 and 𝛽 of the current node.

  2. Simulation

    In the Simulation step, the search evaluates the selected leaf node by quiescence search. It then sets Bounds 𝑉- and 𝑉+— and the score— to the value returned.

  3. Backpropagation

    In the Backpropagation step, the search pushes 𝑉+, 𝑉-, and the score up the tree in the negamax style. Once 𝑉- ≥ 𝑉+ at a node, its score is accurate, and the search has seen everything it needs to see in the tree below. When 𝑉- ≥ 𝑉+ at the root, its score and principal variation are valid. The best move is the move on the principal variation.

Backpropagation of bounds and score

Search Techniques

Homura's search is nearly single-threaded, relying on only one extra thread for garbage collection. It uses both classical and novel techniques.

// Base Search //

// Selectivity //

// Move Ordering //

Moves are sorted incrementally in the following order:

// Evaluation //

// Tree Policy //

Strength

Version Strength RFP NMP R FP LMP LMR
1.0 unrated ~2500 Yes Yes Yes Yes Yes Yes

Move Generation

Homura implements a strictly legal move generator with either PEXT or Fancy Magic for sliding attacks depending on the target CPU. It is heavily inspired by Stockfish, but differs in many ways. This move generator is very fast— a fact that I have been using as a bit of a crutch. Homura doesn't implement staged move generation.

Startup  -  0.001 seconds

perft(1) -  0.000 seconds -         20 nodes visited.
perft(2) -  0.000 seconds -        400 nodes visited.
perft(3) -  0.000 seconds -       8902 nodes visited.
perft(4) -  0.001 seconds -     197281 nodes visited.
perft(5) -  0.012 seconds -    4865609 nodes visited.
perft(6) -  0.249 seconds -  119060324 nodes visited.
Perft 6— from the starting position

UCI

Homura recognizes a small subset of uci commands.

  1. uci

    This command asks Homura to identify itself and confirm that it is a UCI Chess engine. It responds with:

    id name Homura
    id author Ellie Moore
    uciok

  2. ucinewgame

    This command re-initializes Homura’s board state to the starting position and resets the game-history stack.

  3. isready

    This command asks Homura if it is available to start a search. It responds with:

    readyok

  4. go infinite

    This command tells Homura to start a five second search from the current position. After searching, it responds with:

    bestmove <move in algebraic notation>

  5. go movetime <milliseconds>

    This command tells Homura to search from the current position for the given time in milliseconds. After searching, it responds with:

    bestmove <move in algebraic notation>

  6. go wtime <milliseconds> btime <milliseconds> winc <milliseconds> binc <milliseconds>

    This command tells Homura to search from the current position for the remaining time in milliseconds, with optional increment. After searching, it responds with:

    bestmove <move in algebraic notation>

  7. position startpos <list of algebraic moves>

    This command tells Homura to update the state of the board, playing the move at the end of the list of given moves. (This seemed to be the easiest implementation)

Build Homura

You may build the project by cloning the repository, opening a Bash shell in the project directory, navigating to the src directory, and typing “make.” These steps assume you already have the compilation tools “clang++” and “make” installed.

To run the executable file, you must include the "ospec.txt" file in the executable file's directory. The "ospec.txt" file is needed for the lexical analyzer to correctly lex the supported UCI commands.

Play Homura

To play against Homura, you must install a UCI-compatible Chess GUI such as “Cutechess." The infinite time control will give you unlimited time to make a move, and limit Homura to five seconds.

Open Source

Homura is open source with an MIT license. If for any reason you actually like the project, feel free to do stuff with it! :)

#

Disclaimer: I used DALL-E 3 to generate Homura's logo. The image beneath comes from the anime movie PMMM: Rebellion.