Sign in to follow this  
MrLloyd1981

'Chess' Program - anything faster than this possible

Recommended Posts

Hi again everyone, I'm back with a test problem from an old Realtime Worlds competition, I recently posted an interesting collision detection problem here: http://www.gamedev.net/community/forums/topic.asp?topic_id=588999

Now I have had a crack at another problem, the description is below, sans images

Quote:

CHESS (100 points)
You are working on a chess variant game with a standard 8x8 board and two sides
(black and white), but with different piece types:

 The queen moves exactly like a queen in standard chess.
 The elephant moves like a rook or a knight
 The hawk moves like a bishop or a knight

Elephant moves Hawk moves
Bishop moves in standard chess. Rook moves in standard chess.
Knight moves in standard chess.
Queen moves in standard chess.

Pure straight-line moves can only go as far as they are unobstructed: jumping over other pieces is not allowed. No piece may land on a square occupied by another piece of the same colour. A piece can always land on a square occupied by the opposite colour (capturing that piece).
You are working on the AI for this game, and as part of this, you must write code to generate all possible moves for a given board position.

TASK
Write a program that, given a description of a board position, and a piece, computes the number of possible moves by that piece.

TIME LIMIT
A time limit of 1 second will be placed upon your programme for each test case.

INPUT
Your programme must read from standard input, the following set of data:
 Line 1 contains an integer N, the number of pieces on the board.
 Each of the next N lines describes a single piece with 3 fields: colour, type,
and square in that order, separated by a space. “Colour” is ‘w’ or ‘b’ for
white or black respectively. “Type” is ‘q’, ‘e’ or ‘h’ for queen, elephant and
hawk respectively. The square is a letter-number (column-row) pair, from
‘a1’ for the bottom left and ‘h8’ for the top right corner of the board.
 The last line of the file contains the letter-number pair for a piece; this is the piece your programme should calculate moves for.

OUTPUT
Your programme must write to standard output a single integer M, the number of
possible moves for the given piece

EXAMPLE
Sample input
6
b q d6
b q f6
w e f3
w h e4
b q e5
w e d3
f3

Sample Output
16




And my code is as follows, it works for the above test case but I was wondering about a tidier, cleaner approach to evaluating all the possible knight moves

[source lang = "cpp"]
//program to look for possible moves of a chess piece - asks for a number of pieces present from a user and
//then the user enters the grid reference on an 8x8 board, the type of piece and color for each piece.
//The Grid reference for the piece to test is then entered, and then each of the possible moves by the piece are
//counted and output




#include <iostream>
#include <string>
using namespace std;

//enums for piece and colour types

enum PIECE{EMPTY,HAWK,ELEPHANT,QUEEN};
enum COLOUR{BLACK,WHITE};


//a struct to hold a grid reference
struct Position
{
int x;
int y;
};


//a struct to represent a square on a chess board
//shows if the square is empty or not and what colour the piece is if so

struct Square
{
PIECE pieceType;
COLOUR pieceColour;
};



//const values for the size of the board, and to help work out grid refs
//from string input

const int BOARDSIZE = 8;
const int ASCIIVALCHAR = 97;
const int ASCIIVALNUM = 49;

//const values to represent possible directions on a chess board, with a value
//STILL to represent no movement, its just a lot more explanatory than a 0

const int LEFT = -1;
const int RIGHT = 1;
const int DOWN = 1;
const int UP = -1;
const int STILL = 0;

//typedef an int DIR just to make prototypes clearer
typedef int DIR;

//typedef a chessboard, an 8 x 8 grid of squares
typedef Square board[BOARDSIZE][BOARDSIZE];


//function prototypes
void initBoard(board&);
void getData(board&,string&);
Square returnPiece(char,char);
void evaluateMoves(board&,string&);
void EvalDiagonalMoves(board&, COLOUR, Position&,int& );
void EvalStraightMoves(board&, COLOUR, Position&,int&);
void EvalKnightMoves(board&, COLOUR, Position&,int&);
void TestDirection(board&, COLOUR, int, int,int&,DIR, DIR);
PIECE returnPiece(char);



int main()
{
string testingSquare;
board ChessBoard;
initBoard(ChessBoard);
getData(ChessBoard,testingSquare);
evaluateMoves(ChessBoard,testingSquare);
return 0;
}

//initialise all the board squares to EMPTY
void initBoard(board& chessboard)
{
for(int i = 0; i < BOARDSIZE; i++)
{
for(int j = 0; j < BOARDSIZE; j++)
{
chessboard[i][j].pieceType = EMPTY;
}
}
}


//gets all input necessary from the user, assumes that all input is correct
void getData(board& chessboard, string& testSquare)
{
int numPieces;
char colour;
char piece;
string position;

cin >> numPieces;

for(int i = 0; i < numPieces; i++)
{
cin >> colour >> piece >> position;

chessboard[position[0] - ASCIIVALCHAR ][position[1] - ASCIIVALNUM].pieceType =
returnPiece(piece);

if(colour == 'b') chessboard[position[0] -ASCIIVALCHAR][position[1]- ASCIIVALNUM].pieceColour =
BLACK;
else
chessboard[position[0] - ASCIIVALCHAR][position[1]- ASCIIVALNUM].pieceColour = WHITE;

}

cin >>testSquare;

}


//returns a piece value depending on the passed char value
PIECE returnPiece(char piece)
{
switch(piece)
{
case 'e' :
return ELEPHANT;
case 'h' :
return HAWK;
case 'q' :
return QUEEN;
default :
return EMPTY;
}
}


//this evaluates the amount of moves depending on the configuration of the
//chess board, and the string representation of the grid ref that gets broken down
//into two integer indexes. These indexes are used to get the type of the piece, colour
//etc. It assumes all info passed in to be correct.


void evaluateMoves(board& chessboard,string& testSquare)
{
Position testPos;
testPos.x = testSquare[0] - ASCIIVALCHAR;
testPos.y = testSquare[1] - ASCIIVALNUM;

PIECE piece = chessboard[testPos.x][testPos.y].pieceType;
COLOUR colour = chessboard[testPos.x][testPos.y].pieceColour;

int numMoves = 0;


//now the possible num of moves are calculated by calling routines depending
//on the piece type, the total number is passed by reference so it is added up.

switch(piece)
{
case HAWK :
EvalDiagonalMoves(chessboard,colour,testPos,numMoves);
EvalKnightMoves(chessboard,colour,testPos,numMoves);
break;
case ELEPHANT :
EvalStraightMoves(chessboard,colour,testPos,numMoves);
EvalKnightMoves(chessboard,colour,testPos,numMoves);
break;
case QUEEN :
EvalStraightMoves(chessboard,colour,testPos,numMoves);
EvalDiagonalMoves(chessboard,colour,testPos,numMoves);
break;
}

cout << numMoves<<endl;
}

//Wrapper function for TestDirection() - passes appropriate values for horizontal and
//vertical movement to represent straight lines of movement

void EvalStraightMoves(board& chessboard, COLOUR colour, Position& pos,int& moves)
{
//strategy - check up, down, left, right
TestDirection(chessboard,colour, pos.x, pos.y + UP ,moves,UP,STILL);
TestDirection(chessboard,colour, pos.x, pos.y + DOWN ,moves,DOWN,STILL);
TestDirection(chessboard,colour, pos.x + LEFT, pos.y,moves,STILL,LEFT);
TestDirection(chessboard,colour, pos.x + RIGHT, pos.y,moves,STILL,RIGHT);


}

//Wrapper function for TestDirection() - passes appropriate values for horizontal and
//vertical movement to represent diagonal lines of movement

void EvalDiagonalMoves(board& chessboard, COLOUR colour, Position& pos,int& moves)
{
//strategy - check up-left,up-right,down-right,down-left
TestDirection(chessboard,colour, pos.x + LEFT, pos.y + UP ,moves,UP,LEFT);
TestDirection(chessboard,colour, pos.x + RIGHT, pos.y + UP ,moves,UP,RIGHT);
TestDirection(chessboard,colour, pos.x + RIGHT, pos.y + DOWN,moves,DOWN,RIGHT);
TestDirection(chessboard,colour, pos.x + LEFT, pos.y + DOWN,moves,DOWN,LEFT);
}


//tests each possible knight move individually to see if legal using
//bounds checking and testing if square is empty

void EvalKnightMoves(board& chessboard, COLOUR colour, Position& pos,int& moves)
{

//own algorithm for this - check if landing square is
//either out of bounds, on another piece - if so check colour
if(pos.x + 2 < BOARDSIZE && pos.y - 1 >= 0)
{
if(chessboard[pos.x+2][pos.y-1].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x+2][pos.y-1].pieceColour != colour)
moves++;
}
}


if(pos.x + 2 < BOARDSIZE && pos.y + 1 < BOARDSIZE)
{
if(chessboard[pos.x+2][pos.y+1].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x+2][pos.y+1].pieceColour != colour)
moves++;
}
}


if(pos.x - 2 >= 0 && pos.y - 1 >= 0)
{
if(chessboard[pos.x-2][pos.y-1].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x-2][pos.y-1].pieceColour != colour)
moves++;
}
}


if(pos.x - 2 >= 0 && pos.y + 1 < BOARDSIZE)
{
if(chessboard[pos.x-2][pos.y+1].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x-2][pos.y+1].pieceColour != colour)
moves++;
}
}


if(pos.x + 1 < BOARDSIZE && pos.y - 2 >= 0)
{
if(chessboard[pos.x+1][pos.y-2].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x+1][pos.y-2].pieceColour != colour)
moves++;
}
}


if(pos.x - 1 >= 0 && pos.y - 2 >= 0)
{
if(chessboard[pos.x-1][pos.y-2].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x-1][pos.y-2].pieceColour != colour)
moves++;
}
}


if(pos.x + 1 < BOARDSIZE && pos.y + 2 < BOARDSIZE)
{
if(chessboard[pos.x+1][pos.y+2].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x+1][pos.y+2].pieceColour != colour)
moves++;
}
}

if(pos.x - 1 >= 0 && pos.y +2 < BOARDSIZE)
{
if(chessboard[pos.x - 1][pos.y + 2].pieceType == EMPTY)
{
moves++;
}
else
{
if(chessboard[pos.x - 1][pos.y + 2].pieceColour != colour)
moves++;
}
}
}


//recursive procedure used to calculate possible number of moves - first of all tests if passed
//position is within the board and legal, then tests if the square is empty. If so this is a legal
//move, increment the total by one and call the procedure again by one square in the appropriate direction.
//If not test if the piece in the square is the same color - if it is no go, if not increase by one and
//end the recursion.

void TestDirection(board& chessboard, COLOUR colour, int x, int y,int& moves,DIR vert, DIR horiz)
{
if(x < BOARDSIZE && x >= 0 && y < BOARDSIZE && y >= 0)
{
if(chessboard[x][y].pieceType == EMPTY)
{
moves++;
TestDirection(chessboard,colour,x+horiz,y+vert,moves,vert,horiz);
}
else
{
if(chessboard[x][y].pieceColour != colour)
moves++;
}
}
}






I will post some images to explain the sample input asap, as well as some other diagrams

Thanks in advance, I'm curious to see what we can all learn here

[Edited by - MrLloyd1981 on December 7, 2010 4:53:49 PM]

Share this post


Link to post
Share on other sites
Perhaps it's just my lack of C++ know-how, but it looks like you are only checking each rook/bishop movement type with one square in each relevant direction. Aren't you supposed to check available squares across the board?

Edit: Sorry, on my first look I missed the recursive call in TestDirection. :P

Share this post


Link to post
Share on other sites
Quote:
Original post by Abion47
Perhaps it's just my lack of C++ know-how, but it looks like you are only checking each rook/bishop movement type with one square in each relevant direction. Aren't you supposed to check available squares across the board?


It does, its using a recursive approach to check one square at a time until it either goes out of bounds/off the board or finds a square with a piece in it blocking the way, where the recursion terminates

EDIT: Haha there was no need for me to post this afterall ;)

Share this post


Link to post
Share on other sites
IMHO it would be faster for the knight algorithm if you were to check the positions in the order of squares that are similar with each other. Seems like a faster alternative than checking each square independently. I.E. go from x + 2 and y + 1 to x + 2 and y - 1. This way you are only changing the value of one variable instead of two.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this