8

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?

  • 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. – Allure Dec 26 '17 at 0:07
  • I don't see how it can be a duplicate - the question is obviously (?) different. – Allure Dec 27 '17 at 5:59
  • I'm sorry @user3727079, could you remove that downvote? Also tell me if it helps. – QuIcKmAtHs Dec 28 '17 at 5:44
  • @XcoderX he can’t remove it because I am the one who downvoted you – SmallChess Dec 29 '17 at 1:43
5

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.

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

  • @user3727079 does this help? – QuIcKmAtHs Dec 27 '17 at 12:16
  • 1
    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). – Allure Dec 29 '17 at 4:14

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.