27 #include <unordered_map>
29 #include <forward_list>
36 #define GRAND_PARENT_SIMULATION
37 #define GRAND_PARENT_DELAY
39 #define INITIAL_DOMINANCE
41 #define ROOT_PROOF_TOL 65536ul*1024
43 #define ROOT_DISPROOF_TOL 65536ul*1024
49 #define DISPROOF_AVERAGE
51 #define KAKINOKI_FALSE_BRANCH_SEARCH
52 #define IGNORE_MONSTER_CHILD
53 #define KISHIMOTO_WIDEN_THRESHOLD
54 #define ADHOC_SUM_RESTRICTION
55 #define AGGRESSIVE_FIND_DAG
56 #define AGGRESSIVE_FIND_DAG2
57 #define CHECKMATE_A3_GOLD
58 #define CHECKMATE_A3_SIMULLATION
61 #define MEMORIZE_SOLVED_IN_BITSET
75 #ifdef MEMORIZE_SOLVED_IN_BITSET
102 return (n <= 1) ? 1 : 32 - __builtin_clz(n);
109 struct NodeIDTable :
public std::unordered_map<HashKey, int, std::hash<HashKey>>
112 NodeIDTable() : cur(0) {}
113 int id(
const HashKey& key)
115 int& ret = (*this)[key];
121 CArray<int,3> debug_node = {{
124 struct NodeCountTable :
public std::unordered_map<int, std::pair<int,std::vector<Move> > >
126 typedef std::pair<int,std::vector<Move> > pair_t;
129 std::cerr <<
"timer " <<
timer <<
"\n";
130 vector<std::pair<int,int> > all;
132 for (
const auto& v: *
this)
133 all.push_back(std::make_pair(-v.second.first, v.first));
134 std::sort(all.begin(), all.end());
135 for (
size_t i=0; i<
std::min((
size_t)10, size()); ++i){
136 std::cerr <<
"freq " << -all[i].first <<
" id " << std::setw(5) << all[i].second <<
' ';
137 for (Move m: (*
this)[all[i].second].second)
162 template <
bool Enabled=true>
171 if (! Enabled)
return;
177 if (! Enabled)
return;
183 struct DfpnPathList :
public std::forward_list<std::pair<PieceStand, DfpnPathRecord>>
185 typedef std::forward_list<std::pair<PieceStand, DfpnPathRecord> >
list_t;
187 template <Player Attack>
191 iterator ret = end();
192 for (iterator p=begin(); p!=end(); ++p) {
193 if (p->first == black) {
196 if (loop || p->second.visiting)
break;
198 if (! p->second.visiting)
200 if (p->first.isSuperiorOrEqualTo(black)) {
201 if (Attack ==
BLACK) {
203 if (ret != end())
break;
207 if (Attack ==
WHITE) {
209 if (ret != end())
break;
216 template <Player Attack>
220 iterator ret = find<Attack>(black, loop);
222 ret->second.distance =
std::min(depth, ret->second.distance);
223 return &(ret->second);
234 for (
const auto& v: *
this) {
235 if (v.first == black)
249 list_t::iterator p=begin();
251 list_t::iterator q=p;
271 typedef std::unordered_map<BoardKey, DfpnPathList, std::hash<BoardKey>>
table_t;
279 template <Player Attack>
289 if (p ==
table.end())
297 for (table_t::iterator p=
table.begin(); p!=
table.end(); ++p)
301 static double memory_threshold = 0.8;
303 if (memory > memory_threshold) {
305 memory_threshold += 1.0/128;
326 if ((d >= 2) && (a == d))
360 assert(move.
player() == P);
399 return std::find(tl.begin(), tl.end(), p) != tl.end();
448 assert(
children[i].proof_disproof.isCheckmateSuccess());
449 #ifdef MEMORIZE_SOLVED_IN_BITSET
458 assert(
children[i].proof_disproof.isCheckmateFail());
459 #ifdef MEMORIZE_SOLVED_IN_BITSET
476 enum { MinimalMaxDepth = 256 };
479 boost::scoped_array<Node>
node;
506 assert(P == move.
player());
508 assert(next_hash ==
node.hash_key.newHashWithMove(move));
519 node.setNoCheckmateChildInAttack(best_i);
531 for (
int i=0; i<=
depth; ++i) {
532 std::cerr <<
"history " << i <<
" " <<
node[i].moved <<
" ";
533 node[i].hash_key.dumpContentsCerr();
536 const int my_distance =
node[
depth].path_record ?
node[
depth].path_record->distance : -1;
538 std::cerr <<
"time " <<
node.visit_time <<
" (" <<
timer <<
") here " << lines <<
"\n" <<
state;
539 std::cerr <<
" false-branch? " << (bool)
node.record.false_branch <<
"\n";
541 std::cerr <<
" solved " << std::bitset<32>(
node.record.solved) <<
"\n";
543 std::cerr <<
" dags " << std::bitset<32>(
node.record.solved) <<
"\n";
544 std::cerr <<
" last_to " <<
node.record.last_to
545 <<
" threshold " <<
node.threshold
546 <<
" my_distance " << my_distance <<
"\n";
547 for (
size_t i=0; i<
node.moves.size(); ++i) {
548 std::cerr <<
" " << i <<
" " <<
node.moves[i]
549 <<
" " <<
node.children[i].proof_disproof
550 <<
" " << (int)
node.proof_cost[i]
551 <<
" " <<
node.children[i].best_move
552 <<
" depth " << (
node.children_path[i] ?
node.children_path[i]->distance : -1)
553 <<
" count " <<
node.children[i].node_count
556 std::cerr <<
node.record.proof_disproof <<
" " <<
node.record.best_move <<
"\n";
557 std::cerr <<
"path " <<
node.path <<
" twins ";
558 if (
node.path_record) {
559 for (
const auto& path:
node.path_record->twin_list)
560 std::cerr << path <<
" ";
566 void showPath(
const char *message,
size_t table_size)
const
568 std::cerr << message <<
" depth " <<
depth <<
" node " << node_id_table.id(
node[
depth].hash_key)
569 <<
" time " <<
timer <<
" table " << table_size <<
' ';
570 for (
int i=0; i<=
depth; ++i)
578 const size_t old_table_size;
579 Logging(Tree *tr,
DfpnTable *tb,
const char *message)
580 : tree(tr), table(tb), old_table_size(table->size())
584 tree->showPath(message, old_table_size);
590 const Node& node = tree->node[tree->depth];
591 const int id = node_id_table.id(node.hash_key);
592 std::cerr <<
" node " <<
id <<
" " << node.threshold
593 <<
" " << node.record.proof_disproof <<
"\n";
594 if (std::find(debug_node.begin(), debug_node.end(),
id)
596 tree->dump(__LINE__);
597 if (table->
size() == old_table_size)
598 countImmediateReturns(
id);
600 void countImmediateReturns(
int id)
602 NodeCountTable::pair_t& p = node_count_table[id];
604 for (
int i=0; i<=tree->depth; ++i)
605 p.second.push_back(tree->node[i].moved);
620 typedef std::forward_list<DfpnRecord>
list_t;
627 template <Player Attack>
629 template <Player Attack>
631 template <Player Attack>
655 if (leaving_thread_id >= 0) {
702 front().working_threads |= 1u << thread_id;
731 count2proof[key.turn()][count]++;
733 count2disproof[key.turn()][count]++;
735 count2unknown[key.turn()][count]++;
745 list_t::iterator p=begin();
747 list_t::iterator q=p;
751 if (! q->proof_disproof.isFinal()
753 && q->working_threads == 0
762 if (! empty() && ! begin()->proof_disproof.isFinal()
764 && begin()->working_threads == 0
774 template <osl::Player A>
784 #ifdef INITIAL_DOMINANCE
785 unsigned int proof_ll = 1, disproof_ll = 1;
806 #ifdef INITIAL_DOMINANCE
808 if (record.
stands[A].isSuperiorOrEqualTo(attack_stand)) {
817 #ifdef INITIAL_DOMINANCE
833 size_t node_count = 0, exact = 0;
840 return dominance_max ? node_count : exact;
843 template <osl::Player A>
866 template <osl::Player A>
894 : table(new
Table[DIVSIZE]), total_size(0), dfpn_max_depth(0),
903 : table(new
Table[DIVSIZE]), total_size(0), dfpn_max_depth(0)
914 growth_limit = new_limit;
915 for (
int i=0; i<DIVSIZE; ++i) {
916 table[i].rehash(new_limit/DIVSIZE+new_limit/DIVSIZE/128+1);
924 std::cerr <<
"total " << total_size <<
"\n";
925 for (
int i=0; i<DIVSIZE; ++i)
926 std::cerr <<
"DfpnTable " << i <<
" " << table[i].size() <<
"\n";
933 dfpn_max_depth = new_depth;
938 return dfpn_max_depth;
945 for (
int i=0; i<DIVSIZE; ++i)
955 template <osl::Player Attack>
960 assert(table[subindex].attack == Attack);
963 if(!table[subindex].find(it,key.
boardKey()))
967 Table::iterator p = table[subindex].
find(key.
boardKey());
968 if (p == table[subindex].end())
974 template <osl::Player Attack>
979 assert(table[subindex].attack == Attack);
980 return find(key, subindex);
989 if(!table[subindex].find(it,key.
boardKey()))
993 Table::const_iterator p = table[subindex].
find(key.
boardKey());
994 if (p == table[subindex].end())
1000 template <osl::Player Attack>
1004 const int i=keyToIndex(key);
1005 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1008 const List *l = find<Attack>(key, i);
1011 return l->
probe<Attack>(key, white_stand);
1017 if (table[0].attack ==
BLACK)
1018 return probe<BLACK>(key, white_stand);
1020 return probe<WHITE>(key, white_stand);
1022 template <osl::Player Attack>
1026 const int i=keyToIndex(key);
1027 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1030 const List *l = find<Attack>(key, i);
1038 if (table[0].attack ==
BLACK)
1039 return findProofOracle<BLACK>(key, white_stand, last_move);
1041 return findProofOracle<WHITE>(key, white_stand, last_move);
1045 template <osl::Player Attack>
1049 const int i=keyToIndex(key);
1050 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1053 const List *l = find<Attack>(key, i);
1063 const int i=keyToIndex(key);
1064 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1067 const List *l = find(key, i);
1078 const int i=keyToIndex(key);
1081 table[i].insert(it,key.
boardKey());
1082 List& l = it->second;
1084 # ifdef OSL_DFPN_SMP
1089 if (l.
store(value, leaving_thread_id)) {
1090 #ifdef OSL_USE_RACE_DETECTOR
1102 const int i=keyToIndex(key);
1105 table[i].insert(it,key.
boardKey());
1106 List& l = it->second;
1108 # ifdef OSL_DFPN_SMP
1120 const int i=keyToIndex(key);
1123 table[i].insert(it,key.
boardKey());
1124 List& l = it->second;
1126 # ifdef OSL_DFPN_SMP
1132 #ifdef OSL_USE_RACE_DETECTOR
1142 const int i=keyToIndex(key);
1145 table[i].insert(it,key.
boardKey());
1146 List& l = it->second;
1148 # ifdef OSL_DFPN_SMP
1160 for (
int i=0; i<DIVSIZE; ++i) {
1161 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1171 for (
int i=0; i<DIVSIZE; ++i) {
1172 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1175 for (
auto& v: table[i])
1176 v.second.testTable(v.first);
1179 for (
int i=0; i<16; ++i) {
1180 for (
int j=0; j<2; ++j)
1181 std::cout << std::setw(9) << count2proof[j][i]
1182 << std::setw(9) << count2disproof[j][i]
1183 << std::setw(9) << count2unknown[j][i]
1194 for (
int i=0; i<DIVSIZE; ++i) {
1195 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH)
1198 Table::iterator p=table[i].begin();
1199 while (p!=table[i].end()) {
1201 Table::iterator q = p;
1203 if (q->second.empty()) {
1205 table[i].erase(q->first);
1212 total_size -= removed;
1219 const size_t before = total_size;
1220 if (! (before >= growth_limit || (growth_limit - before) < growth_limit/8))
1223 std::cerr <<
"run GC " << before <<
' ' << gc_threshold <<
"\n";
1224 const size_t removed = smallTreeGC(gc_threshold);
1226 std::cerr <<
" GC " << removed
1228 <<
"collected " << std::setprecision(3)
1230 * removed / (1<<20)) <<
"MB "
1231 << 100.0*removed/before <<
"%"
1232 <<
" real " << memory*100 <<
"%"
1236 static double memory_limit = 0.75;
1237 if (memory > memory_limit) {
1238 growth_limit -= growth_limit/8;
1239 gc_threshold += 15 + gc_threshold/4;
1240 memory_limit += 0.01;
1242 if (removed < before*2/3)
1243 gc_threshold += 15 + gc_threshold/2;
1244 if ((removed < before*3/5 && memory > 0.75) || removed < before/2)
1258 template <osl::Player P>
1271 template <osl::Player P>
1289 thread_id(-1), blocking_verify(true)
1307 path_table->clear();
1316 ? path_table->allocate<
BLACK>(key, 0, dummy)
1317 : path_table->allocate<
WHITE>(key, 0, dummy);
1321 DfpnRecord result(key.blackStand(), white_stand);
1324 table->
store(key, result);
1331 std::vector<Move> *pv)
1334 return hasCheckmateMove(state, key, path, limit, best_move, dummy, last_move, pv);
1341 Move last_move, std::vector<Move> *pv)
1346 path_table->clear();
1349 node_count_limit = limit;
1351 Node& root = tree->node[0];
1353 tree->state.copyFrom(state);
1360 root.
moved = last_move;
1367 for (
int i=0; i<=tree->depth; ++i)
1368 table->
leaveWorking(tree->node[i].hash_key, thread_id);
1374 if (parallel_shared)
1375 parallel_shared->stop_all =
true;
1379 parallel_shared->stop_all =
true;
1397 return tryProofMain<true>(state, key, path, oracle, oracle_id, best_move, last_move);
1405 return tryProofMain<false>(state, key, path, oracle, oracle_id, best_move, last_move);
1410 template <
bool UseTable>
1420 path_table->clear();
1422 tree->state.copyFrom(state);
1423 node_count = tree->depth = 0;
1426 Node& root = tree->node[0];
1432 root.
moved = last_move;
1449 for (
int i=0; i<=tree->depth; ++i)
1450 table->
leaveWorking(tree->node[i].hash_key, thread_id);
1471 size_t limit,
Move last_move)
1478 path_table->clear();
1479 node_count = tree->depth = 0;
1480 node_count_limit = limit;
1482 Node& root = tree->node[0];
1484 tree->state.copyFrom(state);
1488 root.
moved = last_move;
1513 if (std::find(tl.begin(), tl.end(), root.
path) != tl.end())
1523 typedef std::tuple<int,int,int> tuple_t;
1524 template <Player Turn>
1530 assert(Turn == state->
turn());
1536 const int to_y =
sign(Turn)*m.
to().
y();
1537 const int to_x = (5 - abs(5-m.
to().
x()))*2 + (m.
to().
x() > 5);
1538 int from_to = (to_y*16+to_x)*256;
1540 from_to += m.
ptype();
1543 return std::make_tuple(a > d, from_to, m.
isPromotion());
1545 bool operator()(Move l, Move r)
const
1553 template <osl::Player Turn>
1557 #ifdef MEMORIZE_SOLVED_IN_BITSET
1558 int last_sorted = 0, cur = 0;
1560 for (;(size_t)cur < moves.
size(); ++cur) {
1561 if (moves[cur].isDrop() || moves[cur].oldPtype() == last_ptype)
1563 std::sort(moves.
begin()+last_sorted, moves.
begin()+cur, move_compare<Turn>(state));
1565 last_ptype = moves[cur].oldPtype();
1567 std::sort(moves.
begin()+last_sorted, moves.
begin()+cur, move_compare<Turn>(state));
1571 template <osl::Player P>
1575 assert(moves.
empty());
1590 (state,state.
kingPiece(
alt(P)).square(),store,has_pawn_checkmate);
1592 for (
Move move: moves)
1594 if(move.hasIgnoredUnpromote<P>()){
1599 moves.push_back(move.unpromote());
1602 sort<P>(state, moves);
1610 #ifdef NAGAI_DAG_TEST
1627 for (
int i=tree->depth - 4 - (d%2); i>=0; i-=2) {
1628 if (parent_key == tree->node[i].hash_key) {
1629 for (
size_t m=0; m<
std::min(tree->node[i].moves.size(), (
size_t)64); ++m) {
1630 if (tree->node[i].moves[m] == tree->node[i+1].moved
1631 || tree->node[i].moves[m] == cur.
last_move)
1632 tree->node[i].record.
dag_moves |= (1ull << m);
1634 if (parallel_shared)
1635 table->
addDag(tree->node[i].hash_key, tree->node[i].record);
1649 findDagSource(tree->node[tree->depth].hash_key, tree->node[tree->depth].record,
1650 tree->node[tree->depth].white_stand, 1);
1654 template <osl::Player P>
1658 assert(! tree->inCheck(
alt(P)));
1659 Node& node = tree->node[tree->depth];
1660 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
1664 Tree::Logging logging(tree.get(), table,
"attack");
1666 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.
path.
getDepth();
1676 const size_t node_count_org = node_count++;
1677 #if (! defined CHECKMATE_D2) && (! defined NO_IMMEDIATE_CHECKMATE)
1678 if (! tree->inCheck(P)
1679 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.
best_move)) {
1688 if (tree->depth + 2 >= tree->MaxDepth) {
1689 std::cerr <<
"throw " << thread_id <<
"\n";
1692 assert(tree->depth + 2 < tree->MaxDepth);
1698 if (tree->depth == 0 && node_count_limit <= 50 && record.node_count >= node_count_limit)
1700 if (tree->depth == 0
1706 && (tree->king(
alt(P)).square().x() <= 3 || tree->king(
alt(P)).square().x() >= 7
1707 || tree->king(
alt(P)).square().
template squareForBlack<P>().y() <= 3))
1733 const size_t removed = table->
runGC();
1736 for (
int i=1; i<tree->depth; ++i)
1737 std::cerr << tree->node[i].threshold.proof() <<
' '
1744 if (parallel_shared)
1745 parallel_shared->stop_all =
true;
1756 const size_t before = path_table->size();
1757 const size_t removed = path_table->runGC();
1760 std::cerr <<
" GC-path collected "
1761 << std::setprecision(3)
1763 * removed / (1<<20)) <<
"MB "
1764 << 100.0*removed/before <<
"%\n";
1765 for (
int i=0; i<tree->depth; ++i) {
1766 for (
size_t j=0; j<tree->node[i].moves.size(); ++j) {
1767 tree->node[i].children_path[j] = 0;
1773 if (parallel_shared) {
1774 if (parallel_shared->stop_all) {
1778 if (parallel_shared->data[thread_id].restart) {
1779 for (
int i=0; i<tree->depth; ++i) {
1780 if (tree->node[i].hash_key
1781 == parallel_shared->data[thread_id].restart_key)
1784 if (tree->node[i].record.dag_terminal)
1789 parallel_shared->data[thread_id].clear();
1794 bool has_pawn_checkmate=
false;
1795 generateCheck<P>(tree->state, node.
moves,has_pawn_checkmate);
1799 if(has_pawn_checkmate)
1806 #ifdef PROOF_AVERAGE
1807 int frontier_count = 0, sum_frontier_proof = 0;
1814 for (
size_t i=0; i<node.
moves.
size(); ++i) {
1815 #ifdef MEMORIZE_SOLVED_IN_BITSET
1816 if (record.
solved & (1ull << i))
1822 unsigned int proof, disproof;
1824 node.
moves[i], proof, disproof);
1829 proof += randomness.first;
1830 disproof += randomness.second;
1838 #ifdef MEMORIZE_SOLVED_IN_BITSET
1839 record.
solved |= (1ull << i);
1843 else if (node.
children[i].proof_disproof.isCheckmateFail())
1844 tree->setNoCheckmateChildInAttack(i);
1845 else if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
1846 record.
node_count += node_count - node_count_org;
1853 #ifdef PROOF_AVERAGE
1854 else if (node.
children[i].node_count == 0) {
1856 sum_frontier_proof += node.
children[i].proof();
1857 assert(node.
children[i].proof() < 128);
1860 #ifdef AGGRESSIVE_FIND_DAG2
1861 else if (!node.
children[i].proof_disproof.isFinal()
1863 && node.
children[i].last_move.isNormal()
1875 if (parallel_shared)
1882 #ifdef PROOF_AVERAGE
1883 const size_t proof_average = frontier_count ? sum_frontier_proof/frontier_count : 1;
1885 const size_t proof_average = 1;
1889 if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.
hash_key))
1891 tree->dump(__LINE__);
1893 for (
int loop=0;
true; ++loop) {
1894 unsigned int min_proof=record.
min_pdp, min_proof2=record.
min_pdp;
1895 size_t sum_disproof = 0, max_disproof = 0, max_disproof_dag = 0, next_i=node.
children.size();
1896 size_t max_drop_disproof_rook = 0, max_drop_disproof_bishop = 0, max_drop_disproof_lance = 0;
1897 int max_children_depth = 0, upward_count = 0;
1898 for (
size_t i=0; i<node.
children.size(); ++i) {
1899 #ifdef MEMORIZE_SOLVED_IN_BITSET
1900 if (record.
solved & (1ull << i))
1904 && node.
moves[i].fromTo() == node.
moves[i-1].fromTo()
1905 && ! node.
moves[i].isDrop()) {
1907 assert(node.
moves[i].ptype() == node.
moves[i-1].oldPtype());
1908 record.
dag_moves |= ((1ull << i) | (1ull << (i-1)));
1914 size_t proof = node.
children[i].proof();
1915 size_t disproof = node.
children[i].disproof();
1916 if (proof && disproof) {
1919 if (parallel_shared && node.
children[i].working_threads) {
1932 else if (! node.
children[i].proof_disproof.isFinal()) {
1934 #ifdef NAGAI_DAG_TEST
1936 max_disproof_dag =
std::max(max_disproof_dag, disproof);
1943 max_disproof =
std::max(max_disproof, disproof);
1949 if (node.
moves[i].isDrop()
1951 && ! node.
moves[i].isCapture()
1953 && ! tree->state.hasEffectAt(
alt(P), node.
moves[i].to()))) {
1958 size_t *target = &max_drop_disproof_lance;
1960 target = &max_drop_disproof_rook;
1962 target = &max_drop_disproof_bishop;
1963 *target =
std::max(*target, disproof);
1972 if (proof < min_proof || (proof == min_proof && disproof && disproof < node.
children[next_i].disproof())) {
1973 min_proof2 = min_proof;
1976 }
else if (proof < min_proof2) {
1979 sum_disproof += disproof;
1981 sum_disproof += max_drop_disproof_rook + max_drop_disproof_bishop + max_drop_disproof_lance
1985 if (max_drop_disproof_bishop) sum_disproof -=
LongDropCount;
1989 if (sum_disproof == 0)
1990 sum_disproof = max_disproof;
1995 #ifdef KISHIMOTO_WIDEN_THRESHOLD
1999 #ifdef ADHOC_SUM_RESTRICTION
2000 if (sum_disproof < ROOT_DISPROOF_TOL && min_proof > 0 && sum_disproof > min_proof*
AdHocSumScale) {
2008 || node_count + min_proof >= node_count_limit) {
2015 if (recorded_last_move.
isNormal() && recorded_last_move != node.
moved
2018 #ifdef AGGRESSIVE_FIND_DAG
2020 && node.
children[next_i].last_move.isNormal()
2029 record.
node_count += node_count - node_count_org;
2036 #ifdef MEMORIZE_SOLVED_IN_BITSET
2037 assert(! (record.
solved & (1ull << next_i)));
2040 tree->newVisit(P, node.
moves[next_i], node.
hashes[next_i]);
2041 Node& next = tree->node[tree->depth+1];
2043 - (sum_disproof - node.
children[next_i].disproof());
2044 #ifdef ADHOC_SUM_RESTRICTION
2046 disproof_c = node.
children[next_i].disproof()
2062 if (node.
children[next_i].proof_disproof.isCheckmateSuccess()) {
2064 record.
node_count += node_count - node_count_org;
2068 if (parallel_shared)
2074 tree->setNoCheckmateChildInAttack(next_i);
2077 && node_count + min_proof >= node_count_limit) {
2079 record.
node_count += node_count - node_count_org;
2082 if (parallel_shared)
2086 if (parallel_shared && parallel_shared->data[thread_id].restart) {
2087 if (tree->depth == 0)
2088 parallel_shared->data[thread_id].clear();
2090 if (parallel_shared->data[thread_id].restart_key == node.
hash_key) {
2094 parallel_shared->data[thread_id].clear();
2103 template <osl::Player P>
2108 assert(moves.
empty());
2110 #ifdef GRAND_PARENT_DELAY
2111 const bool delay_node = last_to !=
Square()
2121 for (
Move move: all) {
2122 if (move.to() == last_to) {
2126 #ifdef MEMORIZE_SOLVED_IN_BITSET
2127 sort<AltP>(state, moves);
2135 #ifdef MEMORIZE_SOLVED_IN_BITSET
2136 sort<AltP>(state, moves);
2140 if (need_full_width) {
2144 #ifdef MEMORIZE_SOLVED_IN_BITSET
2145 sort<AltP>(state, others);
2147 const int org_size = moves.
size();
2148 for (
Move move: others) {
2149 if (std::find(moves.
begin(), moves.
begin()+org_size, move) == moves.
begin()+org_size)
2152 for (
Move move: moves)
2154 if(move.hasIgnoredUnpromote<AltP>())
2155 moves.push_back(move.unpromote());
2164 #ifdef GRAND_PARENT_SIMULATION
2165 Node& node = tree->node[tree->depth];
2166 if (tree->depth >= 2) {
2167 const Node& parent = tree->node[tree->depth-1];
2168 const Node& gparent = tree->node[tree->depth-2];
2181 template <osl::Player P>
2186 if (parallel_shared) {
2187 if (parallel_shared->stop_all)
2189 if (parallel_shared->data[thread_id].restart) {
2190 for (
int i=0; i<tree->depth; ++i) {
2191 if (tree->node[i].hash_key == parallel_shared->data[thread_id].restart_key)
2194 if (tree->node[i].record.dag_terminal)
2199 parallel_shared->data[thread_id].clear();
2203 Node& node = tree->node[tree->depth];
2204 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR)
2208 Tree::Logging logging(tree.get(), table,
"defens");
2210 const int my_distance = tree->depth ? tree->node[tree->depth-1].path_record->distance+1 : node.
path.
getDepth();
2219 const size_t node_count_org = node_count++;
2220 assert(tree->inCheck(
alt(P)));
2228 const bool grand_parent_simulation = grandParentSimulationSuitable();
2231 const Square grand_parent_delay_last_to
2234 generateEscape<P>(tree->state, record.
need_full_width, grand_parent_delay_last_to, node.
moves);
2237 generateEscape<P>(tree->state, record.
need_full_width, grand_parent_delay_last_to, node.
moves);
2245 #ifdef DISPROOF_AVERAGE
2246 int frontier_count = 0, sum_frontier_disproof = 0;
2251 for (
size_t i=0;i <node.
moves.
size(); ++i) {
2252 #ifdef MEMORIZE_SOLVED_IN_BITSET
2253 if (record.
solved & (1ull << i))
2258 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2269 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2270 node.
children[i].best_move = check_move;
2271 node.
children[i].setProofPieces(proof_pieces);
2276 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2282 const int old_size = (int)node.
moves.
size();
2283 for (
int j=1; j<old_size; ++j) {
2296 if (randomness.first || randomness.second) {
2297 unsigned int proof = node.
children[i].proof();
2298 unsigned int disproof = node.
children[i].disproof();
2299 proof += randomness.first;
2300 disproof += randomness.second;
2306 #ifdef DISPROOF_AVERAGE
2308 sum_frontier_disproof += node.
children[i].proof_disproof.disproof();
2314 if (! node.
children[i].proof_disproof.isCheckmateFail()) {
2320 #ifdef GRAND_PARENT_SIMULATION
2322 const Node& gparent = tree->node[tree->depth-2];
2330 gparent.
children[gi].proof_disproof.isCheckmateSuccess())) {
2331 grandParentSimulation<P>(i, gparent, gi);
2332 if (node.
children[i].proof_disproof.isCheckmateSuccess())
2338 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2339 tree->setNoCheckmateDefense(P, i);
2343 #ifdef AGGRESSIVE_FIND_DAG2
2344 if (!node.
children[i].proof_disproof.isFinal()
2346 && node.
children[i].last_move.isNormal()
2355 for (
size_t i=0;i <node.
moves.
size(); ++i) {
2358 ((record.
solved & (1ull<<i))
2359 || (i >= 64 && node.
children[i].proof_disproof.isCheckmateSuccess()))
2361 node.
children[i].proof_disproof.isCheckmateSuccess()
2364 && node.
moves[i].isDrop()) {
2374 if (parallel_shared)
2378 const Move recorded_last_move = node.
moved;
2381 #ifdef DISPROOF_AVERAGE
2382 const size_t disproof_average = frontier_count ? sum_frontier_disproof/frontier_count : 1;
2384 const size_t disproof_average = 1;
2388 if (std::find(debug_node.begin(), debug_node.end(), node_id_table.id(node.
hash_key))
2390 tree->dump(__LINE__);
2393 for (
int loop=0;
true; ++loop) {
2395 unsigned int min_disproof=record.
min_pdp, min_disproof2=record.
min_pdp;
2396 size_t sum_proof = 0, max_upward_proof = 0, max_drop_proof = 0, next_i=node.
children.size();
2397 size_t max_proof_dag = 0;
2398 int max_children_depth = 0, upward_count = 0;
2399 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2400 size_t max_proof = 0;
2403 for (
size_t i=0; i<node.
children.size(); ++i) {
2404 #ifdef MEMORIZE_SOLVED_IN_BITSET
2405 if (record.
solved & (1ull << i))
2409 && node.
moves[i].fromTo() == node.
moves[i-1].fromTo()
2410 && ! node.
moves[i].isDrop()) {
2412 assert(node.
moves[i].ptype() == node.
moves[i-1].oldPtype());
2415 size_t disproof = node.
children[i].disproof();
2416 size_t proof = node.
children[i].proof();
2417 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2419 assert(! node.
children[i].proof_disproof.isLoopDetection());
2420 tree->setNoCheckmateDefense(P, i);
2422 if (parallel_shared)
2427 if (proof && disproof) {
2428 if (parallel_shared && node.
children[i].working_threads) {
2437 if (parallel_shared)
2441 if (! node.
children[i].proof_disproof.isFinal()) {
2443 #ifdef IGNORE_MONSTER_CHILD
2448 false_branch_candidate =
false;
2453 #ifdef NAGAI_DAG_TEST
2455 max_proof_dag =
std::max(max_proof_dag, proof);
2462 max_upward_proof =
std::max(max_upward_proof , proof);
2468 if (node.
moves[i].isDrop() && !tree->state.hasEffectAt(
alt(P), node.
moves[i].to())) {
2469 max_drop_proof =
std::max(max_drop_proof, proof);
2478 if (disproof < min_disproof
2479 || (disproof == min_disproof && proof && proof < node.
children[next_i].proof())) {
2480 min_disproof2 = min_disproof;
2481 min_disproof = disproof;
2483 }
else if (disproof < min_disproof2) {
2484 min_disproof2 = disproof;
2486 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2487 if (false_branch_candidate && ! node.
children[i].proof_disproof.isFinal()
2488 && (node.
children[i].node_count == 0
2489 || ! node.
children[i].best_move.isNormal()
2490 || ! (node.
moves[i].ptype() ==
KING && ! node.
moves[i].isCapture())))
2491 false_branch_candidate =
false;
2492 max_proof =
std::max(max_proof, proof);
2496 #ifdef KAKINOKI_FALSE_BRANCH_SEARCH
2497 if (false_branch_candidate) {
2500 for (
size_t i=0; i<node.
children.size(); ++i) {
2516 sum_proof = max_proof;
2518 sum_proof += max_drop_proof + max_proof_dag;
2523 sum_proof =
std::max(sum_proof, max_upward_proof);
2535 #ifdef KISHIMOTO_WIDEN_THRESHOLD
2539 #ifdef ADHOC_SUM_RESTRICTION
2540 if (sum_proof < ROOT_PROOF_TOL && min_disproof > 0 && sum_proof > min_disproof*
AdHocSumScale) {
2548 || node_count + sum_proof >= node_count_limit) {
2562 if (recorded_last_move.
isNormal() && recorded_last_move != node.
moved
2565 #ifdef AGGRESSIVE_FIND_DAG
2567 && node.
children[next_i].last_move.isNormal()
2576 record.
node_count += node_count - node_count_org;
2583 #ifdef MEMORIZE_SOLVED_IN_BITSET
2584 assert(! (record.
solved & (1ull << next_i)));
2588 Node& next = tree->node[tree->depth+1];
2590 - (sum_proof - node.
children[next_i].proof());
2591 #ifdef ADHOC_SUM_RESTRICTION
2593 proof_c = node.
children[next_i].proof()
2597 std::min(min_disproof2+disproof_average,
2604 if (parallel_shared && parallel_shared->data[thread_id].restart) {
2605 if (tree->depth == 0)
2606 parallel_shared->data[thread_id].clear();
2608 if (parallel_shared->data[thread_id].restart_key == node.
hash_key) {
2611 parallel_shared->data[thread_id].clear();
2624 tree->setNoCheckmateDefense(P, next_i);
2625 record.
node_count += node_count - node_count_org;
2634 if (node_count >= node_count_limit) {
2636 record.
node_count += node_count - node_count_org;
2649 #if (!defined MINIMAL) || (defined DFPNSTATONE)
2657 for (
size_t i=0; i<moves.size(); ++i) {
2665 std::cerr << i <<
' ' << moves[i] <<
" " << path
2669 std::cerr <<
" distance " << path_record->
distance <<
" twins";
2670 for (SimpleTwinList::const_iterator p=path_record->
twin_list.begin();
2672 std::cerr <<
' ' << *p;
2678 bool has_pawn_checkmate=
false;
2680 generateCheck<BLACK>(state, moves, has_pawn_checkmate);
2682 generateCheck<WHITE>(state, moves, has_pawn_checkmate);
2685 const Square grand_parent_delay_last_to
2688 generateEscape<WHITE>(state,
true, grand_parent_delay_last_to, moves);
2690 generateEscape<BLACK>(state,
true, grand_parent_delay_last_to, moves);
2692 for (
size_t i=0; i<moves.
size(); ++i) {
2693 const Move m = moves[i];
2694 std::cerr <<
" " << m;
2699 if (child_path_record) {
2700 std::cerr <<
" d " << child_path_record->
distance <<
" twins";
2701 for (
const auto& path: child_path_record->
twin_list) {
2702 std::cerr <<
' ' << path;
2706 std::cerr <<
" (*)";
2714 template <osl::Player P,
bool UseTable>
2729 template <osl::Player P,
bool UseTable>
2744 template <osl::Player P,
bool UseTable>
2749 Tree::Logging logging(tree.get(), table, UseTable ?
"tpatta" :
"pattac");
2751 assert(! tree->inCheck(
alt(P)));
2752 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2753 Node& node = tree->node[tree->depth];
2763 const size_t node_count_org = node_count++;
2765 && node_count > 100000) {
2766 std::cerr <<
"dfpn proof simulation > 100000 throw " << thread_id <<
"\n";
2769 assert(tree->depth + 2 < tree->MaxDepth);
2770 if (tree->depth + 2 >= tree->MaxDepth) {
2771 std::cerr <<
"throw " << thread_id <<
"\n";
2777 #if (defined CHECKMATE_A3_SIMULLATION) || (defined CHECKMATE_A3)
2781 static stat::Ratio oracle_success(
"a3-simulation");
2797 #elif (!defined CHECKMATE_D2) && (!defined NO_IMMEDIATE_CHECKMATE)
2798 if (! tree->inCheck(P)
2799 && ImmediateCheckmate::hasCheckmateMove<P>(tree->state, record.
best_move)) {
2809 if (tree->depth > 1000) {
2810 std::cerr << tree->state;
2837 if (! UseTable || ! node.
children[0].proof_disproof.isFinal()) {
2838 Node& next = tree->node[tree->depth+1];
2839 tree->newVisit(P, node.
moves[0], new_key);
2853 if (node.
children[0].proof_disproof.isCheckmateSuccess()) {
2855 record.
node_count += node_count - node_count_org;
2856 if (UseTable || node_count - node_count_org > 32) {
2861 else if (UseTable) {
2870 template <osl::Player P,
bool UseTable>
2875 Tree::Logging logging(tree.get(), table, UseTable ?
"tpdefe" :
"pdefen");
2877 const int my_distance = (UseTable && tree->depth) ? (tree->node[tree->depth-1].path_record->distance+1) : 0;
2878 Node& node = tree->node[tree->depth];
2887 if (! UseTable && tree->depth >= 4) {
2888 if (tree->node[tree->depth-4].hash_key == node.
hash_key
2889 || (tree->depth >= 6 && tree->node[tree->depth-6].hash_key == node.
hash_key)) {
2894 const size_t node_count_org = node_count++;
2896 if (! tree->inCheck(
alt(P)) || tree->inCheck(P)) {
2908 const bool grand_parent_simulation = grandParentSimulationSuitable();
2911 const Square grand_parent_delay_last_to
2913 generateEscape<P>(tree->state,
true, grand_parent_delay_last_to, node.
moves);
2924 for (
size_t i=0;i <node.
moves.
size(); ++i) {
2925 #ifdef MEMORIZE_SOLVED_IN_BITSET
2926 if (record.
solved & (1ull << i))
2933 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2943 if (node.
children[i].proof_disproof.isCheckmateSuccess()) {
2944 node.
children[i].best_move = check_move;
2945 node.
children[i].setProofPieces(proof_pieces);
2949 if (node.
children[i].proof_disproof.isCheckmateFail())
2955 if (node.
children[i].proof_disproof.isCheckmateFail()) {
2956 tree->setNoCheckmateDefense(P, i);
2961 node.
children_path[i] = UseTable ? path_table->probe(new_key) : 0;
2966 for (
size_t i=0; i<node.
children.size(); ++i) {
2973 unsigned int sum_proof=0, min_disproof=record.
min_pdp;
2975 for (
size_t next_i=0; next_i<node.
children.size(); ++next_i) {
2976 #ifdef MEMORIZE_SOLVED_IN_BITSET
2977 if (record.
solved & (1ull << next_i))
2980 if (node.
children[next_i].proof_disproof.isCheckmateSuccess()) {
2992 if (sum_proof && tree->state.hasEffectAt(P, next_to)
2993 && (! tree->state.hasEffectAt(
alt(P), next_to)
2994 || (tree->state.countEffect(
alt(P), next_to) == 1
2995 && ! node.
moves[next_i].isDrop())))
2997 assert(! node.
isLoop(next_i));
2998 Node& next = tree->node[tree->depth+1];
2999 #ifdef MEMORIZE_SOLVED_IN_BITSET
3000 assert(! (record.
solved & (1ull << next_i)));
3016 tree->setNoCheckmateDefense(P, next_i);
3017 record.
node_count += node_count - node_count_org;
3028 if ((sum_proof && ! UseTable) || (
int)sum_proof > proof_limit)
3031 if (sum_proof == 0) {
3035 else if (UseTable) {
3044 template <osl::Player P>
3049 Tree::Logging logging(tree.get(), table,
"blocks");
3052 static stat::Ratio oracle_success(
"blocking proof");
3054 Node& node = tree->node[tree->depth];
3055 Node& next = tree->node[tree->depth+1];
3056 const Move oracle_move = node.
moves[oracle_i];
3057 const Square to = oracle_move.
to();
3059 || node.
children[oracle_i].proof_disproof.isCheckmateSuccess());
3060 for (
size_t i=0; i<node.
moves.
size(); ++i) {
3061 #ifdef MEMORIZE_SOLVED_IN_BITSET
3067 if (node.
children[i].proof_disproof.isFinal() || node.
moves[i].to() != to)
3071 #ifdef MEMORIZE_SOLVED_IN_BITSET
3094 template <osl::Player P>
3099 Tree::Logging logging(tree.get(), table,
"grands");
3102 static stat::Ratio oracle_success(
"grandparent proof",
true);
3104 Node& node = tree->node[tree->depth];
3105 Node& next = tree->node[tree->depth+1];
3108 assert(move == node.
moves[cur_i]);