Answers.Body: <p>“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”.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-21T21:37:44.580Z
Answers.Text: This is wrong on several counts. Firstly, there's no secret sauce. It's open source https://github.com/manyoso/allie. Second, the search has no randomness. Third, a combination of minimax and averaging is used for the backup.
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-22T16:11:53.687Z
Answers.Text: 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.
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-08T15:23:19.200Z
Answers.Text: After a quick look at the repo, it seems the relevant code is in https://github.com/manyoso/allie/blob/master/lib/searchengine.cpp
Answers.UserDisplayName: bcdan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-09T00:39:22.373Z
Answers.Text: 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.
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-20T01:56:05.030Z
Answers.LastActivityDate: 2019-06-20T01:56:05.030Z
Answers.UserDisplayName: Laska
Body: <p>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 href="http://www.chessdom.com/alliestein-the-new-neural-network-entering-tcec-s15/" rel="nofollow noreferrer">a March 2019 interview</a> that:</p>
  
  <blockquote>
    <p>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, <strong>I’m hoping to switch to AlphaBeta for the long term direction of the project</strong>. 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.</p>
  </blockquote>
  
  <p>(Emphasis mine.) As of time of writing the <a href="https://github.com/manyoso/allie" rel="nofollow noreferrer">Allie Github page</a> says:</p>
  
  <blockquote>
    <p>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. <strong>The current versions of Allie use a modified hybrid search of Minimax and Monte Carlo.</strong></p>
  </blockquote>
  
  <p>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.</p>
  
Tags: <engines><chess-algorithms>
Title: How does Allie's search algorithm work?
ThreadText: # How does Allie's search algorithm work?
  
  (Asked by: username_0 on 2019-06-20)
  
  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](http://www.chessdom.com/alliestein-the-new-neural-network-entering-tcec-s15/) 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](https://github.com/manyoso/allie) 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.
  
  **Tags:** engines, chess-algorithms
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-20. Score: -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”.
  
  > **Comments:**
  > **username_2**: This is wrong on several counts. Firstly, there's no secret sauce. It's open source https://github.com/manyoso/allie. Second, the search has no randomness. Third, a combination of minimax and averaging is used for the backup.  
  > **username_2**: 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.  
  > **username_3**: After a quick look at the repo, it seems the relevant code is in https://github.com/manyoso/allie/blob/master/lib/searchengine.cpp  
  > **username_1**: 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.  
  
  ---
  
  