All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
dfpn.h
Go to the documentation of this file.
1 /* dfpn.h
2  */
3 #ifndef OSL_DFPN_H
4 #define OSL_DFPN_H
9 #include "osl/hash/hashKey.h"
10 #include "osl/stl/vector.h"
11 #include "osl/pathEncoding.h"
12 #include "osl/config.h"
13 #include <boost/scoped_array.hpp>
14 #include <boost/scoped_ptr.hpp>
15 #include <boost/noncopyable.hpp>
16 
17 #ifdef OSL_SMP
18 # ifndef OSL_DFPN_SMP
19 # define OSL_DFPN_SMP
20 # endif
21 #endif
22 
23 #ifdef OSL_DFPN_SMP
24 # include "osl/misc/lightMutex.h"
25 # include <boost/thread/mutex.hpp>
26 #endif
27 
28 namespace osl
29 {
30  namespace checkmate
31  {
32  class DfpnRecord;
34  class DfpnTable
35  {
36  struct Table;
37  struct List;
38  boost::scoped_array<Table> table;
39  size_t total_size;
42  public:
44  DfpnTable();
45  ~DfpnTable();
46  template <Player Attack>
47  const DfpnRecord probe(const HashKey& key, PieceStand white) const;
48  const DfpnRecord probe(const HashKey& key, PieceStand white) const;
49  size_t estimateNodeCount(const HashKey& key, bool dominance_max=false) const;
50  template <Player Attack>
51  const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
52  const DfpnRecord findProofOracle(const HashKey& key, PieceStand white, Move last_move=Move()) const;
53  template <Player Attack>
54  void showProofOracles(const HashKey& key, PieceStand white, Move last_move=Move()) const;
55  size_t
56 #ifdef __GNUC__
57  __attribute__ ((pure))
58 #endif
59  size() const;
60  void showStats() const;
61 
62  void setAttack(Player);
63  void setWorking(const HashKey& key, const DfpnRecord& value, int thread_id);
64  void leaveWorking(const HashKey& key, int thread_id);
65  void store(const HashKey& key, DfpnRecord& value, int leaving_thread_id=-1);
66  void addDag(const HashKey& key, DfpnRecord& value);
67  void clear();
68  size_t totalSize() { return total_size; }
69  Player attack() const;
70 
71  void setMaxDepth(int);
72  int maxDepth() const;
73 
74  void testTable();
75  size_t smallTreeGC(size_t threshold=10);
77  void setGrowthLimit(size_t new_limit);
78  size_t growthLimit() const { return growth_limit; }
79  bool runGC();
80  private:
81 #ifdef OSL_DFPN_SMP
82  typedef osl::misc::LightMutex Mutex;
83 # ifdef USE_TBB_HASH
84  static const int DIVSIZE=1;
85 # else
86  static const int DIVSIZE=256;
87  mutable CArray<Mutex,DIVSIZE> mutex;
88 # endif
89  // typedef boost::mutex Mutex;
90  // TODO: boost::thread::shared_lock (available version >= 1.35) for multi read accessess
91  LightMutex root_mutex;
92 #else
93  static const int DIVSIZE=1;
94 #endif
95  static int keyToIndex(const HashKey& key)
96  {
97  unsigned long val=key.signature();
98  return (val>>24)%DIVSIZE;
99  }
100  template <Player Attack>
101  List *find(const HashKey& key, int subindex);
102  template <Player Attack>
103  const List *find(const HashKey& key, int subindex) const;
104  const List *find(const HashKey& key, int subindex) const;
105  };
107  class DfpnPathTable;
109  class DfpnShared;
111  class Dfpn : boost::noncopyable
112  {
113  public:
117  private:
119  struct NodeBase;
120  struct Node;
121  struct Tree;
122  boost::scoped_ptr<Tree> tree;
123  boost::scoped_ptr<DfpnPathTable> path_table;
124  size_t node_count;
129  public:
130  Dfpn();
131  ~Dfpn();
132  void setTable(DfpnTable *new_table);
133  void setIllegal(const HashKey& key, PieceStand white);
134  void setBlockingVerify(bool enable=true) { blocking_verify = enable; }
135  void setParallel(int id, DfpnShared *s)
136  {
137  if (s)
138  assert(id >= 0);
139  thread_id = id;
140  parallel_shared = s;
141  }
142  const ProofDisproof
143  hasCheckmateMove(const NumEffectState& state, const HashKey& key,
144  const PathEncoding& path, size_t limit, Move& best_move,
145  Move last_move=Move::INVALID(), vector<Move> *pv=0);
146  const ProofDisproof
147  hasCheckmateMove(const NumEffectState& state, const HashKey& key,
148  const PathEncoding& path, size_t limit, Move& best_move, PieceStand& proof,
149  Move last_move=Move::INVALID(), vector<Move> *pv=0);
150  const ProofDisproof
151  hasEscapeMove(const NumEffectState& state,
152  const HashKey& key, const PathEncoding& path,
153  size_t limit, Move last_move);
154 
155  size_t nodeCount() const { return node_count; }
156  const DfpnTable& currentTable() const { return *table; }
157  void analyze(const PathEncoding& path,
158  const NumEffectState& state, const vector<Move>& moves) const;
159  void clear();
160 
161  // private:
162  template <Player P> void attack();
163  template <Player P> void defense();
164  template <Player P> struct CallAttack;
165  template <Player P> struct CallDefense;
166  struct DepthLimitReached {};
167 
168  struct ProofOracle;
169  template <Player P, bool UseTable> void proofOracleAttack(const ProofOracle& oracle, int proof_limit);
170  template <Player P, bool UseTable> void proofOracleDefense(const ProofOracle& oracle, int proof_limit);
171  template <Player P, bool UseTable> struct CallProofOracleAttack;
172  template <Player P, bool UseTable> struct CallProofOracleDefense;
174  template <Player P> void blockingSimulation(int seed, const ProofOracle&);
175  template <Player P> void grandParentSimulation(int cur_move, const Node& gparent, int gp_move);
176  private:
177  template <bool UseTable>
178  const ProofDisproof
179  tryProofMain(const NumEffectState& state, const HashKey& key,
180  const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
181  Move last_move);
182  public:
183  const ProofDisproof
184  tryProof(const NumEffectState& state, const HashKey& key,
185  const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
186  Move last_move=Move::INVALID());
187  const ProofDisproof
188  tryProofLight(const NumEffectState& state, const HashKey& key,
189  const PathEncoding& path, const ProofOracle&, size_t oracle_id, Move& best_move,
190  Move last_move=Move::INVALID());
191 
192  // debug
193  int distance(const HashKey&) const;
195  template <Player P>
196  static void generateCheck(const NumEffectState&, DfpnMoveVector&, bool&);
198  template <Player P>
199  static void generateEscape(const NumEffectState&, bool need_full_width,
200  Square grand_parent_delay_last_to, DfpnMoveVector&);
202  bool grandParentSimulationSuitable() const;
203  template <Player Turn>
204  static void sort(const NumEffectState&, DfpnMoveVector&);
205  private:
206  void findDagSource();
207  void findDagSource(const HashKey& terminal_key,
208  DfpnRecord& terminal_record,
209  PieceStand terminal_stand, int offset=0);
210  };
211 
212  }
213 }
214 
216 {
217  HashKey key;
219  ProofOracle(const HashKey& k, PieceStand w) : key(k), white_stand(w)
220  {
221  }
222  const ProofOracle newOracle(Player P, Move move) const
223  {
224  assert(P == move.player());
225  return ProofOracle(key.newHashWithMove(move),
226  (P == WHITE) ? white_stand.nextStand(P, move) : white_stand);
227  }
228  bool traceable(Player P, Move move) const
229  {
230  assert(P == move.player());
231  if (! move.isDrop())
232  return true;
233  if (P == BLACK) {
234  if (key.blackStand().get(move.ptype()) == 0)
235  return false;
236  }
237  else {
238  if (white_stand.get(move.ptype()) == 0)
239  return false;
240  }
241  return true;
242  }
243 };
244 
245 #endif /* OSL_DFPN_H */
246 // ;;; Local Variables:
247 // ;;; mode:c++
248 // ;;; c-basic-offset:2
249 // ;;; End: