How does an engine decide which node to search first?

Question

This is a follow-up question to Randomness in Engine Play. 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.

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?

Answer 1

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 2

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