00001
00002
00003 #ifndef OSL_DFPN_H
00004 #define OSL_DFPN_H
00005 #include "osl/checkmate/proofDisproof.h"
00006 #include "osl/numEffectState.h"
00007 #include "osl/hashKey.h"
00008 #include "osl/pathEncoding.h"
00009 #include "osl/config.h"
00010 #include <boost/scoped_array.hpp>
00011
00012 #ifdef OSL_SMP
00013 # ifndef OSL_DFPN_SMP
00014 # define OSL_DFPN_SMP
00015 # endif
00016 #endif
00017
00018 #ifdef OSL_DFPN_SMP
00019 # include "osl/misc/lightMutex.h"
00020 # include <mutex>
00021 #endif
00022
00023 namespace osl
00024 {
00025 namespace checkmate
00026 {
00027 class DfpnRecord;
00029 class DfpnTable
00030 {
00031 struct Table;
00032 struct List;
00033 boost::scoped_array<Table> table;
00034 size_t total_size;
00035 int dfpn_max_depth;
00036 size_t growth_limit, gc_threshold;
00037 public:
00038 DfpnTable(Player attack);
00039 DfpnTable();
00040 ~DfpnTable();
00041 template <Player Attack>
00042 const DfpnRecord probe(const HashKey& key, PieceStand white) const;
00043 const DfpnRecord probe(const HashKey& key, PieceStand white) const;
00044 size_t estimateNodeCount(const HashKey& key, bool dominance_max=false) const;
00045 template <Player Attack>
00046 const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
00047 const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
00048 template <Player Attack>
00049 void showProofOracles(const HashKey& key, PieceStand white, Move last_move=Move()) const;
00050 size_t
00051 #ifdef __GNUC__
00052 __attribute__ ((pure))
00053 #endif
00054 size() const;
00055 void showStats() const;
00056
00057 void setAttack(Player);
00058 void setWorking(const HashKey& key, const DfpnRecord& value, int thread_id);
00059 void leaveWorking(const HashKey& key, int thread_id);
00060 void store(const HashKey& key, DfpnRecord& value, int leaving_thread_id=-1);
00061 void addDag(const HashKey& key, DfpnRecord& value);
00062 void clear();
00063 size_t totalSize() { return total_size; }
00064 Player attack() const;
00065
00066 void setMaxDepth(int);
00067 int maxDepth() const;
00068
00069 void testTable();
00070 size_t smallTreeGC(size_t threshold=10);
00072 void setGrowthLimit(size_t new_limit);
00073 size_t growthLimit() const { return growth_limit; }
00074 bool runGC();
00075 private:
00076 #ifdef OSL_DFPN_SMP
00077 typedef osl::misc::LightMutex Mutex;
00078 # ifdef USE_TBB_HASH
00079 static const int DIVSIZE=1;
00080 # else
00081 static const int DIVSIZE=256;
00082 mutable CArray<Mutex,DIVSIZE> mutex;
00083 # endif
00084
00085
00086 LightMutex root_mutex;
00087 #else
00088 static const int DIVSIZE=1;
00089 #endif
00090 static int keyToIndex(const HashKey& key)
00091 {
00092 unsigned long val=key.signature();
00093 return (val>>24)%DIVSIZE;
00094 }
00095 template <Player Attack>
00096 List *find(const HashKey& key, int subindex);
00097 template <Player Attack>
00098 const List *find(const HashKey& key, int subindex) const;
00099 const List *find(const HashKey& key, int subindex) const;
00100 };
00102 class DfpnPathTable;
00104 class DfpnShared;
00106 class Dfpn
00107 {
00108 Dfpn(const Dfpn&) = delete;
00109 Dfpn& operator=(const Dfpn&) = delete;
00110 public:
00111 enum { DfpnMaxUniqMoves = CheckOrEscapeMaxUniqMoves };
00112 typedef CheckMoveVector DfpnMoveVector;
00113 typedef DfpnTable table_t;
00114 private:
00115 DfpnTable *table;
00116 struct NodeBase;
00117 struct Node;
00118 struct Tree;
00119 std::unique_ptr<Tree> tree;
00120 std::unique_ptr<DfpnPathTable> path_table;
00121 size_t node_count;
00122 size_t node_count_limit;
00123 DfpnShared *parallel_shared;
00124 int thread_id;
00125 bool blocking_verify;
00126 public:
00127 Dfpn();
00128 ~Dfpn();
00129 void setTable(DfpnTable *new_table);
00130 void setIllegal(const HashKey& key, PieceStand white);
00131 void setBlockingVerify(bool enable=true) { blocking_verify = enable; }
00132 void setParallel(int id, DfpnShared *s)
00133 {
00134 if (s)
00135 assert(id >= 0);
00136 thread_id = id;
00137 parallel_shared = s;
00138 }
00139 const ProofDisproof
00140 hasCheckmateMove(const NumEffectState& state, const HashKey& key,
00141 const PathEncoding& path, size_t limit, Move& best_move,
00142 Move last_move=Move::INVALID(), std::vector<Move> *pv=0);
00143 const ProofDisproof
00144 hasCheckmateMove(const NumEffectState& state, const HashKey& key,
00145 const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof,
00146 Move last_move=Move::INVALID(), std::vector<Move> *pv=0);
00147 const ProofDisproof
00148 hasEscapeMove(const NumEffectState& state,
00149 const HashKey& key, const PathEncoding& path,
00150 size_t limit, Move last_move);
00151
00152 size_t nodeCount() const { return node_count; }
00153 const DfpnTable& currentTable() const { return *table; }
00154 void analyze(const PathEncoding& path,
00155 const NumEffectState& state, const std::vector<Move>& moves) const;
00156 void clear();
00157
00158
00159 template <Player P> void attack();
00160 template <Player P> void defense();
00161 template <Player P> struct CallAttack;
00162 template <Player P> struct CallDefense;
00163 struct DepthLimitReached {};
00164
00165 struct ProofOracle;
00166 template <Player P, bool UseTable> void proofOracleAttack(const ProofOracle& oracle, int proof_limit);
00167 template <Player P, bool UseTable> void proofOracleDefense(const ProofOracle& oracle, int proof_limit);
00168 template <Player P, bool UseTable> struct CallProofOracleAttack;
00169 template <Player P, bool UseTable> struct CallProofOracleDefense;
00171 template <Player P> void blockingSimulation(int seed, const ProofOracle&);
00172 template <Player P> void grandParentSimulation(int cur_move, const Node& gparent, int gp_move);
00173 private:
00174 template <bool UseTable>
00175 const ProofDisproof
00176 tryProofMain(const NumEffectState& state, const HashKey& key,
00177 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
00178 Move last_move);
00179 public:
00180 const ProofDisproof
00181 tryProof(const NumEffectState& state, const HashKey& key,
00182 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
00183 Move last_move=Move::INVALID());
00184 const ProofDisproof
00185 tryProofLight(const NumEffectState& state, const HashKey& key,
00186 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
00187 Move last_move=Move::INVALID());
00188
00189
00190 int distance(const HashKey&) const;
00192 template <Player P>
00193 static void generateCheck(const NumEffectState&, DfpnMoveVector&, bool&);
00195 template <Player P>
00196 static void generateEscape(const NumEffectState&, bool need_full_width,
00197 Square grand_parent_delay_last_to, DfpnMoveVector&);
00199 bool grandParentSimulationSuitable() const;
00200 template <Player Turn>
00201 static void sort(const NumEffectState&, DfpnMoveVector&);
00202 private:
00203 void findDagSource();
00204 void findDagSource(const HashKey& terminal_key,
00205 DfpnRecord& terminal_record,
00206 PieceStand terminal_stand, int offset=0);
00207 };
00208
00209 }
00210 }
00211
00212 struct osl::checkmate::Dfpn::ProofOracle
00213 {
00214 HashKey key;
00215 PieceStand white_stand;
00216 ProofOracle(const HashKey& k, PieceStand w) : key(k), white_stand(w)
00217 {
00218 }
00219 const ProofOracle newOracle(Player P, Move move) const
00220 {
00221 assert(P == move.player());
00222 return ProofOracle(key.newHashWithMove(move),
00223 (P == WHITE) ? white_stand.nextStand(P, move) : white_stand);
00224 }
00225 bool traceable(Player P, Move move) const
00226 {
00227 assert(P == move.player());
00228 if (! move.isDrop())
00229 return true;
00230 if (P == BLACK) {
00231 if (key.blackStand().get(move.ptype()) == 0)
00232 return false;
00233 }
00234 else {
00235 if (white_stand.get(move.ptype()) == 0)
00236 return false;
00237 }
00238 return true;
00239 }
00240 };
00241
00242 #endif
00243
00244
00245
00246