Changeset 238

Timestamp:

03/06/07 23:08:07 (1 year ago)

Author:

ug

Message:

Backup of current state (does compile, but hashing is not functional ATM).

Files:

• 06/libkombilo-branches/hash_center/Makefile (modified) (1 diff)
• 06/libkombilo-branches/hash_center/cpptest.cpp (modified) (1 diff)
• 06/libkombilo-branches/hash_center/process.py (modified) (1 diff)
• 06/libkombilo-branches/hash_center/search.cpp (modified) (37 diffs)
• 06/libkombilo-branches/hash_center/search.h (modified) (11 diffs)

06/libkombilo-branches/hash_center/Makefile

@@ -5 +5 @@
-        g++ -c cpptest.cpp
-
-
+ search.h abstractboard.h sgfparser.h
-        g++ -c search.cpp
-
-
+ sgfparser.h
-        g++ -c sgfparser.cpp
-
-
+ abstractboard.h
-        g++ -c abstractboard.cpp
-

06/libkombilo-branches/hash_center/cpptest.cpp

@@ -19 +19 @@
-  // ----------------- set up processing options -----------------------------------
-  ProcessOptions* p_op = new ProcessOptions;
-
+FULL | ALGO_HASH_CORNER | ALGO_HASH_
-
-  // ----------------- create GameList instance -----------------------------------

06/libkombilo-branches/hash_center/process.py

@@ -21 +21 @@
-    try:
-        pop = ProcessOptions()
-
+FULL | ALGO_HASH_CORNER | ALGO_HASH_
-        # pop.rootNodeTags = 'PW,PB,RE,DT'
-        pop.sgfInDB = False
-100
+8
-    except DBError:
-        print 'Database error'

06/libkombilo-branches/hash_center/search.cpp

@@ -145 +145 @@
-
-
-
-// ----------- class Pattern -----------------------------------------------
+
+char invertColor(char co) {
+  if (co == 'X') return 'O';
+  if (co == 'x') return 'o';
+
+  if (co == 'O') return 'X';
+  if (co == 'o') return 'x';
+
+  return co;
+}
-
-int Pattern::operator==(const Pattern& p) {
@@ -158 +167 @@
-}
-
-
-char Pattern::BW2XO(char c) {
-  if (c == 'B') return 'X';
@@ -173 +181 @@
-}
- 
-
-Pattern::Pattern() {
-  initialPos = 0;
@@ -184 +191 @@
-  contLabels = 0;
-}
-
-
-Pattern::Pattern(int type, int BOARDSIZE, int sX, int sY, char* iPos, char* CONTLABELS) {
@@ -238 +244 @@
-}
-
-
-
+
-  flip = 0;
-  colorSwitch = 0;
@@ -293 +298 @@
-}
-
-
-
+
-  // check whether anchor rectangle is valid
-  if (le < 0 || ri+sX > BOARDSIZE || to < 0 || bo+sY > BOARDSIZE || ri < le || bo < to) throw PatternError();
@@ -383 +387 @@
-}
-
-
-Pattern& Pattern::copy(const Pattern& p) {
-  if (&p != this) {
@@ -413 +416 @@
-}
-
+Pattern& Pattern::apply_flip(int f, bool CS) {
+  int newSizeX = max(Pattern::flipsX(f,0,0,sizeX,sizeY),
+      Pattern::flipsX(f,sizeX,sizeY,sizeX,sizeY));
+  int newSizeY = max(Pattern::flipsY(f,0,0,sizeX,sizeY),
+      Pattern::flipsY(f,sizeX,sizeY,sizeX,sizeY));
+
+  int newLeft = min(Pattern::flipsX(f,left,top,boardsize-1,boardsize-1),
+      Pattern::flipsX(f,right+sizeX-1,bottom+sizeY-1,
+        boardsize-1,boardsize-1));
+  int newRight = max(Pattern::flipsX(f,left,top,boardsize-1,boardsize-1),
+      Pattern::flipsX(f,right+sizeX-1,bottom+sizeY-1,
+        boardsize-1,boardsize-1)) - (newSizeX-1);
+  int newTop = min(Pattern::flipsY(f,left,top,boardsize-1,boardsize-1),
+      Pattern::flipsY(f,right+sizeX-1,bottom+sizeY-1,
+        boardsize-1,boardsize-1));
+  int newBottom = max(Pattern::flipsY(f,left,top,boardsize-1,boardsize-1),
+      Pattern::flipsY(f,right+sizeX-1,bottom+sizeY-1,
+        boardsize-1,boardsize-1)) - (newSizeY - 1);
+
+  // printf("%d, %d, %d, %d, %d, %d, %d\n", f, newSizeX, newSizeY, newLeft, newRight, newTop, newBottom);
+  char* newInitialPos = new char[sizeX*sizeY];
+  int i=0;
+  for(i=0; i<sizeX; i++) {
+    for(int j=0; j<sizeY; j++) {
+      if (!CS) 
+        newInitialPos[Pattern::flipsX(f,i,j,sizeX-1,sizeY-1) + \
+          newSizeX*Pattern::flipsY(f,i,j,sizeX-1,sizeY-1)] = getInitial(i, j);
+      else
+        newInitialPos[Pattern::flipsX(f,i,j,sizeX-1,sizeY-1) + \
+          newSizeX*Pattern::flipsY(f,i,j,sizeX-1,sizeY-1)] =
+          invertColor(getInitial(i, j));
+    }
+  }
+
+  vector<MoveNC> newContList;
+  for(i=0; (unsigned int)i<contList.size(); i++) {
+    if (!CS)
+      newContList.push_back(MoveNC(Pattern::flipsX(f, contList[i].x, contList[i].y, 
+              sizeX-1,sizeY-1),
+            Pattern::flipsY(f, contList[i].x, contList[i].y,
+              sizeX-1,sizeY-1),
+            contList[i].color));
+    else
+      newContList.push_back(MoveNC(Pattern::flipsX(f, contList[i].x, contList[i].y, 
+              sizeX-1,sizeY-1),
+            Pattern::flipsY(f, contList[i].x, contList[i].y,
+              sizeX-1,sizeY-1),
+            invertColor(contList[i].color)));
+  }
+
+  Pattern* pNew =new Pattern(newLeft, newRight, newTop, newBottom, boardsize, newSizeX, newSizeY,
+      newInitialPos, newContList);
+
+  pNew->flip = f;
+  if (CS) pNew->colorSwitch = 1;
+  delete [] newInitialPos;
+  return *pNew; 
+}
+
+Pattern& Pattern::subpattern(int offsetX, int offsetY, int SIZEX, int SIZEY) {
+  int newLeft = left + offsetX;
+  int newRight = right + offsetX;
+  int newTop = top + offsetY;
+  int newBottom = bottom + offsetY;
+
+  char* newInitialPos = new char[SIZEX*SIZEY];
+  int i=0;
+  for(i=0; i<SIZEX; i++) {
+    for(int j=0; j<SIZEY; j++) {
+      newInitialPos[i + SIZEX*j] = getInitial(i+offsetX, j+offsetY);
+    }
+  }
+
+  vector<MoveNC> newContList;
+  for(i=0; (unsigned int)i<contList.size(); i++) {
+    newContList.push_back(MoveNC(contList[i].x-offsetX, contList[i].y-offsetY, contList[i].color));
+  }
+
+  Pattern* pNew =new Pattern(newLeft, newRight, newTop, newBottom, boardsize, SIZEX, SIZEY,
+      newInitialPos, newContList);
+
+  pNew->flip = flip;
+  pNew->colorSwitch = colorSwitch;
+  delete [] newInitialPos;
+  return *pNew; 
+}
+
-string Pattern::printPattern() {
-  string result;
@@ -428 +518 @@
-  return result;
-}
-
-
-int Pattern::flipsX(int i, int x, int y, int XX, int YY) {
@@ -454 +543 @@
-}
-
-
-int Pattern::PatternInvFlip(int i) {
-  if (i == 5) return 6;
@@ -475 +563 @@
-}
-
+
-PatternList::PatternList(Pattern& p, int fColor, int nMove) throw(PatternError) {
-.copy(p)
+ = p
-  fixedColor = fColor;
-  nextMove = nMove;
@@ -492 +581 @@
-}
-
-char PatternList::invertColor(char co) {
-  if (co == 'X') return 'O';
-  if (co == 'x') return 'o';
-
-  if (co == 'O') return 'X';
-  if (co == 'o') return 'x';
-
-  return co;
-}
-        
-void PatternList::patternList() {
-        
@@ -509 +588 @@
-
-  for(int f = 0; f < 8; f++) {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-    vector<Pattern>::iterator it;
@@ -570 +606 @@
-    if (pNew == pattern) sy.push_back(pair<int,int>(f,0));
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
-        bool foundNewPattern = true;
-        int lCS_ctr = 0;
@@ -621 +635 @@
-  }
-
+  // add the new CS'ed patterns to data, and update flipTable
-  int lCS_ctr = 0;
-  for(vector<Pattern>::iterator it = lCS.begin(); it != lCS.end(); it++) {
@@ -639 +654 @@
-  }
-
+  // compute the "symmetries"
-  Symmetries symm(pattern.sizeX, pattern.sizeY);
-  for(int i=0; i<symm.sizeX; i++)
@@ -703 +719 @@
-}
-
-
-Pattern PatternList::get(int i) {
-  return data[i];
-}
-
-
-int PatternList::size() {
-  return data.size();
-}
-
-
-char* PatternList::updateContinuations(int index, int x, int y, char co, bool tenuki, char winner) {
@@ -762 +775 @@
-}
-
-
-char* PatternList::sortContinuations() {
-  char* labels = new char[pattern.sizeX*pattern.sizeY+1];
@@ -805 +817 @@
-  return labels;
-}
+
-
-DBError::DBError() {
@@ -861 +874 @@
-void Algorithm::finalize_process() {}
-int Algorithm::readDB(sqlite3* DB) { return 0; }
+
-int Algorithm::search(PatternList& patternList, GameList& gl, SearchOptions& options) { 
-  return -1; 
-}
+
-
-Algo_signature::Algo_signature(int bsize) : Algorithm(bsize) {
@@ -1272 +1287 @@
-}
-        
-
-void Algo_movelist::AW_process(int x, int y) {
-  movelist.push_back((char)x);
-  movelist.push_back((char)(y | WHITE));
-}
-
-
-void Algo_movelist::AE_process(int x, int y, char removed) {
@@ -2093 +2106 @@
-}
-
-
-typedef vector<HashhitF* >* vpsip;
-
-
-
-
+
-  chc = CHC;
-  numStones = NUMSTONES;
@@ -2279 +2289 @@
-}
-
-
-hashtype Algo_hash_full::compute_hashkey(Pattern& pattern) {
-  if (pattern.sizeX != boardsize || pattern.sizeY != boardsize)
@@ -2310 +2319 @@
-  return 0;
-}
-
-
-int Algo_hash_full::search(PatternList& patternList, GameList& gl, SearchOptions& options, sqlite3* db) {
@@ -2409 +2417 @@
-// -----------------------------------------------------------------------------------
-
+HashQuery::HashQuery(std::string SQL, Pattern* p0, int OFF0, int FLIP0, hashtype HASHCODE0, Pattern* p1, int OFF1, int FLIP1) {
+  sql = SQL;
+  if (p0) pl0 = new PatternList(*p0,1,0);
+  else pl0 = 0;
+  if (p1) pl1 = new PatternList(*p1,1,0);
+  else pl1 = 0;
+  offset0 = OFF0;
+  offset1 = OFF1;
+  flip0 = FLIP0;
+  flip1 = FLIP1;
+  hashCode0 = HASHCODE0;
+}
+
+HashQuery::~HashQuery() {
+  if (pl0) delete pl0;
+  if (pl1) delete pl1;
+}
+
+
+CompleteHashKey::CompleteHashKey(hashtype HASHCODE, int OFFSETX, int OFFSETY, int INDEX) {
+  hashCode = HASHCODE;
+  offsetX = OFFSETX;
+  offsetY = OFFSETY;
+  index = INDEX;
+}
+
+CompleteHashKey::CompleteHashKey() {
+  hashCode = NOT_HASHABLE;
+  offsetX = 0;
+  offsetY = 0;
+  index = -1;
+}
+
+
-Algo_hash::Algo_hash(int bsize, const string& DBNAMEEXT, int MAXNUMSTONES) : Algorithm(bsize) {
-  dbnameext = DBNAMEEXT;
@@ -2535 +2577 @@
-}
-
-
-
-
+
+
-}
-
@@ -2555 +2596 @@
-}
-
+HashQuery Algo_hash::searchQuery(PatternList& patternList) {
+  // returns the sql query to be used in the search method,
+  // and the offset that has to be added to the positions stored in the db
+  // (this is necessary since the subpattern used for the hashing may not be
+  // located at the top left corner of the pattern)
+  return HashQuery("", 0, 0, 0, 0, 0, 0, 0);
+}
+
+vector<int>* flip_list(int fl, int flip, int* pattern_ft, int* subpattern_ft) {
+  vector<int>* result = new vector<int>;
+  bool used[8];
+  { for(int i=0; i<8; i++) used[i] = false;
+  }
+  { for(int i=0; i<8; i++) {
+      if (subpattern_ft[i] || used[i]) continue;
+      for(int j=1; j<8; j++)
+        if (pattern_ft[j] == 0) used[Pattern::compose_flips(i,j)] = true;
+      result->push_back(Pattern::compose_flips(Pattern::PatternInvFlip(fl), Pattern::compose_flips(flip, i)));
+    }
+  }
+  return result;
+}
-
-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* >;
-
-
-
-
-
-
+
+
-    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_%d_%s where hash = %lld", 
-      boardsize, 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
-
-
-
-
-
+
+
-
-    // communicate results of query to database
-
+
+
-    vector<HashhitCS* >::iterator resultIT = results->begin();
-    while (resultIT != results->end()) {
@@ -2611 +2645 @@
-      vector<Candidate* >* candidates = new vector<Candidate* >;
-      while ((*resultIT)->gameid == index) {
-// 
+
-        int ori = (*resultIT)->position / (1<<16);
-        // printf("%d %d\n", pos, ori);
-
-
-
-
-
+
+
+
+
+
+
+
+
+
-        } else {
-
-
-
-
-
-
-
-
-
-
+
+
+
-        }
+        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++) {
+          // position = pos - flip(p.offset)
+          int pos_left = 0;
+          int pos_top = 0;
+
+          candidates->push_back(new Candidate(pos_left, pos_top, *flip));
+        }
+        delete f_list;
-        resultIT++;
-        if (resultIT == results->end()) break;
@@ -2648 +2688 @@
-  sprintf(buf, "%d", size);
-  dbnameext += buf;
+}
+
+void Algo_hash_corner::initialize_process(sqlite3* DB) throw(DBError) {
+  Algo_hash::initialize_process(DB);
-  hi = new vector<HashInstance* >;
-  hi->push_back(new HashInstanceCO(0,0,size,size,boardsize));
-
-
-size-size, b
-
-
-pair<hashtype,int>
-make_pair(NOT_HASHABLE,0
+oard
+oard
+oardsize-size, board
+
+
+CompleteHashKey
+CompleteHashKey(
-  hashtype hk = NOT_HASHABLE;
-  int f = 0;
+  int oX = 0;
+  int oY = 0;
-  vector<hashtype> hCodes;
-  for(int pCtr=0; pCtr<pl.size(); pCtr++) {
@@ -2673 +2719 @@
-        for(int j=0; j<size; j++) {
-          char p = pattern->finalPos[i+offsetX + pattern->sizeX*(j+offsetY)];
-make_pair(NOT_HASHABLE,0
+CompleteHashKey(
-          else if (p == 'X') {
-            hashkey += hashCodes[i+offsetX+pattern->left + boardsize*(j+offsetY+pattern->top)];
@@ -2683 +2729 @@
-        }
-      }
-make_pair(NOT_HASHABLE,0);
+CompleteHashKey(); // NOT_HASHABLE
-
-      // make sure all hash keys are unique
-      for(vector<hashtype>::iterator it = hCodes.begin(); it != hCodes.end(); it++)
-make_pair(NOT_HASHABLE, 0);
+CompleteHashKey(); // NOT_HASHABLE
-      hCodes.push_back(hashkey);
-
@@ -2693 +2739 @@
-        hk = hashkey;
-        f = pCtr;
+        oX = offsetX;
+        oY = offsetY;
-      }
-    }
-  }
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-// Algo_hash_side::Algo_hash_side(int bsize, int SIZEX, int SIZEY) : Algo_hash(bsize, "SIDE") {
@@ -2719 +2800 @@
-
-Algo_hash_center::Algo_hash_center(int bsize) : Algo_hash(bsize, "CENTER", 16) {
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-}
-        
-void Algo_hash_center::endOfNode_process() {
-  for(vector<HashInstance* >::iterator it = hi->begin(); it != hi->end(); it++) {
-numStones <= maxNumStones && (*it)->
+
-      (*it)->changed = false;
-      pair<hashtype,int> phi = (*it)->cHC();
-
+
+
-        if (insert_hash(phi.first, phi.second) != 0) throw DBError();
-    }
@@ -2736 +2833 @@
-}
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
@@ -2820 +2989 @@
-  branchpoints->pop();
-}
-
-
-HashInstanceCO::HashInstanceCO(char X, char Y, char SIZEX, char SIZEY, int BOARDSIZE) : HashInstance(X, Y, SIZEX, SIZEY, BOARDSIZE) {
@@ -3364 +3532 @@
-// }
-
-
-
-
-// ----------------------------------------------------------------------------------------------
-
@@ -4406 +4571 @@
-  int pos = 0;
-  while (root) {
+    printf("current: %d\n", current);
-    current++;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    vector<string>* rootNodeProperties = parseRootNode(root, SGFtags);
-    // for(vector<string>::iterator rnp = rootNodeProperties->begin(); rnp != rootNodeProperties->end(); rnp++)

06/libkombilo-branches/hash_center/search.h

@@ -82 +82 @@
-const int FULLBOARD_PATTERN = 9;
-
+class PatternList;
+
-class Pattern {
-  public:
@@ -99 +101 @@
-    char* contLabels;
-    std::vector<MoveNC> contList;
+
-
-    // Pattern constructors
@@ -117 +120 @@
-    Pattern& copy(const Pattern& p);
-
+    Pattern& apply_flip(int f, bool CS = true);
+    Pattern& subpattern(int offsetX, int offsetY, int sizeX, int sizeY);
-    char getInitial(int i, int j);
-    char getFinal(int i, int j);
@@ -128 +133 @@
-    static int PatternInvFlip(int i);
-    static int compose_flips(int i, int j); // returns index of flip "first j, then i"
+    // static int compose_flips_CS(int i, int j); // similarly, but taking CS into account (i.e. 0<=i,j<16)
-};
-
@@ -151 +157 @@
-    std::vector<Symmetries> symmetries;
-    Continuation* continuations;
+    // flipTable encodes the action of the group of symmetries of the square times Z/2 (for color switch)
+    // on pattern: flipTable[i] is the index in data of the pattern resulting from applying flip i and no 
+    // CS (0<=i<8), or flip i-8 and CS (8<=i<16) to pattern.
-    int* flipTable;
+    // special is -1, or equal to the inverse of the flip which maps pattern to its CS'ed pattern
-    int special;
-
@@ -157 +167 @@
-    ~PatternList();
-
-
+// static 
-    void patternList();
-    Pattern get(int i);
@@ -342 +352 @@
-};
-
-ihing hit for corner/side
+hing hit for corner/side/center
-  public:
-    int gameid;
@@ -443 +453 @@
-};
-
+class CompleteHashKey { 
+  // returned by compute_hashkey 
+  // contains the information about which subpattern was used to compute the actual hashCode
+  public:
+    hashtype hashCode;
+    int offsetX;
+    int offsetY;
+    int index; // index in corresp. patternList
+
+    CompleteHashKey(); // = NOT_HASHABLE
+    CompleteHashKey(hashtype HASHCODE, int OFFSETX, int OFFSETY, int INDEX);
+};
+
+class HashQuery {
+  public:
+    std::string sql;
+    PatternList* pl0;
+    PatternList* pl1;
+    int flip0;
+    int flip1;
+    int offset0;
+    int offset1;
+    hashtype hashCode0;
+
+    HashQuery(std::string SQL, Pattern* p0, int OFF0, int FLIP0, hashtype HASHCODE0, Pattern* p1, int OFF1, int FLIP1);
+    ~HashQuery();
+};
-
-class Algo_hash : public Algorithm {
@@ -463 +500 @@
-    virtual void endgame_process();
-    virtual void finalize_process();
+    virtual HashQuery searchQuery(PatternList& patternList);
-    virtual int search(PatternList& patternList, GameList& gl, SearchOptions& options, sqlite3* db);
-
-    virtual int insert_hash(hashtype hashCod, int pos);
-std::pair<hashtype,int>
+CompleteHashKey
-    std::vector<HashInstance* >* hi;
-    std::string dbnameext;
@@ -477 +515 @@
-  public:
-    Algo_hash_corner(int bsize, int SIZE=7, int MAXNUMSTONES = 20);
-
+
+
+
-    int size;
-};
@@ -492 +532 @@
-    Algo_hash_center(int bsize);
-    void initialize_process(sqlite3* DB) throw(DBError);
+    void finalize_process();
-    void endOfNode_process();
-void finalize_process(
-std::pair<hashtype,int> compute_hashkey(PatternList& pl, int CS
+CompleteHashKey compute_hashkey(PatternList& pl, int CS
+HashQuery searchQuery(PatternList& patternList
-
-    std::map<hashtype, int> data;
+  private:
+    std::map<hashtype, int> frequency;
-};
-