Changeset 241

Timestamp:

03/16/07 23:10:00 (1 year ago)

Author:

ug

Message:

Another backup commit of the hash_center branch. The new way of hashing
works for corner patterns now, and support for center patterns should be
very close.

Files:

• 06/libkombilo-branches/hash_center/cpptest.cpp (modified) (5 diffs)
• 06/libkombilo-branches/hash_center/process.py (modified) (4 diffs)
• 06/libkombilo-branches/hash_center/search.cpp (modified) (32 diffs)
• 06/libkombilo-branches/hash_center/search.h (modified) (9 diffs)

06/libkombilo-branches/hash_center/cpptest.cpp

@@ -9 +9 @@
-int main(int argc, char** argv) {
-  // ----------------- parse command line arguments ---------------------------------
-
+ | ALGO_HASH_CENTER
-  bool process = false;
-  for(int i=1; i<argc; i++) {
@@ -29 +29 @@
-    gl.start_processing();
-    directory_iterator end_itr;
-center_hashes/libkombilo
+hash_center
-    // string path = "/home/ug/go/gtl/reviews";
-    string path = "/home/ug/go/gogod06/2000";
@@ -70 +70 @@
-  // For example, CORNER_NW_PATTERN corresponds to (0,0,0,0)
-  // Pattern p(2,3,4,6, 19, 3, 3, ".X.XXXXOX", vector<MoveNC>()); 
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-  // 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'");
-
+// 
-  // vector<MoveNC> contList;
-  // contList.push_back(MoveNC(6,15,'X'));
@@ -88 +105 @@
-  // -------------------- set up search options ----------------------------------
-  SearchOptions so;
+  so.algos = algos;
+//   so.fixedColor = true;
-  // so.trustHashFull = true;
-  // SearchOptions so(0,0,50); // use move limit
@@ -94 +113 @@
-  
-  // -------------------- do pattern search --------------------------------------
-// 
+
-
-  // ------------------- print some information about current list of games ------------
-// 
+
-  // vector<string> res = gl.currentEntriesAsStrings();
-  // for(vector<string>::iterator it = res.begin(); it != res.end(); it++)
-  //   printf("%s\n", it->c_str());
-  //
+//  
-
-  // ------------------- print some statistics ------------------------------------------
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
+
+
+
+
+
+
+
+
+
+
+
+
-
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
-// 
+
+
+
+
+
+
+
+
+
+
+
-
-  // ------------------- check for duplicates ---------------------------------

06/libkombilo-branches/hash_center/process.py

@@ -11 +11 @@
-try: 
-    os.system('rm t1.db*')
+    pass
-except: 
-    pass
@@ -24 +25 @@
-        # pop.rootNodeTags = 'PW,PB,RE,DT'
-        pop.sgfInDB = False
-8
+15
-    except DBError:
-        print 'Database error'
@@ -50 +51 @@
-
-# filelist = glob.glob('./*.sgf')
-# 
-
+
+# 
-# filelist = glob.glob('/home/ug/go/KGS2005/*.sgf')
-
@@ -57 +58 @@
-process(filelist)
-
-
+# 
-
-
-
+# 
+# 
-
-
-
+# 
+# 
-
-
-
+# 
+# 
-
-

06/libkombilo-branches/hash_center/search.cpp

@@ -37 +37 @@
-using std::make_pair;
-using std::stack;
+using std::set;
-
-#if defined(_MSC_VER)
@@ -300 +301 @@
-Pattern::Pattern(int le, int ri, int to, int bo, int BOARDSIZE, int sX, int sY, char* iPos, const vector<MoveNC>& CONTLIST, char* CONTLABELS) throw(PatternError) {
-  // check whether anchor rectangle is valid
-
+
+
-
-  flip = 0;
@@ -466 +468 @@
-  }
-
- newSizeX, newSizeY,
-
+
+                       newSizeX, newSizeY, 
-
-  pNew->flip = f;
-  if (CS) pNew->colorSwitch = 1;
+  else pNew->colorSwitch = 0;
-  delete [] newInitialPos;
-  return *pNew; 
@@ -520 +523 @@
-
-int Pattern::flipsX(int i, int x, int y, int XX, int YY) {
-
-
-
-
-
-
-
-
+         // id
+      // mirror vertically
+         // mirror horizontally
+      // rotate by 180 deg
+         // mirror wrt main diagonal (\)
+      // rotate by -90 deg
+         // rotate by 90 deg
+      // mirror wrt second diagonal (/)
-  return -1;
-}
@@ -582 +585 @@
-
-void PatternList::patternList() {
-
+
-  vector<Pattern> lCS;
-  vector<pair<int,int> > sy;
-  int boardsize = pattern.boardsize;
-
-  for(int f = 0; f < 8; f++) {
@@ -600 +602 @@
-    }
-    if (foundNewPattern) {
+      printf("new p: %s\n", pNew.printPattern().c_str());
-      flipTable[f] = data.size();
-      data.push_back(pNew);
@@ -607 +610 @@
-
-    if (nextMove || !fixedColor) { // need to consider CS'ed patterns
-1
+true
-
-      if (!fixedColor) { 
@@ -2201 +2204 @@
-}
-
+HashhitCS::HashhitCS(int GAMEID, int POS, int ORI, bool CS) {
+  gameid = GAMEID;
+  position = POS + (ORI << 16);
+  cs = CS;
+}
+
-HashhitCS::HashhitCS(int GAMEID, int POSITION, bool CS) {
-  gameid = GAMEID;
@@ -2207 +2216 @@
-}
-
+bool HashhitCS::operator==(const HashhitCS& hcs) {
+  if (gameid != hcs.gameid) return false;
+  if (position != hcs.position) return false;
+  if (cs != hcs.cs) return false;
+  return true;
+}
+
+int HashhitCS::get_pos() {
+  return position % (1<<16);
+}
+
+int HashhitCS::get_ori() {
+  return position / (1<<16);
+}
+
-bool cmp_HashhitCS(const HashhitCS* a, const HashhitCS* b) {
+  if (a->gameid == b->gameid) {
+    if (a->position == b->position) {
+      if (!a->cs && b->cs) return true;
+      else return false;
+    } else return a->position < b->position;
+  }
-  return a->gameid < b->gameid;
-}
@@ -2535 +2565 @@
-// -----------------------------------------------------------------------------------
-
-
+
+
+
+
+
+
+
+
+
+
+
-  sql = SQL;
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-  flip0 = FLIP0;
-  flip1 = FLIP1;
@@ -2553 +2603 @@
-}
-
-
-
+
+
+
+
+
+
+
+
+
+
-  hashCode = HASHCODE;
-
-
+// 
+// 
-  index = INDEX;
-}
@@ -2563 +2621 @@
-CompleteHashKey::CompleteHashKey() {
-  hashCode = NOT_HASHABLE;
-
-
+// 
+// 
-  index = -1;
-}
-
+HashCTREntry::HashCTREntry() {
+}
+
+HashCTREntry::HashCTREntry(unsigned char* c, int l, bool cs) {
+  // format of c: 
+  //     4 bytes: game_id, 
+  //     2 bytes: position,
+  //     1 byte: orientation
+  add(c, l, cs, false);
+}
+
+HashCTREntry::~HashCTREntry() {
+  for(vector<HashhitCS* >::iterator it = data.begin(); it != data.end(); it++)
+    delete *it;
+}
+
+void HashCTREntry::add(unsigned char* c, int l, bool cs, bool do_sort) {
+  for(int i = 0; i < l/7; i++) {
+    int gameid = *(int*)(c+7*i);
+    int ori = c[7*i+6];
+    int pos = (c[7*i+4] << 8) + c[7*i+5];
+    data.push_back(new HashhitCS(gameid, pos, ori, cs));
+//     printf("HashCTREntry::add 0 gid: %d, ori: %d, pos: %d, l: %d\n", gameid, ori, pos, data.size());
+  }
+  if (do_sort) sort(data.begin(), data.end(), cmp_HashhitCS);
+}
+
+void HashCTREntry::add(int gameid, int pos, char ori, bool cs) {
+  data.push_back(new HashhitCS(gameid, pos, ori, cs));
+//   printf("HashCTREntry::add 1 gid: %d, ori: %d, pos: %d,l: %d\n", gameid, ori, pos, data.size());
+  if (data.size() > 1) sort(data.begin(), data.end(), cmp_HashhitCS);
+}
+
+void HashCTREntry::add(int gameid, int position, bool cs) {
+  data.push_back(new HashhitCS(gameid, position, cs));
+//   printf("HashCTREntry::add 2 gid: %d, position: %d, l:%d\n", gameid, position, data.size());
+  if (data.size() > 1) sort(data.begin(), data.end(), cmp_HashhitCS);
+}
+
+char* HashCTREntry::to_charp() {
+//   printf("to charp\n");
+  char* c = new char[7*data.size()];
+  unsigned int i=0;
+  for(vector<HashhitCS* >::iterator it = data.begin(); it != data.end(); it++) {
+//     printf("loop\n");
+    *(int*)(c+7*i) = (*it)->gameid;
+    c[7*i+4] = (*it)->get_pos() / 256;
+    c[7*i+5] = (*it)->get_pos() % 256;
+    c[7*i+6] = (*it)->get_ori();
+    i++;
+  }
+  return c;
+}
+
+int HashCTREntry::get_length() {
+//   printf("get length %d\n", data.size());
+  return 7*data.size();
+}
-
-Algo_hash::Algo_hash(int bsize, const string& DBNAMEEXT, int MAXNUMSTONES) : Algorithm(bsize) {
@@ -2585 +2701 @@
-
-int Algo_hash::insert_hash(hashtype hashCode, int pos) {
-
+
+
-  return 0;
-}
@@ -2591 +2708 @@
-int Algo_hash::insert_all_hashes() {
-  // printf("insert all hashes %d\n", hash_vector.size());
+  int rc;
-  char sql[200];
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-  return 0; // success
-}
@@ -2618 +2800 @@
-  db = DB;
-  char buf[200];
-gameid integer, position integer
+data blob
-  int rc = sqlite3_exec(db, buf, 0, 0, 0);
-  if (rc != SQLITE_OK) throw DBError();
@@ -2624 +2806 @@
-  rc = sqlite3_exec(db, buf, 0, 0, 0);
-  if (rc != SQLITE_OK) throw DBError();
+
+  updStmt = 0;
+  insStmt = 0;
+  selStmt = 0;
-  // printf("leave algo_hash::initialize_processing\n");
-}
@@ -2709 +2895 @@
- 
-void Algo_hash::finalize_process() {
+  int rc;
+  rc = sqlite3_finalize(insStmt);
+  if (rc != SQLITE_OK) printf("error 14: %d\n", rc); // return rc;
+  // else printf("ok 14\n");
+  rc = sqlite3_finalize(updStmt);
+  if (rc != SQLITE_OK) printf("error 15: %d\n", rc); // return rc;
+  // else printf("ok 15\n");
+  rc = sqlite3_finalize(selStmt);
+  if (rc != SQLITE_OK) printf("error 13: %d\n", rc); // throw DBError();
+  insStmt = 0;
+  updStmt = 0;
+  selStmt = 0;
-}
-
-CompleteHashKey Algo_hash::compute_hashkey(PatternList& pl, int CS) {
-  return CompleteHashKey();
-}
-
-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]));
-#if (defined(__BORLANDC__) || defined(_MSC_VER))
-    ((vector<HashhitCS* >*)results)->push_back(new HashhitCS(atoi(argv[0]), atoi(argv[1]), _atoi64(argv[2])!=hashCode));
-#else
-    ((vector<HashhitCS* >*)results)->push_back(new HashhitCS(atoi(argv[0]), atoi(argv[1]), atoll(argv[2])!=hashCode));
-#endif
-  } else throw DBError();
-  return 0;
-}
-
@@ -2735 +2918 @@
-  // (this is necessary since the subpattern used for the hashing may not be
-  // located at the top left corner of the pattern)
-"", 0, 0, 0, 0, 0, 0, 0
+
-}
-
-vector<int>* flip_list(int fl, int flip, int* pattern_ft, int* subpattern_ft) {
+  // meaning of fl:
+  //   fl is the flip which maps the subpattern of the original search pattern to
+  //   the pattern which has hash code hashCode: hash(fl*subpattern) == hashCode.
+  //
+  // meaning of flip (this comes from the hash db):
+  //   Let (P, pos) be the pattern (and position) which has the hashCode we have searched for.
+  //   We assume that P is the unique pattern among all g(P) (g in the
+  //   symmetry group (modulo the stabilizer of P)) with this hashCode.
+  //   In the concerning game, since the game is in the list of results, one of the
+  //   g(P, pos) occurs, and specifically, g == flip^{-1}. 
+  //
+  // so we find fl * i * subpattern == P  (for all i in the stabilizer of subpattern),
+  // and hence flip^{-1} * fl * i * subpattern == flip^{-1} P is the pattern which
+  // occurs (probably) in the game, at position pos.
+  //
+  // in the candidates list, entries are of the form (pp, index) - this means that a
+  // the pattern patternList.data[index] might occur at position pp. So for pp we use flip^{-1}*pos, 
+  // adjusted to take into account that we deal with a subpattern instead of the complete search pattern
+  // (see Algo_hash::search). As index we use all those such that the corresponding flip has
+  // the form flip^{-1} * fl * i  (i in Stab(subpattern)/Stab(pattern)).
+
-  vector<int>* result = new vector<int>;
-  bool used[8];
+  printf("pft "); for(int i=0; i<8; i++) printf("%d, ", pattern_ft[i]); printf("\n");
+  printf("sft ");
+  for(int i=0; i<8; i++)
+    printf("%d, ", subpattern_ft[i]);
+  printf("\n");
-  { for(int i=0; i<8; i++) used[i] = false;
-  }
-  { for(int i=0; i<8; i++) {
-
-
-
-
+
+
+
+
+
-    }
-  }
@@ -2755 +2965 @@
-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
-
-
+
-
-  HashQuery query = searchQuery(patternList);
@@ -2766 +2975 @@
-  if (gl.start_sorted() == 0) {
-    // query database
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-    // communicate results of query to database
-    //
-    // FIXME explain how we get from a hit for the sql query to a candidates entry!
-
-
+data.
+data.
-      // printf("gid %d\n", (*resultIT)->gameid);
-      int index = (*resultIT)->gameid;
@@ -2779 +2999 @@
-      vector<Candidate* >* candidates = new vector<Candidate* >;
-      while ((*resultIT)->gameid == index) {
-position % (1<<16
-position / (1<<16
+get_pos(
+get_ori(
-        // printf("%d %d\n", pos, ori);
-
@@ -2786 +3006 @@
-        int* subpattern_flipTable;
-        int fl;
-
+
+
+
+
-        if ((*resultIT)->cs) {
-           subpattern_flipTable = query.pl1->flipTable;
-           fl = query.flip1;
-
+
+
-        } else {
-          subpattern_flipTable = query.pl0->flipTable;
-          fl = query.flip0;
-
+
+
-        }
-        vector<int>* f_list = flip_list(fl, ori, pattern_flipTable, subpattern_flipTable);
-        for(vector<int>::iterator flip = f_list->begin(); flip != f_list->end(); flip++) {
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-        }
-        delete f_list;
-        resultIT++;
-
+data.
-      }
-      gl.makeIndexCandidate(index, candidates);
-    }
-    for(vector<HashhitCS* >::iterator it = results->begin(); it != results->end(); it++) delete *it;
-    delete results;
-    gl.end_sorted();
@@ -2834 +3069 @@
-
-CompleteHashKey Algo_hash_corner::compute_hashkey(PatternList& pl, int CS) {
-
+
+
+
+
+
-  hashtype hk = NOT_HASHABLE;
-  int f = 0;
-  int oX = 0;
-  int oY = 0;
-  vector<hashtype> hCodes;
+//   printf("before loop %d %d\n", pl.size(), CS);
-  for(int pCtr=0; pCtr<pl.size(); pCtr++) {
-    if (CS == pl.data[pCtr].colorSwitch) {
+//       printf("loop %d\n", pCtr);
-      hashtype hashkey = 0;
-      int ns = 0;
-
-      Pattern *pattern = & pl.data[pCtr];
-
-
-
-
+
-      for(int i=0; i<size; i++) {
-        for(int j=0; j<size; j++) {
-
-
+
+
+
+
+
-          else if (p == 'X') {
-offsetX+pattern->left + boardsize*(j+offsetY
+pattern->left + boardsize*(j
-            ns++;
-          } else if (p == 'O') {
-offsetX+pattern->left + boardsize*(j+offsetY
+pattern->left + boardsize*(j
-            ns++;
-          }
-        }
-      }
-
+
+
+
+
-
-      // make sure all hash keys are unique
-      for(vector<hashtype>::iterator it = hCodes.begin(); it != hCodes.end(); it++)
-
+
+
+
+
+
-      hCodes.push_back(hashkey);
-
-      if (hk==NOT_HASHABLE || hashkey<hk) {
+//         printf("found hk\n");
-        hk = hashkey;
-        f = pCtr;
-        oX = offsetX;
-        oY = offsetY;
-      }
-    }
-  }
-oX, oY, 
+
-}
-
-HashQuery Algo_hash_corner::searchQuery(PatternList& patternList) {
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-  char buf[100];
-gameid,position,hash from algo_hash_%d_%s where hash = %lld", 
-, chk.hashCode
+data,hash from algo_hash_%d_%s where hash ",
+
-  string sql = buf;
-
-
-
-
+
+
-  int fl2 = fl;
-  Pattern* p1 = 0;
-  int off1 = 0;
-  if (patternList.data[patternList.size()-1].colorSwitch) {
-
-
+
-    // printf("HC2 %lld\n", hashCode2);
-
-
-
-
-
+
+
+
+
+
+
+
+
-      sql += buf;
-
-
-
-
+
+
+
+
+
+
+
+
+
+
-}
-
@@ -2968 +3240 @@
-
-void Algo_hash_center::initialize_process(sqlite3* DB) throw(DBError) {
-
-
-
-
-
-
-
-
-
-
+
-  hi = new vector<HashInstance* >;
-  for(int i=0; i<boardsize-3; i++)          // FIXME: boundaries
-    for(int j=0; j<boardsize-3; j++)
-      hi->push_back(new HashInstanceCTR(i, j, 4, 4, boardsize));
-}
-
-void Algo_hash_center::finalize_process() {
-  char buf[200];
-  sprintf(buf, "create index if not exists hash_idx_%d_%s on algo_hash_%d_%s(hash);", boardsize, dbnameext.c_str(), boardsize, dbnameext.c_str());
-  int rc = sqlite3_exec(db, buf, 0, 0, 0);
-  if (rc != SQLITE_OK) throw DBError();
-}
-
@@ -3005 +3261 @@
-          currentHashCode[f] |= 1 << p; // set to 01 = black
-        else if (c == 'W')
-p+1
+(p+1)
-        else if (c != '.') return NOT_HASHABLE;
-      }
@@ -3042 +3298 @@
-
-HashQuery Algo_hash_center::searchQuery(PatternList& patternList) {
-"",0,0,0,0,0,0,0
+
-}
-
@@ -3202 +3458 @@
-      int p = 2*(4*x1+y1);
-      currentHashCode[i] ^= ((currentHashCode[i] >> p)%4) << p; // set to 00
-p+1
+(p+1)
-    }
-  }
@@ -4165 +4421 @@
-
-void GameList::makeCurrentCandidate(vector<Candidate* > * candidates) {
+  printf("GameList::makeCurrentCandidate\n");
-  GameListEntry* gle = (*all)[(*oldList)[current].second];
-  if (gle->candidates) delete gle->candidates;
-  gle->candidates = candidates;
+  for(vector<Candidate* >::iterator it = candidates->begin(); it != candidates->end(); it++) {
+    printf("x: %d, y: %d, flip: %d\n", (*it)->x, (*it)->y, (*it)->orientation);
+  }
-  currentList->push_back((*oldList)[current]);
-}
@@ -4568 +4828 @@
-  sizeX = pattern.sizeX; // need this in lookupLabel
-  PatternList pl(pattern, searchOptions->fixedColor, searchOptions->nextMove);
+  printf("created pl, size: %d\n", pl.size());
+  // for(int i=0; i< pl.size(); i++) printf("%s\n", pl.data[i].printPattern().c_str());
-
-  vector<int>::iterator it = boardsizes.begin();
@@ -4611 +4873 @@
-      if (hash_result == 0) {
-        if (searchOptions->algos & ALGO_MOVELIST && algo_ps[algo_movelist+20*bs_index])
+          printf("movelist 0\n");
-          algo_ps[algo_movelist+20*bs_index]->search(pl, *this, *searchOptions);
-      }
@@ -4618 +4881 @@
-      if (searchOptions->algos & ALGO_FINALPOS && algo_ps[algo_finalpos+20*bs_index])
-        algo_ps[algo_finalpos+20*bs_index]->search(pl, *this, *searchOptions);
+      printf("movelist 1\n");
-      if (searchOptions->algos & ALGO_MOVELIST && algo_ps[algo_movelist+20*bs_index])
-        algo_ps[algo_movelist+20*bs_index]->search(pl, *this, *searchOptions);
@@ -4811 +5075 @@
-      int rc = sqlite3_exec(algo_db2, "commit", 0, 0, 0);
-      if (rc) {
-db
-db
+algo_db2
+algo_db2
-        throw DBError();
-      }
-      rc = sqlite3_exec(algo_db2, "begin transaction", 0, 0, 0);
-      if (rc) {
-db
-db
+algo_db2
+algo_db2
-        throw DBError();
-      }

06/libkombilo-branches/hash_center/search.h

@@ -28 +28 @@
-#include <utility>
-#include <stack>