2.4: Case Study- Simulating a Two-Person Game

In this section, we will design and write the definition for a class that keeps track of the details of a well known, two-person game. We will focus on details of designing the definition of a class in the Java language. Our objective is to understand what the program is doing and how it works without necessarily understanding why it works the way it does. We will get to “why” later in the book.

The game we will consider is played by two persons with a row of sticks or coins or other objects. The players alternate turns. A player must remove one, two, or three sticks from the row on his or her turn. The player who removes the last stick from the row loses. The game can be played with any number of sticks but starting with twenty one sticks is quite common. This game is sometimes referred to as the game of "Nim", but there is a similar game involving multiple rows of sticks that is more frequently given that name. Thus we will refer to this game as "One Row Nim".

Designing a OneRowNim class

Problem Specification

Let’s design a class named OneRowNim that simulates the game of One Row Nim with a row of sticks. An object constructed with this class should manage data that corresponds to having some specified number of sticks when the game begins. It should keep track of whose turn it is and it should allow a player to diminish the number of sticks remaining by one, two, or three. Finally, a OneRowNim object should be able to decide when the game is over and which player has won.

Problem Decomposition

Let’s design OneRowNim so that it can be used in with different kinds of user interfaces. One user interface could manage a game played by two persons who alternately designate their moves to the computer. Another user interface could let a human player play against moves made by the computer. In either of these cases we could have a human player designate a move by typing from the keyboard after being prompted in a console window or, alternatively, by inputting a number into a text field or selecting a radio button on a window. In this chapter, we will be concerned only with designing an object for managing the game. We will design user interfaces for the game in subsequent chapters.

Class Design: OneRowNim

As we saw in the Riddle example, class definitions can usually be broken down into two parts: (1) the information or attributes that the object needs which must be stored in variables, and (2) the behavior or actions the object can take which are defined in methods. In this chapter, we will focus on choosing appropriate instance variables and on designing methods as blocks of reusable code. Recall that a parameter is a variable that temporarily stores data values that are being passed to a method when that method is called. In this chapter, we will restrict our design to methods that do not have parameters and do not return values. We will return to the problem of designing changes to this class in the next chapter after an in-depth discussion of method parameters and return values.

The OneRowNim object should manage two pieces of information that vary as the game is played. One is the number of sticks remaining in the row and the other is which player has the next turn. Clearly, the number of sticks remaining corresponds to a positive integer that can be stored in a variable of type int. One suitable name for such a variable is nSticks. For this chapter, let us assume that the game starts with 7 sticks, rather than 21, to simplify discussion of the program.

Data designating which player takes the next turn could be stored in different ways. One way to do this is to think of the players as player one and player two and store a 1 or 2 in an int variable. Let’s use player as the name for such a variable and assume that player one has the first turn.

The values of these two variable for a particular OneRowNim object at a particular time describes the object’s state. An object’s state at the beginning of a game is a 7 stored in nSticks and 1 stored in player. After player one removes, say, two sticks on the first turn, the values 5 and 2 will be stored in the two variables.

Method Decomposition

Now that we have decided what information the OneRowNim object should manage, we need to decide what actions it should be able to perform. We should think of methods that would be needed to communicate with a user interface that is both prompting some human players as well as receiving moves from them. Clearly, methods are needed for taking a turn in the game. If a message to a OneRowNim object has no argument to indicate the number of sticks taken, there will need to be three methods corresponding to taking one, two, or three sticks. The method names takeOne(), takeTwo(), and takeThree() are descriptive of this action. Each of these methods will be responsible for reducing the value of nSticks as well as changing the value of player.

We should also have a method that gives the information that a user needs when considering a move. Reporting the number of sticks remaining and whose turn it is to the console window would be an appropriate action. We can use report() as a name for this action.

Figure 2.16 is a UML class diagram that summarizes this design of the OneRowNim class. Note that the methods are declared public (\(+\)) and will thereby form the interface for a OneRowNim object. These will be the methods that other objects will use to interact with it. Similarly, we have followed the convention of designating an object’s instance variables—the ’s instance variables—be kept hidden from other objects, and so we have designated them as private(\(-\)).

Defining the OneRowNim Class

Given our design of the OneRowNim class as described in Figure 2.16, the next step in building our simulation is to begin writing the Java class definition.

The Class Header

We need a class header, which will give the class a name and will specify its relationship to other classes. Like all classes that are designed to create objects that could be used by other objects or classes, the class OneRowNim should be preceded by the public modifier. Because the class OneRowNim has not been described as having any relationship to any other Java class, its header can omit the extends clause so it will be a direct subclass of Object (Figure 2.17). Thus, the class header for OneRowNim will look like:

public class OneRowNim  // Class header
{                       // Beginning of class body

}                       // End of class body

The Class’s Instance Variables

The body of a class definition consists of two parts: the class-level variables and the method definitions. A class-level variable is a variable whose definition applies to the entire class in which it is defined. Instance variables, which were introduced in Chapter 1, are one kind of class-level variable.

In general, a class definition will take the form shown in Figure [fig-form].

public class ClassName
{  // Instance and class variables
     VariableDeclaration1
     VariableDeclaration2
     ...
    // Instance and class methods
     MethodDefinition1
     MethodDefinition2
     ...
} // End of class

Although Java does not impose any particular order on variable and method declarations, in this book we’ll define the class’s class-level variables at the beginning of the class definition, followed by method definitions. Class-level variables are distinguished from local variables. A local variable is a variable that is defined within a method. Examples would be the variables q and a that were defined in the Riddle(String q, String a) constructor (Fig. [fig-riddleclass2]). As we will see better in Chapter 3, Java handles each type of variable differently.

A declaration for a variable at class level must follow the rules for declaring variables that were described in Section [subsec:vardecl] with the added restriction that they should be modified by one of the access modifiers public, private, or protected. The rules associated with these access modifiers are:

• A private class-level variable cannot be accessed outside the class in which it is declared.
• A public class-level variable can be referenced and, hence, modified by any other class.
• A protected class-level variable can only be accessed by subclasses of the class in which it is declared or by other classes that belong to the same package.

When a class, instance variable, or method is defined, you can declare it public, protected, or private. Or you can leave its access unspecified, in which case Java’s default accessibility will apply.

Java determines accessibility in a top-down manner. Instance variables and methods are contained in classes, which are contained in packages. To determine whether a instance variable or method is accessible, Java starts by determining whether its containing package is accessible, and then whether its containing class is accessible. Access to classes, instance variables, and methods is defined according to the rules shown in Table 2.2.

[2pt] Element	Modifier	Rule
[-4pt]
[2pt] Class	public	Accessible if its package is accessible.
	by default	Accessible only within its package.
[-4pt]
[2pt] Instance variable	public	Accessible to all other objects.
or	protected	Accessible to its subclasses and to
instance method		other classes in its package.
	private	Accessible only within the class.
	by default	Accessible only within the package.
[-4pt]

Recall the distinction we made in Chapter 0 between class variables and instance variables. A class variable is associated with the class itself, whereas an instance variable is associated with each of the class’s instances. In other words, each object contains its own copy of the class’s instance variables, but only the class itself contains the single copy of a class variable. To designate a variable as a class variable it must be declared static.

The Riddle class that we considered earlier has the following two examples of valid declarations of instance variables:

private String question;
private String answer;

Class Level Variables for OneRowNim

Let’s now consider how to declare the class level variables for the OneRowNim class. The UML class diagram for OneRowNim in Figure 2.16 contains all the information we need. The variables nSticks and player will store data for playing one game of One Row Nim, so they should clearly be private instance variables. They both will store integer values, so they should be declared as variables of type int. Because we wish to start a game of One Row Nim using 7 sticks with player one making the first move, we will assign 7 as the initial value for nSticks and 1 as the initial value for player. If we add the declarations for our instance variable declarations to the class header for the OneRowNimclass, we get the following:

public class OneRowNim
{
  private int nSticks = 7;
  private int player = 1;

  //Method definitions go here
} // OneRowNim

To summarize, despite its apparent simplicity, a class level variable declaration actually accomplishes five tasks:

Sets aside a portion of the object’s memory that can be used to store a certain type of data.

Specifies the type of data that can be stored in that location.

Associates an identifier (or name) with that location.

Determines which objects have access to the variable’s name.

Assigns an initial value to the location.

OneRowNim’s Methods

Designing and defining methods is a form of abstraction. By defining a certain sequence of actions as a method, you encapsulate those actions under a single name that can be invoked whenever needed. Instead of having to list the entire sequence again each time you want it performed, you simply call it by name. As you recall from Chapter 1, a method definition consists of two parts, the method header and the method body. The method header declares the name of the method and other general information about the method. The method body contains the executable statements that the method performs.

public void methodName()  // Method header
{                  // Beginning of method body
}                  // End of method body

The Method Header

The method header follows a general format that consists of one or more MethodModifiers, the method’s ResultType, the MethodName, and the method’s FormalParameterList, which is enclosed in parentheses. The following table illustrates the method header form, and includes several examples of method headers that we have already encountered. The method body follows the method header.

llll
MethodModifiers\(_{opt}\) & ResultType & MethodName & (FormalParameterList)

public static & void & main & (String argv[]) & void & paint & (Graphics g) & & Riddle & (String q, String a) & String & getQuestion & () & String & getAnswer & ()

The rules on method access are the same as the rules on instance variable access: private methods are accessible only within the class itself, protected methods are accessible only to subclasses of the class in which the method is defined and to other classes in the same package, and public methods are accessible to all other classes.

Recall the distinction from Chapter 0 between instance methods and class methods. Methods declared at the class level are assumed to be instance methods unless they are also declared static. The static modifier is used to declare that a class method or variable is associated with the class itself, rather than with its instances. Just as for static variables, methods that are declared static are associated with the class and are therefore called class methods. As its name implies, an instance method can only be used in association with an object (or instance) of a class. Most of the class-level methods we declare will be instance methods. Class methods are used only rarely in Java and mainly in situations where it is necessary to perform some kind calculation before objects of the class are created. We will see examples of class methods when we discuss the Math class, which has such methods as sqrt(N) to calculate the square root of N.

All four of the methods in the OneRowNim class are instance methods (Fig. 2.19). They all perform actions

public class OneRowNim 
{ private int nSticks = 7; // Start with 7 sticks.
  private int player = 1;  // Player 1 plays first.

  public void takeOne(){ } // Method bodies need
  public void takeTwo(){ } //  to be defined.
  public void takeThree(){ }
  public void report(){ }
} //OneRowNim class

associated with a particular instance of OneRowNim. That is, they are all used to manage a particular One Row Nimgame. Moreover, all four methods should be declared public, because they are designed for communicating with other objects rather than for performing internal calculations. Three of the methods are described as changing the values of the instance variables nSticks and player and the fourth, report(), writes information to the console. All four methods will receive no data when being called and will not return any values. Thus they should all have void as a return type and should all have empty parameter lists.

Given these design decisions, we now can add method headers to our class definition of OneRowNim, in Figure [fig-ornmheaders]. The figure displays the class header, instance variable declarations, and method headers.

The Method Body

The body of a method definition is a block of Java statements enclosed by braces, , which are executed in sequence when the method is called. The description of the action required of the takeOne() method is typical of many methods that change the state of an object. The body of the takeOne() method should use a series of assignment statements to reduce the value stored in nSticks by one and change the value in player from 2 to 1 or from 1 to 2. The first change is accomplished in a straightforward way by the assignment:

nSticks = nSticks - 1;

This statement says subtract 1 from the value stored in nSticks and assign the new value back to nSticks.

Deciding how to change the value in player is more difficult because we do not know whether its current value is 1 or 2. If its current value is 1, its new value should be 2; if its current value is 2, its new value should be 1. Notice, however, that in both cases the current value plus the desired new value are equal to 3. Therefore, the new value of player is equal to 3 minus its current value. Writing this as an assignment we have:

player = 3 - player;

One can easily verify that this clever assignment assigns 2 to player if its current value is 1 and assigns 1 to it if its current value is 2. In effect, this assignment will toggle the value off player between 1 and 2 each time it is executed. In the next chapter we will introduce the if-else control structure that would allow us to accomplish this same toggling action in a more straightforward manner. The complete definition of takeOne() method becomes:

public void takeOne()
{
   nSticks = nSticks - 1;  // Take one stick
   player = 3 - player;    // Change to other player
}

The takeTwo() and takeThree() methods are completely analogous to the takeOne() method with the only difference being the amount subtracted from nSticks.

The body of the report() method must merely print the current values of the instance variables to the console window with System.out.println(). To be understandable to someone using a OneRowNim object, the values should be clearly labeled. Thus the body of report() could contain:

System.out.println("Number of sticks left: " + nSticks);
System.out.println("Next turn by player " + player);

This completes the method bodies of the OneRowNim class. The completed class definition is shown in Figure [fig-orndef].

public class OneRowNim 
{ private int nSticks = 7; // Start with 7 sticks.
  private int player = 1;  //Player 1 plays first.

  public void takeOne()
  { nSticks = nSticks - 1;
    player = 3 - player;
  } // takeOne()

  public void takeTwo()
  { nSticks = nSticks - 2;
    player = 3 - player;
  } // takeTwo()

  public void takeThree()
  { nSticks = nSticks - 3;
    player = 3 - player;
  }  // takeThree()

  public void report()
  { System.out.println("Number of sticks left: " + nSticks);
    System.out.println("Next turn by player " + player);
  }   // report()
} // OneRowNim1 class

We will discuss alternative methods for this class in the next chapter. In Chapter 4, we will develop several One Row Nim user interface classes that will facilitate a user indicating certain moves to make.

Testing the OneRowNim Class

Recall our define, create, and use mantra from Section 4.5. Now that we have defined the OneRowNim class, we can test whether it works correctly by creating OneRowNim objects and using them to perform the actions associated with the game. At this point, we can test OneRowNim by defining a main() method. Following the design we used in the riddle example, we will locate the main() method in separate, user interface class, named OneRowNimTester.

The body of main() should declare a variable of type OneRowNim and create an object for it to refer to. The variable can have any name, but a name like game would be consistent with it recording moves in a single game. To test the OneRowNim class, we should make a typical series of moves. For example, three moves taking 3, 3, and 1 sticks respectively would be one way that the 7 sticks could be removed. Also, executing the report() method before the first move and after each move should display the current state of the game in the console window so that we can determine whether it is working correctly.

The following pseudocode outlines an appropriate sequence of statements in a main() method:

Declare a variable of type OneRowNim named game.

Instantiate a OneRowNim object to which game refers.

Command game to report.

Command game to remove three sticks.

Command game to report.

Command game to remove three sticks.

Command game to report.

Command game to remove one stick.

Command game to report.

It is now an easy task to convert the steps in the pseudocode outline into Java statements. The resulting main() method is shown with the complete definition of the OneRowNimTester class:

public class OneRowNimTester 
{ public static void main(String args[])
  {   OneRowNim1 game = new OneRowNim();
      game.report();
      game.takeThree();
      game.report();
      game.takeThree();
      game.report();
      game.takeOne();
      game.report();
  } //main()
}

When it is run, OneRowNimTester produces the following output:

    Number of sticks left: 7
    Next turn by player 1
    Number of sticks left: 4
    Next turn by player 2
    Number of sticks left: 1
    Next turn by player 1
    Number of sticks left: 0
    Next turn by player 2

This output indicates that player 1 removed the final stick and so player 2 is the winner of this game.

Add a new declaration to the Riddle class for a private String instance variable named hint. Assign the variable an initial value of "This riddle is too easy for a hint".

Write a header for a new method definition for Riddle named getHint(). Assume that this method requires no parameters and that it simply returns the String value stored in the hint instance variable. Should this method be declared public or private?

Write a header for the definition of a new public method for Riddle named setHint() which sets the value of the hintinstance variable to whatever String value it receives as a parameter. What should the result type be for this method?

Create a partial definition of a Student class. Create instance variables for the first name, last name, and an integer student identification number. Write the headers for three methods. One method uses three parameters to set values for the three instance variables. One method returns the student identification number. The last method returns a Stringcontaining the student’s first name and last name. Write only the headers for these methods.

Flow of Control: Method Call and Return

A program’s flow of control is the order in which its statements are executed. In an object-oriented program, control passes from one object to another during the program’s execution. It’s important to have a clear understanding of this process.

In order to understand a Java program, it is necessary to understand the method call and return mechanism. We will encounter it repeatedly. A method call causes a program to transfer control to a statement located in another method. Figure [fig-methodcall] shows the method call and return structure.

In this example, we have two methods. We make no assumptions about where these methods are in relation to each other. They could be defined in the same class or in different classes. The method1() method executes sequentially until it calls method2(). This transfers control to the first statement in method2(). Execution continues sequentially through the statements in method2() until the return statement is executed.

Recall that if a void method does not contain a return statement, then control will automatically return to the calling statement after the invoked method executes its last statement.

Tracing the OneRowNim Program

To help us understand the flow of control in OneRowNim, we will perform a trace of its execution. Figure [fig-trace]shows all of the Java code involved in the program. In order to simplify our trace, we have moved the main() method from OneRowNimTester to the OneRowNim class. This does not affect the program’s order of execution in any way. But keep in mind that the code in the main() method could just as well appear

-5pc

  public class OneRowNim 
2 {  private int nSticks = 7; // Start with 7 sticks.
3    private int player = 1;  //Player 1 plays first.

      public void takeOne()
20    {  nSticks = nSticks - 1;
21       player = 3 - player;  
      } // takeOne()
      public void takeTwo()
      {  nSticks = nSticks - 2;
         player = 3 - player; 
      } // takeTwo()

      public void takeThree()
8,14  {  nSticks = nSticks - 3;
9,15     player = 3 - player; 
      }  // takeThree()
      public void report()
5,11,17,23 { System.out.println("Number of sticks left: " + nSticks);
6,12,18,24   System.out.println("Next turn by player " + player);
      }   // report()

      public static void main(String args[])
1     {  OneRowNim1 game = new OneRowNim1();
4        game.report();
7        game.takeThree();
10       game.report();
13       game.takeThree();
16       game.report();
19       game.takeOne();
22       game.report();
23     } //main()
   } //OneRowNim1 class

in the OneRowNimTester class. The listing in Figure [fig-trace] also adds line numbers to the program to show the order in which its statements are executed.

Execution of the OneRowNim program begins with the first statement in the main() method, labeled with line number 1. This statement declares a variable of type OneRowNim named game and calls a constructor OneRowNim() to create and initialize it. The constructor, which in this case is a default constructor, causes control to shift to the declaration of the instance variables nSticks and player in statements 2 and 3, and assigns them initial values of 7 and 1 respectively. Control then shifts back to the second statement in main(), which has the label 4. At this point, game refers to an instance of the OneRowNim class with an initial state shown in Figure 2.23. Executing statement 4 causes control to shift to the report() method where statements 5 and 6 use System.out.println() to write the following statements to the console.

    Number of sticks left: 7
    Next turn by player 1

Control shifts back to statement 7 in the main() method, which calls the takeThree() method, sending control to the first statement of that method. Executing statement 8 causes \(3\) to be subtracted from the int value stored in the instance variable nSticks of game, leaving the value of \(4\). Executing statement 9 subtracts the value stored in the playervariable, which is \(1\), from \(3\) and assigns the result (the value \(2\)) back to player. The state of the object game, at this point, is shown in Figure 2.24. Tracing the remainder of the program follows in a similar manner. Notice that the main() method calls game.report() four different times so that the two statements in the report() method are both executed on four different occasions. Note also that there is no call of game.takeTwo() in main(). As a result, the two statements in that method are never executed.

Object-Oriented Design: Basic Principles

We complete our discussion of the design and this first implementation of the OneRowNim class with a brief review of some of the object-oriented design principles that were employed in this example.

Encapsulation. The OneRowNim class was designed to encapsulate a certain state and a certain set of actions. It was designed to simulate playing the One Row Nim game. In addition, OneRowNim’s methods were designed to encapsulate the actions that make up their particular tasks.

Information Hiding. OneRowNim’s instance variables, nSticks and player are declared private so other objects can only change the values of these variables with the public methods of a OneRowNim instance. The bodies of the public methods are also hidden from users of OneRowNim instances. An instance and its methods can be used without any knowledge of method definitions.

Clearly Designed Interface. OneRowNim’s interface is defined in terms of the public methods. These methods constrain the way users can interact with OneRowNim objects and ensures that OneRowNim instances remain in a valid state. Those are the main purposes of a good interface.

Generality and Extensibility. There is little in our design of that limits its use and its extensibility. Moreover, as we will see later, we can create several different kinds of user interfaces which interact with OneRowNim objects.

The OneRowNim class has some obvious shortcomings that are a result of our decision to limit methods to those without parameters or return values. These shortcomings include:

A OneRowNim object cannot communicate to another object the number of remaining sticks, which player makes the next turn, or whether the game is over. It can only communicate by writing a report to the console window.

The takeOne(), takeTwo() and takeThree() methods all have similar definitions. It would be a better design if a single method could take away a specified number of sticks.

There is no way to play a OneRowNim game starting with a different number of sticks than 7. It would be nice to have a way of playing a game that starts with any number of sticks.

In order to for a user to play a OneRowNim game, a user interface class would need to be developed that would allow the user to receive information about the state of the game and to input moves to make.

As we study other features of Java in the next two chapters, we will modify the OneRowNim class to address these identified shortcomings.