11 #include <boost/foreach.hpp>
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;
31 depth_table[key] = std::make_pair(depth, best_move);
35 bool find(
const HashKey& key,
int& depth,
Move& best_move)
const
40 depth = p->second.first;
41 best_move = p->second.second;
46 index_t::const_iterator p=
depth_index.find(key.boardKey());
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)
55 }
else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
56 if (q->second.first < depth)
61 if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
62 if (q->second.first < depth)
64 }
else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
65 if (q->second.first >= depth)
77 : table(new
Table(dfpn_table))
90 table->state[0] = state;
91 return (is_or_node ? orNode(key, dummy) : andNode(key, dummy));
97 vector<Move>& pv)
const
99 table->state[0] = src;
100 HashKey key(table->state[0]);
102 for (
int i=0; i<table->maxDepth(); ++i) {
104 if (is_or_node ^ (i%2))
111 table->state[0].makeMove(next);
112 key = key.newMakeMove(next);
119 assert(key == HashKey(table->state[height]));
121 if (height >= table->maxDepth())
128 table->store(key, 1, best_move);
133 table->store(key, 3, best_move);
138 DfpnRecord record = table->table.probe(key, white_stand);
140 table->store(key, 5,
Move());
145 if (table->find(key, recorded, best_move))
148 table->store(key, -1,
Move());
153 table->store(key, 1,
Move());
156 const HashKey new_key = key.newHashWithMove(record.
best_move);
157 const PieceStand next_white_stand = (table->state[height].turn() ==
WHITE)
159 DfpnRecord new_record = table->table.probe(new_key, next_white_stand);
161 new_record = table->table.findProofOracle(new_key, next_white_stand, record.
best_move);
163 table->state[height+1] = table->state[height];
164 table->state[height+1].makeMove(record.
best_move);
166 const int depth = andNode(new_key, dummy, height+1);
170 table->store(key, depth+1, best_move);
181 if (height >= table->maxDepth())
185 if (table->find(key, recorded, best_move))
188 table->store(key, -1,
Move());
192 if (table->state[height].turn() ==
BLACK)
193 Dfpn::generateEscape<WHITE>(table->state[height],
true,
Square(), *
moves);
195 Dfpn::generateEscape<BLACK>(table->state[height],
true,
Square(), *
moves);
197 for (
size_t i=0; i<moves->size(); ++i)
199 const HashKey new_key = key.newHashWithMove((*moves)[i]);
200 if (i > 0 && ! table->expectMoreDepth(
alt((*moves)[i].player()), new_key, result))
202 table->state[height+1] = table->state[height];
203 table->state[height+1].makeMove((*moves)[i]);
205 const int depth = orNode(new_key, dummy, height+1);
209 if (result < depth+1) {
211 best_move = (*moves)[i];
215 table->store(key, result, best_move);