3

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.

Improve this question

2 Answers 2

Reset to default
7

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.

Improve this answer
1
  • Thanks for answer. Do you mean that Allie assigns a score to each MCTS "branch" and then uses minimax on those scores?
    – Allure
    Sep 25, 2019 at 0:31
-1

“Minimax” means pick the move which minimises the value of the opponent’s best possible response. If the search space was small this can be applied recursively to essentially solve the game. However chess is too big, so one can’t search the whole space. The program is picking a bunch of different directions randomly (aka Monte Carlo) and finding the minimax over all of these. There is some secret sauce the designer is glossing over here, hence “modified hybrid”.

Improve this answer
4
  • This is wrong on several counts. Firstly, there's no secret sauce. It's open source github.com/manyoso/allie. Second, the search has no randomness. Third, a combination of minimax and averaging is used for the backup.
    – Oscar Smith
    Jun 21, 2019 at 21:37
  • I'm working on understanding it. It's a lot easier to give a wrong answer than a right one. I'll answer once I feel like I am sure what the correct answer is.
    – Oscar Smith
    Jun 22, 2019 at 16:11
  • After a quick look at the repo, it seems the relevant code is in github.com/manyoso/allie/blob/master/lib/searchengine.cpp
    – bcdan
    Jul 8, 2019 at 15:23
  • I was wrong about the “secret” part, but otherwise I think my answer stands up. Monte Carlo described in the original question is essentially random.
    – Laska
    Jul 9, 2019 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.