root/06/libkombilo-branches/hash_center_makedb/search.cpp

// File: search.cpp
// part of libkombilo, http://www.u-go.net/kombilo/

// Copyright (c) 2006-7 Ulrich Goertz <u@g0ertz.de>

// Permission is hereby granted, free of charge, to any person obtaining a copy of 
// this software and associated documentation files (the "Software"), to deal in 
// the Software without restriction, including without limitation the rights to 
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
// of the Software, and to permit persons to whom the Software is furnished to do 
// so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all 
// copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
// SOFTWARE.

#include "sgfparser.h"
#include "abstractboard.h"
#include "search.h"
#include <stdio.h>
#include <string>
#include <cstring>

using std::min;
using std::max;
using std::string;
using std::vector;
using std::map;
using std::pair;
using std::make_pair;
using std::stack;

#if defined(_MSC_VER)
#include <algorithm>
#else
using std::sort;
#endif

PatternError::PatternError() {}

Continuation::Continuation() {
  B  = 0;
  W  = 0;
  tB = 0;
  tW = 0;
  wB = 0;
  lB = 0;
  wW = 0;
  lW = 0;
}

Symmetries::Symmetries(char sX, char sY) {
  sizeX = sX;
  sizeY = sY;
  dataX = new char[sizeX*sizeY];
  dataY = new char[sizeX*sizeY];
  dataCS = new char[sizeX*sizeY];
  for(int i=0; i<sizeX*sizeY; i++) {
    dataX[i] = -1;
    dataY[i] = -1;
    dataCS[i] = -1;
  }
}

Symmetries::~Symmetries() {
  delete [] dataX;
  delete [] dataY;
  delete [] dataCS;
}

Symmetries::Symmetries(const Symmetries& s) {
  sizeX = s.sizeX;
  sizeY = s.sizeY;
  dataX = new char[sizeX*sizeY];
  dataY = new char[sizeX*sizeY];
  dataCS = new char[sizeX*sizeY];
  for(int i=0; i<sizeX*sizeY; i++) {
    dataX[i] = s.dataX[i];
    dataY[i] = s.dataY[i];
    dataCS[i] = s.dataCS[i];
  }
}

Symmetries& Symmetries::operator=(const Symmetries& s) {
  if (&s != this) {
    sizeX = s.sizeX;
    sizeY = s.sizeY;
    delete [] dataX;
    delete [] dataY;
    delete [] dataCS;
    dataX = new char[sizeX*sizeY];
    dataY = new char[sizeX*sizeY];
    dataCS = new char[sizeX*sizeY];
    for(int i=0; i<sizeX*sizeY; i++) {
      dataX[i] = s.dataX[i];
      dataY[i] = s.dataY[i];
      dataCS[i] = s.dataCS[i];
    }
  }
  return *this;
}

void Symmetries::set(char i, char j, char k, char l, char cs) throw(PatternError) {
  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) {
    dataX[i + j*sizeX] = k;
    dataY[i + j*sizeX] = l;
    dataCS[i + j*sizeX] = cs;
  }
  else throw PatternError();
}

char Symmetries::getX(char i, char j) throw(PatternError) {
  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataX[i + j*sizeX];
  else throw PatternError();
  return -1;
}

char Symmetries::getY(char i, char j) throw(PatternError) {
  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataY[i + j*sizeX];
  else throw PatternError();
  return -1;
}

char Symmetries::getCS(char i, char j) throw(PatternError) {
  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataCS[i + j*sizeX];
  else throw PatternError();
  return -1;
}

char Symmetries::has_key(char i, char j) throw(PatternError) {
  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) {
    if (dataX[i + j*sizeX] == -1) return 0;
    else return 1;
  }
  else throw PatternError();
  return 0;
}



// ----------- class Pattern -----------------------------------------------

int Pattern::operator==(const Pattern& p) {
  if (boardsize != p.boardsize) return 0;
  if (sizeX != p.sizeX || sizeY != p.sizeY) return 0;
  if (left != p.left || right != p.right || top != p.top || bottom != p.bottom) return 0; 
  for(int i=0; i < sizeX*sizeY; i++)
    if (initialPos[i] != p.initialPos[i]) return 0;
  if (contList != p.contList) return 0;
  return 1;
}


char Pattern::BW2XO(char c) {
  if (c == 'B') return 'X';
  if (c == 'W') return 'O';
  return c;
}

char Pattern::getInitial(int i, int j) {
  return initialPos[i + sizeX*j];
}
 
char Pattern::getFinal(int i, int j) {
  return finalPos[i + sizeX*j];
}
 

Pattern::Pattern() {
  initialPos = 0;
  finalPos = 0;
  flip = 0;
  colorSwitch = 0;
  sizeX = 0;
  sizeY = 0;
  boardsize = 0;
  contLabels = 0;
}


Pattern::Pattern(int type, int BOARDSIZE, int sX, int sY, char* iPos, char* CONTLABELS) {
  flip = 0;
  colorSwitch = 0;
  sizeX = sX;
  sizeY = sY;
  boardsize = BOARDSIZE;
  if (CONTLABELS) {
    contLabels = new char[sizeX * sizeY];
    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
  } else contLabels = 0;

  if (type == CORNER_NW_PATTERN || type == FULLBOARD_PATTERN) {
    left = right = top = bottom = 0;
  } else if (type == CORNER_NE_PATTERN) {
    top = bottom = 0;
    left = right = boardsize - sizeX;
  } else if (type == CORNER_SE_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = right = boardsize - sizeX;
  } else if (type == CORNER_SW_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = right = 0;
  } else if (type == SIDE_N_PATTERN) {
    top = bottom = 0;
    left = 1;
    right = boardsize -1 - sizeX;
  } else if (type == SIDE_E_PATTERN) {
    left = right = boardsize - sizeX;
    top = 1;
    bottom = boardsize -1 - sizeY;
  } else if (type == SIDE_W_PATTERN) {
    left = right = 0;
    top = 1;
    bottom = boardsize -1 - sizeY;
  } else if (type == SIDE_S_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = 1;
    right = boardsize -1 - sizeX;
  } else if (type == CENTER_PATTERN) {
    left = top = 1;
    right = boardsize -1 - sizeX;
    bottom = boardsize -1 - sizeY;
  }

  initialPos = new char[sizeX * sizeY];
  finalPos = new char[sizeX*sizeY];
  for(int i=0; i<sizeX*sizeY; i++) {
    initialPos[i] = iPos[i];
    finalPos[i] = iPos[i];
  }
}

Pattern::Pattern(int type, int BOARDSIZE, int sX, int sY, char* iPos, vector<MoveNC> CONTLIST, char* CONTLABELS) {
  flip = 0;
  colorSwitch = 0;
  sizeX = sX;
  sizeY = sY;
  boardsize = BOARDSIZE;
  if (CONTLABELS) {
    contLabels = new char[sizeX * sizeY];
    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
  } else contLabels = 0;

  if (type == CORNER_NW_PATTERN || type == FULLBOARD_PATTERN) {
    left = right = top = bottom = 0;
  } else if (type == CORNER_NE_PATTERN) {
    top = bottom = 0;
    left = right = boardsize - sizeX;
  } else if (type == CORNER_SE_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = right = boardsize - sizeX;
  } else if (type == CORNER_SW_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = right = 0;
  } else if (type == SIDE_N_PATTERN) {
    top = bottom = 0;
    left = 1;
    right = boardsize -1 - sizeX;
  } else if (type == SIDE_E_PATTERN) {
    left = right = boardsize - sizeX;
    top = 1;
    bottom = boardsize -1 - sizeY;
  } else if (type == SIDE_W_PATTERN) {
    left = right = 0;
    top = 1;
    bottom = boardsize -1 - sizeY;
  } else if (type == SIDE_S_PATTERN) {
    top = bottom = boardsize - sizeY;
    left = 1;
    right = boardsize -1 - sizeX;
  } else if (type == CENTER_PATTERN) {
    left = top = 1;
    right = boardsize -1 - sizeX;
    bottom = boardsize -1 - sizeY;
  }

  initialPos = new char[sizeX * sizeY];
  finalPos = new char[sizeX*sizeY];
  for(int i=0; i<sizeX*sizeY; i++) {
    initialPos[i] = iPos[i];
    finalPos[i] = iPos[i];
  }

  contList = CONTLIST;
}

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
  if (le < 0 || ri+sX > BOARDSIZE || to < 0 || bo+sY > BOARDSIZE || ri < le || bo < to) throw PatternError();

  flip = 0;
  colorSwitch = 0;
       
  left = le;
  right = ri;
  top = to;
  bottom = bo;
  boardsize = BOARDSIZE;

  sizeX = sX;
  sizeY = sY;
  if (CONTLABELS) {
    contLabels = new char[sizeX * sizeY];
    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
  } else contLabels = 0;

  initialPos = new char[sizeX * sizeY];
  finalPos = new char[sizeX*sizeY];
  for(int i=0; i<sizeX*sizeY; i++) {
    initialPos[i] = iPos[i];
    finalPos[i] = iPos[i];
  }

  contList = CONTLIST;
}

Pattern::~Pattern() {
  if (initialPos) delete [] initialPos;
  if (finalPos) delete [] finalPos;
  if (contLabels) delete [] contLabels;
}

Pattern::Pattern(const Pattern& p) {
  left = p.left;
  right = p.right;
  top = p.top;
  bottom = p.bottom;
  boardsize = p.boardsize;
  sizeX = p.sizeX;
  sizeY = p.sizeY;
  flip = p.flip;
  colorSwitch = p.colorSwitch;

  initialPos = new char[sizeX*sizeY];
  finalPos = new char[sizeX*sizeY];
  if (p.contLabels) contLabels = new char[sizeX*sizeY];
  else contLabels = 0;
  for(int i=0; i<sizeX*sizeY; i++) {
    initialPos[i] = p.initialPos[i];
    finalPos[i] = p.finalPos[i];
    if (p.contLabels) contLabels[i] = p.contLabels[i];
  }
  contList = p.contList;
}

Pattern& Pattern::operator=(const Pattern& p) {
  if (&p != this) {
    left = p.left;
    right = p.right;
    top = p.top;
    bottom = p.bottom;
    boardsize = p.boardsize;
    sizeX = p.sizeX;
    sizeY = p.sizeY;
    flip = p.flip;
    colorSwitch = p.colorSwitch;

    if (initialPos) delete [] initialPos;
    if (finalPos) delete [] finalPos;
    if (contLabels) delete [] contLabels;
    
    initialPos = new char[sizeX*sizeY];
    finalPos = new char[sizeX*sizeY];
    if (p.contLabels) contLabels = new char[sizeX*sizeY];
    else contLabels = 0;
    for(int i=0; i<sizeX*sizeY; i++) {
      initialPos[i] = p.initialPos[i];
      finalPos[i] = p.finalPos[i];
      if (p.contLabels) contLabels[i] = p.contLabels[i];
    }
    contList = p.contList;
  }
  return *this;
}


Pattern& Pattern::copy(const Pattern& p) {
  if (&p != this) {
    left = p.left;
    right = p.right;
    top = p.top;
    bottom = p.bottom;
    boardsize = p.boardsize;
    sizeX = p.sizeX;
    sizeY = p.sizeY;
    flip = p.flip;
    colorSwitch = p.colorSwitch;

    if (initialPos) delete [] initialPos;
    if (finalPos) delete [] finalPos;
    
    initialPos = new char[sizeX*sizeY];
    finalPos = new char[sizeX*sizeY];
    if (p.contLabels) contLabels = new char[sizeX*sizeY];
    else contLabels = 0;
    for(int i=0; i<sizeX*sizeY; i++) {
      initialPos[i] = p.initialPos[i];
      finalPos[i] = p.finalPos[i];
      if (p.contLabels) contLabels[i] = p.contLabels[i];
    }
    contList = p.contList;
  }
  return *this;
}

string Pattern::printPattern() {
  string result;
  char buf[100];
  sprintf(buf, "boardsize: %d, area: %d, %d, %d, %d\nsize: %d, %d\n", boardsize, left, right, top, bottom, sizeX, sizeY);
  result += buf;
  for(int i=0; i<sizeY; i++) {
    for(int j=0; j<sizeX; j++) {
      if (initialPos[i*sizeX + j] == 'X' || initialPos[i*sizeX + j] == 'O' || initialPos[i*sizeX + j] == 'x' || initialPos[i*sizeX + j] == 'x' || initialPos[i*sizeX+j] == '*') result += initialPos[i*sizeX+j];
      else result += '.';
    }
    result += "\n";
  }
  result += "\n";
  return result;
}


int Pattern::flipsX(int i, int x, int y, int XX, int YY) {
  if (i==0) return x;
  if (i==1) return XX-x;
  if (i==2) return x;
  if (i==3) return XX-x;
  if (i==4) return y;
  if (i==5) return YY-y;
  if (i==6) return y;
  if (i==7) return YY-y;
  return -1;
}

int Pattern::flipsY(int i, int x, int y, int XX, int YY) {
  if (i==0) return y;
  if (i==1) return y;
  if (i==2) return YY-y;
  if (i==3) return YY-y;
  if (i==4) return x;
  if (i==5) return x;
  if (i==6) return XX-x;
  if (i==7) return XX-x;
  return -1;
}


int Pattern::PatternInvFlip(int i) {
  if (i == 5) return 6;
  if (i == 6) return 5;
  return i;
}

const int composition_table[] = {
  0, 1, 2, 3, 4, 5, 6, 7,
  1, 0, 3, 2, 5, 4, 7, 6,
  2, 3, 0, 1, 6, 7, 4, 5,
  3, 2, 1, 0, 7, 6, 5, 4,
  4, 6, 5, 7, 0, 2, 1, 3,
  5, 7, 4, 6, 1, 3, 0, 2,
  6, 4, 7, 5, 2, 0, 3, 1,
  7, 5, 6, 4, 3, 1, 2, 0 };

int Pattern::compose_flips(int i, int j) {
  return composition_table[j+8*i];
}

PatternList::PatternList(Pattern& p, int fColor, int nMove) throw(PatternError) {
  pattern.copy(p);
  fixedColor = fColor;
  nextMove = nMove;
  special = -1;
  flipTable = new int[16];
  for(int i=0; i<16; i++) flipTable[i] = -1; // (patternList() relies on this)

  patternList();
  continuations = new Continuation[pattern.sizeX * pattern.sizeY];
}

PatternList::~PatternList() {
  delete [] continuations;
  delete [] flipTable;
}

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() {
        
  vector<Pattern> lCS;
  vector<pair<int,int> > sy;
  int boardsize = pattern.boardsize;

  for(int f = 0; f < 8; f++) {
    int newSizeX = max(Pattern::flipsX(f,0,0,pattern.sizeX,pattern.sizeY),
                       Pattern::flipsX(f,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));
    int newSizeY = max(Pattern::flipsY(f,0,0,pattern.sizeX,pattern.sizeY),
                       Pattern::flipsY(f,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));

    int newLeft = min(Pattern::flipsX(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
                      Pattern::flipsX(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
                                      boardsize-1,boardsize-1));
    int newRight = max(Pattern::flipsX(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
                       Pattern::flipsX(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
                                       boardsize-1,boardsize-1)) - (newSizeX-1);
    int newTop = min(Pattern::flipsY(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
                     Pattern::flipsY(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
                                     boardsize-1,boardsize-1));
    int newBottom = max(Pattern::flipsY(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
                        Pattern::flipsY(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.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[pattern.sizeX*pattern.sizeY];
    int i=0;
    for(i=0; i<pattern.sizeX; i++) {
      for(int j=0; j<pattern.sizeY; j++) {
        newInitialPos[Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1) + \
                      newSizeX*Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1)] = pattern.getInitial(i, j);
      }
    }

    vector<MoveNC> newContList;
    for(i=0; (unsigned int)i<pattern.contList.size(); i++) {
      newContList.push_back(MoveNC(Pattern::flipsX(f, pattern.contList[i].x, pattern.contList[i].y, 
                                                      pattern.sizeX-1,pattern.sizeY-1),
                                  Pattern::flipsY(f, pattern.contList[i].x, pattern.contList[i].y,
                                                      pattern.sizeX-1,pattern.sizeY-1),
                                  pattern.contList[i].color));
    }

    Pattern pNew(newLeft, newRight, newTop, newBottom, pattern.boardsize, newSizeX, newSizeY,
                 newInitialPos, newContList);

    pNew.flip = f;
    // printf("new size %d %d\n", pNew.sizeX, pNew.sizeY);

    delete [] newInitialPos;

    vector<Pattern>::iterator it;
    bool foundNewPattern = true;
    for(it = data.begin(); it != data.end(); it++) {
      if (pNew == *it) {
        foundNewPattern = false;
        flipTable[f] = flipTable[it->flip];
        break;
      }
    }
    if (foundNewPattern) {
      flipTable[f] = data.size();
      data.push_back(pNew);
    }

    if (pNew == pattern) sy.push_back(pair<int,int>(f,0));

    if (nextMove || !fixedColor) {
      char* newInitialPos = new char[pattern.sizeX*pattern.sizeY];
      for(int i=0; i<pattern.sizeX; i++) {
        for(int j=0; j<pattern.sizeY; j++) {
          newInitialPos[Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1) + newSizeX*Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1)] =
            invertColor(pattern.getInitial(i, j));
        }
      }
      vector<MoveNC> newContList;
      {
        for(unsigned int i=0; i<pattern.contList.size(); i++) {
          newContList.push_back(MoveNC(Pattern::flipsX(f, pattern.contList[i].x, pattern.contList[i].y, 
                  pattern.sizeX-1,pattern.sizeY-1),
                Pattern::flipsY(f, pattern.contList[i].x, pattern.contList[i].y,
                  pattern.sizeX-1,pattern.sizeY-1),
                invertColor(pattern.contList[i].color)));
        }
      }


      // printf("new size %d %d", newSizeX, newSizeY);
      Pattern pNew1(newLeft, newRight, newTop, newBottom, pattern.boardsize, newSizeX, newSizeY,
                    newInitialPos, newContList);
      pNew1.flip = f;
      pNew1.colorSwitch = 1;

      delete [] newInitialPos;

      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++;
        }
        if (foundNewPattern) {
          lCS.push_back(pNew1);
        }
      }

      if (pNew1 == pattern) {
        if (!fixedColor) sy.push_back(pair<int