25 # include <tbb/concurrent_hash_map.h>
34 #include <boost/tuple/tuple.hpp>
35 #include <boost/tuple/tuple_comparison.hpp>
42 #define GRAND_PARENT_SIMULATION
43 #define GRAND_PARENT_DELAY
45 #define INITIAL_DOMINANCE
47 #define ROOT_PROOF_TOL 65536ul*1024
49 #define ROOT_DISPROOF_TOL 65536ul*1024
55 #define DISPROOF_AVERAGE
57 #define KAKINOKI_FALSE_BRANCH_SEARCH
58 #define IGNORE_MONSTER_CHILD
59 #define KISHIMOTO_WIDEN_THRESHOLD
60 #define ADHOC_SUM_RESTRICTION
61 #define AGGRESSIVE_FIND_DAG
62 #define AGGRESSIVE_FIND_DAG2
63 #define CHECKMATE_A3_GOLD
64 #define CHECKMATE_A3_SIMULLATION
67 #define MEMORIZE_SOLVED_IN_BITSET
81 #ifdef MEMORIZE_SOLVED_IN_BITSET
108 return (n <= 1) ? 1 : 32 - __builtin_clz(n);
115 struct NodeIDTable :
public hash_map<HashKey, int>
118 NodeIDTable() : cur(0) {}
119 int id(
const HashKey& key)
121 int& ret = (*this)[key];
127 CArray<int,3> debug_node = {{
130 struct NodeCountTable :
public hash_map<int, std::pair<int,vector<Move> > >
132 typedef std::pair<int,vector<Move> >
pair_t;
135 std::cerr <<
"timer " <<
timer <<
"\n";
136 vector<std::pair<int,int> > all;
138 BOOST_FOREACH(
const value_type& v, *
this)
139 all.push_back(std::make_pair(-v.second.first, v.first));
140 std::sort(all.begin(), all.end());
141 for (
size_t i=0; i<std::
min((
size_t)10, size()); ++i){
142 std::cerr <<
"freq " << -all[i].first <<
" id " << std::setw(5) << all[i].second <<
' ';
143 BOOST_FOREACH(Move m, (*
this)[all[i].second].second)
152 #ifdef USE_BOOST_POOL_ALLOCATOR
153 , osl::stl::fast_pool_allocator<PathEncoding>
172 template <
bool Enabled=true>
178 if (! Enabled)
return;
184 if (! Enabled)
return;
190 struct DfpnPathList :
public slist<std::pair<PieceStand, DfpnPathRecord>
191 #ifdef USE_BOOST_POOL_ALLOCATOR
192 , osl::stl::fast_pool_allocator<std::pair<PieceStand,DfpnPathRecord> >
196 typedef slist<std::pair<PieceStand, DfpnPathRecord> >
list_t;
198 template <Player Attack>
202 iterator ret = end();
203 for (iterator p=begin(); p!=end(); ++p) {
204 if (p->first == black) {
207 if (loop || p->second.visiting)
break;
209 if (! p->second.visiting)
211 if (p->first.isSuperiorOrEqualTo(black)) {
212 if (Attack ==
BLACK) {
214 if (ret != end())
break;
218 if (Attack ==
WHITE) {
220 if (ret != end())
break;
227 template <Player Attack>
231 iterator ret = find<Attack>(black, loop);
234 return &(ret->second);
245 BOOST_FOREACH(
const value_type& v, *
this) {
246 if (v.first == black)
260 list_t::iterator p=begin();
262 list_t::iterator q=p;
266 if (!
precious(q->second, threshold)) {
273 if (! empty() && !
precious(begin()->second, threshold)) {
283 # ifdef USE_BOOST_POOL_ALLOCATOR
285 , std::equal_to<BoardKey>
286 , osl::stl::fast_pool_allocator<std::pair<const BoardKey,DfpnPathList> >
296 template <Player Attack>
305 table_t::const_iterator p =
table.find(key.boardKey());
306 if (p ==
table.end())
308 return p->second.probe(key.blackStand());
314 for (table_t::iterator p=
table.begin(); p!=
table.end(); ++p)
318 static double memory_threshold = 0.8;
320 if (memory > memory_threshold) {
322 memory_threshold += 1.0/128;
336 const int a = (state.countEffect(attacker,to)
338 int d = state.countEffect(
alt(attacker),to);
343 if ((d >= 2) && (a == d))
369 FixedCapacityVector<DfpnRecord,DfpnMaxUniqMoves>
children;
377 assert(move.
player() == P);
416 return std::find(tl.begin(), tl.end(), p) != tl.end();
443 assert(
moves.size());
455 assert(
moves.size());
465 assert(
children[i].proof_disproof.isCheckmateSuccess());
466 #ifdef MEMORIZE_SOLVED_IN_BITSET
475 assert(
children[i].proof_disproof.isCheckmateFail());
476 #ifdef MEMORIZE_SOLVED_IN_BITSET
493 enum { MinimalMaxDepth = 256 };
496 boost::scoped_array<Node>
node;
503 ) : state(SimpleState(
HIRATE)),
518 return state.inCheck(P);
523 assert(P == move.
player());
525 assert(next_hash == node.hash_key.newHashWithMove(move));
526 Node& next = this->node[depth+1];
528 next.white_stand = node.nextWhiteStand(P, move);
529 next.path = node.path;
531 next.hash_key = next_hash;
543 void dump(
int lines,
int depth=0)
const
548 for (
int i=0; i<=
depth; ++i) {
549 std::cerr <<
"history " << i <<
" " << node[i].moved <<
" ";
550 node[i].hash_key.dumpContentsCerr();
553 const int my_distance = node[
depth].path_record ? node[
depth].path_record->distance : -1;
555 std::cerr <<
"time " << node.
visit_time <<
" (" <<
timer <<
") here " << lines <<
"\n" <<
state;
558 std::cerr <<
" solved " << std::bitset<32>(node.
record.
solved) <<
"\n";
560 std::cerr <<
" dags " << std::bitset<32>(node.
record.
solved) <<
"\n";
563 <<
" my_distance " << my_distance <<
"\n";
564 for (
size_t i=0; i<node.
moves.size(); ++i) {
565 std::cerr <<
" " << i <<
" " << node.
moves[i]
566 <<
" " << node.
children[i].proof_disproof
568 <<
" " << node.
children[i].best_move
570 <<
" count " << node.
children[i].node_count
574 std::cerr <<
"path " << node.
path <<
" twins ";
577 std::cerr << path <<
" ";
583 void showPath(
const char *message,
size_t table_size)
const
585 std::cerr << message <<
" depth " << depth <<
" node " << node_id_table.id(node[depth].hash_key)
586 <<
" time " <<
timer <<
" table " << table_size <<
' ';
587 for (
int i=0; i<=
depth; ++i)
595 const size_t old_table_size;
596 Logging(Tree *tr,
DfpnTable *tb,
const char *message)
597 : tree(tr), table(tb), old_table_size(table->size())
601 tree->showPath(message, old_table_size);
607 const Node& node = tree->node[tree->depth];
608 const int id = node_id_table.id(node.hash_key);
609 std::cerr <<
" node " <<
id <<
" " << node.threshold
610 <<
" " << node.record.proof_disproof <<
"\n";
611 if (
std::find(debug_node.begin(), debug_node.end(), id)
613 tree->dump(__LINE__);
614 if (table->size() == old_table_size)
615 countImmediateReturns(
id);
617 void countImmediateReturns(
int id)
621 for (
int i=0; i<=tree->depth; ++i)
622 p.second.push_back(tree->node[i].moved);
632 osl::CArray<osl::CArray<int,64>,2> count2proof, count2disproof, count2unknown;
636 #ifdef USE_BOOST_POOL_ALLOCATOR
637 , osl::stl::fast_pool_allocator<DfpnRecord>
642 #ifdef USE_BOOST_POOL_ALLOCATOR
643 , osl::stl::fast_pool_allocator<DfpnRecord>
652 template <Player Attack>
654 template <Player Attack>
656 template <Player Attack>
680 if (leaving_thread_id >= 0) {
727 front().working_threads |= 1u << thread_id;
749 BOOST_FOREACH(
const DfpnRecord& record, *
this) {
756 count2proof[key.turn()][
count]++;
758 count2disproof[key.turn()][
count]++;
760 count2unknown[key.turn()][
count]++;
770 list_t::iterator p=begin();
772 list_t::iterator q=p;
776 if (! q->proof_disproof.isFinal()
778 && q->working_threads == 0
787 if (! empty() && ! begin()->proof_disproof.isFinal()
789 && begin()->working_threads == 0
799 template <osl::Player A>
807 const PieceStand attack_stand = (A ==
BLACK) ? key.blackStand() : white_stand;
808 const PieceStand defense_stand = (A ==
BLACK) ? white_stand : key.blackStand();
809 #ifdef INITIAL_DOMINANCE
810 unsigned int proof_ll = 1, disproof_ll = 1;
812 BOOST_FOREACH(
const DfpnRecord& record, *
this) {
815 if (
result.proof_disproof.isFinal())
820 if (attack_stand.isSuperiorOrEqualTo(record.
proofPieces())) {
831 #ifdef INITIAL_DOMINANCE
833 if (record.
stands[A].isSuperiorOrEqualTo(attack_stand)) {
836 else if (attack_stand.isSuperiorOrEqualTo(record.
stands[A])) {
842 #ifdef INITIAL_DOMINANCE
858 size_t node_count = 0, exact = 0;
859 BOOST_FOREACH(
const DfpnRecord& record, *
this) {
865 return dominance_max ? node_count : exact;
868 template <osl::Player A>
875 const PieceStand attack_stand = (A ==
BLACK) ? key.blackStand() : white_stand;
877 BOOST_FOREACH(
const DfpnRecord& record, *
this) {
891 template <osl::Player A>
895 std::cerr <<
"search proof oracles after " << last_move <<
" size " << size() <<
"\n";
899 const PieceStand attack_stand = (A ==
BLACK) ? key.blackStand() : white_stand;
900 BOOST_FOREACH(
const DfpnRecord& record, *
this) {
920 # ifdef USE_BOOST_POOL_ALLOCATOR
921 , osl::stl::hash<BoardKey>
922 , std::equal_to<BoardKey>
923 , osl::stl::fast_pool_allocator<std::pair<const BoardKey,List> >
934 : table(new
Table[DIVSIZE]), total_size(0), dfpn_max_depth(0),
943 : table(new
Table[DIVSIZE]), total_size(0), dfpn_max_depth(0)
954 growth_limit = new_limit;
955 for (
int i=0; i<DIVSIZE; ++i)
956 table[i].rehash(new_limit/DIVSIZE+new_limit/DIVSIZE/128+1);
963 std::cerr <<
"total " << total_size <<
"\n";
964 for (
int i=0; i<DIVSIZE; ++i)
965 std::cerr <<
"DfpnTable " << i <<
" " << table[i].size() <<
"\n";
972 dfpn_max_depth = new_depth;
977 return dfpn_max_depth;
984 for (
int i=0; i<DIVSIZE; ++i)
991 return table[0].attack;
994 template <osl::Player Attack>
999 assert(table[subindex].attack == Attack);
1002 if(!table[subindex].
find(it,key.boardKey()))
1006 Table::iterator p = table[subindex].find(key.boardKey());
1007 if (p == table[subindex].end())
1013 template <osl::Player Attack>
1018 assert(table[subindex].attack == Attack);
1019 return find(key, subindex);
1028 if(!table[subindex].
find(it,key.boardKey()))
1032 Table::const_iterator p = table[subindex].find(key.boardKey());
1033 if (p == table[subindex].end())
1039 template <osl::Player Attack>
1043 const int i=keyToIndex(key);
1044 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1047 const List *l = find<Attack>(key, i);
1049 return DfpnRecord(key.blackStand(), white_stand);
1050 return l->
probe<Attack>(key, white_stand);
1056 if (table[0].attack ==
BLACK)
1057 return probe<BLACK>(key, white_stand);
1059 return probe<WHITE>(key, white_stand);
1061 template <osl::Player Attack>
1065 const int i=keyToIndex(key);
1066 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1069 const List *l = find<Attack>(key, i);
1071 return DfpnRecord(key.blackStand(), white_stand);
1077 if (table[0].attack ==
BLACK)
1078 return findProofOracle<BLACK>(key, white_stand, last_move);
1080 return findProofOracle<WHITE>(key, white_stand, last_move);
1084 template <osl::Player Attack>
1088 const int i=keyToIndex(key);
1089 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1092 const List *l = find<Attack>(key, i);
1102 const int i=keyToIndex(key);
1103 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1117 const int i=keyToIndex(key);
1120 table[i].insert(it,key.boardKey());
1121 List& l = it->second;
1123 # ifdef OSL_DFPN_SMP
1126 List& l = table[i][key.boardKey()];
1128 if (l.
store(value, leaving_thread_id)) {
1129 #ifdef OSL_USE_RACE_DETECTOR
1141 const int i=keyToIndex(key);
1144 table[i].insert(it,key.boardKey());
1145 List& l = it->second;
1147 # ifdef OSL_DFPN_SMP
1150 List& l = table[i][key.boardKey()];
1159 const int i=keyToIndex(key);
1162 table[i].insert(it,key.boardKey());
1163 List& l = it->second;
1165 # ifdef OSL_DFPN_SMP
1168 List& l = table[i][key.boardKey()];
1171 #ifdef OSL_USE_RACE_DETECTOR
1181 const int i=keyToIndex(key);
1184 table[i].insert(it,key.boardKey());
1185 List& l = it->second;
1187 # ifdef OSL_DFPN_SMP
1190 List& l = table[i][key.boardKey()];
1199 for (
int i=0; i<DIVSIZE; ++i) {
1200 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1210 for (
int i=0; i<DIVSIZE; ++i) {
1211 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1214 BOOST_FOREACH(Table::value_type& v, table[i])
1215 v.second.testTable(v.first);
1218 for (
int i=0; i<16; ++i) {
1219 for (
int j=0; j<2; ++j)
1220 std::cout << std::setw(9) << count2proof[j][i]
1221 << std::setw(9) << count2disproof[j][i]
1222 << std::setw(9) << count2unknown[j][i]
1233 for (
int i=0; i<DIVSIZE; ++i) {
1234 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1237 Table::iterator p=table[i].begin();
1238 while (p!=table[i].end()) {
1239 removed += p->second.smallTreeGC(threshold);
1240 Table::iterator q = p;
1242 if (q->second.empty()) {
1244 table[i].erase(q->first);
1251 total_size -= removed;
1258 const size_t before = total_size;
1259 if (! (before >= growth_limit || (growth_limit - before) < growth_limit/8))
1262 std::cerr <<
"run GC " << before <<
' ' << gc_threshold <<
"\n";
1263 const size_t removed = smallTreeGC(gc_threshold);
1265 std::cerr <<
" GC " << removed
1267 <<
"collected " << std::setprecision(3)
1268 << ((
sizeof(HashKey)+
sizeof(
DfpnRecord)+
sizeof(
char*)*2)
1269 * removed / (1<<20)) <<
"MB "
1270 << 100.0*removed/before <<
"%"
1271 <<
" real " << memory*100 <<
"%"
1275 static double memory_limit = 0.75;
1276 if (memory > memory_limit) {
1277 growth_limit -= growth_limit/8;
1278 gc_threshold += 15 + gc_threshold/4;
1279 memory_limit += 0.01;
1281 if (removed < before*2/3)
1282 gc_threshold += 15 + gc_threshold/2;
1283 if ((removed < before*3/5 && memory > 0.75) || removed < before/2)
1297 template <osl::Player P>
1310 template <osl::Player P>
1341 path_table->rehash(parallel_shared ? table->growthLimit()/4 : table->growthLimit());
1346 path_table->clear();
1355 ? path_table->allocate<
BLACK>(key, 0, dummy)
1356 : path_table->allocate<
WHITE>(key, 0, dummy);
1362 result.setDisproofPieces((table->attack() ==
WHITE) ? key.blackStand() : white_stand);
1363 table->store(key,
result);
1373 return hasCheckmateMove(state, key, path, limit, best_move, dummy, last_move, pv);
1380 Move last_move, vector<Move> *pv)
1385 path_table->clear();
1388 node_count_limit =
limit;
1390 Node& root = tree->node[0];
1392 tree->state.copyFrom(state);
1399 root.
moved = last_move;
1400 if (state.turn() ==
BLACK)
1406 for (
int i=0; i<=tree->depth; ++i)
1407 table->leaveWorking(tree->node[i].hash_key, thread_id);
1413 if (parallel_shared)
1414 parallel_shared->stop_all =
true;
1418 parallel_shared->stop_all =
true;
1436 return tryProofMain<true>(state, key, path, oracle, oracle_id, best_move, last_move);
1444 return tryProofMain<false>(state, key, path, oracle, oracle_id, best_move, last_move);
1449 template <
bool UseTable>
1459 path_table->clear();
1461 tree->state.copyFrom(state);
1462 node_count = tree->depth = 0;
1465 Node& root = tree->node[0];
1471 root.
moved = last_move;
1482 if (state.turn() ==
BLACK)
1488 for (
int i=0; i<=tree->depth; ++i)
1489 table->leaveWorking(tree->node[i].hash_key, thread_id);
1513 if (! state.hasEffectAt(
alt(state.turn()), state.kingSquare(state.turn())))
1517 path_table->clear();
1518 node_count = tree->depth = 0;
1519 node_count_limit =
limit;
1521 Node& root = tree->node[0];
1523 tree->state.copyFrom(state);
1527 root.
moved = last_move;
1531 if (state.turn() ==
BLACK)
1538 if (state.turn() ==
BLACK)
1562 typedef boost::tuple<int,int,int> tuple_t;
1563 template <Player Turn>
1566 const NumEffectState *state;
1567 move_compare(
const NumEffectState& s) : state(&s)
1569 assert(Turn == state->turn());
1573 const int a = state->countEffect(Turn, m.
to()) + m.
isDrop();
1574 const int d = state->countEffect(
alt(Turn), m.
to());
1576 const int to_x = (5 - abs(5-m.
to().
x()))*2 + (m.
to().
x() > 5);
1577 int from_to = (to_y*16+to_x)*256;
1579 from_to += m.
ptype();
1582 return boost::make_tuple(a > d, from_to, m.
isPromotion());
1584 bool operator()(Move l, Move r)
const
1592 template <osl::Player Turn>
1596 #ifdef MEMORIZE_SOLVED_IN_BITSET
1597 int last_sorted = 0, cur = 0;
1599 for (;(size_t)cur < moves.size(); ++cur) {
1600 if (moves[cur].isDrop() || moves[cur].oldPtype() == last_ptype)
1602 std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
1604 last_ptype = moves[cur].oldPtype();
1606 std::sort(moves.begin()+last_sorted, moves.begin()+cur, move_compare<Turn>(state));
1610 template <osl::Player P>
1614 assert(moves.empty());
1615 if (state.inCheck(P))
1617 using namespace osl::move_classifier;
1623 moves.push_back(move);
1630 (state,state.kingPiece(
alt(P)).square(),
store,has_pawn_checkmate);
1632 BOOST_FOREACH(
Move move, moves)
1637 || (state.pinOrOpen(
alt(P)).test
1638 (state.pieceAt(move.
from()).number())))
1642 sort<P>(state,
moves);
1650 #ifdef NAGAI_DAG_TEST
1652 HashKey key = terminal_key;
1659 HashKey parent_key = key.newUnmakeMove(cur.
last_move);
1661 DfpnRecord parent = table->probe(parent_key, white_stand);
1667 for (
int i=tree->depth - 4 - (d%2); i>=0; i-=2) {
1668 if (parent_key == tree->node[i].hash_key) {
1669 for (
size_t m=0; m<
std::min(tree->node[i].moves.size(), (size_t)64); ++m) {
1670 if (tree->node[i].moves[m] == tree->node[i+1].moved
1671 || tree->node[i].moves[m] == cur.
last_move)
1672 tree->node[i].record.
dag_moves |= (1ull << m);
1674 if (parallel_shared)
1675 table->addDag(tree->node[i].hash_key, tree->node[i].record);
1689 findDagSource(tree->node[tree->depth].hash_key, tree->node[tree->depth].record,
1690 tree->node[tree->depth].white_stand, 1);
1694 template <osl::Player P>
1698 assert(! tree->inCheck(
alt(P)));
1699 Node& node = tree->node[tree->depth];
1700 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
1704 Tree::Logging logging(tree.get(), table,
"attack");
1706 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.path.getDepth();
1708 DfpnVisitLock<> lk(node.path_record = path_table->allocate<P>(node.hash_key, my_distance, loop));
1712 node.setLoopDetection();
1716 const size_t node_count_org = node_count++;
1717 #if (! defined CHECKMATE_D2) && (! defined NO_IMMEDIATE_CHECKMATE)
1718 if (! tree->inCheck(P)
1719 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.
best_move)) {
1728 if (tree->depth + 2 >= tree->MaxDepth) {
1729 std::cerr <<
"throw " << thread_id <<
"\n";
1732 assert(tree->depth + 2 < tree->MaxDepth);
1733 record = table->probe<P>(node.hash_key, node.white_stand);
1734 assert(record.
stands[
BLACK] == node.hash_key.blackStand());
1738 if (tree->depth == 0 && node_count_limit <= 50 && record.node_count >= node_count_limit)
1740 if (tree->depth == 0
1746 && (tree->king(
alt(P)).square().x() <= 3 || tree->king(
alt(P)).square().x() >= 7
1747 || tree->king(
alt(P)).square().template squareForBlack<P>().y() <= 3))
1766 table->store(node.hash_key, record);
1773 const size_t removed = table->runGC();
1776 for (
int i=1; i<tree->depth; ++i)
1777 std::cerr << tree->node[i].threshold.proof() <<
' '
1784 if (parallel_shared)
1785 parallel_shared->stop_all =
true;
1790 && (path_table->size() > table->growthLimit()
1793 && path_table->size() > table->growthLimit()/4)
1796 const size_t before = path_table->size();
1797 const size_t removed = path_table->runGC();
1800 std::cerr <<
" GC-path collected "
1801 << std::setprecision(3)
1803 * removed / (1<<20)) <<
"MB "
1804 << 100.0*removed/before <<
"%\n";
1805 for (
int i=0; i<tree->depth; ++i) {
1806 for (
size_t j=0; j<tree->node[i].moves.size(); ++j) {
1807 tree->node[i].children_path[j] = 0;
1813 if (parallel_shared) {
1814 if (parallel_shared->stop_all) {
1818 if (parallel_shared->data[thread_id].restart) {
1819 for (
int i=0; i<tree->depth; ++i) {
1820 if (tree->node[i].hash_key
1821 == parallel_shared->data[thread_id].restart_key)
1824 if (tree->node[i].record.dag_terminal)
1829 parallel_shared->data[thread_id].clear();
1834 bool has_pawn_checkmate=
false;
1835 generateCheck<P>(tree->state, node.moves,has_pawn_checkmate);
1836 if (node.moves.empty()) {
1839 if(has_pawn_checkmate)
1846 #ifdef PROOF_AVERAGE
1847 int frontier_count = 0, sum_frontier_proof = 0;
1849 assert(node.children.empty());
1851 node.allocate(node.moves.size());
1854 for (
size_t i=0; i<node.moves.size(); ++i) {
1855 #ifdef MEMORIZE_SOLVED_IN_BITSET
1856 if (record.
solved & (1ull << i))
1859 const HashKey& new_key = node.hashes[i] = node.hash_key.newHashWithMove(node.moves[i]);
1860 node.children[i] = table->probe<P>(new_key, node.nextWhiteStand(P, node.moves[i]));
1861 if (node.children[i].proof_disproof ==
ProofDisproof(1,1)) {
1862 unsigned int proof, disproof;
1864 node.
moves[i], proof, disproof);
1866 if (HashRandomPair::initialized()) {
1868 std::pair<char,char> randomness = HashRandomPair::value(new_key);
1869 proof += randomness.first;
1870 disproof += randomness.second;
1873 node.children[i].proof_disproof =
ProofDisproof(proof, disproof);
1876 && node.moves[i].isDrop() && node.moves[i].ptype() ==
PAWN) {
1878 #ifdef MEMORIZE_SOLVED_IN_BITSET
1879 record.
solved |= (1ull << i);
1883 else if (node.children[i].proof_disproof.isCheckmateFail())
1884 tree->setNoCheckmateChildInAttack(i);
1885 else if (node.children[i].proof_disproof.isCheckmateSuccess()) {
1886 record.
node_count += node_count - node_count_org;
1887 node.setCheckmateAttack(P,i);
1889 table->store(node.hash_key, record);
1890 node.path_record->node_count = 0;
1893 #ifdef PROOF_AVERAGE
1894 else if (node.children[i].node_count == 0) {
1896 sum_frontier_proof += node.children[i].proof();
1897 assert(node.children[i].proof() < 128);
1900 #ifdef AGGRESSIVE_FIND_DAG2
1901 else if (!node.children[i].proof_disproof.isFinal()
1903 && node.children[i].last_move.isNormal()
1904 && node.children[i].last_move != node.moves[i]) {
1905 findDagSource(node.hashes[i], node.children[i],
1906 node.nextWhiteStand(P, node.moves[i]));
1909 node.children_path[i] = path_table->probe(new_key);
1915 if (parallel_shared)
1916 table->setWorking(node.hash_key, record, thread_id);
1921 assert(node.children.size() == node.moves.size());
1922 #ifdef PROOF_AVERAGE
1923 const size_t proof_average = frontier_count ? sum_frontier_proof/frontier_count : 1;
1925 const size_t proof_average = 1;
1929 if (
std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.hash_key))
1931 tree->dump(__LINE__);
1933 for (
int loop=0;
true; ++loop) {
1934 unsigned int min_proof=record.
min_pdp, min_proof2=record.
min_pdp;
1935 size_t sum_disproof = 0, max_disproof = 0, max_disproof_dag = 0, next_i=node.children.size();
1936 size_t max_drop_disproof_rook = 0, max_drop_disproof_bishop = 0, max_drop_disproof_lance = 0;
1937 int max_children_depth = 0, upward_count = 0;
1938 for (
size_t i=0; i<node.children.size(); ++i) {
1939 #ifdef MEMORIZE_SOLVED_IN_BITSET
1940 if (record.
solved & (1ull << i))
1944 && node.moves[i].fromTo() == node.moves[i-1].fromTo()
1945 && ! node.moves[i].isDrop()) {
1947 assert(node.moves[i].ptype() == node.moves[i-1].oldPtype());
1948 record.
dag_moves |= ((1ull << i) | (1ull << (i-1)));
1954 size_t proof = node.children[i].proof();
1955 size_t disproof = node.children[i].disproof();
1956 if (proof && disproof) {
1957 proof += node.proof_cost[i];
1959 if (parallel_shared && node.children[i].working_threads) {
1965 if (node.children_path[i]) {
1966 if (node.isLoop(i)) {
1972 else if (! node.children[i].proof_disproof.isFinal()) {
1973 max_children_depth =
std::max(max_children_depth, node.children_path[i]->distance);
1974 #ifdef NAGAI_DAG_TEST
1976 max_disproof_dag =
std::max(max_disproof_dag, disproof);
1982 if (node.children_path[i]->distance <= node.path_record->distance) {
1983 max_disproof =
std::max(max_disproof, disproof);
1989 if (node.moves[i].isDrop()
1990 || (
isMajor(node.moves[i].ptype())
1991 && ! node.moves[i].isCapture()
1992 && ! node.moves[i].isPromotion() &&
isPromoted(node.moves[i].ptype())
1993 && ! tree->state.hasEffectAt(
alt(P), node.moves[i].to()))) {
1996 Offset32(tree->king(
alt(P)).square(), node.moves[i].to()));
1998 size_t *
target = &max_drop_disproof_lance;
2000 target = &max_drop_disproof_rook;
2002 target = &max_drop_disproof_bishop;
2003 *target =
std::max(*target, disproof);
2010 max_children_depth = node.path_record->distance+1;
2012 if (proof < min_proof || (proof == min_proof && disproof && disproof < node.children[next_i].disproof())) {
2013 min_proof2 = min_proof;
2016 }
else if (proof < min_proof2) {
2019 sum_disproof += disproof;
2021 sum_disproof += max_drop_disproof_rook + max_drop_disproof_bishop + max_drop_disproof_lance
2025 if (max_drop_disproof_bishop) sum_disproof -=
LongDropCount;
2029 if (sum_disproof == 0)
2030 sum_disproof = max_disproof;
2032 if (node.path_record->distance >= max_children_depth) {
2033 node.path_record->distance = max_children_depth-1;
2035 #ifdef KISHIMOTO_WIDEN_THRESHOLD
2037 node.threshold =
ProofDisproof(node.threshold.proof(), sum_disproof+1);
2039 #ifdef ADHOC_SUM_RESTRICTION
2040 if (sum_disproof < ROOT_DISPROOF_TOL && min_proof > 0 && sum_disproof > min_proof*
AdHocSumScale) {
2041 sum_disproof = min_proof*AdHocSumScale
2045 if (min_proof >= node.threshold.proof()
2046 || sum_disproof >= node.threshold.disproof()
2047 || next_i >= node.children.size()
2048 || node_count + min_proof >= node_count_limit) {
2051 node.setLoopDetection();
2053 node.setNoCheckmateAttack(P, tree->state);
2055 if (recorded_last_move.
isNormal() && recorded_last_move != node.moved
2058 #ifdef AGGRESSIVE_FIND_DAG
2060 && node.children[next_i].last_move.isNormal()
2061 && node.children[next_i].last_move != node.moves[next_i]) {
2062 findDagSource(node.hashes[next_i], node.children[next_i],
2063 node.nextWhiteStand(P, node.moves[next_i]));
2064 node.children[next_i].last_move = node.moves[next_i];
2065 table->store(node.hashes[next_i], node.children[next_i]);
2069 record.
node_count += node_count - node_count_org;
2070 table->store(node.hash_key, record, thread_id);
2071 node.path_record->node_count = record.
node_count;
2073 parallel_shared->restartThreads(node.hash_key, tree->depth, record.
working_threads);
2076 #ifdef MEMORIZE_SOLVED_IN_BITSET
2077 assert(! (record.
solved & (1ull << next_i)));
2080 tree->newVisit(P, node.moves[next_i], node.hashes[next_i]);
2081 Node& next = tree->node[tree->depth+1];
2083 - (sum_disproof - node.children[next_i].disproof());
2084 #ifdef ADHOC_SUM_RESTRICTION
2085 if (disproof_c > node.threshold.disproof())
2086 disproof_c = node.children[next_i].disproof()
2087 + (node.threshold.disproof() - sum_disproof);
2090 - node.proof_cost[next_i],
2095 tree->state.makeUnmakeMove(Player2Type<P>(), next.
moved, helper);
2097 node.children[next_i] = next.
record;
2102 if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
2103 node.setCheckmateAttack(P,next_i);
2104 record.
node_count += node_count - node_count_org;
2106 table->store(node.hash_key, record, thread_id);
2107 node.path_record->node_count = 0;
2108 if (parallel_shared)
2109 parallel_shared->restartThreads(node.hash_key, tree->depth, record.
working_threads);
2114 tree->setNoCheckmateChildInAttack(next_i);
2115 min_proof =
std::min(min_proof2, node.children[next_i].proof());
2117 && node_count + min_proof >= node_count_limit) {
2119 record.
node_count += node_count - node_count_org;
2120 table->store(node.hash_key, record, thread_id);
2121 node.path_record->node_count = record.
node_count;
2122 if (parallel_shared)
2123 parallel_shared->restartThreads(node.hash_key, tree->depth, record.
working_threads);
2126 if (parallel_shared && parallel_shared->data[thread_id].restart) {
2127 if (tree->depth == 0)
2128 parallel_shared->data[thread_id].clear();
2130 if (parallel_shared->data[thread_id].restart_key == node.hash_key) {
2131 record = table->probe<P>(node.hash_key, node.white_stand);
2134 parallel_shared->data[thread_id].clear();
2136 table->leaveWorking(node.hash_key, thread_id);
2143 template <osl::Player P>
2148 assert(moves.empty());
2150 #ifdef GRAND_PARENT_DELAY
2151 const bool delay_node = last_to !=
Square()
2152 && state.hasEffectAt(
alt(P), last_to)
2153 && (state.hasEffectNotBy(
alt(P), state.kingPiece(
alt(P)), last_to)
2154 || ! state.hasEffectAt(P, last_to));
2161 BOOST_FOREACH(
Move move, all) {
2162 if (move.
to() == last_to) {
2163 moves.push_back(move);
2166 #ifdef MEMORIZE_SOLVED_IN_BITSET
2167 sort<AltP>(state,
moves);
2175 #ifdef MEMORIZE_SOLVED_IN_BITSET
2176 sort<AltP>(state,
moves);
2180 if (need_full_width) {
2184 #ifdef MEMORIZE_SOLVED_IN_BITSET
2185 sort<AltP>(state, others);
2187 const int org_size = moves.size();
2188 BOOST_FOREACH(
Move move, others) {
2189 if (
std::find(moves.begin(), moves.begin()+org_size, move) == moves.begin()+org_size)
2190 moves.push_back(move);
2192 BOOST_FOREACH(
Move move, moves)
2204 #ifdef GRAND_PARENT_SIMULATION
2205 Node& node = tree->node[tree->depth];
2206 if (tree->depth >= 2) {
2207 const Node& parent = tree->node[tree->depth-1];
2208 const Node& gparent = tree->node[tree->depth-2];
2221 template <osl::Player P>
2226 if (parallel_shared) {
2227 if (parallel_shared->stop_all)
2229 if (parallel_shared->data[thread_id].restart) {
2230 for (
int i=0; i<tree->depth; ++i) {
2231 if (tree->node[i].hash_key == parallel_shared->data[thread_id].restart_key)
2234 if (tree->node[i].record.dag_terminal)
2239 parallel_shared->data[thread_id].clear();
2243 Node& node = tree->node[tree->depth];
2244 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
2248 Tree::Logging logging(tree.get(), table,
"defens");
2250 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.
path.
getDepth();
2259 const size_t node_count_org = node_count++;
2260 assert(tree->inCheck(
alt(P)));
2268 const bool grand_parent_simulation = grandParentSimulationSuitable();
2271 const Square grand_parent_delay_last_to
2274 generateEscape<P>(tree->state, record.
need_full_width, grand_parent_delay_last_to, node.
moves);
2277 generateEscape<P>(tree->state, record.
need_full_width, grand_parent_delay_last_to, node.
moves);
2279 if (node.
moves.empty()) {
2285 #ifdef DISPROOF_AVERAGE
2286 int frontier_count = 0, sum_frontier_disproof = 0;
2291 for (
size_t i=0;i <node.
moves.size(); ++i) {
2292 #ifdef MEMORIZE_SOLVED_IN_BITSET
2293 if (record.
solved & (1ull << i))
2298 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2309 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2310 node.
children[i].best_move = check_move;
2311 node.
children[i].setProofPieces(proof_pieces);
2316 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2322 const int old_size = (int)node.
moves.size();
2323 for (
int j=1; j<old_size; ++j) {
2324 node.
moves.pop_back();
2333 if (HashRandomPair::initialized()) {
2335 std::pair<char,char> randomness = HashRandomPair::value(new_key);
2336 if (randomness.first || randomness.second) {
2337 unsigned int proof = node.
children[i].proof();
2338 unsigned int disproof = node.
children[i].disproof();
2339 proof += randomness.first;
2340 disproof += randomness.second;
2346 #ifdef DISPROOF_AVERAGE
2348 sum_frontier_disproof += node.
children[i].proof_disproof.disproof();
2354 if (! node.
children[i].proof_disproof.isCheckmateFail()) {
2360 #ifdef GRAND_PARENT_SIMULATION
2362 const Node& gparent = tree->node[tree->depth-2];
2364 if (gi < gparent.
moves.size()
2366 #ifdef MEMORIZE_SOLVED_IN_BITSET
2370 gparent.
children[gi].proof_disproof.isCheckmateSuccess())) {
2371 grandParentSimulation<P>(i, gparent, gi);
2372 if (node.
children[i].proof_disproof.isCheckmateSuccess())
2378 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2379 tree->setNoCheckmateDefense(P, i);
2380 table->store(node.
hash_key, record);
2383 #ifdef AGGRESSIVE_FIND_DAG2
2384 if (!node.
children[i].proof_disproof.isFinal()
2386 && node.
children[i].last_move.isNormal()
2395 for (
size_t i=0;i <node.
moves.size(); ++i) {
2398 ((record.
solved & (1ull<<i))
2399 || (i >= 64 && node.
children[i].proof_disproof.isCheckmateSuccess()))
2401 node.
children[i].proof_disproof.isCheckmateSuccess()
2404 && node.
moves[i].isDrop()) {
2414 if (parallel_shared)
2415 table->setWorking(node.
hash_key, record, thread_id);
2418 const Move recorded_last_move = node.
moved;
2421 #ifdef DISPROOF_AVERAGE
2422 const size_t disproof_average = frontier_count ? sum_frontier_disproof/frontier_count : 1;
2424 const size_t disproof_average = 1;
2428 if (
std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.
hash_key))
2430 tree->dump(__LINE__);
2432 CArray<char,DfpnMaxUniqMoves>
target;
2433 for (
int loop=0;
true; ++loop) {
2434 std::fill(target.begin(), target.begin()+(int)node.
moves.size(),
false);
2435 unsigned int min_disproof=record.
min_pdp, min_disproof2=record.
min_pdp;
2436 size_t sum_proof = 0, max_upward_proof = 0, max_drop_proof = 0, next_i=node.
children.size();
2437 size_t max_proof_dag = 0;
2438 int max_children_depth = 0, upward_count = 0;
2439 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2440 size_t max_proof = 0;
2443 for (
size_t i=0; i<node.
children.size(); ++i) {
2444 #ifdef MEMORIZE_SOLVED_IN_BITSET
2445 if (record.
solved & (1ull << i))
2449 && node.
moves[i].fromTo() == node.
moves[i-1].fromTo()
2450 && ! node.
moves[i].isDrop()) {
2452 assert(node.
moves[i].ptype() == node.
moves[i-1].oldPtype());
2455 size_t disproof = node.
children[i].disproof();
2456 size_t proof = node.
children[i].proof();
2457 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2459 assert(! node.
children[i].proof_disproof.isLoopDetection());
2460 tree->setNoCheckmateDefense(P, i);
2461 table->store(node.
hash_key, record, thread_id);
2462 if (parallel_shared)
2467 if (proof && disproof) {
2468 if (parallel_shared && node.
children[i].working_threads) {
2477 if (parallel_shared)
2478 table->leaveWorking(node.
hash_key, thread_id);
2481 if (! node.
children[i].proof_disproof.isFinal()) {
2483 #ifdef IGNORE_MONSTER_CHILD
2488 false_branch_candidate =
false;
2493 #ifdef NAGAI_DAG_TEST
2495 max_proof_dag =
std::max(max_proof_dag, proof);
2502 max_upward_proof =
std::max(max_upward_proof , proof);
2508 if (node.
moves[i].isDrop() && !tree->state.hasEffectAt(
alt(P), node.
moves[i].to())) {
2509 max_drop_proof =
std::max(max_drop_proof, proof);
2518 if (disproof < min_disproof
2519 || (disproof == min_disproof && proof && proof < node.
children[next_i].proof())) {
2520 min_disproof2 = min_disproof;
2521 min_disproof = disproof;
2523 }
else if (disproof < min_disproof2) {
2524 min_disproof2 = disproof;
2526 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2527 if (false_branch_candidate && ! node.
children[i].proof_disproof.isFinal()
2528 && (node.
children[i].node_count == 0
2529 || ! node.
children[i].best_move.isNormal()
2530 || ! (node.
moves[i].ptype() ==
KING && ! node.
moves[i].isCapture())))
2531 false_branch_candidate =
false;
2532 max_proof =
std::max(max_proof, proof);
2536 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2537 if (false_branch_candidate) {
2540 for (
size_t i=0; i<node.
children.size(); ++i) {
2543 HashKey key = node.
hashes[i];
2544 key = key.newHashWithMove(node.
children[i].best_move);
2545 if (goal == HashKey()) {
2556 sum_proof = max_proof;
2558 sum_proof += max_drop_proof + max_proof_dag;
2563 sum_proof =
std::max(sum_proof, max_upward_proof);
2572 table->store(node.
hash_key, record, thread_id);
2575 #ifdef KISHIMOTO_WIDEN_THRESHOLD
2579 #ifdef ADHOC_SUM_RESTRICTION
2580 if (sum_proof < ROOT_PROOF_TOL && min_disproof > 0 && sum_proof > min_disproof*
AdHocSumScale) {
2581 sum_proof = min_disproof*AdHocSumScale
2588 || node_count + sum_proof >= node_count_limit) {
2597 table->store(node.
hash_key, record, thread_id);
2602 if (recorded_last_move.
isNormal() && recorded_last_move != node.
moved
2605 #ifdef AGGRESSIVE_FIND_DAG
2607 && node.
children[next_i].last_move.isNormal()
2616 record.
node_count += node_count - node_count_org;
2617 table->store(node.
hash_key, record, thread_id);
2623 #ifdef MEMORIZE_SOLVED_IN_BITSET
2624 assert(! (record.
solved & (1ull << next_i)));
2628 Node& next = tree->node[tree->depth+1];
2630 - (sum_proof - node.
children[next_i].proof());
2631 #ifdef ADHOC_SUM_RESTRICTION
2633 proof_c = node.
children[next_i].proof()
2637 std::min(min_disproof2+disproof_average,
2644 if (parallel_shared && parallel_shared->data[thread_id].restart) {
2645 if (tree->depth == 0)
2646 parallel_shared->data[thread_id].clear();
2648 if (parallel_shared->data[thread_id].restart_key == node.
hash_key) {
2651 parallel_shared->data[thread_id].clear();
2653 table->leaveWorking(node.
hash_key, thread_id);
2664 tree->setNoCheckmateDefense(P, next_i);
2665 record.
node_count += node_count - node_count_org;
2666 table->store(node.
hash_key, record, thread_id);
2674 if (node_count >= node_count_limit) {
2676 record.
node_count += node_count - node_count_org;
2677 table->store(node.
hash_key, record, thread_id);
2689 #if (!defined MINIMAL) || (defined DFPNSTATONE)
2692 const NumEffectState& src,
const vector<Move>&
moves)
const
2694 NumEffectState state(src);
2697 for (
size_t i=0; i<moves.size(); ++i) {
2698 if (! state.isAlmostValidMove(moves[i]))
2700 state.makeMove(moves[i]);
2701 key = key.newMakeMove(moves[i]);
2705 std::cerr << i <<
' ' << moves[i] <<
" " << path
2709 std::cerr <<
" distance " << path_record->
distance <<
" twins";
2710 for (SimpleTwinList::const_iterator p=path_record->
twin_list.begin();
2712 std::cerr <<
' ' << *p;
2717 if (state.turn() == table->attack()) {
2718 bool has_pawn_checkmate=
false;
2719 if (state.turn() ==
BLACK)
2720 generateCheck<BLACK>(state, moves, has_pawn_checkmate);
2722 generateCheck<WHITE>(state,
moves, has_pawn_checkmate);
2725 const Square grand_parent_delay_last_to
2727 if (state.turn() ==
BLACK)
2728 generateEscape<WHITE>(state,
true, grand_parent_delay_last_to, moves);
2730 generateEscape<BLACK>(state,
true, grand_parent_delay_last_to,
moves);
2732 for (
size_t i=0; i<moves.size(); ++i) {
2733 const Move m = moves[i];
2734 std::cerr <<
" " << m;
2735 DfpnRecord child = table->probe(key.newMakeMove(m),
2738 const DfpnPathRecord *child_path_record = path_table->probe(key.newMakeMove(m));
2739 if (child_path_record) {
2740 std::cerr <<
" d " << child_path_record->
distance <<
" twins";
2742 std::cerr <<
' ' << path;
2746 std::cerr <<
" (*)";
2754 template <osl::Player P,
bool UseTable>
2765 search->proofOracleAttack<P,UseTable>(oracle, proof_limit);
2769 template <osl::Player P,
bool UseTable>
2780 search->proofOracleDefense<P,UseTable>(oracle, proof_limit);
2784 template <osl::Player P,
bool UseTable>
2789 Tree::Logging logging(tree.get(), table, UseTable ?
"tpatta" :
"pattac");
2791 assert(! tree->inCheck(
alt(P)));
2792 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2793 Node& node = tree->node[tree->depth];
2803 const size_t node_count_org = node_count++;
2804 if (node_count_limit == root_proof_simulation_limit
2805 && node_count > 100000) {
2806 std::cerr <<
"dfpn proof simulation > 100000 throw " << thread_id <<
"\n";
2809 assert(tree->depth + 2 < tree->MaxDepth);
2810 if (tree->depth + 2 >= tree->MaxDepth) {
2811 std::cerr <<
"throw " << thread_id <<
"\n";
2817 #if (defined CHECKMATE_A3_SIMULLATION) || (defined CHECKMATE_A3)
2821 static stat::Ratio oracle_success(
"a3-simulation");
2837 #elif (!defined CHECKMATE_D2) && (!defined NO_IMMEDIATE_CHECKMATE)
2838 if (! tree->inCheck(P)
2839 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.
best_move)) {
2849 if (tree->depth > 1000) {
2850 std::cerr << tree->state;
2851 node.
hash_key.dumpContents(std::cerr);
2865 node.
moves.push_back(check_move);
2866 const HashKey new_key = node.
hash_key.newHashWithMove(node.
moves[0]);
2877 if (! UseTable || ! node.
children[0].proof_disproof.isFinal()) {
2878 Node& next = tree->node[tree->depth+1];
2879 tree->newVisit(P, node.
moves[0], new_key);
2884 tree->state.makeUnmakeMove(Player2Type<P>(), next.
moved, helper);
2893 if (node.
children[0].proof_disproof.isCheckmateSuccess()) {
2895 record.
node_count += node_count - node_count_org;
2896 if (UseTable || node_count - node_count_org > 32) {
2898 table->store(node.
hash_key, record);
2901 else if (UseTable) {
2910 template <osl::Player P,
bool UseTable>
2915 Tree::Logging logging(tree.get(), table, UseTable ?
"tpdefe" :
"pdefen");
2917 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2918 Node& node = tree->node[tree->depth];
2927 if (! UseTable && tree->depth >= 4) {
2928 if (tree->node[tree->depth-4].hash_key == node.
hash_key
2929 || (tree->depth >= 6 && tree->node[tree->depth-6].hash_key == node.
hash_key)) {
2934 const size_t node_count_org = node_count++;
2936 if (! tree->inCheck(
alt(P)) || tree->inCheck(P)) {
2948 const bool grand_parent_simulation = grandParentSimulationSuitable();
2951 const Square grand_parent_delay_last_to
2953 generateEscape<P>(tree->state,
true, grand_parent_delay_last_to, node.
moves);
2954 if (node.
moves.empty()) {
2964 for (
size_t i=0;i <node.
moves.size(); ++i) {
2965 #ifdef MEMORIZE_SOLVED_IN_BITSET
2966 if (record.
solved & (1ull << i))
2973 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2983 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2984 node.
children[i].best_move = check_move;
2985 node.
children[i].setProofPieces(proof_pieces);
2989 if (node.
children[i].proof_disproof.isCheckmateFail())
2995 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2996 tree->setNoCheckmateDefense(P, i);
2998 table->store(node.
hash_key, record);
3001 node.
children_path[i] = UseTable ? path_table->probe(new_key) : 0;
3006 for (
size_t i=0; i<node.
children.size(); ++i) {
3013 unsigned int sum_proof=0, min_disproof=record.
min_pdp;
3015 for (
size_t next_i=0; next_i<node.
children.size(); ++next_i) {
3016 #ifdef MEMORIZE_SOLVED_IN_BITSET
3017 if (record.
solved & (1ull << next_i))
3020 if (node.
children[next_i].proof_disproof.isCheckmateSuccess()) {
3032 if (sum_proof && tree->state.hasEffectAt(P, next_to)
3033 && (! tree->state.hasEffectAt(
alt(P), next_to)
3034 || (tree->state.countEffect(
alt(P), next_to) == 1
3035 && ! node.
moves[next_i].isDrop())))
3037 assert(! node.
isLoop(next_i));
3038 Node& next = tree->node[tree->depth+1];
3039 #ifdef MEMORIZE_SOLVED_IN_BITSET
3040 assert(! (record.
solved & (1ull << next_i)));
3046 next.path.pushMove(node.
moves[next_i]);
3050 node.
children[next_i] = next.record;
3052 if (next.record.proof_disproof.isCheckmateFail()) {
3056 tree->setNoCheckmateDefense(P, next_i);
3057 record.
node_count += node_count - node_count_org;
3059 table->store(node.
hash_key, record);
3062 if (next.record.proof_disproof.isCheckmateSuccess()) {
3066 sum_proof += next.record.proof();
3067 min_disproof =
std::min(min_disproof, next.record.disproof());
3068 if ((sum_proof && ! UseTable) || (int)sum_proof > proof_limit)
3071 if (sum_proof == 0) {
3075 else if (UseTable) {
3084 template <osl::Player P>
3089 Tree::Logging logging(tree.get(), table,
"blocks");
3092 static stat::Ratio oracle_success(
"blocking proof");
3094 Node& node = tree->node[tree->depth];
3095 Node& next = tree->node[tree->depth+1];
3096 const Move oracle_move = node.
moves[oracle_i];
3097 const Square to = oracle_move.
to();
3099 || node.
children[oracle_i].proof_disproof.isCheckmateSuccess());
3100 for (
size_t i=0; i<node.
moves.size(); ++i) {
3101 #ifdef MEMORIZE_SOLVED_IN_BITSET
3107 if (node.
children[i].proof_disproof.isFinal() || node.
moves[i].to() != to)
3111 #ifdef MEMORIZE_SOLVED_IN_BITSET
3134 template <osl::Player P>
3139 Tree::Logging logging(tree.get(), table,
"grands");
3142 static stat::Ratio oracle_success(
"grandparent proof",
true);
3144 Node& node = tree->node[tree->depth];
3145 Node& next = tree->node[tree->depth+1];
3148 assert(move == node.
moves[cur_i]);
3149 const HashKey& oracle_hash = (gparent.
record.
solved & (1ull << gp_i))
3150 ? gparent.
hash_key.newHashWithMove(move)