Hey folks! Last time we dealt with move generation for sliders. This time, we’ll see how to generate good old knight moves. We’ve actually gone through the more arduous part of slider move generation first, so the following code snippet should be a piece of cake for you:

// Move generation for knights - both white and black

// 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}};

// Generate all knight moves -&gt; capture an opponent piece or just move somewhere.
for(auto next : knight_moves) {
    var_i = i + next.first;
    var_j = j + next.second;
    if(is_square_in_range(var_i, var_j)) {
        next_piece = board[var_i][var_j];
        if(next_piece == BL) {
            movelist.push_back(move({i, j}, {var_i, var_j}));
        } else if(get_piece_side(next_piece) == opposite_side()) {
            movelist.push_back(move({i, j}, {var_i, var_j}, next_piece));    
        }
    }
}

The array knight_moves represents the directions in which a knight can move, like so:

    0  1  2  3  4  5  6  7
0  -- -- -- -- -- -- -- --                          
1  -- -- -- -- -- -- -- --           
2  -- -- -- XX -- XX -- --                      
3  -- -- XX -- -- -- XX --                              
4  -- -- -- -- BN -- -- -- 
5  -- -- XX -- -- -- XX --
6  -- -- -- XX -- XX -- --          
7  -- -- -- -- -- -- -- --

The figure above should make the choice of increments clear. We simply get the next square, check if it is within the board, and generate a capture or simple move accordingly. That’s it! Simple, wasn’t it? Now on to pawn move generation.

if(curr_piece == WP || curr_piece == BP) {
    int increment_sign = (side_to_play == WHITE ? -1 : 1);
    
    // Move the pawns 1 square ahead
    // Note that we have to take care of pawn promotion as well
    var_i = i + increment_sign;
    var_j = j;
    if(is_square_in_range(var_i, var_j)) {
        next_piece = board[var_i][var_j];
        if(next_piece == BL) {
            movelist.push_back(move({i, j}, {var_i, var_j}));
        }
    }
    
    // Move the pawns 2 squares ahead if the conditions are satisfied
    var_i = i + increment_sign * 2;
    var_j = j;
    if((i == 6 && curr_piece == WP) || (i == 1 && curr_piece == BP)) {
        next_piece = board[var_i][var_j];
        if(next_piece == BL) {
            movelist.push_back(move({i, j}, {var_i, var_j}));
        }
    }

    ...(skipped)...
}

Here, we are moving the pawn one step ahead or two steps ahead. To avoid repeating the code, I have something called as increment_sign, which is basically a variable with value -1 or 1 ( -1 for white, since they are going ‘down’ with reference to our representation and 1 for black). Note that as per the way we print the board, the white pawns still go ‘up’ and the black pawns still go ‘down’.

We generate diagonal capture moves in a similar way, just check if any one of the diagonals has an enemy piece and if so; capture it.

// Diagonal captures
var_i = i + increment_sign;
var_j = j + 1;
if(is_square_in_range(var_i, var_j)) {
    next_piece = board[var_i][var_j];
    if(get_piece_side(next_piece) == opposite_side()) {
        movelist.push_back(move({i, j}, {var_i, var_j}, next_piece));    
    }
}

var_i = i + increment_sign;
var_j = j - 1;
if(is_square_in_range(var_i, var_j)) {
    next_piece = board[var_i][var_j];
    if(get_piece_side(next_piece) == opposite_side()) {
        movelist.push_back(move({i, j}, {var_i, var_j}, next_piece));    
    }
}

Simple, wasn’t it? Unlike a bishop or a queen, a pawn cannot move backwards, hence we check only 2 directions.

For the king, we do something similar to what we did with the knight. A king can move in all 8 directions, but only 1 square. Hence, the directions in which it can move are (0, ±1), ( ±1, 0) and (±1, ±1). See if you can come up with code for this(look here to verify).

The move generator produces an output of 20 moves for the start position, which is correct. You can put any arbitrary position you like(just edit the variable init_board) and check the output. Play around with different board positions until you are convinced.

What we did today was pretty simple, but what about special moves such as castling, en passant and pawn promotion? We’ll implement these in the next article.

There is another pressing issue(which we’ll cover soon): what about the fact that our move generator produces moves that could put in the king in check or even result in its capture? We have essentially generated pseudo-legal moves. These need to be filtered out. Actually, there is another approach, which involves tweaking the AI graph search function; although I believe in taking a simpler approach for your first implementation.

That should give you flavor of the upcoming stuff..see you 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