My Project
proofTreeDepthDfpn.cc
Go to the documentation of this file.
1 /* proofTreeDepthDfpn.cc
2  */
4 #include "osl/checkmate/dfpn.h"
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;
23  const DfpnTable& table;
24  Table(const DfpnTable& t) : state(new NumEffectState[t.maxDepth()]), table(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 
81 {
82 }
83 
85 ProofTreeDepthDfpn::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 
115 ProofTreeDepthDfpn::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 
176 ProofTreeDepthDfpn::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の表現 .
Definition: basic_type.h:1052
bool isNormal() const
INVALID でも PASS でもない.
Definition: basic_type.h:1088
利きを持つ局面
片方の手番の持駒の枚数を記録するクラス.
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
int maxDepth() const
Definition: dfpn.cc:936
List * find(const HashKey &key, int subindex)
boost::scoped_array< Table > table
Definition: dfpn.h:32
深さ固定で,その深さまで depth first searchで読む詰将棋.
const ProofDisproof hasCheckmateMoveOfTurn(int depth, Move &best_move)
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
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