Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

On a chess board, the bishop can move diagonally forward or back by any number of squares. I've never seen a bishop in person, but I can say with a high degree of certainty that they don't move diagonally in real life. But just to be on the safe side, if I ever meet a bishop in real life I'm going to stand directly infront of them so they don't bump into me. Wikipedia has a technically correct but literally impenetrable explanation of how bishops move on chess boards, but I believe I've bested the Wikipedia community with my diagram.

Potential moves of the bishop,
aka "the diagonal piece"

Given a square on a chess board, how do we draw the potential moves of a bishop? In the diagram above, the bishop is in position (3,4). There are four possible directions the bishop can move in.

• Up-left: (0,1) (1,2) (2,3)
• Up-right: (0,7) (1,6) (2,5)
• Down-left: (4,3) (5,2) (6,1) (7,0)
• Down-right: (4,5) (5,6) (6,7)

Each direction radiates outward from the bishop like rays from the sun. To make this easy, work on each diagonal separately.

Radiating up-left.

Mission: write an algorithm that returns the upper-left diagonal.

The bishop is at (3,4). We need an algorithm that returns us the positions (0,1) (1,2) (2,3). If the bishop wanted to move up-left one square from (3,4), it would be in (2,3). If it wanted to move up-left two squares, it would be in (1,2). If it moved up-left three squares, it would be in (0,1). It seems simple enough to generate the list of potential moves: you start from the bishop, then work backwards from there. 

Now let's implement it. Remember the code used to iterate through each square on the board from part one of the blog post? I'll post it here.

The code iterates uses two for loops to iterate through each square on the board. The code starts at board position (0,0) and iterates to the end of the row (0,7). It repeats this until it reaches position (7,7). We used this code to clear the board (overwrite each array element with a zero) and also to draw the board. Here's an illustration of how that code works.

The catch is that you can't use this code to work out where the bishop's potential moves are. Imagine the bishop is at (3,4). When the iteration code reaches (3,4), it will be too late already: you'll have passed some of the squares which are potential bishop moves. The iteration code is only useful if you're trying to work out the potential down-right bishop moves. To work out the potential up-left diagonal bishop moves, you need to work backwards.

In the first post of this blog series, I put some code in the original program to iterate through the two-dimensional board array backwards, just for fun. Here's the code to iterate through the board backwards.



Here's our logic. It's incorrect, but let's run with it for now.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop in the lower-right square.
1. If there is, mark this square as a potential move.
3. Repeat until you reach (0,0).
4. All potential diagonal up-left moves have been marked.

Let's model this theory before we code it. If you need to, put your finger on position (7,7) on the diagram and ask yourself the question: for this square, is there a bishop in the lower-right square?

This algorithm correctly identifies (2,3) as a potential move, but not (1,2) or (0,1) which are also potential moves. Close, but no cigar. We can modify our algorithm to mark some squares with breadcrumbs. A breadcrumb is a marker for a potential move. Why do we need breadcrumbs? Well, it's obvious that (2,3) is a potential move and our algorithm works for this. But this check doesn't work for (1,2). What we can do at (2,3) is drop a breadcrumb: a marker that can be checked for when we get to (1,2). We can modify the algorithm to drop and detect breadcrumbs as follows:

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's model this theory. Again, put your finger on the square and ask the question, is there a bishop or breadcrumb in the lower-right square?

Hey, this works! Time to pop the champagne? Well, no. There's still another flaw in this code. When you're at position (7,7), you're asking the question, is there a bishop or breadcrumb in the lower-right square? In this instance, the lower-right square is (8,8), which doesn't exist. The memory allocated outside of the array could be anything. If you check for position (8,8), you'll get undefined behaviour: when you run your program, board[8][8] could be equal to 0. The next time you run, it could be equal to 5. Or 9. Or 42. I've described why this happens in part two. Basically, you don't know what information is stored outside of the array. All you need to know is that you must not check array locations that don't exist. This will require one final change to the algorithm.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if the lower-right square is within the board
1. If it is, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's code it! I'll also put the code containing #define lines that contain the cell to piece mapping. This is so you know that an array element with value 5 is a bishop, and value 50 is a breadcrumb for a bishop.

Here's an implementation of the algorithm.


Line 1 and 2 contain the for loops that perform the iteration. Because we are iterating backwards, the conditions of the for loop are slightly different.

• Instead of i being equal to 0, i starts at 7 (the end).
• Instead of i iterating until 7, i iterates while it is larger than or equal to 0.
• Instead of incrementing, i decrements.

Line 8 does the bounds checking. The if statement performing the bounds checking has two checks: (j+1 != 8) and (i!=7). If j+1 is equal to 8, that means you're in the final column, so don't check further! If i is equal to 7, you're in the bottom row so don't check further! Line 11 checks whether the down-left square has a breadcrumb or a bishop. Line 11 is only executed if the bounds checking in line 8 is successful. And finally, if all these tests have passed, line 13 marks the square as containing a breadcrumb. Here's the code so far. Copy and pasta it into your IDE and hit compile!


Let's see the output.

Bishop in position (0,0).
This is easy.

Bishop in position (4,4).
Yay, it works!

Bishop in position (3,4).
Woo hoo!

Bishop in position (7,7).
It can move right across the board. Great!
No nasty errors from trying to check array elements
that don't exist. 

Bishop in position (4,7).
It works! And no nasty out of bounds errors.

Great! We've written the code that works out the potential upper-left diagonal moves of a bishop. This was the most difficult diagonal move of the bishop to work out: you needed to combine your knowledge of iterating backwards through two-dimensional arrays, bounds checking, and algorithms. It's easy from here on in! In the next post, I'll discuss how to code the other potential moves of the bishop.

Other posts in this series

Chess in C (Part 1)
Chess in C (Part 2) - Insert Pawn Pun Here
Chess in C (Part 3) - Rook, Rooks, Rookies, Wookies, same thing
Chess in C (Part 4) - I'm asking for input
Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope