Like any other game, we need to know if our game has ended. There can be various reasons for this: Checkmate, stalemate, draw by insufficient material, draw by repetition of the same position 3 times and the rare case when no piece is captured for more than 50 moves.

We implement a function which tells the way a game has ended(if it has) and this method is called after every move is played. First, let’s make an enumeration of these conditions:

enum {
    NO_END_OF_GAME, CHECKMATE, STALEMATE, INSUFFICIENT_MATERIAL_DRAW,
    THREE_MOVE_DRAW, FIFTY_MOVE_DRAW
};

Now on to the function:

int is_end_of_game() {
    ...(skipped: code to determine the king's position)...
    
    bool is_king_in_check = is_square_attacked(king_sq, opposite_side());
    std::vector<move&gt; movelist = generate_all_moves();
    
    // See if it's a CHECKMATE or a STALEMATE    
    if(is_king_in_check &amp;&amp; movelist.empty()){
        return CHECKMATE;
    } else if(movelist.empty()) {
        return STALEMATE;
    }

    ...
}

What we do determine the king’s position(look here – similar to what we did for filtering moves), and then check if the king is in check and the number of moves possible is zero. If so it is a checkmate. If the king is not under check and the movelist is empty, we have stalemate.

For dealing with draw due to the 50 move rule, we create a new vector in the chessboard class.

 std::vector<int&gt; fifty_move_history;

This list is initialized to {0} in the init function. When a move is being played, we append a new value to this list as per the following rules:

  1. If it is a pawn move or a capture move, append zero to the vector
  2. Else append one more than the previous value
// This is inside the make_move function
// Update the move history for the fifty move rule
if(m.captured_piece != BLANK || is_pawn(curr_piece)) {
    fifty_move_history.push_back(0);
} else {
    fifty_move_history.push_back(fifty_move_history[fifty_move_history.size()-1] + 1);
}

Finally, in the is_end_of_game function, we add the following check:

// 50 MOVE Rule
if(fifty_move_history[fifty_move_history.size()-1] >= 100) {
    return FIFTY_MOVE_DRAW;
}

Hence, if a piece has not be a captured or a pawn not moved for 50 turns(or 100 plies); it’s draw by the fifty move rule.

The implementation to check if it’s draw due to insufficient material is a bit tricky; but it’s doable with some verbose code. Basically, we go with the following rules:

  1. If there is only 1 knight on the board, then it’s a draw.
  2. If there are 2 or more than 2 bishops but they lie on the same color, then it’s a draw(2 bishops of the same side and of the same color can occur due to piece promotion).

What about stuff like 2 knights and king vs. king? Well, it is true that two knights cannot force a checkmate against the king. However, it may still occur due to blunders committed by the opponent. Hence, this case is ruled out of draw by insufficient material. Here is the code:

int is_draw_by_insufficient_material() {
    // Draw by insufficient material:
    int knight_count = 0;
    int bishop_count = 0, bishops_on_white = 0, bishops_on_black = 0;
    int pawn_count = 0;
    int queen_rook_count = 0;
    
    static int const colours[][8] = {
        {BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
        {WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
        {BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
        {WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
        {BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
        {WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK},
        {BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE},
        {WHITE, BLACK, WHITE, BLACK, WHITE, BLACK, WHITE, BLACK}
    };

    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            int piece = board[i][j];
            if(is_knight(piece)) {
                knight_count++;
            } else if(is_bishop(piece)) {
                bishop_count++;
                if(colours[i][j] == BLACK) {
                    bishops_on_black++;
                } else {
                    bishops_on_white++;
                }
            } else if(is_pawn(piece)) {
                pawn_count++;
            } else if(is_straight_attacker(piece)) {
                queen_rook_count++;
            }
        }
    }
    
    if(pawn_count + queen_rook_count &gt; 0) {
        return NO_END_OF_GAME;
    }

    if(knight_count == 1 &amp;&amp; bishop_count == 0) {
        return INSUFFICIENT_MATERIAL_DRAW;
    }
    
    if(knight_count == 0) {
       if(bishops_on_white == 0 || bishops_on_black == 0) {
           return INSUFFICIENT_MATERIAL_DRAW;
       }
    }
    
    // Default
    return NO_END_OF_GAME;
}   

That is a verbatim translation of the two points mentioned before.

You might be wondering how we use this function. Every time we play a move during actual play, we call the is_end_of_game function(probably named incorrectly – should be named end_of_game_type or something…) to find out the end of game status. If yes, we stop the game and declare the status. Otherwise, we continue. I have created a sample position and output for the CHECKMATE status.

-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
BQ BK -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- WK -- -- -- -- -- -- 

Side to play: BLACK

-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- BK -- -- -- -- -- -- 
-- BQ -- -- -- -- -- -- 
-- WK -- -- -- -- -- -- 

Side to play: WHITE

Game has ended.

1

The ‘1’ at the end is the enum value for the CHECKMATE status. Why don’t you try and input your positions to generate the other statuses? That would be an interesting exercise and also verify the sanity of the code.

In the next article, we will implement an interface to play this. Oh, and yes…I have skipped implementing draw by threefold repetition(try it as an exercise :p). See ya soon!

Advertisements

About the Author Pranav Deshpande

Software Developer interested in AI, Reinforcement Learning and game programming.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s