Answers.Body: <p>This problem is rather similar to some coding problems.  Stockfish already has multiple pre-computed move sets.  It represents the state of the chessboard using multiple bitboards, which it then uses to evaluate the  board positions using a categorical(checks, tempos, checkmates) and statistical representation(piece values).  Almost immediately, it uses an advanced alpha-beta search algorithm. In order to not analyze the same position several times, a transposition table is used. This is essentially memorization applied to the search function, which is a fundamental in many graph-theory programming problems.  Thus, it actually uses a rather simple algorithm.
  Here is some research done before:</p>
  
  <p>Step 1. Initialize node</p>
  
  <p>Step 2. Check for aborted search and immediate draw. Enforce node limit here. (This only works with 1 search thread, as of Stockfish 2.3.1.)</p>
  
  <p>Step 3. Mate distance pruning. Even if we mate at the next move our score would be at best mate_in(textssrightarrowtextply+1textssrightarrowtextply+1, but if alpha is already bigger because  a shorter mate was found upward in the tree then there is no need to search further, we will never beat current alpha. Same logic but with reversed signs applies also in the opposite condition of being mated instead of giving mate, in this case return a fail-high score.</p>
  
  <p>Step 4. Transposition table lookup. We don’t want the score of a partial search to overwrite a previous full search. We use a different position key in case of an excluded move.</p>
  
  <p>Step 5. Evaluate the position statically and update parent’s gain statistics</p>
  
  <p>Step 6. Razoring (is omitted in PV nodes)</p>
  
  <p>Step 7. Static null move pruning (is omitted in PV nodes). We’re betting that the opponent doesn’t have a move that will reduce the score by more than futility_margin(depth) if we do a null move.</p>
  
  <p>Step 8. Null move search with verification search</p>
  
  <p>Step 9. ProbCut.  If we have a very good capture and a reduced search returns a value much above beta, we can (almost) safely prune the previous move.</p>
  
  <p>Step 10. Internal iterative deepening.</p>
  
  <p>Step 11. Loop through moves.  Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs</p>
  
  <p>Step 12. Extend checks and also dangerous moves</p>
  
  <p>Step 13. Futility pruning.</p>
  
  <p>Step 14. Make the move</p>
  
  <p>Step 15. Reduced depth search (LMR). If the move fails high will be re-searched at full depth.</p>
  
  <p>Step 16. Full depth search, when LMR is skipped or fails high.</p>
  
  <p>Step 17. Undo move</p>
  
  <p>Step 18. Check for new best move</p>
  
  <p>Step 19. Check for split</p>
  
  <p>Step 20. Check for mate and stalemate</p>
  
  <p>Step 21. Update tables. Update transposition table entry, killers and history</p>
  
  <p>I shall attempt to explain what the professor's research is talking about.  Stockfish creates a search tree of the legal move.<a href="https://i.sstatic.net/Kd9I5.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Kd9I5.jpg" alt="enter image description here"></a>
  Then, it begins to evaluate whether each move is good or bad, and how good or bad it is, by executing a shallow search field first, and then using the resulting alpha/beta cutoff values as start values for a deeper search.  Stockfish also prioritises pieces.  For instance, knights would be prioritised at the centre, so if a knight and bishop get forked at the centre, it will move the knight, unless there are other significant gains by moving the bishop.  While this may seem complicated, this execution is approximately log(number of possible moves), hence making it rather fast still.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-27T12:16:46.290Z
Answers.Text: @user3727079 does this help?
Answers.UserDisplayName: QuIcKmAtHs
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-29T04:14:52.647Z
Answers.Text: No, unfortunately. I don't understand your answer. It doesn't seem to be answering my question, which was on which node to search first, not how does Stockfish make its decisions (I understand what it means to search trees).
Answers.UserDisplayName: Allure
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-27T06:13:49.003Z
Answers.LastActivityDate: 2017-12-27T06:13:49.003Z
Answers.UserDisplayName: QuIcKmAtHs
Answers.Body: <p><a href="http://rebel13.nl/rebel13/ideas.html" rel="noreferrer">http://rebel13.nl/rebel13/ideas.html</a> explains this well.  </p>
  
  <p>The basic idea is to order the moves based upon what the program thinks is the best move without searching.  This score is usually based upon mobility, piece-square value, center control, history, attacking potential, captures, and other elements the programmer thinks is important.  Just as humans base their candidate moves based on intuition and history, the computer searches the highest scoring move first.</p>
  
  <p>If the computer is limited to only five nodes, then yes, the computer will only search the five highest scoring moves.  This time limit factor could cause to computer to miss a mate-in-one if it was scored poorly.  The first method to correct for this was to establish fail-safes.  These would cut short a search if the position became noticeably worse or significantly better.  The hope was to allow for more time to search more variations that might use the time better.  Other search algorithms, iterative deepening,  have improved the time management as they have a shorter length before they enact a fail-safe.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-04T11:59:46.633Z
Answers.LastActivityDate: 2018-01-04T11:59:46.633Z
Answers.UserDisplayName: Fred Knight
Body: <p>This is a follow-up question to <a href="https://chess.stackexchange.com/questions/19482/randomness-in-engine-play/">Randomness in Engine Play</a>. SmallChess's answer indicates that in one instance, Stockfish searched a given number of nodes after 20s, and a different number in the other 20s, hence there is randomness.</p>
  
  <p>The question: if each node is a given position, how does Stockfish decide which node to search first? Take for example the first half-ply. White has 20 possible first moves, so there are 20 nodes. I demand that Stockfish play a move after searching five nodes. Does this mean that Stockfish might only have evaluated 1. a4, 1. a3, 1. b4, 1. b3 and 1. c3 before it has to make a move? A systematic search like this would mean Stockfish hasn't evaluated the most common first moves however.</p>
  
  <p>I imagine that, later in the game, there'd be a massive jump in the number of nodes per half-ply. That would mean that Stockfish would sometimes decides to make a move even though it hasn't finished evaluating every node in the half-ply. How would it know that it's searched the most promising nodes?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-25T13:08:58.290Z
Comments.Text: https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-26T00:07:41.493Z
Comments.Text: Thanks for link, still don't really get it though. Say the graph at the bottom. I assume A is the current position, and B, C & E are the three candidate moves? If IDDFS at depth two goes A, B, D, F, C, G, E, F, and the best move is E, it could conceivably miss the best move if it had to terminate the search before reaching it.
Comments.UserDisplayName: Allure
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-27T05:59:32.157Z
Comments.Text: I don't see how it can be a duplicate - the question is obviously (?) different.
Comments.UserDisplayName: Allure
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-28T05:44:44.543Z
Comments.Text: I'm sorry @user3727079, could you remove that downvote?  Also tell me if it helps.
Comments.UserDisplayName: QuIcKmAtHs
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-29T01:43:30.547Z
Comments.Text: @XcoderX he can’t remove it because I am the one who downvoted you
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-29T02:05:18.683Z
Comments.Text: could you remove it if I edit my post?
Comments.UserDisplayName: QuIcKmAtHs
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-29T04:15:44.170Z
Comments.Text: @SmallChess do you know if SF uses MCTS (Monte Carlo Tree Search)?
Comments.UserDisplayName: Allure
Tags: <engines>
Title: How does an engine decide which node to search first?
ThreadText: # How does an engine decide which node to search first?
  
  (Asked by: username_0 on 2017-12-25)
  
  This is a follow-up question to [Randomness in Engine Play](https://chess.stackexchange.com/questions/19482/randomness-in-engine-play/). username_1's answer indicates that in one instance, Stockfish searched a given number of nodes after 20s, and a different number in the other 20s, hence there is randomness.
  
  The question: if each node is a given position, how does Stockfish decide which node to search first? Take for example the first half-ply. White has 20 possible first moves, so there are 20 nodes. I demand that Stockfish play a move after searching five nodes. Does this mean that Stockfish might only have evaluated 1. a4, 1. a3, 1. b4, 1. b3 and 1. c3 before it has to make a move? A systematic search like this would mean Stockfish hasn't evaluated the most common first moves however.
  
  I imagine that, later in the game, there'd be a massive jump in the number of nodes per half-ply. That would mean that Stockfish would sometimes decides to make a move even though it hasn't finished evaluating every node in the half-ply. How would it know that it's searched the most promising nodes?
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search  
  > **username_0**: Thanks for link, still don't really get it though. Say the graph at the bottom. I assume A is the current position, and B, C & E are the three candidate moves? If IDDFS at depth two goes A, B, D, F, C, G, E, F, and the best move is E, it could conceivably miss the best move if it had to terminate the search before reaching it.  
  > **username_0**: I don't see how it can be a duplicate - the question is obviously (?) different.  
  > **username_2**: I'm sorry @user3727079, could you remove that downvote?  Also tell me if it helps.  
  > **username_1**: @XcoderX he can’t remove it because I am the one who downvoted you  
  > **username_2**: could you remove it if I edit my post?  
  > **username_0**: @username_1 do you know if SF uses MCTS (Monte Carlo Tree Search)?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2018-01-04. Score: 5 | Accepted answer
  
  <http://rebel13.nl/rebel13/ideas.html> explains this well.
  
  The basic idea is to order the moves based upon what the program thinks is the best move without searching. This score is usually based upon mobility, piece-square value, center control, history, attacking potential, captures, and other elements the programmer thinks is important. Just as humans base their candidate moves based on intuition and history, the computer searches the highest scoring move first.
  
  If the computer is limited to only five nodes, then yes, the computer will only search the five highest scoring moves. This time limit factor could cause to computer to miss a mate-in-one if it was scored poorly. The first method to correct for this was to establish fail-safes. These would cut short a search if the position became noticeably worse or significantly better. The hope was to allow for more time to search more variations that might use the time better. Other search algorithms, iterative deepening, have improved the time management as they have a shorter length before they enact a fail-safe.
  
  
  ---
  
  ### Answer by username_2 on 2017-12-27. Score: 0
  
  This problem is rather similar to some coding problems. Stockfish already has multiple pre-computed move sets. It represents the state of the chessboard using multiple bitboards, which it then uses to evaluate the board positions using a categorical(checks, tempos, checkmates) and statistical representation(piece values). Almost immediately, it uses an advanced alpha-beta search algorithm. In order to not analyze the same position several times, a transposition table is used. This is essentially memorization applied to the search function, which is a fundamental in many graph-theory programming problems. Thus, it actually uses a rather simple algorithm.
  Here is some research done before:
  
  Step 1. Initialize node
  
  Step 2. Check for aborted search and immediate draw. Enforce node limit here. (This only works with 1 search thread, as of Stockfish 2.3.1.)
  
  Step 3. Mate distance pruning. Even if we mate at the next move our score would be at best mate\_in(textssrightarrowtextply+1textssrightarrowtextply+1, but if alpha is already bigger because a shorter mate was found upward in the tree then there is no need to search further, we will never beat current alpha. Same logic but with reversed signs applies also in the opposite condition of being mated instead of giving mate, in this case return a fail-high score.
  
  Step 4. Transposition table lookup. We don’t want the score of a partial search to overwrite a previous full search. We use a different position key in case of an excluded move.
  
  Step 5. Evaluate the position statically and update parent’s gain statistics
  
  Step 6. Razoring (is omitted in PV nodes)
  
  Step 7. Static null move pruning (is omitted in PV nodes). We’re betting that the opponent doesn’t have a move that will reduce the score by more than futility\_margin(depth) if we do a null move.
  
  Step 8. Null move search with verification search
  
  Step 9. ProbCut. If we have a very good capture and a reduced search returns a value much above beta, we can (almost) safely prune the previous move.
  
  Step 10. Internal iterative deepening.
  
  Step 11. Loop through moves. Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs
  
  Step 12. Extend checks and also dangerous moves
  
  Step 13. Futility pruning.
  
  Step 14. Make the move
  
  Step 15. Reduced depth search (LMR). If the move fails high will be re-searched at full depth.
  
  Step 16. Full depth search, when LMR is skipped or fails high.
  
  Step 17. Undo move
  
  Step 18. Check for new best move
  
  Step 19. Check for split
  
  Step 20. Check for mate and stalemate
  
  Step 21. Update tables. Update transposition table entry, killers and history
  
  I shall attempt to explain what the professor's research is talking about. Stockfish creates a search tree of the legal move.[![enter image description here](https://i.sstatic.net/Kd9I5.jpg)](https://i.sstatic.net/Kd9I5.jpg)
  Then, it begins to evaluate whether each move is good or bad, and how good or bad it is, by executing a shallow search field first, and then using the resulting alpha/beta cutoff values as start values for a deeper search. Stockfish also prioritises pieces. For instance, knights would be prioritised at the centre, so if a username_3 and bishop get forked at the centre, it will move the username_3, unless there are other significant gains by moving the bishop. While this may seem complicated, this execution is approximately log(number of possible moves), hence making it rather fast still.
  
  > **Comments:**
  > **username_2**: @user3727079 does this help?  
  > **username_0**: No, unfortunately. I don't understand your answer. It doesn't seem to be answering my question, which was on which node to search first, not how does Stockfish make its decisions (I understand what it means to search trees).  
  
  ---
  
  