dualDfpn.cc
Go to the documentation of this file.
/* dualDfpn.cc
*/
#include "osl/checkmate/dualDfpn.h"
#include "osl/checkmate/dfpn.h"
#include "osl/checkmate/dfpnRecord.h"
#ifdef OSL_DFPN_SMP
# include "osl/checkmate/dfpnParallel.h"
#endif
#include "osl/repetitionCounter.h"
#include "osl/stat/average.h"
#include "osl/centering3x3.h"
#include "osl/bits/centering5x3.h"
#ifdef OSL_SMP
# include "osl/misc/lightMutex.h"
# include <condition_variable>
#endif
#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
# include "osl/stat/ratio.h"
#endif
#include "osl/misc/milliSeconds.h"
#include "osl/oslConfig.h"
#include <unordered_map>
#include <forward_list>
#include <iostream>
#include <iomanip>
#define DFPN_SHARE_TABLE
static const int max_oracle_list_size = 2;
static const size_t local_table_growth_limit = 40000;
struct osl::checkmate::DualDfpn::OraclePool
{
struct Element
{
Dfpn::ProofOracle oracle;
PieceStand proof_pieces;
unsigned int id;
bool in_check;
Element() : oracle(HashKey(), PieceStand()), id((unsigned int)-1), in_check(false)
{
}
Element(const Dfpn::ProofOracle& o, PieceStand p, size_t i, bool c) : oracle(o), proof_pieces(p), id(i), in_check(c)
{
}
};
struct List : FixedCapacityVector<Element, max_oracle_list_size>
{
void add(const Element& e)
{
if (size() == capacity())
back() = e;
else
push_back(e);
}
};
#ifdef OSL_SMP
mutable std::mutex mutex;
#endif
typedef std::unordered_map<HashKey, List, std::hash<HashKey>> table_t;
table_t table;
Player defender;
void setAttack(Player attack)
{
defender = alt(attack);
}
void addProof(const NumEffectState& state, const HashKey& key, PieceStand proof_pieces)
{
const Dfpn::ProofOracle oracle(key, PieceStand(WHITE, state));
const std::pair<HashKey,HashKey> king = makeLargeKey(state);
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(mutex);;
#endif
const Element e(oracle, proof_pieces, table.size(), state.inCheck());
table[king.first].add(e);
table[king.second].add(e);
}
const List probe(const NumEffectState& state) const
{
const std::pair<HashKey,HashKey> key = makeLargeKey(state);
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(mutex);;
#endif
table_t::const_iterator p = table.find(key.first);
if (p != table.end())
return p->second;
p = table.find(key.second);
if (p != table.end())
return p->second;
return List();
}
template <Direction DIR>
static void addKey(HashKey& key, const SimpleState& state, Square target)
{
const Offset offset = DirectionTraits<DIR>::blackOffset();
target += offset; // 8 近傍全て試すなら手番による符合変換は不要
const Piece piece = state.pieceOnBoard(target);
HashGenTable::addHashKey(key, target, piece.ptypeO());
}
template <Direction DIR, Direction DIR2>
static void addKey(HashKey& key, const SimpleState& state, Square target)
{
const Offset offset = DirectionTraits<DIR>::blackOffset()
+ DirectionTraits<DIR2>::blackOffset();
target += offset;
const Piece piece = state.pieceOnBoard(target);
HashGenTable::addHashKey(key, target, piece.ptypeO());
}
const HashKey makeKey(const SimpleState& state) const
{
const Square target_king=state.kingSquare(defender);
const Square center = Centering3x3::adjustCenter(target_king);
HashKey key;
HashGenTable::addHashKey(key, center,
state.pieceOnBoard(center).ptypeO());
addKey<UL>(key, state, center); addKey<U> (key, state, center);
addKey<UR>(key, state, center);
addKey<L> (key, state, center); addKey<R> (key, state, center);
addKey<DL>(key, state, center); addKey<D> (key, state, center);
addKey<DR>(key, state, center);
return key;
}
const std::pair<HashKey,HashKey> makeLargeKey(const SimpleState& state) const
{
HashKey key_small = makeKey(state), key_large;
const Square target_king=state.kingSquare(defender);
const Square center = Centering5x3::adjustCenter(target_king);
HashGenTable::addHashKey(key_large, center,
state.pieceOnBoard(center).ptypeO());
addKey<UL>(key_large, state, center); addKey<U> (key_large, state, center);
addKey<UR>(key_large, state, center);
addKey<L> (key_large, state, center); addKey<R> (key_large, state, center);
addKey<DL>(key_large, state, center); addKey<D> (key_large, state, center);
addKey<DR>(key_large, state, center);
addKey<L,UL>(key_large, state, center); addKey<L,L> (key_large, state, center);
addKey<L,DL>(key_large, state, center);
addKey<R,UR>(key_large, state, center); addKey<R,R> (key_large, state, center);
addKey<R,DR>(key_large, state, center);
return std::make_pair(key_large, key_small);
}
};
struct osl::checkmate::DualDfpn::Shared
{
CArray<DfpnTable,2> table;
CArray<OraclePool,2> pool;
size_t main_node_count;
size_t simulation_count;
volatile size_t last_gc, gc_threshold;
CArray<stat::Average,max_oracle_list_size> proof_by_oracle;
CArray<bool,2> blocking_verify;
#ifdef OSL_SMP
std::mutex mutex;
std::condition_variable condition;
CArray<LightMutex,max_oracle_list_size> proof_by_oracle_mutex;
#endif
volatile int shared_table_user, shared_table_gc_wait;
#ifdef OSL_DFPN_SMP
std::unique_ptr<DfpnParallel> parallel_search;
#endif
typedef std::forward_list<PathEncoding> disproof_list_t;
typedef std::unordered_map<HashKey, disproof_list_t, std::hash<HashKey>> disproof_table_t;
disproof_table_t disproof_table;
Shared() : main_node_count(0), simulation_count(0), last_gc(0), gc_threshold(10),
shared_table_user(0), shared_table_gc_wait(0)
{
table[BLACK].setAttack(BLACK);
table[WHITE].setAttack(WHITE);
pool[BLACK].setAttack(BLACK);
pool[WHITE].setAttack(WHITE);
blocking_verify.fill(true);
}
~Shared()
{
showStats();
}
void showStats()
{
if (main_node_count || simulation_count) {
#ifdef DFPN_DEBUG
std::cerr << "shared " << main_node_count << " " << simulation_count << "\n";
for (stat::Average& a: proof_by_oracle)
std::cerr << a.getAverage()
<< " " << (int)(a.getAverage()*a.numElements()) << "\n";
std::cerr << "oracles " << pool[BLACK].table.size() << " " << pool[WHITE].table.size() << "\n";
std::cerr << "table " << table[0].totalSize() << " " << table[1].totalSize() << "\n";
table[0].showStats();
table[1].showStats();
#endif
}
}
void addMainNodeCount(int add)
{
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(mutex);;
#endif
main_node_count += add;
}
void addSimulationNodeCount(int add)
{
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(mutex);;
#endif
simulation_count += add;
}
struct TableUseLock
{
TableUseLock(const TableUseLock&) = delete;
TableUseLock& operator=(const TableUseLock&) = delete;
Shared *shared;
explicit TableUseLock(Shared *s) : shared(s)
{
# ifdef OSL_SMP
std::unique_lock<std::mutex> lk(shared->mutex);
while (shared->shared_table_user < 0) // in gc
shared->condition.wait(lk);
shared->shared_table_user++;
# endif
}
~TableUseLock()
{
# ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
assert(shared->shared_table_user > 0);
shared->shared_table_user--;
if (shared->shared_table_user == 0 && shared->shared_table_gc_wait)
shared->condition.notify_all();
# endif
}
};
};
struct osl::checkmate::DualDfpn::Local
{
Dfpn dfpn;
#ifndef DFPN_SHARE_TABLE
CArray<DfpnTable,2> table;
#endif
CArray<DfpnTable,2> table_small;
size_t local_node_count;
Local() : local_node_count(0)
{
#ifndef DFPN_SHARE_TABLE
table[BLACK].setAttack(BLACK);
table[WHITE].setAttack(WHITE);
#endif
table_small[BLACK].setAttack(BLACK);
table_small[WHITE].setAttack(WHITE);
}
~Local()
{
#ifdef DFPN_DEBUG
std::cerr << "local " << table_small[0].totalSize()
<< " " << table_small[1].totalSize() << "\n";
#endif
}
};
/* ------------------------------------------------------------------------- */
osl::checkmate::
DualDfpn::DualDfpn(uint64_t /*limit*/)
: shared(new Shared), local(new Local)
{
}
osl::checkmate::
DualDfpn::DualDfpn(const DualDfpn& src)
: shared(src.shared), local(new Local)
{
}
osl::checkmate::
DualDfpn::~DualDfpn()
{
}
osl::checkmate::Dfpn& osl::checkmate::
DualDfpn::prepareDfpn(Player attack)
{
#ifdef DFPN_SHARE_TABLE
local->dfpn.setTable(&(shared->table[attack]));
#else
local->dfpn.setTable(&(local->table[attack]));
#endif
local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
return local->dfpn;
}
osl::checkmate::Dfpn& osl::checkmate::
DualDfpn::prepareDfpnSmall(Player attack)
{
local->dfpn.setTable(&(local->table_small[attack]));
local->dfpn.setBlockingVerify(shared->blocking_verify[attack]);
return local->dfpn;
}
void osl::checkmate::
DualDfpn::runGC(bool verbose, size_t memory_use_ratio_1000)
{
#ifdef DFPN_SHARE_TABLE
const size_t unit_size = (sizeof(HashKey)+sizeof(DfpnRecord)+sizeof(char*)*2);
size_t removed = 0;
size_t total = shared->table[BLACK].size() + shared->table[WHITE].size();
size_t current_use = memory_use_ratio_1000*(OslConfig::memoryUseLimit()/1000);
if (total < local_table_growth_limit*8
|| total*unit_size*64 < OslConfig::memoryUseLimit()
|| (total*unit_size*3 < current_use
&& total*unit_size*8 < OslConfig::memoryUseLimit()))
return;
time_point start = clock::now();
{
{
# ifdef OSL_SMP
std::unique_lock<std::mutex> lk(shared->mutex);
# endif
total = shared->table[BLACK].size() + shared->table[WHITE].size();
if (total < local_table_growth_limit*8
|| (total*unit_size*3 < current_use
&& total*unit_size*6 < OslConfig::memoryUseLimit()))
return;
if (total < shared->last_gc + local_table_growth_limit*2)
return;
if (shared->shared_table_user > 0
&& memory_use_ratio_1000 < 650
&& total < shared->last_gc*2)
return;
if (shared->shared_table_user < 0 || shared->shared_table_gc_wait > 0)
return;
# ifdef OSL_SMP
while (shared->shared_table_user > 0) {
++shared->shared_table_gc_wait;
shared->condition.wait(lk);
--shared->shared_table_gc_wait;
}
if (shared->shared_table_user < 0)
return;
# endif
shared->shared_table_user--;
}
removed += shared->table[BLACK].smallTreeGC(shared->gc_threshold);
removed += shared->table[WHITE].smallTreeGC(shared->gc_threshold);
{
# ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
# endif
if (total > shared->last_gc*2) {
if (100.0*removed/total < 70)
shared->gc_threshold += 15;
else if (100.0*removed/total < 90)
shared->gc_threshold += 5;
}
shared->last_gc = total - removed;
shared->shared_table_user++;
assert(shared->shared_table_user == 0);
# ifdef OSL_SMP
shared->condition.notify_all();
# endif
}
}
if (! verbose)
return;
const double elapsed = elapsedSeconds(start);
if (removed > 10000 || elapsed > 0.1)
std::cerr << " GC " << removed
<< " entries " << std::setprecision(3)
<< (unit_size * removed / (1<<20)) << "MB "
<< 100.0*removed/total << "%"
<< " (" << elapsed << " s)\n";
#endif
}
template <osl::Player P>
osl::ProofDisproof osl::checkmate::
DualDfpn::findProof(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move& best_move, Move last_move)
{
assert(state.turn() == P);
// oracle
Dfpn& dfpn = prepareDfpn(P);
const OraclePool::List l(shared->pool[P].probe(state));
const PieceStand attack_stand = (P==BLACK) ? key.blackStand() : PieceStand(WHITE, state);
int num_tried = 0;
for (size_t i=0; i<l.size(); ++i)
{
if (! attack_stand.isSuperiorOrEqualTo(l[i].proof_pieces)
|| l[i].in_check != state.inCheck())
continue;
++num_tried;
const ProofDisproof pdp = (node_limit > 20)
? dfpn.tryProof(state, key, path, l[i].oracle, l[i].id, best_move, last_move)
: dfpn.tryProofLight(state, key, path, l[i].oracle, l[i].id, best_move, last_move);
const size_t count = dfpn.nodeCount();
local->local_node_count += count;
shared->addSimulationNodeCount(count);
if (count) {
#ifdef OSL_SMP
SCOPED_LOCK(lk,shared->proof_by_oracle_mutex[i]);
#endif
shared->proof_by_oracle[i].add(pdp.isCheckmateSuccess());
}
if (pdp.isCheckmateSuccess())
assert(best_move.isNormal());
if (pdp.isFinal())
return pdp;
}
if (node_limit == 0 && num_tried)
return ProofDisproof(1,1); // already tested table
const ProofDisproof table_pdp = dfpn.hasCheckmateMove(state, key, path, 0, best_move, last_move);
if (table_pdp.isCheckmateSuccess())
return table_pdp;
{
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
Shared::disproof_table_t::const_iterator p = shared->disproof_table.find(key);
if (p != shared->disproof_table.end()) {
for (const auto& ppath: p->second)
if (ppath == path)
return ProofDisproof::LoopDetection();
}
}
#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
static stat::Ratio migration_success("migration_success", true);
bool need_migration = false;
#endif
// local
if (node_limit < 80) {
if (local->table_small[P].totalSize() >= local_table_growth_limit) {
local->table_small[P].clear();
}
Dfpn& dfpn_small = prepareDfpnSmall(P);
const ProofDisproof pdp = dfpn_small.hasCheckmateMove(state, key, path, node_limit, best_move, last_move);
const size_t count = dfpn_small.nodeCount();
local->local_node_count += count;
shared->addMainNodeCount(count);
if (pdp.isLoopDetection()) {
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
shared->disproof_table[key].push_front(path);
}
if (! pdp.isCheckmateSuccess())
return pdp;
assert(best_move.isNormal());
// fall through if checkmate success (TODO: efficient proof tree migration)
#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
need_migration = true;
#endif
}
// main
Shared::TableUseLock lk(&*shared);
PieceStand proof_pieces;
const ProofDisproof pdp = dfpn.hasCheckmateMove(state, key, path, node_limit, best_move, proof_pieces, last_move);
const size_t count = dfpn.nodeCount();
local->local_node_count += count;
shared->addMainNodeCount(count);
if (pdp.isCheckmateSuccess())
shared->pool[P].addProof(state, key, proof_pieces);
#ifdef OSL_SHOW_PROOF_TREE_MIGRATION_STAT
if (need_migration)
migration_success.add(pdp.isCheckmateSuccess());
#endif
if (pdp.isLoopDetection()) {
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
shared->disproof_table[key].push_front(path);
}
if (pdp.isCheckmateSuccess())
assert(best_move.isNormal());
return pdp;
}
osl::checkmate::ProofDisproof osl::checkmate::
DualDfpn::findProof(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move& best_move, Move last_move)
{
if (state.turn() == BLACK)
return findProof<BLACK>(node_limit, state, key, path, best_move, last_move);
else
return findProof<WHITE>(node_limit, state, key, path, best_move, last_move);
}
bool osl::checkmate::
DualDfpn::isWinningState(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move& best_move, Move last_move)
{
return findProof(node_limit, state, key, path, best_move, last_move)
.isCheckmateSuccess();
}
#ifdef OSL_DFPN_SMP
template <osl::Player P>
bool osl::checkmate::
DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move& best_move, Move last_move)
{
PieceStand proof_pieces;
size_t count;
ProofDisproof pdp;
{
#ifdef OSL_SMP
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
if (! shared->parallel_search)
shared->parallel_search.reset(new DfpnParallel(std::min(OslConfig::concurrency(), 8)));
#ifdef DFPN_SHARE_TABLE
shared->parallel_search->setTable(&(shared->table[P]));
#else
shared->parallel_search->setTable(&(local->table[P]));
#endif
pdp = shared->parallel_search->hasCheckmateMove
(state, key, path, node_limit, best_move, proof_pieces, last_move);
count = shared->parallel_search->nodeCount();
}
shared->addMainNodeCount(count);
if (pdp.isCheckmateSuccess())
shared->pool[P].addProof(state, key, proof_pieces);
if (pdp.isLoopDetection()) {
shared->disproof_table[key].push_front(path);
}
if (pdp.isCheckmateSuccess())
assert(best_move.isNormal());
return pdp.isCheckmateSuccess();
}
bool osl::checkmate::
DualDfpn::isWinningStateParallel(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move& best_move, Move last_move)
{
if (state.turn() == BLACK)
return isWinningStateParallel<BLACK>(node_limit, state, key, path, best_move, last_move);
else
return isWinningStateParallel<WHITE>(node_limit, state, key, path, best_move, last_move);
}
#endif
template <osl::Player P>
bool
osl::checkmate::
DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move last_move)
{
Shared::TableUseLock lk(&*shared);
assert(state.turn() == P);
Dfpn& dfpn = prepareDfpn(alt(P));
const ProofDisproof pdp = dfpn.hasEscapeMove(state, key, path, node_limit, last_move);
const size_t count = dfpn.nodeCount();
local->local_node_count += count;
shared->addMainNodeCount(count);
return pdp.isCheckmateSuccess();
}
bool osl::checkmate::
DualDfpn::isLosingState(int node_limit, const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
Move last_move)
{
if (state.turn() == BLACK)
return isLosingState<BLACK>(node_limit, state, key, path, last_move);
else
return isLosingState<WHITE>(node_limit, state, key, path, last_move);
}
void osl::checkmate::
DualDfpn::writeRootHistory(const RepetitionCounter& counter,
const MoveStack& moves,
const SimpleState& state, Player attack)
{
// TODO: 局面表をクリアしてしまうと忘れられる => DualDfpn 内で記憶した方が良い
Shared::TableUseLock lk(&*shared);
Dfpn& dfpn = prepareDfpn(attack);
PieceStand white_stand(WHITE, state);
for (int i=0; i<counter.checkCount(attack); ++i)
{
const HashKey& key = counter.history().top(i);
if (key != counter.history().top(0)) // ignore current state
{
dfpn.setIllegal(key, white_stand);
}
assert(moves.hasLastMove(i+1)); // oops, different index
if (! moves.hasLastMove(i+1))
break;
const Move last_move = moves.lastMove(i+1);
if (last_move.isNormal())
white_stand = white_stand.previousStand(WHITE, last_move);
}
}
void osl::checkmate::
DualDfpn::setRootPlayer(Player root)
{
shared->blocking_verify[root] = true;
shared->blocking_verify[alt(root)] = true; // TODO: set false when issues around proof pieces are corrected
}
void osl::checkmate::
DualDfpn::setVerbose(int /*level*/)
{
}
int osl::checkmate::
DualDfpn::distance(Player attack, const HashKey& key)
{
Shared::TableUseLock lk(&*shared);
return prepareDfpn(attack).distance(key);
}
size_t osl::checkmate::
DualDfpn::mainNodeCount() const
{
#ifdef OSL_USE_RACE_DETECTOR
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
return shared->main_node_count;
// return shared->table[BLACK].totalSize() + shared->table[WHITE].totalSize();
}
size_t osl::checkmate::
DualDfpn::totalNodeCount() const
{
#ifdef OSL_USE_RACE_DETECTOR
std::lock_guard<std::mutex> lk(shared->mutex);
#endif
return shared->main_node_count + shared->simulation_count;
}
const osl::checkmate::DfpnTable& osl::checkmate::
DualDfpn::table(Player attack) const
{
return shared->table[attack];
}
namespace osl
{
template ProofDisproof checkmate::DualDfpn::findProof<BLACK>
(int, const NumEffectState&, const HashKey&, const PathEncoding&,
Move&, Move);
template ProofDisproof checkmate::DualDfpn::findProof<WHITE>
(int, const NumEffectState&, const HashKey&, const PathEncoding&,
Move&, Move);
template bool checkmate::DualDfpn::isLosingState<BLACK>
(int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
template bool checkmate::DualDfpn::isLosingState<WHITE>
(int, const NumEffectState&, const HashKey&, const PathEncoding&, Move);
#ifdef OSL_DFPN_SMP
template bool checkmate::DualDfpn::isWinningStateParallel<BLACK>
(int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
template bool checkmate::DualDfpn::isWinningStateParallel<WHITE>
(int, const NumEffectState&, const HashKey&, const PathEncoding&, Move&, Move);
#endif
}
/* ------------------------------------------------------------------------- */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
average.h
centering3x3.h
centering5x3.h
osl::FixedCapacityVector< Element, max_oracle_list_size >::size
size_t size() const
Definition container.h:243
osl::FixedCapacityVector< Element, max_oracle_list_size >::push_back
void push_back(const Element &e)
Definition container.h:204
osl::FixedCapacityVector< Element, max_oracle_list_size >::FixedCapacityVector
FixedCapacityVector()
Definition container.h:159
osl::FixedCapacityVector< Element, max_oracle_list_size >::back
Element & back()
Definition container.h:202
osl::FixedCapacityVector< Element, max_oracle_list_size >::capacity
size_t capacity() const
Definition container.h:245
osl::Move
圧縮していない moveの表現 .
Definition basic_type.h:1052
osl::Move::isNormal
bool isNormal() const
INVALID でも PASS でもない.
Definition basic_type.h:1088
osl::NumEffectState
利きを持つ局面
Definition numEffectState.h:34
osl::NumEffectState::inCheck
bool inCheck(Player P) const
Pの玉が王手状態
Definition numEffectState.h:88
osl::PieceStand
片方の手番の持駒の枚数を記録するクラス.
Definition bits/pieceStand.h:38
osl::PieceStand::isSuperiorOrEqualTo
bool isSuperiorOrEqualTo(PieceStand other) const
Definition bits/pieceStand.h:138
osl::PieceStand::previousStand
const PieceStand previousStand(Player pl, Move move) const
Definition bits/pieceStand.h:226
osl::RepetitionCounter
千日手の検出.
Definition repetitionCounter.h:21
osl::RepetitionCounter::checkCount
int checkCount(Player attack) const
Definition repetitionCounter.h:91
osl::RepetitionCounter::history
const HashKeyStack & history() const
Definition repetitionCounter.h:95
osl::SimpleState
Definition simpleState.h:35
osl::SimpleState::turn
Player turn() const
Definition simpleState.h:220
osl::checkmate::DfpnRecord
Definition dfpnRecord.h:58
osl::checkmate::DfpnTable
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
osl::checkmate::Dfpn
詰探索
Definition dfpn.h:107
osl::checkmate::Dfpn::hasEscapeMove
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition dfpn.cc:1469
osl::checkmate::Dfpn::nodeCount
size_t nodeCount() const
Definition dfpn.h:152
osl::checkmate::Dfpn::tryProofLight
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())
Definition dfpn.cc:1401
osl::checkmate::Dfpn::setIllegal
void setIllegal(const HashKey &key, PieceStand white)
Definition dfpn.cc:1311
osl::checkmate::Dfpn::tryProof
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())
Definition dfpn.cc:1393
osl::checkmate::Dfpn::hasCheckmateMove
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)
Definition dfpn.cc:1329
osl::checkmate::DualDfpn::runGC
void runGC(bool verbose=false, size_t memory_use_ratio_1000=0)
Definition dualDfpn.cc:301
osl::checkmate::DualDfpn::isLosingState
bool isLosingState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move last_move=Move::INVALID())
Definition dualDfpn.cc:551
osl::checkmate::DualDfpn::prepareDfpn
Dfpn & prepareDfpn(Player attack)
Definition dualDfpn.cc:281
osl::checkmate::DualDfpn::setVerbose
void setVerbose(int level=1)
Definition dualDfpn.cc:609
osl::checkmate::DualDfpn::isWinningState
bool isWinningState(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
詰みを発見.
Definition dualDfpn.h:51
osl::checkmate::DualDfpn::totalNodeCount
size_t totalNodeCount() const
Definition dualDfpn.cc:631
osl::checkmate::DualDfpn::~DualDfpn
~DualDfpn()
Definition dualDfpn.cc:276
osl::checkmate::DualDfpn::prepareDfpnSmall
Dfpn & prepareDfpnSmall(Player attack)
Definition dualDfpn.cc:293
osl::checkmate::DualDfpn::findProof
ProofDisproof findProof(int node_limit, const NumEffectState &state, const HashKey &key, const PathEncoding &path, Move &best_move, Move last_move=Move::INVALID())
osl::checkmate::DualDfpn::mainNodeCount
size_t mainNodeCount() const
Definition dualDfpn.cc:621
osl::checkmate::DualDfpn::distance
int distance(Player attack, const HashKey &key)
Definition dualDfpn.cc:614
osl::checkmate::DualDfpn::writeRootHistory
void writeRootHistory(const RepetitionCounter &counter, const MoveStack &moves, const SimpleState &state, Player attack)
Definition dualDfpn.cc:577
osl::checkmate::DualDfpn::shared
std::shared_ptr< Shared > shared
Definition dualDfpn.h:33
osl::checkmate::DualDfpn::setRootPlayer
void setRootPlayer(Player)
Definition dualDfpn.cc:602
osl::checkmate::DualDfpn::table
const DfpnTable & table(Player) const
Definition dualDfpn.cc:640
osl::checkmate::DualDfpn::DualDfpn
DualDfpn(uint64_t ignored=std::numeric_limits< uint64_t >::max())
Definition dualDfpn.cc:264
osl::checkmate::DualDfpn::local
std::unique_ptr< Local > local
Definition dualDfpn.h:34
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition proofDisproof.h:17
osl::checkmate::ProofDisproof::isFinal
bool isFinal() const
Definition proofDisproof.h:88
osl::checkmate::ProofDisproof::LoopDetection
static const ProofDisproof LoopDetection()
Definition proofDisproof.h:78
osl::checkmate::ProofDisproof::isCheckmateSuccess
bool isCheckmateSuccess() const
Definition proofDisproof.h:86
osl::checkmate::ProofDisproof::isLoopDetection
bool isLoopDetection() const
Definition proofDisproof.h:97
osl::container::MoveStack
Move のstack.
Definition moveStack.h:15
osl::container::MoveStack::hasLastMove
bool hasLastMove(size_t last=1) const
Definition moveStack.h:27
osl::container::MoveStack::lastMove
const Move lastMove(size_t last=1) const
Definition moveStack.h:28
osl::hash::HashKey128::blackStand
const PieceStand blackStand() const
Definition hashKey.h:64
osl::hash::HashKeyStack::top
const HashKey & top(size_t n=0) const
Definition hashKeyStack.h:23
osl::hash::HashKey
Definition hashKey.h:153
osl::stat::Ratio
Definition ratio.h:13
osl::stat::Ratio::add
void add(bool success)
Definition ratio.h:22
dfpnParallel.h
dfpnRecord.h
dfpn.h
local_table_growth_limit
static const size_t local_table_growth_limit
Definition dualDfpn.cc:30
max_oracle_list_size
static const int max_oracle_list_size
Definition dualDfpn.cc:29
dualDfpn.h
lightMutex.h
SCOPED_LOCK
#define SCOPED_LOCK(lock, m)
Definition lightMutex.h:176
milliSeconds.h
PathEncoding
Definition pathEncoding.cc:12
osl::misc::time_point
std::chrono::time_point< clock > time_point
Definition milliSeconds.h:18
osl
Definition additionalEffect.h:6
osl::elapsedSeconds
double elapsedSeconds(time_point start)
Definition milliSeconds.h:29
osl::Player
Player
Definition basic_type.h:8
osl::WHITE
@ WHITE
Definition basic_type.h:10
osl::BLACK
@ BLACK
Definition basic_type.h:9
osl::alt
constexpr Player alt(Player player)
Definition basic_type.h:13
oslConfig.h
ratio.h
repetitionCounter.h
osl::OslConfig::concurrency
static int concurrency()
Definition oslConfig.cc:133
osl::OslConfig::memoryUseLimit
static size_t memoryUseLimit()
Definition oslConfig.h:59
checkmate::DualDfpn::Local::table_small
CArray< DfpnTable, 2 > table_small
Definition dualDfpn.cc:241
checkmate::DualDfpn::Local::~Local
~Local()
Definition dualDfpn.cc:252
checkmate::DualDfpn::Local::Local
Local()
Definition dualDfpn.cc:243
checkmate::DualDfpn::Local::dfpn
Dfpn dfpn
Definition dualDfpn.cc:237
checkmate::DualDfpn::Local::local_node_count
size_t local_node_count
Definition dualDfpn.cc:242
checkmate::DualDfpn::OraclePool::Element
Definition dualDfpn.cc:34
checkmate::DualDfpn::OraclePool::Element::Element
Element()
Definition dualDfpn.cc:39
checkmate::DualDfpn::OraclePool::Element::oracle
Dfpn::ProofOracle oracle
Definition dualDfpn.cc:35
checkmate::DualDfpn::OraclePool::Element::Element
Element(const Dfpn::ProofOracle &o, PieceStand p, size_t i, bool c)
Definition dualDfpn.cc:42
checkmate::DualDfpn::OraclePool::Element::proof_pieces
PieceStand proof_pieces
Definition dualDfpn.cc:36
checkmate::DualDfpn::OraclePool::Element::id
unsigned int id
Definition dualDfpn.cc:37
checkmate::DualDfpn::OraclePool::Element::in_check
bool in_check
Definition dualDfpn.cc:38
checkmate::DualDfpn::OraclePool::List
Definition dualDfpn.cc:47
checkmate::DualDfpn::OraclePool::List::add
void add(const Element &e)
Definition dualDfpn.cc:48
checkmate::DualDfpn::OraclePool::addKey
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition dualDfpn.cc:101
checkmate::DualDfpn::OraclePool::probe
const List probe(const NumEffectState &state) const
Definition dualDfpn.cc:77
checkmate::DualDfpn::OraclePool::makeLargeKey
const std::pair< HashKey, HashKey > makeLargeKey(const SimpleState &state) const
Definition dualDfpn.cc:123
checkmate::DualDfpn::OraclePool::table
table_t table
Definition dualDfpn.cc:60
checkmate::DualDfpn::OraclePool::table_t
std::unordered_map< HashKey, List, std::hash< HashKey > > table_t
Definition dualDfpn.cc:59
checkmate::DualDfpn::OraclePool::setAttack
void setAttack(Player attack)
Definition dualDfpn.cc:62
checkmate::DualDfpn::OraclePool::makeKey
const HashKey makeKey(const SimpleState &state) const
Definition dualDfpn.cc:109
checkmate::DualDfpn::OraclePool::defender
Player defender
Definition dualDfpn.cc:61
checkmate::DualDfpn::OraclePool::addKey
static void addKey(HashKey &key, const SimpleState &state, Square target)
Definition dualDfpn.cc:93
checkmate::DualDfpn::OraclePool::addProof
void addProof(const NumEffectState &state, const HashKey &key, PieceStand proof_pieces)
Definition dualDfpn.cc:66
checkmate::DualDfpn::Shared::TableUseLock::TableUseLock
TableUseLock(const TableUseLock &)=delete
checkmate::DualDfpn::Shared::TableUseLock::TableUseLock
TableUseLock(Shared *s)
Definition dualDfpn.cc:213
checkmate::DualDfpn::Shared::TableUseLock::~TableUseLock
~TableUseLock()
Definition dualDfpn.cc:222
checkmate::DualDfpn::Shared::TableUseLock::shared
Shared * shared
Definition dualDfpn.cc:212
checkmate::DualDfpn::Shared::TableUseLock::operator=
TableUseLock & operator=(const TableUseLock &)=delete
checkmate::DualDfpn::Shared
Definition dualDfpn.cc:144
checkmate::DualDfpn::Shared::pool
CArray< OraclePool, 2 > pool
Definition dualDfpn.cc:146
checkmate::DualDfpn::Shared::main_node_count
size_t main_node_count
Definition dualDfpn.cc:147
checkmate::DualDfpn::Shared::addSimulationNodeCount
void addSimulationNodeCount(int add)
Definition dualDfpn.cc:200
checkmate::DualDfpn::Shared::addMainNodeCount
void addMainNodeCount(int add)
Definition dualDfpn.cc:193
checkmate::DualDfpn::Shared::~Shared
~Shared()
Definition dualDfpn.cc:174
checkmate::DualDfpn::Shared::blocking_verify
CArray< bool, 2 > blocking_verify
Definition dualDfpn.cc:151
checkmate::DualDfpn::Shared::disproof_list_t
std::forward_list< PathEncoding > disproof_list_t
Definition dualDfpn.cc:161
checkmate::DualDfpn::Shared::shared_table_user
volatile int shared_table_user
Definition dualDfpn.cc:157
checkmate::DualDfpn::Shared::Shared
Shared()
Definition dualDfpn.cc:165
checkmate::DualDfpn::Shared::simulation_count
size_t simulation_count
Definition dualDfpn.cc:148
checkmate::DualDfpn::Shared::shared_table_gc_wait
volatile int shared_table_gc_wait
Definition dualDfpn.cc:157
checkmate::DualDfpn::Shared::disproof_table_t
std::unordered_map< HashKey, disproof_list_t, std::hash< HashKey > > disproof_table_t
Definition dualDfpn.cc:162
checkmate::DualDfpn::Shared::showStats
void showStats()
Definition dualDfpn.cc:178
checkmate::DualDfpn::Shared::last_gc
volatile size_t last_gc
Definition dualDfpn.cc:149
checkmate::DualDfpn::Shared::proof_by_oracle
CArray< stat::Average, max_oracle_list_size > proof_by_oracle
Definition dualDfpn.cc:150
checkmate::DualDfpn::Shared::disproof_table
disproof_table_t disproof_table
Definition dualDfpn.cc:163
checkmate::DualDfpn::Shared::gc_threshold
volatile size_t gc_threshold
Definition dualDfpn.cc:149
checkmate::DualDfpn::Shared::table
CArray< DfpnTable, 2 > table
Definition dualDfpn.cc:145