agents/c++/qchess.cpp

   1 /**
   2  * agent++ : A Sample agent for UCC::Progcomp2013
   3  * @file qchess.h
   4  * @purpose Definitions for game related classes; Piece, Square, Board
   5  */
   6
   7 #include "qchess.h"
   8 #include <cassert>
   9
  10 using namespace std;
  11
  12
  13 /**
  14  * @constructor
  15  * @param new_x, new_y - Position of piece
  16  * @param new_colour - Colour of piece
  17  * @param type1, type2 - Types of piece
  18  * @param new_type_index - Index for initial type of piece
  19  * @param new_piece_index - Index for piece in a vector
  20  */
  21 Piece::Piece(int new_x, int new_y, const Piece::Colour & new_colour, const Piece::Type & type1, const Piece::Type & type2,
  22              int new_type_index, int new_piece_index)
  23         : x(new_x), y(new_y), colour(new_colour), type_index(new_type_index), types(), current_type(), piece_index(new_piece_index)
  24 {
  25         types[0] = type1; types[1] = type2;
  26         if (type_index < 0 || type_index >= 2)
  27         {
  28                 current_type = Piece::UNKNOWN;
  29         }
  30         else
  31         {
  32                 current_type = types[type_index];
  33         }
  34 }
  35
  36 /**
  37  * @constructor
  38  * @param cpy - Piece to copy construct from
  39  */
  40 Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_index(cpy.type_index), piece_index(cpy.piece_index)
  41 {
  42         types[0] = cpy.types[0];
  43         types[1] = cpy.types[1];
  44 }
  45
  46 /**
  47  * @constructor
  48  * @param choose_types - Indicates whether Board should setup the 2nd types of pieces; default false
  49  */
  50 Board::Board(bool choose_types)
  51         : white(), black(), white_unknown(), black_unknown(), white_nUnknown(0), black_nUnknown(0),
  52         white_king(NULL), black_king(NULL),  parent(NULL)
  53 {
  54
  55         // initialise all the Squares
  56         for (int x = 0; x < BOARD_WIDTH; ++x)
  57         {
  58                 for (int y = 0; y < BOARD_HEIGHT; ++y)
  59                 {
  60                         grid[x][y].x = x;
  61                         grid[x][y].y = y;
  62                 }
  63         }
  64
  65         // const arrays simplify below code
  66         Piece::Colour colours[] = {Piece::BLACK, Piece::WHITE};
  67         Piece::Type types[] = {Piece::PAWN, Piece::BISHOP, Piece::KNIGHT, Piece::ROOK, Piece::QUEEN};
  68
  69         // frequency of each type of piece
  70         map<Piece::Type, int> freq;
  71         freq[Piece::ROOK] = 2;
  72         freq[Piece::BISHOP] = 2;
  73         freq[Piece::KNIGHT] = 2;
  74         freq[Piece::QUEEN] = 1;
  75         freq[Piece::PAWN] = 8;
  76
  77         if (!choose_types)
  78         {
  79                 white_unknown = freq;
  80                 black_unknown = freq;
  81                 white_nUnknown = 15;
  82                 black_nUnknown = 15;
  83         }
  84
  85         // for white and black...
  86         for (int i = 0; i < 2; ++i)
  87         {
  88                 vector<Piece*> & v = pieces(colours[i]); // get vector of pieces
  89
  90
  91
  92                 // add pawns
  93                 int y = (i == 0) ? 1 : BOARD_HEIGHT-2;
  94                 for (int x = 0; x < BOARD_WIDTH; ++x)
  95                 {
  96                         Piece::AddPiece(v, x, y, colours[i], Piece::PAWN, Piece::UNKNOWN);
  97                 }
  98
  99                 // add other pieces
 100                 y = (i == 0) ? 0 : BOARD_HEIGHT-1;
 101                 Piece::AddPiece(v, 0, y, colours[i], Piece::ROOK, Piece::UNKNOWN);
 102                 Piece::AddPiece(v, BOARD_WIDTH-1, y, colours[i], Piece::ROOK, Piece::UNKNOWN);
 103                 Piece::AddPiece(v, 1, y, colours[i], Piece::KNIGHT, Piece::UNKNOWN);
 104                 Piece::AddPiece(v, BOARD_WIDTH-2, y, colours[i], Piece::KNIGHT, Piece::UNKNOWN);
 105                 Piece::AddPiece(v, 2, y, colours[i], Piece::BISHOP, Piece::UNKNOWN);
 106                 Piece::AddPiece(v, BOARD_WIDTH-3, y, colours[i], Piece::BISHOP, Piece::UNKNOWN);
 107                 Piece::AddPiece(v, 3, y, colours[i], Piece::QUEEN, Piece::UNKNOWN);
 108
 109                 Piece * k = Piece::AddPiece(v, 4, y, colours[i], Piece::KING, Piece::KING, 1);
 110                 if (i == 0)
 111                         white_king = k;
 112                 else
 113                         black_king = k;
 114
 115
 116                 // add to board and choose second types if required
 117                 map<Piece::Type, int> f(freq);
 118                 int type2;
 119                 for (unsigned j = 0; j < v.size(); ++j)
 120                 {
 121                         Piece * p = v[j];
 122                         grid[p->x][p->y].piece = p;
 123                         if (choose_types)
 124                         {
 125                                 if (p->types[1] != Piece::UNKNOWN)
 126                                         continue;
 127
 128                                 do
 129                                 {
 130                                         type2 = rand() % 5;
 131                                 } while (f[types[type2]] <= 0);
 132                                 f[types[type2]] -= 1;
 133
 134                                 p->types[1] = types[type2];
 135                         }
 136
 137
 138                 }
 139
 140
 141
 142         }
 143
 144 }
 145
 146 /**
 147  * @constructor
 148  * @param cpy - Board to clone
 149  */
 150 Board::Board(Board & cpy)
 151 : white(cpy.white), black(cpy.black), white_unknown(cpy.white_unknown), black_unknown(cpy.black_unknown),
 152   white_nUnknown(cpy.white_nUnknown), black_nUnknown(cpy.black_nUnknown),
 153   white_king(cpy.white_king), black_king(cpy.black_king), parent(&cpy)
 154 {
 155         for (int x = 0; x < BOARD_WIDTH; ++x)
 156         {
 157                 for (int y = 0; y < BOARD_HEIGHT; ++y)
 158                 {
 159                         grid[x][y].x = x;
 160                         grid[x][y].y = y;
 161                         grid[x][y].piece = cpy.grid[x][y].piece;
 162                 }
 163         }
 164 }
 165
 166 /**
 167  * @destructor
 168  */
 169 Board::~Board()
 170 {
 171         white.clear();
 172         black.clear();
 173         for (int x = 0; x < BOARD_WIDTH; ++x)
 174         {
 175                 for (int y = 0; y < BOARD_HEIGHT; ++y)
 176                 {
 177                         delete grid[x][y].piece;
 178                 }
 179         }
 180
 181 }
 182
 183 /**
 184  * @funct Update_select
 185  * @purpose Update Piece that has been selected
 186  * @param x, y - Position of Piece to update
 187  * @param index - 0 or 1 - State the Piece "collapsed" into
 188  * @param type - Type of the Piece as a string
 189  */
 190 void Board::Update_select(int x, int y, int index, const string & type)
 191 {
 192         Board::Update_select(x, y, index, Piece::str2type(type));
 193 }
 194
 195 /**
 196  * @funct Update_select
 197  * @purpose Update Piece that has been selected
 198  * @param x, y - Position of Piece to update
 199  * @param index - 0 or 1 - State the Piece "collapsed" into
 200  * @param t - Type of the Piece
 201  */
 202 void Board::Update_select(int x, int y, int index, const Piece::Type & t)
 203 {
 204         cerr << "Updating " << x << "," << y << " " << grid[x][y].piece << " " << index << " " << t << "\n";
 205         Square & s = grid[x][y];
 206
 207         Clone_copy(s);
 208
 209         assert(s.piece != NULL);
 210         assert(index >= 0 && index < 2);
 211         s.piece->type_index = index;
 212
 213         if (s.piece->types[index] == Piece::UNKNOWN)
 214         {
 215                 map<Piece::Type, int> & m = unknown_types(s.piece->colour);
 216                 int n = (m[t]--);
 217                 if (n < 0)
 218                         throw Exception("Board::Update_select", "Too many pieces of type %s found", Piece::type2str(t));
 219
 220                 nUnknown(s.piece->colour)--;
 221
 222         }
 223         s.piece->types[index] = t;
 224         s.piece->current_type = t;
 225 }
 226
 227 /**
 228  * @funct Update_move
 229  * @purpose Move a Piece from one square to another
 230  * @param x1, y1 - Coords of Square containing moving Piece
 231  * @param x2, y2 - Coords of Square to move into
 232  *      NOTE: Any Piece in the destination Square will be destroyed ("taken")
 233  *              and the Board's other members updated accordingly
 234  */
 235 void Board::Update_move(int x1, int y1, int x2, int y2)
 236 {
 237         Square & s1 = grid[x1][y1];
 238         Square & s2 = grid[x2][y2];
 239
 240         Clone_copy(s1);
 241
 242
 243
 244
 245         if (s2.piece != NULL)
 246         {
 247                 vector<Piece*> & p = pieces(s2.piece->colour);
 248                 vector<Piece*>::iterator i = p.begin();
 249                 while (i != p.end())
 250                 {
 251                         if (*i == s2.piece)
 252                         {
 253                                 p.erase(i);
 254                                 break;
 255                         }
 256                         ++i;
 257                 }
 258                 while (i != p.end())
 259                 {
 260                         (*i)->piece_index -= 1;
 261                         ++i;
 262                 }
 263                 Piece * k = king(s2.piece->colour);
 264                 if (k == s2.piece)
 265                 {
 266                         if (k->colour == Piece::WHITE)
 267                                 white_king = NULL;
 268                         else
 269                                 black_king = NULL;
 270                 }
 271                 if ((IsClone() && s2.piece == parent->grid[x2][y2].piece) == false)
 272                 {
 273                         delete s2.piece;
 274                 }
 275         }
 276
 277         s1.piece->x = s2.x;
 278         s1.piece->y = s2.y;
 279
 280         s2.piece = s1.piece;
 281         s1.piece = NULL;
 282 }
 283
 284 /**
 285  * @funct Get_moves
 286  * @purpose Get all moves for a Piece and store them
 287  * @param p - Piece
 288  * @param v - vector to store Squares in. Will *not* be cleared.
 289  */
 290 void Board::Get_moves(Piece * p, vector<Square*> & v)
 291 {
 292         assert(p->current_type != Piece::UNKNOWN);
 293         int x = p->x; int y = p->y;
 294         if (p->current_type == Piece::KING)
 295         {
 296                 Move(p, x+1, y, v);
 297                 Move(p, x-1, y, v);
 298                 Move(p, x, y+1, v);
 299                 Move(p, x, y-1, v);
 300                 Move(p, x+1, y+1, v);
 301                 Move(p, x+1, y-1, v);
 302                 Move(p, x-1, y+1, v);
 303                 Move(p, x-1, y-1, v);
 304         }
 305         else if (p->current_type == Piece::KNIGHT)
 306         {
 307                 Move(p, x+2, y+1, v);
 308                 Move(p, x+2, y-1, v);
 309                 Move(p, x-2, y+1, v);
 310                 Move(p, x-2, y-1, v);
 311                 Move(p, x+1, y+2, v);
 312                 Move(p, x-1, y+2, v);
 313                 Move(p, x+1, y-2, v);
 314                 Move(p, x-1, y-2, v);
 315         }
 316         else if (p->current_type == Piece::PAWN)
 317         {
 318                 int y1 = (p->colour == Piece::WHITE) ? BOARD_HEIGHT-2 : 1;
 319                 int y2 = (p->colour == Piece::WHITE) ? y1 - 2 : y1 + 2;
 320                 if (p->types[0] == Piece::PAWN && p->y == y1)
 321                 {
 322
 323                         Move(p, x, y2, v);
 324                 }
 325                 y2 = (p->colour == Piece::WHITE) ? y - 1 : y + 1;
 326                 Move(p, x, y2, v);
 327
 328                 if (Valid_position(x-1, y2) && grid[x-1][y2].piece != NULL)
 329                         Move(p, x-1, y2, v);
 330                 if (Valid_position(x+1, y2) && grid[x+1][y2].piece != NULL)
 331                         Move(p, x+1, y2, v);
 332         }
 333         else if (p->current_type == Piece::BISHOP)
 334         {
 335                 Scan(p, 1, 1, v);
 336                 Scan(p, 1, -1, v);
 337                 Scan(p, -1, 1, v);
 338                 Scan(p, -1, -1, v);
 339         }
 340         else if (p->current_type == Piece::ROOK)
 341         {
 342                 Scan(p, 1, 0, v);
 343                 Scan(p, -1, 0, v);
 344                 Scan(p, 0, 1, v);
 345                 Scan(p, 0, -1, v);
 346         }
 347         else if (p->current_type == Piece::QUEEN)
 348         {
 349                 Scan(p, 1, 1, v);
 350                 Scan(p, 1, -1, v);
 351                 Scan(p, -1, 1, v);
 352                 Scan(p, -1, -1, v);
 353                 Scan(p, 1, 0, v);
 354                 Scan(p, -1, 0, v);
 355                 Scan(p, 0, 1, v);
 356                 Scan(p, 0, -1, v);
 357         }
 358
 359 }
 360
 361 /**
 362  * @funct Move
 363  * @purpose Add a move to the vector, if it is valid
 364  * @param p - Piece that would move
 365  * @param x, y - Destination Square coords
 366  * @param v - vector to put the destination Square in, if the move is valid
 367  */
 368 void Board::Move(Piece * p, int x, int y, vector<Square*> & v)
 369 {
 370         if (Valid_position(x, y) && (grid[x][y].piece == NULL || grid[x][y].piece->colour != p->colour))
 371         {
 372                 v.push_back(&(grid[x][y]));
 373         }
 374         //else
 375         //      cerr << "Square " << x << "," << y << " invalid; " << grid[x][y].piece << "\n";
 376 }
 377
 378 /**
 379  * @funct Scan
 380  * @purpose Add moves in a specified direction to the vector, until we get to an invalid move
 381  * @param p - Piece to start scanning from
 382  * @param vx, vy - "velocity" - change in coords each move
 383  * @param v - vector to store valid Squares in
 384  */
 385 void Board::Scan(Piece * p, int vx, int vy, vector<Square*> & v)
 386 {
 387         int x = p->x + vx;
 388         int y = p->y + vy;
 389         while (Valid_position(x, y) && (grid[x][y].piece == NULL || grid[x][y].piece->colour != p->colour))
 390         {
 391                 v.push_back(&(grid[x][y]));
 392                 if (grid[x][y].piece != NULL)
 393                         break;
 394                 x += vx;
 395                 y += vy;
 396         }
 397 }
 398
 399 /**
 400  * @funct str2type
 401  * @purpose Convert string to Piece::Type
 402  * @param str - The string
 403  * @returns A Piece::Type
 404  */
 405 Piece::Type Piece::str2type(const string & str)
 406 {
 407         if (str == "king")
 408                 return Piece::KING;
 409         else if (str == "queen")
 410                 return Piece::QUEEN;
 411         else if (str == "rook")
 412                 return Piece::ROOK;
 413         else if (str == "bishop")
 414                 return Piece::BISHOP;
 415         else if (str == "knight")
 416                 return Piece::KNIGHT;
 417         else if (str == "pawn")
 418                 return Piece::PAWN;
 419         else if (str == "unknown")
 420                 return Piece::UNKNOWN;
 421
 422         throw Exception("Piece::str2type", "String \"%s\" doesn't represent a type", str.c_str());
 423         return Piece::UNKNOWN;
 424 }
 425
 426 /**
 427  * @funct type2str
 428  * @purpose Convert Piece::Type to string
 429  * @param t - The Types
 430  * @returns a const char*
 431  */
 432 const char * Piece::type2str(const Piece::Type & t)
 433 {
 434         switch (t)
 435         {
 436                 case PAWN:
 437                         return "pawn";
 438                 case BISHOP:
 439                         return "bishop";
 440                 case KNIGHT:
 441                         return "knight";
 442                 case ROOK:
 443                         return "rook";
 444                 case QUEEN:
 445                         return "queen";
 446                 case UNKNOWN:
 447                         return "unknown";
 448                 case KING:
 449                         return "king";
 450                 default:
 451                         throw Exception("Piece::type2str", "Unknown type %d", (int)t);
 452                         return "";
 453         }
 454 }
 455
 456 /**
 457  * @funct str2colour
 458  * @purpose Convert string to Piece::Colour
 459  * @param str - The string
 460  * @returns A Piece::Colour
 461  */
 462 Piece::Colour Piece::str2colour(const string & str)
 463 {
 464         if (str == "white")
 465                 return Piece::WHITE;
 466         else if (str == "black")
 467                 return Piece::BLACK;
 468
 469         throw Exception("Piece::str2colour", "string \"%s\" is not white|black", str.c_str());
 470         return Piece::BLACK; // should never get here
 471 }
 472
 473 /**
 474  * @funct AddPiece
 475  * @purpose Creates a new Piece and adds it to a vector
 476  * @param v - The vector
 477  * @params - All remaining parameters passed to Piece::Piece
 478  * @returns Pointer to the new Piece
 479  */
 480 Piece * Piece::AddPiece(vector<Piece*> & v, int x, int y, const Piece::Colour & colour, const Piece::Type & t1, const Piece::Type & t2,
 481                         int type_index)
 482 {
 483         Piece * p = new Piece(x,y,colour,t1, t2,type_index, v.size());
 484         v.push_back(p);
 485         return p;
 486 }
 487
 488 /**
 489  * @funct Clone_copy
 490  * @purpose If necessary, copy the piece in the square
 491  * @param s - The square
 492  */
 493 void Board::Clone_copy(Square & s)
 494 {
 495         if (s.piece == NULL || !IsClone()) return;
 496         if (parent->grid[s.x][s.y].piece == s.piece)
 497         {
 498                 s.piece = new Piece(*(s.piece));
 499                 vector<Piece*> & v = pieces(s.piece->colour);
 500                 v[s.piece->piece_index] = s.piece;
 501         }
 502
 503 }