All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
proofTreeDepthDfpn.cc
Go to the documentation of this file.
1 /* proofTreeDepthDfpn.cc
2  */
4 #include "osl/checkmate/dfpn.h"
9 #include "osl/stl/hash_map.h"
10 #include "osl/stl/slist.h"
11 #include <boost/foreach.hpp>
17 {
18  boost::scoped_array<NumEffectState> state;
19  typedef osl::hash_map<HashKey, std::pair<int, Move> > map_t;
20  typedef std::pair<const HashKey, std::pair<int, Move> > entry_t;
21  typedef slist<const entry_t*> list_t;
22  typedef hash_map<BoardKey, list_t> index_t;
25  const DfpnTable& table;
26  Table(const DfpnTable& t) : state(new NumEffectState[t.maxDepth()]), table(t)
27  {
28  }
29  void store(const HashKey& key, int depth, Move best_move=Move())
30  {
31  depth_table[key] = std::make_pair(depth, best_move);
32  const entry_t& e = *depth_table.find(key);
33  depth_index[key.boardKey()].push_front(&e);
34  }
35  bool find(const HashKey& key, int& depth, Move& best_move) const
36  {
37  map_t::const_iterator p=depth_table.find(key);
38  if (p == depth_table.end())
39  return false;
40  depth = p->second.first;
41  best_move = p->second.second;
42  return true;
43  }
44  bool expectMoreDepth(Player attack, const HashKey& key, int depth) const
45  {
46  index_t::const_iterator p=depth_index.find(key.boardKey());
47  if (p == depth_index.end())
48  return true;
49  BOOST_FOREACH(const entry_t *q, p->second) {
50  assert(q->first.boardKey() == key.boardKey());
51  if (attack == BLACK) {
52  if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
53  if (q->second.first >= depth)
54  return true;
55  } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
56  if (q->second.first < depth)
57  return false;
58  }
59  }
60  else {
61  if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
62  if (q->second.first < depth)
63  return false;
64  } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
65  if (q->second.first >= depth)
66  return true;
67  }
68  }
69  }
70  return true;
71  }
72  int maxDepth() const { return table.maxDepth(); }
73 };
74 
77  : table(new Table(dfpn_table))
78 {
79 }
80 
83 {
84 }
85 
87 ProofTreeDepthDfpn::depth(const HashKey& key, const NumEffectState& state, bool is_or_node) const
88 {
89  Move dummy;
90  table->state[0] = state;
91  return (is_or_node ? orNode(key, dummy) : andNode(key, dummy));
92 }
93 
96 (const state::NumEffectState& src, bool is_or_node,
97  vector<Move>& pv) const
98 {
99  table->state[0] = src;
100  HashKey key(table->state[0]);
101  pv.clear();
102  for (int i=0; i<table->maxDepth(); ++i) {
103  Move next;
104  if (is_or_node ^ (i%2))
105  orNode(key, next);
106  else
107  andNode(key, next);
108  if (! next.isNormal())
109  return;
110  pv.push_back(next);
111  table->state[0].makeMove(next);
112  key = key.newMakeMove(next);
113  }
114 }
115 
117 ProofTreeDepthDfpn::orNode(const HashKey& key, Move& best_move, int height) const
118 {
119  assert(key == HashKey(table->state[height]));
120  best_move = Move();
121  if (height >= table->maxDepth())
122  return -1;
123 
124  // always test ImmediateCheckmate since users do not want to see redundant solutions
125  FixedDepthSearcher fixed_searcher(table->state[height]);
126  ProofDisproof pdp = fixed_searcher.hasCheckmateMoveOfTurn(0, best_move);
127  if (pdp.isCheckmateSuccess()) {
128  table->store(key, 1, best_move);
129  return 1;
130  }
131  pdp = fixed_searcher.hasCheckmateMoveOfTurn(2, best_move);
132  if (pdp.isCheckmateSuccess()) {
133  table->store(key, 3, best_move);
134  return 3;
135  }
136 
137  const PieceStand white_stand = PieceStand(WHITE, table->state[height]);
138  DfpnRecord record = table->table.probe(key, white_stand);
139  if (! record.proof_disproof.isCheckmateSuccess()) {
140  table->store(key, 5, Move()); // XXX
141  return 5;
142  }
143  {
144  int recorded;
145  if (table->find(key, recorded, best_move))
146  return recorded;
147  }
148  table->store(key, -1, Move());
149 
150  if (! record.best_move.isNormal())
151  {
152  // XXX // ImmediateCheckmate
153  table->store(key, 1, Move());
154  }
155 
156  const HashKey new_key = key.newHashWithMove(record.best_move);
157  const PieceStand next_white_stand = (table->state[height].turn() == WHITE)
158  ? white_stand.nextStand(WHITE, record.best_move) : white_stand;
159  DfpnRecord new_record = table->table.probe(new_key, next_white_stand);
160  if (! new_record.proof_disproof.isCheckmateSuccess())
161  new_record = table->table.findProofOracle(new_key, next_white_stand, record.best_move);
162  if (new_record.proof_disproof.isCheckmateSuccess()) {
163  table->state[height+1] = table->state[height];
164  table->state[height+1].makeMove(record.best_move);
165  Move dummy;
166  const int depth = andNode(new_key, dummy, height+1);
167  if (depth >= 0)
168  {
169  best_move = record.best_move;
170  table->store(key, depth+1, best_move);
171  return depth+1;
172  }
173  }
174  return 0;
175 }
176 
178 ProofTreeDepthDfpn::andNode(const HashKey& key, Move& best_move, int height) const
179 {
180  best_move = Move();
181  if (height >= table->maxDepth())
182  return -1;
183  {
184  int recorded;
185  if (table->find(key, recorded, best_move))
186  return recorded;
187  }
188  table->store(key, -1, Move());
189 
190  int result = 0; // and node で指手がなくて詰 => 逃げられない
191  boost::scoped_ptr<Dfpn::DfpnMoveVector> moves(new Dfpn::DfpnMoveVector);
192  if (table->state[height].turn() == BLACK)
193  Dfpn::generateEscape<WHITE>(table->state[height], true, Square(), *moves);
194  else
195  Dfpn::generateEscape<BLACK>(table->state[height], true, Square(), *moves);
196 
197  for (size_t i=0; i<moves->size(); ++i)
198  {
199  const HashKey new_key = key.newHashWithMove((*moves)[i]);
200  if (i > 0 && ! table->expectMoreDepth(alt((*moves)[i].player()), new_key, result))
201  continue;
202  table->state[height+1] = table->state[height];
203  table->state[height+1].makeMove((*moves)[i]);
204  Move dummy;
205  const int depth = orNode(new_key, dummy, height+1);
206  if (depth < 0) {
207  return depth; // loop found
208  }
209  if (result < depth+1) {
210  result = depth+1;
211  best_move = (*moves)[i];
212  }
213  }
214 
215  table->store(key, result, best_move);
216  return result;
217 }
218 
219 /* ------------------------------------------------------------------------- */
220 // ;;; Local Variables:
221 // ;;; mode:c++
222 // ;;; c-basic-offset:2
223 // ;;; End: