4 ms·
It seems that the strategy is to use the neural network to score various moves and then a search strategy to try to find moves that result in a favourable score
by dan-robertson 6y ago
It seems that the strategy is to use the neural network to score various moves and then a search strategy to try to find moves that result in a favourable score. And this post focuses on some of the technical engineering details to design such a scoring network. In particular the scoring is split into two parts: 1. A matrix multiplication by a sparse input vector to get a dense representation of a position, and 2. Some nonlinear and further layers after this first step. And it seems that step 1 is considered more expensive.
The way this is made cheap is by making it incremental: given some board s and output of the first layer b + Ws, it is cheap to compute b + Wt where a t is a board that is similar to s (the difference is W(t-s) but the vector t-s is 0 in almost every element.)
This motivates some of the engineering choices like using integers instead of floats. If you used floats then this incremental update wouldn’t work.
It seems to me that a lot of the smarts of stockfish will be in the search algorithm getting good results, but I don’t know if that just requires a bit of parallelism (surely some kind of work-stealing scheduler) and brute force or if it mostly relies on some more clever strategies. And maybe I’m wrong and the key is really in the scoring of positions.
- eutectic 6y agoI don't think the integer weights are neccessary for sparsity; they are just faster because they allow for low precision. Of course floats aren't strictly associative so you wouldn't get bitwise equivalence between the incremental and non-incremental updates, but I don't see how that would matter in this context.
- dan-robertson 6y agoThe point is that integer weights allow for incremental updates to be correct. If you used floats then they would drift away from correct as you applied more incremental updates. And neural networks can be quite sensitive to small errors
- eutectic 6y agoWith 32 bits of precision I don't see it being a big problem over a maximum of say 50 moves. Neural networks which are not overfit should be tolerant of a small amount of random (not crafted) noise.
- deleted 6y ago[deleted]
- recursive 6y ago64-bit floats have 53 bits of precision. 32-bit floats have 24. The rest goes into sign and exponent.
- dan-robertson 6y agoMaybe the network uses integers for other reasons. Perhaps due to the history of the program. I don’t know how the search works but I would imagine it would consider more than 50 moves with lots of backtracking and trying different possible moves.
- thomasahle 6y ago> It seems that the strategy is to use the neural network to score various moves and then a search strategy to try to find moves that result in a favourable score The neural net is only for scoring positions, not moves. Check the article on Stockfish NNUE at the chess programming wiki: https://www.chessprogramming.org/Stockfish_NNUE https://www.chessprogramming.org/Stockfish_NNUE There is a LOT of cleverness built into the stockfish search as well. In fact, while neural networks have now won the position evolution game, it is still an open discussion in the chess programming community if the Alpha Zero / Leela search (NN + Monte Carlo) is as good as Stockfish's PVS.
- ogogmad 6y agoPVS?
- zone411 6y agohttps://www.chessprogramming.org/Principal_Variation_Search https://www.chessprogramming.org/Principal_Variation_Search
- zirkonit 6y agoI presume, Principal Variation Search (https://www.chessprogramming.org/Principal_Variation_Search https://www.chessprogramming.org/Principal_Variation_Search)