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.

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.

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

     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.

    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.

     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.)

     1 while not b.board_full() and not b.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 in Example 12-5 is for the board_full method. This method determines if the board is full, meaning that no more pieces may be placed.

     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.

     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.

     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 and first_symbol != EMPTY_POS
     8 				return first_symbol
     9 			end
    10 		end
    11 	end
    12 	return
    13 end

• 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.

     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 and first_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.

     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 and first_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 and first_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.

     1 def ask_player_for_move(current_player)
     2 	played = false
     3 	while not played
     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 played flag 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.

     1 def validate_position(row, col)
     2 	if row <= @board.size and col <= @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.

    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.

    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.

     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.