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.

-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”.

  • 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 at 21:37
  • Perhaps you could answer by the question then with all of that knowledge that is relevant to it? @Oscar Smith – Rewan Demontay Jun 22 at 11:12
  • 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 at 16:11
  • That's alright. It's your decision after all, and not mine. – Rewan Demontay Jun 23 at 2:52
  • 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 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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