Changeset 194

Timestamp:

10/06/06 20:46:47 (2 years ago)

Author:

ug

Message:

Hashing for corner patterns AlgoHash. Various smaller bug fixes.

Files:

• 06/libkombilo/cpptest.cc (modified) (3 diffs)
• 06/libkombilo/process.py (modified) (1 diff)
• 06/libkombilo/search.cc (modified) (28 diffs)
• 06/libkombilo/search.h (modified) (8 diffs)
• 06/libkombilo/testhash.py (modified) (1 diff)

06/libkombilo/cpptest.cc

@@ -8 +8 @@
-
-int main(int argc, char** argv) {
-
+
+
+
+
+
+
+
-
-
+
+
+
-    gl.start_processing();
-    directory_iterator end_itr;
-    // string path = "/home/ug/go/kombilo/06/libkombilo";
-
-// 
+// 
+
-    for(directory_iterator it(path); it != end_itr; ++it) {
-      string n = it->string();
@@ -38 +46 @@
-  printf("%d games.\n", gl.size());
-
+  Pattern p(CORNER_NW_PATTERN,19,8,8,"...................X......X.......XO......OO....................");
+  // Pattern p(CORNER_NW_PATTERN,19,7,7,".................X.....X......XO.....OO..........");
+  // Pattern p(CORNER_NW_PATTERN,19,7,7,".......................X.........................");
+
-  // gl.gisearch("pw = 'Hane Naoki'");
-Pattern p(CENTER_PATTERN, 19, 3, 5, ".X..OX.OX.OXOXO") 
+// Pattern p(CENTER_PATTERN, 19, 3, 5, ".X..OX.OX.OXOXO")
-  // vector<MoveNC> contList;
-  // contList.push_back(MoveNC(6,15,'X'));
@@ -50 +62 @@
-  gl.search(p, so);
-  printf("num games: %d, num hits: %d\n", gl.size(), gl.numHits());
-
-
-
-// 
+// 
+// 
+// 
+
-  printf("Search pattern:\n");
-  printf("%s\n", p.printPattern().c_str());

06/libkombilo/process.py

@@ -19 +19 @@
-
-    starttime = time.time()
-
+ | ALGO_HASH_CORNER
-    try:
-        gl = GameList('t1.db', 'id', '', algos, 19)

06/libkombilo/search.cc

@@ -36 +36 @@
-using std::make_pair;
-using std::stack;
+using std::sort;
-
-PatternError::PatternError() {}
@@ -419 +420 @@
-}
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-  pattern.copy(p);
-  fixedColor = fColor;
@@ -425 +440 @@
-  boardsize = bsize;
-  special = -1;
+  flipTable = new int[16];
+  for(int i=0; i<16; i++) flipTable[i] = -1; // (patternList() relies on this)
-
-  patternList();
+  for(int i=0; i<16; i++) 
+    if (flipTable[i] == -1) throw PatternError(); // FIXME: remove this once flipTable works ...
-  continuations = new Continuation[pattern.sizeX * pattern.sizeY];
-}
@@ -432 +451 @@
-PatternList::~PatternList() {
-  delete [] continuations;
+  delete [] flipTable;
-}
-
@@ -499 +519 @@
-      if (pNew == *it) {
-        foundNewPattern = false;
+        flipTable[f] = flipTable[it->flip];
-        break;
-      }
-    }
-
+
+
+
+
-
-    if (pNew == pattern) sy.push_back(pair<int,int>(f,0));
@@ -534 +558 @@
-      if (!fixedColor) {
-        bool foundNewPattern = true;
+        int lCS_ctr = 0;
-        for(vector<Pattern>::iterator it = lCS.begin(); it != lCS.end(); it++) {
-          if (pNew1 == *it) {
-            foundNewPattern = false;
+            flipTable[f+8] = lCS_ctr;
-            break;
-          }
+          lCS_ctr++;
-        }
-
+
+
+
-      }
-
@@ -550 +579 @@
-  }
-
+  int lCS_ctr = 0;
-  for(vector<Pattern>::iterator it = lCS.begin(); it != lCS.end(); it++) {
-    bool contained_in_l = false;
@@ -555 +585 @@
-      if (*it == *it_l) {
-        contained_in_l = true;
+        flipTable[8+it->flip] = flipTable[it_l->flip];
-        break;
-      }
-
+
+
+
+
+
+
+
-  }
-
@@ -763 +800 @@
-void Algorithm::finalize_process() {}
-int Algorithm::readDB(sqlite3* DB) { return 0; }
-
+
+
+
+
-
-Algo_signature::Algo_signature(int bsize) : Algorithm(bsize) {
@@ -1394 +1434 @@
-          if (p_ij != '.') d[i+p->sizeX*j] = p_ij;
-          else d[i+p->sizeX*j] = 0;
-or
+||
-        }
-      }
@@ -1478 +1518 @@
-                  (*it)->orientation, // pattern in question
-                  x-(*it)->mx, y-(*it)->my, // pos of continuation
-inv
+
-                  (counter.total_move_num()-(*it)->dictsF.total_move_num())>2, // tenuki?
-                  gl.getCurrentWinner()
@@ -1915 +1955 @@
-#endif
-
+HashhitF::HashhitF(int GAMEID, char ORIENTATION, char* blob) {
+  gameid = GAMEID;
+  orientation = ORIENTATION;
+  cont = new MoveNC(blob[0], blob[1], blob[2]);
+  emn = new ExtendedMoveNumber;
+  emn->length = blob[3] * 256 + blob[4];
+  emn->data = new int[emn->length];
+  for(int i=0; i<emn->length; i++) {
+    emn->data[i] = blob[5+2*i]*256 + blob[6+2*i];
+  }
+}
+
+HashhitF::HashhitF() {
+  printf("oops\n");
+  cont = 0;
+  emn = 0;
+}
+
+HashhitF::~HashhitF() {
+  if (cont) delete cont;
+  if (emn) delete emn;
+}
+
+bool cmp_HashhitF(const HashhitF* a, const HashhitF* b) {
+  return a->gameid < b->gameid;
+}
+
+HashhitCS::HashhitCS(int GAMEID, int POSITION, bool CS) {
+  gameid = GAMEID;
+  position = POSITION;
+  cs = CS;
+}
+
+bool cmp_HashhitCS(const HashhitCS* a, const HashhitCS* b) {
+  return a->gameid < b->gameid;
+}
+
+
+typedef vector<HashhitF* >* vpsip;
+
+
-HashVarInfo::HashVarInfo(hashtype CHC, vector<pair<hashtype, ExtendedMoveNumber>* > * LFC,
-
+, int NUMSTONES
-  chc = CHC;
+  numStones = NUMSTONES;
-  moveNumber = new ExtendedMoveNumber(*MOVENUMBER);
-  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
@@ -1926 +2008 @@
-
-
-::Algo_hash(int bsize
+_full::Algo_hash_full(int bsize, int MAXNUMSTONES
-  branchpoints = 0;
-
-
-
-
-
-
+
+
+
+
+
+
+
-  // printf("insert %lld\n", hashCode);
-  char* buf = new char[30 + mn.length*2];
@@ -1951 +2034 @@
-    buf[6+2*i] = mn.data[i]%256;
-  }
-
+_full
-  sqlite3_stmt *ppStmt=0;
-  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
-  if (rc != SQLITE_OK || ppStmt==0) return rc;
-currentH
+h
-  if (rc != SQLITE_OK) return rc;
-  rc = sqlite3_bind_int(ppStmt, 2, gid);
@@ -1969 +2052 @@
-}
-
-
+_full
-  db = DB;
-
+_full
-  if (rc != SQLITE_OK) throw DBError();
-
+_full
-  if (rc != SQLITE_OK) throw DBError();
-}
-        
-
+
+
-  gid = game_id;
-  moveNumber = new ExtendedMoveNumber(0);
@@ -1985 +2069 @@
-}
-
-
+_full
-  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
-    Move* continuation = new Move(x,y,'B');
@@ -1994 +2078 @@
-  delete lfc;
-  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
-
-
-
-
+
+
+
+
+
-  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
-    Move* continuation = new Move(x,y,'W');
@@ -2006 +2091 @@
-  delete lfc;
-  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
-
+
+
-}                 
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-  moveNumber->next();
-}
-
-
+_full
-  // (we do not count pass as continuation)
-}
-
-
+_full
-  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
-    Move* continuation = new Move(m);
@@ -2034 +2121 @@
-  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
-  int epsilon = (m.color == 'B' || m.color == 'X' ? 1 : -1);
-
+
+
-
-  if (m.captures) {
@@ -2042 +2130 @@
-      int yy = it->second;
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-  // printf("push %lld\n", currentHashCode);
-}
-
-
+_full
-  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
-    int rc = insert_hash((*it)->first, (*it)->second, 0);
@@ -2063 +2152 @@
-  lfc = branchpoints->top().lfc;
-  moveNumber = branchpoints->top().moveNumber;
+  numStones = branchpoints->top().numStones;
-  // printf("pop %lld\n", currentHashCode);
-  branchpoints->pop();
-}
-
-
+_full
-  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
-    Move* continuation = 0;
@@ -2079 +2169 @@
-}
- 
-
-
-
-
-
+_full
+
+
+
+_full
-  if (pattern.sizeX != boardsize || pattern.sizeY != boardsize)
-    return NOT_HASHABLE;
-  hashtype hashkey = 0;
-
+int ns = 0;
-  for(int i=0; i<boardsize; i++) {
-    for(int j=0; j<boardsize; j++) {
-      char p = pattern.finalPos[i + boardsize*j];
-      if (p == 'x' || p ==  'o' || p == '*') return NOT_HASHABLE;
-
-
-
-
+
+
+
+
+
+
+
+
+
+
-  return hashkey;
-}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-  vpsip res = ((pair<vpsip, int>*)results)->first;
-  int orientation = ((pair<vpsip, int>*)results)->second;
-  if (argc==2 && argv[0]) {
-
-
-
-
-
+
+
-  return 0;
-}
-
-
+
+
-  int hash_result = -1; // -1 = failure; 0 = ok, but have to check w/ Algo_movelist, 1 = ok, produced final result
+  int plS = patternList.size();
+  vpsip results = new vector<HashhitF* >;
+  for(int N=0; N<plS; N++) {
+    hashtype hashCode = compute_hashkey(patternList.data[N]);
+    if (hashCode == NOT_HASHABLE) return -1; // failure
+
+    char sql[100];
+    sprintf(sql, "select gameid,hit from algo_hash_full where hash = %lld", hashCode);
+    // printf("hc %lld, %s\n", hashCode, sql);
+    pair<vpsip, int> rN(results, N);
+    sqlite3_exec(db, sql, insert_result_hf, &rN, 0);
+  }
+  if (options.trustHashFull && patternList.pattern.contList.size()==0) hash_result = 1;
+  else hash_result = 0;
-  if (gl.start_sorted() == 0) {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-    // printf("res-size %d\n", results->size());
-
-
+
-    while (resultIT != results->end()) {
-      int index = (*resultIT)->gameid;
@@ -2204 +2268 @@
-      }
-    }
-
+F
-    delete results;
-    gl.end_sorted();
-  }
-  return 0;
+}
+
+// -----------------------------------------------------------------------------------
+
+Algo_hash::Algo_hash(int bsize, const string& DBNAMEEXT) : Algorithm(bsize) {
+  dbnameext = DBNAMEEXT;
+  maxNumStones = 20; // FIXME
+  hi = 0;
+}
+
+Algo_hash::~Algo_hash() {
+  if (hi) delete hi;
+}
+
+int Algo_hash::insert_hash(hashtype hashCode, int pos) {
+  // printf("insert %lld\n", hashCode);
+  char sql[200];
+  sprintf(sql, "insert into algo_hash%s (hash, gameid, position) values (?,?,?);", dbnameext.c_str());
+  sqlite3_stmt *ppStmt=0;
+  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
+  if (rc != SQLITE_OK || ppStmt==0) return rc;
+  rc = sqlite3_bind_int64(ppStmt, 1, hashCode);
+  if (rc != SQLITE_OK) return rc;
+  rc = sqlite3_bind_int(ppStmt, 2, gid);
+  if (rc != SQLITE_OK) return rc;
+  rc = sqlite3_bind_int(ppStmt, 3, pos);
+  if (rc != SQLITE_OK) return rc;
+  rc = sqlite3_step(ppStmt);
+  if (rc != SQLITE_DONE) return rc;
+  rc = sqlite3_finalize(ppStmt);
+  if (rc != SQLITE_OK) return rc;
+  return 0; // success
+}
+
+void Algo_hash::initialize_process(sqlite3* DB) throw(DBError) {
+  db = DB;
+  char buf[200];
+  sprintf(buf, "create table if not exists algo_hash%s ( hash integer, gameid integer, position integer );", dbnameext.c_str());
+  int rc = sqlite3_exec(db, buf, 0, 0, 0);
+  if (rc != SQLITE_OK) throw DBError();
+  sprintf(buf, "create index if not exists hash_idx%s on algo_hash%s(hash);", dbnameext.c_str(), dbnameext.c_str());
+  rc = sqlite3_exec(db, buf, 0, 0, 0);
+  if (rc != SQLITE_OK) throw DBError();
+}
+        
+void Algo_hash::newgame_process(int game_id) {
+  gid = game_id;
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->initialize();
+}
+
+void Algo_hash::AB_process(int x, int y) {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->addB(x,y);
+}
+
+void Algo_hash::AW_process(int x, int y) {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->addW(x,y);
+}                 
+
+void Algo_hash::AE_process(int x, int y, char removed) {
+  if (removed == 'B') {
+    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) it->removeB(x,y);
+  } else { 
+    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) it->removeW(x,y);
+  }
+}
+
+void Algo_hash::endOfNode_process() {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) {
+    if (it->numStones <= maxNumStones && it->changed) {
+      it->changed = false;
+      pair<hashtype,int> phi = it->cHC();
+      if (insert_hash(phi.first, phi.second) != 0) throw DBError();
+    }
+  }
+}
+
+void Algo_hash::pass_process() {
+  // (we do not count pass as continuation)
+}
+
+void Algo_hash::move_process(Move m) throw(DBError) {
+  if (m.color == 'B') {
+    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+      it->addB(m.x, m.y);
+    if (m.captures) {
+      for(vector<p_cc>::iterator cap_it = m.captures->begin(); cap_it != m.captures->end(); cap_it++) {
+        for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+          it->removeW(cap_it->first, cap_it->second);
+      }
+    }
+  } else {
+    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+      it->addW(m.x, m.y);
+    if (m.captures) {
+      for(vector<p_cc>::iterator cap_it = m.captures->begin(); cap_it != m.captures->end(); cap_it++) {
+        for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+          it->removeB(cap_it->first, cap_it->second);
+      }
+    }
+  }
+}
+
+void Algo_hash::branchpoint_process() {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->bppush();
+}
+
+void Algo_hash::endOfVariation_process() {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->bppop();
+}
+
+void Algo_hash::endgame_process() {
+  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
+    it->finalize();
+}
+ 
+void Algo_hash::finalize_process() {
+}
+
+
+pair<hashtype,int> Algo_hash::compute_hashkey(PatternList& pl, int CS) {
+  return make_pair(NOT_HASHABLE,0);
+}
+
+int insert_result(void *rN, int argc, char **argv, char **azColName) throw (DBError) {
+  vector<HashhitCS* >* results = ((pair<vector<HashhitCS* >*, hashtype>*)rN)->first;
+  hashtype hashCode = ((pair<vector<HashhitCS* >*, hashtype>*)rN)->second;
+
+  if (argc==3 && argv[0] && argv[1] && argv[2]) {
+    // printf("found %s, %lld", argv[2], atoi(argv[2]));
+    ((vector<HashhitCS* >*)results)->push_back(new HashhitCS(atoi(argv[0]), atoi(argv[1]), atoll(argv[2])!=hashCode));
+  } else throw DBError();
+  return 0;
+}
+
+
+int Algo_hash::search(PatternList& patternList, GameList& gl, SearchOptions& options, sqlite3* db) {
+  // return value: -1 = failure; 0 = ok, but have to check w/ Algo_movelist
+
+  vector<HashhitCS* >* results = new vector<HashhitCS* >;
+
+  pair<hashtype, int> hco = compute_hashkey(patternList, 0);
+  hashtype hashCode = hco.first;
+  // printf("HC %lld\n", hashCode);
+  hashtype hashCode2 = hashCode;
+  if (hashCode == NOT_HASHABLE) {
+    delete results;
+    return -1; // failure
+  }
+  int fl = patternList.data[hco.second].flip;
+  int fl2 = fl;
+  char buf[100];
+  sprintf(buf, "select gameid,position,hash from algo_hash%s where hash = %lld", 
+      dbnameext.c_str(), hashCode);
+  string sql = buf;
+
+  bool cs = patternList.data[patternList.size()-1].colorSwitch;
+  if (cs) {
+    pair<hashtype, int> hco = compute_hashkey(patternList, 1);
+    hashCode2 = hco.first;
+    // printf("HC2 %lld\n", hashCode2);
+    if (hashCode == NOT_HASHABLE) {
+      delete results;
+      return -1; // failure
+    }
+    fl2 = patternList.data[hco.second].flip;
+
+    if (hashCode != hashCode2) {
+      sprintf(buf, " or hash = %lld", hashCode2);
+      sql += buf;
+    }
+  }
+  sql += " order by gameid";
+
+  if (gl.start_sorted() == 0) {
+    // query database
+
+    // printf("%s\n", sql);
+    pair<vector<HashhitCS* >*, hashtype> rN(results, hashCode);
+    sqlite3_exec(db, sql.c_str(), insert_result, &rN, 0);
+    // printf("results->size() %d\n", results->size());
+
+    // communicate results of query to database
+    
+    vector<HashhitCS* >::iterator resultIT = results->begin();
+    while (resultIT != results->end()) {
+      // printf("gid %d\n", (*resultIT)->gameid);
+      int index = (*resultIT)->gameid;
+
+      vector<Candidate* >* candidates = new vector<Candidate* >;
+      while ((*resultIT)->gameid == index) {
+        // int pos = (*resultIT)->position % (1<<16);
+        int ori = (*resultIT)->position / (1<<16);
+        // printf("%d %d\n", pos, ori);
+        if (cs && hashCode == hashCode2) { // this is a somewhat pathological case ...
+          int ind = patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)];
+          candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
+          ind = patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)];
+          candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
+        } else {
+          if ((*resultIT)->cs) {
+            // FIXME works only for corner patterns right now!
+            int ind = patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)];
+            // printf("cand cs %d %d %d\n", patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)], patternList.data[ind].left, patternList.data[ind].top);
+            candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
+          } else {
+            int ind = patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)];
+            // printf("cand %d %d %d\n", patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)], patternList.data[ind].left, patternList.data[ind].top);
+            candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
+          }
+        }
+        resultIT++;
+        if (resultIT == results->end()) break;
+      }
+      gl.makeIndexCandidate(index, candidates);
+    }
+    for(vector<HashhitCS* >::iterator it = results->begin(); it != results->end(); it++) delete *it;
+    delete results;
+    gl.end_sorted();
+  } else return -1;
+  return 0;
+}
+
+Algo_hash_corner::Algo_hash_corner(int bsize, int SIZE) : Algo_hash(bsize, "CORNER") {
+  size = SIZE;
+  char buf[5];
+  sprintf(buf, "%d", size);
+  dbnameext += buf;
+  hi = new vector<HashInstance>;
+  hi->push_back(HashInstance(0,0,size,size,boardsize));
+  hi->push_back(HashInstance(0,bsize-size,size,size,boardsize));
+  hi->push_back(HashInstance(bsize-size,0,size,size,boardsize));
+  hi->push_back(HashInstance(bsize-size, bsize-size, size, size,boardsize));
+}
+
+pair<hashtype,int> Algo_hash_corner::compute_hashkey(PatternList& pl, int CS) {
+  if (pl.data[0].sizeX < size || pl.data[0].sizeY < size || pl.data[0].left != pl.data[0].right || pl.data[0].top != pl.data[0].bottom || (pl.data[0].left != 0 && pl.data[0].left != boardsize-size) || (pl.data[0].top != 0 && pl.data[0].top != boardsize-size)) return make_pair(NOT_HASHABLE,0);
+  hashtype hk = NOT_HASHABLE;
+  int f = 0;
+  vector<hashtype> hCodes;
+  for(int pCtr=0; pCtr<pl.size(); pCtr++) {
+    if (CS == pl.data[pCtr].colorSwitch) {
+      hashtype hashkey = 0;
+      int ns = 0;
+
+      Pattern *pattern = & pl.data[pCtr];
+      int offsetX = 0;
+      int offsetY = 0;
+      if (pattern->left > 0) offsetX = boardsize-size-pattern->left; // pattern located on east side of board
+      if (pattern->top > 0) offsetY = boardsize-size-pattern->top;   // ... south ...
+      for(int i=0; i<size; i++) {
+        for(int j=0; j<size; j++) {
+          char p = pattern->finalPos[i+offsetX + pattern->sizeX*(j+offsetY)];
+          if (p == 'x' || p ==  'o' || p == '*') return make_pair(NOT_HASHABLE,0);
+          else if (p == 'X') {
+            hashkey += hashCodes[i+offsetX+pattern->left + boardsize*(j+offsetY+pattern->top)];
+            ns++;
+          } else if (p == 'O') {
+            hashkey -= hashCodes[i+offsetX+pattern->left + boardsize*(j+offsetY+pattern->top)];
+            ns++;
+          }
+        }
+      }
+      if (ns > maxNumStones) return make_pair(NOT_HASHABLE,0);
+
+      // make sure all hash keys are unique
+      for(vector<hashtype>::iterator it = hCodes.begin(); it != hCodes.end(); it++)
+        if (*it == hashkey) return make_pair(NOT_HASHABLE, 0);
+      hCodes.push_back(hashkey);
+
+      if (hk==NOT_HASHABLE || hashkey<hk) {
+        hk = hashkey;
+        f = pCtr;
+      }
+    }
+  }
+  return make_pair(hk, f);
+}
+
+// Algo_hash_side::Algo_hash_side(int bsize, int SIZEX, int SIZEY) : Algo_hash(bsize, "SIDE") {
+//   sizeX = SIZEX;
+//   sizeY = SIZEY;
+//   char buf[10];
+//   sprintf(buf, "%d_%d", sizeX, sizeY);
+//   dbnameext += buf;
+// 
+//   hi = new vector<HashInstance>;
+//   for(int i=1; i<bsize-1-sizeX; i++)
+//     hi->push_back(HashInstance(i,0,sizeX, sizeY,boardsize));
+//   for(int i=1; i<bsize-1-sizeX; i++)
+//     hi->push_back(HashInstance(i,bsize-sizeY,sizeX, sizeY,boardsize));
+//   for(int i=1; i<bsize-1-sizeX; i++)
+//     hi->push_back(HashInstance(0, i, sizeY, sizeX,boardsize));
+//   for(int i=1; i<bsize-1-sizeX; i++)
+//     hi->push_back(HashInstance(bsize-sizeY, i, sizeY, sizeX,boardsize));
+// }
+
+HashInstance::HashInstance(char X, char Y, char SIZEX, char SIZEY, int BOARDSIZE) {
+  boardsize = BOARDSIZE;
+  xx = X;
+  yy = Y;
+  pos = xx + boardsize*yy;
+  sizeX = SIZEX; 
+  sizeY = SIZEY;
+  branchpoints = 0;
+  currentHashCode = 0;
+  numStones = 0;
+  changed = true;
+}
+
+HashInstance::~HashInstance() {
+  finalize();
+}
+
+void HashInstance::finalize() {
+  if (branchpoints) {
+    while (branchpoints->size()) {
+      delete [] branchpoints->top().first;
+      branchpoints->pop();
+    }
+    delete branchpoints;
+    branchpoints = 0;
+  }
+  if (currentHashCode) {
+    delete [] currentHashCode;
+    currentHashCode = 0;
+  }
+}
+
+bool HashInstance::inRelevantRegion(char X, char Y) {
+  if (xx <= X && X < xx+sizeX && yy <= Y && Y < yy+sizeY) return true;
+  return false;
+}
+
+void HashInstance::initialize() {
+  currentHashCode = new hashtype[8]; 
+  for(int i=0; i<8; i++) currentHashCode[i] = 0; // start with empty board
+  numStones = 0;
+  branchpoints = new stack<pair<hashtype*,int> >;
+  changed = true; // do record empty pattern ...
+}
+
+void HashInstance::addB(char x, char y) {
+  if (inRelevantRegion(x,y)) {
+    changed = true;
+    for(int i=0; i<8; i++) {
+      currentHashCode[i] += Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
+    }
+    numStones++;
+  }
+}
+
+void HashInstance::addW(char x, char y) {
+  if (inRelevantRegion(x,y)) {
+    changed = true;
+    for(int i=0; i<8; i++) {
+      currentHashCode[i] -= Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
+    }
+    numStones++;
+  }
+}
+
+void HashInstance::removeB(char x, char y) {
+  if (inRelevantRegion(x,y)) {
+    changed = true;
+    for(int i=0; i<8; i++) {
+      currentHashCode[i] -= Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
+    }
+    numStones++;
+  }
+}
+
+void HashInstance::removeW(char x, char y) {
+  if (inRelevantRegion(x,y)) {
+    changed = true;
+    for(int i=0; i<8; i++) {
+      currentHashCode[i] += Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
+    }
+    numStones++;
+  }
+}
+
+pair<hashtype,int> HashInstance::cHC() {
+  int flip = 0;
+  hashtype minCHC = currentHashCode[0];
+  for(int i=1; i<8; i++) { 
+    if (currentHashCode[i] < minCHC) {
+      minCHC = currentHashCode[i];
+      flip = i;
+    }
+  }
+  return make_pair(minCHC, flip*(1<<16)  + pos);
+}
+
+void HashInstance::bppush() {
+  hashtype* chc = new hashtype[8];
+  for(int i=0; i<8; i++) chc[i] = currentHashCode[i];
+  branchpoints->push(make_pair(chc, numStones));
+}
+
+void HashInstance::bppop() {
+  delete [] currentHashCode;
+  currentHashCode = branchpoints->top().first;
+  numStones = branchpoints->top().second;
+  branchpoints->pop();
-}
-
@@ -2793 +3266 @@
-    algo_ps[algo_movelist] = new Algo_movelist(boardsize);
-  if (algos & ALGO_HASH_FULL) 
-
+
+
+
+
+
-  all = 0;
-  currentList = oldList = 0;
@@ -2826 +3303 @@
-  rc = sqlite3_exec(db, "pragma cache_size = 300000;", 0, 0, 0);
-  if (rc) throw DBError();
+  rc = sqlite3_exec(db, "begin transaction;", 0, 0, 0);
+  if (rc) throw DBError();
-
-  string sql = "select "; // those two we need in any case
@@ -2837 +3316 @@
-    readDBs = 1;
-  } else readDBs = 0;
+  rc = sqlite3_exec(db, "commit;", 0, 0, 0);
+  if (rc) throw DBError();
-
-  sqlite3_close(db);
@@ -3111 +3592 @@
-
-  int hash_result = -1;
+  // FULL BOARD PATTERN?
-  if (pl.pattern.sizeX == 19 && pl.pattern.sizeY == 19 && algo_ps[algo_hash_full]) {
-*)algo_ps[algo_finalpos
+_full*)algo_ps[algo_hash_full
-    if (hash_result == 1) {
-    } else if (hash_result == 0) {
@@ -3118 +3600 @@
-    }
-  }
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-  }
-  sqlite3_close(db);

06/libkombilo/search.h

@@ -35 +35 @@
-#ifdef __BORLANDC__
-typedef __int64 hashtype;
+const hashtype NOT_HASHABLE = 9223372036854775807i64;
-#else
-typedef long long hashtype;
+const hashtype NOT_HASHABLE = 9223372036854775807LL;
-#endif
-
@@ -115 +117 @@
-    static int flipsY(int i, int x, int y, int XX, int YY);
-    static int PatternInvFlip(int i);
+    static int compose_flips(int i, int j); // returns index of flip "first j, then i"
-};
-
@@ -139 +142 @@
-    std::vector<Symmetries> symmetries;
-    Continuation* continuations;
+    int* flipTable;
-    int special;
-
-
+ throw (PatternError)
-    ~PatternList();
-
@@ -318 +322 @@
-};
-
-
-
-
-
+
+
-  public:
-    int gameid;
@@ -328 +330 @@
-    ExtendedMoveNumber* emn;
-
-
-
-
+
+
+
+
+
+
+
+
+
+