All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
repetitionCounter.cc
Go to the documentation of this file.
1 /* repetitionCounter.cc
2  */
4 #include "osl/hash/hashKey.h"
9 #include "osl/stl/hash_map.h"
10 #include <boost/foreach.hpp>
11 #include <iostream>
12 
13 #if (__GNUC__ < 3 || (__GNUC__ ==3 && __GNUC_MINOR__ < 4) ) && defined(USE_GPL_POOL_ALLOCATOR)
14 template class osl::__gnu_cxx::__pool_alloc<true,0>;
15 #endif
16 
18 typedef osl::hash_map<osl::HashKey,list_t> map_t;
19 
21 {
22 };
23 
24 static const int initial_capacity = 256;
25 
28 {
29  table->clear();
30  continuous_check[0].clear();
31  continuous_check[1].clear();
32  hash_history.clear();
33 
36 
37  continuous_check[0].push_back(0);
38  continuous_check[1].push_back(0);
39 }
40 
42 RepetitionCounter() : table(new Table()), hash_history(initial_capacity)
43 {
44  clear();
45 }
46 
49  : continuous_check(c.continuous_check),
50  hash_history(c.hash_history)
51 {
52  if (c.table)
53  table.reset(new Table(*c.table));
54  assert(isConsistent());
55 }
56 
57 
59 RepetitionCounter(const NumEffectState& initial)
60  : table(new Table()), hash_history(initial_capacity)
61 {
62  clear();
63  const HashKey key(initial);
64  push(key, initial);
65 }
66 
69 {
70 }
71 
73 push(const HashKey& new_key, bool is_check)
74 {
75  const Player last_turn = alt(new_key.turn());
76  if (is_check)
77  {
78  continuous_check[last_turn].push_back(checkCount(last_turn)+1);
79  }
80  else
81  {
82  continuous_check[last_turn].push_back(0);
83  }
84 
85  const Table::iterator p=table->find(new_key);
86  if (p == table->end())
87  {
88  (*table)[new_key].push_front(order());
89  }
90  else
91  {
92  list_t& l = p->second;
93  l.push_front(order());
94  }
95  hash_history.push(new_key);
96 }
97 
99 push(const HashKey& key, const NumEffectState& state)
100 {
101  const bool is_check = state.inCheck();
102  push(key, is_check);
103 }
104 
106 push(const NumEffectState& state)
107 {
108  push(HashKey(state), state);
109 }
110 
112 push(const NumEffectState& state, Move move)
113 {
114  assert(move.isValidOrPass());
115  assert(state.turn() == move.player());
116 
117  HashKey key(state);
118  key = key.newHashWithMove(move);
119 
120  // 指した後の王手を検出
121  using namespace move_classifier;
122  const bool is_check
123  = (!move.isPass()) && PlayerMoveAdaptor<Check>::isMember(state, move);
124  push(key, is_check);
125 }
126 
129 {
130  assert(order());
131  assert(hash_history.size()>0);
132  const HashKey last_key = hash_history.top();
133  hash_history.pop();
134 
135  const Player last_turn = alt(last_key.turn());
136  assert(! continuous_check[last_turn].empty());
137  continuous_check[last_turn].pop_back();
138 
139  const Table::iterator p=table->find(last_key);
140  assert(p != table->end());
141 
142 #ifndef NDEBUG
143  const list_t::iterator q = p->second.begin();
144  assert(q != p->second.end());
145  assert(*q == order());
146 #endif
147  p->second.pop_front();
148  if (p->second.empty())
149  table->erase(p);
150 }
151 
153 getLastMove(const HashKey& key) const
154 {
155  const Table::const_iterator p=table->find(key);
156  if (p == table->end())
157  return -1;
158  return p->second.front();
159 }
161 getFirstMove(const HashKey& key) const
162 {
163  const Table::const_iterator p=table->find(key);
164  if (p == table->end())
165  return -1;
166  list_t::const_iterator q = p->second.begin();
167  assert(q != p->second.end());
168  int result = *q++;
169  while (q != p->second.end())
170  result = *q++;
171  return result;
172 }
173 
175 isSennichite(const NumEffectState& state, Move move) const
176 {
177  HashKey key(state);
178  key = key.newHashWithMove(move);
179  const Table::const_iterator p=table->find(key);
180  if (p == table->end())
181  return Sennichite::NORMAL();
182 
183  // 現在3だと次で4
184  if (p->second.size() < 3)
185  return Sennichite::NORMAL();
186  return isAlmostSennichite(key);
187 }
188 
189 const std::pair<osl::Sennichite,int> osl::RepetitionCounter::
190 distanceToSennichite(const HashKey& key) const
191 {
192  const Table::const_iterator p=table->find(key);
193  if (p == table->end())
194  return std::make_pair(Sennichite::NORMAL(), 0);
195  return std::make_pair(isAlmostSennichite(key), p->second.size());
196 }
197 
198 unsigned int osl::RepetitionCounter::
199 countRepetition(const HashKey& key) const
200 {
201  const Table::const_iterator p=table->find(key);
202  if (p == table->end())
203  return 0;
204  return p->second.size();
205 }
206 
208 getRepetitions(const HashKey& key) const
209 {
210  Table::const_iterator p=table->find(key);
211  if (p == table->end())
212  return list_t();
213  return p->second;
214 }
215 
216 #ifndef MINIMAL
218 printMatches(const HashKey& key) const
219 {
220  Table::const_iterator p=table->find(key);
221  if (p == table->end())
222  return;
223  BOOST_FOREACH(int q, p->second)
224  {
225  std::cerr << q << " ";
226  }
227  std::cerr << "\n";
228 }
229 
232 {
233  HashKeyStack history = hash_history;
234  Table table(*this->table);
235  CArray<osl::vector<int>, 2> continuous_check = this->continuous_check;
236  while (history.empty())
237  {
238  const HashKey last_key = history.top();
239  history.pop();
240 
241  const Player last_turn = alt(last_key.turn());
242  assert(! continuous_check[last_turn].empty());
243  continuous_check[last_turn].pop_back();
244 
245  const Table::iterator p=table.find(last_key);
246  if (p == table.end())
247  {
248  std::cerr << "oops, " << this << "\n";
249  return false;
250  }
251  assert(p != table.end());
252 
253 #ifndef NDEBUG
254  const list_t::iterator q = p->second.begin();
255  assert(q != p->second.end());
256  assert(*q == order());
257 #endif
258  p->second.pop_front();
259  if (p->second.empty())
260  table.erase(p);
261  }
262  return true;
263 }
264 
266 {
267 #if ! (__GNUC__ >= 4 && __GNUC_MINOR__ >=3)
268  // oops
269  if (*l.table != *r.table)
270  return false;
271 #endif
272  if (l.continuous_check[0] != r.continuous_check[0])
273  return false;
274  if (l.continuous_check[1] != r.continuous_check[1])
275  return false;
276  return l.hash_history == r.hash_history;
277 }
278 #endif
279 
280 /* ------------------------------------------------------------------------- */
281 // ;;; Local Variables:
282 // ;;; mode:c++
283 // ;;; c-basic-offset:2
284 // ;;; coding:utf-8
285 // ;;; End: