My Project
proofTreeDepthDfpn.cc
Go to the documentation of this file.
1/* proofTreeDepthDfpn.cc
2 */
8#include <unordered_map>
9#include <forward_list>
15{
16 boost::scoped_array<NumEffectState> state;
17 typedef std::unordered_map<HashKey, std::pair<int, Move>, std::hash<HashKey>> map_t;
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;
25 {
26 }
27 void store(const HashKey& key, int depth, Move best_move=Move())
28 {
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);
32 }
33 bool find(const HashKey& key, int& depth, Move& best_move) const
34 {
35 map_t::const_iterator p=depth_table.find(key);
36 if (p == depth_table.end())
37 return false;
38 depth = p->second.first;
39 best_move = p->second.second;
40 return true;
41 }
42 bool expectMoreDepth(Player attack, const HashKey& key, int depth) const
43 {
44 index_t::const_iterator p=depth_index.find(key.boardKey());
45 if (p == depth_index.end())
46 return true;
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)
52 return true;
53 } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
54 if (q->second.first < depth)
55 return false;
56 }
57 }
58 else {
59 if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
60 if (q->second.first < depth)
61 return false;
62 } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
63 if (q->second.first >= depth)
64 return true;
65 }
66 }
67 }
68 return true;
69 }
70 int maxDepth() const { return table.maxDepth(); }
71};
72
75 : table(new Table(dfpn_table))
76{
77}
78
83
85ProofTreeDepthDfpn::depth(const HashKey& key, const NumEffectState& state, bool is_or_node) const
86{
87 Move dummy;
88 table->state[0] = state;
89 return (is_or_node ? orNode(key, dummy) : andNode(key, dummy));
90}
91
94(const NumEffectState& src, bool is_or_node,
95 std::vector<Move>& pv) const
96{
97 table->state[0] = src;
98 HashKey key(table->state[0]);
99 pv.clear();
100 for (int i=0; i<table->maxDepth(); ++i) {
101 Move next;
102 if (is_or_node ^ (i%2))
103 orNode(key, next);
104 else
105 andNode(key, next);
106 if (! next.isNormal())
107 return;
108 pv.push_back(next);
109 table->state[0].makeMove(next);
110 key = key.newMakeMove(next);
111 }
112}
113
115ProofTreeDepthDfpn::orNode(const HashKey& key, Move& best_move, int height) const
116{
117 assert(key == HashKey(table->state[height]));
118 best_move = Move();
119 if (height >= table->maxDepth())
120 return -1;
121
122 // always test ImmediateCheckmate since users do not want to see redundant solutions
123 FixedDepthSearcher fixed_searcher(table->state[height]);
124 ProofDisproof pdp = fixed_searcher.hasCheckmateMoveOfTurn(0, best_move);
125 if (pdp.isCheckmateSuccess()) {
126 table->store(key, 1, best_move);
127 return 1;
128 }
129 pdp = fixed_searcher.hasCheckmateMoveOfTurn(2, best_move);
130 if (pdp.isCheckmateSuccess()) {
131 table->store(key, 3, best_move);
132 return 3;
133 }
134
135 const PieceStand white_stand = PieceStand(WHITE, table->state[height]);
136 DfpnRecord record = table->table.probe(key, white_stand);
137 if (! record.proof_disproof.isCheckmateSuccess()) {
138 table->store(key, 5, Move()); // XXX
139 return 5;
140 }
141 {
142 int recorded;
143 if (table->find(key, recorded, best_move))
144 return recorded;
145 }
146 table->store(key, -1, Move());
147
148 if (! record.best_move.isNormal())
149 {
150 // XXX // ImmediateCheckmate
151 table->store(key, 1, Move());
152 }
153
154 const HashKey new_key = key.newHashWithMove(record.best_move);
155 const PieceStand next_white_stand = (table->state[height].turn() == WHITE)
156 ? white_stand.nextStand(WHITE, record.best_move) : white_stand;
157 DfpnRecord new_record = table->table.probe(new_key, next_white_stand);
158 if (! new_record.proof_disproof.isCheckmateSuccess())
159 new_record = table->table.findProofOracle(new_key, next_white_stand, record.best_move);
160 if (new_record.proof_disproof.isCheckmateSuccess()) {
161 table->state[height+1] = table->state[height];
162 table->state[height+1].makeMove(record.best_move);
163 Move dummy;
164 const int depth = andNode(new_key, dummy, height+1);
165 if (depth >= 0)
166 {
167 best_move = record.best_move;
168 table->store(key, depth+1, best_move);
169 return depth+1;
170 }
171 }
172 return 0;
173}
174
176ProofTreeDepthDfpn::andNode(const HashKey& key, Move& best_move, int height) const
177{
178 best_move = Move();
179 if (height >= table->maxDepth())
180 return -1;
181 {
182 int recorded;
183 if (table->find(key, recorded, best_move))
184 return recorded;
185 }
186 table->store(key, -1, Move());
187
188 int result = 0; // and node で指手がなくて詰 => 逃げられない
189 std::unique_ptr<Dfpn::DfpnMoveVector> moves(new Dfpn::DfpnMoveVector);
190 if (table->state[height].turn() == BLACK)
191 Dfpn::generateEscape<WHITE>(table->state[height], true, Square(), *moves);
192 else
193 Dfpn::generateEscape<BLACK>(table->state[height], true, Square(), *moves);
194
195 for (size_t i=0; i<moves->size(); ++i)
196 {
197 const HashKey new_key = key.newHashWithMove((*moves)[i]);
198 if (i > 0 && ! table->expectMoreDepth(alt((*moves)[i].player()), new_key, result))
199 continue;
200 table->state[height+1] = table->state[height];
201 table->state[height+1].makeMove((*moves)[i]);
202 Move dummy;
203 const int depth = orNode(new_key, dummy, height+1);
204 if (depth < 0) {
205 return depth; // loop found
206 }
207 if (result < depth+1) {
208 result = depth+1;
209 best_move = (*moves)[i];
210 }
211 }
212
213 table->store(key, result, best_move);
214 return result;
215}
216
217/* ------------------------------------------------------------------------- */
218// ;;; Local Variables:
219// ;;; mode:c++
220// ;;; c-basic-offset:2
221// ;;; End:
圧縮していない moveの表現 .
bool isNormal() const
INVALID でも PASS でもない.
利きを持つ局面
片方の手番の持駒の枚数を記録するクラス.
const PieceStand nextStand(Player pl, Move move) const
bool isSuperiorOrEqualTo(PieceStand other) const
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition dfpn.cc:1074
List * find(const HashKey &key, int subindex)
int maxDepth() const
Definition dfpn.cc:936
boost::scoped_array< Table > table
Definition dfpn.h:33
深さ固定で,その深さまで depth first searchで読む詰将棋.
const ProofDisproof hasCheckmateMoveOfTurn(int depth, Move &best_move)
証明数(proof number)と反証数(disproof number).
int depth(const HashKey &key, const NumEffectState &state, bool is_or_node) const
ProofTreeDepthDfpn(const DfpnTable &table)
void retrievePV(const NumEffectState &state, bool is_or_node, std::vector< Move > &pv) const
int orNode(const HashKey &key, Move &best_move, int height=0) const
int andNode(const HashKey &key, Move &best_move, int height=0) const
const PieceStand blackStand() const
Definition hashKey.h:64
const BoardKey96 boardKey() const
Definition hashKey.h:53
const HashKey newMakeMove(Move) const
Definition hashKey.cc:69
const HashKey newHashWithMove(Move move) const
Definition hashKey.cc:63
Player
Definition basic_type.h:8
@ WHITE
Definition basic_type.h:10
@ BLACK
Definition basic_type.h:9
constexpr Player alt(Player player)
Definition basic_type.h:13
深さを記憶するテーブル.
bool find(const HashKey &key, int &depth, Move &best_move) const
std::pair< const HashKey, std::pair< int, Move > > entry_t
std::forward_list< const entry_t * > list_t
std::unordered_map< HashKey, std::pair< int, Move >, std::hash< HashKey > > map_t
std::unordered_map< BoardKey, list_t, std::hash< BoardKey > > index_t
void store(const HashKey &key, int depth, Move best_move=Move())
boost::scoped_array< NumEffectState > state
bool expectMoreDepth(Player attack, const HashKey &key, int depth) const