My Project
repetitionCounter.cc
Go to the documentation of this file.
1/* repetitionCounter.cc
2 */
4#include "osl/hashKey.h"
6#include <unordered_map>
7#include <iostream>
8
9
11typedef std::unordered_map<osl::HashKey,list_t,std::hash<osl::HashKey>> map_t;
12
14{
15};
16
17static const int initial_capacity = 256;
18
20clear()
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
35RepetitionCounter() : 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
53 : table(new Table()), hash_history(initial_capacity)
54{
55 clear();
56 const HashKey key(initial);
57 push(key, initial);
58}
59
64
66push(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
92push(const HashKey& key, const NumEffectState& state)
93{
94 const bool is_check = state.inCheck();
95 push(key, is_check);
96}
97
99push(const NumEffectState& state)
100{
101 push(HashKey(state), state);
102}
103
105push(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
120pop()
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
145getLastMove(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}
153getFirstMove(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
167isSennichite(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
181const std::pair<osl::Sennichite,int> osl::RepetitionCounter::
182distanceToSennichite(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
191countRepetition(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
200getRepetitions(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
210printMatches(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
222isConsistent() 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:
圧縮していない moveの表現 .
Player player() const
bool isPass() const
bool isValidOrPass() const
利きを持つ局面
bool inCheck(Player P) const
Pの玉が王手状態
bool isCheck(Move move) const
千日手の検出.
const Sennichite isSennichite(const NumEffectState &state, Move move) const
std::unique_ptr< Table > table
int getLastMove(const HashKey &key) const
key の手を最後に登録した指手番号.
const std::pair< Sennichite, int > distanceToSennichite(const HashKey &key) const
void push(const HashKey &new_key, bool is_check)
const list_t getRepetitions(const HashKey &) const
unsigned int countRepetition(const HashKey &) const
CArray< std::vector< int >, 2 > continuous_check
void printMatches(const HashKey &key) const
int getFirstMove(const HashKey &key) const
key の手を最初に登録した指手番号.
static bool maybeEqual(const RepetitionCounter &l, const RepetitionCounter &r)
static Sennichite NORMAL()
Definition sennichite.h:21
Player turn() const
Player turn() const
Definition hashKey.h:105
const HashKey & top(size_t n=0) const
const HashKey newHashWithMove(Move move) const
Definition hashKey.cc:63
Player
Definition basic_type.h:8
constexpr Player alt(Player player)
Definition basic_type.h:13
std::unordered_map< osl::HashKey, list_t, std::hash< osl::HashKey > > map_t
osl::RepetitionCounter::list_t list_t
static const int initial_capacity