kombilo/abstractboard.cpp

   1 // File: abstractboard.cpp
   2 // part of libkombilo, http://www.u-go.net/kombilo/
   3
   4 // Copyright (c) 2006-7 Ulrich Goertz <u@g0ertz.de>
   5
   6 // Permission is hereby granted, free of charge, to any person obtaining a copy of
   7 // this software and associated documentation files (the "Software"), to deal in
   8 // the Software without restriction, including without limitation the rights to
   9 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  10 // of the Software, and to permit persons to whom the Software is furnished to do
  11 // so, subject to the following conditions:
  12 //
  13 // The above copyright notice and this permission notice shall be included in all
  14 // copies or substantial portions of the Software.
  15 //
  16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22 // SOFTWARE.
  23
  24 #include "abstractboard.h"
  25 using std::stack;
  26 using std::vector;
  27
  28 BoardError::BoardError() {}
  29
  30 MoveNC::MoveNC() {
  31   x = -1;
  32   y = -1;
  33   color = ' ';
  34 }
  35
  36 // coordinates used here: top left = (0,0) - bottom right = (boardsize-1,boardsize-1)
  37 MoveNC::MoveNC(char X, char Y, char COLOR) {
  38   x = X;
  39   y = Y;
  40   color = COLOR;
  41 }
  42
  43 bool MoveNC::operator==(const MoveNC& mnc) const {
  44   if (x == mnc.x && y == mnc.y && color == mnc.color) return true;
  45   else return false;
  46 }
  47
  48 Move::Move(char xx, char yy, char cc) : MoveNC(xx, yy, cc) {
  49   captures = 0;
  50 }
  51
  52 Move::Move(const Move& m) : MoveNC(m.x, m.y, m.color) {
  53   if (m.captures) {
  54     captures = new vector<p_cc>;
  55     vector<p_cc>::iterator it;
  56     for(it = m.captures->begin(); it != m.captures->end(); it++)
  57       captures->push_back(*it);
  58   }
  59   else captures = 0;
  60 }
  61
  62 Move::~Move() {
  63   if (captures) delete captures;
  64 }
  65
  66 Move& Move::operator=(const Move& m) {
  67   if (this != &m) {
  68     x = m.x;
  69     y = m.y;
  70     color = m.color;
  71     if (captures) delete captures;
  72     if (m.captures) {
  73       captures = new vector<p_cc>;
  74       vector<p_cc>::iterator it;
  75       for(it = m.captures->begin(); it != m.captures->end(); it++)
  76         captures->push_back(*it);
  77     }
  78     else captures = 0;
  79   }
  80   return *this;
  81 }
  82
  83 abstractBoard::abstractBoard(int bs) throw(BoardError) {
  84   boardsize = bs;
  85   if (boardsize < 1) throw BoardError();
  86   status = new char[boardsize*boardsize+1];
  87   for (int i = 0; i < boardsize*boardsize; i++)
  88       status[i] = ' ';
  89   status[boardsize*boardsize] = 0;
  90 }
  91
  92 abstractBoard::abstractBoard(const abstractBoard& ab) {
  93   boardsize = ab.boardsize;
  94   status = new char[boardsize*boardsize+1];
  95   for (int i = 0; i < boardsize*boardsize; i++)
  96       status[i] = ab.status[i];
  97   status[boardsize*boardsize] = 0;
  98   undostack = stack<Move>(ab.undostack);
  99 }
 100
 101 abstractBoard& abstractBoard::operator=(const abstractBoard& ab) {
 102   if (this != &ab) {
 103     boardsize = ab.boardsize;
 104     delete [] status;
 105     status = new char[boardsize*boardsize+1];
 106     for (int i = 0; i < boardsize*boardsize; i++)
 107       status[i] = ab.status[i];
 108     status[boardsize*boardsize] = 0;
 109     undostack = stack<Move>(ab.undostack);
 110   }
 111   return *this;
 112 }
 113
 114 abstractBoard::~abstractBoard() {
 115   delete [] status;
 116 }
 117
 118 // abstractBoard& abstractBoard::copy(const abstractBoard& ab) {
 119 //   printf("copy assignment operator\n");
 120 //   if (this != &ab) {
 121 //     delete status;
 122 //     boardsize = ab.boardsize;
 123 //     status = new char[boardsize*boardsize+1];
 124 //     for (int i = 0; i < boardsize*boardsize; i++)
 125 //       status[i] = ab.status[i];
 126 //     status[boardsize*boardsize] = 0;
 127 //     undostack = ab.undostack;
 128 //   }
 129 //   return *this;
 130 // }
 131
 132 char abstractBoard::getStatus(int x, int y) {
 133   return status[boardsize*x + y];
 134 }
 135
 136 void abstractBoard::setStatus(int x, int y, char val) {
 137   if (val=='b' || val=='B') status[boardsize*x + y] = 'B';
 138   else if (val=='w' || val=='W') status[boardsize*x + y] = 'W';
 139   else status[boardsize*x + y] = val;
 140 }
 141
 142 int abstractBoard::len_cap_last() throw(BoardError) {
 143   if (!undostack.size()) throw BoardError();
 144   Move m = undostack.top();
 145   if (m.captures) return m.captures->size();
 146   else return 0;
 147 }
 148
 149 void abstractBoard::undostack_append_pass() {
 150   undostack.push(Move(19,19,'-'));
 151 }
 152
 153 int* abstractBoard::neighbors(int x, int y) {
 154   int* result = new int[5];
 155   char resultIndex = 1;
 156   if (x-1 >= 0) result[resultIndex++]=(x-1) * boardsize + y;
 157   if (x+1 < boardsize) result[resultIndex++]=(x+1) * boardsize + y;
 158   if (y-1 >= 0) result[resultIndex++]=x * boardsize + y-1;
 159   if (y+1 < boardsize) result[resultIndex++]=x*boardsize + y+1;
 160   result[0] = resultIndex-1;
 161   return result;
 162 }
 163
 164 void abstractBoard::clear() {
 165   for(int i=0; i<boardsize*boardsize; i++) status[i]=' ';
 166   undostack = stack<Move>();
 167 }
 168
 169 int abstractBoard::play(int x, int y, char* color) throw (BoardError) {
 170   if (x<0 || x>=boardsize || y<0 || y>=boardsize) return 0;
 171   if (status[boardsize*x+y] != ' ') {
 172     return 0;
 173   }
 174
 175   vector<p_cc>* captures = legal(x, y, color[0]);
 176   if (captures) {
 177     vector<p_cc>::iterator it;
 178     for(it=captures->begin(); it!=captures->end(); it++)
 179       status[boardsize*it->first + it->second] = ' '; // remove captured stones, if any
 180     Move m(x, y, color[0]);
 181     if (captures->size()) m.captures = captures;
 182     else delete captures;
 183     undostack.push(m);
 184     return 1;
 185   }
 186   return 0;
 187 }
 188
 189 vector<p_cc>* abstractBoard::legal(int x, int y, char color) {
 190   vector<p_cc>* c = new vector<p_cc>;
 191   int* nb = neighbors(x,y);
 192   for(int i=1; i<=nb[0]; i++) {
 193     int x1 = nb[i] / boardsize;
 194     int y1 = nb[i] % boardsize;
 195     if (status[boardsize*x1 + y1] == invert(color)) {
 196       vector<p_cc>* d = hasNoLibExcP(x1, y1, x*boardsize+y);
 197       vector<p_cc>::iterator it;
 198       for(it = d->begin(); it != d->end(); it++) c->push_back(*it);
 199       delete d;
 200     }
 201   }
 202   delete [] nb;
 203   setStatus(x,y,color);
 204
 205   if (c->size()) {
 206     vector<p_cc>* captures = new vector<p_cc>();
 207     while (c->size()) {
 208       p_cc ctop = (*c)[0];
 209       bool contained = false;
 210       vector<p_cc>::iterator it;
 211       for(it = captures->begin(); it != captures->end(); it++) {
 212         if (ctop.first == it->first && ctop.second == it->second) {
 213           contained = true;
 214           break;
 215         }
 216       }
 217       if (!contained) captures->push_back(ctop);
 218       c->erase(c->begin());
 219     }
 220     delete c;
 221     return captures;
 222   }
 223   delete c;
 224   vector<p_cc>* d = hasNoLibExcP(x, y);
 225   if (d->size()) {
 226     delete d;
 227     status[boardsize*x + y] = ' ';
 228     return 0;
 229   }
 230   else {
 231     delete d;
 232     vector<p_cc>* ret = new vector<p_cc>();
 233     return ret;
 234   }
 235 }
 236
 237 vector<p_cc>* abstractBoard::hasNoLibExcP(int x1, int y1, int exc) {
 238   vector<p_cc>* st = new vector<p_cc>;
 239   vector<p_cc>* newlyFound = new vector<p_cc>;
 240   newlyFound->push_back(p_cc(x1, y1));
 241   vector<p_cc>* n;
 242   int foundNew = 1;
 243
 244   while (foundNew) {
 245     foundNew = 0;
 246     n = new vector<p_cc>;
 247     vector<p_cc>::iterator it1;
 248     for(it1=newlyFound->begin(); it1!=newlyFound->end(); it1++) {
 249       int x = it1->first;
 250       int y = it1->second;
 251       int* nbs = neighbors(x,y);
 252       for (int j=1; j <= nbs[0]; j++) {
 253         int yy1 = nbs[j];
 254         if (status[yy1] == ' ' && yy1 != exc) {
 255           delete [] nbs;
 256           delete st;
 257           delete newlyFound;
 258           delete n;
 259           return new vector<p_cc>;
 260         }
 261         else {
 262           if (status[yy1]==status[x*boardsize+y]) {
 263             p_cc yy(yy1/boardsize, yy1%boardsize);
 264             int foundNewHere = 1;
 265             vector<p_cc>::iterator it;
 266             for(it=n->begin(); it!=n->end(); it++) {
 267               if (it->first==yy.first && it->second==yy.second) {
 268                 foundNewHere = 0;
 269                 break;
 270               }
 271             }
 272             if (foundNewHere) {
 273               for(it = st->begin(); it!=st->end(); it++) {
 274                 if (it->first==yy.first && it->second==yy.second) {
 275                   foundNewHere = 0;
 276                   break;
 277                 }
 278               }
 279             }
 280             if (foundNewHere) {
 281               n->push_back(yy);
 282               foundNew = 1;
 283             }
 284           }
 285         }
 286       }
 287       delete [] nbs;
 288     }
 289
 290     vector<p_cc>::iterator it;
 291     for(it=newlyFound->begin(); it!=newlyFound->end(); it++) {
 292       st->push_back(*it);
 293     }
 294     delete newlyFound;
 295     newlyFound = n;
 296   }
 297   delete n;
 298   return st;
 299 }
 300
 301 void abstractBoard::undo(int n) {
 302   for(int i=0; i<n; i++) {
 303     if (undostack.size()) {
 304       Move tuple = undostack.top();
 305       undostack.pop();
 306
 307       char color = tuple.color;
 308       vector<p_cc>* captures = tuple.captures;
 309       int x = tuple.x;
 310       int y = tuple.y;
 311
 312       status[x*boardsize+y] = ' ';
 313       if (captures) {
 314   for(unsigned int i=0; i < captures->size(); i++) {
 315     p_cc t = (*captures)[i];
 316     setStatus(t.first, t.second, invert(color));
 317   }
 318       }
 319     }
 320   }
 321 }
 322
 323 void abstractBoard::remove(int x, int y) {
 324   undostack.push(Move(-1, -1, invert(status[boardsize*x+y])));
 325   status[boardsize*x+y] = ' ';
 326 }
 327
 328 char abstractBoard::invert(char color) {
 329   if (color == 'B' || color == 'b') return 'W';
 330   if (color == 'W' || color == 'w') return 'B';
 331   return ' ';
 332 }
 333