0

This is a conceptual question about the shared hashtable algorithm for parallel chess search.

I have implemented an alpha-beta search that spawns 4 threads, each of which conducts a search and returns the best move/evaluation. However, I am observing search instabilities, in which the threads return different results. I am using the lockless hashtable described in the link, so some entries might be overwritten or corrupted, although corrupt data will never actually be used.

Why might search threads return different results? Is this an expected outcome of parallel search, or is it a problem? If expected, how do I know which move to select?

dylhunn
  • 989
  • 2
  • 8
  • 25

1 Answers1

1

A parallel search is expected to be non-deterministic. Once you share knowledge via the transposition table (aka hashtable), you will have this effect.

If you run parallel searches, there is no easy way to decide what the correct result is. So, what can you do? If you have four threads, you could try a majority vote but I'm not aware of engines that do that.

Note that search stability is an issue that you will even have in a sequential search algorithm once you start using transposition tables.

If you run a sequential search algorithm with a transposition table and later repeat the same search (without resetting the transposition table), you are not guaranteed to get the same results. The same goes for a parallel search, only that a parallel search will not even be deterministic.

Search stability and determinism are not the same thing:

  • In a sequential search, you can achieve determinism (useful for debugging). In a parallel search, you cannot avoid it in practice.
  • Neither a sequential nor a parallel search can rule out search stability in practice. In a good search algorithm, it should be relatively unlikely, however.

For an explanation why transposition tables lead to search instability, take a look at this question.

Philipp Claßen
  • 41,306
  • 31
  • 146
  • 239