My Project
repetitionCounter.cc
Go to the documentation of this file.
1 /* repetitionCounter.cc
2  */
4 #include "osl/hashKey.h"
5 #include "osl/numEffectState.h"
6 #include <unordered_map>
7 #include <iostream>
8 
9 
11 typedef std::unordered_map<osl::HashKey,list_t,std::hash<osl::HashKey>> map_t;
12 
14 {
15 };
16 
17 static const int initial_capacity = 256;
18 
20 clear()
21 {
22  table->clear();
23  continuous_check[0].clear();
24  continuous_check[1].clear();
26 
29 
30  continuous_check[0].push_back(0);
31  continuous_check[1].push_back(0);
32 }
33 
35 RepetitionCounter() : table(new Table()), hash_history(initial_capacity)
36 {
37  clear();
38 }
39 
42  : continuous_check(c.continuous_check),
43  hash_history(c.hash_history)
44 {
45  if (c.table)
46  table.reset(new Table(*c.table));
47  assert(isConsistent());
48 }
49 
50 
52 RepetitionCounter(const NumEffectState& initial)
53  : table(new Table()), hash_history(initial_capacity)
54 {
55  clear();
56  const HashKey key(initial);
57  push(key, initial);
58 }
59 
62 {
63 }
64 
66 push(const HashKey& new_key, bool is_check)
67 {
68  const Player last_turn = alt(new_key.turn());
69  if (is_check)
70  {
71  continuous_check[last_turn].push_back(checkCount(last_turn)+1);
72  }
73  else
74  {
75  continuous_check[last_turn].push_back(0);
76  }
77 
78  const Table::iterator p=table->find(new_key);
79  if (p == table->end())
80  {
81  (*table)[new_key].push_front(order());
82  }
83  else
84  {
85  list_t& l = p->second;
86  l.push_front(order());
87  }
88  hash_history.push(new_key);
89 }
90 
92 push(const HashKey& key, const NumEffectState& state)
93 {
94  const bool is_check = state.inCheck();
95  push(key, is_check);
96 }
97 
99 push(const NumEffectState& state)
100 {
101  push(HashKey(state), state);
102 }
103 
105 push(const NumEffectState& state, Move move)
106 {
107  assert(move.isValidOrPass());
108  assert(state.turn() == move.player());
109 
110  HashKey key(state);
111  key = key.newHashWithMove(move);
112 
113  // 指した後の王手を検出
114  const bool is_check
115  = (!move.isPass()) && state.isCheck(move);
116  push(key, is_check);
117 }
118 
120 pop()
121 {
122  assert(order());
123  assert(hash_history.size()>0);
124  const HashKey last_key = hash_history.top();
125  hash_history.pop();
126 
127  const Player last_turn = alt(last_key.turn());
128  assert(! continuous_check[last_turn].empty());
129  continuous_check[last_turn].pop_back();
130 
131  const Table::iterator p=table->find(last_key);
132  assert(p != table->end());
133 
134 #ifndef NDEBUG
135  const list_t::iterator q = p->second.begin();
136  assert(q != p->second.end());
137  assert(*q == order());
138 #endif
139  p->second.pop_front();
140  if (p->second.empty())
141  table->erase(p);
142 }
143 
145 getLastMove(const HashKey& key) const
146 {
147  const Table::const_iterator p=table->find(key);
148  if (p == table->end())
149  return -1;
150  return p->second.front();
151 }
153 getFirstMove(const HashKey& key) const
154 {
155  const Table::const_iterator p=table->find(key);
156  if (p == table->end())
157  return -1;
158  list_t::const_iterator q = p->second.begin();
159  assert(q != p->second.end());
160  int result = *q++;
161  while (q != p->second.end())
162  result = *q++;
163  return result;
164 }
165 
167 isSennichite(const NumEffectState& state, Move move) const
168 {
169  HashKey key(state);
170  key = key.newHashWithMove(move);
171  const Table::const_iterator p=table->find(key);
172  if (p == table->end())
173  return Sennichite::NORMAL();
174 
175  // 現在3だと次で4
176  if (p->second.size() < 3)
177  return Sennichite::NORMAL();
178  return isAlmostSennichite(key);
179 }
180 
181 const std::pair<osl::Sennichite,int> osl::RepetitionCounter::
182 distanceToSennichite(const HashKey& key) const
183 {
184  const Table::const_iterator p=table->find(key);
185  if (p == table->end())
186  return std::make_pair(Sennichite::NORMAL(), 0);
187  return std::make_pair(isAlmostSennichite(key), p->second.size());
188 }
189 
191 countRepetition(const HashKey& key) const
192 {
193  const Table::const_iterator p=table->find(key);
194  if (p == table->end())
195  return 0;
196  return p->second.size();
197 }
198 
200 getRepetitions(const HashKey& key) const
201 {
202  Table::const_iterator p=table->find(key);
203  if (p == table->end())
204  return list_t();
205  return p->second;
206 }
207 
208 #ifndef MINIMAL
210 printMatches(const HashKey& key) const
211 {
212  Table::const_iterator p=table->find(key);
213  if (p == table->end())
214  return;
215  for (int q: p->second) {
216  std::cerr << q << " ";
217  }
218  std::cerr << "\n";
219 }
220 
222 isConsistent() const
223 {
224  HashKeyStack history = hash_history;
225  Table table(*this->table);
226  CArray<std::vector<int>, 2> continuous_check = this->continuous_check;
227  while (history.empty())
228  {
229  const HashKey last_key = history.top();
230  history.pop();
231 
232  const Player last_turn = alt(last_key.turn());
233  assert(! continuous_check[last_turn].empty());
234  continuous_check[last_turn].pop_back();
235 
236  const Table::iterator p=table.find(last_key);
237  if (p == table.end())
238  {
239  std::cerr << "oops, " << this << "\n";
240  return false;
241  }
242  assert(p != table.end());
243 
244 #ifndef NDEBUG
245  const list_t::iterator q = p->second.begin();
246  assert(q != p->second.end());
247  assert(*q == order());
248 #endif
249  p->second.pop_front();
250  if (p->second.empty())
251  table.erase(p);
252  }
253  return true;
254 }
255 
257 {
258 #if ! (__GNUC__ >= 4 && __GNUC_MINOR__ >=3)
259  // oops
260  if (*l.table != *r.table)
261  return false;
262 #endif
263  if (l.continuous_check[0] != r.continuous_check[0])
264  return false;
265  if (l.continuous_check[1] != r.continuous_check[1])
266  return false;
267  return l.hash_history == r.hash_history;
268 }
269 #endif
270 
271 /* ------------------------------------------------------------------------- */
272 // ;;; Local Variables:
273 // ;;; mode:c++
274 // ;;; c-basic-offset:2
275 // ;;; coding:utf-8
276 // ;;; End:
repetitionCounter.h
osl::hash::HashKey::newHashWithMove
const HashKey newHashWithMove(Move move) const
Definition: hashKey.cc:63
osl::RepetitionCounter::~RepetitionCounter
~RepetitionCounter()
Definition: repetitionCounter.cc:61
osl::RepetitionCounter::pop
void pop()
Definition: repetitionCounter.cc:120
osl::RepetitionCounter::isConsistent
bool isConsistent() const
Definition: repetitionCounter.cc:222
osl::alt
constexpr Player alt(Player player)
Definition: basic_type.h:13
osl::RepetitionCounter::push
void push(const HashKey &new_key, bool is_check)
Definition: repetitionCounter.cc:66
osl::hash::HashKeyStack::clear
void clear()
Definition: hashKeyStack.h:21
osl::RepetitionCounter::isSennichite
const Sennichite isSennichite(const NumEffectState &state, Move move) const
Definition: repetitionCounter.cc:167
list_t
osl::RepetitionCounter::list_t list_t
Definition: repetitionCounter.cc:10
osl::Move
圧縮していない moveの表現 .
Definition: basic_type.h:1052
osl::hash::HashKey128::turn
Player turn() const
Definition: hashKey.h:105
osl::NumEffectState::inCheck
bool inCheck(Player P) const
Pの玉が王手状態
Definition: numEffectState.h:88
osl::hash::HashKey
Definition: hashKey.h:153
osl::RepetitionCounter::distanceToSennichite
const std::pair< Sennichite, int > distanceToSennichite(const HashKey &key) const
Definition: repetitionCounter.cc:182
osl::RepetitionCounter::getFirstMove
int getFirstMove(const HashKey &key) const
key の手を最初に登録した指手番号.
Definition: repetitionCounter.cc:153
osl::RepetitionCounter::printMatches
void printMatches(const HashKey &key) const
Definition: repetitionCounter.cc:210
osl::RepetitionCounter::Table
Definition: repetitionCounter.cc:14
osl::hash::HashKeyStack
Definition: hashKeyStack.h:12
osl::RepetitionCounter::list_t
std::list< int > list_t
Definition: repetitionCounter.h:28
osl::Move::isValidOrPass
bool isValidOrPass() const
Definition: basic_type.h:1205
osl::RepetitionCounter::RepetitionCounter
RepetitionCounter()
Definition: repetitionCounter.cc:35
osl::RepetitionCounter::clear
void clear()
Definition: repetitionCounter.cc:20
osl::RepetitionCounter::continuous_check
CArray< std::vector< int >, 2 > continuous_check
Definition: repetitionCounter.h:24
osl::RepetitionCounter::getLastMove
int getLastMove(const HashKey &key) const
key の手を最後に登録した指手番号.
Definition: repetitionCounter.cc:145
osl::hash::HashKeyStack::top
const HashKey & top(size_t n=0) const
Definition: hashKeyStack.h:23
osl::Sennichite
Definition: sennichite.h:12
osl::hash::HashKeyStack::pop
void pop()
Definition: hashKeyStack.h:20
map_t
std::unordered_map< osl::HashKey, list_t, std::hash< osl::HashKey > > map_t
Definition: repetitionCounter.cc:11
osl::NumEffectState
利きを持つ局面
Definition: numEffectState.h:34
hashKey.h
osl::NumEffectState::isCheck
bool isCheck(Move move) const
Definition: numEffectState.cc:1058
initial_capacity
static const int initial_capacity
Definition: repetitionCounter.cc:17
osl::Move::isPass
bool isPass() const
Definition: basic_type.h:1092
osl::RepetitionCounter::getRepetitions
const list_t getRepetitions(const HashKey &) const
Definition: repetitionCounter.cc:200
osl::SimpleState::turn
Player turn() const
Definition: simpleState.h:220
osl::Player
Player
Definition: basic_type.h:8
numEffectState.h
osl::RepetitionCounter
千日手の検出.
Definition: repetitionCounter.h:21
osl::CArray
Definition: container.h:20
osl::RepetitionCounter::maybeEqual
static bool maybeEqual(const RepetitionCounter &l, const RepetitionCounter &r)
Definition: repetitionCounter.cc:256
osl::hash::HashKeyStack::empty
bool empty() const
Definition: hashKeyStack.h:29
osl::RepetitionCounter::countRepetition
unsigned int countRepetition(const HashKey &) const
Definition: repetitionCounter.cc:191
osl::RepetitionCounter::hash_history
HashKeyStack hash_history
Definition: repetitionCounter.h:25
osl::Sennichite::NORMAL
static Sennichite NORMAL()
Definition: sennichite.h:21
osl::Move::player
Player player() const
Definition: basic_type.h:1195
osl::RepetitionCounter::table
std::unique_ptr< Table > table
Definition: repetitionCounter.h:22