Computer Science Programming Basics in Ruby (2013)

Chapter 12. Putting It All Together: Tic-Tac-Toe

IN THIS CHAPTER

§ Approaching the problem

§ Implementing tic-tac-toe

12.1 Introduction

It is finally time to put everything you know all together. You will no longer use programming elements in isolation; writing programs rarely involves using only if statements, loops, or objects. Typically, all programming elements are interleaved. For clarity, we described these elements in isolation; now we integrate them. The challenge is to create a task that requires integration that is not too simple to be uninteresting but not so complex that it requires 500 pages of text.

After much thought, we decided to develop the simple, well-known game of tic-tac-toe. The idea is to initially develop a program that facilitates two people playing against each other, and then to enhance the program so that a person can play against a computer. As correct play guarantees at least a tie, we provide sufficient algorithm detail to guarantee that the computer will never lose. We provide sufficient code segments to illustrate the development of the program but leave it to you to complete it. Good luck; you are ready for it.

Using what you have learned so far, it is time to put all of your knowledge together into one fun program. The game of tic-tac-toe is a classic, and the rules can be easily looked up if you are not familiar with them. First you will learn how to build a Ruby program that will allow two users to play the game. After this program has been established, we will extend the program to allow a user to play against the computer.

Our tic-tac-toe game will not have a nice user interface. User interfaces are a more advanced topic that is beyond the scope of this book. We want you to focus on problem solving in this course and not on figuring out how to create a pretty user interface.

Our board will be drawn with simple X’s and O’s and will be invoked from the command line of your operating system.

We will first talk about how to approach the problem, and then how to implement the solution in an incremental fashion.

GEM OF WISDOM

If you can write a tic-tac-toe game in Ruby that works, most people would agree that you know Ruby and that you have a clue about programming. It is not the easiest thing to do. If you grasp everything in this chapter, then you are ready to move beyond just an introduction to computer science.

12.2 Programming Approach

First we need to break the problem into key steps. Many programmers are tempted to run to the computer and start writing code immediately and then debug their code. This is not recommended.

It is strongly suggested that you step away from the computer, grab paper and pencil, and write out the key algorithms that will be needed to solve the problem. As part of this effort, you should be able to describe the key objects and methods that will be involved.

The key steps of a tic-tac-toe game are rather straightforward. Until the board is full and there is no winner, do the following:

1. Draw the current board.

2. Ask the player for a move.

3. Make sure the move is valid (e.g., you can’t move to a square that is already taken).

4. Store the current move.

You should write out the key objects and the key methods and then implement them gradually.

12.3 Tic-Tac-Toe

When two players initiate a game of tic-tac-toe, what is the first thing they do? They draw a board. Therefore, we will worry about the board first. A key object we will need is a Board object that stores the tic-tac-toe board. Think about the properties of such a board. A board is typically a large square made up of 3  × 3 smaller squares. At the start of the game all the little squares will be empty, but later they will be filled in with X’s and O’s as the game progresses. Therefore, we will need a 3  × 3 array that is initially empty and can be filled in later while the game is being played. Using objects, we will be able to design the board construction.

GEM OF WISDOM

In Example 12-1, we use a shorthand way of declaring an array and its members. Array.new(5) { 3 } creates an array of five elements, with each value initialized to 3. Lines 8–10 declare an array (line 8), with each element being an array initialized to EMPTY_POS (line 9).

Using our knowledge of arrays and objects, we are able to set up the board constructor as shown in Example 12-1.

Example 12-1. Initial board and constructor

1 class Board

2

3 BOARD_MAX_INDEX = 2

4 EMPTY_POS = ' '

5

6 def initialize(current_player)

7 @current_player = current_player

8 @board = Array.new(BOARD_MAX_INDEX + 1) {

9 Array.new(BOARD_MAX_INDEX + 1) { EMPTY_POS }

10 }

11 end

12 end

§ Line 3 defines the largest index (remember, array indices start at 0).

§ Line 4 defines what is considered an empty position, or a position not occupied by either an X or an O.

§ Lines 6–11 define the constructor for our board.

§ Line 7 assigns an instance variable that represents the current player.

§ Lines 8–10 create the board instance variable, a 3  × 3 array.

The main program (tictactoe.rb) will use the board class. The start of the main program is given in Example 12-2.

Example 12-2. Beginning of tictactoe.rb

1 require_relative 'board.rb'

2

3 puts "Starting tic-tac-toe..."

4 players = ['X', 'O']

5 current_player = players[rand(2)]

6 b = Board.new(current_player)

7 b.display()

8 puts

§ Lines 4 and 5 randomly pick an initial player (either X or O).

§ Line 6 creates an instance of the Board class and assigns it to b.

§ Lines 7 and 8 display the initial blank board and output a fresh blank line for readability.

The display method (which is part of board.rb) is given in Example 12-3.

Example 12-3. Display method for Board class

1 def display

2 puts "+- - - - - -+"

3 for row in 0..BOARD_MAX_INDEX

4 # print has to be used when we don't want to output a line break

5 print "| "

6 for col in 0..BOARD_MAX_INDEX

7 s = @board[row][col]

8 if s == EMPTY_POS

9 print col + (row * 3) + 1

10 else

11 print s

12 end

13 print " | "

14 end

15 puts "\n+- - - - - -+"

16 end

17 end

§ Line 2 prints a row of dashes (the top of the board).

§ Line 3 starts an outer loop that runs through each row.

§ Line 6 starts an inner loop that traverses each column.

§ Line 7 assigns the current cell to the variable s.

§ Lines 8–12 print the number of the cell if it’s currently unoccupied or the current occupant if the cell is occupied.

Note the difference between print and puts: print simply writes the characters passed to it without writing an end of line upon completion. Thus, if one wishes to continue writing to a given line, print would be used. Remember, however, that if using print and a new line is desired, the newline character (\n) must be entered, as shown in line 15. This is in contrast to puts, which automatically inserts the newline character every time.

Returning to our main program, the key loop that runs the game will be implemented. The code is presented in Example 12-4. (The code begins at line 1; however, this is a continuation of tictactoe.rb.)

Example 12-4. Continuation of tictactoe.rb

1 while notb.board_full() and notb.winner()

2 b.ask_player_for_move(current_player)

3 current_player = b.get_next_turn()

4 b.display()

5 puts

6 end

7

8 if b.winner()

9 puts "Player " + b.get_next_turn() + " wins."

10 else

11 puts "Tie Game."

12 end

13 puts "Game Over"

§ Line 1 starts a loop that continues as long as the board is not full and there is no winner.

§ Line 2 prompts the current player for a move.

§ Line 3 gets the next player.

§ Lines 4 and 5 display the current board.

§ Lines 8–13 print the winner’s name if there was a winner, or “Tie Game” if the game ended in a tie.

The loop ends when there is a winner or there is a full board detected. At this point, you can see we need to discuss the board_full method, the winner method, and the get_next_turn method. The code presented inExample 12-5 is for the board_full method. This method determines if the board is full, meaning that no more pieces may be placed.

Example 12-5. board_full method

1 def board_full

2 for row in 0..BOARD_MAX_INDEX

3 for col in 0..BOARD_MAX_INDEX

4 if @board[row][col] == EMPTY_POS

5 return false

6 end

7 end

8 end

9 # Since we found no open positions, the board is full

10 return true

11 end

§ Line 4 checks each cell to see if it is unoccupied. If at least one cell is unoccupied, the board is not full and the game must continue.

§ Line 10 returns true in the event that none of the cells are open for possible capture.

The winner method is more complex. Essentially, we must check every row, every column, and every diagonal for a winner. The method is presented in Example 12-6.

Example 12-6. Winner method

1 def winner

2 winner = winner_rows()

3 if winner

4 return winner

5 end

6 winner = winner_cols()

7 if winner

8 return winner

9 end

10 winner = winner_diagonals()

11 if winner

12 return winner

13 end

14 # No winners

15 return

16 end

The winner method uses the helper methods winner_rows, winner_cols, and winner_diagonals, which return the player’s symbol if the player won by connecting the rows, columns, or diagonals with her or his pieces, respectively. If winner is set, then we know that the current value of winner is the player who won the game. Otherwise, we return nothing, signifying there is no winner yet.

The methods winner_rows, winner_cols, and winner_diagonals are good examples of class methods, as explained in Chapter 9. They are all fairly straightforward, as they all look for three of the same values with regard to their given task. The method winner_rows is shown in Example 12-7.

Example 12-7. winner_rows method

1 def winner_rows

2 for row_index in 0..BOARD_MAX_INDEX

3 first_symbol = @board[row_index][0]

4 for col_index in 1..BOARD_MAX_INDEX

5 if first_symbol != @board[row_index][col_index]

6 break

7 elsif col_index == BOARD_MAX_INDEX andfirst_symbol != EMPTY_POS

8 return first_symbol

9 end

10 end

11 end

12 return

13 end

GEM OF WISDOM

Aside from being able to return values, the return keyword immediately stops execution of the current method and returns to the one from which it was called. This is used heavily in the winner method. If the winner is found in the rows, the columns and diagonals are not searched. Likewise, if the winner is found in the columns, the diagonals are not searched.

§ Line 2 begins an outer loop to look for a winner across a row. For each row, all the columns are checked. The variable first_symbol contains the symbol that must match.

§ Line 3 initializes first_symbol for row 0.

§ Lines 4–10 provide an inner loop that looks at all elements in the given column. If a cell does not match the first_symbol value, then it is not a winning combination.

For example, if the first_symbol value was initially an O and now we encounter an X in the same column, then this is not a winning combination. If we reach the end of the columns, we have a winner, and we return the winner as its name is in the first_symbol column.

§ Line 7 contains a final check to make sure we have not found three empty positions in a column. If we do not return a winner, then we simply return on line 12 (this is essentially returning a nil or false value) to the caller of this method.

The next method, presented in Example 12-8, is very similar in that it looks for a winning column. This time, a given column is checked, and we travel down the column checking to see if we have all matching symbols.

Example 12-8. winner_cols method

1 def winner_cols

2 for col_index in 0..BOARD_MAX_INDEX

3 first_symbol = @board[0][col_index]

4 for row_index in 1..BOARD_MAX_INDEX

5 if first_symbol != @board[row_index][col_index]

6 break

7 elsif row_index == BOARD_MAX_INDEX andfirst_symbol != EMPTY_POS

8 return first_symbol

9 end

10 end

11 end

12 return

13 end

Finally, we look for a win across a diagonal. This is inherently more difficult because it requires a backward traversal of the columns. This is done with the winner_diagonals method shown in Example 12-9.

Example 12-9. winner_diagonals method

1 def winner_diagonals

2 first_symbol = @board[0][0]

3 for index in 1..BOARD_MAX_INDEX

4 if first_symbol != @board[index][index]

5 break

6 elsif index == BOARD_MAX_INDEX andfirst_symbol != EMPTY_POS

7 return first_symbol

8 end

9 end

10 first_symbol = @board[0][BOARD_MAX_INDEX]

11 row_index = 0

12 col_index = BOARD_MAX_INDEX

13 while row_index < BOARD_MAX_INDEX

14 row_index = row_index + 1

15 col_index = col_index - 1

16 if first_symbol != @board[row_index][col_index]

17 break

18 elsif row_index == BOARD_MAX_INDEX andfirst_symbol != EMPTY_POS

19 return first_symbol

20 end

21 end

22 return

23 end

§ Line 2 initializes our search with the upper-lefthand corner of the board.

§ Lines 3–9 traverse the diagonal from the top left to the bottom right, continuing as long as there is a match.

§ Line 10 sets the initial value to the top right.

§ Lines 11–20 check the diagonal from the top right to the bottom left. If no matches are found, we return nothing (line 22).

The only methods we have not yet described are the ask_player_for_move method and the validate_position method, which simply prompt the user for a move and ensures that the move is allowed. The ask_player_for_move method is presented in Example 12-10.

Example 12-10. ask_player_for_move method

1 def ask_player_for_move(current_player)

2 played = false

3 while notplayed

4 puts "Player " + current_player + ": Where would you like to play?"

5 move = gets.to_i - 1

6 col = move % @board.size

7 row = (move - col) / @board.size

8 if validate_position(row, col)

9 @board[row][col] = current_player

10 played = true

11 end

12 end

13 end

§ Line 3 starts a loop that keeps processing until a valid move is obtained. The flag played is initially set to false.

§ Line 4 asks the user for her or his move.

§ Line 5 obtains the user’s response with a call to gets, which obtains a string and then converts it to an integer.

§ Line 6 converts the number 1–9 into column number 0–2, and line 7 converts it into a row number. These conversions stem from the equation that took each cell of the array and assigned a cell number. Convince yourself that lines 6 and 7 are correct.

§ Line 8 calls another internal method, validate_position, which is a method that makes sure the user chooses a spot on the board and a spot that is not already taken. If a valid position is obtained, then line 10 sets the playedflag to be true, and the loop will end when line 3 is encountered. For an invalid move, the played flag is not set to true, so the loop will continue again.

The validate_position method is given in Example 12-11.

Example 12-11. validate_position method

1 def validate_position(row, col)

2 if row <= @board.size andcol <= @board.size

3 if @board[row][col] == EMPTY_POS

4 return true

5 else

6 puts "That position is occupied."

7 end

8 else

9 puts "Invalid position."

10 end

11 return false

12 end

§ Line 2 makes sure the row and column are within the range of the board. We know it’s a three row by three column game, but by using the size variable we could easily expand this to larger board sizes for other games, like Connect Four. In this case the size is three elements, 0, 1, and 2. The size was established earlier, but this will allow us to easily change the size of the board.

§ Line 3 checks to make sure the user has selected a position that was previously empty. If so, true is returned, and we are done.

§ Lines 5–7 handle the case for when a user selects an occupied position.

§ Lines 8–10 handle the case for when a user selects a position off the board.

§ Line 11 returns false, which indicates that an invalid move occurred. Note that line 11 is reached only when an invalid move is attempted.

Finally, we need to discuss the get_next_turn method, and we are done. It is very simple and is shown in Example 12-12.

Example 12-12. get_next_turn_method

1 def get_next_turn

2 if @current_player == 'X'

3 @current_player = 'O'

4 else

5 @current_player = 'X'

6 end

7 return @current_player

8 end

§ Line 2 checks to see if we were using an X, and if so, we change to the O in line 3; otherwise, it was an O, so in line 5 we turn it into an X.

At this point, we have created a working game of tic-tac-toe that you can play against yourself or a friend. The code written for this game encompasses almost all the topics covered in this book. If you understood it all, give yourself a pat on the back. If you are frustrated with this chapter and do not understand all the ideas presented, it is a good idea to go back to previous chapters and play around with the Ruby concepts presented in those chapters.

Don’t get too comfortable if you’ve done well thus far. The next section will add artificial intelligence to our tic-tac-toe game, enabling you to play against the computer.

12.4 Tic-Tac-Toe Revised

Although a player-versus-player version of tic-tac-toe is nice, chances are you will not have a friend who wants to spend time playing computerized tic-tac-toe with you for long. Perhaps it will be more satisfying if you create a version of tic-tac-toe that will play against you. This is what we will do in this section.

First, let’s understand the change we are trying to make. Instead of always having the player input the position on the board to fill, we want the computer to take one of the turns. Therefore, we will make a clearer distinction between the human’s move and the computer’s move. The code in Example 12-13 illustrates this change.

Example 12-13. Revised ask_player_for_move method

1 def ask_player_for_move(current_player)

2 if current_player == COMPUTER_PLAYER

3 computer_move(current_player)

4 else

5 human_move(current_player)

6 end

7 end

The purpose of the ask_player_for_move method is to switch between player input and computer AI (artificial intelligence) based on the current player. If the current player is the computer (line 2), let the computer take its move (line 3); otherwise (line 4), let the user take her or his move (line 5). Make sure to define the constant COMPUTER_PLAYER. It may be set equal to X or O. This would also be a good time to define the constant HUMAN_PLAYER. This should be set equal to O if COMPUTER_PLAYER is equal to X, or X if COMPUTER_PLAYER is equal to O.

If you have been reading carefully, you will have noticed that ask_player_for_move was already defined pages ago, and now we have changed its definition here. Previously, the method prompted either player one or player two for which turn she or he wanted to make, and then took the turn if it was valid. That code was relocated to the method human_move. The code for human_move is identical to our old ask_player_for_move method.

At this point, we have a mechanism for changing between the human’s and the computer’s turn, and we have slightly changed the definition of the human’s turn. From here it should be clear that the next logical step is to define the computer_move method, and it is defined in Example 12-14.

Example 12-14. computer_move method

1 def computer_move(current_player)

2 row = -1

3 col = -1

4 found = "F"

5

6 check_rows(COMPUTER_PLAYER, found)

7 check_cols(COMPUTER_PLAYER, found)

8 check_diagonals(COMPUTER_PLAYER, found)

9

10 check_rows(HUMAN_PLAYER, found)

11 check_cols(HUMAN_PLAYER, found)

12 check_diagonals(HUMAN_PLAYER, found)

13

14 if found == "F"

15 if @board[1][1] == EMPTY_POS

16 row = 1

17 col = 1

18 @board[row][col] = current_player

19 elsif available_corner()

20 pick_corner(current_player)

21 else

22 until validate_position(row, col)

23 row = rand(@board.size)

24 col = rand(@board.size)

25 end

26 @board[row][col] = current_player

27 end

28 end

29 end

If this method looks complicated, don’t worry. First, let’s walk through the code at an algorithmic level. The computer_move method does the following in order, picking the first rule it can successfully complete:

1. Check the rows, columns, and diagonals to see if either the computer can win or the human can win. If such a spot exists, take it to either win the game or prevent the human from winning. Note that we intentionally do not include the code for those methods, as their implementation is straightforward and their details are unnecessary for the purposes of our discussion.

2. If the middle cell is unoccupied, take the middle cell.

3. If there is an available corner, take any of the available corner spots.

4. If none of the prior conditions are true, pick a random cell.

For simplicity, we did not include all the necessary code to guarantee at least a draw for the AI. However, in tic-tac-toe, correct play guarantees at least a draw. To guarantee at least a draw, the computer’s corner selection option should be modified as follows:

If a corner spot is available, then select a corner spot, with the following corner selection preference. If the computer went first, randomly choose among the available corners that are not adjacent to the human’s noncenter spot(s). If the human went first, then check for one exception condition; otherwise, randomly choose among the available corners that are adjacent to the human’s noncenter spot(s). The exception condition is one in which only three squares are occupied, the computer has the center square, and the human has both corners on the same diagonal; in such a case, override the corner selection option and randomly choose a noncorner spot. If none of the aforementioned conditions are met, then choose any available corner.

This description defines a high-level algorithm for the game of tic-tac-toe. You now have all the needed skills to design, develop, and debug all the implementation specifics. Please do so and enjoy playing your computerized opponent.

12.5 Summary

Now that we have walked through a more detailed example, you should be able to implement some fun games in Ruby. Games like blackjack and poker are now all within your grasp.

We have combined the concepts covered in the previous chapters in this example. With the file processing we discussed in Chapter 11, you can even make it so that you can save the state of these games or the current high score to a file. These concepts are common among most programming languages. So, as a programmer, it is much more effective to learn these concepts and how they can be used to solve certain problems than to direct your focus onto learning syntax, which is just the tool that allows us to implement our ideas.

The best way to become more comfortable with these types of problems is to practice doing them. Take your time with the following problems, draw out what the problem requires, and design a solution. Eventually, this process becomes much easier, and you will be able to implement the solution in any language.

12.6 Exercises

1. Give a detailed explanation of the relationship between the board and the tic-tac-toe objects.

2. Design and implement a game of “pick a number.” This is a simple guessing game where you think of a number between 1 and n in your head (don’t let the computer know this number). Tell the computer what n is, and then let the computer guess the number. If the guess is too low, you should let the computer know that the guess was too low; likewise, if the guess was too high you should also let the computer know. The computer can take multiple turns (hint: it should take log n turns), but simply guessing every number between 1 and n is far from an acceptable answer. Implement this program two different ways: procedurally and object-oriented.

3. Design and implement a simplified version of the card game blackjack. The rules are as follows:

a. A standard 52-card deck is used and shuffled well.

b. The cards have the following values: 2 to 10 are the value of the card, jack to king have a value of 10, and ace has a value of 1 or 11.

c. Only you are playing, trying to get the cards to add up to 21 without going over 21. If you go over 21, you lose.

d. Initially you are dealt two cards. If you are dissatisfied with these cards, you can ask for more. It is not a trade; additional cards are added. If you feel like you have enough cards and do not want to bust, you can “stay” and end this round of blackjack.

After the game has ended, the user should be able to play again, if she or he chooses to do so. If so, the game will restart like a brand-new game. Implement this in an OO fashion. If you split the work among your objects properly, you will be able to reuse a significant chunk of code on the next problem.

4. Add scoreboard functionality to Exercise 3. To do this, you need to make a few game modifications. First, you need to ask for the user’s name at the beginning of every game. Next, you need the ability to view the scoreboard during a game; this should be done directly after prompting for a name. If a user’s name already exists on the scoreboard, you will modify that user’s score. Otherwise, the new user will be added to the scoreboard in the proper position. The scoreboard needs to remember scores even after the program is exited (hint: write scores out to a file). If a score surpasses another score, the ordering of scores on the scoreboard needs to change. The highest score should be listed first, the lowest score last. The scoring criteria are defined in Table 12-1.

Table 12-1. Blackjack scoring criteria

5. Being able to read and modify other people’s code is essential to being a successful computer scientist. Modify tictactoe.rb and board.rb to play tic-tac-toe on boards of size 3  × 3, 6  × 6, and 9  × 9 based on the user’s choice. Adjust everything so that the game works as well on 6  × 6 and 9  × 9 boards as it does on 3  × 3 boards.

6. The current AI for the tic-tac-toe game is not perfect. Implement the behavior discussed in this chapter’s summary to guarantee at least a draw, and ensure its correctness.