How does Allie's search algorithm work? Allie is a strong engine that's looking competitive with the top ones (Leela Chess Zero and Stockfish). It's supposedly based off AlphaZero, but works differently. As far as I understand it, the most important difference is the search algorithm. The author said in a March 2019 interview that:


  AT: To begin the tournament, Allie will perform MCTS based search with absolute fpu where new nodes start off with win pct of -1. The search is modeled after Deepminds paper’s. As I said above, I’m hoping to switch to AlphaBeta for the long term direction of the project. I’ve experimented with many, many ways of doing this with the networks generated by the Lc0 project and I think I’ve hit upon a way to achieve the depths required to maintain ELO level with MCTS based search, but it is not ready yet. In the future, I imagine we’ll see a lot of experimentation with different variations of search (mcts, ab) + eval (handwritten, NN) in computer chess engines. Hoping to be a part of that and to contribute to the shared pool of knowledge.


(Emphasis mine.) As of time of writing the Allie Github page says:


  Well, I was inspired during the original CCC to see if you could pair traditional Minimax/AlphaBeta search with an NN. This is still her main purpose and the focus going forward. However, the initial versions were using a similar pure MCTS algorithm as Lc0 and AlphaZero. The current versions of Allie use a modified hybrid search of Minimax and Monte Carlo.


I don't understand what "modified hybrid search of Minimax and Monte Carlo" means. Can someone explain? I know what each of these terms mean, but I don't understand the combination.
Allie's search is a combination of MCTS and Minimax. The MCTS is very much like you would find in AlphaZero or LC0 as it was taken from the same papers. In addition to MCTS, Allie also does a minimax based backup of the tree whenever a new MCTS batch is evaluated by the NN. This minimax backup is then used to modify the Q values of the nodes in the tree that were either 'min' or 'max'. This modification is a further averaging of the MCTS based backups.

So:


Allie uses MCTS for playouts and for back prop in much the same way as A0 and Lc0
Allie also does a minimax-based back prop to supplement that mcts based back prop


I've also tried many, many, many, different ways of adding newer AB/Minimax to the algorithm, but so far nothing that has successfully gained elo over the above. Finally, I'll note that in all of my testing of Allie (pure MCTS) vs Allie (MCTS+Minimax) the latter has scored significantly higher so I am confident that it does improve elo at least in self play.

UPDATE:

Since I wrote this, the Allie minimax backup has grown more complicated. Now, in positions where the best candidate move is a terminal node Allie does a pure minimax based backup with no mcts averaging. If the best is proven best among all of its siblings, then the parent is also made terminal and assigned the inverse score of the best child. If the best is not proven, then it still does pure minimax backup, but the parent continues to be expanded and if a sibling becomes best it switches back to the combination of minimax+mcts backup. Finally, this is all kept track of for transpositions too.