All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
alphaBeta2Parallel.cc
Go to the documentation of this file.
1 /* alphaBeta2Parallel.cc
2  */
3 #ifdef OSL_SMP
4 
9 #include <boost/foreach.hpp>
10 #include <iostream>
11 #include <bitset>
12 #ifdef _WIN32
13 # include <malloc.h>
14 #endif
15 
16 #define DEBUG_SMP 0
17 #define ONLY_HELP_DESCENDANT
18 // #define OSL_BUSY_WAIT
19 
20 /* ------------------------------------------------------------------------- */
21 struct osl::search::AlphaBeta2ParallelCommon::LivingThreadLock
22 {
23  AlphaBeta2ParallelCommon *shared;
24  LivingThreadLock(AlphaBeta2ParallelCommon *s) : shared(s)
25  {
26  boost::mutex::scoped_lock lk(shared->living_threads_lock);
27  shared->living_threads += 1;
28  shared->living_threads_condition.notify_one();
29  }
30  ~LivingThreadLock()
31  {
32  boost::mutex::scoped_lock lk(shared->living_threads_lock);
33  shared->living_threads -= 1;
34  shared->living_threads_condition.notify_one();
35  }
36 };
37 
38 /* ------------------------------------------------------------------------- */
39 template <class EvalT>
41 Worker::Worker(int tid, AlphaBeta2Parallel *s) : shared(s), thread_id(tid)
42 {
43 }
44 
45 template <class EvalT>
46 void
47 #ifdef __GNUC__
48 # ifdef _WIN32
49 __attribute__((noinline))
50 __attribute__((force_align_arg_pointer))
51 # endif
52 #endif
54 {
55 #if DEBUG_SMP > 1
56  {
57  boost::mutex::scoped_lock lk(OslConfig::lock_io);
58  std::cerr << "thread " << thread_id << " started\n";
59  }
60 #endif
61  try {
62  AlphaBeta2ParallelCommon::LivingThreadLock lk(shared);
63  shared->threadWait(thread_id, -1);
64  }
65  catch (std::exception& e) {
66  std::cerr << "warning caught exception in thread root " << e.what() << "\n";
67  }
68  catch (...) {
69  std::cerr << "warning caught unknown exception in thread root\n";
70  }
71 }
72 
73 /* ------------------------------------------------------------------------- */
74 
75 static osl::misc::AtomicCounter parallel_counter;
76 
77 osl::search::AlphaBeta2ParallelCommon::
78 AlphaBeta2ParallelCommon()
79  : smp_idle(0), quit(false),
80  parallel_splits(0), max_split_depth(0), descendant_reject(0), descendant_test(0),
81  living_threads(0), max_threads(OslConfig::numCPUs()), max_thread_group(5),
82  split_min_limit(400), my_id(parallel_counter.valueAndinc()), started(false)
83 {
84  job.fill(0);
85  info[0].thread_id = 0;
86  info[0].used = true;
87  info[0].parent = -1;
88  waiting.fill(0);
89 
90  threads.fill(0);
91  checkmate.fill(0);
92  for (int i=1; i<max_threads; ++i) {
93  threads[i] = 0;
94  checkmate[i] = 0;
95  }
96 }
97 
98 osl::search::AlphaBeta2ParallelCommon::
99 ~AlphaBeta2ParallelCommon()
100 {
101  waitAll();
102  for (int i=1; i<max_threads; ++i) {
103  delete checkmate[i];
104  }
105 #if DEBUG_SMP > 1
106  std::cerr << "<= AlphaBeta2Parallel " << my_id << "\n";
107 #endif
108 #if DEBUG_SMP > 2
109  std::cerr << "descendant_reject " << descendant_reject
110  << " / " << descendant_test << " = " << (double)descendant_reject/descendant_test << "\n";
111  std::cerr << "max_split_depth " << max_split_depth << "\n";
112 #endif
113 }
114 
115 void osl::search::
116 AlphaBeta2ParallelCommon::waitAll() {
117 #ifndef OSL_BUSY_WAIT
118  {
119  boost::mutex::scoped_lock lk(lock_smp);
120 #endif
121  quit = true;
122  started = false;
123 #ifndef OSL_BUSY_WAIT
124  condition_smp.notify_all();
125  }
126 #endif
127  boost::mutex::scoped_lock lk(living_threads_lock);
128  while (living_threads != (quit ? 0 : smp_idle)) {
129  living_threads_condition.wait(lk);
130  }
131  for (int i=1; i<max_threads; ++i) {
132  delete threads[i];
133  threads[i] = 0;
134  }
135 }
136 
137 bool osl::search::AlphaBeta2ParallelCommon::isDescendant(int elder, int younger)
138 {
139 #ifndef ONLY_HELP_DESCENDANT
140  return true;
141 #else
142  ++descendant_test;
143  if (elder < 0)
144  return true;
145  while (younger >= 0) {
146  if (elder == younger)
147  return true;
148  younger = info[younger].parent;
149  }
150  ++descendant_reject;
151  return false;
152 #endif
153 }
154 
155 /* ------------------------------------------------------------------------- */
156 
157 template <class EvalT>
159 AlphaBeta2Parallel(AlphaBeta2Tree<EvalT> *m)
160  : AlphaBeta2ParallelCommon(), master(m)
161 {
162 #if DEBUG_SMP > 0
163  std::cerr << "=> AlphaBeta2Parallel " << max_threads << " threads ";
164 # if DEBUG_SMP > 1
165  std::cerr << " id " << my_id;
166 # endif
167  std::cerr << "\n";
168 #endif
169  tree.fill(0);
170  tree[0] = master;
171  checkmate[0] = checkmateSearcher(*master);
172 }
173 
174 template <class EvalT>
177 {
178 }
179 
180 template <class EvalT>
182 threadStart()
183 {
184  if (started)
185  return;
186  started = true;
187  quit = false;
188  int i=1;
189  for (; i<max_threads; ++i) {
190  int j=0, max_retry=4;
191  for (; j<max_retry; ++j) {
192  try
193  {
194  if (! checkmate[i])
195  checkmate[i] = new checkmate_t(master->checkmateSearcher());
196  threads[i] = new boost::thread(Worker(i, this));
197  break;
198  }
199  catch (std::exception& e)
200  {
201  std::cerr << e.what() << "\n";
202  }
203  std::cerr << "wait for thread " << i << " started\n";
204  const int microseconds = (j+1)*100000;
205 #ifdef _WIN32
206  boost::this_thread::sleep(boost::posix_time::microseconds(microseconds));
207 #else
208  usleep(microseconds);
209 #endif
210  NonBlockDelete::deleteAll();
211  }
212  if (j == max_retry)
213  break;
214  }
215  if (i < max_threads)
216  {
217  std::cerr << "error in start thread #" << i << "\n";
218  for (int j=i; j<max_threads; ++j) {
219  delete checkmate[j];
220  checkmate[j] = 0;
221  }
222  max_threads = i;
223  }
224  boost::mutex::scoped_lock lk(living_threads_lock);
225  while (living_threads+1 != max_threads) {
226  living_threads_condition.wait(lk);
227  }
228 }
229 
230 template <class EvalT>
232 search(int tree_id)
233 {
234  TreeInfo *info = &this->info[tree_id];
235  assert(tree[tree_id]);
236  if (info->is_root)
237  tree[tree_id]->examineMovesRootPar(tree_id);
238  else
239  tree[tree_id]->examineMovesOther(tree_id);
240 }
241 
242 template <class EvalT>
243 int osl::search::
244 AlphaBeta2Parallel<EvalT>::treeId(AlphaBeta2Tree<EvalT> *t)
245 {
246  if (t == master)
247  return 0;
248  for (size_t i=1; i<tree.size(); ++i)
249  if (t == tree[i])
250  return i;
251  assert(0);
252  abort();
253 }
254 
255 template <class EvalT>
257 threadWait(int thread_id, int waiting)
258 {
259 #if DEBUG_SMP > 2
260  {
261  boost::mutex::scoped_lock lk(OslConfig::lock_io);
262  std::cerr << "thread " << thread_id << " ready, waiting " << waiting << "\n";
263  }
264 #endif
265  while (1) {
266  this->waiting[thread_id] = waiting;
267  {
268  boost::mutex::scoped_lock lk(lock_smp);
269  smp_idle++;
270  }
271  {
272 #ifndef OSL_BUSY_WAIT
273  boost::mutex::scoped_lock lk(lock_smp);
274 #endif
275  while (! job[thread_id]
276  && ! quit
277  && (waiting < 0 || info[waiting].nprocs))
278  {
279 #ifndef OSL_BUSY_WAIT
280  condition_smp.wait(lk);
281 #endif
282  }
283 
284  if (quit) {
285  {
286 #ifdef OSL_BUSY_WAIT
287  boost::mutex::scoped_lock lk(lock_smp);
288 #endif
289  --smp_idle;
290  }
291 #if DEBUG_SMP > 1
292  boost::mutex::scoped_lock lk(OslConfig::lock_io);
293  std::cerr << "thread " << thread_id << " exiting\n";
294 #endif
295  return;
296  }
297  {
298 #ifdef OSL_BUSY_WAIT
299  boost::mutex::scoped_lock lk(lock_smp);
300 #endif
301  if (! job[thread_id])
302  job[thread_id] = waiting;
303  --smp_idle;
304  }
305  }
306 
307  if (job[thread_id] == waiting) {
308 #ifndef NDEBUG
309  if (waiting >= 0) {
310  for (int i=0; i<max_threads; ++i) {
311  assert(info[waiting].siblings[i] == 0);
312  }
313  assert(info[waiting].nprocs == 0);
314  }
315 #endif
316 #if DEBUG_SMP > 3
317  boost::mutex::scoped_lock lk(OslConfig::lock_io);
318  std::cerr << "thread " << thread_id << " go up "
319  << waiting << " " << info[job[thread_id]].best_move << "\n";
320 #endif
321  return;
322  }
323 
324  if (quit || job[thread_id] == -1) {
325  return;
326  }
327  int my_job = job[thread_id];
328 #if DEBUG_SMP > 3
329  {
330  boost::mutex::scoped_lock lk(OslConfig::lock_io);
331  std::cerr << "thread " << thread_id << " go to job " << my_job << " waiting " << waiting << "\n";
332  if (! tree[my_job]) {
333  std::cerr << "thread " << thread_id << " null job " << my_job << " waiting " << waiting << "\n";
334  }
335  }
336 #endif
337 
338  assert(tree[my_job]);
339  search(my_job);
340 
341  int parent = info[my_job].parent;
342  boost::mutex::scoped_lock lk(lock_smp);
343  {
344  SCOPED_LOCK(lk,info[parent].lock);
345  copyToParent(parent, my_job);
346  info[parent].nprocs--;
347  info[parent].siblings[thread_id] = 0;
348 #ifndef OSL_BUSY_WAIT
349  if (info[parent].nprocs == 0)
350  condition_smp.notify_all();
351 #endif
352  }
353  job[thread_id] = 0;
354  delete tree[my_job];
355  tree[my_job] = 0;
356 #if DEBUG_SMP > 3
357  {
358  boost::mutex::scoped_lock lk(OslConfig::lock_io);
359  std::cerr << "thread " << thread_id << " back from job " << my_job << " waiting " << waiting;
360  if (waiting >= 0)
361  std::cerr << " rest " << info[waiting].nprocs;
362  std::cerr << "\n";
363  }
364 #endif
365  }
366 }
367 
368 template <class EvalT>
370 split(AlphaBeta2Tree<EvalT> *tree, int tree_id, int thread_id, int max_split)
371 {
372  TreeInfo *pinfo = &info[tree_id];
373 #if DEBUG_SMP > 2
374  {
375  unsigned int depth = 0;
376  int parent = pinfo->parent;
377  while (parent >= 0)
378  ++depth, parent = info[parent].parent;;
379  max_split_depth = std::max(depth, max_split_depth);
380  }
381  for (int i=0; i<max_threads; ++i) {
382  assert(pinfo->siblings[i] == 0);
383  }
384 #endif
385  assert(tree == master || tree == this->tree[tree_id]);
386  {
387  boost::mutex::scoped_lock lk(lock_smp);
388  {
389  int tid=0;
390  for (; tid<max_threads && job[tid]; ++tid)
391  ;
392  if (tid == max_threads || tree->stop_tree)
393  return false;
394  }
395 
396  parallel_splits++;
397  job[pinfo->thread_id] = 0;
398  pinfo->nprocs = 0;
399 
400  int nblocks = 0;
401  if (const int child_id = copyToChild(tree_id, thread_id))
402  {
403  // first, assgin job to splitting thread
404  nblocks++;
405  pinfo->siblings[thread_id] = child_id;
406  info[child_id].thread_id = thread_id;
407  info[child_id].parent = tree_id;
408  pinfo->nprocs++;
409  }
410  if (max_split <= 0)
411  max_split = std::max(max_threads/2, max_thread_group);
412  else
413  max_split = std::min(max_split, std::max(max_threads/2, max_thread_group));
414  for (int tid = 0;
415  tid < max_threads && nblocks < max_split;
416  ++tid) {
417  assert(pinfo->siblings[tid] == 0 || tid == thread_id);
418  if (job[tid] || tid == thread_id) // he is working
419  continue;
420  if (! isDescendant(waiting[tid], pinfo->parent))
421  continue;
422  int child_id = copyToChild(tree_id, tid);
423  if (!child_id)
424  continue;
425 #if DEBUG_SMP > 3
426  {
427  boost::mutex::scoped_lock lk(OslConfig::lock_io);
428  std::cerr << "split " << tree_id << " in " << thread_id << " => " << child_id << " in " << tid << "\n";
429  }
430 #endif
431  nblocks++;
432  pinfo->siblings[tid] = child_id;
433  info[child_id].thread_id = tid;
434  info[child_id].parent = tree_id;
435  pinfo->nprocs++;
436  }
437  pinfo->search_value = pinfo->value;
438 
439  if (!nblocks) {
440  job[pinfo->thread_id] = tree_id;
441  return false;
442  }
443 
444  for (int tid=0; tid< max_threads; ++tid)
445  if (pinfo->siblings[tid])
446  job[tid] = pinfo->siblings[tid];
447  }
448 #ifndef OSL_BUSY_WAIT
449  condition_smp.notify_all();
450 #endif
451  threadWait(pinfo->thread_id, tree_id);
452 
453  return true;
454 }
455 
456 template <class EvalT>
457 void osl::search::
459 {
460  TreeInfo *info = &this->info[tree_id];
461  AlphaBeta2Tree<EvalT> *tree = this->tree[tree_id];
462  SCOPED_LOCK(lk,info->lock);
463  tree->stop_tree = true;
464  for (int tid = 0; tid<max_threads; tid++)
465  if (info->siblings[tid])
466  stopThread(info->siblings[tid]);
467 }
468 
469 template <class EvalT>
470 void osl::search::
471 AlphaBeta2Parallel<EvalT>::copyToParent(int parent, int child)
472 {
473  TreeInfo *c = &info[child];
474  AlphaBeta2Tree<EvalT> *cc = tree[child], *pp = tree[parent];
475  c->used = 0;
476  pp->node_count += cc->nodeCount();
477  pp->mpn.merge(cc->mpn);
478  pp->mpn_cut.merge(cc->mpn_cut);
479  pp->alpha_update.merge(cc->alpha_update);
480  pp->last_alpha_update.merge(cc->last_alpha_update);
481  pp->ext.merge(cc->ext);
482  pp->ext_limit.merge(cc->ext_limit);
483 }
484 
485 template <class EvalT>
486 int osl::search::
487 AlphaBeta2Parallel<EvalT>::copyToChild(int parent, int thread_id)
488 {
489  static int warnings = 0;
490  int first = thread_id * MaxBlocksPerCpu + 1;
491  int last = first + MaxBlocksPerCpu;
492  int maxb = max_threads * MaxBlocksPerCpu + 1;
493 
494  int cid=first;
495  for (; cid < last && info[cid].used; cid++)
496  ;
497 
498  if (cid >= last) {
499  if (++warnings < 6) {
500  boost::mutex::scoped_lock lk(OslConfig::lock_io);
501  std::cerr << "WARNING. optimal SMP block cannot be allocated, thread "
502  << thread_id << "\n";
503  }
504  for (cid=1; cid<maxb && info[cid].used; cid++)
505  ;
506  if (cid >= maxb) {
507  if (warnings < 6) {
508  boost::mutex::scoped_lock lk(OslConfig::lock_io);
509  std::cerr << "ERROR. no SMP block can be allocated\n";
510  }
511  return 0;
512  }
513  }
514 
515  TreeInfo *c = &info[cid], *p = &info[parent];
516  try
517  {
518  assert(tree[cid] == 0);
519  tree[cid] = new AlphaBeta2Tree<EvalT>(*tree[parent], this);
520  }
521  catch (std::bad_alloc&)
522  {
523  boost::mutex::scoped_lock lk(OslConfig::lock_io);
524  std::cerr << "ERROR. split failed due to bad_alloc\n";
525  return 0;
526  }
527  c->set(*p, max_threads);
528  tree[cid]->setCheckmateSearcher(checkmate[thread_id]);
529 
530  return cid;
531 }
532 
533 template <class EvalT>
534 const std::pair<osl::MoveLogProb,size_t> osl::search::
536 {
537  int parent = info[tree_id].parent;
538  TreeInfo *info = &this->info[parent];
539  SCOPED_LOCK(lk,info->lock);
540  const size_t old_index = info->move_index;
541  if (tree[parent]->stop_tree)
542  return std::make_pair(MoveLogProb(), old_index);
543  if (info->is_root) {
544  if (old_index < info->moves.size()) {
545  ++(info->move_index);
546  return std::make_pair(info->moves[old_index], old_index);
547  }
548  return std::make_pair(MoveLogProb(), old_index);
549  }
550  else {
551  MoveLogProb m = (info->turn == BLACK)
552  ? tree[parent]->template nextMove<BLACK>()
553  : tree[parent]->template nextMove<WHITE>();
554  if (m.validMove()) {
555  assert(m.player() == info->turn);
556  ++(info->move_index);
557  }
558  return std::make_pair(m, old_index);
559  }
560 }
561 
562 template <class EvalT>
563 size_t osl::search::
565 {
566  return master->checkmateSearcher().totalNodeCount();
567 }
568 
569 template <class EvalT>
570 size_t osl::search::
572 {
573  return master->checkmateSearcher().mainNodeCount();
574 }
575 
576 /* ------------------------------------------------------------------------- */
577 
578 template <class EvalT>
579 template <osl::Player P>
580 void osl::search::
581 AlphaBeta2Tree<EvalT>::testMoveRoot(int tree_id, const MoveLogProb& m)
582 {
583  if (stop_tree) {
584  std::cerr << "root tree stop\n";
585  return;
586  }
587 
588  Window w;
589  AlphaBeta2ParallelCommon::TreeInfo *parent = shared->parent(tree_id);
590  {
591  SCOPED_LOCK(lk,parent->lock);
592  w = parent->window;
593  assert(w.isConsistent());
594  }
595  assert(P == m.player());
596 #ifndef GPSONE
597  if (this->multi_pv) {
598  int width = this->multi_pv*this->eval.captureValue(newPtypeO(P, PAWN))/200;
599  if (width % 2 == 0)
600  width -= EvalTraits<P>::delta;
601  w.alpha(P) = parent->search_value + width;
602  }
603 #endif
604  const int result = alphaBetaSearch<P>(m, w, false);
605 
606  if (eval::betterThan(P, result, parent->search_value)) {
607  makePV(m.move());
608  if (eval::betterThan(P, result, w.beta(P))) {
609  {
610  boost::mutex::scoped_lock lk_smp(shared->lock_smp);
611  SCOPED_LOCK(lk,parent->lock);
612  if (! stop_tree) {
613 #if DEBUG_SMP > 2
614  std::cerr << "beta cut root " << tree_id << "\n";
615 #endif
616  for (int tid=0; tid<shared->max_threads; tid++)
617  if (parent->siblings[tid] && tid != shared->info[tree_id].thread_id)
618  shared->stopThread(parent->siblings[tid]);
619  }
620  }
621  shared->parallel_abort.inc();
622  }
623  SCOPED_LOCK(lk,parent->lock);
624  if (! stopping()
625  && (eval::betterThan(P, result, parent->search_value))) {
626  assert(parent->window.isConsistent());
627  parent->window.alpha(P) = result + EvalTraits<P>::delta;
628  parent->best_move = m;
629  parent->search_value = result;
630  updateRootPV(P, std::cerr, result, m.move());
631  assert(parent->window.isConsistent());
632  shared->tree[shared->parentID(tree_id)]->pv[0] = pv[0];
633  }
634  }
635 #ifndef GPSONE
636  else if (this->multi_pv && !stopping()
637  && eval::betterThan(P, result, w.alpha(P)))
638  addMultiPV(P, result, m.move());
639 #endif
640 }
641 
642 template <class EvalT>
643 template <osl::Player P>
645 examineMovesRootPar(const MoveLogProbVector& moves, size_t start, Window window,
646  MoveLogProb& best_move, int& best_value)
647 {
648  const int id = shared->treeId(this);
649 #if DEBUG_SMP > 3
650  {
651  boost::mutex::scoped_lock lk(OslConfig::lock_io);
652  std::cerr << "start split root " << id << " turn " << P << " parent " << shared->info[id].parent << "\n";
653  history().dump();
654  }
655 #endif
656  AlphaBeta2ParallelCommon::TreeInfo *info = &shared->info[id];
657  info->window = window;
658  info->is_root = true;
659  info->in_pv = false;
660  info->value = best_value;
661  info->moves = moves;
662  info->move_index = start;
663  info->turn = P;
664  info->best_move = best_move;
665  if (! shared->split(this, id, info->thread_id, -1)) {
666  shared->cancelled_splits.inc();
667  throw AlphaBeta2ParallelCommon::SplitFailed();
668  }
669  SCOPED_LOCK(lk,info->lock);
670  best_value = info->search_value;
671  best_move = info->best_move;
672 }
673 
674 template <class EvalT>
676 examineMovesRootPar(int tree_id)
677 {
678  AlphaBeta2ParallelCommon::TreeInfo *info = &shared->info[tree_id];
679  const Player my_turn = info->turn;
680  for (MoveLogProb m = shared->nextMove(tree_id).first;
681  m.validMove() && ! stopping();
682  m = shared->nextMove(tree_id).first) {
683 #ifndef GPSONE
684  if (this->elapsed() > 1.0)
685  {
686  boost::mutex::scoped_lock lk(OslConfig::lock_io);
687  BOOST_FOREACH(const boost::shared_ptr<SearchMonitor>& monitor,
688  this->monitors())
689  monitor->rootMove(m.move());
690  }
691 #endif
692  try {
693  if (my_turn == BLACK)
694  testMoveRoot<BLACK>(tree_id, m);
695  else
696  testMoveRoot<WHITE>(tree_id, m);
697  if (this->root_limit >= 1600)
698  this->checkmate_searcher->runGC(this->table->isVerbose(),
699  lastMemoryUseRatio1000());
700  }
701  catch (BetaCut& e) {
702  std::cerr << "caught BetaCut at root " << info->thread_id << "\n";
703  assert(stop_tree);
704  break;
705  }
706  catch (std::runtime_error&) {
707  stop_tree = true;
708  this->stopNow();
709  break;
710  }
711  catch (std::exception& e) {
712 #if DEBUG_SMP > 0
713  boost::mutex::scoped_lock lk(OslConfig::lock_io);
714  std::cerr << "caught " << e.what() << " at root " << info->thread_id << "\n";
715 #endif
716  stop_tree = true;
717  this->stopNow();
718  break;
719  }
720  catch (...) {
721  boost::mutex::scoped_lock lk(OslConfig::lock_io);
722  std::cerr << "caught something at root " << info->thread_id << "\n";
723  stop_tree = true;
724  this->stopNow();
725  break;
726  }
727  }
728  // cut or no more moves to search
729 }
730 
731 template <class EvalT>
732 template <osl::Player P>
733 bool osl::search::
734 AlphaBeta2Tree<EvalT>::testMoveOther(int tree_id, const MoveLogProb& m, size_t index,
735  bool in_pv)
736 {
737  if (stopping())
738  return false;
739 
740  Window w;
741  AlphaBeta2ParallelCommon::TreeInfo *parent = shared->parent(tree_id);
742  {
743  SCOPED_LOCK(lk,parent->lock);
744  w = parent->window;
745  }
746  assert(w.isConsistent() || stop_tree);
747  if (stopping())
748  return false;
749  assert(P == m.player());
750  const int result = alphaBetaSearch<P>(m, w, in_pv);
751  if (stopping())
752  return false;
753 
754  bool cut = false;
755  int parent_search_value;
756  {
757 #ifdef OSL_USE_RACE_DETECTOR
758  SCOPED_LOCK(lk,parent->lock);
759 #endif
760  parent_search_value = parent->search_value;
761  }
762  if (eval::betterThan(P, result, parent_search_value)) {
763  makePV(m.move());
764  if (eval::betterThan(P, result, w.beta(P))) {
765  cut = true;
766  {
767  boost::mutex::scoped_lock lk_smp(shared->lock_smp);
768  SCOPED_LOCK(lk,parent->lock);
769  if (! stop_tree) {
770 #if DEBUG_SMP > 2
771  std::cerr << "beta cut " << tree_id << "\n";
772 #endif
773  for (int tid=0; tid<shared->max_threads; tid++)
774  if (parent->siblings[tid] && tid != shared->info[tree_id].thread_id)
775  shared->stopThread(parent->siblings[tid]);
776  }
777  }
778  shared->parallel_abort.inc();
779  }
780  SCOPED_LOCK(lk,parent->lock);
781  if (! stopping() && eval::betterThan(P, result, parent->search_value)) {
782  parent->window.alpha(P) = result + EvalTraits<P>::delta;
783  parent->best_move = m;
784  parent->search_value = result;
785  parent->alpha_update++;
786  parent->last_alpha_update = index;
787  assert(cut || shared->tree[shared->info[tree_id].parent]->stop_tree
788  || parent->window.isConsistent());
789  AlphaBeta2Tree *pp = shared->tree[shared->parentID(tree_id)];
790  pp->pv[pp->curDepth()] = pv[curDepth()];
791  if (cut)
792  return true;
793  }
794  }
795  return false;
796 }
797 
798 template <class EvalT>
799 template <osl::Player P>
801 examineMovesOther(Window& w, MoveLogProb& best_move, int& best_value,
802  int& tried_moves, int& alpha_update, int& last_alpha_update)
803 {
804  assert(w.isConsistent());
805 
806  const int id = shared->treeId(this);
807 #if DEBUG_SMP > 3
808  {
809  boost::mutex::scoped_lock lk(OslConfig::lock_io);
810  std::cerr << "start split at " << curLimit() << " " << id << " turn " << P
811  << " move " << tried_moves
812  << " parent " << shared->info[id].parent << "\n";
813  history().dump();
814  }
815 #endif
816  AlphaBeta2ParallelCommon::TreeInfo *info = &shared->info[id];
817  info->window = w;
818  info->is_root = false;
819  info->in_pv = (! w.null()) && (! best_move.validMove());
820  info->value = best_value;
821  info->move_index = tried_moves;
822  info->turn = P;
823  info->best_move = best_move;
824  info->alpha_update = alpha_update;
825  info->last_alpha_update = last_alpha_update;
826  if (! shared->split(this, id, info->thread_id, shared->max_thread_group)) {
827 #if DEBUG_SMP > 2
828  boost::mutex::scoped_lock lk(OslConfig::lock_io);
829  std::cerr << "failed split " << id << " turn " << P << "\n";
830  for (int i=0; i<shared->max_threads; ++i) {
831  std::cerr << " " << i << " " << shared->job[i] << "\n";
832  }
833 #endif
834  shared->cancelled_splits.inc();
835  throw AlphaBeta2ParallelCommon::SplitFailed();
836  }
837  SCOPED_LOCK(lk,info->lock);
838  best_value = info->search_value;
839  best_move = info->best_move;
840  w = info->window;
841  tried_moves = info->move_index;
842  alpha_update += info->alpha_update;
843  last_alpha_update = info->last_alpha_update;
844 #if DEBUG_SMP > 3
845  {
846  boost::mutex::scoped_lock lk(OslConfig::lock_io);
847  std::cerr << "back from split at " << curLimit() << " " << id << " turn " << P << " parent " << shared->info[id].parent << "\n";
848  }
849 #endif
850  testStop();
851  return EvalTraits<P>::betterThan(best_value, w.beta(P));
852 }
853 
854 template <class EvalT>
856 examineMovesOther(int tree_id)
857 {
858  AlphaBeta2ParallelCommon::TreeInfo *parent = shared->parent(tree_id);
859  for (std::pair<MoveLogProb,size_t> m = shared->nextMove(tree_id); m.first.validMove() && !stopping();
860  m = shared->nextMove(tree_id)) {
861  bool in_pv = parent->in_pv;
862  if (in_pv) {
863  in_pv = ! parent->best_move.validMove();
864  }
865  assert(parent->turn == m.first.player());
866  try {
867  const bool cut_by_move =
868  (parent->turn == BLACK)
869  ? testMoveOther<BLACK>(tree_id, m.first, m.second, in_pv)
870  : testMoveOther<WHITE>(tree_id, m.first, m.second, in_pv);
871  if (cut_by_move) {
872  break;
873  }
874  testStop();
875  }
876  catch (BetaCut&) {
877  assert(stop_tree);
878  }
879  catch (TableFull&) {
880  stop_tree = true;
881  this->stopNow();
882  break;
883  }
884  catch (misc::NoMoreTime&) {
885  stop_tree = true;
886  this->stopNow();
887 #if DEBUG_SMP > 2
888  boost::mutex::scoped_lock lk(OslConfig::lock_io);
889  std::cerr << "caught timeout in tree " << tree_id << " thread " << shared->info[tree_id].thread_id << "\n";
890 #endif
891  break;
892  }
893  catch (NoMoreMemory&) {
894  stop_tree = true;
895  this->stopNow();
896 #if DEBUG_SMP > 2
897  boost::mutex::scoped_lock lk(OslConfig::lock_io);
898  std::cerr << "caught memory full in tree " << tree_id << " thread " << shared->info[tree_id].thread_id << "\n";
899 #endif
900  break;
901  }
902  catch (std::exception& e) {
903  this->stopNow();
904  stop_tree = true;
905  boost::mutex::scoped_lock lk(OslConfig::lock_io);
906  std::cerr << "caught exception at " << tree_id << " " << e.what() << "\n";
907  break;
908  }
909  catch (...) {
910  boost::mutex::scoped_lock lk(OslConfig::lock_io);
911  std::cerr << "caught unknown exception at " << tree_id << "\n";
912  throw;
913  }
914  }
915  // cut or no more moves to search
916 }
917 
918 namespace osl
919 {
920  namespace search
921  {
922 #ifndef MINIMAL
923  template struct AlphaBeta2Parallel<eval::ProgressEval>;
924 
925  template
926  bool AlphaBeta2Tree<eval::ProgressEval>::examineMovesOther<BLACK>(Window&, MoveLogProb&, int&, int&, int&, int&);
927  template
928  bool AlphaBeta2Tree<eval::ProgressEval>::examineMovesOther<WHITE>(Window&, MoveLogProb&, int&, int&, int&, int&);
929 
930  template
931  void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRootPar<BLACK>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
932  template
933  void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRootPar<WHITE>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
934 #endif
935  template struct AlphaBeta2Parallel<eval::ml::OpenMidEndingEval>;
936 
937  template
938  bool AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesOther<BLACK>(Window&, MoveLogProb&, int&, int&, int&, int&);
939  template
940  bool AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesOther<WHITE>(Window&, MoveLogProb&, int&, int&, int&, int&);
941 
942  template
943  void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRootPar<BLACK>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
944  template
945  void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRootPar<WHITE>(const MoveLogProbVector&, size_t, Window, MoveLogProb&, int&);
946  }
947 }
948 
949 #endif /* OSL_SMP */
950 /* ------------------------------------------------------------------------- */
951 // ;;; Local Variables:
952 // ;;; mode:c++
953 // ;;; c-basic-offset:2
954 // ;;; End: