8 #include <unordered_map> 9 #include <forward_list> 16 boost::scoped_array<NumEffectState>
state;
18 typedef std::pair<const HashKey, std::pair<int, Move>>
entry_t;
19 typedef std::forward_list<const entry_t*>
list_t;
20 typedef std::unordered_map<BoardKey, list_t, std::hash<BoardKey>>
index_t;
29 depth_table[key] = std::make_pair(depth, best_move);
30 const entry_t& e = *depth_table.find(key);
31 depth_index[key.
boardKey()].push_front(&e);
35 map_t::const_iterator p=depth_table.find(key);
36 if (p == depth_table.end())
38 depth = p->second.first;
39 best_move = p->second.second;
44 index_t::const_iterator p=depth_index.find(key.
boardKey());
45 if (p == depth_index.end())
47 for (
const entry_t *q: p->second) {
48 assert(q->first.boardKey() == key.
boardKey());
49 if (attack ==
BLACK) {
50 if (q->first.blackStand().isSuperiorOrEqualTo(key.
blackStand())) {
51 if (q->second.first >= depth)
54 if (q->second.first < depth)
59 if (q->first.blackStand().isSuperiorOrEqualTo(key.
blackStand())) {
60 if (q->second.first < depth)
63 if (q->second.first >= depth)
75 : table(new
Table(dfpn_table))
88 table->state[0] = state;
89 return (is_or_node ?
orNode(key, dummy) :
andNode(key, dummy));
95 std::vector<Move>& pv)
const 97 table->state[0] = src;
100 for (
int i=0; i<table->
maxDepth(); ++i) {
102 if (is_or_node ^ (i%2))
109 table->state[0].makeMove(next);
117 assert(key ==
HashKey(table->state[height]));
126 table->
store(key, 1, best_move);
131 table->
store(key, 3, best_move);
143 if (table->
find(key, recorded, best_move))
155 const PieceStand next_white_stand = (table->state[height].turn() ==
WHITE)
159 new_record = table->
table.findProofOracle(new_key, next_white_stand, record.
best_move);
161 table->state[height+1] = table->state[height];
162 table->state[height+1].makeMove(record.
best_move);
168 table->
store(key, depth+1, best_move);
183 if (table->
find(key, recorded, best_move))
190 if (table->state[height].turn() ==
BLACK)
191 Dfpn::generateEscape<WHITE>(table->state[height],
true,
Square(), *moves);
193 Dfpn::generateEscape<BLACK>(table->state[height],
true,
Square(), *moves);
195 for (
size_t i=0; i<moves->size(); ++i)
198 if (i > 0 && ! table->expectMoreDepth(
alt((*moves)[i].player()), new_key, result))
200 table->state[height+1] = table->state[height];
201 table->state[height+1].makeMove((*moves)[i]);
203 const int depth =
orNode(new_key, dummy, height+1);
207 if (result < depth+1) {
209 best_move = (*moves)[i];
213 table->
store(key, result, best_move);
int orNode(const HashKey &key, Move &best_move, int height=0) const
int depth(const HashKey &key, const NumEffectState &state, bool is_or_node) const
std::forward_list< const entry_t * > list_t
深さ固定で,その深さまで depth first searchで読む詰将棋.
bool isSuperiorOrEqualTo(PieceStand other) const
boost::scoped_array< NumEffectState > state
const HashKey newMakeMove(Move) const
constexpr Player alt(Player player)
const BoardKey96 boardKey() const
bool isNormal() const
INVALID でも PASS でもない.
List * find(const HashKey &key, int subindex)
Table(const DfpnTable &t)
const PieceStand nextStand(Player pl, Move move) const
const PieceStand blackStand() const
std::unordered_map< BoardKey, list_t, std::hash< BoardKey > > index_t
boost::scoped_array< Table > table
int andNode(const HashKey &key, Move &best_move, int height=0) const
const ProofDisproof hasCheckmateMoveOfTurn(int depth, Move &best_move)
bool expectMoreDepth(Player attack, const HashKey &key, int depth) const
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
std::unordered_map< HashKey, std::pair< int, Move >, std::hash< HashKey > > map_t
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
const HashKey newHashWithMove(Move move) const
証明数(proof number)と反証数(disproof number).
bool isCheckmateSuccess() const
ProofTreeDepthDfpn(const DfpnTable &table)
bool find(const HashKey &key, int &depth, Move &best_move) const
std::pair< const HashKey, std::pair< int, Move > > entry_t
ProofDisproof proof_disproof
void store(const HashKey &key, int depth, Move best_move=Move())