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:
osl::checkmate::Dfpn::ProofOracle::white_stand
PieceStand white_stand
Definition: dfpn.h:215
osl::checkmate::DfpnTable::table
boost::scoped_array< Table > table
Definition: dfpn.h:32
osl::checkmate::Dfpn::NodeBase
Definition: dfpn.cc:337
osl::Square
Definition: basic_type.h:532
osl::hash::HashKey::newHashWithMove
const HashKey newHashWithMove(Move move) const
Definition: hashKey.cc:63
osl::checkmate::Dfpn::thread_id
int thread_id
Definition: dfpn.h:124
osl::checkmate::Dfpn::parallel_shared
DfpnShared * parallel_shared
Definition: dfpn.h:123
osl::WHITE
@ WHITE
Definition: basic_type.h:10
osl::checkmate::DfpnRecord
Definition: dfpnRecord.h:58
osl::checkmate::DfpnTable::store
void store(const HashKey &key, DfpnRecord &value, int leaving_thread_id=-1)
Definition: dfpn.cc:1074
osl::checkmate::Dfpn::path_table
std::unique_ptr< DfpnPathTable > path_table
Definition: dfpn.h:120
osl::checkmate::Dfpn::CallProofOracleDefense
Definition: dfpn.cc:2731
osl::checkmate::Dfpn::setBlockingVerify
void setBlockingVerify(bool enable=true)
Definition: dfpn.h:131
osl::checkmate::Dfpn::attack
void attack()
Definition: dfpn.cc:1656
osl::checkmate::Dfpn::tree
std::unique_ptr< Tree > tree
Definition: dfpn.h:118
osl::checkmate::Dfpn
詰探索
Definition: dfpn.h:107
osl::checkmate::Dfpn::ProofOracle
Definition: dfpn.h:213
osl::checkmate::Dfpn::proofOracleDefense
void proofOracleDefense(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2872
PathEncoding
Definition: pathEncoding.cc:12
osl::CheckMoveVector
Definition: container.h:301
osl::checkmate::DfpnTable::setGrowthLimit
void setGrowthLimit(size_t new_limit)
set the maximum size of table (otherwise infinity).
Definition: dfpn.cc:912
osl::checkmate::Dfpn::grandParentSimulation
void grandParentSimulation(int cur_move, const Node &gparent, int gp_move)
Definition: dfpn.cc:3096
osl::Move
圧縮していない moveの表現 .
Definition: basic_type.h:1052
osl::checkmate::DfpnTable::probe
const DfpnRecord probe(const HashKey &key, PieceStand white) const
osl::checkmate::DfpnTable::maxDepth
int maxDepth() const
Definition: dfpn.cc:936
osl::checkmate::DfpnTable::~DfpnTable
~DfpnTable()
Definition: dfpn.cc:907
osl::checkmate::Dfpn::Dfpn
Dfpn(const Dfpn &)=delete
lightMutex.h
osl::checkmate::Dfpn::DfpnMaxUniqMoves
@ DfpnMaxUniqMoves
Definition: dfpn.h:111
osl::checkmate::Dfpn::tryProof
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
osl::checkmate::Dfpn::node_count_limit
size_t node_count_limit
Definition: dfpn.h:122
osl::checkmate::Dfpn::hasEscapeMove
const ProofDisproof hasEscapeMove(const NumEffectState &state, const HashKey &key, const PathEncoding &path, size_t limit, Move last_move)
Definition: dfpn.cc:1469
osl::checkmate::DfpnTable::setAttack
void setAttack(Player)
Definition: dfpn.cc:942
osl::hash::HashKey128::blackStand
const PieceStand blackStand() const
Definition: hashKey.h:64
osl::Move::INVALID
static const Move INVALID()
Definition: basic_type.h:1095
osl::checkmate::Dfpn::Tree
Definition: dfpn.cc:472
osl::checkmate::Dfpn::proofOracleAttack
void proofOracleAttack(const ProofOracle &oracle, int proof_limit)
Definition: dfpn.cc:2746
osl::CheckOrEscapeMaxUniqMoves
@ CheckOrEscapeMaxUniqMoves
Definition: container.h:299
osl::checkmate::Dfpn::blockingSimulation
void blockingSimulation(int seed, const ProofOracle &)
合駒が詰と判った直後に、同じような合駒を詰める
Definition: dfpn.cc:3046
osl::checkmate::Dfpn::~Dfpn
~Dfpn()
Definition: dfpn.cc:1292
osl::checkmate::DfpnTable::gc_threshold
size_t gc_threshold
Definition: dfpn.h:36
osl::checkmate::DfpnTable::keyToIndex
static int keyToIndex(const HashKey &key)
Definition: dfpn.h:90
osl::checkmate::DfpnTable::totalSize
size_t totalSize()
Definition: dfpn.h:63
osl::checkmate::DfpnTable::runGC
bool runGC()
Definition: dfpn.cc:1217
osl::checkmate::DfpnTable::addDag
void addDag(const HashKey &key, DfpnRecord &value)
Definition: dfpn.cc:1098
osl::checkmate::Dfpn::defense
void defense()
Definition: dfpn.cc:2183
osl::checkmate::DfpnTable::setMaxDepth
void setMaxDepth(int)
Definition: dfpn.cc:931
osl::hash::HashKey
Definition: hashKey.h:153
checkmate
osl::PieceStand::nextStand
const PieceStand nextStand(Player pl, Move move) const
Definition: bits/pieceStand.h:203
osl::checkmate::DfpnTable::clear
void clear()
Definition: dfpn.cc:1157
pathEncoding.h
osl::checkmate::Dfpn::distance
int distance(const HashKey &) const
Definition: dfpn.cc:3131
proofDisproof.h
osl::checkmate::Dfpn::ProofOracle::key
HashKey key
Definition: dfpn.h:214
threshold
static const osl::CArray2d< int, 8, 16 > threshold
Definition: featureSet.cc:518
osl::checkmate::Dfpn::node_count
size_t node_count
Definition: dfpn.h:121
osl::checkmate::DfpnTable::size
size_t size() const
Definition: dfpn.cc:1251
osl::misc::LightMutex
Definition: lightMutex.h:51
osl::Move::isDrop
bool isDrop() const
Definition: basic_type.h:1150
osl::checkmate::Dfpn::sort
static void sort(const NumEffectState &, DfpnMoveVector &)
Definition: dfpn.cc:1555
osl::checkmate::DfpnTable::growth_limit
size_t growth_limit
Definition: dfpn.h:36
osl::checkmate::DfpnTable::smallTreeGC
size_t smallTreeGC(size_t threshold=10)
Definition: dfpn.cc:1191
osl::checkmate::Dfpn::CallProofOracleAttack
Definition: dfpn.cc:2716
osl::checkmate::Dfpn::setTable
void setTable(DfpnTable *new_table)
Definition: dfpn.cc:1296
osl::checkmate::DfpnTable::leaveWorking
void leaveWorking(const HashKey &key, int thread_id)
Definition: dfpn.cc:1140
osl::checkmate::Dfpn::analyze
void analyze(const PathEncoding &path, const NumEffectState &state, const std::vector< Move > &moves) const
Definition: dfpn.cc:2651
osl::PieceStand
片方の手番の持駒の枚数を記録するクラス.
Definition: bits/pieceStand.h:38
osl::checkmate::DfpnTable::showStats
void showStats() const
Definition: dfpn.cc:921
osl::checkmate::DfpnTable::find
List * find(const HashKey &key, int subindex)
osl::checkmate::Dfpn::ProofOracle::traceable
bool traceable(Player P, Move move) const
Definition: dfpn.h:225
osl::checkmate::Dfpn::hasCheckmateMove
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
osl::checkmate::DfpnTable::setWorking
void setWorking(const HashKey &key, const DfpnRecord &value, int thread_id)
Definition: dfpn.cc:1117
osl::checkmate::Dfpn::ProofOracle::ProofOracle
ProofOracle(const HashKey &k, PieceStand w)
Definition: dfpn.h:216
osl::checkmate::DfpnTable::find
const List * find(const HashKey &key, int subindex) const
osl::NumEffectState
利きを持つ局面
Definition: numEffectState.h:34
osl::checkmate::Dfpn::Dfpn
Dfpn()
Definition: dfpn.cc:1287
osl::checkmate::Dfpn::tryProofMain
const ProofDisproof tryProofMain(const NumEffectState &state, const HashKey &key, const PathEncoding &path, const ProofOracle &, size_t oracle_id, Move &best_move, Move last_move)
osl::checkmate::Dfpn::setParallel
void setParallel(int id, DfpnShared *s)
Definition: dfpn.h:132
hashKey.h
osl::checkmate::Dfpn::DfpnMoveVector
CheckMoveVector DfpnMoveVector
Definition: dfpn.h:112
osl::checkmate::Dfpn::DepthLimitReached
Definition: dfpn.h:163
osl::checkmate::DfpnPathTable
Definition: dfpn.cc:270
osl::checkmate::Dfpn::Node
Definition: dfpn.cc:350
osl::checkmate::DfpnTable::findProofOracle
const DfpnRecord findProofOracle(const HashKey &key, PieceStand white, Move last_move=Move()) const
osl::checkmate::DfpnTable::showProofOracles
void showProofOracles(const HashKey &key, PieceStand white, Move last_move=Move()) const
Definition: dfpn.cc:1047
osl::checkmate::DfpnTable::attack
Player attack() const
Definition: dfpn.cc:950
osl::checkmate::Dfpn::table
DfpnTable * table
Definition: dfpn.h:115
osl::checkmate::Dfpn::clear
void clear()
Definition: dfpn.cc:1305
osl::Move::ptype
Ptype ptype() const
Definition: basic_type.h:1155
osl::BLACK
@ BLACK
Definition: basic_type.h:9
osl::checkmate::Dfpn::ProofOracle::newOracle
const ProofOracle newOracle(Player P, Move move) const
Definition: dfpn.h:219
osl::checkmate::Dfpn::currentTable
const DfpnTable & currentTable() const
Definition: dfpn.h:153
osl::checkmate::DfpnTable::List
Definition: dfpn.cc:619
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
osl::checkmate::Dfpn::operator=
Dfpn & operator=(const Dfpn &)=delete
osl::hash::HashKey128::signature
uint64_t signature() const
Definition: hashKey.h:57
osl::checkmate::DfpnTable::DIVSIZE
static const int DIVSIZE
Definition: dfpn.h:88
config.h
osl::checkmate::Dfpn::tryProofLight
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
osl::checkmate::DfpnShared
Definition: dfpnParallel.h:14
osl::checkmate::Dfpn::blocking_verify
bool blocking_verify
Definition: dfpn.h:125
osl::checkmate::DfpnTable::dfpn_max_depth
int dfpn_max_depth
Definition: dfpn.h:35
osl::checkmate::Dfpn::findDagSource
void findDagSource()
Definition: dfpn.cc:1647
osl::checkmate::DfpnTable
詰探索局面表 – 並列でも共有する部分
Definition: dfpn.h:30
osl::checkmate::DfpnTable::Table
Definition: dfpn.cc:886
osl::checkmate::Dfpn::table_t
DfpnTable table_t
Definition: dfpn.h:113
osl::Player
Player
Definition: basic_type.h:8
numEffectState.h
osl::CArray
Definition: container.h:20
osl::checkmate::DfpnTable::estimateNodeCount
size_t estimateNodeCount(const HashKey &key, bool dominance_max=false) const
Definition: dfpn.cc:1061
osl::checkmate::Dfpn::grandParentSimulationSuitable
bool grandParentSimulationSuitable() const
test suitability of simulation of grand-parent relation
Definition: dfpn.cc:2162
osl::checkmate::DfpnTable::total_size
size_t total_size
Definition: dfpn.h:34
osl::checkmate::Dfpn::generateCheck
static void generateCheck(const NumEffectState &, DfpnMoveVector &, bool &)
Pは攻撃側
Definition: dfpn.cc:1573
osl::PieceStand::get
unsigned int get(Ptype type) const
Definition: bits/pieceStand.h:131
osl::checkmate::Dfpn::nodeCount
size_t nodeCount() const
Definition: dfpn.h:152
osl::checkmate::Dfpn::setIllegal
void setIllegal(const HashKey &key, PieceStand white)
Definition: dfpn.cc:1311
osl::checkmate::DfpnTable::growthLimit
size_t growthLimit() const
Definition: dfpn.h:73
osl::checkmate::Dfpn::generateEscape
static void generateEscape(const NumEffectState &, bool need_full_width, Square grand_parent_delay_last_to, DfpnMoveVector &)
Pは攻撃側
Definition: dfpn.cc:2105
osl::Move::player
Player player() const
Definition: basic_type.h:1195
osl::__attribute__
const PtypeO PTYPEO_EDGE __attribute__((unused))
osl::checkmate::DfpnTable::DfpnTable
DfpnTable()
Definition: dfpn.cc:902
osl
Definition: additionalEffect.h:6
osl::checkmate::DfpnTable::testTable
void testTable()
Definition: dfpn.cc:1169