As mentioned before, let us see how to filter out the legal moves from the list of pseudo legal moves. To do this, we basically need to know if the move we are making puts the king in check; that is we need to see if the square on which which the king is present is attacked or not. This method will also be used to determine if the king is in check already. Checking if a square is attacked or not is very similar to move generation, as you will see below.

Firstly, we’ll check the diagonals for enemy attackers.

bool is_square_attacked(std::pair<int, int&gt; square, int side) {
    ...

    var_i = i + 1;
    var_j = j + 1;
    while(is_square_in_range(var_i, var_j)) {
        piece = board[var_i][var_j];
        if(get_piece_side(piece) == side 
            &amp;&amp; is_diagonal_attacker(piece)) {
            return true;
        } else if(get_piece_side(piece) == BLANK) {
            var_i++;
            var_j++;
        } else {
            break;
        }
    }

    ...
}

If we encounter an enemy piece along the diagonal, the square is under attack, if it’s blank we move on to the next square. Otherwise, it’s blocked by our own piece and hence the square is safe; and therefore we get out of the loop. We check for attacks along the rest of the diagonals and even the straight moves in a similar manner. For recap, I you can see the tables from the 2nd article again. For the full code, look here.

For knights and kings, we see if the square is attacked from the position where an opposing piece may be present. If so, we return true, otherwise we just proceed to the next square until we run out of them.

// Check if the square is attacked by a night
// The directions in which the knights can move
std::pair<int, int&gt; knight_moves[] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
                                      {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

for(auto next : knight_moves) {
    var_i = i + next.first;
    var_j = j + next.second;
    if(is_square_in_range(var_i, var_j)) {
        piece = board[var_i][var_j];
        if(get_piece_side(piece) == side &amp;&amp; is_knight(piece)) {
            return true;
        }
    }
}   

// The directions in which a king can move
std::pair<int, int&gt; king_moves[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},
                                {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

for(auto next : king_moves) {
    var_i = i + next.first;
    var_j = j + next.second;
    if(is_square_in_range(var_i, var_j)) {
        piece = board[var_i][var_j];
        if(get_piece_side(piece) == side &amp;&amp; is_king(piece)) {
            return true;
        }
    }
}

For pawn attacks, we check the diagonals(naturally only in 1 direction – up or down). An important point to note here is how the increment_sign is defined.

// Let's check for pawn attacks
int increment_sign = (side == WHITE ? 1 : -1);

var_i = i + increment_sign;
var_j = j + 1;
if(is_square_in_range(var_i, var_j)) {
    piece = board[var_i][var_j];
    if(get_piece_side(piece) == side && is_pawn(piece)) {
        return true;
    }
}

var_i = i + increment_sign;
var_j = j - 1;
if(is_square_in_range(var_i, var_j)) {
    piece = board[var_i][var_j];
    if(get_piece_side(piece) == side && is_pawn(piece)) {
        return true;
    }
}

Finally, let’s get on on to filtering the moves. We play each move and see if the square which is the king is on or has moved to is safe(not under attack). If so, the move is a perfectly legal move.

auto get_filtered_moves(auto movelist) {
    std::pair<int, int&gt; king_sq = {INVALID, INVALID};
    int king = INVALID;
    
    // Obtain the king's square
    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            if(is_king(board[i][j]) 
                &amp;&amp; get_piece_side(board[i][j]) == side_to_play) {
                king_sq = {i, j};
                king = board[i][j];
            }
        }
    }
    
    if(king == INVALID) {
        std::cout << "INVALID chess position, king not found on board\n\n";
        assert(false);
    }
    
    int attacking_side = opposite_side();
    
    std::vector<move&gt; filtered_moves;
    for(move m: movelist) {
        make_move(m);
        if(board[m.final_pos.first][m.final_pos.second] == king) {
            king_sq = m.final_pos;
        }
        if(!is_square_attacked(king_sq, attacking_side)) {
            filtered_moves.push_back(m);
        }
        undo_move(m);
    }
    
    return filtered_moves;
    
}

Finally, just modify generate_all_moves as follows:

// Filter the moves instead of returning the movelist directly.
return get_filtered_moves(movelist);

We test our code on the sample position given below(White to move):

-- -- -- -- -- BR -- --   
-- -- -- -- -- -- -- --    
-- -- -- -- -- -- -- BQ  
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BB  
-- -- BP -- -- -- -- -- 
-- -- -- -- WK -- -- -- 

The output is:

-- -- -- -- -- BR -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BQ 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BB 
-- -- BP -- -- -- -- -- 
-- -- -- -- WK -- -- -- 

Side to play: WHITE

-- -- -- -- -- BR -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BQ 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BB 
-- -- BP -- WK -- -- -- 
-- -- -- -- -- -- -- -- 

Side to play: BLACK

-- -- -- -- -- BR -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BQ 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- BB 
-- -- BP -- -- -- -- -- 
-- -- -- -- WK -- -- -- 

Side to play: WHITE

Only 1 valid move was played, which is correct :-). In the upcoming tutorials, we’ll define end of game conditions(checkmate, stalemate and so on..) and eventually build an interface for users to play; one of interfaces will be handed over to an ‘AI’ we program. Well, bye for now…

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