proofTreeDepthDfpn.cc
Go to the documentation of this file.
/* proofTreeDepthDfpn.cc
*/
#include "osl/checkmate/proofTreeDepthDfpn.h"
#include "osl/checkmate/dfpn.h"
#include "osl/checkmate/dfpnRecord.h"
#include "osl/checkmate/fixedDepthSearcher.h"
#include "osl/checkmate/fixedDepthSearcher.tcc"
#include <unordered_map>
#include <forward_list>
struct osl::checkmate::ProofTreeDepthDfpn::Table
{
boost::scoped_array<NumEffectState> state;
typedef std::unordered_map<HashKey, std::pair<int, Move>, std::hash<HashKey>> map_t;
typedef std::pair<const HashKey, std::pair<int, Move>> entry_t;
typedef std::forward_list<const entry_t*> list_t;
typedef std::unordered_map<BoardKey, list_t, std::hash<BoardKey>> index_t;
map_t depth_table;
index_t depth_index;
const DfpnTable& table;
Table(const DfpnTable& t) : state(new NumEffectState[t.maxDepth()]), table(t)
{
}
void store(const HashKey& key, int depth, Move best_move=Move())
{
depth_table[key] = std::make_pair(depth, best_move);
const entry_t& e = *depth_table.find(key);
depth_index[key.boardKey()].push_front(&e);
}
bool find(const HashKey& key, int& depth, Move& best_move) const
{
map_t::const_iterator p=depth_table.find(key);
if (p == depth_table.end())
return false;
depth = p->second.first;
best_move = p->second.second;
return true;
}
bool expectMoreDepth(Player attack, const HashKey& key, int depth) const
{
index_t::const_iterator p=depth_index.find(key.boardKey());
if (p == depth_index.end())
return true;
for (const entry_t *q: p->second) {
assert(q->first.boardKey() == key.boardKey());
if (attack == BLACK) {
if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
if (q->second.first >= depth)
return true;
} else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
if (q->second.first < depth)
return false;
}
}
else {
if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
if (q->second.first < depth)
return false;
} else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
if (q->second.first >= depth)
return true;
}
}
}
return true;
}
int maxDepth() const { return table.maxDepth(); }
};
osl::checkmate::
ProofTreeDepthDfpn::ProofTreeDepthDfpn(const DfpnTable& dfpn_table)
: table(new Table(dfpn_table))
{
}
osl::checkmate::
ProofTreeDepthDfpn::~ProofTreeDepthDfpn()
{
}
int osl::checkmate::
ProofTreeDepthDfpn::depth(const HashKey& key, const NumEffectState& state, bool is_or_node) const
{
Move dummy;
table->state[0] = state;
return (is_or_node ? orNode(key, dummy) : andNode(key, dummy));
}
void osl::checkmate::
ProofTreeDepthDfpn::retrievePV
(const NumEffectState& src, bool is_or_node,
std::vector<Move>& pv) const
{
table->state[0] = src;
HashKey key(table->state[0]);
pv.clear();
for (int i=0; i<table->maxDepth(); ++i) {
Move next;
if (is_or_node ^ (i%2))
orNode(key, next);
else
andNode(key, next);
if (! next.isNormal())
return;
pv.push_back(next);
table->state[0].makeMove(next);
key = key.newMakeMove(next);
}
}
int osl::checkmate::
ProofTreeDepthDfpn::orNode(const HashKey& key, Move& best_move, int height) const
{
assert(key == HashKey(table->state[height]));
best_move = Move();
if (height >= table->maxDepth())
return -1;
// always test ImmediateCheckmate since users do not want to see redundant solutions
FixedDepthSearcher fixed_searcher(table->state[height]);
ProofDisproof pdp = fixed_searcher.hasCheckmateMoveOfTurn(0, best_move);
if (pdp.isCheckmateSuccess()) {
table->store(key, 1, best_move);
return 1;
}
pdp = fixed_searcher.hasCheckmateMoveOfTurn(2, best_move);
if (pdp.isCheckmateSuccess()) {
table->store(key, 3, best_move);
return 3;
}
const PieceStand white_stand = PieceStand(WHITE, table->state[height]);
DfpnRecord record = table->table.probe(key, white_stand);
if (! record.proof_disproof.isCheckmateSuccess()) {
table->store(key, 5, Move()); // XXX
return 5;
}
{
int recorded;
if (table->find(key, recorded, best_move))
return recorded;
}
table->store(key, -1, Move());
if (! record.best_move.isNormal())
{
// XXX // ImmediateCheckmate
table->store(key, 1, Move());
}
const HashKey new_key = key.newHashWithMove(record.best_move);
const PieceStand next_white_stand = (table->state[height].turn() == WHITE)
? white_stand.nextStand(WHITE, record.best_move) : white_stand;
DfpnRecord new_record = table->table.probe(new_key, next_white_stand);
if (! new_record.proof_disproof.isCheckmateSuccess())
new_record = table->table.findProofOracle(new_key, next_white_stand, record.best_move);
if (new_record.proof_disproof.isCheckmateSuccess()) {
table->state[height+1] = table->state[height];
table->state[height+1].makeMove(record.best_move);
Move dummy;
const int depth = andNode(new_key, dummy, height+1);
if (depth >= 0)
{
best_move = record.best_move;
table->store(key, depth+1, best_move);
return depth+1;
}
}
return 0;
}
int osl::checkmate::
ProofTreeDepthDfpn::andNode(const HashKey& key, Move& best_move, int height) const
{
best_move = Move();
if (height >= table->maxDepth())
return -1;
{
int recorded;
if (table->find(key, recorded, best_move))
return recorded;
}
table->store(key, -1, Move());
int result = 0; // and node で指手がなくて詰 => 逃げられない
std::unique_ptr<Dfpn::DfpnMoveVector> moves(new Dfpn::DfpnMoveVector);
if (table->state[height].turn() == BLACK)
Dfpn::generateEscape<WHITE>(table->state[height], true, Square(), *moves);
else
Dfpn::generateEscape<BLACK>(table->state[height], true, Square(), *moves);
for (size_t i=0; i<moves->size(); ++i)
{
const HashKey new_key = key.newHashWithMove((*moves)[i]);
if (i > 0 && ! table->expectMoreDepth(alt((*moves)[i].player()), new_key, result))
continue;
table->state[height+1] = table->state[height];
table->state[height+1].makeMove((*moves)[i]);
Move dummy;
const int depth = orNode(new_key, dummy, height+1);
if (depth < 0) {
return depth; // loop found
}
if (result < depth+1) {
result = depth+1;
best_move = (*moves)[i];
}
}
table->store(key, result, best_move);
return result;
}
/* ------------------------------------------------------------------------- */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
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::PieceStand
片方の手番の持駒の枚数を記録するクラス.
Definition bits/pieceStand.h:38
osl::PieceStand::nextStand
const PieceStand nextStand(Player pl, Move move) const
Definition bits/pieceStand.h:203
osl::PieceStand::isSuperiorOrEqualTo
bool isSuperiorOrEqualTo(PieceStand other) const
Definition bits/pieceStand.h:138
osl::Square
Definition basic_type.h:532
osl::checkmate::DfpnRecord
Definition dfpnRecord.h:58
osl::checkmate::DfpnTable
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
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::FixedDepthSearcher
深さ固定で，その深さまで depth first searchで読む詰将棋.
Definition fixedDepthSearcher.h:41
osl::checkmate::FixedDepthSearcher::hasCheckmateMoveOfTurn
const ProofDisproof hasCheckmateMoveOfTurn(int depth, Move &best_move)
Definition fixedDepthSearcher.cc:10
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition proofDisproof.h:17
osl::checkmate::ProofDisproof::isCheckmateSuccess
bool isCheckmateSuccess() const
Definition proofDisproof.h:86
osl::checkmate::ProofTreeDepthDfpn::table
std::unique_ptr< Table > table
Definition proofTreeDepthDfpn.h:24
osl::checkmate::ProofTreeDepthDfpn::depth
int depth(const HashKey &key, const NumEffectState &state, bool is_or_node) const
Definition proofTreeDepthDfpn.cc:85
osl::checkmate::ProofTreeDepthDfpn::ProofTreeDepthDfpn
ProofTreeDepthDfpn(const DfpnTable &table)
Definition proofTreeDepthDfpn.cc:74
osl::checkmate::ProofTreeDepthDfpn::~ProofTreeDepthDfpn
~ProofTreeDepthDfpn()
Definition proofTreeDepthDfpn.cc:80
osl::checkmate::ProofTreeDepthDfpn::retrievePV
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
Definition proofTreeDepthDfpn.cc:94
osl::checkmate::ProofTreeDepthDfpn::orNode
int orNode(const HashKey &key, Move &best_move, int height=0) const
Definition proofTreeDepthDfpn.cc:115
osl::checkmate::ProofTreeDepthDfpn::andNode
int andNode(const HashKey &key, Move &best_move, int height=0) const
Definition proofTreeDepthDfpn.cc:176
osl::hash::HashKey128::blackStand
const PieceStand blackStand() const
Definition hashKey.h:64
osl::hash::HashKey128::boardKey
const BoardKey96 boardKey() const
Definition hashKey.h:53
osl::hash::HashKey
Definition hashKey.h:153
osl::hash::HashKey::newMakeMove
const HashKey newMakeMove(Move) const
Definition hashKey.cc:69
osl::hash::HashKey::newHashWithMove
const HashKey newHashWithMove(Move move) const
Definition hashKey.cc:63
dfpnRecord.h
dfpn.h
fixedDepthSearcher.h
fixedDepthSearcher.tcc
osl::record
棋譜関係
Definition checkDuplicate.h:15
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
proofTreeDepthDfpn.h
osl::checkmate::DfpnRecordBase::proof_disproof
ProofDisproof proof_disproof
Definition dfpnRecord.h:17
osl::checkmate::ProofTreeDepthDfpn::Table
深さを記憶するテーブル.
Definition proofTreeDepthDfpn.cc:15
osl::checkmate::ProofTreeDepthDfpn::Table::depth_table
map_t depth_table
Definition proofTreeDepthDfpn.cc:21
osl::checkmate::ProofTreeDepthDfpn::Table::find
bool find(const HashKey &key, int &depth, Move &best_move) const
Definition proofTreeDepthDfpn.cc:33
osl::checkmate::ProofTreeDepthDfpn::Table::entry_t
std::pair< const HashKey, std::pair< int, Move > > entry_t
Definition proofTreeDepthDfpn.cc:18
osl::checkmate::ProofTreeDepthDfpn::Table::list_t
std::forward_list< const entry_t * > list_t
Definition proofTreeDepthDfpn.cc:19
osl::checkmate::ProofTreeDepthDfpn::Table::Table
Table(const DfpnTable &t)
Definition proofTreeDepthDfpn.cc:24
osl::checkmate::ProofTreeDepthDfpn::Table::table
const DfpnTable & table
Definition proofTreeDepthDfpn.cc:23
osl::checkmate::ProofTreeDepthDfpn::Table::map_t
std::unordered_map< HashKey, std::pair< int, Move >, std::hash< HashKey > > map_t
Definition proofTreeDepthDfpn.cc:17
osl::checkmate::ProofTreeDepthDfpn::Table::depth_index
index_t depth_index
Definition proofTreeDepthDfpn.cc:22
osl::checkmate::ProofTreeDepthDfpn::Table::index_t
std::unordered_map< BoardKey, list_t, std::hash< BoardKey > > index_t
Definition proofTreeDepthDfpn.cc:20
osl::checkmate::ProofTreeDepthDfpn::Table::store
void store(const HashKey &key, int depth, Move best_move=Move())
Definition proofTreeDepthDfpn.cc:27
osl::checkmate::ProofTreeDepthDfpn::Table::state
boost::scoped_array< NumEffectState > state
Definition proofTreeDepthDfpn.cc:16
osl::checkmate::ProofTreeDepthDfpn::Table::expectMoreDepth
bool expectMoreDepth(Player attack, const HashKey &key, int depth) const
Definition proofTreeDepthDfpn.cc:42
osl::checkmate::ProofTreeDepthDfpn::Table::maxDepth
int maxDepth() const
Definition proofTreeDepthDfpn.cc:70
std::hash
Definition basic_type.h:1354