Tuesday, June 19, 2012

Chess in C (Part 2) - Insert Pawn Pun Here

I'm glad you could make it to the second instalment of Chess in C! In my last blog post, we made a chessboard out of an array (board[i][j], where i represented rows and j represented columns), put some pieces on the board, and found out that if you have a picnic on a farm that cows, chickens, dogs and ducks will come to share your food.

Sure, invite yourself along.

When we left off, the chess board was looking like this.

Today I'm going to discuss how we can chart the possible moves of pieces. To do this, we need to do some housekeeping. I'm going to add some macros/#define's so that we can mark a square being a potential move for a piece. If you're playing with this code and compiling as we go, take a moment now to stop, copy and paste! If you haven't got this code already, open your IDE and download the code at the end of my previous blog post so you can start modifying it.

I'm also going to update the board display code with extra case statements so that we can display the potential moves. Potential moves will be represented with +.

To simply things, I'll start by removing every piece on the board except for two pawns.

To comment out a line in C, simply surround it with /* and */, or put a // in front of it. If a line is commented out, the compiler will ignore it. Alright, now we're ready to start! Let's take a look at our board now.

Hapless losers!
Let's model a pawn's move. In this exercise, we will assume that the two hapless pawns are in their starting position, and moving forward means they will move downward.

According to the Wikipedia article on chess pawns, there are three valid moves:
1) A pawn can move to the square directly in front of itself, if that square is clear.
2) A pawn on its starting rank can move forward two squares
3) A pawn can move front-left diagonally or front-right diagonally to capture another piece.

We're going to keep it simple and only implement the first and second pawn moves. We can always add functionality later.

If a pawn is in its starting position at board[1][1], then there are two valid moves: board[2][1] (if the pawn moves forward one square) and board[3][1](if the pawn moves forward two squares). You can confirm on the board below: place your finger (or pencil or assorted pointing apparatus) on the board square represented by board[1][1]. Now move your finger down one square to simulate a pawn moving forward once: you're now at board[2][1]. If you move your finger down one square again, you will reach board[3][1]. Easy!

Use this as an aid. Wipe after use.

Obviously, we can't code every permutation of move into our chess application. If we had infinite time, we could write a million if statements for each square and piece. But I don't have that sort of time: Crust Pizza closes in an hour! Instead, we can write a simple algorithm that calculates possible moves for a piece. If we represent the board row as i, we could say that the valid move for any pawn at board[i][j] is board[i+1][j]. If a pawn is in its starting position, it can move forward two squares, we could say the pawn's valid move would be board[i+2][j].

So how do we code this in C?

There are a few ways of doing this, and they're all a variation of our board zero'ing code: we 1) iterate through every square in the board, 2) check if there's a pawn in that square, and 3) if there is a pawn in that square, mark the potential moves.

Cast your mind back to my last post. There was a nested for loop which let us iterate through every position on the board to mark it empty. Here it is below.

Let's modify it a little. We'll start by getting rid of that board zero'ing code and...*pulls out chainsaw*...done! Let's look.

The if statement checks whether the current square contains a pawn. If the if statement evaluates to true (ie. there is a pawn in the current square), then we will mark the square below it as a potential pawn move. Let's run it and see what happens.

Two pawns in their starting position.

Looks good! We can add a second if statement to determine the potential move if the pawn is in its starting position (row 1 - remember, in C we start counting from 0!) and allowed to move forward two squares (to board [i+2][j]).

Looks good? Let's see what happens.

That's two pawns and their potential moves, not a
game of Minesweeper.

If you've made it this far, that's great! You've made a simple chess board and calculated the position of a few pieces. You've also unintentionally created one of the most common bugs in the history of programming: an out of bounds errors. Don't feel bad: I intentionally led you down this path. You've got to experience the problem before you can know how to prevent it.

So what is a out of bounds error? Well, it makes demons fly out of your nose. Let me explain.

Our pawn move calculator doesn't take into account what happens if the pawn is on the final row. What if the pawn was on the final row? According to rules of chess, the pawn can be promoted to a Queen, which is helpful. But ignore that for now. If our pawn is on the final row of the board (i == 7), then the next line of code (board[i+1][j] = POTENTIAL_MOVE_PAWN) will modify a board position that doesn't exist: board[8][j]. Look at the aid: there is no row 8! If your program modified row 8, I kid you not: you would be modifying THE MATRIX. This is an out of bounds error.

The people you'll annoy if you don't bounds check your arrays.

C is an unsafe language. In a smarter language like Java, Java would pick up an invalid statement like board[8][j] = POTENTIAL_MOVE_PAWN and say "NO YUO! That doesn't exist! Go back to programming school" then crash your program. But C will happily let you make your mistake. The catch is, your bad statement won't modify the board. You'll modify the variables whose memory is stored after the board, which causes undefined behaviour. Undefined behaviour could be anything: if you're lucky, the undefined behaviour will cause your program to crash and you'll find your mistake. If you're unlucky, the undefined behaviour won't do anything...for now. This well written post by jalf (someone smarter than me) on stackoverflow.com describes undefined behaviour well:

Welcome to every C/C++ programmers bestest friend: Undefined Behavior. 
There is a lot that is not specified by the language standard, for a variety of reasons. This is one of them.
In general, whenever you encounter undefined behavior, anything might happen. The application may crash, it may freeze, it may eject your CD-ROM drive or make demons come out of your nose. It may format your harddrive or email all your porn to your grandmother.
It may even, if you are really unlucky, appear to work correctly.
The language simply says what should happen if you access the elements within the bounds of an array. It is left undefined what happens if you go out of bounds. It might seem to work today, on your compiler, but it is not legal C or C++, and there is no guarantee that it'll still work the next time you run the program. Or that it hasn't overwritten essential data even now, and you just haven't encountered the problems that is going to cause yet.

So let's modify our code and do a simple bounds check. All we need to do is write an if statement that prevents the code from being executed if the row (i) is the final row (7).

There we go. All fixed! If the row is 7 (the final row), there's no way the code modifying the contents of the next row (which doesn't exist) which prevents undefined behaviour from occurring (demons flying out of your nose).

That's it for today! I thought I'd get to some more interesting parts (like calculating potential moves of bishops and horses), but we gotta nail the simple stuff down first.

Thanks for reading so far. Here's a full copy of the code so you can play around with it. Remember kids, always bounds check your arrays!

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