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) {}
115 int& ret = (*this)[key];
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)
151 static const int MaxDistance = 1024*128;
158 : distance(MaxDistance), visiting(false), node_count(0)
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);
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;
255 if (! precious(q->second, threshold)) {
262 if (! empty() && ! precious(begin()->second, threshold)) {
271 typedef std::unordered_map<BoardKey, DfpnPathList, std::hash<BoardKey>>
table_t;
279 template <Player Attack>
288 table_t::const_iterator p = table.find(key.
boardKey());
289 if (p == table.end())
297 for (table_t::iterator p=table.begin(); p!=table.end(); ++p)
298 removed += p->second.runGC(gc_threshold);
299 total_size -= removed;
301 static double memory_threshold = 0.8;
303 if (memory > memory_threshold) {
305 memory_threshold += 1.0/128;
309 size_t size()
const {
return total_size; }
310 void rehash(
size_t bucket_size) { table.rehash(bucket_size); }
326 if ((d >= 2) && (a == d))
360 assert(move.
player() == P);
361 return (P ==
WHITE) ? white_stand.
nextStand(P, move) : white_stand;
368 children_path.
clear();
380 assert(! (record.proof_disproof.isFinal()
381 && ! record.proof_disproof.isLoopDetection()));
383 path_record->twin_list.push_front(path);
393 if (! children_path[c] || children[c].proof_disproof.isFinal())
395 if (children_path[c]->visiting)
399 return std::find(tl.begin(), tl.end(), p) != tl.end();
406 record.best_move = moves[best_i];
409 record.stands[attack]);
410 record.setProofPieces(proof_pieces);
418 record.best_move = moves[best_i];
421 record.stands[
alt(attack)]);
422 record.setDisproofPieces(disproof_pieces);
426 assert(moves.
size());
427 assert(record.proof_disproof.isCheckmateSuccess());
429 PieceStand result = record.proof_pieces_candidate;
434 record.setProofPieces(result);
438 assert(moves.
size());
439 assert(record.proof_disproof.isCheckmateFail());
440 assert(! record.proof_disproof.isLoopDetection());
441 PieceStand result = record.proof_pieces_candidate;
444 record.setDisproofPieces(result);
448 assert(children[i].proof_disproof.isCheckmateSuccess());
449 #ifdef MEMORIZE_SOLVED_IN_BITSET 450 record.solved |= (1ull<<i);
452 record.min_pdp =
std::min(record.min_pdp, children[i].proof_disproof.disproof());
453 record.proof_pieces_candidate
454 = record.proof_pieces_candidate.max(children[i].proofPieces());
458 assert(children[i].proof_disproof.isCheckmateFail());
459 #ifdef MEMORIZE_SOLVED_IN_BITSET 460 record.solved |= (1ull<<i);
462 record.min_pdp =
std::min(record.min_pdp, children[i].proof_disproof.proof());
463 record.proof_pieces_candidate
464 = record.proof_pieces_candidate.max(children[i].disproofPieces());
476 enum { MinimalMaxDepth = 256 };
479 boost::scoped_array<Node>
node;
496 node.reset(
new Node[max_depth]);
506 assert(P == move.
player());
509 Node& next = this->node[depth+1];
511 next.white_stand = node.nextWhiteStand(P, move);
512 next.path = node.path;
514 next.hash_key = next_hash;
526 void dump(
int lines,
int depth=0)
const 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;
541 std::cerr <<
" solved " << std::bitset<32>(node.
record.
solved) <<
"\n";
543 std::cerr <<
" dags " << std::bitset<32>(node.
record.
solved) <<
"\n";
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
551 <<
" " << node.
children[i].best_move
553 <<
" count " << node.
children[i].node_count
557 std::cerr <<
"path " << node.
path <<
" twins ";
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;
580 : tree(tr), table(tb), old_table_size(table->
size())
584 tree->showPath(message, old_table_size);
591 const int id = node_id_table.id(node.
hash_key);
592 std::cerr <<
" node " <<
id <<
" " << node.
threshold 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
772 size_t estimateNodeCount(
const HashKey& key,
bool dominance_max)
const;
774 template <osl::Player A>
784 #ifdef INITIAL_DOMINANCE 785 unsigned int proof_ll = 1, disproof_ll = 1;
790 if (result.proof_disproof.isFinal())
795 if (attack_stand.isSuperiorOrEqualTo(record.
proofPieces())) {
802 result.setFrom(record);
806 #ifdef INITIAL_DOMINANCE 808 if (record.
stands[A].isSuperiorOrEqualTo(attack_stand)) {
811 else if (attack_stand.isSuperiorOrEqualTo(record.
stands[A])) {
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),
915 for (
int i=0; i<
DIVSIZE; ++i) {
916 table[i].rehash(new_limit/DIVSIZE+new_limit/DIVSIZE/128+1);
926 std::cerr <<
"DfpnTable " << i <<
" " <<
table[i].
size() <<
"\n";
952 return table[0].attack;
955 template <osl::Player Attack>
968 if (p ==
table[subindex].end())
974 template <osl::Player Attack>
980 return find(key, subindex);
993 Table::const_iterator p =
table[subindex].find(key.
boardKey());
994 if (p ==
table[subindex].end())
1000 template <osl::Player Attack>
1005 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH) 1008 const List *l = find<Attack>(key, i);
1010 return DfpnRecord(key.blackStand(), white_stand);
1011 return l->
probe<Attack>(key, white_stand);
1018 return probe<BLACK>(key, white_stand);
1020 return probe<WHITE>(key, white_stand);
1022 template <osl::Player Attack>
1027 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH) 1030 const List *l = find<Attack>(key, i);
1032 return DfpnRecord(key.blackStand(), white_stand);
1039 return findProofOracle<BLACK>(key, white_stand, last_move);
1041 return findProofOracle<WHITE>(key, white_stand, last_move);
1045 template <osl::Player Attack>
1050 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH) 1053 const List *l = find<Attack>(key, i);
1064 #if (defined OSL_DFPN_SMP) && (! defined USE_TBB_HASH) 1082 List& l = it->second;
1084 # ifdef OSL_DFPN_SMP 1089 if (l.
store(value, leaving_thread_id)) {
1090 #ifdef OSL_USE_RACE_DETECTOR 1106 List& l = it->second;
1108 # ifdef OSL_DFPN_SMP 1124 List& l = it->second;
1126 # ifdef OSL_DFPN_SMP 1132 #ifdef OSL_USE_RACE_DETECTOR 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()) {
1200 removed += p->second.smallTreeGC(threshold);
1201 Table::iterator q = p;
1203 if (q->second.empty()) {
1205 table[i].erase(q->first);
1223 std::cerr <<
"run GC " << before <<
' ' <<
gc_threshold <<
"\n";
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) {
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)
1321 DfpnRecord result(key.blackStand(), white_stand);
1323 result.setDisproofPieces((
table->
attack() ==
WHITE) ? key.blackStand() : white_stand);
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)
1353 tree->state.copyFrom(state);
1360 root.
moved = last_move;
1367 for (
int i=0; i<=
tree->depth; ++i)
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>
1422 tree->state.copyFrom(state);
1432 root.
moved = last_move;
1449 for (
int i=0; i<=
tree->depth; ++i)
1471 size_t limit,
Move last_move)
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());
1581 for (
Move move: escape) {
1590 (state,state.kingPiece(
alt(P)).square(),store,has_pawn_checkmate);
1592 for (
Move move: moves)
1594 if(move.hasIgnoredUnpromote<P>()){
1598 (state.
pieceAt(move.from()).number())))
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
1632 tree->node[i].record.dag_moves |= (1ull << m);
1650 tree->node[
tree->depth].white_stand, 1);
1654 template <osl::Player P>
1658 assert(!
tree->inCheck(
alt(P)));
1660 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR) 1661 node.visit_time = ++
timer;
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();
1672 node.setLoopDetection();
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);
1693 record =
table->
probe<P>(node.hash_key, node.white_stand);
1694 assert(record.
stands[
BLACK] == node.hash_key.blackStand());
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))
1736 for (
int i=1; i<
tree->depth; ++i)
1737 std::cerr <<
tree->node[i].threshold.proof() <<
' ' 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;
1779 for (
int i=0; i<
tree->depth; ++i) {
1780 if (
tree->node[i].hash_key
1784 if (
tree->node[i].record.dag_terminal)
1794 bool has_pawn_checkmate=
false;
1795 generateCheck<P>(
tree->state, node.moves,has_pawn_checkmate);
1796 if (node.moves.empty()) {
1799 if(has_pawn_checkmate)
1806 #ifdef PROOF_AVERAGE 1807 int frontier_count = 0, sum_frontier_proof = 0;
1809 assert(node.children.empty());
1811 node.allocate(node.moves.size());
1814 for (
size_t i=0; i<node.moves.size(); ++i) {
1815 #ifdef MEMORIZE_SOLVED_IN_BITSET 1816 if (record.
solved & (1ull << i))
1820 node.children[i] =
table->
probe<P>(new_key, node.nextWhiteStand(P, node.moves[i]));
1821 if (node.children[i].proof_disproof ==
ProofDisproof(1,1)) {
1822 unsigned int proof, disproof;
1824 node.
moves[i], proof, disproof);
1829 proof += randomness.first;
1830 disproof += randomness.second;
1833 node.children[i].proof_disproof =
ProofDisproof(proof, disproof);
1836 && node.moves[i].isDrop() && node.moves[i].ptype() ==
PAWN) {
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()) {
1847 node.setCheckmateAttack(P,i);
1850 node.path_record->node_count = 0;
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()
1864 && node.children[i].last_move != node.moves[i]) {
1866 node.nextWhiteStand(P, node.moves[i]));
1869 node.children_path[i] =
path_table->probe(new_key);
1881 assert(node.children.size() == node.moves.size());
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) {
1917 proof += node.proof_cost[i];
1925 if (node.children_path[i]) {
1926 if (node.isLoop(i)) {
1932 else if (! node.children[i].proof_disproof.isFinal()) {
1933 max_children_depth =
std::max(max_children_depth, node.children_path[i]->distance);
1934 #ifdef NAGAI_DAG_TEST 1936 max_disproof_dag =
std::max(max_disproof_dag, disproof);
1942 if (node.children_path[i]->distance <= node.path_record->distance) {
1943 max_disproof =
std::max(max_disproof, disproof);
1949 if (node.moves[i].isDrop()
1950 || (
isMajor(node.moves[i].ptype())
1951 && ! node.moves[i].isCapture()
1952 && ! node.moves[i].isPromotion() &&
isPromoted(node.moves[i].ptype())
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);
1970 max_children_depth = node.path_record->distance+1;
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;
1992 if (node.path_record->distance >= max_children_depth) {
1993 node.path_record->distance = max_children_depth-1;
1995 #ifdef KISHIMOTO_WIDEN_THRESHOLD 1997 node.threshold =
ProofDisproof(node.threshold.proof(), sum_disproof+1);
1999 #ifdef ADHOC_SUM_RESTRICTION 2000 if (sum_disproof < ROOT_DISPROOF_TOL && min_proof > 0 && sum_disproof > min_proof*
AdHocSumScale) {
2001 sum_disproof = min_proof*AdHocSumScale
2005 if (min_proof >= node.threshold.proof()
2006 || sum_disproof >= node.threshold.disproof()
2007 || next_i >= node.children.size()
2011 node.setLoopDetection();
2013 node.setNoCheckmateAttack(P,
tree->state);
2015 if (recorded_last_move.
isNormal() && recorded_last_move != node.moved
2018 #ifdef AGGRESSIVE_FIND_DAG 2020 && node.children[next_i].last_move.isNormal()
2021 && node.children[next_i].last_move != node.moves[next_i]) {
2023 node.nextWhiteStand(P, node.moves[next_i]));
2024 node.children[next_i].last_move = node.moves[next_i];
2025 table->
store(node.hashes[next_i], node.children[next_i]);
2031 node.path_record->node_count = record.
node_count;
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]);
2042 unsigned int disproof_c = node.threshold.disproof()
2043 - (sum_disproof - node.children[next_i].disproof());
2044 #ifdef ADHOC_SUM_RESTRICTION 2045 if (disproof_c > node.threshold.disproof())
2046 disproof_c = node.children[next_i].disproof()
2047 + (node.threshold.disproof() - sum_disproof);
2050 - node.proof_cost[next_i],
2057 node.children[next_i] = next.
record;
2062 if (node.children[next_i].proof_disproof.isCheckmateSuccess()) {
2063 node.setCheckmateAttack(P,next_i);
2067 node.path_record->node_count = 0;
2074 tree->setNoCheckmateChildInAttack(next_i);
2075 min_proof =
std::min(min_proof2, node.children[next_i].proof());
2081 node.path_record->node_count = record.
node_count;
2087 if (
tree->depth == 0)
2091 record =
table->
probe<P>(node.hash_key, node.white_stand);
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 2166 if (
tree->depth >= 2) {
2181 template <osl::Player P>
2190 for (
int i=0; i<
tree->depth; ++i) {
2194 if (
tree->node[i].record.dag_terminal)
2204 #if (! defined NDEBUG) && (! defined OSL_USE_RACE_DETECTOR) 2208 Tree::Logging logging(
tree.get(),
table,
"defens");
2220 assert(
tree->inCheck(
alt(P)));
2231 const Square grand_parent_delay_last_to
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 2326 #ifdef MEMORIZE_SOLVED_IN_BITSET 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()) {
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);
2427 if (proof && disproof) {
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) {
2541 sum_proof = min_disproof*AdHocSumScale
2562 if (recorded_last_move.
isNormal() && recorded_last_move != node.
moved 2565 #ifdef AGGRESSIVE_FIND_DAG 2567 && node.
children[next_i].last_move.isNormal()
2583 #ifdef MEMORIZE_SOLVED_IN_BITSET 2584 assert(! (record.
solved & (1ull << next_i)));
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,
2605 if (
tree->depth == 0)
2624 tree->setNoCheckmateDefense(P, next_i);
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;
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;
2817 if (! oracle.proof_disproof.isCheckmateSuccess() || ! oracle.best_move.isNormal())
2837 if (! UseTable || ! node.
children[0].proof_disproof.isFinal()) {
2839 tree->newVisit(P, node.
moves[0], new_key);
2853 if (node.
children[0].proof_disproof.isCheckmateSuccess()) {
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;
2887 if (! UseTable &&
tree->depth >= 4) {
2896 if (!
tree->inCheck(
alt(P)) ||
tree->inCheck(P)) {
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);
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));
2999 #ifdef MEMORIZE_SOLVED_IN_BITSET 3000 assert(! (record.
solved & (1ull << next_i)));
3006 next.path.pushMove(node.
moves[next_i]);
3010 node.
children[next_i] = next.record;
3012 if (next.record.proof_disproof.isCheckmateFail()) {
3016 tree->setNoCheckmateDefense(P, next_i);
3022 if (next.record.proof_disproof.isCheckmateSuccess()) {
3026 sum_proof += next.record.proof();
3027 min_disproof =
std::min(min_disproof, next.record.disproof());
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");
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);
3108 assert(move == node.
moves[cur_i]);
Ptype unpromote(Ptype ptype)
ptypeがpromote後の型の時に,promote前の型を返す. promoteしていない型の時はそのまま返す ...
bool hasUnblockableEffect() const
短い利きがある.長い利きの隣も含む
void push_back(const T &e)
int countEffect(Player player, Square target) const
利きの数を数える.
static const unsigned int IgnoreUpwardDisproofThreshold
void setCheckmateDefense(Player attack, const NumEffectState &state)
static const PieceStand leaf(const SimpleState &state, Player defender, const PieceStand max)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
int max(Player p, int v1, int v2)
bool isCheckmateFail() const
bool isSuperiorOrEqualTo(PieceStand other) const
void add(Ptype type, unsigned int num=1)
static const PieceStand defense(const PieceStand prev, Move move, const PieceStand max)
const int ProofSimulationTolerance
iterator find(PieceStand black, LoopToDominance &loop)
bool hasEffectAt(Square target) const
対象とするマスにあるプレイヤーの利きがあるかどうか.
void restartThreads(const HashKey &key, int depth, unsigned int threads)
bool isMajor(Ptype ptype)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white_stand, Move last_move) const
void setDisproofPieces(PieceStand a)
PieceMask pinOrOpen(Player king) const
void setTable(DfpnTable *new_table)
const HashKey newMakeMove(Move) const
const PieceStand disproofPieces() const
constexpr Player alt(Player player)
int slow_increase(uint32_t n)
const BoardKey96 boardKey() const
bool store(DfpnRecord &value, int leaving_thread_id)
const PathEncoding newPath(int c) const
static const unsigned int InitialDominanceProofMax
const ProofOracle newOracle(Player P, Move move) const
int min(Player p, int v1, int v2)
bool inUnblockableCheck(Player target) const
target の王に合駒可能でない王手がかかっているかどうか.
static const ProofDisproof LoopDetection()
void setCheckmateChildInDefense(size_t i)
void operator()(Square) const
const ProofDisproof tryProof(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
static int countBit(Integer mask)
void testTable(const BoardKey &) const
static const unsigned int InitialDominanceDisproofMax
static void generateKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
不成の受けは作成しないので必要な場合はユーザが作成
bool inCheck(Player P) const
void addDag(DfpnRecord &value)
const Piece pieceAt(Square sq) const
bool isNormal() const
INVALID でも PASS でもない.
bool traceable(Player P, Move move) const
static const ProofDisproof PawnCheckmate()
size_t growthLimit() const
int y() const
将棋としてのY座標を返す.
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
List * find(const HashKey &key, int subindex)
static const ProofDisproof NoCheckmate()
static const CArray< signed char, PTYPE_SIZE > attack_sacrifice_cost
uint64_t dag_moves
合流を引き起こす指手一覧
static const int UpwardWeight
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
static const int LongDropCount
const PieceStand nextStand(Player pl, Move move) const
const PieceStand blackStand() const
const ProofDisproof tryProofMain(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move)
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
static const PieceStand attack(const PieceStand prev, Move move, const PieceStand max)
int x() const
将棋としてのX座標を返す.
FixedCapacityVector< int8_t, DfpnMaxUniqMoves > proof_cost
static const size_t root_proof_simulation_limit
Offset32Base< 8, 9 > Offset32
std::forward_list< std::pair< PieceStand, DfpnPathRecord > > list_t
const ProofDisproof hasCheckmateMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move &best_move, Move last_move=Move::INVALID(), std::vector< Move > *pv=0)
int distance
distance from root
PieceStand proof_pieces_candidate
solved のmax
static const unsigned int NoPromoeIgnoreProofThreshold
#define CHECKMATE_A3_GOLD
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
void showProofOracles(const HashKey &key, PieceStand white_stand, Move last_move) const
FixedCapacityVector< DfpnRecord, DfpnMaxUniqMoves > children
Square kingSquare() const
static const int EnableGCDepth
boost::scoped_array< Table > table
static const unsigned int IgnoreUpwardProofThreshold
int convert(Player P, int value)
unsigned int proof() const
const PtypeTable Ptype_Table
static std::pair< char, char > value(size_t key)
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
int attackProofCost(Player attacker, const NumEffectState &state, Move move)
CallProofOracleAttack(Dfpn *s, const ProofOracle &o, int pl)
const Square from() const
unsigned int tried_oracle
const DfpnPathRecord * probe(PieceStand black) const
unsigned int disproof() const
const DfpnPathRecord * probe(const HashKey &key) const
DfpnShared * parallel_shared
void leaveWorking(PieceStand black, int thread_id)
static const unsigned int DagFindThreshold
static void addMonopolizedPieces(const SimpleState &state, Player player, const PieceStand max, PieceStand &out)
alt(player) が持っていない種類の持駒を playerが持っていたら out に独占分を加算する. ...
static void attackH(Player attacker, const State &, King8Info, Move move, unsigned int &proof_number, unsigned int &disproof_number)
攻撃側の move に対する proof_number と disproof_number を予想する
const EffectContent getEffect(PtypeO ptypeo, Square from, Square to) const
fromにいるptypeoがtoに利きを持つか?
void setProofPieces(PieceStand a)
void setNoCheckmateDefense(Player attack, int best_i)
static const osl::CArray2d< int, 8, 16 > threshold
const PieceStand previousStand(Player pl, Move move) const
unsigned int moves() const
size_t smallTreeGC(size_t threshold)
void setNoCheckmateChildInAttack(size_t best_i)
Move last_move
合流検知+simulation中の簡易 無限ループ回避
unsigned int index() const
#define SCOPED_LOCK(lock, m)
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
static const int AdHocSumScale
static bool precious(const DfpnPathRecord &record, size_t threshold)
bool isAlmostValidMove(Move move) const
合法手かどうかを簡単に検査する.局面に依存するチェックのみ. ルール上指せない手である可能性がある場合...
#define ROOT_DISPROOF_TOL
root で打切る反証数の閾値
constexpr int sign(Player player)
int distance(const HashKey &) const
CArray< HashKey, DfpnMaxUniqMoves > hashes
bool setWorking(const DfpnRecord &value, int thread_id)
DfpnPathRecord * allocate(PieceStand black, int depth, LoopToDominance &loop, size_t &size)
#define MEMORIZE_SOLVED_IN_BITSET
#define ROOT_PROOF_TOL
root で打切る証明数の閾値
CArray< PieceStand, 2 > stands
const Piece king(Player P) const
DfpnPathRecord * allocate(const HashKey &key, int depth, LoopToDominance &loop)
size_t smallTreeGC(size_t threshold=10)
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
static void sort(const NumEffectState &, DfpnMoveVector &)
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
bool inCheck(Player P) const
Pの玉が王手状態
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
const PieceStand nextWhiteStand(Player P, Move move) const
void setNoCheckmateDefense(Player attack, int best_i)
size_t runGC(size_t threshold)
bool isLoopDetection() const
static const ProofDisproof NoEscape()
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
const ProofDisproof hasEscapeByMove(Move next_move, int depth, Move &check_move, PieceStand &proof_pieces)
next_move を指して逃げられるかどうかを調べる
static const Move attack(const NumEffectState &state, Move check_move)
CallProofOracleDefense(Dfpn *s, const ProofOracle &o, int pl)
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
void escape(std::string &str)
URIやFile systemとして使えるように、文字をescape.
void setFrom(const DfpnRecordBase &src)
const HashKey newHashWithMove(Move move) const
unsigned int proof() const
void setIllegal(const HashKey &key, PieceStand white)
void leaveWorking(const HashKey &key, int thread_id)
const PieceStand proofPieces() const
void operator()(Square) const
const ProofDisproof tryProofLight(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
証明数(proof number)と反証数(disproof number).
void newVisit(Player P, Move move, const HashKey &next_hash)
void dump(int lines, int depth=0) const
void setNoCheckmateChildInAttack(size_t i)
const std::string show(Move)
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
void rehash(size_t bucket_size)
bool isCheckmateSuccess() const
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
const HashKey newUnmakeMove(Move) const
const DfpnRecord probe(const HashKey &key, PieceStand white) const
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
const ProofDisproof hasCheckmateMove(int depth, Move &best_move, PieceStand &proof_pieces)
stateがPから詰む局面かを返す.
static int keyToIndex(const HashKey &key)
static void generateCheapKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
bool hasEffectNotBy(Player player, Piece piece, Square target) const
対象とするマスにあるプレイヤーの(ただしある駒以外)利きがあるかどうか.
DfpnPathRecord * path_record
利きをつける手を生成 利きを持つstateでしか使えない.
static const int MaxDistance
static const int MaxDagTraceDepth
const PieceStand max(PieceStand other) const
種類毎に this と other の持駒の多い方を取る
void operator()(Square) const
static bool initialized()
void setNoCheckmateAttack(Player attack, const NumEffectState &state)
const Piece kingPiece() const
static const ProofDisproof Checkmate()
CArray< ThreadData, 32 > data
const King8Info resetEdgeFromLiberty(Player king_player, Square king, King8Info info) const
liberty から盤の淵(xかyが1か9)を取り除く.
static const size_t GrowthLimitInfty
static const unsigned int NoPromoeIgnoreDisproofThreshold
FixedCapacityVector< const DfpnPathRecord *, DfpnMaxUniqMoves > children_path
static const int SacrificeBlockCount
bool isPieceStand() const
void setCheckmateAttack(Player attack, int best_i)
void operator()(Square) const
uint64_t solved
手番に否定的に結果が判明したリスト loop は除く
ProofDisproof proof_disproof
void dumpContents(std::ostream &os) const
std::unique_ptr< DfpnPathTable > path_table
static const unsigned int DagFindThreshold2
void addDag(const HashKey &key, DfpnRecord &value)
const size_t debug_time_start
std::unordered_map< BoardKey, DfpnPathList, std::hash< BoardKey > > table_t
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
static const PieceStand leaf(const NumEffectState &state, Player attacker, const PieceStand max)
size_t estimateNodeCount(const HashKey &key, bool dominance_max) const
unsigned int disproof() const
static double memoryUseRatio()
std::forward_list< DfpnRecord > list_t
boost::scoped_array< Node > node
std::unique_ptr< Tree > tree
const DfpnRecord probe(const HashKey &key, PieceStand white_stand) const
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
DfpnVisitLock(DfpnPathRecord *r)