00001
00002
00003 #include "osl/checkmate/proofTreeDepthDfpn.h"
00004 #include "osl/checkmate/dfpn.h"
00005 #include "osl/checkmate/dfpnRecord.h"
00006 #include "osl/checkmate/fixedDepthSearcher.h"
00007 #include "osl/checkmate/fixedDepthSearcher.tcc"
00008 #include <unordered_map>
00009 #include <forward_list>
00014 struct osl::checkmate::ProofTreeDepthDfpn::Table
00015 {
00016 boost::scoped_array<NumEffectState> state;
00017 typedef std::unordered_map<HashKey, std::pair<int, Move>, std::hash<HashKey>> map_t;
00018 typedef std::pair<const HashKey, std::pair<int, Move>> entry_t;
00019 typedef std::forward_list<const entry_t*> list_t;
00020 typedef std::unordered_map<BoardKey, list_t, std::hash<BoardKey>> index_t;
00021 map_t depth_table;
00022 index_t depth_index;
00023 const DfpnTable& table;
00024 Table(const DfpnTable& t) : state(new NumEffectState[t.maxDepth()]), table(t)
00025 {
00026 }
00027 void store(const HashKey& key, int depth, Move best_move=Move())
00028 {
00029 depth_table[key] = std::make_pair(depth, best_move);
00030 const entry_t& e = *depth_table.find(key);
00031 depth_index[key.boardKey()].push_front(&e);
00032 }
00033 bool find(const HashKey& key, int& depth, Move& best_move) const
00034 {
00035 map_t::const_iterator p=depth_table.find(key);
00036 if (p == depth_table.end())
00037 return false;
00038 depth = p->second.first;
00039 best_move = p->second.second;
00040 return true;
00041 }
00042 bool expectMoreDepth(Player attack, const HashKey& key, int depth) const
00043 {
00044 index_t::const_iterator p=depth_index.find(key.boardKey());
00045 if (p == depth_index.end())
00046 return true;
00047 for (const entry_t *q: p->second) {
00048 assert(q->first.boardKey() == key.boardKey());
00049 if (attack == BLACK) {
00050 if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
00051 if (q->second.first >= depth)
00052 return true;
00053 } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
00054 if (q->second.first < depth)
00055 return false;
00056 }
00057 }
00058 else {
00059 if (q->first.blackStand().isSuperiorOrEqualTo(key.blackStand())) {
00060 if (q->second.first < depth)
00061 return false;
00062 } else if (key.blackStand().isSuperiorOrEqualTo(q->first.blackStand())) {
00063 if (q->second.first >= depth)
00064 return true;
00065 }
00066 }
00067 }
00068 return true;
00069 }
00070 int maxDepth() const { return table.maxDepth(); }
00071 };
00072
00073 osl::checkmate::
00074 ProofTreeDepthDfpn::ProofTreeDepthDfpn(const DfpnTable& dfpn_table)
00075 : table(new Table(dfpn_table))
00076 {
00077 }
00078
00079 osl::checkmate::
00080 ProofTreeDepthDfpn::~ProofTreeDepthDfpn()
00081 {
00082 }
00083
00084 int osl::checkmate::
00085 ProofTreeDepthDfpn::depth(const HashKey& key, const NumEffectState& state, bool is_or_node) const
00086 {
00087 Move dummy;
00088 table->state[0] = state;
00089 return (is_or_node ? orNode(key, dummy) : andNode(key, dummy));
00090 }
00091
00092 void osl::checkmate::
00093 ProofTreeDepthDfpn::retrievePV
00094 (const NumEffectState& src, bool is_or_node,
00095 std::vector<Move>& pv) const
00096 {
00097 table->state[0] = src;
00098 HashKey key(table->state[0]);
00099 pv.clear();
00100 for (int i=0; i<table->maxDepth(); ++i) {
00101 Move next;
00102 if (is_or_node ^ (i%2))
00103 orNode(key, next);
00104 else
00105 andNode(key, next);
00106 if (! next.isNormal())
00107 return;
00108 pv.push_back(next);
00109 table->state[0].makeMove(next);
00110 key = key.newMakeMove(next);
00111 }
00112 }
00113
00114 int osl::checkmate::
00115 ProofTreeDepthDfpn::orNode(const HashKey& key, Move& best_move, int height) const
00116 {
00117 assert(key == HashKey(table->state[height]));
00118 best_move = Move();
00119 if (height >= table->maxDepth())
00120 return -1;
00121
00122
00123 FixedDepthSearcher fixed_searcher(table->state[height]);
00124 ProofDisproof pdp = fixed_searcher.hasCheckmateMoveOfTurn(0, best_move);
00125 if (pdp.isCheckmateSuccess()) {
00126 table->store(key, 1, best_move);
00127 return 1;
00128 }
00129 pdp = fixed_searcher.hasCheckmateMoveOfTurn(2, best_move);
00130 if (pdp.isCheckmateSuccess()) {
00131 table->store(key, 3, best_move);
00132 return 3;
00133 }
00134
00135 const PieceStand white_stand = PieceStand(WHITE, table->state[height]);
00136 DfpnRecord record = table->table.probe(key, white_stand);
00137 if (! record.proof_disproof.isCheckmateSuccess()) {
00138 table->store(key, 5, Move());
00139 return 5;
00140 }
00141 {
00142 int recorded;
00143 if (table->find(key, recorded, best_move))
00144 return recorded;
00145 }
00146 table->store(key, -1, Move());
00147
00148 if (! record.best_move.isNormal())
00149 {
00150
00151 table->store(key, 1, Move());
00152 }
00153
00154 const HashKey new_key = key.newHashWithMove(record.best_move);
00155 const PieceStand next_white_stand = (table->state[height].turn() == WHITE)
00156 ? white_stand.nextStand(WHITE, record.best_move) : white_stand;
00157 DfpnRecord new_record = table->table.probe(new_key, next_white_stand);
00158 if (! new_record.proof_disproof.isCheckmateSuccess())
00159 new_record = table->table.findProofOracle(new_key, next_white_stand, record.best_move);
00160 if (new_record.proof_disproof.isCheckmateSuccess()) {
00161 table->state[height+1] = table->state[height];
00162 table->state[height+1].makeMove(record.best_move);
00163 Move dummy;
00164 const int depth = andNode(new_key, dummy, height+1);
00165 if (depth >= 0)
00166 {
00167 best_move = record.best_move;
00168 table->store(key, depth+1, best_move);
00169 return depth+1;
00170 }
00171 }
00172 return 0;
00173 }
00174
00175 int osl::checkmate::
00176 ProofTreeDepthDfpn::andNode(const HashKey& key, Move& best_move, int height) const
00177 {
00178 best_move = Move();
00179 if (height >= table->maxDepth())
00180 return -1;
00181 {
00182 int recorded;
00183 if (table->find(key, recorded, best_move))
00184 return recorded;
00185 }
00186 table->store(key, -1, Move());
00187
00188 int result = 0;
00189 std::unique_ptr<Dfpn::DfpnMoveVector> moves(new Dfpn::DfpnMoveVector);
00190 if (table->state[height].turn() == BLACK)
00191 Dfpn::generateEscape<WHITE>(table->state[height], true, Square(), *moves);
00192 else
00193 Dfpn::generateEscape<BLACK>(table->state[height], true, Square(), *moves);
00194
00195 for (size_t i=0; i<moves->size(); ++i)
00196 {
00197 const HashKey new_key = key.newHashWithMove((*moves)[i]);
00198 if (i > 0 && ! table->expectMoreDepth(alt((*moves)[i].player()), new_key, result))
00199 continue;
00200 table->state[height+1] = table->state[height];
00201 table->state[height+1].makeMove((*moves)[i]);
00202 Move dummy;
00203 const int depth = orNode(new_key, dummy, height+1);
00204 if (depth < 0) {
00205 return depth;
00206 }
00207 if (result < depth+1) {
00208 result = depth+1;
00209 best_move = (*moves)[i];
00210 }
00211 }
00212
00213 table->store(key, result, best_move);
00214 return result;
00215 }
00216
00217
00218
00219
00220
00221