15110 Fall 2012 [Touretzky/Kaynar]

Lab 10 - Thursday, November 15, 2012

CA Demonstration

Canvas primitives:

Canvas.init(90,90,"Lab10")
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)
Canvas::Text.new("Hello World", 45, 70, :anchor => "center", :fill => "magenta")

input_num(prompt)

def input_num(prompt)
  while true do
    s = Readline::readline(prompt).chomp
    raise "quit" if s == "quit"
    return 0 if s == "0"
    return 1 if s == "1"
    return 2 if s == "2"
    print "input must be a number between 0 and 2 (inclusive)", "\n"
  end
end

Deliverables

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.
A file drawing.txt
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.

Starter code: tic_tac_toe.rb

Activities

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
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 "O", then draw a circle centered at (x,y).
  3. If the grid indicates that the position should hold an "X" (i.e., grid[row][col] == 0), then draw an "X" at the correct coordinates.
  4. If the grid indicates that the position should hold neither an "X" nor an "O", then do the following:
    1. Create a string, consisting of the row, a comma, and the column. (Hint: You can convert the integer x to a string with x.to_s.)
    2. Place this string as "darkblue" text centered at (x,y).
The following usage should result in the image shown above:
```
>> Canvas.init(90,90,"Lab10")
=> true
>> display_grid([[1,nil,0],[nil,0,nil],[nil,nil,nil]])
=> nil
```

Game Play

Trace through the execution of the play function play, given below (on the left), for the first few moves of a game as shown below (on the right):

Code

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

Trace

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

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.

The function check_win(grid) will be easiest to implement if you define helper functions to determine whether there are three marks for the same player lined up horizontally on a particular row, vertically on a particular row, diagonally from upper-left to lower-right, and diagonally from upper-right to lower-left. In this way, check_win could be defined with the following algorithm:
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.
Challenge: Tic-Tac-Toe AI

Create the file tic_tac_toe2.rb containing a function play2() (along with whatever support functions that are needed) that allows a user to play tic-tac-toe against the computer.

Additional Information

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.