Chess game I developed, originally written with Borland C 4.5 for DOS in early 2003, then ported to Windows (Microsoft Visual C++ v6.0) late 2003 and early 2004, with a few minor changes since. The conversion was easier than I expected, only the graphics and user interface were platform dependant, probably less than 1/4 of the ~3500 lines of code. I would also like to note that the application can be resized on the fly, a neat little trick courtesy of MFC.
As for the game itself, there are tougher games out there, and certainly some that look better (I never claimed to have much artistic ability). I optimized for quick moves rather than super-smart play, and could do a better job of that if I were to try again. There is a lot of memory allocating and deallocating that a little pooling could help. Multi-threading could unlock a whole new level of performance as well.
Download 448k, one program, one file, download and run.
Source Sample
This sample is one half of the interesting AI bits for the game. A tree of possible boards is built, starting with the current board, and generating a new board for every possible move. Each of those boards spawns a list of all possible moves from there, and so on. When the desired depth is met, the function turns around, picking the best move for each set. (The other interesting part is scoring a given board.)
Essentially we start with the current board, and ask, what moves can I make? What are my opponent's responses to those, and my reponses from there? When we reach the desired level of recursion, we score the final outcomes. We then start filtering backwards. If I make move A, and my opponent responds with B, C is my best outcome. Knowing this, would my opponent choose B, or another move? Based on my opponent's ability to limit my choices, should I start with A or a different move?
List moves:
Current Board
/ | \
White A B C
/ | \ / | \ / | \
Black D E F G H I J K L
/|\ /| | /|\
White M N O P Q R S T U
Choose best end results for white (N, P, R, S):
Current Board
/ | \
White A B C
/ | \ / | \ / | \
Black D E F G H I J K L
| | | /
White N P R S
But black's best moves are (D, G, L):
Current Board
/ | \
White A B C
/ / \
Black D G L
| /
White M S
Only one path has a positive outcome for white, C -> L -> S:
Current Board
/ | \
White A B C
/ / \
Black D G L
| /
White M S
A few notes about the classes and functions used-chess_board
This is the primary data structure for the game. It represents a chess board, including location of all the pieces. It was also convenient to attach some other data, such as a score for each player, as well as in_check state flags.
pos_move
This class represents a possible move, storing source and destination information. Both chess_board and pos_move, when passed another board or move to the constructor, will copy the data of the passed instance.
chess_board::comp_score()
This function, outside of cpu_move(), is the most crucial to the AI routine in this game. It handles scoring of a chess board, setting score values for each player, as well as the in_check flags as applicable.
cpu_list_moves()
This function is actually similar in structure to comp_score(), but rather than tabulating score information, it creates a linked list of possible moves for a given player. Moves into check are included in the list, since the moves are listed to be scored, not just to be made.
pos_move::apply()
This function applies a possible move to a chess board, the first of two arguments. The second, a true/false value, indicates whether or not the move is final, determining if a dialog is displayed in the case of pawn promotion.
Disclaimer: This was written in 2003, more than a year before I got my first programming job. I would do things differently now, this code could be cleaned up, a lot of names could be improved, and the logic clarified. I also made a more subtle and costly mistake on this project. When I showed the game to one of my former professors, he asked if I had done any research, and was impressed when I admitted that I had not. That experience made me think it was better to try to figure things out on your own, rather than reading up on existing solutions. That might be the case if you are just trying to stretch your own brain, but for real world problems a little Googling can save a lot of pain. Long story short:
I don't write code like this anymore.
void CWin_chessDlg::cpu_move_rec(
int cur_lvl, int max_lvl, chess_board *in_board, bool p, short int score[]) {
pos_move *move_list, *cur_move, *next_move;
chess_board * t_board;
short int local_score[2];
short int sav_score_1, sav_score_2, high_score;
bool checkmate;
if (in_board->in_check[p]) // This board was conveniently scored
checkmate = TRUE; // in calling function.
else
checkmate = FALSE;
move_list = cpu_list_moves(p, in_board);
cur_move = move_list;
high_score = -32767;
while(cur_move)
{
t_board = new chess_board(in_board);
cur_move->apply(t_board, FALSE);
t_board->comp_score();
// If in check, don't get responses,
// because we can't move into check.
if(!t_board->in_check[p])
{
checkmate = FALSE;
if(cur_lvl < max_lvl)
cpu_move_rec(cur_lvl+1, max_lvl, t_board, !p, local_score);
else
{
local_score[0] = t_board->score[p];
local_score[1] = t_board->score[!p];
}
// If high score, save.
if ((local_score[0] - local_score[1]) > high_score)
{
high_score = (local_score[0] - local_score[1]);
sav_score_1 = local_score[0];
sav_score_2 = local_score[1];
}
} // end if (!t_board->in_check[p])
delete t_board;
cur_move = cur_move->next;
}
if (checkmate) // In check, all moves into check or no moves.
{ // +/- (cur_lvl << 1) prevents preference of later checkmates.
sav_score_1 = (-CHECKMATE_VALUE) + (cur_lvl << 1);
sav_score_2 = CHECKMATE_VALUE - (cur_lvl << 1);
}
else if (!move_list) // No moves, not in check, draw.
{
sav_score_1 = 0; // Since the losing player will show a negative
sav_score_2 = 0; // score, 0/0 is an improvement, but a loss
} // for the winning player, who will
// always have a positive score.
// Delete moves.
cur_move = move_list;
while(cur_move)
{
next_move = cur_move->next;
delete cur_move;
cur_move = next_move;
}
// Pass back saved scores.
// Since next level down p and !p will be reversed,
// send scores reversed as well.
score[0] = sav_score_2;
score[1] = sav_score_1;
return;
}