16

If I get two engines to play against each other with the same colours, will the same game result every time? If not, where does the randomness in engine play come from? (Neglecting the opening book, where if I'm not mistaken the book can tell the engine to pick between two moves at random since they're equally good.)

I'm assuming that there is randomness because in the Alphazero vs. Stockfish match, we didn't get the same game happening many times in a row. However I don't understand why. Presumably the only way to do this is to get the engine to play a subpar move some of the time, which sounds like seppuku.

2
  • AlphaZero learns by playing, so after each game it's model is updated.
    – ferit
    Dec 21, 2017 at 7:56
  • Adding small random value to evaluation is one of possible ways. I think stockfish is doing that.
    – hoacin
    Dec 21, 2017 at 10:44

2 Answers 2

11

Regarding the AlphaZero vs Stockfish match, this question has already been covered here by SmallChess.

AlphaZero aside (which employs a specialised Monte Carlo1 routine in its exploration of the lines of play), which is made to be non-deterministic by construction, for the usual heuristics based chess engines, such as Stockfish and others (though there are other engines that have MC-based routines, AFAIK Rybka used to have such feature), the source of randomness is generally just a consequence of technical aspects in the implementation, rather than intentional randomness being introduced algorithmically in the engine's decision making. Abstractly speaking, one reason for that is the fact that the engines aren't running in a purely sequential manner (executing one task after the other). Instead, to render the engines more efficient, they perform parallel searches in various branches of the tree of possible moves. They do so via what is called multi-threading (or -processing but that is a bit different). So multiple threads of the CPUs are concurrently executing operations to search the tree (and cache the evaluations of visited positions), so imagine each thread being assigned a subtree. The problem with this kind of implementation is that the overall execution of the threads becomes highly dependent on all sorts of conditions (waiting times, RAM swaps, ...), so in the end a principal variation may be chosen without having allowed all other threads to finish their search.

This indeed happens often because the engine is set to make a decision under a certain amount of time, so time management alters the behaviour. You can also revert this statement by saying: knowing the algorithm and implementing deterministic threading routines are not sufficient to reliably predict the state of the program after any time t. Of course if one always allows all threads to finish their search, and there haven't been concurrency issues during that execution (for instance a thread trying to access a certain cache that isn't accessible), then the behaviour will indeed be fully reproducible given everything else is the same2.


1: Together with the fact that through additional training (for instance self-play) its neural network keeps evolving (re-adjusted parameters), or if you will its evaluation function doesn't have a constant, fixed definition (unlike heuristics based engines).

2: Even then, as you said, at the opening level, with an opening book, there are sometimes intentional random decisions made by the engine as to which variation to choose. Similarly, outside of the opening phase, there can be moments where multiple variations have close to equal evaluations (within the resolution chosen for the Eval), then based on the design, it may end up choosing one randomly. Finally, at the level of engine settings you have to be careful as well, for instance the depth of search and ponder times chosen for each engine (and whether they can further calculate during each other's ponder times).

8

Thanks to @Phonon covering my previous answers in details. I'd like to add one more point: time control.

The only deterministic time control is by number of nodes, but this is uncommon. The much more common time control - fixed number of seconds or game time are generally not deterministic.

Let's try an example. Run stockfish on your terminal. Type:

go movetime 20000

This command instructs the engine to make a move after 20 seconds. My results:

info depth 23 seldepth 32 multipv 1 score cp 6 upperbound nodes 24325860 nps 1216171 hashfull 999 tbhits 0 time 20002 pv g1f3 d7d5
bestmove g1f3 ponder d7d5

The move was 1.Nf3. Next, I killed my Stockfish, started a new one. Again, 20 seconds. I got:

info depth 23 seldepth 32 multipv 1 score cp 20 nodes 26185280 nps 1309067 hashfull 999 tbhits 0 time 20003 pv d2d4
bestmove d2d4 ponder g8f6

It's 1.d4! Same position, both 20 seconds search!

Do you see? Both 20 seconds for the move, but due to fluctuation in the Linux operating system my second run had deeper search (26185280 > 24325860).

Please note this little experiment wasn't even multithreaded (number of threads = 1). Multithreading would make things even more non-deterministic.

Stockfish was given one minute per move in the Google AlphaZero match. Number of threads was 64. Stockfish's decisions in the match couldn't possibly be deterministic.

4
  • Indeed, very instructive example and remark.
    – user929304
    Dec 21, 2017 at 15:20
  • nice! cool idea to showcase even the 1 thread case.
    – Ellie
    Dec 21, 2017 at 15:28
  • Thanks for the answer. Stupid follow-up question: what's a node (in the context of chess-playing engines)?
    – Allure
    Dec 24, 2017 at 6:09
  • @user3727079 The nodes are the vertices (unique positions) in the game tree. For instance if the root node is the starting position, then it has 20 child nodes, which are the 20 unique legal positions that are one-ply away from the root.
    – Ellie
    Dec 25, 2017 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.