Home * Search * Parallel Search * Lazy SMP
Our_living_world_(Full_Page_Illustration).jpg

Lazy SMP,
based on the shared hash table approach of a parallel search to profit from probing hash entries written by other instances of the search, as already used by Vincent David's αβ* [1]. Multiple processes or threads search the same root position, but are launched with different depths, and/or varying move ordering at the root node, to statistically improve the gains from the effect of nondeterminism, otherwise depending on random timing fluctuations [2]. The term Lazy SMP was coined by Julien Marcel end of 2012 [3] with further elaborations by Daniel Homan [4] [5], Martin Sedlak and others. Today, many chess programs use this easy to implement parallel search approach, which scales surprisingly well up to 8 cores and beyond [6], not only in nodes per second (as expected), but in playing strength, while it seems worse than YBW in speedup concerning time to depth [7]. Notably Stockfish 7, released in January 2016, switched from YBW to lazy SMP [8] [9] [10].
Sloths traversing a tree [11]

Cheng's Pseudo Code

Pseudo Code of Lazy SMP in Cheng as given by its author Martin Sedlak [12]:
IterativeDeepening:
  synchronize smp threads (copy age, board, history, repetition list, multipv => helpers)
  depth 1 with full width window on 1 thread
  loop (depth=2 .. max)
    AspirationLoop:
      (as usual)
      start helper threads( depth, alpha, beta )
      root( depth, alpha, beta)
      stop helper threads
      (rest as usual)
    end aspiration loop
  end depth loop 
 
starting helper threads:
  clear smp abort flag
  for each helper thread:
    copy rootmoves and minimum qs depth => helper
    signal helper to start root search at current depth (add 1 for each even helper 
     assuming 0-based indexing)  with aspiration alpha, beta bounds and wait until 
     helper starts searching 
 
aborting helper threads:
  set abort flag for each helper and wait for each to stop searching 

See also


Selected Publications


Forum Posts

2010 ...

2015

2016

2017


External Links


References

  1. ^ Vincent David (1993). Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, École nationale supérieure de l'aéronautique et de l'espace, Toulouse, France
  2. ^ Re: Lazy SMP - how it works by Evert Glebbeek, CCC, October 19, 2016
  3. ^ Lazy SMP by Julien Marcel, CCC, December 27, 2012
  4. ^ Lazy SMP, part 2 by Daniel Homan, CCC, January 12, 2013
  5. ^ Lazy SMP and Work Sharing by Daniel Homan, CCC, July 03, 2013
  6. ^ Re: A new chess engine : m8 (comming not so soon) by Peter Österlund, CCC, February 01, 2015
  7. ^ Time to depth concerns by Carl Bicknell, CCC, August 15, 2016
  8. ^ Stockfish 7 by Joona Kiiski, CCC, January 02, 2016
  9. ^ Threads test incl. Stockfish 7 by Andreas Strangmüller, CCC, January 11, 2016
  10. ^ Stockfish 7 progress by Carl Lumma, CCC, January 16, 2016
  11. ^ Three-toed sloth, Image by Friedrich Specht in Joseph Bassett Holder, John George Wood (1885). Our living world; an artistic edition of the Rev. J. G. Wood's Natural history of animate creation. New York : Selmar Hess, Wikimedia Commons
  12. ^ Lazy SMP in Cheng by Martin Sedlak, CCC, February 02, 2015 » Cheng
  13. ^ std::async - cppreference.com

What links here?


Up one level