dfpn.h
Go to the documentation of this file.
/* dfpn.h
*/
#ifndef OSL_DFPN_H
#define OSL_DFPN_H
#include "osl/checkmate/proofDisproof.h"
#include "osl/numEffectState.h"
#include "osl/hashKey.h"
#include "osl/pathEncoding.h"
#include "osl/config.h"
#include <boost/scoped_array.hpp>
#ifdef OSL_SMP
# ifndef OSL_DFPN_SMP
# define OSL_DFPN_SMP
# endif
#endif
#ifdef OSL_DFPN_SMP
# include "osl/misc/lightMutex.h"
# include <mutex>
#endif
namespace osl
{
namespace checkmate
{
class DfpnRecord;
class DfpnTable
{
struct Table;
struct List;
boost::scoped_array<Table> table;
size_t total_size;
int dfpn_max_depth;
size_t growth_limit, gc_threshold;
public:
DfpnTable(Player attack);
DfpnTable();
~DfpnTable();
template <Player Attack>
const DfpnRecord probe(const HashKey& key, PieceStand white) const;
const DfpnRecord probe(const HashKey& key, PieceStand white) const;
size_t estimateNodeCount(const HashKey& key, bool dominance_max=false) const;
template <Player Attack>
const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
template <Player Attack>
void showProofOracles(const HashKey& key, PieceStand white, Move last_move=Move()) const;
size_t
#ifdef __GNUC__
__attribute__ ((pure))
#endif
size() const;
void showStats() const;
void setAttack(Player);
void setWorking(const HashKey& key, const DfpnRecord& value, int thread_id);
void leaveWorking(const HashKey& key, int thread_id);
void store(const HashKey& key, DfpnRecord& value, int leaving_thread_id=-1);
void addDag(const HashKey& key, DfpnRecord& value);
void clear();
size_t totalSize() { return total_size; }
Player attack() const;
void setMaxDepth(int);
int maxDepth() const;
void testTable();
size_t smallTreeGC(size_t threshold=10);
void setGrowthLimit(size_t new_limit);
size_t growthLimit() const { return growth_limit; }
bool runGC();
private:
#ifdef OSL_DFPN_SMP
typedef osl::misc::LightMutex Mutex;
# ifdef USE_TBB_HASH
static const int DIVSIZE=1;
# else
static const int DIVSIZE=256;
mutable CArray<Mutex,DIVSIZE> mutex;
# endif
// typedef boost::mutex Mutex;
// TODO: boost::thread::shared_lock (available version >= 1.35) for multi read accessess
LightMutex root_mutex;
#else
static const int DIVSIZE=1;
#endif
static int keyToIndex(const HashKey& key)
{
unsigned long val=key.signature();
return (val>>24)%DIVSIZE;
}
template <Player Attack>
List *find(const HashKey& key, int subindex);
template <Player Attack>
const List *find(const HashKey& key, int subindex) const;
const List *find(const HashKey& key, int subindex) const;
};
class DfpnPathTable;
class DfpnShared;
class Dfpn
{
Dfpn(const Dfpn&) = delete;
Dfpn& operator=(const Dfpn&) = delete;
public:
enum { DfpnMaxUniqMoves = CheckOrEscapeMaxUniqMoves };
typedef CheckMoveVector DfpnMoveVector;
typedef DfpnTable table_t;
private:
DfpnTable *table;
struct NodeBase;
struct Node;
struct Tree;
std::unique_ptr<Tree> tree;
std::unique_ptr<DfpnPathTable> path_table;
size_t node_count;
size_t node_count_limit;
DfpnShared *parallel_shared;
int thread_id;
bool blocking_verify;
public:
Dfpn();
~Dfpn();
void setTable(DfpnTable *new_table);
void setIllegal(const HashKey& key, PieceStand white);
void setBlockingVerify(bool enable=true) { blocking_verify = enable; }
void setParallel(int id, DfpnShared *s)
{
if (s)
assert(id >= 0);
thread_id = id;
parallel_shared = s;
}
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
hasCheckmateMove(const NumEffectState& state, const HashKey& key,
const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof,
Move last_move=Move::INVALID(), std::vector<Move> *pv=0);
const ProofDisproof
hasEscapeMove(const NumEffectState& state,
const HashKey& key, const PathEncoding& path,
size_t limit, Move last_move);
size_t nodeCount() const { return node_count; }
const DfpnTable& currentTable() const { return *table; }
void analyze(const PathEncoding& path,
const NumEffectState& state, const std::vector<Move>& moves) const;
void clear();
// private:
template <Player P> void attack();
template <Player P> void defense();
template <Player P> struct CallAttack;
template <Player P> struct CallDefense;
struct DepthLimitReached {};
struct ProofOracle;
template <Player P, bool UseTable> void proofOracleAttack(const ProofOracle& oracle, int proof_limit);
template <Player P, bool UseTable> void proofOracleDefense(const ProofOracle& oracle, int proof_limit);
template <Player P, bool UseTable> struct CallProofOracleAttack;
template <Player P, bool UseTable> struct CallProofOracleDefense;
template <Player P> void blockingSimulation(int seed, const ProofOracle&);
template <Player P> void grandParentSimulation(int cur_move, const Node& gparent, int gp_move);
private:
template <bool UseTable>
const ProofDisproof
tryProofMain(const NumEffectState& state, const HashKey& key,
const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
Move last_move);
public:
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
tryProofLight(const NumEffectState& state, const HashKey& key,
const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
Move last_move=Move::INVALID());
// debug
int distance(const HashKey&) const;
template <Player P>
static void generateCheck(const NumEffectState&, DfpnMoveVector&, bool&);
template <Player P>
static void generateEscape(const NumEffectState&, bool need_full_width,
Square grand_parent_delay_last_to, DfpnMoveVector&);
bool grandParentSimulationSuitable() const;
template <Player Turn>
static void sort(const NumEffectState&, DfpnMoveVector&);
private:
void findDagSource();
void findDagSource(const HashKey& terminal_key,
DfpnRecord& terminal_record,
PieceStand terminal_stand, int offset=0);
};
}
}
struct osl::checkmate::Dfpn::ProofOracle
{
HashKey key;
PieceStand white_stand;
ProofOracle(const HashKey& k, PieceStand w) : key(k), white_stand(w)
{
}
const ProofOracle newOracle(Player P, Move move) const
{
assert(P == move.player());
return ProofOracle(key.newHashWithMove(move),
(P == WHITE) ? white_stand.nextStand(P, move) : white_stand);
}
bool traceable(Player P, Move move) const
{
assert(P == move.player());
if (! move.isDrop())
return true;
if (P == BLACK) {
if (key.blackStand().get(move.ptype()) == 0)
return false;
}
else {
if (white_stand.get(move.ptype()) == 0)
return false;
}
return true;
}
};
#endif /* OSL_DFPN_H */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
osl::CArray
Definition container.h:20
osl::CheckMoveVector
Definition container.h:301
osl::Move
圧縮していない moveの表現 .
Definition basic_type.h:1052
osl::Move::INVALID
static const Move INVALID()
Definition basic_type.h:1095
osl::Move::ptype
Ptype ptype() const
Definition basic_type.h:1155
osl::Move::player
Player player() const
Definition basic_type.h:1195
osl::Move::isDrop
bool isDrop() const
Definition basic_type.h:1150
osl::NumEffectState
利きを持つ局面
Definition numEffectState.h:34
osl::PieceStand
片方の手番の持駒の枚数を記録するクラス.
Definition bits/pieceStand.h:38
osl::Square
Definition basic_type.h:532
osl::checkmate::DfpnPathTable
Definition dfpn.cc:270
osl::checkmate::DfpnRecord
Definition dfpnRecord.h:58
osl::checkmate::DfpnShared
Definition dfpnParallel.h:14
osl::checkmate::DfpnTable
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
osl::checkmate::DfpnTable::DfpnTable
DfpnTable()
Definition dfpn.cc:902
osl::checkmate::DfpnTable::size
size_t size() const
Definition dfpn.cc:1251
osl::checkmate::DfpnTable::DIVSIZE
static const int DIVSIZE
Definition dfpn.h:88
osl::checkmate::DfpnTable::growthLimit
size_t growthLimit() const
Definition dfpn.h:73
osl::checkmate::DfpnTable::setMaxDepth
void setMaxDepth(int)
Definition dfpn.cc:931
osl::checkmate::DfpnTable::dfpn_max_depth
int dfpn_max_depth
Definition dfpn.h:35
osl::checkmate::DfpnTable::store
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition dfpn.cc:1074
osl::checkmate::DfpnTable::DfpnTable
DfpnTable(Player attack)
Definition dfpn.cc:893
osl::checkmate::DfpnTable::keyToIndex
static int keyToIndex(const HashKey &key)
Definition dfpn.h:90
osl::checkmate::DfpnTable::find
List * find(const HashKey &key, int subindex)
osl::checkmate::DfpnTable::total_size
size_t total_size
Definition dfpn.h:34
osl::checkmate::DfpnTable::findProofOracle
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
osl::checkmate::DfpnTable::maxDepth
int maxDepth() const
Definition dfpn.cc:936
osl::checkmate::DfpnTable::find
const List * find(const HashKey &key, int subindex) const
osl::checkmate::DfpnTable::showProofOracles
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition dfpn.cc:1047
osl::checkmate::DfpnTable::runGC
bool runGC()
Definition dfpn.cc:1217
osl::checkmate::DfpnTable::estimateNodeCount
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition dfpn.cc:1061
osl::checkmate::DfpnTable::attack
Player attack() const
Definition dfpn.cc:950
osl::checkmate::DfpnTable::totalSize
size_t totalSize()
Definition dfpn.h:63
osl::checkmate::DfpnTable::testTable
void testTable()
Definition dfpn.cc:1169
osl::checkmate::DfpnTable::setWorking
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition dfpn.cc:1117
osl::checkmate::DfpnTable::~DfpnTable
~DfpnTable()
Definition dfpn.cc:907
osl::checkmate::DfpnTable::addDag
void addDag(const HashKey &key, DfpnRecord &value)
Definition dfpn.cc:1098
osl::checkmate::DfpnTable::gc_threshold
size_t gc_threshold
Definition dfpn.h:36
osl::checkmate::DfpnTable::showStats
void showStats() const
Definition dfpn.cc:921
osl::checkmate::DfpnTable::setGrowthLimit
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition dfpn.cc:912
osl::checkmate::DfpnTable::leaveWorking
void leaveWorking(const HashKey &key, int thread_id)
Definition dfpn.cc:1140
osl::checkmate::DfpnTable::probe
const DfpnRecord probe(const HashKey &key, PieceStand white) const
osl::checkmate::DfpnTable::table
boost::scoped_array< Table > table
Definition dfpn.h:33
osl::checkmate::DfpnTable::setAttack
void setAttack(Player)
Definition dfpn.cc:942
osl::checkmate::DfpnTable::clear
void clear()
Definition dfpn.cc:1157
osl::checkmate::DfpnTable::growth_limit
size_t growth_limit
Definition dfpn.h:36
osl::checkmate::DfpnTable::smallTreeGC
size_t smallTreeGC(size_t threshold=10)
Definition dfpn.cc:1191
osl::checkmate::Dfpn::generateCheck
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
Definition dfpn.cc:1573
osl::checkmate::Dfpn::distance
int distance(const HashKey &) const
Definition dfpn.cc:3131
osl::checkmate::Dfpn::generateEscape
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
Definition dfpn.cc:2105
osl::checkmate::Dfpn::DfpnMoveVector
CheckMoveVector DfpnMoveVector
Definition dfpn.h:112
osl::checkmate::Dfpn::operator=
Dfpn & operator=(const Dfpn &)=delete
osl::checkmate::Dfpn::proofOracleAttack
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition dfpn.cc:2746
osl::checkmate::Dfpn::tree
std::unique_ptr< Tree > tree
Definition dfpn.h:119
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::table_t
DfpnTable table_t
Definition dfpn.h:113
osl::checkmate::Dfpn::sort
static void sort(const NumEffectState &, DfpnMoveVector &)
Definition dfpn.cc:1555
osl::checkmate::Dfpn::nodeCount
size_t nodeCount() const
Definition dfpn.h:152
osl::checkmate::Dfpn::Dfpn
Dfpn()
Definition dfpn.cc:1287
osl::checkmate::Dfpn::analyze
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
Definition dfpn.cc:2651
osl::checkmate::Dfpn::parallel_shared
DfpnShared * parallel_shared
Definition dfpn.h:123
osl::checkmate::Dfpn::~Dfpn
~Dfpn()
Definition dfpn.cc:1292
osl::checkmate::Dfpn::grandParentSimulation
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
Definition dfpn.cc:3096
osl::checkmate::Dfpn::attack
void attack()
Definition dfpn.cc:1656
osl::checkmate::Dfpn::path_table
std::unique_ptr< DfpnPathTable > path_table
Definition dfpn.h:120
osl::checkmate::Dfpn::DfpnMaxUniqMoves
@ DfpnMaxUniqMoves
Definition dfpn.h:111
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::blocking_verify
bool blocking_verify
Definition dfpn.h:125
osl::checkmate::Dfpn::grandParentSimulationSuitable
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
Definition dfpn.cc:2162
osl::checkmate::Dfpn::node_count
size_t node_count
Definition dfpn.h:121
osl::checkmate::Dfpn::setIllegal
void setIllegal(const HashKey &key, PieceStand white)
Definition dfpn.cc:1311
osl::checkmate::Dfpn::blockingSimulation
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
Definition dfpn.cc:3046
osl::checkmate::Dfpn::currentTable
const DfpnTable & currentTable() const
Definition dfpn.h:153
osl::checkmate::Dfpn::proofOracleDefense
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
Definition dfpn.cc:2872
osl::checkmate::Dfpn::Dfpn
Dfpn(const Dfpn &)=delete
osl::checkmate::Dfpn::setParallel
void setParallel(int id, DfpnShared *s)
Definition dfpn.h:132
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::Dfpn::tryProofMain
const ProofDisproof tryProofMain(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move)
osl::checkmate::Dfpn::node_count_limit
size_t node_count_limit
Definition dfpn.h:122
osl::checkmate::Dfpn::clear
void clear()
Definition dfpn.cc:1305
osl::checkmate::Dfpn::setTable
void setTable(DfpnTable *new_table)
Definition dfpn.cc:1296
osl::checkmate::Dfpn::setBlockingVerify
void setBlockingVerify(bool enable=true)
Definition dfpn.h:131
osl::checkmate::Dfpn::thread_id
int thread_id
Definition dfpn.h:124
osl::checkmate::Dfpn::table
DfpnTable * table
Definition dfpn.h:115
osl::checkmate::Dfpn::findDagSource
void findDagSource()
Definition dfpn.cc:1647
osl::checkmate::Dfpn::defense
void defense()
Definition dfpn.cc:2183
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition proofDisproof.h:17
osl::hash::HashKey128::signature
uint64_t signature() const
Definition hashKey.h:57
osl::hash::HashKey
Definition hashKey.h:153
osl::misc::LightMutex
Definition lightMutex.h:51
config.h
threshold
static const osl::CArray2d< int, 8, 16 > threshold
Definition featureSet.cc:518
hashKey.h
lightMutex.h
PathEncoding
Definition pathEncoding.cc:12
osl::checkmate
Definition king8Info.h:12
osl
Definition additionalEffect.h:6
osl::CheckOrEscapeMaxUniqMoves
@ CheckOrEscapeMaxUniqMoves
Definition container.h:299
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::__attribute__
const PtypeO PTYPEO_EDGE __attribute__((unused))
numEffectState.h
pathEncoding.h
proofDisproof.h
osl::checkmate::DfpnTable::List
Definition dfpn.cc:619
osl::checkmate::DfpnTable::Table
Definition dfpn.cc:886
osl::checkmate::Dfpn::CallProofOracleAttack
Definition dfpn.cc:2716
osl::checkmate::Dfpn::CallProofOracleDefense
Definition dfpn.cc:2731
osl::checkmate::Dfpn::DepthLimitReached
Definition dfpn.h:163
osl::checkmate::Dfpn::NodeBase
Definition dfpn.cc:337
osl::checkmate::Dfpn::Node
Definition dfpn.cc:350
osl::checkmate::Dfpn::ProofOracle
Definition dfpn.h:213
osl::checkmate::Dfpn::ProofOracle::key
HashKey key
Definition dfpn.h:214
osl::checkmate::Dfpn::ProofOracle::ProofOracle
ProofOracle(const HashKey &k, PieceStand w)
Definition dfpn.h:216
osl::checkmate::Dfpn::ProofOracle::newOracle
const ProofOracle newOracle(Player P, Move move) const
Definition dfpn.h:219
osl::checkmate::Dfpn::ProofOracle::traceable
bool traceable(Player P, Move move) const
Definition dfpn.h:225
osl::checkmate::Dfpn::ProofOracle::white_stand
PieceStand white_stand
Definition dfpn.h:215
osl::checkmate::Dfpn::Tree
Definition dfpn.cc:472