2 * agent++ : A Sample agent for UCC::Progcomp2013
4 * @purpose Definitions for game related classes; Piece, Square, Board
13 Piece::Type Piece::AllTypes[] = {PAWN, BISHOP, KNIGHT, ROOK, QUEEN, KING, UNKNOWN};
14 Piece::Colour Piece::AllColours[] = {WHITE, BLACK};
18 * @param new_x, new_y - Position of piece
19 * @param new_colour - Colour of piece
20 * @param type1, type2 - Types of piece
21 * @param new_type_index - Index for initial type of piece
22 * @param new_piece_index - Index for piece in a vector
24 Piece::Piece(int new_x, int new_y, const Piece::Colour & new_colour, const Piece::Type & type1, const Piece::Type & type2,
26 : x(new_x), y(new_y), colour(new_colour), type_index(new_type_index), types(), current_type()
28 types[0] = type1; types[1] = type2;
29 if (type_index < 0 || type_index >= 2)
31 current_type = Piece::UNKNOWN;
35 current_type = types[type_index];
41 * @param cpy - Piece to copy construct from
43 Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_index(cpy.type_index)
45 types[0] = cpy.types[0];
46 types[1] = cpy.types[1];
51 * @param choose_types - Indicates whether Board should setup the 2nd types of pieces; default false
53 Board::Board(bool choose_types)
54 : white(), black(), white_unknown(), black_unknown(), white_nUnknown(0), black_nUnknown(0),
55 white_king(NULL), black_king(NULL)
58 // initialise all the Squares
59 for (int x = 0; x < BOARD_WIDTH; ++x)
61 for (int y = 0; y < BOARD_HEIGHT; ++y)
68 // const arrays simplify below code
71 // frequency of each type of piece
72 map<Piece::Type, int> freq;
73 freq[Piece::ROOK] = 2;
74 freq[Piece::BISHOP] = 2;
75 freq[Piece::KNIGHT] = 2;
76 freq[Piece::QUEEN] = 1;
77 freq[Piece::PAWN] = 8;
87 // for white and black...
88 for (int i = 0; i < 2; ++i)
90 vector<Piece*> & v = pieces(Piece::AllColours[i]); // get vector of pieces
95 int y = (i == 0) ? 1 : BOARD_HEIGHT-2;
96 for (int x = 0; x < BOARD_WIDTH; ++x)
98 Piece::AddPiece(v, x, y, Piece::AllColours[i], Piece::PAWN, Piece::UNKNOWN);
102 y = (i == 0) ? 0 : BOARD_HEIGHT-1;
103 Piece::AddPiece(v, 0, y, Piece::AllColours[i], Piece::ROOK, Piece::UNKNOWN);
104 Piece::AddPiece(v, BOARD_WIDTH-1, y, Piece::AllColours[i], Piece::ROOK, Piece::UNKNOWN);
105 Piece::AddPiece(v, 1, y, Piece::AllColours[i], Piece::KNIGHT, Piece::UNKNOWN);
106 Piece::AddPiece(v, BOARD_WIDTH-2, y, Piece::AllColours[i], Piece::KNIGHT, Piece::UNKNOWN);
107 Piece::AddPiece(v, 2, y, Piece::AllColours[i], Piece::BISHOP, Piece::UNKNOWN);
108 Piece::AddPiece(v, BOARD_WIDTH-3, y, Piece::AllColours[i], Piece::BISHOP, Piece::UNKNOWN);
109 Piece::AddPiece(v, 3, y, Piece::AllColours[i], Piece::QUEEN, Piece::UNKNOWN);
111 Piece * k = Piece::AddPiece(v, 4, y, Piece::AllColours[i], Piece::KING, Piece::KING, 1);
118 // add to board and choose second types if required
119 map<Piece::Type, int> f(freq);
121 for (unsigned j = 0; j < v.size(); ++j)
124 grid[p->x][p->y].piece = p;
127 if (p->types[1] != Piece::UNKNOWN)
133 } while (f[Piece::AllTypes[type2]] <= 0);
134 f[Piece::AllTypes[type2]] -= 1;
136 p->types[1] = Piece::AllTypes[type2];
150 * @param cpy - Board to clone
152 Board::Board(Board & cpy)
153 : white(cpy.white), black(cpy.black), white_unknown(cpy.white_unknown), black_unknown(cpy.black_unknown),
154 white_nUnknown(cpy.white_nUnknown), black_nUnknown(cpy.black_nUnknown),
155 white_king(cpy.white_king), black_king(cpy.black_king)
157 for (int x = 0; x < BOARD_WIDTH; ++x)
159 for (int y = 0; y < BOARD_HEIGHT; ++y)
163 if (cpy.grid[x][y].piece != NULL)
165 vector<Piece*> & v = pieces(cpy.grid[x][y].piece->colour);
166 Piece::AddPiece(v, *(cpy.grid[x][y].piece));
179 for (int x = 0; x < BOARD_WIDTH; ++x)
181 for (int y = 0; y < BOARD_HEIGHT; ++y)
183 delete grid[x][y].piece;
190 * @funct Update_select
191 * @purpose Update Piece that has been selected
192 * @param x, y - Position of Piece to update
193 * @param index - 0 or 1 - State the Piece "collapsed" into
194 * @param type - Type of the Piece as a string
196 void Board::Update_select(int x, int y, int index, const string & type)
198 Board::Update_select(x, y, index, Piece::str2type(type));
202 * @funct Update_select
203 * @purpose Update Piece that has been selected
204 * @param x, y - Position of Piece to update
205 * @param index - 0 or 1 - State the Piece "collapsed" into
206 * @param t - Type of the Piece
208 void Board::Update_select(int x, int y, int index, const Piece::Type & t)
210 cerr << "Updating " << x << "," << y << " " << grid[x][y].piece << " " << index << " " << t << "\n";
211 Square & s = grid[x][y];
215 assert(s.piece != NULL);
216 assert(index >= 0 && index < 2);
217 s.piece->type_index = index;
219 if (s.piece->types[index] == Piece::UNKNOWN)
221 map<Piece::Type, int> & m = unknown_types(s.piece->colour);
224 throw Exception("Board::Update_select", "Too many pieces of type %s found", Piece::type2str(t));
226 nUnknown(s.piece->colour)--;
229 s.piece->types[index] = t;
230 s.piece->current_type = t;
232 for (int x = 0; x < BOARD_WIDTH; ++x)
234 for (int y = 0; y < BOARD_HEIGHT; ++y)
236 grid[x][y].Update_coverage(*this);
243 * @purpose Move a Piece from one square to another
244 * @param x1, y1 - Coords of Square containing moving Piece
245 * @param x2, y2 - Coords of Square to move into
246 * NOTE: Any Piece in the destination Square will be destroyed ("taken")
247 * and the Board's other members updated accordingly
249 void Board::Update_move(int x1, int y1, int x2, int y2)
251 Square & s1 = grid[x1][y1];
252 Square & s2 = grid[x2][y2];
258 if (s2.piece != NULL)
260 vector<Piece*> & p = pieces(s2.piece->colour);
261 vector<Piece*>::iterator i = p.begin();
272 Piece * k = king(s2.piece->colour);
275 if (k->colour == Piece::WHITE)
290 for (int x = 0; x < BOARD_WIDTH; ++x)
292 for (int y = 0; y < BOARD_HEIGHT; ++y)
294 grid[x][y].Update_coverage(*this);
298 if ((s2.x + s2.y % 2) == 0)
300 s2.piece->type_index = -1;
301 s2.piece->current_type = Piece::UNKNOWN;
307 * @purpose Get all moves for a Piece and store them
309 * @param v - vector to store Squares in. Will *not* be cleared.
311 void Board::Get_moves(Piece * p, vector<Square*> & v)
313 assert(p->current_type != Piece::UNKNOWN);
314 Board::Get_moves(grid[p->x][p->y], p->current_type, v);
319 * @purpose Get moves from a square for piece of specified type
322 * @param v - Vector to store squares in. Will *not* be cleared.
324 void Board::Get_moves(Square & s, const Piece::Type & t, vector<Square*> & v)
326 int x = s.x; int y = s.y;
329 if (t == Piece::KING)
331 CheckMove(p, x+1, y, v);
332 CheckMove(p, x-1, y, v);
333 CheckMove(p, x, y+1, v);
334 CheckMove(p, x, y-1, v);
335 CheckMove(p, x+1, y+1, v);
336 CheckMove(p, x+1, y-1, v);
337 CheckMove(p, x-1, y+1, v);
338 CheckMove(p, x-1, y-1, v);
340 else if (t == Piece::KNIGHT)
342 CheckMove(p, x+2, y+1, v);
343 CheckMove(p, x+2, y-1, v);
344 CheckMove(p, x-2, y+1, v);
345 CheckMove(p, x-2, y-1, v);
346 CheckMove(p, x+1, y+2, v);
347 CheckMove(p, x-1, y+2, v);
348 CheckMove(p, x+1, y-2, v);
349 CheckMove(p, x-1, y-2, v);
351 else if (t == Piece::PAWN)
353 int y1 = (p->colour == Piece::WHITE) ? BOARD_HEIGHT-2 : 1;
354 int y2 = (p->colour == Piece::WHITE) ? y1 - 2 : y1 + 2;
355 if (p->types[0] == Piece::PAWN && p->y == y1)
358 CheckMove(p, x, y2, v);
360 y2 = (p->colour == Piece::WHITE) ? y - 1 : y + 1;
361 CheckMove(p, x, y2, v);
363 if (Valid_position(x-1, y2) && grid[x-1][y2].piece != NULL)
364 CheckMove(p, x-1, y2, v);
365 if (Valid_position(x+1, y2) && grid[x+1][y2].piece != NULL)
366 CheckMove(p, x+1, y2, v);
368 else if (t == Piece::BISHOP)
370 ScanMoves(p, 1, 1, v);
371 ScanMoves(p, 1, -1, v);
372 ScanMoves(p, -1, 1, v);
373 ScanMoves(p, -1, -1, v);
375 else if (t == Piece::ROOK)
377 ScanMoves(p, 1, 0, v);
378 ScanMoves(p, -1, 0, v);
379 ScanMoves(p, 0, 1, v);
380 ScanMoves(p, 0, -1, v);
382 else if (t == Piece::QUEEN)
384 ScanMoves(p, 1, 1, v);
385 ScanMoves(p, 1, -1, v);
386 ScanMoves(p, -1, 1, v);
387 ScanMoves(p, -1, -1, v);
388 ScanMoves(p, 1, 0, v);
389 ScanMoves(p, -1, 0, v);
390 ScanMoves(p, 0, 1, v);
391 ScanMoves(p, 0, -1, v);
398 * @purpose Add a move to the vector, if it is valid
399 * @param p - Piece that would move
400 * @param x, y - Destination Square coords
401 * @param v - vector to put the destination Square in, if the move is valid
403 void Board::CheckMove(Piece * p, int x, int y, vector<Square*> & v)
405 if (Valid_position(x, y) && (grid[x][y].piece == NULL || p == NULL || grid[x][y].piece->colour != p->colour))
407 v.push_back(&(grid[x][y]));
410 // cerr << "Square " << x << "," << y << " invalid; " << grid[x][y].piece << "\n";
415 * @purpose Add moves in a specified direction to the vector, until we get to an invalid move
416 * @param p - Piece to start scanning from
417 * @param vx, vy - "velocity" - change in coords each move
418 * @param v - vector to store valid Squares in
420 void Board::ScanMoves(Piece * p, int vx, int vy, vector<Square*> & v)
424 while (Valid_position(x, y) && (grid[x][y].piece == NULL || p == NULL || grid[x][y].piece->colour != p->colour))
426 v.push_back(&(grid[x][y]));
427 if (grid[x][y].piece != NULL)
436 * @purpose Scan in a direction until we either hit a piece or go off the board
437 * @param s - Square to start scanning from
438 * @param vx, vy - "velocity" - change in coords each move
440 Piece * Board::ScanPiece(Square & s, int vx, int vy)
444 while (Valid_position(x, y))
446 if (grid[x][y].piece != NULL)
447 return grid[x][y].piece;
456 * @purpose Convert string to Piece::Type
457 * @param str - The string
458 * @returns A Piece::Type
460 Piece::Type Piece::str2type(const string & str)
464 else if (str == "queen")
466 else if (str == "rook")
468 else if (str == "bishop")
469 return Piece::BISHOP;
470 else if (str == "knight")
471 return Piece::KNIGHT;
472 else if (str == "pawn")
474 else if (str == "unknown")
475 return Piece::UNKNOWN;
477 throw Exception("Piece::str2type", "String \"%s\" doesn't represent a type", str.c_str());
478 return Piece::UNKNOWN;
483 * @purpose Convert Piece::Type to string
484 * @param t - The Types
485 * @returns a const char*
487 const char * Piece::type2str(const Piece::Type & t)
506 throw Exception("Piece::type2str", "Unknown type %d", (int)t);
513 * @purpose Convert string to Piece::Colour
514 * @param str - The string
515 * @returns A Piece::Colour
517 Piece::Colour Piece::str2colour(const string & str)
521 else if (str == "black")
524 throw Exception("Piece::str2colour", "string \"%s\" is not white|black", str.c_str());
525 return Piece::BLACK; // should never get here
530 * @purpose Creates a new Piece and adds it to a vector
531 * @param v - The vector
532 * @params - All remaining parameters passed to Piece::Piece
533 * @returns Pointer to the new Piece
535 Piece * Piece::AddPiece(vector<Piece*> & v, int x, int y, const Piece::Colour & colour, const Piece::Type & t1, const Piece::Type & t2,
538 Piece * p = new Piece(x,y,colour,t1, t2,type_index);
545 * @purpose Copy a Piece and add it to a vector
546 * @param v - The vector
547 * @param cpy - Piece to copy
548 * @returns Pointer to the new Piece
550 Piece * Piece::AddPiece(vector<Piece*> & v, const Piece & cpy)
552 Piece * p = new Piece(cpy);
558 * @funct Update_coverage
559 * @purpose Update the map of Pieces that cover a square
560 * @param b - Board to use for updating
563 void Square::Update_coverage(Board & b)
565 coverage[Piece::WHITE].clear();
566 coverage[Piece::BLACK].clear();
569 static int directions[][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
573 for (unsigned i = 0; i < sizeof(directions); ++i)
575 Piece * p = b.ScanPiece(*this, directions[i][0], directions[i][1]);
580 // take care of kings
581 if (abs(p->x - x) + abs(p->y - y) && p->current_type == Piece::KING)
583 coverage[p->colour][p] = 1.0;
594 prob = p->ProbIsType(b,Piece::ROOK) + p->ProbIsType(b,Piece::QUEEN);
595 if (i == 2 && p->colour == Piece::WHITE)
597 if (abs(y - p->y) < 1 || ((p->y == BOARD_HEIGHT-2 && abs(y - p->y) == 2)))
598 prob += p->ProbIsType(b,Piece::PAWN);
600 if (i == 3 && p->colour == Piece::BLACK)
602 if (abs(y - p->y) < 1 || ((p->y == 1 && abs(y - p->y) == 2)))
603 prob += p->ProbIsType(b,Piece::PAWN);
607 coverage[p->colour][p] = prob;
615 prob = p->ProbIsType(b,Piece::BISHOP) + p->ProbIsType(b,Piece::QUEEN);
616 if ((i == 4 || i == 6) && p->colour == Piece::WHITE)
618 if (abs(y - p->y) == 1 && abs(x - p->x) == 1)
619 prob += p->ProbIsType(b, Piece::PAWN);
621 if ((i == 5 || i == 7) && p->colour == Piece::BLACK)
623 if (abs(y - p->y) == 1 && abs(x - p->x) == 1)
624 prob += p->ProbIsType(b, Piece::PAWN);
628 coverage[p->colour][p] = prob;
635 static int knight_pos[][2] = {{-1,2},{1,2},{-1,-2},{-1,2}, {-2,1},{-2,-1},{2,1},{2,-1}};
636 for (unsigned i = 0; i < sizeof(knight_pos); ++i)
638 if (!b.Valid_position(x+knight_pos[i][0], y+knight_pos[i][1]))
641 Piece * p = b.SquareAt(x+knight_pos[i][0],y+knight_pos[i][1]).piece;
644 double prob = p->ProbIsType(b, Piece::KNIGHT);
646 coverage[p->colour][p] = prob;
655 * @purpose Determine the probability that a Piece will become the specified type on its next selection
656 * @param b - Board to use to calculate probabilities
657 * @param t - The type
658 * @returns Probability that the piece's type becomes t on its next selection taking into account unknown types
660 double Piece::ProbIsType(Board & b, const Piece::Type & t)
662 if (current_type != Piece::UNKNOWN)
663 return (current_type == t) ? 1.0 : 0.0;
667 map<Piece::Type, int> & m = b.unknown_types(colour);
668 int nUnknown = b.nUnknown(colour);
669 for (unsigned i = 0; i < sizeof(types); ++i)
671 if (types[i] != Piece::UNKNOWN)
673 prob += (1.0 / double(sizeof(types))) * (double)(types[i] == t);
677 prob += (1.0 / double(sizeof(types))) * (m[t] / double(nUnknown));
685 * @purpose Return square at a position on the board
689 Square & Board::SquareAt(int x, int y)
691 if (!Valid_position(x, y))
692 throw Exception("Board::SquareAt", "Invalid position %d,%d", x, y);