My Project
dfpn.h
Go to the documentation of this file.
1/* dfpn.h
2 */
3#ifndef OSL_DFPN_H
4#define OSL_DFPN_H
7#include "osl/hashKey.h"
8#include "osl/pathEncoding.h"
9#include "osl/config.h"
10#include <boost/scoped_array.hpp>
11
12#ifdef OSL_SMP
13# ifndef OSL_DFPN_SMP
14# define OSL_DFPN_SMP
15# endif
16#endif
17
18#ifdef OSL_DFPN_SMP
19# include "osl/misc/lightMutex.h"
20# include <mutex>
21#endif
22
23namespace osl
24{
25 namespace checkmate
26 {
27 class DfpnRecord;
30 {
31 struct Table;
32 struct List;
33 boost::scoped_array<Table> table;
34 size_t total_size;
37 public:
39 DfpnTable();
40 ~DfpnTable();
41 template <Player Attack>
42 const DfpnRecord probe(const HashKey& key, PieceStand white) const;
43 const DfpnRecord probe(const HashKey& key, PieceStand white) const;
44 size_t estimateNodeCount(const HashKey& key, bool dominance_max=false) const;
45 template <Player Attack>
46 const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
47 const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
48 template <Player Attack>
49 void showProofOracles(const HashKey& key, PieceStand white, Move last_move=Move()) const;
50 size_t
51#ifdef __GNUC__
52 __attribute__ ((pure))
53#endif
54 size() const;
55 void showStats() const;
56
57 void setAttack(Player);
58 void setWorking(const HashKey& key, const DfpnRecord& value, int thread_id);
59 void leaveWorking(const HashKey& key, int thread_id);
60 void store(const HashKey& key, DfpnRecord& value, int leaving_thread_id=-1);
61 void addDag(const HashKey& key, DfpnRecord& value);
62 void clear();
63 size_t totalSize() { return total_size; }
64 Player attack() const;
65
66 void setMaxDepth(int);
67 int maxDepth() const;
68
69 void testTable();
70 size_t smallTreeGC(size_t threshold=10);
72 void setGrowthLimit(size_t new_limit);
73 size_t growthLimit() const { return growth_limit; }
74 bool runGC();
75 private:
76#ifdef OSL_DFPN_SMP
77 typedef osl::misc::LightMutex Mutex;
78# ifdef USE_TBB_HASH
79 static const int DIVSIZE=1;
80# else
81 static const int DIVSIZE=256;
82 mutable CArray<Mutex,DIVSIZE> mutex;
83# endif
84 // typedef boost::mutex Mutex;
85 // TODO: boost::thread::shared_lock (available version >= 1.35) for multi read accessess
86 LightMutex root_mutex;
87#else
88 static const int DIVSIZE=1;
89#endif
90 static int keyToIndex(const HashKey& key)
91 {
92 unsigned long val=key.signature();
93 return (val>>24)%DIVSIZE;
94 }
95 template <Player Attack>
96 List *find(const HashKey& key, int subindex);
97 template <Player Attack>
98 const List *find(const HashKey& key, int subindex) const;
99 const List *find(const HashKey& key, int subindex) const;
100 };
102 class DfpnPathTable;
104 class DfpnShared;
106 class Dfpn
107 {
108 Dfpn(const Dfpn&) = delete;
109 Dfpn& operator=(const Dfpn&) = delete;
110 public:
114 private:
116 struct NodeBase;
117 struct Node;
118 struct Tree;
119 std::unique_ptr<Tree> tree;
120 std::unique_ptr<DfpnPathTable> path_table;
126 public:
127 Dfpn();
128 ~Dfpn();
129 void setTable(DfpnTable *new_table);
130 void setIllegal(const HashKey& key, PieceStand white);
131 void setBlockingVerify(bool enable=true) { blocking_verify = enable; }
132 void setParallel(int id, DfpnShared *s)
133 {
134 if (s)
135 assert(id >= 0);
136 thread_id = id;
137 parallel_shared = s;
138 }
139 const ProofDisproof
140 hasCheckmateMove(const NumEffectState& state, const HashKey& key,
141 const PathEncoding& path, size_t limit, Move& best_move,
142 Move last_move=Move::INVALID(), std::vector<Move> *pv=0);
143 const ProofDisproof
144 hasCheckmateMove(const NumEffectState& state, const HashKey& key,
145 const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof,
146 Move last_move=Move::INVALID(), std::vector<Move> *pv=0);
147 const ProofDisproof
148 hasEscapeMove(const NumEffectState& state,
149 const HashKey& key, const PathEncoding& path,
150 size_t limit, Move last_move);
151
152 size_t nodeCount() const { return node_count; }
153 const DfpnTable& currentTable() const { return *table; }
154 void analyze(const PathEncoding& path,
155 const NumEffectState& state, const std::vector<Move>& moves) const;
156 void clear();
157
158 // private:
159 template <Player P> void attack();
160 template <Player P> void defense();
161 template <Player P> struct CallAttack;
162 template <Player P> struct CallDefense;
164
165 struct ProofOracle;
166 template <Player P, bool UseTable> void proofOracleAttack(const ProofOracle& oracle, int proof_limit);
167 template <Player P, bool UseTable> void proofOracleDefense(const ProofOracle& oracle, int proof_limit);
168 template <Player P, bool UseTable> struct CallProofOracleAttack;
169 template <Player P, bool UseTable> struct CallProofOracleDefense;
171 template <Player P> void blockingSimulation(int seed, const ProofOracle&);
172 template <Player P> void grandParentSimulation(int cur_move, const Node& gparent, int gp_move);
173 private:
174 template <bool UseTable>
175 const ProofDisproof
176 tryProofMain(const NumEffectState& state, const HashKey& key,
177 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
178 Move last_move);
179 public:
180 const ProofDisproof
181 tryProof(const NumEffectState& state, const HashKey& key,
182 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
183 Move last_move=Move::INVALID());
184 const ProofDisproof
185 tryProofLight(const NumEffectState& state, const HashKey& key,
186 const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
187 Move last_move=Move::INVALID());
188
189 // debug
190 int distance(const HashKey&) const;
192 template <Player P>
193 static void generateCheck(const NumEffectState&, DfpnMoveVector&, bool&);
195 template <Player P>
196 static void generateEscape(const NumEffectState&, bool need_full_width,
197 Square grand_parent_delay_last_to, DfpnMoveVector&);
200 template <Player Turn>
201 static void sort(const NumEffectState&, DfpnMoveVector&);
202 private:
203 void findDagSource();
204 void findDagSource(const HashKey& terminal_key,
205 DfpnRecord& terminal_record,
206 PieceStand terminal_stand, int offset=0);
207 };
208
209 }
210}
211
213{
217 {
218 }
219 const ProofOracle newOracle(Player P, Move move) const
220 {
221 assert(P == move.player());
222 return ProofOracle(key.newHashWithMove(move),
223 (P == WHITE) ? white_stand.nextStand(P, move) : white_stand);
224 }
225 bool traceable(Player P, Move move) const
226 {
227 assert(P == move.player());
228 if (! move.isDrop())
229 return true;
230 if (P == BLACK) {
231 if (key.blackStand().get(move.ptype()) == 0)
232 return false;
233 }
234 else {
235 if (white_stand.get(move.ptype()) == 0)
236 return false;
237 }
238 return true;
239 }
240};
241
242#endif /* OSL_DFPN_H */
243// ;;; Local Variables:
244// ;;; mode:c++
245// ;;; c-basic-offset:2
246// ;;; End:
圧縮していない moveの表現 .
static const Move INVALID()
Ptype ptype() const
Player player() const
bool isDrop() const
利きを持つ局面
片方の手番の持駒の枚数を記録するクラス.
const PieceStand nextStand(Player pl, Move move) const
unsigned int get(Ptype type) const
詰探索局面表 – 並列でも共有する部分
Definition dfpn.h:30
size_t size() const
Definition dfpn.cc:1251
static const int DIVSIZE
Definition dfpn.h:88
size_t growthLimit() const
Definition dfpn.h:73
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition dfpn.cc:1074
static int keyToIndex(const HashKey &key)
Definition dfpn.h:90
List * find(const HashKey &key, int subindex)
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
int maxDepth() const
Definition dfpn.cc:936
const List * find(const HashKey &key, int subindex) const
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition dfpn.cc:1047
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition dfpn.cc:1061
Player attack() const
Definition dfpn.cc:950
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition dfpn.cc:1117
void addDag(const HashKey &key, DfpnRecord &value)
Definition dfpn.cc:1098
void showStats() const
Definition dfpn.cc:921
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition dfpn.cc:912
void leaveWorking(const HashKey &key, int thread_id)
Definition dfpn.cc:1140
const DfpnRecord probe(const HashKey &key, PieceStand white) const
boost::scoped_array< Table > table
Definition dfpn.h:33
void setAttack(Player)
Definition dfpn.cc:942
size_t smallTreeGC(size_t threshold=10)
Definition dfpn.cc:1191
詰探索
Definition dfpn.h:107
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
Definition dfpn.cc:1573
int distance(const HashKey &) const
Definition dfpn.cc:3131
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
Definition dfpn.cc:2105
CheckMoveVector DfpnMoveVector
Definition dfpn.h:112
Dfpn & operator=(const Dfpn &)=delete
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition dfpn.cc:2746
std::unique_ptr< Tree > tree
Definition dfpn.h:119
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition dfpn.cc:1469
DfpnTable table_t
Definition dfpn.h:113
static void sort(const NumEffectState &, DfpnMoveVector &)
Definition dfpn.cc:1555
size_t nodeCount() const
Definition dfpn.h:152
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
Definition dfpn.cc:2651
DfpnShared * parallel_shared
Definition dfpn.h:123
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
Definition dfpn.cc:3096
std::unique_ptr< DfpnPathTable > path_table
Definition dfpn.h:120
const ProofDisproof tryProofLight(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
Definition dfpn.cc:1401
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
Definition dfpn.cc:2162
size_t node_count
Definition dfpn.h:121
void setIllegal(const HashKey &key, PieceStand white)
Definition dfpn.cc:1311
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
Definition dfpn.cc:3046
const DfpnTable & currentTable() const
Definition dfpn.h:153
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
Definition dfpn.cc:2872
Dfpn(const Dfpn &)=delete
void setParallel(int id, DfpnShared *s)
Definition dfpn.h:132
const ProofDisproof tryProof(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move=Move::INVALID())
Definition dfpn.cc:1393
const ProofDisproof hasCheckmateMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move &best_move, Move last_move=Move::INVALID(), std::vector< Move > *pv=0)
Definition dfpn.cc:1329
const ProofDisproof tryProofMain(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move)
size_t node_count_limit
Definition dfpn.h:122
void setTable(DfpnTable *new_table)
Definition dfpn.cc:1296
void setBlockingVerify(bool enable=true)
Definition dfpn.h:131
DfpnTable * table
Definition dfpn.h:115
証明数(proof number)と反証数(disproof number).
uint64_t signature() const
Definition hashKey.h:57
const PieceStand blackStand() const
Definition hashKey.h:64
const HashKey newHashWithMove(Move move) const
Definition hashKey.cc:63
static const osl::CArray2d< int, 8, 16 > threshold
Player
Definition basic_type.h:8
@ WHITE
Definition basic_type.h:10
@ BLACK
Definition basic_type.h:9
const PtypeO PTYPEO_EDGE __attribute__((unused))
@ CheckOrEscapeMaxUniqMoves
Definition container.h:299
ProofOracle(const HashKey &k, PieceStand w)
Definition dfpn.h:216
const ProofOracle newOracle(Player P, Move move) const
Definition dfpn.h:219
bool traceable(Player P, Move move) const
Definition dfpn.h:225