Chapter 7.5.3 – Example: Checkers | Introduction to Programming Using Java

Chapter 7.5.3 – Example: Checkers | Introduction to Programming Using Java

 

7.5.3 Example: Checkers

 

For the rest of this section, we’ll look at a more substantial example. We look at a program that lets two users play checkers against each other. A player moves by clicking on the piece to be moved and then on the empty square to which it is to be moved. The squares that the current player can legally click are hilited. The square containing a piece that has been selected to be moved is surrounded by a white border. Other pieces that can legally be moved are surrounded by a cyan-colored border.

If a piece has been selected, each empty square that it can legally move to is hilited with a green border. The game enforces the rule that if the current player can jump one of the opponent’s pieces, then the player must jump. When a player’s piece becomes a king, by reaching the opposite end of the board, a big white “K” is drawn on the piece. You can try an applet version of the program in the on-line version of this section. Here is what it looks like:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

I will only cover a part of the programming of this applet. I encourage you to read the complete source code, Checkers.java. At over 750 lines, this is a more substantial example than anything you’ve seen before in this course, but it’s an excellent example of state-based, event-driven programming.

The data about the pieces on the board are stored in a two-dimensional array. Because of the complexity of the program, I wanted to divide it into several classes. In addition to the main class, there are several nested classes. One of these classes is CheckersData, which handles the data for the board. It is mainly this class that I want to talk about.

The CheckersData class has an instance variable named board of type int[][]. The value of board is set to “new int[8][8]”, an 8-by-8 grid of integers. The values stored in the grid are defined as constants representing the possible contents of a square on a checkerboard:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

The constants RED and BLACK are also used in my program (or, perhaps, misused) to represent the two players in the game. When a game is started, the values in the variable, board, are set to represent the initial state of the board. The grid of values looks like

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

A black piece can only move “down” the grid. That is, the row number of the square it moves to must be greater than the row number of the square it comes from. A red piece can only move up the grid. Kings of either color, of course, can move in both directions.

One function of the CheckersData class is to take care of all the details of making moves on the board. An instance method named makeMove() is provided to do this. When a player moves a piece from one square to another, the values stored at two positions in the array are changed. But that’s not all. If the move is a jump, then the piece that was jumped is removed from the board.

(The method checks whether the move is a jump by checking if the square to which the piece is moving is two rows away from the square where it starts.) Furthermore, a RED piece that moves to row 0 or a BLACK piece that moves to row 7 becomes a king. This is good programming: the rest of the program doesn’t have to worry about any of these details. It just calls this makeMove() method:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

An even more important function of the CheckersData class is to find legal moves on the board. In my program, a move in a Checkers game is represented by an object belonging to the following class:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

The CheckersData class has an instance method which finds all the legal moves that are currently available for a specified player. This method is a function that returns an array of type CheckersMove[ ]. The array contains all the legal moves, represented as CheckersMove objects. The specification for this method reads

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

A brief pseudocode algorithm for the method is the list

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

 

Now, what is this “list”? We have to return the legal moves in an array. But since an array has a fixed size, we can’t create the array until we know how many moves there are, and we don’t know that until near the end of the method, after we’ve already made the list! A neat solution is to use an ArrayList instead of an array to hold the moves as we find them. In fact, I use an object defined by the parameterized type ArrayList<CheckersMove> so that the list is restricted to holding objects of type CheckersMove.

As we add moves to the list, it will grow just as large as necessary. At the end of the method, we can create the array that we really want and copy the data into it:

 

75 Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

Now, how do we find the legal jumps or the legal moves? The information we need is in the board array, but it takes some work to extract it. We have to look through all the positions in the array and find the pieces that belong to the current player. For each piece, we have to check each square that it could conceivably move to, and check whether that would be a legal move. There are four squares to consider. For a jump, we want to look at squares that are two rows and two columns away from the piece.

Thus, the line in the algorithm that says “Find any legal jumps and add them to moves” expands to:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

The line that says “Find any other legal moves and add them to moves” expands to something similar, except that we have to look at the four squares that are one column and one row away from the piece. Testing whether a player can legally move from one given square to another given square is itself non-trivial. The square the player is moving to must actually be on the board, and it must be empty. Furthermore, regular red and black pieces can only move in one direction. I wrote the following utility method to check whether a player can make a given non-jump move:

 

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

This method is called by my getLegalMoves() method to check whether one of the possible moves that it has found is actually legal. I have a similar method that is called to check whether a jump is legal. In this case, I pass to the method the square containing the player’s piece, the square that the player might move to, and the square between those two, which the player would be jumping over. The square that is being jumped must contain one of the opponent’s pieces. This method has the specification:

 

79 Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

Given all this, you should be in a position to understand the complete getLegalMoves() method. It’s a nice way to finish off this chapter, since it combines several topics that we’ve looked at: one-dimensional arrays, ArrayLists, and two-dimensional arrays:

 

80 Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

checkers

 

82 Chapter 7.5.3 - Example: Checkers | Introduction to Programming Using Java

 

 

 

 

 

Read More…

1 thought on “Chapter 7.5.3 – Example: Checkers | Introduction to Programming Using Java”

Leave a Comment