9 #include <boost/foreach.hpp>
17 #define ONLY_HELP_DESCENDANT
21 struct osl::search::AlphaBeta2ParallelCommon::LivingThreadLock
23 AlphaBeta2ParallelCommon *shared;
24 LivingThreadLock(AlphaBeta2ParallelCommon *s) : shared(s)
26 boost::mutex::scoped_lock lk(shared->living_threads_lock);
27 shared->living_threads += 1;
28 shared->living_threads_condition.notify_one();
32 boost::mutex::scoped_lock lk(shared->living_threads_lock);
33 shared->living_threads -= 1;
34 shared->living_threads_condition.notify_one();
39 template <
class EvalT>
41 Worker::Worker(
int tid, AlphaBeta2Parallel *s) : shared(s), thread_id(tid)
45 template <
class EvalT>
57 boost::mutex::scoped_lock lk(OslConfig::lock_io);
58 std::cerr <<
"thread " << thread_id <<
" started\n";
62 AlphaBeta2ParallelCommon::LivingThreadLock lk(shared);
63 shared->threadWait(thread_id, -1);
65 catch (std::exception& e) {
66 std::cerr <<
"warning caught exception in thread root " << e.what() <<
"\n";
69 std::cerr <<
"warning caught unknown exception in thread root\n";
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)
85 info[0].thread_id = 0;
92 for (
int i=1; i<max_threads; ++i) {
98 osl::search::AlphaBeta2ParallelCommon::
99 ~AlphaBeta2ParallelCommon()
102 for (
int i=1; i<max_threads; ++i) {
106 std::cerr <<
"<= AlphaBeta2Parallel " << my_id <<
"\n";
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";
116 AlphaBeta2ParallelCommon::waitAll() {
117 #ifndef OSL_BUSY_WAIT
119 boost::mutex::scoped_lock lk(lock_smp);
123 #ifndef OSL_BUSY_WAIT
124 condition_smp.notify_all();
127 boost::mutex::scoped_lock lk(living_threads_lock);
128 while (living_threads != (quit ? 0 : smp_idle)) {
129 living_threads_condition.wait(lk);
131 for (
int i=1; i<max_threads; ++i) {
137 bool osl::search::AlphaBeta2ParallelCommon::isDescendant(
int elder,
int younger)
139 #ifndef ONLY_HELP_DESCENDANT
145 while (younger >= 0) {
146 if (elder == younger)
148 younger = info[younger].parent;
157 template <
class EvalT>
160 : AlphaBeta2ParallelCommon(), master(m)
163 std::cerr <<
"=> AlphaBeta2Parallel " << max_threads <<
" threads ";
165 std::cerr <<
" id " << my_id;
171 checkmate[0] = checkmateSearcher(*master);
174 template <
class EvalT>
180 template <
class EvalT>
189 for (; i<max_threads; ++i) {
190 int j=0, max_retry=4;
191 for (; j<max_retry; ++j) {
195 checkmate[i] =
new checkmate_t(master->checkmateSearcher());
196 threads[i] =
new boost::thread(Worker(i,
this));
199 catch (std::exception& e)
201 std::cerr << e.what() <<
"\n";
203 std::cerr <<
"wait for thread " << i <<
" started\n";
204 const int microseconds = (j+1)*100000;
206 boost::this_thread::sleep(boost::posix_time::microseconds(microseconds));
208 usleep(microseconds);
210 NonBlockDelete::deleteAll();
217 std::cerr <<
"error in start thread #" << i <<
"\n";
218 for (
int j=i; j<max_threads; ++j) {
224 boost::mutex::scoped_lock lk(living_threads_lock);
225 while (living_threads+1 != max_threads) {
226 living_threads_condition.wait(lk);
230 template <
class EvalT>
234 TreeInfo *info = &this->info[tree_id];
235 assert(tree[tree_id]);
237 tree[tree_id]->examineMovesRootPar(tree_id);
239 tree[tree_id]->examineMovesOther(tree_id);
242 template <
class EvalT>
248 for (
size_t i=1; i<tree.size(); ++i)
255 template <
class EvalT>
261 boost::mutex::scoped_lock lk(OslConfig::lock_io);
262 std::cerr <<
"thread " << thread_id <<
" ready, waiting " << waiting <<
"\n";
266 this->waiting[thread_id] = waiting;
268 boost::mutex::scoped_lock lk(lock_smp);
272 #ifndef OSL_BUSY_WAIT
273 boost::mutex::scoped_lock lk(lock_smp);
275 while (! job[thread_id]
277 && (waiting < 0 || info[waiting].nprocs))
279 #ifndef OSL_BUSY_WAIT
280 condition_smp.wait(lk);
287 boost::mutex::scoped_lock lk(lock_smp);
292 boost::mutex::scoped_lock lk(OslConfig::lock_io);
293 std::cerr <<
"thread " << thread_id <<
" exiting\n";
299 boost::mutex::scoped_lock lk(lock_smp);
301 if (! job[thread_id])
302 job[thread_id] = waiting;
307 if (job[thread_id] == waiting) {
310 for (
int i=0; i<max_threads; ++i) {
311 assert(info[waiting].siblings[i] == 0);
313 assert(info[waiting].nprocs == 0);
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";
324 if (quit || job[thread_id] == -1) {
327 int my_job = job[thread_id];
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";
338 assert(tree[my_job]);
341 int parent = info[my_job].parent;
342 boost::mutex::scoped_lock lk(lock_smp);
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();
358 boost::mutex::scoped_lock lk(OslConfig::lock_io);
359 std::cerr <<
"thread " << thread_id <<
" back from job " << my_job <<
" waiting " << waiting;
361 std::cerr <<
" rest " << info[waiting].nprocs;
368 template <
class EvalT>
370 split(AlphaBeta2Tree<EvalT> *tree,
int tree_id,
int thread_id,
int max_split)
372 TreeInfo *pinfo = &info[tree_id];
375 unsigned int depth = 0;
376 int parent = pinfo->parent;
378 ++
depth, parent = info[parent].parent;;
379 max_split_depth =
std::max(depth, max_split_depth);
381 for (
int i=0; i<max_threads; ++i) {
382 assert(pinfo->siblings[i] == 0);
385 assert(tree == master || tree == this->tree[tree_id]);
387 boost::mutex::scoped_lock lk(lock_smp);
390 for (; tid<max_threads && job[tid]; ++tid)
392 if (tid == max_threads || tree->stop_tree)
397 job[pinfo->thread_id] = 0;
401 if (
const int child_id = copyToChild(tree_id, thread_id))
405 pinfo->siblings[thread_id] = child_id;
406 info[child_id].thread_id = thread_id;
407 info[child_id].parent = tree_id;
411 max_split =
std::max(max_threads/2, max_thread_group);
415 tid < max_threads && nblocks < max_split;
417 assert(pinfo->siblings[tid] == 0 || tid == thread_id);
418 if (job[tid] || tid == thread_id)
420 if (! isDescendant(waiting[tid], pinfo->parent))
422 int child_id = copyToChild(tree_id, tid);
427 boost::mutex::scoped_lock lk(OslConfig::lock_io);
428 std::cerr <<
"split " << tree_id <<
" in " << thread_id <<
" => " << child_id <<
" in " << tid <<
"\n";
432 pinfo->siblings[tid] = child_id;
433 info[child_id].thread_id = tid;
434 info[child_id].parent = tree_id;
437 pinfo->search_value = pinfo->value;
440 job[pinfo->thread_id] = tree_id;
444 for (
int tid=0; tid< max_threads; ++tid)
445 if (pinfo->siblings[tid])
446 job[tid] = pinfo->siblings[tid];
448 #ifndef OSL_BUSY_WAIT
449 condition_smp.notify_all();
451 threadWait(pinfo->thread_id, tree_id);
456 template <
class EvalT>
460 TreeInfo *info = &this->info[tree_id];
461 AlphaBeta2Tree<EvalT> *tree = this->tree[tree_id];
463 tree->stop_tree =
true;
464 for (
int tid = 0; tid<max_threads; tid++)
465 if (info->siblings[tid])
466 stopThread(info->siblings[tid]);
469 template <
class EvalT>
473 TreeInfo *c = &info[child];
474 AlphaBeta2Tree<EvalT> *cc = tree[child], *pp = tree[parent];
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);
485 template <
class EvalT>
489 static int warnings = 0;
490 int first = thread_id * MaxBlocksPerCpu + 1;
491 int last = first + MaxBlocksPerCpu;
492 int maxb = max_threads * MaxBlocksPerCpu + 1;
495 for (; cid < last && info[cid].used; cid++)
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";
504 for (cid=1; cid<maxb && info[cid].used; cid++)
508 boost::mutex::scoped_lock lk(OslConfig::lock_io);
509 std::cerr <<
"ERROR. no SMP block can be allocated\n";
515 TreeInfo *c = &info[cid], *p = &info[parent];
518 assert(tree[cid] == 0);
519 tree[cid] =
new AlphaBeta2Tree<EvalT>(*tree[parent],
this);
521 catch (std::bad_alloc&)
523 boost::mutex::scoped_lock lk(OslConfig::lock_io);
524 std::cerr <<
"ERROR. split failed due to bad_alloc\n";
527 c->set(*p, max_threads);
528 tree[cid]->setCheckmateSearcher(checkmate[thread_id]);
533 template <
class EvalT>
537 int parent = info[tree_id].parent;
538 TreeInfo *info = &this->info[parent];
540 const size_t old_index = info->move_index;
541 if (tree[parent]->stop_tree)
542 return std::make_pair(MoveLogProb(), old_index);
544 if (old_index < info->
moves.size()) {
545 ++(info->move_index);
546 return std::make_pair(info->moves[old_index], old_index);
548 return std::make_pair(MoveLogProb(), old_index);
551 MoveLogProb m = (info->turn ==
BLACK)
552 ? tree[parent]->
template nextMove<BLACK>()
553 : tree[parent]->template nextMove<WHITE>();
555 assert(m.player() == info->turn);
556 ++(info->move_index);
558 return std::make_pair(m, old_index);
562 template <
class EvalT>
566 return master->checkmateSearcher().totalNodeCount();
569 template <
class EvalT>
573 return master->checkmateSearcher().mainNodeCount();
578 template <
class EvalT>
579 template <osl::Player P>
584 std::cerr <<
"root tree stop\n";
589 AlphaBeta2ParallelCommon::TreeInfo *parent = shared->parent(tree_id);
593 assert(w.isConsistent());
595 assert(P == m.player());
597 if (this->multi_pv) {
601 w.alpha(P) = parent->search_value +
width;
604 const int result = alphaBetaSearch<P>(m, w,
false);
610 boost::mutex::scoped_lock lk_smp(shared->lock_smp);
614 std::cerr <<
"beta cut root " << tree_id <<
"\n";
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]);
621 shared->parallel_abort.inc();
626 assert(parent->window.isConsistent());
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];
636 else if (this->multi_pv && !stopping()
638 addMultiPV(P, result, m.move());
642 template <
class EvalT>
643 template <osl::Player P>
646 MoveLogProb& best_move,
int& best_value)
648 const int id = shared->treeId(
this);
651 boost::mutex::scoped_lock lk(OslConfig::lock_io);
652 std::cerr <<
"start split root " <<
id <<
" turn " << P <<
" parent " << shared->info[id].parent <<
"\n";
656 AlphaBeta2ParallelCommon::TreeInfo *info = &shared->info[id];
657 info->window = window;
658 info->is_root =
true;
660 info->value = best_value;
662 info->move_index = start;
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();
670 best_value = info->search_value;
671 best_move = info->best_move;
674 template <
class EvalT>
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) {
684 if (this->elapsed() > 1.0)
686 boost::mutex::scoped_lock lk(OslConfig::lock_io);
687 BOOST_FOREACH(
const boost::shared_ptr<SearchMonitor>& monitor,
689 monitor->rootMove(m.move());
693 if (my_turn ==
BLACK)
694 testMoveRoot<BLACK>(tree_id, m);
696 testMoveRoot<WHITE>(tree_id, m);
697 if (this->root_limit >= 1600)
698 this->checkmate_searcher->runGC(this->table->isVerbose(),
699 lastMemoryUseRatio1000());
702 std::cerr <<
"caught BetaCut at root " << info->thread_id <<
"\n";
706 catch (std::runtime_error&) {
711 catch (std::exception& e) {
713 boost::mutex::scoped_lock lk(OslConfig::lock_io);
714 std::cerr <<
"caught " << e.what() <<
" at root " << info->thread_id <<
"\n";
721 boost::mutex::scoped_lock lk(OslConfig::lock_io);
722 std::cerr <<
"caught something at root " << info->thread_id <<
"\n";
731 template <
class EvalT>
732 template <osl::Player P>
741 AlphaBeta2ParallelCommon::TreeInfo *parent = shared->parent(tree_id);
746 assert(w.isConsistent() || stop_tree);
749 assert(P == m.player());
750 const int result = alphaBetaSearch<P>(m, w, in_pv);
755 int parent_search_value;
757 #ifdef OSL_USE_RACE_DETECTOR
760 parent_search_value = parent->search_value;
767 boost::mutex::scoped_lock lk_smp(shared->lock_smp);
771 std::cerr <<
"beta cut " << tree_id <<
"\n";
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]);
778 shared->parallel_abort.inc();
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()];
798 template <
class EvalT>
799 template <osl::Player P>
802 int& tried_moves,
int& alpha_update,
int& last_alpha_update)
804 assert(w.isConsistent());
806 const int id = shared->treeId(
this);
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";
816 AlphaBeta2ParallelCommon::TreeInfo *info = &shared->info[id];
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;
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)) {
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";
834 shared->cancelled_splits.inc();
835 throw AlphaBeta2ParallelCommon::SplitFailed();
838 best_value = info->search_value;
839 best_move = info->best_move;
841 tried_moves = info->move_index;
842 alpha_update += info->alpha_update;
843 last_alpha_update = info->last_alpha_update;
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";
854 template <
class EvalT>
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;
863 in_pv = ! parent->best_move.validMove();
865 assert(parent->turn == m.first.player());
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);
884 catch (misc::NoMoreTime&) {
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";
893 catch (NoMoreMemory&) {
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";
902 catch (std::exception& e) {
905 boost::mutex::scoped_lock lk(OslConfig::lock_io);
906 std::cerr <<
"caught exception at " << tree_id <<
" " << e.what() <<
"\n";
910 boost::mutex::scoped_lock lk(OslConfig::lock_io);
911 std::cerr <<
"caught unknown exception at " << tree_id <<
"\n";
923 template struct AlphaBeta2Parallel<eval::ProgressEval>;
926 bool AlphaBeta2Tree<eval::ProgressEval>::examineMovesOther<
BLACK>(Window&, MoveLogProb&,
int&,
int&,
int&,
int&);
928 bool AlphaBeta2Tree<eval::ProgressEval>::examineMovesOther<
WHITE>(Window&, MoveLogProb&,
int&,
int&,
int&,
int&);
931 void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRootPar<
BLACK>(
const MoveLogProbVector&, size_t, Window, MoveLogProb&,
int&);
933 void AlphaBeta2Tree<eval::ProgressEval>::examineMovesRootPar<
WHITE>(
const MoveLogProbVector&, size_t, Window, MoveLogProb&,
int&);
935 template struct AlphaBeta2Parallel<eval::ml::OpenMidEndingEval>;
938 bool AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesOther<
BLACK>(Window&, MoveLogProb&,
int&,
int&,
int&,
int&);
940 bool AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesOther<
WHITE>(Window&, MoveLogProb&,
int&,
int&,
int&,
int&);
943 void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRootPar<
BLACK>(
const MoveLogProbVector&, size_t, Window, MoveLogProb&,
int&);
945 void AlphaBeta2Tree<eval::ml::OpenMidEndingEval>::examineMovesRootPar<
WHITE>(
const MoveLogProbVector&, size_t, Window, MoveLogProb&,
int&);