Public Group

# 'Chess' Program - anything faster than this possible

This topic is 2877 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 knightElephant moves Hawk movesBishop 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.TASKWrite a program that, given a description of a board position, and a piece, computes the number of possible moves by that piece.TIME LIMITA time limit of 1 second will be placed upon your programme for each test case.INPUTYour 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’ forwhite or black respectively. “Type” is ‘q’, ‘e’ or ‘h’ for queen, elephant andhawk 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.OUTPUTYour programme must write to standard output a single integer M, the number ofpossible moves for the given pieceEXAMPLESample input 6b q d6b q f6w e f3w h e4b q e5w e d3f3Sample 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 typesenum 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 sostruct Square {         PIECE  pieceType;         COLOUR pieceColour; };//const values for the size of the board, and to help work out grid refs //from string inputconst 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 0const 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[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 movementvoid 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 movementvoid 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 emptyvoid 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 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 on other sites
Explanations of the ways the pieces move in the exercise

An illustration of the sample input data

##### Share on other sites
Quote:
 Original post by Abion47Perhaps 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 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.

1. 1
Rutin
45
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 15
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633004
• Total Posts
3009841
• ### Who's Online (See full list)

There are no registered users currently online

×