Section 2.5. Case Study: Simulating a Two-Person Game

[Page 78] 2.5. 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 the 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. On each turn a player must remove one, two, or three sticks from the row. The player who removes the last stick from the row loses. The game can be played with any number of sticks, but starting with 21 sticks is quite common. This game is sometimes called "Nim," but there is a similar game involving multiple rows of sticks that is more frequently given that name. Thus we will refer to the game as "One-Row Nim." 2.5.1. 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 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 the 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 seven sticks rather than 21, to simplify discussion of the program. [Page 79] What data do we need? 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 1 and player 2 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 1 has the first turn. The values of these two variables for a particular OneRowNim object at a particular time describe the object's state. An object's state at the beginning of a game is a 7 stored in nSticks and a 1 stored in player. After player 1 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 the human players and 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 these actions. Each of these methods will be responsible for reducing the value of nSticks as well as for changing the value of player. What methods do we need? We should also have a method that gives the information 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 that an object's instance variablesOneRowNim's instance variablesare to be kept hidden from other objects, and so we have designated them as private (-). Figure 2.16. A UML class diagram for OneRowNim. 2.5.2. 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. [Page 80] 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 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 a relationship to any other Java class, its header can omit the extends clause, and therefore 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 Figure 2.17. By default, OneRowNim is a subclass of Object. 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. Variables and methods In general, a class definition will take the form shown in Figure 2.18. Although Java does not impose any particular order on variable and method declarations, in this book we will 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 defined in the Riddle(String q, String a) constructor (Fig. 2.12). As we will see better in Chapter 3, Java handles each type of variable differently. [Page 81] Figure 2.18. A template for constructing a Java class definition. (This item is displayed on page 80 in the print version) public class ClassName { // Instance and class variables VariableDeclaration1 VariableDeclaration2 ... // Instance and class methods MethodDefinition1 MethodDefinition2 ... } // End of class Class-level vs. local variables A declaration for a variable at class level must follow the rules for declaring variables that were described in Section 1.4.8 with the added restriction that they should be modified by an access modifier, either 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 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 an 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. Table 2.2. Java's accessibility rules. Element Modifier Rule Class public by default Accessible if its package is accessible. Accessible only within its package. Instance variable or instance method public protected Accessible to all other objects. Accessible to its subclasses and to other classes in its package.   private by default Accessible only within the class. Accessible only within the package. 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 seven sticks, with player 1 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 OneRowNim class, we get the following: [Page 82] public class OneRowNim { private int nSticks = 7; private int player = 1; // Method definitions go here } // OneRowNim class To summarize, despite its apparent simplicity, a class-level variable declaration actually accomplishes five tasks: 1. Sets aside a portion of the object's memory that can be used to store a certain type of data. 2. Specifies the type of data that can be stored in that location. 3. Associates an identifier (or name) with that location. 4. Determines which objects have access to the variable's name. 5. 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 will 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. Table 2.3 illustrates the method header form, and includes several examples of method headers that we have already encountered. The method body follows the method header. [Page 83] Table 2.3. Method headers. MethodModifiersopt ResultType MethodName (FormalParameterList) public static void main (String argv[]) public void paint (Graphics g) public   Riddle (String q, String a) public String getQuestion () public 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. Effective Design: Public versus Private Methods If a method is used to communicate with an object, or if it passes information to or from an object, it should be declared public. If a method is intended to be used solely for internal operations within the object, it should be declared private. These methods are sometimes called utility methods or helper methods. Recall from Chapter 0 the distinction 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 like 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 a calculation of some kind 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. Java Programming Tip: Class versus Instance Methods If a method is designed to be used by an object, it is referred to as an instance method. No modifier is needed to designate an instance method. Class methods, which are used infrequently compared to instance methods, must be declared static. All four of the methods in the OneRowNim class are instance methods (Fig. 2.19). They all perform actions associated with a particular instance of OneRowNim. That is, they are all used to manage a particular One-Row Nim game. 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. [Page 84] Given these design decisions, we now can add method headers to our class definition of OneRowNim, in Figure 2.19. The figure displays the class header, instance variable declarations, and method headers. Figure 2.19. The Instance variables and method headers for the OneRowNim class. 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 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 1 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; Designing a method is an application of the encapsulation principle. 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. Note, however, that in both cases the current value plus the desired new value is equal to 3. Therefore, the new value of player are 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, which will allow us to accomplish the 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 } [Page 85] 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 2.20. 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 by indicating certain moves to make. Figure 2.20. The OneRowNim class definition. 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 2.5.3. Testing the OneRowNim Class Recall our define, create, and use mantra from Section 2.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 a 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 the function of recording moves in a single game. To test the OneRowNim class, we should make a typical series of moves. For example, three moves taking three, three, and one sticks respectively would be one way that the seven 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. [Page 86] The following pseudocode outlines an appropriate sequence of statements in a main() method: 1. Declare a variable of type OneRowNim named game. 2. Instantiate a OneRowNim object to which game refers. 3. Command game to report. 4. Command game to remove three sticks. 5. Command game to report. 6. Command game to remove three sticks. 7. Command game to report. 8. Command game to remove one stick. 9. 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() } // OneRowNimTester class 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 the game. [Page 87] Self-Study Exercises Exercise 2.4 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". Exercise 2.5 Write a header for a new method definition for Riddle named getHint(). Assume that this method requires no parameters and simply returns the String value stored in the hint instance variable. Should this method be declared public or private? Exercise 2.6 Write a header for the definition of a new public method for Riddle named setHint() which sets the value of the hint instance variable to whatever String value it receives as a parameter. What should the result type be for this method? Exercise 2.7 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 String containing the student's first name and last name. Write only the headers for these methods. 2.5.4. 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 is 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 2.21 shows the method call and return structure. Figure 2.21. The method call and return control structure. It is important to realize that method1() and method2() may be contained in different classes. 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. Java Language Rule: Return Statement The return statement causes a method to return control to the calling statementthat is, to the statement that called the method in the first place. [Page 88] 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. Default returns 2.5.5. Tracing the OneRowNim Program To help us understand the flow of control in OneRowNim, we will perform a trace of its execution. Figure 2.22 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 in the OneRowNimTester class. The listing in Figure 2.22 also adds line numbers to the program to show the order in which its statements are executed. Figure 2.22. A trace of the OneRowNim program. 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 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 the 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. [Page 89] Figure 2.23. The initial state of game, a OneRowNim object. 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 player variable, 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. Note 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. Figure 2.24. The state of game after line 9 is executed. 2.5.6. 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 that 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. [Page 90] 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 ensure that OneRowNim instances remain in a valid state. These are the main purposes of a good interface. Generality and Extensibility. There is little in our design of OneRowNim that limits its use and extensibility. Moreover, as we will see later, we can create several different kinds of user interfaces to interact with OneRowNim objects. The OneRowNim class has some obvious shortcomings that are a result of our decision to limit the design to methods 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. Alan Kay and the Smalltalk Language Although Simula was the first programming language to use the concept of an object, Smalltalk was the first pure object-oriented language. Smalltalk was developed by Alan Kay in the late 1960s. Kay is an innovative thinker who has had a hand in the development of several advances, including windowing interfaces, laser printing, and the client/server model, all of which are commonplace today. One of the abiding themes throughout Kay's career has been the idea that computers should be easy enough for kids to use. In the late 1960s, while still in graduate school, Kay designed a computer model that consisted of a notebook-sized portable computer with a keyboard, screen, mouse, and high-quality graphics interface. He had become convinced that graphics and icons were a far better way to communicate with a computer than the command-line interfaces that were prevalent at the time. In the early 1970s Kay went to work at the Xerox Palo Alto Research Center (PARC), where he developed a prototype of his system known as the Dynabook. Smalltalk was the computer language Kay developed for this project. Smalltalk was designed along a biological model, in which individual entities, or "objects," communicate with each other by passing messages back and forth. Another goal of Smalltalk was to enable children to invent their own concepts and build programs with themthus, the name Smalltalk. Xerox's management was unable to see the potential of Kay's innovations. However, during a visit to Xerox in 1979, Steve Jobs, the founder of Apple Computer, was so impressed by Kay's work that he made it the inspiration of the Macintosh computer, which was first released in 1984. Kay left Xerox in 1983 and became an Apple Fellow in 1984. In addition to working for Apple, Kay spent considerable time teaching kids how to use computers at his Open School in West Hollywood. In 1996 Kay became a Fellow (an "Imagineer") at Walt Disney Imagineering's Research and Development Organization, where he continues to explore innovative ways to enhance the educational and entertainment value of computers. [Page 91] There is no way to play a OneRowNim game starting with a number of sticks other than seven. It would be nice to have a way of playing a game that starts with any number of sticks. In order 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. As we study other features of Java in the next two chapters, we will modify the OneRowNim class to address these identified shortcomings.