25,161
edits
Changes
no edit summary
also known as '''Multithreaded Search''' or [[SMP]] Search, is a way to increase [[Search|search]] speed by using additional [https://en.wikipedia.org/wiki/Central_Processing_Unit processors]. This topic that has been gaining popularity recently with [https://en.wikipedia.org/wiki/Multiprocessing multiprocessor] computers becoming widely available. Utilizing these additional processors is an interesting domain of research, as traversing a search tree is inherently serial. Several approaches have been devised, with the most popular today being [[Young Brothers Wait Concept]] and [[Shared Hash Table]] aka [[Lazy SMP]].
This page gives a brief summary of the different types. SMP algorithms are classified by their [https://en.wikipedia.org/wiki/Scalability scalability] (trend in search speed as the number of processors becomes large) and their [https://en.wikipedia.org/wiki/Speedup speedup] (change in time to complete a search). Typically, programmers use '''scaling''' to mean change in [[Nodes per secondSecond|nodes per second]] (NPS) rates, and speedup to mean change in time to [[Depth|depth]]. Scaling and scalability are thus two different concepts.
=Distributed Search=
''see Main page: [[Shared Hash Table]]''
This technique is a very simple approach to [[SMP]]. The implementation requires little more than starting additional processors. Processors are simply fed the root position at the beginning of the search, and each searches the same tree with the only communication being the [[Transposition Table|transposition table]]. The gains come from the effect of nondeterminism. Each processor will finish the various subtrees in varying amounts of time, and as the search continues, these effects grow making the search trees diverge. The speedup is then based on how many nodes the main processor is able to skip from transposition table entries. Many programs used this if a "quick and dirty" approach to SMP is needed. It had the reputation of little speedup on a mere 2 processors, and to scale quite badly after this.
<span id="Lazy"></span>
==Lazy SMP==
''see Main page: [[Lazy SMP]]''
Recent improvements by [[Dan Daniel Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013</ref> , [[Martin Sedlak]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015</ref> and others on '''Lazy''' SMP indicate that the algorithm scales quite well up to 8 cores and beyond <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11 Re: A new chess engine : m8 (comming not so soon)] by [[Peter Österlund]], [[CCC]], February 01, 2015</ref> .
==ABDADA==
* [[Parallel Prefix Algorithms]]
* [[SIMD and SWAR Techniques]]
=Publications=
'''1983'''
* [[Raphael Finkel]], [[John Philip Fishburn]] ('''1983'''). ''Improved Speedup Bounds for Parallel Alpha-Beta Search''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 5, No. 1, pp. 89 - 92
* [[Clyde Kruskal]] ('''1983'''). ''[httphttps://ieeexplore.ieee.org/xpldocument/freeabs_all.jsp1676138?arnumber=1676138 Searching, Merging, and Sorting in Parallel Computation]''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. C-32, No 10
* [[Gary Lindstrom]] ('''1983'''). ''The Key Node Method: A Highly-Parallel Alpha-Beta Algorithm''. Technical Report UUCCS 83-101, [https://en.wikipedia.org/wiki/University_of_Utah University of Utah], [http://content.lib.utah.edu/utils/getfile/collection/uspace/id/3706/filename/image pdf]
'''1984'''
* [[Lionel Moser]] ('''1984'''). ''An Experiment in Distributed Game Tree Searching'', M.Sc. thesis, [[University of Waterloo]] <ref>[[Jonathan Schaeffer]] ('''1985'''). ''[[Lionel Moser]]: An Experiment in Distributed Game Tree Searching.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]] (Review)</ref> <ref>[httphttps://www.cs.uwaterloo.ca/~alopez-o/divulge/chimp.html An Introduction to Computer Chess] by [http://www.cs.uwaterloo.ca/~alopez-o/ [Alejandro López-Ortiz]], 1993</ref>
==1985 ...==
* [[Tony Marsland]], [[Fred Popowich]] ('''1985'''). ''Parallel Game-Tree Search.'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 4, pp. 442-452. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/parallel.pdf 1984 pdf] (Draft)
* [[Baruch Awerbuch]] ('''1985'''). ''[http://www.sciencedirect.com/science/article/pii/0020019085900833 A New Distributed Depth-First Search Algorithm]''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters], Vol. 20, No. 3
* [[Monroe Newborn]] ('''1985'''). ''A Parallel Search Chess Program''. Proceedings of the ACM Annual Conference, pp. 272-277. Denver, Co.
* [[Clyde Kruskal]], [https://en.wikipedia.org/wiki/Alan_Weiss_%28mathematician%29 [Mathematician#AWeiss|Alan Weiss]] ('''1985'''). ''Allocating Independent Subtasks on Parallel Processors''. [https://en.wikipedia.org/wiki/IEEE_Transactions_on_Software_Engineering [IEEE#SE|IEEE Transactions on Software Engineering]], Vol. 11, No. 10
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Leifker:Daniel_B=.html Daniel B. Leifker], [[Laveen Kanal|Laveen N. Kanal]] ('''1985'''). ''[http://dl.acm.org/citation.cfm?id=1623687 A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai85.html#LeifkerK85 IJCAI'85] » [[SSS* and Dual*]]
'''1986'''
* [[Henri Bal]], [[Robbert van Renesse]] ('''1986'''). ''A Summary of Parallel Alpha-Beta Search Results''. [[ICGA Journal#9_3|ICCA Journal, Vol 9, No. 3]]
* [[Jonathan Schaeffer]] ('''1986'''). ''Improved Parallel Alpha-Beta Searching''. Proceedings ACM/IEEE Fall Joint Computer Conference, pp. 519-527.
* [[Rainer Feldmann]], [[Peter Mysliwietz]], [[Oliver Vornberger]] ('''1986'''). ''A Local Area Network Used as a Parallel Architecture''. Technical Report 31, [[Paderborn University of Paderborn]]
'''1987'''
* [http://www.onesource.com/free/Usui-Hiromoto/People/Profile/51361305-8 Hiromoto Usui], [http://www.informatik.uni-trier.de/~ley/pers/hd/y/Yamashita:Masafumi.html Masafumi Yamashita], [http://www.informatik.uni-trier.de/~ley/pers/hd/i/Imai:Masaharu.html Masaharu Imai], [[Toshihide Ibaraki]] ('''1987'''). ''Parallel Searches of Game Tree''. Systems and Computer in Japan, Vol. 18, No. 8, pp. 97-109.
* [[Robert Hyatt]], [[Bruce W. Suter]], [[Harry Nelson]] ('''1989'''). ''A Parallel Alpha-Beta Tree Searching Algorithm''. Parallel Computing, Vol. 10, No. 3, pp. 299-308. ISSN 0167-8191.
* [[Igor Steinberg]], [[Marvin Solomon]] ('''1989'''). ''Searching Game Trees in Parallel''. Technical report 877, [ftp://ftp.cs.wisc.edu/pub/techreports/1989/TR877.pdf pdf]
* [[Richard Karp]], [[Yanjun Zhang]] ('''1989'''). ''[httphttps://dlwww.icsi.acmberkeley.orgedu/icsi/citation.cfm?id=72979&dl=ACM&coll=DL&CFID=67253533&CFTOKEN=20355103 node/2253 On parallel evaluation of game trees]''. [httphttps://www.informatikdblp.uni-trier.de/%7Eley/db/conf/spaa/spaa89.html SPAA '89]* [[Yanjun Zhang]] ('''1989'''). ''[https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5909.html Parallel Algorithms for Combinatorial Search Problems]''. Ph.D. thesis, [[University of California, Berkeley]], advisor [[Richard Karp]]
* [[Feng-hsiung Hsu]] ('''1989'''). ''Large Scale Parallelization of Alpha-beta Search: An Algorithmic and Architectural Study with Computer Chess''. Ph.D. thesis, Technical report CMU-CS-90-108, [[Carnegie Mellon University]], advisor [[Mathematician#Kung|Hsiang-Tsung Kung]]
==1990 ...==
* [[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1991''') ''A Fully Distributed Chess Program''. [[Advances in Computer Chess 6]], [http://www.top-5000.nl/ps/A%20fully%20distribuited%20chess%20program.pdf pdf]
* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1990'''). ''[https://www.sciencedirect.com/science/article/pii/030439759090192K A Complexity Theory of Efficient Parallel Algorithms]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science], Vol. 71
* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1990'''). ''[https://link.springer.com/article/10.1007/BF01840376 Efficient Parallel Algorithms for Graph Problems]''. [https://en.wikipedia.org/wiki/Algorithmica Algorithmica], Vol. 5, No. 1
'''1992'''
* [[Jaleh Rezaie]], [[Raphael Finkel]], ('''1992'''). ''[https://www.researchgate.net/publication/2813087_A_comparison_of_some_parallel_game-tree_search_algorithms_Revised_version A comparison of some parallel game-tree search algorithms]'', . [ftphttps://ftp.csen.ukywikipedia.eduorg/cswiki/techreports/214-92.ps.gz zipped postscriptUniversity_of_Kentucky University of Kentucky]
* [[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1992'''). ''Experiments with a Fully Distributed Chess Program''. [[3rd Computer Olympiad#Workshop|Heuristic Programming in AI 3]]
* [[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1992'''). ''Distributed Game Tree Search on a Massively Parallel System''. Data Structures and Efficient Algorithms, B. Monien, Th. Ottmann (eds.), Springer, Lecture Notes in Computer Science, 594, 1992, 270-288
==1995 ...==
* [[Bradley Kuszmaul|Bradley C. Kuszmaul]] ('''1995'''). ''The StarTech Massively Parallel Chess Program''. [http://supertech.csail.mit.edu/papers/startech.pdf pdf]
* [[Henri Bal]] and , [[Victor Allis]] ('''1995'''). ''Parallel Retrograde Analysis on a Distributed System''. Supercomputing ’95, San Diego, CA.
* [[Jean-Christophe Weill]] ('''1995'''). ''Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche''. Ph.D. Thesis. Université Paris 8, Saint-Denis, [http://www.recherche.enac.fr/%7Eweill/publications/phdJCW.ps.gz zipped ps] (French)
* [[Holger Hopp]], [[Peter Sanders]] ('''1995'''). ''Parallel Game Tree Search on SIMD Machines''. [http://www.informatik.uni-trier.de/~ley/db/conf/irregular/irregular95.html#HoppS95 IRREGULAR 1995], from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.6343 CiteSeerX]
* [[Tony Marsland]] and , [[Yaoqing Gao]] ('''1995'''). ''Speculative Parallelism Improves Search?'' Technical Report 95-05, Department of Computing Science, [[University of Alberta]], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.2187 CiteSeerX]
'''1996'''
* [[Jean-Christophe Weill]] ('''1996'''). ''The ABDADA Distributed Minimax Search Agorithm''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]
* [[Andrew Tridgell]] ('''1997'''). ''KnightCap — a parallel chess program on the AP1000+''. [ftp://us6.samba.org/pub/tridge/knightcap_pcw97.ps.gz zipped ps] » [[KnightCap]]
* [[Mark Brockington]], [[Jonathan Schaeffer]] ('''1997'''). ''APHID Game-Tree Search''. [[Advances in Computer Chess 8]]
* [[David Sturgill]] and , [[Alberto Maria Segre]] ('''1997'''). ''[http://www.springerlink.com/content/j11186905500t384/ Nagging: A Distributed, Adversarial Search-Pruning Technique Applied to First-Order Inference]''. [https://en.wikipedia.org/wiki/Journal_of_Automated_Reasoning Journal of Automated Reasoning], Vol. 19, No. 3 <ref>[https://en.wikipedia.org/wiki/Nagging Nagging from Wikipedia]</ref>
'''1998'''
* [[Mark Brockington]] ('''1998'''). ''Asynchronous Parallel Game-Tree Search''. Ph.D. Thesis, [[University of Alberta]], [http://games.cs.ualberta.ca/articles/mgb_thesis.ps.gz zipped postscript]
'''2001'''
* [[John Romein]] ('''2001'''). ''Multigame - An Environment for Distributed Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universiteit], supervisor [[Henri Bal]], [http://dare.ubvu.vu.nl/bitstream/1871/11305/1/5429.pdf pdf]
* [[Valavan Manohararajah]] ('''2001'''). ''Parallel Alpha-Beta Search on Shared Memory Multiprocessors''. Masters Thesis, [http://www.top-5000.nl/ps/Parallel%20Alpha-Beta%20Search%20on%20Shared%20Memory%20Multiprocessors.pdf pdf]
* [http://www.zib.de/schintke/ Florian Schintke], [http://pc2.uni-paderborn.de/people/jens-simon/ Jens Simon], [[Alexander Reinefeld]] ('''2001'''). ''A Cache Simulator for Shared Memory Systems''. International Conference on Computational Science ICCS 2001, San Francisco, CA, Springer LNCS 2074, vol. 2, pp. 569-578. [http://www.zib.de/reinefeld/Publications/ldasim-lncs.ps.gz zipped ps]
'''2002'''
* [[Yaron Shoham]], [[Sivan Toledo]] ('''2002'''). ''[https://www.sciencedirect.com/science/article/pii/S0004370202001959 Parallel Randomized Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 137, Nos. 1-2
* [[Akihiro Kishimoto]], [[Jonathan Schaeffer]]. ('''2002'''). ''Distributed Game-Tree Search Using Transposition Table Driven Work Scheduling'', In Proc. of 31st International Conference on Parallel Processing (ICPP'02), pages 323-330, IEEE Computer Society Press. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.8604&rep=rep1&type=pdf pdf] via [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.8604 CiteSeerX]
* [[Akihiro Kishimoto]], [[Jonathan Schaeffer]]. ('''2002'''). ''Transposition Table Driven Work Scheduling in Distributed Game-Tree Search'' (Best Paper Prize), In Proc. of Fifteenth Canadian Conference on Artificial Intelligence (AI'2002), volume 2338 of Lecture Notes in Artificial Intelligence (LNAI), pages 56-68, [http://www.springerlink.com/content/47b3crn04egmmx8l/ Springer]
* [[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf] » [[Transposition Table]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013</ref>
* [[Alberto Maria Segre]], [[Sean Forman]], [[Giovanni Resta]], [[Andrew Wildenberg]] ('''2002'''). ''[https://www.sciencedirect.com/science/article/pii/S000437020200228X Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence] 140, [http://jmvidalVol.cse.sc.edu/library/segre02a.pdf pdf]140, [http://compepiNos.cs.uiowa.edu/uploads/Profiles/Segre/nag.pdf pdf]1-2
'''2003'''
* [[Brian Greskamp]] ('''2003'''). ''Parallelizing a Simple Chess Program''. [http://iacoma.cs.uiuc.edu/~greskamp/pdfs/412.pdf pdf]
* [[Kai Himstedt]], [[Ulf Lorenz]], [http://www.informatik.uni-hamburg.de/TIS/index.php Dietmar P. F. Möller] ('''2008'''). ''A Twofold Distributed Game-Tree Search Approach Using Interconnected Clusters''. Euro-Par 2008: 587-598, [http://www.springerlink.com/content/2471845u5w6j1211/ abstract] from [http://www.springerlink.com/home/main.mpx springerlink]
* [[Tristan Cazenave]], [[Nicolas Jouandeau]] ('''2008'''). ''A Parallel Monte-Carlo Tree Search Algorithm''. [http://www.lamsade.dauphine.fr/~cazenave/papers/parallelMCTS.pdf pdf]
* [[James Swafford]] ('''2008'''). ''[https://fr.slideshare.net/JamesSwafford2/jfsmasters1 A Survey of Parallel Search Algorithms over Alpha-Beta Search Trees using Symmetric Multiprocessor Machines]''. Masters Project, [https://en.wikipedia.org/wiki/East_Carolina_University East Carolina University], advisor [http://www.cs.ecu.edu/rws/ Ronnie Smith]
'''2009'''
* [[Markus Enzenberger]], [[Martin Müller]] ('''2009'''). ''A lock-free multithreaded Monte-Carlo tree search algorithm'', [[Advances in Computer Games 12]], [http://webdocs.cs.ualberta.ca/~mmueller/ps/enzenberger-mueller-acg12.pdf pdf]
'''2014'''
* [https://plus.google.com/113202287320302059445/about Paul E. McKenney] ('''2014'''). ''[https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html Is Parallel Programming Hard, And, If So, What Can You Do About It?]''. [https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-e1p.pdf pdf]
* [[Lars Schaefers]] ('''2014'''). ''Parallel Monte-Carlo Tree Search for HPC Systems and its Application to Computer Go''. Ph.D. thesis, [[Paderborn University of Paderborn]], advisors [[Marco Platzner]], [[Ulf Lorenz]], [http://www.althofer.de/phd-thesis-schaefers.pdf pdf], [https://www.dropbox.com/s/x0lh7ky5lvj6c1y/PhdThesisSchaefers.pdf pdf]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2014'''). ''Performance analysis of a 240 thread tournament level MCTS Go program on the Intel Xeon Phi''. [http://arxiv.org/abs/1409.4297 CoRR abs/1409.4297] » [[Go]], [[Monte-Carlo Tree Search|MCTS]], [[x86-64]]
* [[Ting-Fu Liao]], [[I-Chen Wu]], [[Guan-Wun Chen]], [[Chung-Chin Shih]], [[Po-Ya Kang]], [[Bing-Tsung Chiang]], [[Ting-Chu Ho]], [[Ti-Rong Wu]] ('''2014'''). ''A Study of Software Framework for Parallel Monte Carlo Tree Search''. [[Conferences#GPW19|GPW-2014]]
* [[Shu Yokoyama]], [[Tomoyuki Kaneko]], [[Tetsuro Tanaka]] ('''2015'''). ''Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search''. [[Advances in Computer Games 14]]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Scaling Monte Carlo Tree Search on Intel Xeon Phi''. [http://arxiv.org/abs/1507.04383 CoRR abs/1507.04383] » [[Hex]], [[Monte-Carlo Tree Search|MCTS]], [[x86-64]]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Parallel Monte Carlo Tree Search from Multi-core to Many-core Processors''. [https://whova.com/portal/ieeet_201508/ TrustCom/BigDataSE/|ISPA 2015], [https://askeplaat.files.wordpress.com/2013/01/ispa2015.pdf pdf]
* [[Ting-Han Wei]], [[Chao-Chin Liang]], [[I-Chen Wu]], [[Lung-Pin Chen]] ('''2015'''). ''Software Development Framework for Job-Level Algorithms''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]]
* [[Akira Ura]], [[Yoshimasa Tsuruoka]], [[Takashi Chikayama]] ('''2015'''). ''[https://www.jstage.jst.go.jp/article/ipsjjip/23/1/23_9/_article Dynamic Prediction of Minimal Trees in Large-Scale Parallel Game Tree Search]''. [https://www.jstage.jst.go.jp/browse/ipsjjip/ Journal of Information Processing], Vol. 23, No. 1
* [[Jr-Chang Chen]], [[I-Chen Wu]], [[Wen-Jie Tseng]], [[Bo-Han Lin]], [[Chia-Hui Chang]] ('''2015'''). ''[https://ir.nctu.edu.tw/handle/11536/124541 Job-Level Alpha-Beta Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 1
* [[Lars Schaefers]], [[Marco Platzner]] ('''2015'''). ''[http://ieeexplore.ieee.org/document/6876158/ Distributed Monte Carlo Tree Search: A Novel Technique and its Application to Computer Go]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 4 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66125&start=18 Re: Minmax backup operator for MCTS] by [[Brahim Hamadicharef]], [[CCC]], December 30, 2017</ref>
'''2016'''* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2016'''). ''A New Method for Parallel Monte Carlo Tree Search''. [https://arxiv.org/abs/1605.04447 arXiv:1605.04447] » [[Monte-Carlo Tree Search|MCTS]]* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2016'''). ''An Efficient Computation Pattern for Parallel MCTS''. [http://www.ictopen.nl/content/Previous+editions ICT.OPEN 2016], [http://liacs.leidenuniv.nl/~plaata1/papers/ictopen2016.pdf pdf] '''2017'''* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2017'''). ''Structured Parallel Programming for Monte Carlo Tree Search''. [https://arxiv.org/abs/1704.00325 arXiv:1704.00325]* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2017'''). ''An Analysis of Virtual Loss in Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2017-2.html ICAART 2017], Vol. 2, [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART17.pdf pdf]'''2018'''* [[S. Ali Mirsoleimani]], [[Jaap van den Herik]], [[Aske Plaat]], [[Jos Vermaseren]] ('''2018'''). ''Pipeline Pattern for Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2018-2.html ICAART 2018], [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART18_pos.pdf pdf]* [[S. Ali Mirsoleimani]], [[Jaap van den Herik]], [[Aske Plaat]], [[Jos Vermaseren]] ('''2018'''). ''A Lock-free Algorithm for Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2018-2.html ICAART 2018], [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART18.pdf pdf]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=112849 tip for "simulating" an MP computer & performance of ABDADA] by [[Tom Kerrigan]], [[CCC]], May 28, 2000
* [https://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/ab55c5d57a3a1fd1 Re: Atomic write of 64 bits] by [[Frans Morsch]], [https://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], September 25, 2000
* [https://www.stmintz.com/ccc/index.php?id=163888 Parallel algorithms in chess programming] by [[Dieter Bürssner|Dieter BuerssnerBürßner]], [[CCC]], April 16, 2001 » [[ABDADA]]
* [https://www.stmintz.com/ccc/index.php?id=186273 Parallel search algorithms] by [[Scott Gasch]], [[CCC]], August 29, 2001
* [https://www.stmintz.com/ccc/index.php?id=189126 Chess over LAN revisited - APHID] by [[Gian-Carlo Pascutto]], [[CCC]], September 17, 2001 » [[APHID]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012 » [[Lazy SMP]]
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47171 Parallel search: System-level programming details] by [[Álvaro Begué]], [[CCC]], February 09, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47298 SMP search in Viper and idea about search in cluster system] by [[Chao Ma]], [[CCC]], February 22, 2013 » [[Viper]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48524 Measure of SMP scalability] by [[Edsel Apostol]], [[CCC]], July 03, 2013 » [[Hannibal]]
: [http://www.talkchess.com/forum/viewtopic.php?t=48591 Measure of SMP scalability (sub-thread)] by [[Ernest Bonnem]], [[CCC]], July 08, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Daniel Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChessEXchess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48612 use sleeping threads] by [[Don Dailey]], [[CCC]], July 10, 2013 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 2013 » [[Texel]], [[Recursion]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2378 DTS-like SMP] by [[Vadim Demichev|ThinkingALot]], [[Computer Chess Forums|OpenChess Forum]], July 25, 2013 » [[GullChess|Gull]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48780 Time to depth measuring tool] by [[Peter Österlund]], [[CCC]], July 28, 2013 » [[Depth]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49450 interesting SMP bug] by [[Robert Hyatt]], [[CCC]], September 24, 2013 » [[Crafty]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58946 Parallel Search to Fixed Depth] by [[Brian Richardson]], [[CCC]], January 17, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=58950 Threads test incl. Komodo 9.3] by [[Andreas Strangmüller]], [[CCC]], January 17, 2016 » [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by [[Kalyankumar Ramaseshan]], [[CCC]], February 29, 2016 » [[Lazy SMP]]
* [http://talkchess.com/forum/viewtopic.php?t=59745 Crafty SMP measurement] by [[Robert Hyatt]], [[CCC]], April 04, 2016 » [[Crafty]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60271 parallel search speed measurement] by [[Robert Hyatt]], [[CCC]], May 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=66044 Parallel search/LazySMP question] by [[Jon Dart]], [[CCC]], December 17, 2017 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66099 Time Managment translating to SMP] by [[Andrew Grant]], [[CCC]], December 23, 2017 » [[Time Management]]
'''2018'''
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68154 Lazy SMP and 44 cores] by [[Sander Maassen vd Brink]], [[CCC]], August 07, 2018 » [[Lazy SMP]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68278 Lazy SMP ideas] by [[Edsel Apostol]], [[CCC]], August 22, 2018
'''2019'''
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69481 Simplest way to implement quick and dirty lazy smp] by [[Tom King]], [[CCC]], January 04, 2019
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71115 OpenMP for chess programming] by BeyondCritics, [[CCC]], June 27, 2019
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71739 Multithreaded noob question] by [[Michael Sherwin]], [[CCC]], September 06, 2019
=External Links=
* [http://www.netlib.org/utk/lsi/pcwLSI/text/node350.html Parallel Alpha-Beta Pruning] from [http://www.netlib.org/utk/lsi/pcwLSI/text/BOOK.html Parallel Computing Works]
* [http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]
* [http://www2.cs.uni-paderborn.de/cs/ag-monien/PERSONAL/FLULO/gametree.html AG-Monien - Research - Game Trees], [[Burkhard Monien|AG-Monien]], [[Paderborn University of Paderborn]]
* [http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/cook98a-html/eureka.html Adaptive Parallel Iterative Deepening Search] by [http://portal.acm.org/author_page.cfm?id=81100111814&coll=GUIDE&dl=GUIDE&trk=0&CFID=85545608&CFTOKEN=17034339 Diane J. Cook], [http://portal.acm.org/author_page.cfm?id=81100529798&coll=GUIDE&dl=GUIDE&trk=0&CFID=85545608&CFTOKEN=17034339 R. Craig Varnell]
* [http://software.intel.com/en-us/articles/intel-parallel-universe-magazine/ Intel Parallel Universe Magazine - Intel® Software Network]
* [http://research.microsoft.com/en-us/projects/chess/ CHESS - Microsoft Research] a tool for finding and reproducing [https://en.wikipedia.org/wiki/Unusual_software_bug Heisenbugs] in concurrent programs.
* [[Videos#LedZeppelin:Category:Led Zeppelin|Led Zeppelin]] - [https://en.wikipedia.org/wiki/Communication_Breakdown Communication Breakdown], [https://en.wikipedia.org/wiki/YouTube YouTube] Video, Lost Performances (1/5)
: {{#evu:https://www.youtube.com/watch?v=-fG4JCerIuE|alignment=left|valignment=top}}
'''[[Search|Up one level]]'''
[[Category:Led Zeppelin]]
