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
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:
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 {
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の表現 .
Definition: basic_type.h:1052
static const Move INVALID()
Definition: basic_type.h:1095
Ptype ptype() const
Definition: basic_type.h:1155
Player player() const
Definition: basic_type.h:1195
bool isDrop() const
Definition: basic_type.h:1150
利きを持つ局面
片方の手番の持駒の枚数を記録するクラス.
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
const List * find(const HashKey &key, int subindex) const
size_t growthLimit() const
Definition: dfpn.h:73
void setMaxDepth(int)
Definition: dfpn.cc:931
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
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
int maxDepth() const
Definition: dfpn.cc:936
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
size_t totalSize()
Definition: dfpn.h:63
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
List * find(const HashKey &key, int subindex)
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:32
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
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2746
std::unique_ptr< Tree > tree
Definition: dfpn.h:118
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
const DfpnTable & currentTable() const
Definition: dfpn.h:153
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 blocking_verify
Definition: dfpn.h:125
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
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
void findDagSource()
Definition: dfpn.cc:1647
Dfpn & operator=(const Dfpn &)=delete
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
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
Definition: featureSet.cc:518
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