15110 Fall 2011 [Cortina/von Ronne]

Lab 13 - Tic Tac Toe

You may work on this lab with another student if you wish. If you do, put a comment in the program code that includes both of your names, and both of you should submit the code.

Deliverables:

1. A file tic_tac_toe.rb containing the functions: new_grid, add_mark, display_grid, input_num, play, check_win, check_win_horiz, check_win_vert, check_win_diagonal1, and check_win_diagonal2 as described below.
2. A file drawing.txt
3. A file games.txt

Overview of Tic Tac Toe

In this lab, you will develop a program that allows two players to play Tic Tac Toe. In Tic Tac Toe, two players alternate placing their marks ("X"'s and "O"'s, respectively) in the of a 9 positions of a 3x3 grid. The first player to put three of their marks in a vertical, horizontal, or diagonal line is the winner. If nine marks have been placed without either player getting three marks in a row, the game ends in a tie.

Board Representation

In order to represent the state of play in a game of Tic Tac Toe, we will use a two-dimensional 3x3 array, where each element is nil (if the corresponding position is unoccupied), 0 if the position is occupied by the mark ("X") of the first player ("Player 0"), or 1 if the position is occupied by the mark ("O") of the second player ("Player 1"). For example, the Tic Tac Toe grid shown at right could be represented by the 2d Ruby array:

[[1, nil, 0], 
 [nil, 0, nil], 
 [nil, nil, nil]]

1. Define a function new_grid that creates the data representation for a blank 3x3 Tic Tac Toe grid.
2. Define a function add_mark that takes parameters grid, row, col, player, and which modifies grid to place player's mark at the position specified by row and col as long as that position is unoccupied. If the position was unoccupied, then after modifying the grid, add_mark should return true. Otherwise (i.e., the position was already occupied), add_mark should return false.

Usage:

>> grid = new_grid()
=> [[nil, nil, nil], [nil, nil, nil], [nil, nil, nil]]
>> add_mark(grid,1,2,0)
=> true
>> grid
=> [[nil, nil, nil], [nil, nil, 0], [nil, nil, nil]]
>> add_mark(grid,1,2,1)
=> false
>> grid
=> [[nil, nil, nil], [nil, nil, 0], [nil, nil, nil]]
>> add_mark(grid,2,2,1)
=> true
>> grid
=> [[nil, nil, nil], [nil, nil, 0], [nil, nil, 1]]

Graphical Display of Board State

The RubyLabs Canvas provides three types of graphical objects (Rectangle, Line, and Circle) that are useful for the parts of a Tic Tac Toe game:

Canvas.init(90,90,"Lab13")
Canvas::Rectangle.new(0, 0, 90, 50, :fill => :gray, :width => 0)
Canvas::Line.new(5, 45, 85, 5, :width => 3)
Canvas::Circle.new(75, 35, 10,  :outline => :black, :fill => :gray, :width => 2)

1. In irb, create a 90x90 pixel canvas, and try to draw the Tic Tac Toe grid shown at right using rectangles, lines, and circles. Create a text file drawing.txt that contains the irb commands you used to draw this image (hint: cut & paste them from your terminal window).

2. Define a Ruby function display_grid(grid) that draws a game state to the Canvas. The following algorithm may be used for display_grid:

   1. Create a Rectangle covering the entire 90x90 Canvas and filled with gray.
   2. Draw the horizontal and vertical lines separating the positions in the grid.
   3. For each grid position (rows in 0..2, columns in 0..2), do the following:
      1. Calculate the x, y coordinates of the center of that grid position
      2. If the grid indicates that the position should hold an "X" (i.e., grid[row][col] == 0), then draw an "X" at the correct coordinate.
      3. If the grid indicates that the position should hold an "O", then draw a circle coordinate.

   The following usage should result in the image shown above:

   >> Canvas.init(90,90,"Lab13")
   => true
   >> display_grid([[1,nil,0],[nil,0,nil],[nil,nil,nil]])
   => nil
   

Game Play

With your CA, trace through the execution of the functions play and input_num, given below, for the first few moves of a game as shown here:

>> play()
Player 0: Which row (0-2)? 1
Player 0: Which column (0-2)? 1
Player 1: Which row (0-2)? f
input must be a number between 0 and 2 (inclusive)
Player 1: Which row (0-2)? 3
input must be a number between 0 and 2 (inclusive)
Player 1: Which row (0-2)? 1
Player 1: Which column (0-2)? 1
Grid position (row=1, column=1) is already occupied.
Players 1: Which row (0-2)? 0
Player 1: Which column (0-2)? 0
Player 0: Which row (0-2)? 0
Player 0: Which column (0-2)? 1

def play()
  # draw the inital (empty) game grid
  Canvas.init(90,90,"TicTacToe")

  grid = new_grid()
  display_grid(grid)
  player = 0

  9.times {
    # keep on asking for rows/columns until the user inputs a valid move
    # add a mark to the correct cell
    repeat = true
    while repeat == true do
      row = input_num("Player " + player.to_s + ": Which row (0-2)? ")
      col = input_num("Player " + player.to_s + ": Which column (0-2)? ")

      if add_mark(grid, row, col, player) then
        repeat = false
      else
        puts "Grid position (row=" + row.to_s + ", column=" + col.to_s +
          ") is already occupied."
      end
    end

    # redisplay grid with new mark
    display_grid(grid)

    if check_win(grid) then
      puts "Player " + player.to_s + " won!"
      return
    end

    # alternate between player 0 and player 1
    player = (player + 1) % 2
  }

  # If no-one wins in 9 moves, the game is a tie.
  puts "The game ended in a tie."
end


# get a number between 0 and 2, inclusive
def input_num(prompt)
  num = nil
  while num == nil do
    input = Readline.readline(prompt)

    # Determine whether input is a number by checking if it matches
    # a regular expression.  The ^ says that the regular expression
    # has to be at the beginning of the input. The rest of the regular
    # expression checks to see if the first character is either the 
    # numeral 0, 1, or 2
    is_number = input.match("^(0|1|2)")
    num = input.to_i

    if is_number && num >= 0 && num <= 2 then
      return num
    else
      puts "input must be a number between 0 and 2 (inclusive)"
      num = nil
    end
  end
  return num
end

At this point, if you supply a "stub" definition of check_win, then you should be able to play Tic Tac Toe, except that the computer will not stop when a player wins.

>> def check_win(grid)
>>   return false
>> end
=> nil
>> play()
Player 0: Which row (0-2)? 0
Player 0: Which column (0-2)? 0
Player 1: Which row (0-2)? 0
Player 1: Which column (0-2)? 2
Player 0: Which row (0-2)? 2
Player 0: Which column (0-2)? 2
Player 1: Which row (0-2)? 1
Player 1: Which column (0-2)? 1
Player 0: Which row (0-2)? 2
Player 0: Which column (0-2)? 0
Player 1: Which row (0-2)? 1
Player 1: Which column (0-2)? 0
Player 0: Which row (0-2)? 2
Player 0: Which column (0-2)? 1
Player 1: Which row (0-2)? 1
Player 1: Which column (0-2)? 2
Player 0: Which row (0-2)? 0
Player 0: Which column (0-2)? 1
The game ended in a tie.
=> nil

Determining a Winner

1. For each row, return true if the three positions on that row are occupied by marks belonging to the same player.

2. For each column, return true if the three positions on that column are occupied by marks belonging to the same player.

3. Return true if the three positions on the diagonal line form the upper-left corner to the lower-right corner are all occupied by marks belonging to the same player.

4. Return true if the three positions on the diagonal line form the upper-right corner to the lower-left corner are all occupied by marks belonging to the same player.

5. Return false.

A helper function check_win_horiz(grid, row) that returns true if row row in grid contains three marks belonging to the same player, can be defined by implementing the following algorithm:

1. Set at_left equal to grid[row][0].
2. Return false if at_left is nil.
3. For each col from 1 to 2, return false if grid[row][col] is not equal to at_left.
4. Return true.

The other helper functions can be defined similarly.

Define the following Ruby functions:

1. A function check_win_horiz(grid, row) that returns true if row row in grid contains three marks belonging to the same player.

2. A function check_win_vert(grid, col) that returns true if column col in grid contains three marks belonging to the same player.

3. A function check_win_diagonal1(grid) that returns true if the diagonal from the upper-left corner to lower-right corner contains three marks belonging to the same player.

4. A function check_win_diagonal2(grid) that returns true if the diagonal from the upper-right corner to lower-left corner contains three marks belonging to the same player.

5. A function check_win(grid) that returns true if there are three marks by the same player in a horizontal, vertical, or diagonal line.

Playing Tic Tac Toe

Call the play() function in irb to play your Tic Tac Toe game. Try to come up with games in which:

1. Player 1 wins horizontally.
2. Player 0 wins vertically.
3. Player 1 wins diagonally from upper-left to lower-right
4. Player 0 wins diagonally from upper-right to lower-left
5. There is a tie.

Copy and paste your the irb commands and outputs for these games into the file games.txt.