説明を見る。00001
00002
00003 #include "osl/repetitionCounter.h"
00004 #include "osl/hashKey.h"
00005 #include "osl/numEffectState.h"
00006 #include <unordered_map>
00007 #include <iostream>
00008
00009
00010 typedef osl::RepetitionCounter::list_t list_t;
00011 typedef std::unordered_map<osl::HashKey,list_t,std::hash<osl::HashKey>> map_t;
00012
00013 struct osl::RepetitionCounter::Table : public map_t
00014 {
00015 };
00016
00017 static const int initial_capacity = 256;
00018
00019 void osl::RepetitionCounter::
00020 clear()
00021 {
00022 table->clear();
00023 continuous_check[0].clear();
00024 continuous_check[1].clear();
00025 hash_history.clear();
00026
00027 continuous_check[0].reserve(initial_capacity);
00028 continuous_check[1].reserve(initial_capacity);
00029
00030 continuous_check[0].push_back(0);
00031 continuous_check[1].push_back(0);
00032 }
00033
00034 osl::RepetitionCounter::
00035 RepetitionCounter() : table(new Table()), hash_history(initial_capacity)
00036 {
00037 clear();
00038 }
00039
00040 osl::RepetitionCounter::
00041 RepetitionCounter(const RepetitionCounter& c)
00042 : continuous_check(c.continuous_check),
00043 hash_history(c.hash_history)
00044 {
00045 if (c.table)
00046 table.reset(new Table(*c.table));
00047 assert(isConsistent());
00048 }
00049
00050
00051 osl::RepetitionCounter::
00052 RepetitionCounter(const NumEffectState& initial)
00053 : table(new Table()), hash_history(initial_capacity)
00054 {
00055 clear();
00056 const HashKey key(initial);
00057 push(key, initial);
00058 }
00059
00060 osl::RepetitionCounter::
00061 ~RepetitionCounter()
00062 {
00063 }
00064
00065 void osl::RepetitionCounter::
00066 push(const HashKey& new_key, bool is_check)
00067 {
00068 const Player last_turn = alt(new_key.turn());
00069 if (is_check)
00070 {
00071 continuous_check[last_turn].push_back(checkCount(last_turn)+1);
00072 }
00073 else
00074 {
00075 continuous_check[last_turn].push_back(0);
00076 }
00077
00078 const Table::iterator p=table->find(new_key);
00079 if (p == table->end())
00080 {
00081 (*table)[new_key].push_front(order());
00082 }
00083 else
00084 {
00085 list_t& l = p->second;
00086 l.push_front(order());
00087 }
00088 hash_history.push(new_key);
00089 }
00090
00091 void osl::RepetitionCounter::
00092 push(const HashKey& key, const NumEffectState& state)
00093 {
00094 const bool is_check = state.inCheck();
00095 push(key, is_check);
00096 }
00097
00098 void osl::RepetitionCounter::
00099 push(const NumEffectState& state)
00100 {
00101 push(HashKey(state), state);
00102 }
00103
00104 void osl::RepetitionCounter::
00105 push(const NumEffectState& state, Move move)
00106 {
00107 assert(move.isValidOrPass());
00108 assert(state.turn() == move.player());
00109
00110 HashKey key(state);
00111 key = key.newHashWithMove(move);
00112
00113
00114 const bool is_check
00115 = (!move.isPass()) && state.isCheck(move);
00116 push(key, is_check);
00117 }
00118
00119 void osl::RepetitionCounter::
00120 pop()
00121 {
00122 assert(order());
00123 assert(hash_history.size()>0);
00124 const HashKey last_key = hash_history.top();
00125 hash_history.pop();
00126
00127 const Player last_turn = alt(last_key.turn());
00128 assert(! continuous_check[last_turn].empty());
00129 continuous_check[last_turn].pop_back();
00130
00131 const Table::iterator p=table->find(last_key);
00132 assert(p != table->end());
00133
00134 #ifndef NDEBUG
00135 const list_t::iterator q = p->second.begin();
00136 assert(q != p->second.end());
00137 assert(*q == order());
00138 #endif
00139 p->second.pop_front();
00140 if (p->second.empty())
00141 table->erase(p);
00142 }
00143
00144 int osl::RepetitionCounter::
00145 getLastMove(const HashKey& key) const
00146 {
00147 const Table::const_iterator p=table->find(key);
00148 if (p == table->end())
00149 return -1;
00150 return p->second.front();
00151 }
00152 int osl::RepetitionCounter::
00153 getFirstMove(const HashKey& key) const
00154 {
00155 const Table::const_iterator p=table->find(key);
00156 if (p == table->end())
00157 return -1;
00158 list_t::const_iterator q = p->second.begin();
00159 assert(q != p->second.end());
00160 int result = *q++;
00161 while (q != p->second.end())
00162 result = *q++;
00163 return result;
00164 }
00165
00166 const osl::Sennichite osl::RepetitionCounter::
00167 isSennichite(const NumEffectState& state, Move move) const
00168 {
00169 HashKey key(state);
00170 key = key.newHashWithMove(move);
00171 const Table::const_iterator p=table->find(key);
00172 if (p == table->end())
00173 return Sennichite::NORMAL();
00174
00175
00176 if (p->second.size() < 3)
00177 return Sennichite::NORMAL();
00178 return isAlmostSennichite(key);
00179 }
00180
00181 const std::pair<osl::Sennichite,int> osl::RepetitionCounter::
00182 distanceToSennichite(const HashKey& key) const
00183 {
00184 const Table::const_iterator p=table->find(key);
00185 if (p == table->end())
00186 return std::make_pair(Sennichite::NORMAL(), 0);
00187 return std::make_pair(isAlmostSennichite(key), p->second.size());
00188 }
00189
00190 unsigned int osl::RepetitionCounter::
00191 countRepetition(const HashKey& key) const
00192 {
00193 const Table::const_iterator p=table->find(key);
00194 if (p == table->end())
00195 return 0;
00196 return p->second.size();
00197 }
00198
00199 const list_t osl::RepetitionCounter::
00200 getRepetitions(const HashKey& key) const
00201 {
00202 Table::const_iterator p=table->find(key);
00203 if (p == table->end())
00204 return list_t();
00205 return p->second;
00206 }
00207
00208 #ifndef MINIMAL
00209 void osl::RepetitionCounter::
00210 printMatches(const HashKey& key) const
00211 {
00212 Table::const_iterator p=table->find(key);
00213 if (p == table->end())
00214 return;
00215 for (int q: p->second) {
00216 std::cerr << q << " ";
00217 }
00218 std::cerr << "\n";
00219 }
00220
00221 bool osl::RepetitionCounter::
00222 isConsistent() const
00223 {
00224 HashKeyStack history = hash_history;
00225 Table table(*this->table);
00226 CArray<std::vector<int>, 2> continuous_check = this->continuous_check;
00227 while (history.empty())
00228 {
00229 const HashKey last_key = history.top();
00230 history.pop();
00231
00232 const Player last_turn = alt(last_key.turn());
00233 assert(! continuous_check[last_turn].empty());
00234 continuous_check[last_turn].pop_back();
00235
00236 const Table::iterator p=table.find(last_key);
00237 if (p == table.end())
00238 {
00239 std::cerr << "oops, " << this << "\n";
00240 return false;
00241 }
00242 assert(p != table.end());
00243
00244 #ifndef NDEBUG
00245 const list_t::iterator q = p->second.begin();
00246 assert(q != p->second.end());
00247 assert(*q == order());
00248 #endif
00249 p->second.pop_front();
00250 if (p->second.empty())
00251 table.erase(p);
00252 }
00253 return true;
00254 }
00255
00256 bool osl::RepetitionCounter::maybeEqual(const RepetitionCounter& l, const RepetitionCounter& r)
00257 {
00258 #if ! (__GNUC__ >= 4 && __GNUC_MINOR__ >=3)
00259
00260 if (*l.table != *r.table)
00261 return false;
00262 #endif
00263 if (l.continuous_check[0] != r.continuous_check[0])
00264 return false;
00265 if (l.continuous_check[1] != r.continuous_check[1])
00266 return false;
00267 return l.hash_history == r.hash_history;
00268 }
00269 #endif
00270
00271
00272
00273
00274
00275
00276