25,161
edits
Changes
Created page with "'''Home * Search * Parallel Search * Jamboree''' '''Jamboree algorithm''',<br/> a parallelized version of the Scout search algorithm. Similar to the..."
'''[[Main Page|Home]] * [[Search]] * [[Parallel Search]] * Jamboree'''
'''Jamboree algorithm''',<br/>
a parallelized version of the [[Scout]] search algorithm. Similar to the [[Young Brothers Wait Concept]], the idea is that all of the testing of any child that is not the first one, is done in parallel, and any tests that fail are sequentially valued. Jamboree search was introduced by [[Bradley Kuszmaul]] in his [[Timeline#1994|1994]] thesis ''Synchronized MIMD Computing'' <ref>[[Bradley Kuszmaul]] ('''1994'''). ''Synchronized MIMD Computing''. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology]], [http://supertech.csail.mit.edu/papers/thesis-kuszmaul.pdf pdf]</ref> <ref>[https://en.wikipedia.org/wiki/MIMD MIMD From Wikipedia]</ref>.
Jamboree was used in the massive parallel chess programs [[StarTech]] and [[Star Socrates|*Socrates]]. It sequentialize full-window searches for values, because, while their authors are willing to take a chance that an [[Null Window|empty window]] search will be squandered work, they are not willing to take the chance that a full-window search (which does not prune very much) will be squandered work.
=Pseudo Code=
<ref>based on Figure 5: Algorithm Jamboree from [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]</ref>
<pre>
int jamboree(CNode n, int α, int β) {
if (n is leaf) return static_eval(n);
c[] = the childen of n;
b = -jamboree(c[0], -β, -α);
if (b >= β) return b;
if (b > α) α = b;
In Parallel: for (i=1; i < |c[]|; i++) {
s = -jamboree(c[i], -α - 1, -α);
if (s > b) b = s;
if (s >= β) abort_and_return s;
if (s > α) {
/* Wait for completion of all previous iterations of the parallel loop */
s = -jamboree(c[i], -β, -α);
if (s >= β) abort_and_return s;
if (s > α) α = s;
if (s > b) b = s;
}
/* Note the completion of the ith iteration of the parallel loop */
}
return b;
}
</pre>
=See also=
* [[ABDADA]]
* [[NegaScout]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
* [[Scout]]
* [[Star Socrates|*Socrates]]
* [[StarTech]]
* [[Young Brothers Wait Concept]]
=Publications=
<ref>[http://supertech.csail.mit.edu/papers.html SuperTech Paper Listing]</ref>
* [[Bradley Kuszmaul]] ('''1994'''). ''Synchronized MIMD Computing''. Ph. D. thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology|MIT]], [http://supertech.csail.mit.edu/papers/thesis-kuszmaul.pdf pdf]
* [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]
* [[Bradley Kuszmaul]] ('''1995'''). ''The StarTech Massively Parallel Chess Program''. [[ICGA Journal#18_1|ICCA Journal, Vol. 18, No. 1]], [http://supertech.csail.mit.edu/papers/startech.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Jamboree_%28Scouting%29 Jamboree (Scouting) from Wikipedia]
* [https://en.wikipedia.org/wiki/World_Scout_Jamboree World Scout Jamboree from Wikipedia]
* [https://en.wikipedia.org/wiki/Robert_Baden-Powell,_1st_Baron_Baden-Powell Robert Baden-Powell, 1st Baron Baden-Powell from Wikipedia]
* [http://www.scout.org/en/information_events/events/world_events/world_jamboree/jamborees_history Jamborees History / World Jamboree / World Events / Events / Information & Events / Home - World Organization of the Scout Movement]
* [[Videos#UrszulaDudziak|Urszula Dudziak]] with [[Videos#MichalUrbaniak|Michał Urbaniak]] - [http://www.allmusic.com/song/papaya-young-pale-man-ft-michael-urbaniak-mt0026585652 Papaya/Young Pale Man], [https://www.jpc.de/jpcng/jazz/detail/-/art/Urszula-Dudziak-For-You-Live-At-The-Warsaw-Jamboree-Jazz-Festival-1991/hnum/5560756 Warsaw Jamboree Jazz Festival 1991], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [https://pl.wikipedia.org/wiki/Zbigniew_Jakubek Zbgniew Jakubek], [https://pl.wikipedia.org/wiki/Adam_Wendt Adam Wendt], [https://pl.wikipedia.org/wiki/Bernard_Maseli Bernard Maseli], [http://www.discogs.com/artist/1260524-Marek-B%C5%82aszczyk Marek Blaszczyk], [http://www.walkaway.home.pl/chris.htm Krystof Zawdzki]
: {{#evu:https://www.youtube.com/watch?v=97-UPAcT_pk|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
'''Jamboree algorithm''',<br/>
a parallelized version of the [[Scout]] search algorithm. Similar to the [[Young Brothers Wait Concept]], the idea is that all of the testing of any child that is not the first one, is done in parallel, and any tests that fail are sequentially valued. Jamboree search was introduced by [[Bradley Kuszmaul]] in his [[Timeline#1994|1994]] thesis ''Synchronized MIMD Computing'' <ref>[[Bradley Kuszmaul]] ('''1994'''). ''Synchronized MIMD Computing''. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology]], [http://supertech.csail.mit.edu/papers/thesis-kuszmaul.pdf pdf]</ref> <ref>[https://en.wikipedia.org/wiki/MIMD MIMD From Wikipedia]</ref>.
Jamboree was used in the massive parallel chess programs [[StarTech]] and [[Star Socrates|*Socrates]]. It sequentialize full-window searches for values, because, while their authors are willing to take a chance that an [[Null Window|empty window]] search will be squandered work, they are not willing to take the chance that a full-window search (which does not prune very much) will be squandered work.
=Pseudo Code=
<ref>based on Figure 5: Algorithm Jamboree from [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]</ref>
<pre>
int jamboree(CNode n, int α, int β) {
if (n is leaf) return static_eval(n);
c[] = the childen of n;
b = -jamboree(c[0], -β, -α);
if (b >= β) return b;
if (b > α) α = b;
In Parallel: for (i=1; i < |c[]|; i++) {
s = -jamboree(c[i], -α - 1, -α);
if (s > b) b = s;
if (s >= β) abort_and_return s;
if (s > α) {
/* Wait for completion of all previous iterations of the parallel loop */
s = -jamboree(c[i], -β, -α);
if (s >= β) abort_and_return s;
if (s > α) α = s;
if (s > b) b = s;
}
/* Note the completion of the ith iteration of the parallel loop */
}
return b;
}
</pre>
=See also=
* [[ABDADA]]
* [[NegaScout]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
* [[Scout]]
* [[Star Socrates|*Socrates]]
* [[StarTech]]
* [[Young Brothers Wait Concept]]
=Publications=
<ref>[http://supertech.csail.mit.edu/papers.html SuperTech Paper Listing]</ref>
* [[Bradley Kuszmaul]] ('''1994'''). ''Synchronized MIMD Computing''. Ph. D. thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology|MIT]], [http://supertech.csail.mit.edu/papers/thesis-kuszmaul.pdf pdf]
* [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]
* [[Bradley Kuszmaul]] ('''1995'''). ''The StarTech Massively Parallel Chess Program''. [[ICGA Journal#18_1|ICCA Journal, Vol. 18, No. 1]], [http://supertech.csail.mit.edu/papers/startech.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Jamboree_%28Scouting%29 Jamboree (Scouting) from Wikipedia]
* [https://en.wikipedia.org/wiki/World_Scout_Jamboree World Scout Jamboree from Wikipedia]
* [https://en.wikipedia.org/wiki/Robert_Baden-Powell,_1st_Baron_Baden-Powell Robert Baden-Powell, 1st Baron Baden-Powell from Wikipedia]
* [http://www.scout.org/en/information_events/events/world_events/world_jamboree/jamborees_history Jamborees History / World Jamboree / World Events / Events / Information & Events / Home - World Organization of the Scout Movement]
* [[Videos#UrszulaDudziak|Urszula Dudziak]] with [[Videos#MichalUrbaniak|Michał Urbaniak]] - [http://www.allmusic.com/song/papaya-young-pale-man-ft-michael-urbaniak-mt0026585652 Papaya/Young Pale Man], [https://www.jpc.de/jpcng/jazz/detail/-/art/Urszula-Dudziak-For-You-Live-At-The-Warsaw-Jamboree-Jazz-Festival-1991/hnum/5560756 Warsaw Jamboree Jazz Festival 1991], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [https://pl.wikipedia.org/wiki/Zbigniew_Jakubek Zbgniew Jakubek], [https://pl.wikipedia.org/wiki/Adam_Wendt Adam Wendt], [https://pl.wikipedia.org/wiki/Bernard_Maseli Bernard Maseli], [http://www.discogs.com/artist/1260524-Marek-B%C5%82aszczyk Marek Blaszczyk], [http://www.walkaway.home.pl/chris.htm Krystof Zawdzki]
: {{#evu:https://www.youtube.com/watch?v=97-UPAcT_pk|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
