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