Checkers - Game Logic

We begin our exploration of game programming by looking at how we can implement a well-known game, checkers, using JavaScript. For now, we'll use the JavaScript console to view and play our game, and in future lessons we'll look at several html5 methods for implementing graphics of the game board and pieces.

Representing Game State

Every game maintains state - which decribes the current status of all "important" aspects of the game world. I.e., state would include if a door was open or closed, were it a door the player can use. If the door is non-functional in the game world, there is no reason to store it as state - doing so would be a unnecessary consumption of memory.

Consider our game of checkers - what state is important to store?

  • The position of each piece on the board
  • The type of piece (i.e. is the checker kinged?)
  • The color of the piece (i.e. who does the checker belong to?)
  • Whose turn is it?
  • Is the game over (i.e. has someone won?)

State is typically stored in one or more variables in RAM. For saving and loading games, we can also seralize this state and save/load from disk.

For our game, let's place all of our state in a single variable, state, by using a JavaScript Object. One useful way to reason about JavaScript objects is to view them as a collection of properties, i.e. a key/value store (also called a map or dictionary). Thus, our state variable stores an object with properties board (the game board and peices thereon), turn (whose turn it is), over (a boolean indicating if the game is still going false or ended true), and captures (a count of all white and black pieces captured).

Our state then would look something like this:

In [ ]:
/** The state of the game */
var state = {
  over: false,
  turn: 'b',
  board: [
    [null,'w',null, 'w', null, 'w',  null, 'w',  null, 'w'],
    ['w',null,'w',null,'w',null,'w',null,'w',null],
    [null,'w',null,'w',null,'w',null,'w',null,'w'],
    ['w',null,'w',null,'w',null,'w',null,'w',null],
    [null, null, null, null, null, null, null, null, null, null],
    [null, null, null, null, null, null, null, null, null, null],
    [null,'b',null,'b',null,'b',null,'b',null,'b'],
    ['b',null,'b',null,'b',null,'b',null,'b',null],
    [null,'b',null,'b',null,'b',null,'b',null,'b'],
    ['b',null,'b',null,'b',null,'b',null,'b',null]
  ],
  captures: {w: 0, b: 0}
}

One important aspect to note is that when declaring the variable state as well as the properties, we did not declare the type of the variable. This is because JavaScript is a dynamically typed language. There are no explicit types, and variables can be reassigned a value with a different type. The value will typically be cast by the langauge into an appropriate form for the action called out upon it in your code, i.e.:

In [ ]:
var b = 56;
var c = "foo";
console.log(b + c);

Will output the string "56foo", because the integer 56 is converted to a string as the + is interpreted as a concatenation operation instead of addition, as c is a string. While dynamic typing is a powerful ability, it is also a very common GOTCHA causing problems for programmers more used to statically typed languages.

The state.board property is composed of a JavaScript Array object containing other Array objects. The Array is a singularly powerful tool in the JavaScript developer's arsenal. In implementation, it is actually more similar to a list than the traditional linear memory array. It also implements methods that allow it to be used as a stack (push, pop) and queue (shift, push).

Peformance Note Because it is implemented as a list, these operations are quite fast - linear in fact <O(1)>. However, because array elements are not necessarily located near each other, iterating over the array can cause numerous cache misses, resulting in poorer performance than in other languages. There is a linear, statically-declared, in-memory array implementation in JavaScript that is more in-line with our traditional understandings of arrays, and this will be covered later in the course.

The astute observer may note that in the board array, we are using null values to indicate both empty black and white squares. Since pieces cannot ever move onto a white square, we could remove these entries from the data representation. However, this would make the algorithms for determining legal moves more involved, so there is a clear trade-off in code readability and efficiency. In this case, we'll opt for the former, as our memory demand is not great, nor does checkers require great processing speed. But in other circumstances, efficiency may be more important. Game programming is full of these kinds of trade-offs.

Determining Legal Moves

Next, let's look at how we can deterine if a move is legal. We'll need to start with a peice to move. One easy way to identify the piece in question is to use coordinates corresponding to its position on the board (i.e the indices for the state.board array). Once we've selected the square holding piece, we need to:

  1. Determine if there actually is a piece on the square to move
  2. Make sure that the piece belongs to the player whose turn it is
  3. Check to see if we can slide forward (and backward, for kings)
  4. Determine if any jumps are possible

This is a lot of functionality, so it makes sense to break it into multiple functions. Let's define one for checking possible slides, one for checking possible jumps, and one for doing our 'due dilligence' checks that also collects moves from the other two functions. This 'collecting' and representing of moves also needs to be carefully considered.

Representing Moves

We have two different kinds of moves possible. A slide simply moves the checker into an unocupied square adjacent to its current square. At a minimum, we only need to know what square we are moving into. A jump needs to know not only what square it is moving into, but a way of identifying the checker it is jumping over (and capturing). Moreover, a jump could include jumping multiple checkers. And, if we want to implement animations of the jumping, we also need to know each intermediate square we land on.

One way of representing these disparate operations is to represent them as a JavaScript object with a type property. Move objects with the 'slide' type would then have a property for the x and y landing position. Move objects with the 'jump' type would have an array (list) of captures and landings. Before we process either of them, we'd check the type to determine the appropriate way of processing the move.

We can put both kinds of moves into an array of possible moves that we pass from function to function, allowing them each to add additional moves they determine possible. This array is a form of the general accumulator design pattern. An alternative would be returning arrays to calling functions, which would then be merged and returned up the function stack. An example of such an array of moves appears below:

In [ ]:
var moves = [
    {type: 'slide', x: 3, y:3},
    {type: 'jump', captures: [{x:1, y:3}], jump: [{x:0, y:2}]},
    {type: 'jump', captures: [{x:1, y:3}, {x:1, y:1}], jump: [{x:0, y:2},{x:2, y:0}]}
]

Note also that our second jump move contains the first jump move... as we can choose not to jump the second checker.

This example also demonstrates the flexibility of a dynamically typed language like JavaScript. To accomplish the same task in C#, for example, we'd need to declare an interface for Move that would define the property type, and do a lot of dynamic casting based in this value. In C++, we might choose to utilize a union to achieve a similar effect while optmizing our memory consumption by storing a bool (for type) and two ints (x & y) or a bool (type) and two addresses (captures array and jump array). Clearly, our langauge of implementation has a strong effect on how we structure our code.

The use of a move object is itself an example of the Command Pattern, as each move essentially represents a function we might call to move a peice in the corresponding way. We'll revisit this when we implement choosing a move.

Determining if a Slide is Possible

Let's move onto setting up these functions, and start with the easiest challenge: to determine if a checker can slide into a square. For this decision we need to know which square we're checking, and the overall state of the board (to determine if the square is already occupied). The last is currently stored in a global variable, state, so we don't need to provide it to the function. The remaining variables we'll take as function parameters. We also want to pass in our accumulator, the moves array, which may or may not already have values in it:

In [ ]:
function checkSlide(moves, x, y) {
  // Check square is on grid
  if(x < 0 || x > 9 || y < 0 || y > 9) return;
  // check square is unoccupied
  if(state.board[y][x]) return;
  // legal move!  Add it to the move list
  moves.push({type: 'slide', x: x, y: y});
}

The function is relatively straightforward. First, we test that we are moving onto a square on the board, and end execution if it is not. We often call this kind of test a quick-rejection test, as it minimizes the number of instructions that need to be carried out to evalute the function. Since x and y are passed into this function, we don't need to do any memory accessing to use them, and comparision operators and boolean operators are relatively fast to process.

Then we check that the square is unoccupied. This does involve an array access, which does require a potential dip into memory - so slightly more costly. Also, note that by placing this after our position is on the board check, we eliminate the possibility of trying to access an index outside the bounds of our array. Similarly to our first rejection test, if the square is occupied, we stop execution with a return.

Finally, if we've passed both our tests, we know the square is unoccupied and we can potentially move into it. We push a new slide move into our moves array (which was passed by reference, so it exists outside the scope of our function with the new move added).

Determining if a Jump is Possible

Jumping is a bit more involved, as we may be able to jump more than one checker. Moreover, we need to collect all possible combinations of jumps that are possible. This suggests we'll need to employ some kind of recursive algorithm - i.e. find all jumps possible from our current location, and then all jumps possible from where we land. We also need to be able to pass on a partially completed jump pattern to this recursive function. But this partially completed jump pattern also needs to be stored in our moves array as a legal move. As we pass all Objects and Arrays in Javascript by reference, we need to ensure the arrays in the moves array are not the same as the ones we are using for future jumps. In other words, we need to clone our jumping-related arrays. Let's start with a helper function for doing so:

In [ ]:
function copyJumps(jumps) {
  // Use Array.prototype.slice() to create a copy
  // of the landings and captures array.
  var newJumps = {
    landings: jumps.landings.slice(),
    captures: jumps.captures.slice()
  }
  return newJumps;
}

Here we assume that our partially completed jump pattern consists of two arrays: landings and jumps (these conform to the same pattern of lists of objects with x and y properties we defined in the jump move type above). We can clone individual arrays with a call to thier slice() method, which when called without arguments, has the handy effect of creating a shallow copy of the array (since our x and y values are primitive integers, a shallow copy suffices for our needs). We then construct a new object (read: new reference) with properites of landings and captures and return it. We can now use the newJumps object without fear of accidentally altering our original jumps object.

Now we turn our attention to the trickier problem of determining what jumps are possible. Let's start by decomposing the problem into two problems: determining if a landing is legal, and determining where we can jump. We'll start with the simpler of these, determining if a jump is legal, which is very similar to the earlier process of determining if a slide was legal:

  1. Is the landing square on the board?
  2. Is that square unoccupied?
  3. Is there a piece on the square we'd be passing over to capture?
  4. Is the peice we are capturing our opponents'?

This also suggests what parameters our method would need to know about: the square we are landing on, and the square we are capturing from. We also need to know the color of our moving player and the overall board, both of which are in our global state variable. We also need our moves accumulator, and a second accumulator for collecting partial jump patterns. Our function would then look something like:

In [ ]:
function checkLanding(moves, jumps, cx, cy, lx, ly) {
  // Check landing square is on grid
  if(lx < 0 || lx > 9 || ly < 0 || ly > 9) return;
  // Check landing square is unoccupied
  if(state.board[ly][lx]) return;
  // Check capture square is occupied by opponent
  if(state.turn === 'b' && !(state.board[cy][cx] === 'w' || state.board[cy][cx] === 'wk')) return;
  if(state.turn === 'w' && !(state.board[cy][cx] === 'b' || state.board[cy][cx] === 'bk')) return;
  // legal jump! add it to the moves list
  jumps.captures.push({x: cx, y: cy});
  jumps.landings.push({x: lx, y: ly});
  moves.push({
    type: 'jump',
    captures: jumps.captures.slice(),
    landings: jumps.landings.slice()
  });
  // check for further jump opportunities
  checkJump(moves, jumps, lx, ly);
}

This function follows the same pattern of utilzing rejection tests. If we pass each of these, we add a jump command to our moves array, again using Array.prototoype.slice to ensure our move's captures and landings arrays are not modified. Finally, we trigger our next function, checkJump, to determine if further jump opportunities exist.

This function likewise needs to pass our two accumulators, and the position we will be jumping from (which is our landing position). Inside it, we need to determine which squares we can jump to based on what piece we are currently moving.

In [ ]:
function checkJump(moves, jumps, piece, x, y) {
  switch(piece) {
    case 'b': // black can only move down the board diagonally
      checkLanding(moves, copyJumps(jumps), piece, x-1, y-1, x-2, y-2);
      checkLanding(moves, copyJumps(jumps), piece, x+1, y-1, x+2, y-2);
      break;
    case 'w':  // white can only move up the board diagonally
      checkLanding(moves, copyJumps(jumps), piece, x-1, y+1, x-2, y+2);
      checkLanding(moves, copyJumps(jumps), piece, x+1, y+1, x+2, y+2);
      break;
    case 'bk': // kings can move diagonally any direction
    case 'wk': // kings can move diagonally any direction
      checkLanding(moves, copyJumps(jumps), piece, x-1, y+1, x-2, y+2);
      checkLanding(moves, copyJumps(jumps), piece, x+1, y+1, x+2, y+2);
      checkLanding(moves, copyJumps(jumps), piece, x-1, y-1, x-2, y-2);
      checkLanding(moves, copyJumps(jumps), piece, x+1, y-1, x+2, y-2);
      break;
  }
}

We can implement this fairly easily with a switch statement. Single checkers can only move diagonally one direction down the board. Kings can move diagonally in any direction. GOTCHA However, this does introduce a possible recursion issue, because as we currently have our two functions written, a king could infinitely jump back and forth over the same peice! Which in turn, means our program can get caught in an infinite recursion loop. We also need to pass the piece into our checkJump function, but we don't have it in our current version of checkLanding. Let's address both of these by refactoring our checkLanding function, and adding an initial x and y to our jump object:

In [ ]:
function checkLanding(moves, jumps, piece, cx, cy, lx, ly) {
  // Check that we're not jumping back to our starting position
  if(lx == jumps.x && ly == jumps.y) return;
  // Check landing square is on grid
  if(lx < 0 || lx > 9 || ly < 0 || ly > 9) return;
  // Check landing square is unoccupied
  if(state.board[ly][lx]) return;
  // Check capture square is occupied by opponent
  if(state.turn === 'b' && !(state.board[cy][cx] === 'w' || state.board[cy][cx] === 'wk')) return;
  if(state.turn === 'w' && !(state.board[cy][cx] === 'b' || state.board[cy][cx] === 'bk')) return;
  // Check that we haven't landed on this square previously
  if(0 < jumps.landings.indexOf(function(landing){return landing.x == lx && landing.y == ly;})) return;
  // legal jump! add it to the moves list
  jumps.captures.push({x: cx, y: cy});
  jumps.landings.push({x: lx, y: ly});
  moves.push({
    type: 'jump',
    captures: jumps.captures.slice(),
    landings: jumps.landings.slice()
  });
  // check for further jump opportunities
  checkJump(moves, jumps, piece, lx, ly);
}

The first line we added, if(lx == jumps.x && ly == jumps.y) return;, assumes that the jumps object has an x and y variable which are the square indices where our checker started from, and rejects the potential landing if it is the same as that square.

Similarly, the line if(0 < jumps.landings.indexOf(function(landing){return landing.x == lx && landing.y == ly;})) return; uses the Array.prototype.indexOf() function to determine if the landing square is in the jumps object's list of prior landings. If it is, the index is returned. If not, -1 is returned, so comparing the return value to 0 with the less than operator allows us to quick reject as well. Performance note: because indexOf() returns as soon as it finds the landing, the average performance would be o(n/2), while worst case is linear O(n). Since the landing data is unsorted, this is about the best we can do.

Of course, since we added to our jumps object, we need to refactor our copyJumps() method:

In [ ]:
function copyJumps(jumps) {
  // Use Array.prototype.slice() to create a copy
  // of the landings and captures array.
  var newJumps = {
    x: jumps.x,
    y: jumps.y,
    landings: jumps.landings.slice(),
    captures: jumps.captures.slice()
  }
  return newJumps;
}

Since x and y are primitives, their data will aways be copied - no need to clone them.

Finally, we need to write our initial getLegalMoves() function, which uses these helper functions we just built to collect and return an array of all legal moves:

In [ ]:
function getLegalMoves(piece, x, y) {
  var moves = [];
  switch(piece) {
    case 'b': // black can only move down the board diagonally
      checkSlide(moves, x-1, y-1);
      checkSlide(moves, x+1, y-1);
      checkJump(moves, {captures:[],landings:[], x:x, y:y}, piece, x, y);
      break;
    case 'w':  // white can only move up the board diagonally
      checkSlide(moves, x-1, y+1);
      checkSlide(moves, x+1, y+1);
      checkJump(moves, {captures:[],landings:[], x:x, y:y}, piece, x, y);
      break;
    case 'bk': // kings can move diagonally any direction
    case 'wk': // kings can move diagonally any direction
      checkSlide(moves, x-1, y+1);
      checkSlide(moves, x+1, y+1);
      checkSlide(moves, x-1, y-1);
      checkSlide(moves, x+1, y-1);
      checkJump(moves, {captures:[],landings:[], x:x, y:y}, piece, x, y);
      break;
  }
  return moves;
}

In most ways, this function parallels that of our checkJump - we use a switch statement to determine what kind of piece is moving, and determine what squares are within reach of a slide, and start the recurive evaluation of jumping. Note that we supply a jumps object to our checkJump with empty lists for captures and landings, along with the initial x and y indices. We also supply the moves variable, an Array, to all of our children functions. Because Arrays are passed by reference, this is the same array in all called functions, and the resulting moves added to it are preserved and returned at the end of getLegalMoves().

Applying Moves

Once we have a list of legal moves, we need to select one to carry out. Remember that we mentioned our moves represented the command pattern - in other words, each move represents a function call that has been reified (abstracted, in this case, into an object). As such, it contains all the information we need to carry out the function it represents (i.e. sliding or jumping). So our task is simply to take the move object, and apply the appropriate result:

In [ ]:
function applyMove(x, y, move) {
  if(move.type === "slide") {
    state.board[move.y][move.x] = state.board[y][x];
    state.board[y][x] = null;
  } else {
    move.captures.forEach(function(square){
      var piece = state.board[square.y][square.x];
      state.captures[piece.substring(0,1)]++;
      state.board[square.y][square.x] = null;
    });
    var index = move.landings.length - 1;
    state.board[move.landings[index].y][move.landings[index].x] = state.board[y][x];
    state.board[y][x] = null;
  }
}

First, we determine if the move was a jump or a slide. Slide is the easier of the two; we simply reassign the position of the piece in question. For captures, we iterate through the capture squares, removing those pieces and incrementing the appropriate capture counter of the state variable. Then we move our piece to its final position.

Note that our applyMove() only applies the logical results to the state. When we add rendering, we will either need to refactor this function to also render the visible results, or place that code elsewhere.

Checking for Victory

Checking for victory is straightforward - we just need to see if either player's captured count is equal to the total number of checkers on thier side. If it is, they've lost, and we can return an indication to that effect (in this case, a string), and mark the game as over in our state variable:

In [ ]:
function checkForVictory() {
  if(state.captures.w == 20) {
    state.over = true;
    return 'black wins';
  }
  if(state.captures.b == 20) {
    state.over = true;
    return 'white wins';
  }
  return null;
}

Again, this function may need to be tweaked to account for our rendering.

Starting the Next Turn

Starting the next turn is simply a matter of switching which player's turn it is in the state variable:

In [ ]:
function nextTurn() {
  if(state.turn === 'b') state.turn = 'w';
  else state.turn = 'b';
}

This wraps up our discussion of the logic behind the game of checkers. Next we'll turn our attention to how we can visually display the game.