dfpn.h
Go to the documentation of this file.
1 /* dfpn.h
2  */
3 #ifndef OSL_DFPN_H
4 #define OSL_DFPN_H
6 #include "osl/numEffectState.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 
23 namespace osl
24 {
25  namespace checkmate
26  {
27  class DfpnRecord;
29  class DfpnTable
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:
111  enum { DfpnMaxUniqMoves = CheckOrEscapeMaxUniqMoves };
114  private:
116  struct NodeBase;
117  struct Node;
118  struct Tree;
119  std::unique_ptr<Tree> tree;
120  std::unique_ptr<DfpnPathTable> path_table;
121  size_t node_count;
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;
163  struct DepthLimitReached {};
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&);
199  bool grandParentSimulationSuitable() const;
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 {
216  ProofOracle(const HashKey& k, PieceStand w) : key(k), white_stand(w)
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:
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
const PtypeO PTYPEO_EDGE __attribute__((unused))
const ProofOracle newOracle(Player P, Move move) const
Definition: dfpn.h:219
void setParallel(int id, DfpnShared *s)
Definition: dfpn.h:132
size_t totalSize()
Definition: dfpn.h:63
bool traceable(Player P, Move move) const
Definition: dfpn.h:225
size_t growthLimit() const
Definition: dfpn.h:73
List * find(const HashKey &key, int subindex)
size_t node_count_limit
Definition: dfpn.h:122
unsigned int get(Ptype type) const
const PieceStand nextStand(Player pl, Move move) const
const PieceStand blackStand() const
Definition: hashKey.h:64
void setAttack(Player)
Definition: dfpn.cc:942
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:29
static const int DIVSIZE
Definition: dfpn.h:88
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition: dfpn.cc:1061
size_t nodeCount() const
Definition: dfpn.h:152
Ptype ptype() const
Definition: basic_type.h:1155
boost::scoped_array< Table > table
Definition: dfpn.h:32
圧縮していない moveの表現 .
Definition: basic_type.h:1051
DfpnShared * parallel_shared
Definition: dfpn.h:123
static const Move INVALID()
Definition: basic_type.h:1095
static const osl::CArray2d< int, 8, 16 > threshold
Definition: featureSet.cc:518
Player player() const
Definition: basic_type.h:1195
DfpnTable * table
Definition: dfpn.h:115
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition: dfpn.cc:1047
DfpnTable table_t
Definition: dfpn.h:113
size_t smallTreeGC(size_t threshold=10)
Definition: dfpn.cc:1191
void setBlockingVerify(bool enable=true)
Definition: dfpn.h:131
利きを持つ局面
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition: dfpn.cc:1074
詰探索
Definition: dfpn.h:106
bool isDrop() const
Definition: basic_type.h:1150
const HashKey newHashWithMove(Move move) const
Definition: hashKey.cc:63
void leaveWorking(const HashKey &key, int thread_id)
Definition: dfpn.cc:1140
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:16
size_t node_count
Definition: dfpn.h:121
CheckMoveVector DfpnMoveVector
Definition: dfpn.h:112
const DfpnRecord probe(const HashKey &key, PieceStand white) const
static int keyToIndex(const HashKey &key)
Definition: dfpn.h:90
Player
Definition: basic_type.h:8
size_t size() const
Definition: dfpn.cc:1251
uint64_t signature() const
Definition: hashKey.h:57
const DfpnTable & currentTable() const
Definition: dfpn.h:153
片方の手番の持駒の枚数を記録するクラス.
void showStats() const
Definition: dfpn.cc:921
std::unique_ptr< DfpnPathTable > path_table
Definition: dfpn.h:120
void addDag(const HashKey &key, DfpnRecord &value)
Definition: dfpn.cc:1098
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:1117
bool blocking_verify
Definition: dfpn.h:125
std::unique_ptr< Tree > tree
Definition: dfpn.h:118
Player attack() const
Definition: dfpn.cc:950
ProofOracle(const HashKey &k, PieceStand w)
Definition: dfpn.h:216
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition: dfpn.cc:912
int maxDepth() const
Definition: dfpn.cc:936
void setMaxDepth(int)
Definition: dfpn.cc:931