From: Sam Moore Date: Fri, 5 Apr 2013 13:30:54 +0000 (+0800) Subject: Did something, apparently X-Git-Url: https://git.ucc.asn.au/?p=progcomp2013.git;a=commitdiff_plain;h=7a6c3dd98ba430b9bcdf95b7a92100cb7c0a1bbe;hp=6632f3437f19a985d3b6b311b30bc1bafbca0002 Did something, apparently --- diff --git a/agents/c++/agent++ b/agents/c++/agent++ index 956a644..2f2ebeb 100755 Binary files a/agents/c++/agent++ and b/agents/c++/agent++ differ diff --git a/agents/c++/qchess.cpp b/agents/c++/qchess.cpp index f908756..922d0c3 100644 --- a/agents/c++/qchess.cpp +++ b/agents/c++/qchess.cpp @@ -19,8 +19,8 @@ using namespace std; * @param new_piece_index - Index for piece in a vector */ Piece::Piece(int new_x, int new_y, const Piece::Colour & new_colour, const Piece::Type & type1, const Piece::Type & type2, - int new_type_index, int new_piece_index) - : x(new_x), y(new_y), colour(new_colour), type_index(new_type_index), types(), current_type(), piece_index(new_piece_index) + int new_type_index) + : x(new_x), y(new_y), colour(new_colour), type_index(new_type_index), types(), current_type() { types[0] = type1; types[1] = type2; if (type_index < 0 || type_index >= 2) @@ -37,7 +37,7 @@ Piece::Piece(int new_x, int new_y, const Piece::Colour & new_colour, const Piece * @constructor * @param cpy - Piece to copy construct from */ -Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_index(cpy.type_index), piece_index(cpy.piece_index) +Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_index(cpy.type_index) { types[0] = cpy.types[0]; types[1] = cpy.types[1]; @@ -49,7 +49,7 @@ Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_i */ Board::Board(bool choose_types) : white(), black(), white_unknown(), black_unknown(), white_nUnknown(0), black_nUnknown(0), - white_king(NULL), black_king(NULL), parent(NULL) + white_king(NULL), black_king(NULL) { // initialise all the Squares @@ -150,7 +150,7 @@ Board::Board(bool choose_types) Board::Board(Board & cpy) : white(cpy.white), black(cpy.black), white_unknown(cpy.white_unknown), black_unknown(cpy.black_unknown), white_nUnknown(cpy.white_nUnknown), black_nUnknown(cpy.black_nUnknown), - white_king(cpy.white_king), black_king(cpy.black_king), parent(&cpy) + white_king(cpy.white_king), black_king(cpy.black_king) { for (int x = 0; x < BOARD_WIDTH; ++x) { @@ -158,7 +158,11 @@ Board::Board(Board & cpy) { grid[x][y].x = x; grid[x][y].y = y; - grid[x][y].piece = cpy.grid[x][y].piece; + if (cpy.grid[x][y].piece != NULL) + { + vector & v = pieces(cpy.grid[x][y].piece->colour); + Piece::AddPiece(v, *(cpy.grid[x][y].piece)); + } } } } @@ -204,7 +208,7 @@ void Board::Update_select(int x, int y, int index, const Piece::Type & t) cerr << "Updating " << x << "," << y << " " << grid[x][y].piece << " " << index << " " << t << "\n"; Square & s = grid[x][y]; - Clone_copy(s); + assert(s.piece != NULL); assert(index >= 0 && index < 2); @@ -237,7 +241,6 @@ void Board::Update_move(int x1, int y1, int x2, int y2) Square & s1 = grid[x1][y1]; Square & s2 = grid[x2][y2]; - Clone_copy(s1); @@ -255,11 +258,7 @@ void Board::Update_move(int x1, int y1, int x2, int y2) } ++i; } - while (i != p.end()) - { - (*i)->piece_index -= 1; - ++i; - } + Piece * k = king(s2.piece->colour); if (k == s2.piece) { @@ -268,10 +267,8 @@ void Board::Update_move(int x1, int y1, int x2, int y2) else black_king = NULL; } - if ((IsClone() && s2.piece == parent->grid[x2][y2].piece) == false) - { - delete s2.piece; - } + delete s2.piece; + } s1.piece->x = s2.x; @@ -290,6 +287,7 @@ void Board::Update_move(int x1, int y1, int x2, int y2) void Board::Get_moves(Piece * p, vector & v) { assert(p->current_type != Piece::UNKNOWN); + int x = p->x; int y = p->y; if (p->current_type == Piece::KING) { @@ -480,24 +478,21 @@ Piece::Colour Piece::str2colour(const string & str) Piece * Piece::AddPiece(vector & v, int x, int y, const Piece::Colour & colour, const Piece::Type & t1, const Piece::Type & t2, int type_index) { - Piece * p = new Piece(x,y,colour,t1, t2,type_index, v.size()); + Piece * p = new Piece(x,y,colour,t1, t2,type_index); v.push_back(p); return p; } /** - * @funct Clone_copy - * @purpose If necessary, copy the piece in the square - * @param s - The square + * @funct AddPiece + * @purpose Copy a Piece and add it to a vector + * @param v - The vector + * @param cpy - Piece to copy + * @returns Pointer to the new Piece */ -void Board::Clone_copy(Square & s) +Piece * Piece::AddPiece(vector & v, const Piece & cpy) { - if (s.piece == NULL || !IsClone()) return; - if (parent->grid[s.x][s.y].piece == s.piece) - { - s.piece = new Piece(*(s.piece)); - vector & v = pieces(s.piece->colour); - v[s.piece->piece_index] = s.piece; - } - + Piece * p = new Piece(cpy); + v.push_back(p); + return p; } \ No newline at end of file diff --git a/agents/c++/qchess.h b/agents/c++/qchess.h index 40b09f1..31ab7a9 100644 --- a/agents/c++/qchess.h +++ b/agents/c++/qchess.h @@ -45,14 +45,14 @@ class Piece static const char * type2str(const Type & t); static Piece * AddPiece(std::vector & v, int x, int y, const Colour & colour, const Type & type1, const Type & type2, int type_index=-1); + static Piece * AddPiece(std::vector & v, const Piece & cpy); private: friend class Board; Piece(int x, int y, const Colour & colour, const Type & type1, const Type & type2 - , int type_index, int new_piece_index); // constructor + , int type_index); // constructor Piece(const Piece & cpy); // copy constructor - - int piece_index; // index of the piece in Board's pieces vector + }; @@ -111,8 +111,7 @@ class Board // determine if position is on the board bool Valid_position(int x, int y) {return (x >= 0 && x <= BOARD_WIDTH-1 && y >= 0 && y <= BOARD_HEIGHT-1);} - bool IsClone() const {return parent != NULL;} - void Clone_copy(Square & s); + private: Square grid[BOARD_WIDTH][BOARD_HEIGHT]; @@ -128,7 +127,7 @@ class Board Piece * white_king; Piece * black_king; - Board * parent; + // Add a move to the vector if it is valid void Move(Piece * p, int x, int y, std::vector & v); diff --git a/agents/silverfish/Makefile b/agents/silverfish/Makefile index e2c4927..196cdca 100644 --- a/agents/silverfish/Makefile +++ b/agents/silverfish/Makefile @@ -11,7 +11,7 @@ BIN = silver $(BIN) : $(LINKOBJ) - $(CXX) -o $(BIN) $(LINKOBJ) + $(CXX) -o $(BIN) $(LINKOBJ) $(LIB) %.o : %.cpp $(CXX) -c $< diff --git a/agents/silverfish/agent.cpp b/agents/silverfish/agent.cpp deleted file mode 120000 index 9851ddc..0000000 --- a/agents/silverfish/agent.cpp +++ /dev/null @@ -1 +0,0 @@ -../c++/agent.cpp \ No newline at end of file diff --git a/agents/silverfish/agent.cpp b/agents/silverfish/agent.cpp new file mode 100644 index 0000000..2014f55 --- /dev/null +++ b/agents/silverfish/agent.cpp @@ -0,0 +1,113 @@ +/** + * agent++ : A Sample agent for UCC::Progcomp2013 + * @file agent.cpp + * @purpose Definition of Agent class + */ + +#include "agent.h" +#include // for sanity checks + +using namespace std; + +/** + * @constructor Agent + * @param new_colour - colour of the Agent + */ +Agent::Agent(const string & new_colour) : colour(Piece::str2colour(new_colour)), board(), selected(NULL) +{ + +} + +/** + * @destructor ~Agent + */ +Agent::~Agent() +{ + +} + +/** + * @funct Select + * @purpose Selects a piece at random + * @returns Square containing the selected piece + */ +Square & Agent::Select() +{ + vector & v = board.pieces(colour); // get pieces + int choice = rand() % v.size(); // pick random index + Piece * p = v[choice]; // get piece at the index + assert(p->colour == colour); + selected = p; // update selected + //cerr << "Selected " << p->x << "," << p->y << " [" << p->types[0] << "," << p->types[1] << "]\n"; + return board.square(p->x, p->y); // get Square from board +} + +/** + * @funct Move + * @purpose Pick a square to move a selected piece into + * @returns Square to move last selected piece into + */ +Square & Agent::Move() +{ + assert(selected != NULL); + vector moves; // all possible moves for selected piece + board.Get_moves(selected, moves); // populate possible moves + assert(moves.size() > 0); + int choice = rand() % moves.size(); // pick random index + return *(moves[choice]); // return that move +} + +/** + * @funct Run + * @purpose The "Game Loop" for the agent; read commands and call appropriate function to make responses + * @param in - Stream to read input from (use std::cin) + * @param out - Stream to write output to (use std::cout) + */ +void Agent::Run(istream & in, ostream & out) +{ + string cmd; // buffer for tokens + while (in.good()) + { + in >> cmd; // read first token only + if (cmd == "QUIT") + { + break; + } + else if (cmd == "SELECTION?") + { + Square & s = Select(); // get selection + out << s.x << " " << s.y << "\n"; // return response through output + } + else if (cmd == "MOVE?") + { + Square & s = Move(); // get move + out << s.x << " " << s.y << "\n"; // return response through output + } + else + { + // There were multiple tokens... + stringstream s(cmd); + int x; int y; + s >> x; // Convert first token (in cmd) to an int + in >> y; // Read second token from in + + in >> cmd; // Read third token + + if (cmd == "->") // Token indicates a move was made + { + int x2; int y2; // remaining two tokens indicate destination + in >> x2; in >> y2; + board.Update_move(x, y, x2, y2); // update the board + } + else + { + // Tokens are for a selection + int index; stringstream s2(cmd); + s2 >> index; // convert third token to an index + in >> cmd; // Read fourth token - the new type of the piece + board.Update_select(x, y, index, cmd); // update the board + } + + } + } +} diff --git a/agents/silverfish/agent.h b/agents/silverfish/agent.h deleted file mode 120000 index 8fbe3b6..0000000 --- a/agents/silverfish/agent.h +++ /dev/null @@ -1 +0,0 @@ -../c++/agent.h \ No newline at end of file diff --git a/agents/silverfish/agent.h b/agents/silverfish/agent.h new file mode 100644 index 0000000..9c05edd --- /dev/null +++ b/agents/silverfish/agent.h @@ -0,0 +1,39 @@ +/** + * agent++ : A Sample agent for UCC::Progcomp2013 + * @file agent.h + * @purpose Declaration of Agent class + */ + +#ifndef _AGENT_H +#define _AGENT_H + +#include +#include +#include "qchess.h" // Declarations of Board, Piece and Square classes; see also qchess.cpp + +/** + * @class Agent + * @purpose Class that represents an agent which will play qchess + */ +class Agent +{ + public: + Agent(const std::string & colour); // initialise with colour + virtual ~Agent(); // destructor + + void Run(std::istream & in, std::ostream & out); // agent run loop, specify input and output streams + + virtual Square & Select(); // select a square (default: random square containing one of my pieces) + virtual Square & Move(); // select a move (default: random valid move for selected piece) + + + protected: + const Piece::Colour colour; // colour of the agent; do not change it + Board board; // board, see qchess.h + Piece * selected; // last piece chosen by Agent::Select, see qchess.h + +}; + +#endif //_AGENT_H + +//EOF diff --git a/agents/silverfish/main.cpp b/agents/silverfish/main.cpp index 7d24493..f6887b4 100644 --- a/agents/silverfish/main.cpp +++ b/agents/silverfish/main.cpp @@ -9,6 +9,7 @@ #include "silverfish.h" + using namespace std; /** @@ -20,6 +21,8 @@ using namespace std; int main(int argc, char ** argv) { srand(time(NULL)); // seed random number generator + + string colour; cin >> colour; // first read the colour of the agent diff --git a/agents/silverfish/qchess.cpp b/agents/silverfish/qchess.cpp deleted file mode 120000 index a770972..0000000 --- a/agents/silverfish/qchess.cpp +++ /dev/null @@ -1 +0,0 @@ -../c++/qchess.cpp \ No newline at end of file diff --git a/agents/silverfish/qchess.cpp b/agents/silverfish/qchess.cpp new file mode 100644 index 0000000..2f2a33b --- /dev/null +++ b/agents/silverfish/qchess.cpp @@ -0,0 +1,694 @@ +/** + * agent++ : A Sample agent for UCC::Progcomp2013 + * @file qchess.h + * @purpose Definitions for game related classes; Piece, Square, Board + */ + +#include "qchess.h" +#include + +using namespace std; + + +Piece::Type Piece::AllTypes[] = {PAWN, BISHOP, KNIGHT, ROOK, QUEEN, KING, UNKNOWN}; +Piece::Colour Piece::AllColours[] = {WHITE, BLACK}; + +/** + * @constructor + * @param new_x, new_y - Position of piece + * @param new_colour - Colour of piece + * @param type1, type2 - Types of piece + * @param new_type_index - Index for initial type of piece + * @param new_piece_index - Index for piece in a vector + */ +Piece::Piece(int new_x, int new_y, const Piece::Colour & new_colour, const Piece::Type & type1, const Piece::Type & type2, + int new_type_index) + : x(new_x), y(new_y), colour(new_colour), type_index(new_type_index), types(), current_type() +{ + types[0] = type1; types[1] = type2; + if (type_index < 0 || type_index >= 2) + { + current_type = Piece::UNKNOWN; + } + else + { + current_type = types[type_index]; + } +} + +/** + * @constructor + * @param cpy - Piece to copy construct from + */ +Piece::Piece(const Piece & cpy) : x(cpy.x), y(cpy.y), colour(cpy.colour), type_index(cpy.type_index) +{ + types[0] = cpy.types[0]; + types[1] = cpy.types[1]; +} + +/** + * @constructor + * @param choose_types - Indicates whether Board should setup the 2nd types of pieces; default false + */ +Board::Board(bool choose_types) + : white(), black(), white_unknown(), black_unknown(), white_nUnknown(0), black_nUnknown(0), + white_king(NULL), black_king(NULL) +{ + + // initialise all the Squares + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + grid[x][y].x = x; + grid[x][y].y = y; + } + } + + // const arrays simplify below code + + + // frequency of each type of piece + map freq; + freq[Piece::ROOK] = 2; + freq[Piece::BISHOP] = 2; + freq[Piece::KNIGHT] = 2; + freq[Piece::QUEEN] = 1; + freq[Piece::PAWN] = 8; + + if (!choose_types) + { + white_unknown = freq; + black_unknown = freq; + white_nUnknown = 15; + black_nUnknown = 15; + } + + // for white and black... + for (int i = 0; i < 2; ++i) + { + vector & v = pieces(Piece::AllColours[i]); // get vector of pieces + + + + // add pawns + int y = (i == 0) ? 1 : BOARD_HEIGHT-2; + for (int x = 0; x < BOARD_WIDTH; ++x) + { + Piece::AddPiece(v, x, y, Piece::AllColours[i], Piece::PAWN, Piece::UNKNOWN); + } + + // add other pieces + y = (i == 0) ? 0 : BOARD_HEIGHT-1; + Piece::AddPiece(v, 0, y, Piece::AllColours[i], Piece::ROOK, Piece::UNKNOWN); + Piece::AddPiece(v, BOARD_WIDTH-1, y, Piece::AllColours[i], Piece::ROOK, Piece::UNKNOWN); + Piece::AddPiece(v, 1, y, Piece::AllColours[i], Piece::KNIGHT, Piece::UNKNOWN); + Piece::AddPiece(v, BOARD_WIDTH-2, y, Piece::AllColours[i], Piece::KNIGHT, Piece::UNKNOWN); + Piece::AddPiece(v, 2, y, Piece::AllColours[i], Piece::BISHOP, Piece::UNKNOWN); + Piece::AddPiece(v, BOARD_WIDTH-3, y, Piece::AllColours[i], Piece::BISHOP, Piece::UNKNOWN); + Piece::AddPiece(v, 3, y, Piece::AllColours[i], Piece::QUEEN, Piece::UNKNOWN); + + Piece * k = Piece::AddPiece(v, 4, y, Piece::AllColours[i], Piece::KING, Piece::KING, 1); + if (i == 0) + white_king = k; + else + black_king = k; + + + // add to board and choose second types if required + map f(freq); + int type2; + for (unsigned j = 0; j < v.size(); ++j) + { + Piece * p = v[j]; + grid[p->x][p->y].piece = p; + if (choose_types) + { + if (p->types[1] != Piece::UNKNOWN) + continue; + + do + { + type2 = rand() % 5; + } while (f[Piece::AllTypes[type2]] <= 0); + f[Piece::AllTypes[type2]] -= 1; + + p->types[1] = Piece::AllTypes[type2]; + } + + + } + + + + } + +} + +/** + * @constructor + * @param cpy - Board to clone + */ +Board::Board(Board & cpy) +: white(cpy.white), black(cpy.black), white_unknown(cpy.white_unknown), black_unknown(cpy.black_unknown), + white_nUnknown(cpy.white_nUnknown), black_nUnknown(cpy.black_nUnknown), + white_king(cpy.white_king), black_king(cpy.black_king) +{ + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + grid[x][y].x = x; + grid[x][y].y = y; + if (cpy.grid[x][y].piece != NULL) + { + vector & v = pieces(cpy.grid[x][y].piece->colour); + Piece::AddPiece(v, *(cpy.grid[x][y].piece)); + } + } + } +} + +/** + * @destructor + */ +Board::~Board() +{ + white.clear(); + black.clear(); + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + delete grid[x][y].piece; + } + } + +} + +/** + * @funct Update_select + * @purpose Update Piece that has been selected + * @param x, y - Position of Piece to update + * @param index - 0 or 1 - State the Piece "collapsed" into + * @param type - Type of the Piece as a string + */ +void Board::Update_select(int x, int y, int index, const string & type) +{ + Board::Update_select(x, y, index, Piece::str2type(type)); +} + +/** + * @funct Update_select + * @purpose Update Piece that has been selected + * @param x, y - Position of Piece to update + * @param index - 0 or 1 - State the Piece "collapsed" into + * @param t - Type of the Piece + */ +void Board::Update_select(int x, int y, int index, const Piece::Type & t) +{ + cerr << "Updating " << x << "," << y << " " << grid[x][y].piece << " " << index << " " << t << "\n"; + Square & s = grid[x][y]; + + + + assert(s.piece != NULL); + assert(index >= 0 && index < 2); + s.piece->type_index = index; + + if (s.piece->types[index] == Piece::UNKNOWN) + { + map & m = unknown_types(s.piece->colour); + int n = (m[t]--); + if (n < 0) + throw Exception("Board::Update_select", "Too many pieces of type %s found", Piece::type2str(t)); + + nUnknown(s.piece->colour)--; + + } + s.piece->types[index] = t; + s.piece->current_type = t; + + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + grid[x][y].Update_coverage(*this); + } + } +} + +/** + * @funct Update_move + * @purpose Move a Piece from one square to another + * @param x1, y1 - Coords of Square containing moving Piece + * @param x2, y2 - Coords of Square to move into + * NOTE: Any Piece in the destination Square will be destroyed ("taken") + * and the Board's other members updated accordingly + */ +void Board::Update_move(int x1, int y1, int x2, int y2) +{ + Square & s1 = grid[x1][y1]; + Square & s2 = grid[x2][y2]; + + + + + + if (s2.piece != NULL) + { + vector & p = pieces(s2.piece->colour); + vector::iterator i = p.begin(); + while (i != p.end()) + { + if (*i == s2.piece) + { + p.erase(i); + break; + } + ++i; + } + + Piece * k = king(s2.piece->colour); + if (k == s2.piece) + { + if (k->colour == Piece::WHITE) + white_king = NULL; + else + black_king = NULL; + } + delete s2.piece; + + } + + s1.piece->x = s2.x; + s1.piece->y = s2.y; + + s2.piece = s1.piece; + s1.piece = NULL; + + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + grid[x][y].Update_coverage(*this); + } + } + + if ((s2.x + s2.y % 2) == 0) + { + s2.piece->type_index = -1; + s2.piece->current_type = Piece::UNKNOWN; + } +} + +/** + * @funct Get_moves + * @purpose Get all moves for a Piece and store them + * @param p - Piece + * @param v - vector to store Squares in. Will *not* be cleared. + */ +void Board::Get_moves(Piece * p, vector & v) +{ + assert(p->current_type != Piece::UNKNOWN); + Board::Get_moves(grid[p->x][p->y], p->current_type, v); +} + +/** + * @funct Get_moves + * @purpose Get moves from a square for piece of specified type + * @param s - Square + * @param t - Type + * @param v - Vector to store squares in. Will *not* be cleared. + */ +void Board::Get_moves(Square & s, const Piece::Type & t, vector & v) +{ + int x = s.x; int y = s.y; + Piece * p = s.piece; + + if (t == Piece::KING) + { + CheckMove(p, x+1, y, v); + CheckMove(p, x-1, y, v); + CheckMove(p, x, y+1, v); + CheckMove(p, x, y-1, v); + CheckMove(p, x+1, y+1, v); + CheckMove(p, x+1, y-1, v); + CheckMove(p, x-1, y+1, v); + CheckMove(p, x-1, y-1, v); + } + else if (t == Piece::KNIGHT) + { + CheckMove(p, x+2, y+1, v); + CheckMove(p, x+2, y-1, v); + CheckMove(p, x-2, y+1, v); + CheckMove(p, x-2, y-1, v); + CheckMove(p, x+1, y+2, v); + CheckMove(p, x-1, y+2, v); + CheckMove(p, x+1, y-2, v); + CheckMove(p, x-1, y-2, v); + } + else if (t == Piece::PAWN) + { + int y1 = (p->colour == Piece::WHITE) ? BOARD_HEIGHT-2 : 1; + int y2 = (p->colour == Piece::WHITE) ? y1 - 2 : y1 + 2; + if (p->types[0] == Piece::PAWN && p->y == y1) + { + + CheckMove(p, x, y2, v); + } + y2 = (p->colour == Piece::WHITE) ? y - 1 : y + 1; + CheckMove(p, x, y2, v); + + if (Valid_position(x-1, y2) && grid[x-1][y2].piece != NULL) + CheckMove(p, x-1, y2, v); + if (Valid_position(x+1, y2) && grid[x+1][y2].piece != NULL) + CheckMove(p, x+1, y2, v); + } + else if (t == Piece::BISHOP) + { + ScanMoves(p, 1, 1, v); + ScanMoves(p, 1, -1, v); + ScanMoves(p, -1, 1, v); + ScanMoves(p, -1, -1, v); + } + else if (t == Piece::ROOK) + { + ScanMoves(p, 1, 0, v); + ScanMoves(p, -1, 0, v); + ScanMoves(p, 0, 1, v); + ScanMoves(p, 0, -1, v); + } + else if (t == Piece::QUEEN) + { + ScanMoves(p, 1, 1, v); + ScanMoves(p, 1, -1, v); + ScanMoves(p, -1, 1, v); + ScanMoves(p, -1, -1, v); + ScanMoves(p, 1, 0, v); + ScanMoves(p, -1, 0, v); + ScanMoves(p, 0, 1, v); + ScanMoves(p, 0, -1, v); + } + +} + +/** + * @funct CheckMove + * @purpose Add a move to the vector, if it is valid + * @param p - Piece that would move + * @param x, y - Destination Square coords + * @param v - vector to put the destination Square in, if the move is valid + */ +void Board::CheckMove(Piece * p, int x, int y, vector & v) +{ + if (Valid_position(x, y) && (grid[x][y].piece == NULL || p == NULL || grid[x][y].piece->colour != p->colour)) + { + v.push_back(&(grid[x][y])); + } + //else + // cerr << "Square " << x << "," << y << " invalid; " << grid[x][y].piece << "\n"; +} + +/** + * @funct ScanMoves + * @purpose Add moves in a specified direction to the vector, until we get to an invalid move + * @param p - Piece to start scanning from + * @param vx, vy - "velocity" - change in coords each move + * @param v - vector to store valid Squares in + */ +void Board::ScanMoves(Piece * p, int vx, int vy, vector & v) +{ + int x = p->x + vx; + int y = p->y + vy; + while (Valid_position(x, y) && (grid[x][y].piece == NULL || p == NULL || grid[x][y].piece->colour != p->colour)) + { + v.push_back(&(grid[x][y])); + if (grid[x][y].piece != NULL) + break; + x += vx; + y += vy; + } +} + +/** + * @funct ScanPiece + * @purpose Scan in a direction until we either hit a piece or go off the board + * @param s - Square to start scanning from + * @param vx, vy - "velocity" - change in coords each move + */ +Piece * Board::ScanPiece(Square & s, int vx, int vy) +{ + int x = s.x + vx; + int y = s.y + vy; + while (Valid_position(x, y)) + { + if (grid[x][y].piece != NULL) + return grid[x][y].piece; + x += vx; + y += vy; + } + return NULL; +} + +/** + * @funct str2type + * @purpose Convert string to Piece::Type + * @param str - The string + * @returns A Piece::Type + */ +Piece::Type Piece::str2type(const string & str) +{ + if (str == "king") + return Piece::KING; + else if (str == "queen") + return Piece::QUEEN; + else if (str == "rook") + return Piece::ROOK; + else if (str == "bishop") + return Piece::BISHOP; + else if (str == "knight") + return Piece::KNIGHT; + else if (str == "pawn") + return Piece::PAWN; + else if (str == "unknown") + return Piece::UNKNOWN; + + throw Exception("Piece::str2type", "String \"%s\" doesn't represent a type", str.c_str()); + return Piece::UNKNOWN; +} + +/** + * @funct type2str + * @purpose Convert Piece::Type to string + * @param t - The Types + * @returns a const char* + */ +const char * Piece::type2str(const Piece::Type & t) +{ + switch (t) + { + case PAWN: + return "pawn"; + case BISHOP: + return "bishop"; + case KNIGHT: + return "knight"; + case ROOK: + return "rook"; + case QUEEN: + return "queen"; + case UNKNOWN: + return "unknown"; + case KING: + return "king"; + default: + throw Exception("Piece::type2str", "Unknown type %d", (int)t); + return ""; + } +} + +/** + * @funct str2colour + * @purpose Convert string to Piece::Colour + * @param str - The string + * @returns A Piece::Colour + */ +Piece::Colour Piece::str2colour(const string & str) +{ + if (str == "white") + return Piece::WHITE; + else if (str == "black") + return Piece::BLACK; + + throw Exception("Piece::str2colour", "string \"%s\" is not white|black", str.c_str()); + return Piece::BLACK; // should never get here +} + +/** + * @funct AddPiece + * @purpose Creates a new Piece and adds it to a vector + * @param v - The vector + * @params - All remaining parameters passed to Piece::Piece + * @returns Pointer to the new Piece + */ +Piece * Piece::AddPiece(vector & v, int x, int y, const Piece::Colour & colour, const Piece::Type & t1, const Piece::Type & t2, + int type_index) +{ + Piece * p = new Piece(x,y,colour,t1, t2,type_index); + v.push_back(p); + return p; +} + +/** + * @funct AddPiece + * @purpose Copy a Piece and add it to a vector + * @param v - The vector + * @param cpy - Piece to copy + * @returns Pointer to the new Piece + */ +Piece * Piece::AddPiece(vector & v, const Piece & cpy) +{ + Piece * p = new Piece(cpy); + v.push_back(p); + return p; +} + +/** + * @funct Update_coverage + * @purpose Update the map of Pieces that cover a square + * @param b - Board to use for updating + */ + +void Square::Update_coverage(Board & b) +{ + coverage[Piece::WHITE].clear(); + coverage[Piece::BLACK].clear(); + + + static int directions[][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; + + + + for (unsigned i = 0; i < sizeof(directions); ++i) + { + Piece * p = b.ScanPiece(*this, directions[i][0], directions[i][1]); + if (p == NULL) + continue; + double prob = 0.0; + + // take care of kings + if (abs(p->x - x) + abs(p->y - y) && p->current_type == Piece::KING) + { + coverage[p->colour][p] = 1.0; + continue; + } + + switch (i) + { + // ranks + case 0: + case 1: + case 2: + case 3: + prob = p->ProbIsType(b,Piece::ROOK) + p->ProbIsType(b,Piece::QUEEN); + if (i == 2 && p->colour == Piece::WHITE) + { + if (abs(y - p->y) < 1 || ((p->y == BOARD_HEIGHT-2 && abs(y - p->y) == 2))) + prob += p->ProbIsType(b,Piece::PAWN); + } + if (i == 3 && p->colour == Piece::BLACK) + { + if (abs(y - p->y) < 1 || ((p->y == 1 && abs(y - p->y) == 2))) + prob += p->ProbIsType(b,Piece::PAWN); + } + + if (prob > 0.001) + coverage[p->colour][p] = prob; + break; + + //diagonals + case 4: + case 5: + case 6: + case 7: + prob = p->ProbIsType(b,Piece::BISHOP) + p->ProbIsType(b,Piece::QUEEN); + if ((i == 4 || i == 6) && p->colour == Piece::WHITE) + { + if (abs(y - p->y) == 1 && abs(x - p->x) == 1) + prob += p->ProbIsType(b, Piece::PAWN); + } + if ((i == 5 || i == 7) && p->colour == Piece::BLACK) + { + if (abs(y - p->y) == 1 && abs(x - p->x) == 1) + prob += p->ProbIsType(b, Piece::PAWN); + } + + if (prob > 0.001) + coverage[p->colour][p] = prob; + break; + } + + } + + // check knights + static int knight_pos[][2] = {{-1,2},{1,2},{-1,-2},{-1,2}, {-2,1},{-2,-1},{2,1},{2,-1}}; + for (unsigned i = 0; i < sizeof(knight_pos); ++i) + { + if (!b.Valid_position(x+knight_pos[i][0], y+knight_pos[i][1])) + continue; + + Piece * p = b.SquareAt(x+knight_pos[i][0],y+knight_pos[i][1]).piece; + if (p != NULL) + { + double prob = p->ProbIsType(b, Piece::KNIGHT); + if (prob > 0.001) + coverage[p->colour][p] = prob; + } + + } + + +} +/** + * @funct ProbIsType + * @purpose Determine the probability that a Piece will become the specified type on its next selection + * @param b - Board to use to calculate probabilities + * @param t - The type + * @returns Probability that the piece's type becomes t on its next selection taking into account unknown types + */ +double Piece::ProbIsType(Board & b, const Piece::Type & t) +{ + if (current_type != Piece::UNKNOWN) + return (current_type == t) ? 1.0 : 0.0; + + + double prob = 0.0; + map & m = b.unknown_types(colour); + int nUnknown = b.nUnknown(colour); + for (unsigned i = 0; i < sizeof(types); ++i) + { + if (types[i] != Piece::UNKNOWN) + { + prob += (1.0 / double(sizeof(types))) * (double)(types[i] == t); + } + else + { + prob += (1.0 / double(sizeof(types))) * (m[t] / double(nUnknown)); + } + } + return prob; +} + +/** + * @funct SquareAt + * @purpose Return square at a position on the board + * @param x - x coord + * @param y - y coord + */ +Square & Board::SquareAt(int x, int y) +{ + if (!Valid_position(x, y)) + throw Exception("Board::SquareAt", "Invalid position %d,%d", x, y); + return grid[x][y]; +} \ No newline at end of file diff --git a/agents/silverfish/qchess.h b/agents/silverfish/qchess.h deleted file mode 120000 index c020ad2..0000000 --- a/agents/silverfish/qchess.h +++ /dev/null @@ -1 +0,0 @@ -../c++/qchess.h \ No newline at end of file diff --git a/agents/silverfish/qchess.h b/agents/silverfish/qchess.h new file mode 100644 index 0000000..db2f9a9 --- /dev/null +++ b/agents/silverfish/qchess.h @@ -0,0 +1,191 @@ +/** + * agent++ : A Sample agent for UCC::Progcomp2013 + * @file qchess.h + * @purpose Declarations for game related classes; Piece, Square, Board + */ + +#ifndef _QCHESS_H +#define _QCHESS_H + + +// board height and width (don't change!) +#define BOARD_HEIGHT 8 +#define BOARD_WIDTH 8 + +#include +#include +#include +#include +#include + +#include +#include // for vfprintf... for the Exception + +class Board; //forward declaration + +/** + * @class Piece + * @purpose Represent a quantum chess piece + */ +class Piece +{ + public: + + typedef enum {PAWN, BISHOP, KNIGHT, ROOK, QUEEN, KING, UNKNOWN} Type; + typedef enum {WHITE=0, BLACK=1} Colour; + + static Type AllTypes[]; + static Colour AllColours[]; + + + virtual ~Piece() {} // destructor + + int x; int y; // position of the piece + Colour colour; // colour of the piece + int type_index; // indicates state the piece is in; 0, 1, or -1 (unknown) + Type types[2]; // states of the piece + Type current_type; // current state of the piece + + static Type str2type(const std::string & str); + static Colour str2colour(const std::string & str); + static const char * type2str(const Type & t); + + static Piece * AddPiece(std::vector & v, int x, int y, const Colour & colour, const Type & type1, const Type & type2, int type_index=-1); + static Piece * AddPiece(std::vector & v, const Piece & cpy); + + static Colour Opposite(const Colour & c) + { + return (c == WHITE) ? BLACK : WHITE; + } + + double ProbIsType(Board & b, const Piece::Type & t); + + private: + friend class Board; + Piece(int x, int y, const Colour & colour, const Type & type1, const Type & type2 + , int type_index); // constructor + Piece(const Piece & cpy); // copy constructor + + + +}; + +/** + * @class Square + * @purpose Represent a Square on the board; not necessarily occupied + */ +class Square +{ + public: + Square() : x(-1), y(-1), piece(NULL) {} // constructor + Square(int new_x, int new_y, Piece * new_piece = NULL) : x(new_x), y(new_y), piece(new_piece) {} //UNUSED + Square(const Square & cpy) : x(cpy.x), y(cpy.y), piece(cpy.piece) {} // copy constructor (UNUSED) + virtual ~Square() {} //destructor + int x; int y; // position of the square + Piece * piece; // Piece that is in the Square (NULL if unoccupied) + + const std::map & Coverage(const Piece::Colour & c) + { + return (c == Piece::WHITE) ? coverage[Piece::WHITE] : coverage[Piece::BLACK]; + } + + void Update_coverage(Board & b); + + private: + std::map > coverage; +}; + +/** + * @class Board + * @purpose Represent a quantum chess board + */ +class Board +{ + public: + Board(bool choose_types = false); // constructor + Board(Board & parent); // clones a board, copy on write + virtual ~Board(); // destructor + + + // helper; return vector of pieces given player colour + std::vector & pieces(const Piece::Colour & colour) {return ((colour == Piece::WHITE) ? white : black);} + // helper; return map of unidentified 2nd types for given colour + std::map & unknown_types(const Piece::Colour & colour) + { + return ((colour == Piece::WHITE) ? white_unknown : black_unknown); + } + + int & nUnknown(const Piece::Colour & colour) + { + return ((colour == Piece::WHITE) ? white_nUnknown : black_nUnknown); + } + + // helper; return king given player colour + Piece * king(const Piece::Colour & colour) {return ((colour == Piece::WHITE) ? white_king : black_king);} + + void Update_move(int x, int y, int x2, int y2); // move a piece + void Update_select(int x, int y, int index, const std::string & type); // update a selected piece + void Update_select(int x, int y, int index, const Piece::Type & t); + + Square & square(int x, int y) {return grid[x][y];} // get square on board + + void Get_moves(Square & s, const Piece::Type & t, std::vector & v); + void Get_moves(Piece * p, std::vector & v); // get allowed moves for piece of known type + + // determine if position is on the board + bool Valid_position(int x, int y) const {return (x >= 0 && x <= BOARD_WIDTH-1 && y >= 0 && y <= BOARD_HEIGHT-1);} + + + // scans from a square until a piece is reached + Piece * ScanPiece(Square & s, int vx, int vy); + + // Get a piece + Square & SquareAt(int x, int y); + + private: + Square grid[BOARD_WIDTH][BOARD_HEIGHT]; + + // All pieces for each player + std::vector white; + std::vector black; + // The number of pieces with each 2nd type that are still unidentified + std::map white_unknown; + std::map black_unknown; + int white_nUnknown; + int black_nUnknown; + Piece * white_king; + Piece * black_king; + + + + // Add a move to the vector if it is valid + void CheckMove(Piece * p, int x, int y, std::vector & v); + + // Add all valid moves in a direction, stopping at the first invalid move + void ScanMoves(Piece * p, int vx, int vy, std::vector & v); + + +}; + +/** + * @class Exception + * @purpose The only exception. + */ +class Exception +{ + public: + Exception(const char * funct, const char * fmt, ...) + { + fprintf(stderr, "Exception in %s - ", funct); + va_list va; + va_start(va, fmt); + vfprintf(stderr, fmt, va); + va_end(va); + fprintf(stderr, "\n"); + } + +}; + +#endif //_QCHESS_H + +//EOF diff --git a/agents/silverfish/silverfish.cpp b/agents/silverfish/silverfish.cpp index 20eb9e9..5ef044f 100644 --- a/agents/silverfish/silverfish.cpp +++ b/agents/silverfish/silverfish.cpp @@ -2,7 +2,15 @@ using namespace std; -Silver::Silver(const string & colour) : Agent(colour), values() + + +bool sort_scores(pair & a, pair & b) +{ + return a.second > b.second; +} + + +Silver::Silver(const string & colour, int new_max_depth) : Agent(colour), values(), max_depth(new_max_depth), depth(0), { values[Piece::PAWN] = 1; values[Piece::BISHOP] = 3; @@ -13,18 +21,64 @@ Silver::Silver(const string & colour) : Agent(colour), values() values[Piece::UNKNOWN] = 1.5; } -Silver::Silver(const string & colour, const map & new_values) : Agent(colour), values(new_values) +Silver::Silver(const string & colour, const map & new_values, int new_max_depth) + : Agent(colour), values(new_values), max_depth(new_max_depth), depth(0) { //TODO: Assert map is valid } +Move Silver::BestMove(Piece::Colour c) +{ + +} + Square & Silver::Select() { - return Agent::Select(); + + for (int x = 0; x < BOARD_WIDTH; ++x) + { + for (int y = 0; y < BOARD_HEIGHT; ++y) + { + Square & s = board.SquareAt(x,y); + + if (s.piece != NULL && s.piece.colour == colour) + continue; + + map m = board.SquareAt(x,y).Coverage(colour); + + for (map::iterator i = m.begin(); i != m.end(); ++i) + { + moves[i->first].push_back(pair + } + } + } + + for (map > >::iterator i = moves.begin(); i < moves.end() + } Square & Silver::Move() { - return Agent::Move(); + vector moves; + board.Get_moves(selected); +} + +double ScoreMove(Piece * p, Square & target) +{ + ++depth; + double score = 0.0; + if (target.piece == NULL) + score = 0.0 + else + score = 0.5*(values[target.piece->types[0]] + values[target.piece->types[1]]); + + if (depth < max_depth) + { + double recurse_score; + + BestMove(Piece::Opposite(p->colour)); + } + --depth; + return score; } \ No newline at end of file diff --git a/agents/silverfish/silverfish.h b/agents/silverfish/silverfish.h index dc5b26a..fe0111d 100644 --- a/agents/silverfish/silverfish.h +++ b/agents/silverfish/silverfish.h @@ -6,14 +6,32 @@ class Silver : public Agent { public: - Silver(const std::string & colour); - Silver(const std::string & colour, const std::map & new_values); + Silver(const std::string & colour, int max_depth=2;); + Silver(const std::string & colour, const std::map & new_values, int max_depth=2;); virtual ~Silver() {} virtual Square & Select(); virtual Square & Move(); - + std::map values; + int max_depth; + int depth; + +}; + +class Move +{ + public: + Move(Piece * new_p, Square & new_s, double new_score) : p(new_p), s(new_s), score(new_score) {} + virtual ~Move() {} + Move(const Move & cpy) : p(cpy.p), s(cpy.s), score(cpy.score) {} + + Piece * p; + Square & s; + double score; + + bool operator>(const Move & m) const {return score > m.score;} + bool operator<(const Move & m) const {return score < m.score;} };