33 #include <boost/scoped_array.hpp>
34 #include <boost/foreach.hpp>
81 typedef hash_map<HashKey, CompactRecord>
table_t;
92 table_t::const_iterator p =
table.find(key);
93 if (p !=
table.end()) {
116 boost::scoped_array<osl::search::AlphaBeta3::SearchInfo> tree;
124 void init_node_count()
126 max_node_depth = total_node_count = 0;
127 std::fill(depth_node_count, depth_node_count+
sizeof(depth_node_count)/
sizeof(
int), 0);
129 inline void add_node_count(
int depth)
131 max_node_depth =
std::max(max_node_depth, depth);
132 ++depth_node_count[
depth];
144 : state(s),
depth(0), recorder(r), table_common(t)
161 if ((eval_count % (1<<18) == 0) || stop_by_alarm)
162 if (this->timeAssigned().standard.toSeconds() - this->elapsed() < 0.3 || stop_by_alarm)
164 return tree[
depth].eval.value();
173 this->setStartTime(MilliSeconds::now());
174 this->setTimeAssign(assign);
178 last_alpha_update.
clear();
179 bigram_killers.
clear();
184 initial_limit =
std::min(initial_limit, limit);
191 for (
int i=0; i<=
limit; i+=100) {
192 double new_consumed = this->elapsed(), diff = new_consumed - consumed;
193 consumed = new_consumed;
194 if (table_common->verboseLevel() > 1)
195 std::cerr << i <<
" sec " << diff <<
" " << new_consumed
197 <<
" " << last_alpha_update.
getAverage() <<
"\n";
198 best_move = searchRoot(i);
201 const double current_time_left = this->timeAssigned().standard.toSeconds()-this->elapsed();
202 const double coef = nextIterationCoefficient();
203 if (current_time_left < new_consumed * coef) {
204 if (table_common->verboseLevel() > 1)
205 std::cerr <<
"expected timeover\n";
212 if (table_common->verboseLevel() > 1)
213 std::cerr <<
"timeover\n";
216 if (table_common->verboseLevel() > 1)
217 std::cerr <<
"memory full\n";
219 double new_consumed = this->elapsed(), diff = new_consumed - consumed;
220 consumed = new_consumed;
221 if (table_common->verboseLevel() > 1) {
222 std::cerr <<
"finish" <<
" sec " << diff <<
" " << new_consumed
224 <<
" " << last_alpha_update.
getAverage() <<
"\n";
227 recorder.finishSearch(best_move, consumed, table_common->verboseLevel() > 1);
229 for (
int i=0; i<=max_node_depth/4; ++i) {
230 for (
int j=0; j<4; ++j) {
231 const int id = i + (max_node_depth/4)*j;
232 fprintf(stderr,
" depth %2d %5.2f%%",
233 id, 100.0*depth_node_count[
id] / (
double)total_node_count);
235 fprintf(stderr,
"\n");
277 recorder.resetNodeCount();
278 root_player = state.turn();
279 repetition_counter.clear();
280 repetition_counter.push(root.
hash_key, state);
282 RatedMoveVector
moves;
288 BOOST_FOREACH(
const RatedMove& move, moves)
289 root.
moves.push_back(move.move());
296 const Player turn = state.turn();
297 int best_value = minusInfty(turn);
304 MoveVector::iterator p
306 if (p != root.
moves.end())
307 std::swap(*root.
moves.begin(), *p);
316 const int value = (turn ==
BLACK)
317 ? makeMoveAndSearch<BLACK>(move, 100)
318 : makeMoveAndSearch<WHITE>(move, 100);
321 if (limit && table_common->verboseLevel()) {
322 std::cerr <<
" " <<
record::csa::show(move) <<
" " << std::setw(6) << value <<
" " << std::setw(3) << root.
pv.size() <<
" ";
323 for (
size_t i=1; i<root.
pv.size(); ++i) {
326 if (i && root.
pv[i-1].move.to() == root.
pv[i].move.to()) std::cerr <<
'!';
327 else if (root.
pv[i].move.capturePtype()) std::cerr <<
'x' << record::csa::show(root.
pv[i].move.capturePtype());
328 if (root.
pv[i].move.isPromotion()) std::cerr <<
'*';
329 if (root.
pv[i].in_check) std::cerr <<
'#';
333 std::cerr << std::endl;
344 record.
value = best_value;
351 template <osl::Player P>
359 template <osl::Player P>
367 template <osl::Player P>
374 node.
hash_key = tree[
depth-1].hash_key.newHashWithMove(move);
376 node.
height = parent.height - consume;
377 node.
alpha = parent.beta;
378 node.
beta = parent.alpha;
380 node.
eval = parent.eval;
388 = repetition_counter.isAlmostSennichite(node.
hash_key);
390 return this->drawValue();
392 return this->winByFoul(next_sennichite.
winner());
398 state.makeUnmakeMove(Player2Type<P>(), move, f);
404 return tree[
depth+1].search_value;
420 template <osl::Player P>
425 assert(state.turn() ==
alt(P));
427 if (state.hasEffectAt(turn, state.kingSquare(
alt(turn)))) {
431 node.
in_check = state.hasEffectAt(
alt(turn), state.kingSquare(turn));
451 || tree[
depth-1].moved.isCapture())
459 const int ext = (node.
height >= 500) ? -200 : -100;
465 const int org_alpha = node.
alpha, org_height = node.
height;
480 lmr_reduce =
std::min(400, lmr_reduce);
481 node.
height -= lmr_reduce;
485 search<PlayerTraits<P>::opponent>();
489 node.
alpha = org_alpha;
494 node.
height -= lmr_reduce/2;
495 if (lmr_reduce >= 100 || node.
height >= 400)
496 search<PlayerTraits<P>::opponent>();
509 const int height = node.
height;
510 for (
int i=200; i+100<height; i+=200) {
512 search<PlayerTraits<P>::opponent>();
513 node.
alpha = org_alpha;
520 const bool best_move_extension_candidate
523 const bool skip_main_search
524 = best_move_extension_candidate && pv_in_pvs;
525 if (! skip_main_search)
526 search<PlayerTraits<P>::opponent>();
528 if (best_move_extension_candidate
532 node.
alpha = org_alpha;
535 search<PlayerTraits<P>::opponent>();
539 template <osl::Player P>
543 using namespace move_classifier;
544 add_node_count(
depth);
547 assert(state.turn() == P);
548 recorder.addNodeCount();
550 if (node.height < 0) {
556 ? table.
probe(node.hash_key)
558 if (node.alpha == node.beta) {
559 if (record.highFail<P>(node.height, node.beta)) {
560 node.search_value = record.value;
563 if (record.lowFail<P>(node.height, node.alpha)) {
564 node.search_value = record.value;
570 const bool in_pv = node.alpha != node.beta;
571 node.move_type = Initial;
572 node.moves_tried = 0;
574 int best_value = initial_value, last_alpha_update=0;
578 node.search_value = best_value;
582 const int initial_alpha = node.alpha;
583 if (record.best_move.isNormal()) {
584 const Move move = record.best_move;
585 int value = makeMoveAndSearch<P>(move, 100);
590 node.pv.setPV(move, node, tree[
depth+1].pv);
592 last_alpha_update = node.moves_tried+1;
593 alpha_update_type.
add(node.move_type);
595 mpn_cut.
add(node.moves_tried+1);
603 && ImmediateCheckmate::hasCheckmateMove<P>(state)) {
604 node.search_value = winByCheckmate(P);
607 for (
Move move=nextMove<P>(); !move.
isInvalid(); move=nextMove<P>(), node.moves_tried++) {
608 if (node.moves_tried == 1)
609 node.node_type = AllNode;
610 if (move == record.best_move)
612 if (! node.in_check && node.node_type != PvNode) {
613 if (frontier_node && node.move_type > Pass) {
614 const int futility = evalValue()
615 + (move.capturePtype() ? eval_t::captureValue(move.capturePtypeO()) : 0)
618 && (!tree[
depth-1].in_check || !PlayerMoveAdaptor<DirectCheck>::isMember(state,move)))
621 else if (extended_frontier_node && node.move_type > Killer) {
623 if ((move.capturePtype()
626 if (!tree[
depth-1].in_check || !PlayerMoveAdaptor<DirectCheck>::isMember(state,move))
630 int value = makeMoveAndSearch<P>(move, 100);
633 record.best_move = move;
636 node.pv.setPV(move, node, tree[
depth+1].pv);
638 last_alpha_update = node.moves_tried+1;
639 alpha_update_type.
add(node.move_type);
641 mpn_cut.
add(node.moves_tried+1);
647 mpn.
add(node.moves_tried);
648 if (last_alpha_update)
649 ::last_alpha_update.add(last_alpha_update);
651 if (last_alpha_update && node.move_type > Killer) {
652 bigram_killers.
setMove(node.moved, record.best_move);
657 record.value = best_value;
658 record.limit = node.height;
665 table.
store(node.hash_key, record);
667 node.search_value = best_value;
670 template <osl::Player P>
684 if (! node.
moves.empty()) {
705 generateCapture<P>(state, node);
719 generateCaptureAll<P>(state, node);
725 generateAllMoves<P>(state, tree[
depth-1], node);
733 template <osl::Player P>
745 GenerateAllMoves::generateOnBoard<P>(state, node.
moves);
751 RatedMoveVector
moves;
756 BOOST_FOREACH(
const RatedMove& move, moves)
757 if (move.move().isDrop() || ! seePlusLight<P>(state, move.move()))
758 node.
moves.push_back(move.move());
762 GenerateAllMoves::generate<P>(state, node.
moves);
769 template <osl::Player P>
780 const Piece p = state.pieceOf(j);
785 BOOST_FOREACH(
Move move, all) {
786 if (See::see(state, move) > 0) {
787 node.
moves.push_back(move);
790 if (! node.
moves.empty())
796 BOOST_FOREACH(
Move move, all) {
797 if (See::see(state, move) > 0) {
798 node.
moves.push_back(move);
801 if (! node.
moves.empty())
808 const Piece p = state.pieceOf(j);
814 BOOST_FOREACH(
Move move, all) {
815 if (See::see(state, move) > 0) {
816 node.
moves.push_back(move);
820 template <osl::Player P>
826 assert(P == state.turn());
828 if (state.countEffect(P, m.
to()) > state.countEffect(P, m.
to()))
833 template <osl::Player P>
844 const Piece p = state.pieceOf(j);
852 const Piece p = state.pieceOf(j);
858 BOOST_FOREACH(
Move move, all)
859 if (seePlusLight<P>(state, move))
860 node.
moves.push_back(move);
864 template <osl::Player P>
869 assert(! state.hasEffectAt(P, state.kingSquare(
alt(P))));
870 assert(node.
in_check == state.hasEffectAt(
alt(P), state.kingSquare(P)));
874 int best_value = static_value;
882 int value = makeMoveAndQuiesce<P>(move);
888 node.
alpha = value + EvalTraits<P>::delta;
907 const Piece p = state.pieceOf(j);
913 if (See::see(state, move) < 0)
915 int value = makeMoveAndQuiesce<P>(move);
933 template <osl::Player P>
939 tree[
depth].moved = move;
940 tree[
depth].hash_key = tree[
depth-1].hash_key.newHashWithMove(move);
941 tree[
depth].height -= 1;
942 std::swap(tree[
depth].alpha, tree[
depth].beta);
943 tree[
depth].pv.clear();
946 tree[
depth].path.pushMove(move);
947 state.makeUnmakeMove(move, f);
948 tree[
depth].path.popMove(move);
952 return tree[
depth+1].search_value;
955 template <osl::Player P>
959 add_node_count(
depth);
961 assert(state.turn() == P);
962 recorder.addQuiescenceCount();
964 if (state.hasEffectAt(P, state.kingSquare(
alt(P)))) {
969 node.
in_check = state.hasEffectAt(
alt(P), state.kingSquare(P));
971 const int static_value = evalValue();
972 int best_value = static_value;
982 int value = makeMoveAndQuiesce<P>(move);
986 node.
alpha = value + EvalTraits<P>::delta;
1008 const Piece p = state.pieceOf(j);
1014 for (
size_t k=0; k<
std::min((
size_t)1, node.
moves.size()); ++k) {
1016 const int see = See::see(state, move);
1044 push_back(child.begin(), child.end());