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)
138 std::cerr << record::csa::
show(m);
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());
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;
539 std::cerr <<
" false-branch? " << (bool)
node.record.false_branch <<
"\n";
540#ifdef MEMORIZE_SOLVED_IN_BITSET
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)
571 std::cerr << record::csa::show(
node[i].moved);
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>
641 if (record.proof_disproof.isFinal()) {
651 value.
solved |= record.solved;
655 if (leaving_thread_id >= 0) {
680 value.
solved |= record.solved;
697 record.working_threads |= 1u << thread_id;
702 front().working_threads |= 1u << thread_id;
711 if (record.stands[
BLACK] == black) {
713 record.working_threads &= ~(1u << thread_id);
725 if (record.working_threads)
726 std::cerr << std::bitset<16>(record.working_threads) <<
"\n";
727 assert(record.working_threads == 0);
730 if (record.proof_disproof.isCheckmateSuccess())
731 count2proof[key.turn()][count]++;
732 else if (record.proof_disproof.isCheckmateFail())
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
774template <osl::Player A>
784#ifdef INITIAL_DOMINANCE
785 unsigned int proof_ll = 1, disproof_ll = 1;
794 if (record.proof_disproof.isCheckmateSuccess()) {
800 else if (record.proof_disproof.isCheckmateFail()) {
806#ifdef INITIAL_DOMINANCE
808 if (record.stands[A].isSuperiorOrEqualTo(attack_stand)) {
809 proof_ll = std::max(proof_ll, record.proof());
812 disproof_ll = std::max(disproof_ll, record.disproof());
817#ifdef INITIAL_DOMINANCE
833 size_t node_count = 0, exact = 0;
835 if (node_count < record.node_count)
836 node_count = record.node_count;
838 exact = record.node_count;
840 return dominance_max ? node_count : exact;
843template <osl::Player A>
853 if (! record.proof_disproof.isCheckmateSuccess())
858 if (record.last_move == last_move)
866template <osl::Player A>
875 if (! record.proof_disproof.isCheckmateSuccess())
878 std::cerr << record.last_move <<
" " << record.best_move <<
" " << record.node_count <<
" " << record.proofPieces()
879 <<
" " << record.stands[
BLACK] <<
" " << record.stands[
WHITE] <<
"\n";
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)
955template <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())
974template <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())
1000template <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);
1022template <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);
1045template <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;
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;
1120 const int i=keyToIndex(key);
1123 table[i].insert(it,key.
boardKey());
1124 List& l = it->second;
1132#ifdef OSL_USE_RACE_DETECTOR
1142 const int i=keyToIndex(key);
1145 table[i].insert(it,key.
boardKey());
1146 List& l = it->second;
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)
1258template <osl::Player P>
1271template <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);
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);
1410template <
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());
1532 tuple_t convert(
Move m)
const
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
1547 return convert(l) > convert(r);
1553template <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));
1571template <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>()){
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);
1654template <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() <<
' '
1738 << record::csa::show(tree->node[i].moved) <<
' ';
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)
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;
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)
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()) {
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);
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);
2075 min_proof = std::min(min_proof2, node.
children[next_i].proof());
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();
2103template <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>())
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];
2181template <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()) {
2442 max_children_depth = std::max(max_children_depth, node.
children_path[i]->distance);
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 <<
" (*)";
2714template <osl::Player P,
bool UseTable>
2729template <osl::Player P,
bool UseTable>
2744template <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) {
2870template <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)) {
2903 if (record.proof_disproof.isFinal())
2908 const bool grand_parent_simulation = grandParentSimulationSuitable();
2909 if (record.last_to ==
Square())
2910 record.last_to = grand_parent_simulation ? node.
moved.
to() : tree->king(
alt(P)).
square();
2911 const Square grand_parent_delay_last_to
2912 = (record.last_to != tree->king(
alt(P)).square()) ? record.last_to :
Square();
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()) {
2981 min_disproof = std::min(min_disproof, node.
children[next_i].disproof());
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)));
3013 if (record.proof_disproof.isLoopDetection())
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) {
3037 if (record.last_move.isNormal() && record.last_move != node.
moved
3038 && std::max(record.proof(), record.disproof()) >= 128)
3040 record.last_move = node.
moved;
3044template <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
3094template <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]);
bool hasEffect() const
短い利きがあるか,間がemptyなら長い利きがある
bool hasUnblockableEffect() const
短い利きがある.長い利きの隣も含む
void push_back(const T &e)
bool isNormal() const
INVALID でも PASS でもない.
const Square from() const
bool hasEffectNotBy(Player player, Piece piece, Square target) const
対象とするマスにあるプレイヤーの(ただしある駒以外)利きがあるかどうか.
int countEffect(Player player, Square target) const
利きの数を数える.
bool isAlmostValidMove(Move move) const
合法手かどうかを簡単に検査する.局面に依存するチェックのみ. ルール上指せない手である可能性がある場合は,isValidMove を用いる.
bool hasEffectAt(Square target) const
対象とするマスにあるプレイヤーの利きがあるかどうか.
bool inUnblockableCheck(Player target) const
target の王に合駒可能でない王手がかかっているかどうか.
bool inCheck(Player P) const
Pの玉が王手状態
PieceMask pinOrOpen(Player king) const
void add(Ptype type, unsigned int num=1)
const PieceStand nextStand(Player pl, Move move) const
bool isSuperiorOrEqualTo(PieceStand other) const
const PieceStand max(PieceStand other) const
種類毎に this と other の持駒の多い方を取る
const PieceStand previousStand(Player pl, Move move) const
const EffectContent getEffect(PtypeO ptypeo, Square from, Square to) const
fromにいるptypeoがtoに利きを持つか?
const Piece kingPiece() const
Square kingSquare() const
const Piece pieceAt(Square sq) const
unsigned int index() const
bool isPieceStand() const
int y() const
将棋としてのY座標を返す.
int x() const
将棋としてのX座標を返す.
DfpnPathRecord * allocate(const HashKey &key, int depth, LoopToDominance &loop)
std::unordered_map< BoardKey, DfpnPathList, std::hash< BoardKey > > table_t
const DfpnPathRecord * probe(const HashKey &key) const
void rehash(size_t bucket_size)
const PieceStand disproofPieces() const
CArray< PieceStand, 2 > stands
unsigned int disproof() const
void setFrom(const DfpnRecordBase &src)
unsigned int proof() const
const PieceStand proofPieces() const
void setDisproofPieces(PieceStand a)
void setProofPieces(PieceStand a)
size_t growthLimit() const
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
List * find(const HashKey &key, int subindex)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
void addDag(const HashKey &key, DfpnRecord &value)
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
void leaveWorking(const HashKey &key, int thread_id)
const DfpnRecord probe(const HashKey &key, PieceStand white) const
size_t smallTreeGC(size_t threshold=10)
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
int distance(const HashKey &) const
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
static void sort(const NumEffectState &, DfpnMoveVector &)
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
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())
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
void setIllegal(const HashKey &key, PieceStand white)
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
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())
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)
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 setTable(DfpnTable *new_table)
const King8Info resetEdgeFromLiberty(Player king_player, Square king, King8Info info) const
liberty から盤の淵(xかyが1か9)を取り除く.
const ProofDisproof hasEscapeByMove(Move next_move, int depth, Move &check_move, PieceStand &proof_pieces)
next_move を指して逃げられるかどうかを調べる
const ProofDisproof hasCheckmateMove(int depth, Move &best_move, PieceStand &proof_pieces)
stateがPから詰む局面かを返す.
証明数(proof number)と反証数(disproof number).
bool isCheckmateFail() const
static const ProofDisproof PawnCheckmate()
static const ProofDisproof LoopDetection()
static const ProofDisproof NoEscape()
static const ProofDisproof NoCheckmate()
bool isCheckmateSuccess() const
@ DISPROOF_LIMIT
通常の反証数の上限
bool isLoopDetection() const
unsigned int disproof() const
unsigned int proof() const
static const ProofDisproof Checkmate()
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
const PieceStand blackStand() const
const BoardKey96 boardKey() const
const HashKey newMakeMove(Move) const
const HashKey newHashWithMove(Move move) const
void dumpContents(std::ostream &os) const
const HashKey newUnmakeMove(Move) const
static bool initialized()
static std::pair< char, char > value(size_t key)
利きをつける手を生成 利きを持つstateでしか使えない.
#define ROOT_DISPROOF_TOL
root で打切る反証数の閾値
#define CHECKMATE_A3_GOLD
static const unsigned int NoPromoeIgnoreProofThreshold
static const unsigned int IgnoreUpwardProofThreshold
static const size_t GrowthLimitInfty
static const unsigned int DagFindThreshold2
const size_t debug_time_start
static const unsigned int DagFindThreshold
static const int LongDropCount
static const int MaxDagTraceDepth
static const int EnableGCDepth
static const unsigned int NoPromoeIgnoreDisproofThreshold
static const size_t root_proof_simulation_limit
#define ROOT_PROOF_TOL
root で打切る証明数の閾値
static const int SacrificeBlockCount
static const unsigned int IgnoreUpwardDisproofThreshold
static const int AdHocSumScale
static const int UpwardWeight
static const unsigned int InitialDominanceProofMax
static const unsigned int InitialDominanceDisproofMax
const int ProofSimulationTolerance
#define MEMORIZE_SOLVED_IN_BITSET
static const osl::CArray2d< int, 8, 16 > threshold
#define SCOPED_LOCK(lock, m)
int slow_increase(uint32_t n)
int attackProofCost(Player attacker, const NumEffectState &state, Move move)
const std::string show(Move)
const PtypeTable Ptype_Table
Ptype unpromote(Ptype ptype)
ptypeがpromote後の型の時に,promote前の型を返す. promoteしていない型の時はそのまま返す
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
constexpr int sign(Player player)
bool isMajor(Ptype ptype)
constexpr Player alt(Player player)
static double memoryUseRatio()
const DfpnPathRecord * probe(PieceStand black) const
iterator find(PieceStand black, LoopToDominance &loop)
DfpnPathRecord * allocate(PieceStand black, int depth, LoopToDominance &loop, size_t &size)
static bool precious(const DfpnPathRecord &record, size_t threshold)
size_t runGC(size_t threshold)
std::forward_list< std::pair< PieceStand, DfpnPathRecord > > list_t
int distance
distance from root
static const int MaxDistance
ProofDisproof proof_disproof
PieceStand proof_pieces_candidate
solved のmax
unsigned int tried_oracle
uint64_t solved
手番に否定的に結果が判明したリスト loop は除く
Move last_move
合流検知+simulation中の簡易 無限ループ回避
uint64_t dag_moves
合流を引き起こす指手一覧
size_t estimateNodeCount(const HashKey &key, bool dominance_max) const
std::forward_list< DfpnRecord > list_t
size_t smallTreeGC(size_t threshold)
bool store(DfpnRecord &value, int leaving_thread_id)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white_stand, Move last_move) const
bool setWorking(const DfpnRecord &value, int thread_id)
const DfpnRecord probe(const HashKey &key, PieceStand white_stand) const
void addDag(DfpnRecord &value)
void showProofOracles(const HashKey &key, PieceStand white_stand, Move last_move) const
void leaveWorking(PieceStand black, int thread_id)
void testTable(const BoardKey &) const
DfpnVisitLock & operator=(const DfpnVisitLock &)=delete
DfpnVisitLock(const DfpnVisitLock &)=delete
DfpnVisitLock(DfpnPathRecord *r)
void operator()(Square) const
void operator()(Square) const
CallProofOracleAttack(Dfpn *s, const ProofOracle &o, int pl)
void operator()(Square) const
CallProofOracleDefense(Dfpn *s, const ProofOracle &o, int pl)
void operator()(Square) const
DfpnPathRecord * path_record
CArray< HashKey, DfpnMaxUniqMoves > hashes
void setCheckmateDefense(Player attack, const NumEffectState &state)
const PieceStand nextWhiteStand(Player P, Move move) const
void setNoCheckmateAttack(Player attack, const NumEffectState &state)
void setNoCheckmateDefense(Player attack, int best_i)
FixedCapacityVector< DfpnRecord, DfpnMaxUniqMoves > children
void setCheckmateChildInDefense(size_t i)
void setNoCheckmateChildInAttack(size_t i)
FixedCapacityVector< int8_t, DfpnMaxUniqMoves > proof_cost
void setCheckmateAttack(Player attack, int best_i)
FixedCapacityVector< const DfpnPathRecord *, DfpnMaxUniqMoves > children_path
const PathEncoding newPath(int c) const
const ProofOracle newOracle(Player P, Move move) const
bool traceable(Player P, Move move) const
bool inCheck(Player P) const
void newVisit(Player P, Move move, const HashKey &next_hash)
void dump(int lines, int depth=0) const
void setNoCheckmateChildInAttack(size_t best_i)
boost::scoped_array< Node > node
const Piece king(Player P) const
void setNoCheckmateDefense(Player attack, int best_i)
static const PieceStand leaf(const SimpleState &state, Player defender, const PieceStand max)
static const PieceStand defense(const PieceStand prev, Move move, const PieceStand max)
static void attackH(Player attacker, const State &, King8Info, Move move, unsigned int &proof_number, unsigned int &disproof_number)
攻撃側の move に対する proof_number と disproof_number を予想する
static const Move attack(const NumEffectState &state, Move check_move)
static const CArray< signed char, PTYPE_SIZE > attack_sacrifice_cost
static void addMonopolizedPieces(const SimpleState &state, Player player, const PieceStand max, PieceStand &out)
alt(player) が持っていない種類の持駒を playerが持っていたら out に独占分を加算する.
static const PieceStand leaf(const NumEffectState &state, Player attacker, const PieceStand max)
static const PieceStand attack(const PieceStand prev, Move move, const PieceStand max)
static int countBit(Integer mask)
static void generateCheapKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
static void generateKingEscape(const NumEffectState &state, FixedCapacityVector< Move, Capacity > &out)
不成の受けは作成しないので必要な場合はユーザが作成