Tic-Tac-Toe implementation where computer should not lose

Question

I have implemented Tic-Tac-Toe so that human can play with the computer, where the computer should never lose. I did a simple analysis before implementing, and I found out that there are certain cells you want to occupy (I named it BEST_CELLS).

Here is the link to the implementation: https://github.com/yangtheman/tictactoe

I have five classes:

• Player: human or CPU
• TicTacToe: holds board instance variable
• TicTacToeGame: gets user input and make CPU move
• TicTacToePrint: prints out the board
• TicTacToeScan: scan the board for any two in a rows and three in a row (column/row/diagonal)

I don't feel that my class design is optimal and scanning algorithms can be improved. I also used hashes for the board for faster look-up, but perhaps using arrays would be easier? I am looking for feedback on my design and algorithm.

tic_tac_toe.rb

class TicTacToe

  X_COORDS = ["A", "B", "C"]
  Y_COORDS = ["1", "2", "3"]

  attr_reader :board

  def initialize
    @best_cells = ["B2", "A1", "A3", "C1", "C3"]
    @board = {}
    X_COORDS.each do |x|
      @board[x] = {}
    end
  end

  def x_coords
    X_COORDS
  end

  def y_coords
    Y_COORDS
  end

  def place_marker(coord_string, player)
    x, y = coord_string.upcase.split("")
    return nil unless coord_valid?(x, y)
    deduct_from_best_cells(x, y)
    @board[x][y] = player
  end

  def best_cells_left
    @best_cells
  end

  def board_full?
    sum = X_COORDS.inject(0) {|sum, x| sum += @board[x].size}
    sum == 9
  end

  def player_cell?(x, y, player)
    @board[x][y] == player
  end

  def empty_cell?(x, y)
    @board[x][y].nil?
  end

  def cell_marker(x, y)
    @board[x][y].nil? ? "." : @board[x][y].marker
  end

  private

  def coord_valid?(x, y)
    within_range?(x, y) && @board[x][y].nil?
  end

  def within_range?(x, y)
    X_COORDS.include?(x) && Y_COORDS.include?(y)
  end

  def deduct_from_best_cells(x, y)
    @best_cells -= ["#{x}#{y}"]
  end

end

tic_tac_toe_game.rb

require_relative './player'
require_relative './tic_tac_toe'
require_relative './tic_tac_toe_scan'
require_relative './tic_tac_toe_print'

class TicTacToeGame

  def initialize
    @board = TicTacToe.new
    @cpu = Player.new
    @human = Player.new(false)
  end

  def play
    print_initial_instruction
    interact_with_human
    play if continue_to_play? 
  end

  def print_board
    TicTacToePrint.print_board(@board)
  end

  def scan_board(player)
    TicTacToeScan.new(@board, player)
  end       

  private

  def print_initial_instruction
    puts "Welcome to a Tic-Tac-Toe Game!\nYou are playing against the computer. Try to win."
    puts "CPU marker is #{@cpu.marker}\nYour marker is #{@human.marker}"
    print_board
  end

  def interact_with_human
    loop do
      if human_turn
        break if game_over?
      else
        puts "Invalid Move. Please try again."
      end
    end
  end

  def game_over?
    human_scan = scan_board(@human)
    return true if game_finished?(human_scan)

    cpu_scan = scan_board(@cpu)
    cpu_turn(cpu_scan, human_scan)
    print_board
    return true if game_finished?(scan_board(@cpu))
  end

  def human_turn
    print "Your Next Move (for example A1 or C3): "
    input = STDIN.gets.chomp().upcase
    @board.place_marker(input, @human)
  end

  def cpu_turn(cpu_scan, human_scan)
    cpu_cell = calculate_cpu_cell(cpu_scan, human_scan)
    @board.place_marker(cpu_cell, @cpu)
    puts "CPU put his/her marker on #{cpu_cell}"
  end

  def calculate_cpu_cell(cpu_scan, human_scan)
    playable_cells = cpu_scan.get_playable_cells
    to_block       = human_scan.get_playable_cells

    if playable_cells[2] && playable_cells[2].length > 0
      cpu_cell = playable_cells[2].first
    elsif to_block[2] && to_block[2].length > 0
      cpu_cell = to_block[2].first
    elsif @board.best_cells_left.length > 0
      cpu_cell = @board.best_cells_left.first
    elsif playable_cells[1] && playable_cells[1].length > 0
      cpu_cell = playable_cells[1].first
    else
      cpu_cell = playable_cells[0].first
    end
    cpu_cell
  end

  def game_finished?(scan)
    if scan.winner?
      if scan.player == @human
        puts "Congratulations, You Won!"
      else
        puts "Sorry. You Lost!"
      end
      return true
    elsif @board.board_full? 
      puts "Awwwww. No one won! Game is tied!"
      return true
    end
    false
  end

  def continue_to_play?
    print "Would you like to play again? (Y or N): "
    if STDIN.gets.chomp() =~ /Y|y/
      @board = TicTacToe.new
      return true
    end
    false
  end

end

tic_tac_toe_scan.rb

class TicTacToeScan

  attr_reader :player, :playable_cells

  def initialize(game, player)
    @game = game
    @player = player
    @playable_cells = {}
  end

  def get_playable_cells
    calculate_playable_cells
    @playable_cells
  end

  def winner?
    calculate_playable_cells if @playable_cells == {}
    @playable_cells[3] && @playable_cells[3] == []
  end

  private

  def calculate_playable_cells
    scan_rows
    scan_cols
    scan_diag_w2e
    scan_diag_e2w
  end

  def add_to_playable_cells(num, array)
    @playable_cells[num] ||= []
    @playable_cells[num] += array
    @playable_cells[num].uniq!    
  end

  def scan_rows
    @game.y_coords.each do |y|
      player_cell_num = 0
      empty_cells = []
      @game.x_coords.each do |x|
        empty_cells << "#{x}#{y}" if @game.empty_cell?(x, y)
        player_cell_num += 1 if @game.player_cell?(x, y, @player)
      end
      add_to_playable_cells(player_cell_num, empty_cells)
    end
  end

  def scan_cols
    @game.x_coords.each do |x|
      player_cell_num = 0
      empty_cells = []
      @game.y_coords.each do |y|
        empty_cells << "#{x}#{y}" if @game.empty_cell?(x, y)
        player_cell_num += 1 if @game.player_cell?(x, y, @player)
      end
      add_to_playable_cells(player_cell_num, empty_cells)
    end
  end

  def scan_diag_w2e
    player_cell_num = 0
    empty_cells = []
    @game.x_coords.each_with_index do |x, index|
      y = @game.y_coords[index]
      empty_cells << "#{x}#{y}" if @game.empty_cell?(x, y)
      player_cell_num += 1 if @game.player_cell?(x, y, @player)
    end
    add_to_playable_cells(player_cell_num, empty_cells)
  end

  def scan_diag_e2w
    player_cell_num = 0
    empty_cells = []
    @game.x_coords.each_with_index do |x, index|
      y = @game.y_coords.reverse[index]
      empty_cells << "#{x}#{y}" if @game.empty_cell?(x, y)
      player_cell_num += 1 if @game.player_cell?(x, y, @player)
    end
    add_to_playable_cells(player_cell_num, empty_cells)
  end

end

Answer 1

Random access and performance
Flambino has correctly remarked that performance is no issue with any container holding a 3x3 matrix, but for the sake of argument, let's say that it might be an issue.
A major benefit in a Hash structure is that it keeps a \$O(1)\$ complexity in setting as well as fetching elements in it, no matter how large it is (as long as the hashing function is well thought of). This is what is called "Random Access".
An Array on the other hand has... Random access as well! That is, as long as you know where your item is, reaching that item is done immediately.
In actuality, small hashes with a fixed number of elements will always be less performant than arrays, since the hashing function will be much too generic, and since hashes are implemented using buckets (some variants of a tree structure) which are kept in an array...

I guess when you said "faster look-up" you might have meant using less code, or maybe having a structure closer to the human metaphor (human player enters A2...) - both are debatable, but from a performance point-of-view it is quite clear cut - there is no reason to work with a Hash for the board state - an array (or a two-dimensional array) will be your best option.

Class names and motivations
Flambino has noted that the TicTacToe prefix is not advisable, and should be removed.
Class names should be of actors and not of actions - this is extra obvious after removing the prefix of the class names - Printer and Scanner are better names than Print and Scan.
Both of those classes look suspiciously specific, which should make us think are they really class-worthy?

Shouldn't the TicTacToePrint class simply be a def print method within the Game class? After all - it is used only once, and you even chose to omit its implementation, since it is trivial...

Also, it seems that TicTacToeScan is an elaborate class intended to maintain the state of the board, I believe that it should either be part of the board's state, or simply make the calculation ad-hoc on the fly.

Oh, and forgotten - what does Player do? Does it do anything? Is it really class worthy?

Method boundaries
A method should do exactly what it claims it does.
For example - interact_with_human looks innocent enough, since it calls human_turn, and breaks if game_over?, but actually game_over? plays the computer's turn!
This is unpredictable and confusing. game_over? should do just that - check whether the game is over. Any other logic should be done elsewhere.

Where is your strategy?
In the title of the post you put at center stage that "computer should not lose" - which means that the point of the exercise is to showcase the strategy for playing cpu. But your strategy code is strewn all over the code (some in TicTacToe, some in TicTacToeGame, and some in TicTacToeScan) - that it is impossible to understand in one reading what your strategy actually is.
From all the classes you decided to implement, that one most obviously missing is the Strategy class (you could call it CpuPlayer, as it stands as complement to the human player against it). It should know (or, at least, claim) which are the best cells, decide to score playable cells by player_cell_num (which, I admit, I couldn't thoroughly understand), and, of course, decide which is the next cell the CPU player should play.

Be DRY
You TicTacToeScan class is full of cut-and-paste code. This makes it hard to read, and hard to maintain.

Answer 2

There's a lot of code there, so I'll just pick out a some things.

From a bird's eye view, it looks like there's just too much code. That's my initial gut feeling without looking at any of it in-depth. It just seems like you're working too hard.

Also:

1. Comment your code, please!
2. Test your code, please!

More in-depth:

You've prefixed (almost) all you classes with TicTacToe. Don't use prefixes: Use a module to do the namespacing. And put Player in there too.

You said you use hashes for performance reasons, but I'd bet something like 99% of the time will be spent waiting on the human player, not the code. I.e. I highly doubt performance is a concern. Premature optimization is the root of all evil and all that. Of course, hashes work just fine for the job, and it's not like it's a cryptic solution. Just don't let "performance" be the only reason you choose it - except if you know performance is an issue, and you have a good indication that hashes will solve it.

Personally, I'd use a flat array. Ruby's array and enumerable methods are powerful, and it's usually very easy to process an array into whatever shape you need. For instance:

# as an example, set each cell to its index
cells = Array.new(9) { |i| i }  # => [0, 1, 2, 3, 4, 5, 6, 7, 8] 

# get the rows as 3 individual arrays
rows = cells.each_slice(3).to_a # => [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

# get the columns
columns = rows.transpose        # => [[0, 3, 6], [1, 4, 7], [2, 5, 8]]

# get the diagonals (a bit more tricky)
diagonals = []
diagonals << 3.times.map { |i| cells[i * 4] }
diagonals << 3.times.map { |i| cells[2 + i * 2] }
# => [[0, 4, 8], [2, 4, 6]]

This requires that you use a slightly different internal structure than what you present to the player. Having the player type "B3" is of course nicer than the player having to figure out the 0-based index of a cell. But the translation is trivial, for instance:

if gets.chomp =~ /^([a-c])([1-3])$/i # get and check user input
  x = %w(a b c).index($1.downcase) # get a 0-2 x-coordinate
  y = $2.to_i - 1 # get a 0-2 y-coordinate
  index = y * 3 + x
else
  # user entered some nonsense
end

Of course, your Board model could easily have a cell[x, y] (or cell(x, y)) method to do the xy-to-index conversion for you, but I'd rather place this concern at the Player model's end.

Speaking of OOP modelling, you're not too far off, although the Scan class seems iffy; its functionality should probably be part of the game board.
I'd do something like this, starting with the "physical" parts of a tic-tac-toe game (board and players), before moving to the more abstract bits (the game and its rules). This is all just sketched out pseudo-code style

module TicTacToe

  # model the board (i.e. the cells), including methods for accessing and setting
  # (unoccupied) cells, getting the down/across/diagonal cells, etc..
  # It does not know about players, it just knows the layout of the board
  class Board
    def initialize; end
    def rows; end
    def columns; end
    def diagonals; end
    def blanks; end
    def full?; end
    def to_s; end
    # ... and so on
  end

  # Model a human player (the initializer may be used to ask the player for his/her name)
  class Human
    def move(board)
      # get user input etc.
    end
  end

  # Model a computer player. Privately, this class can have a bunch of methods for
  # determining its move, but its public API doesn't need more than a #move method
  class Computer
    def move(board)
      # determine best move etc.
    end
  end

  # Model the game, i.e. the players taking turns and so on.
  # Note that the players above don't have to know the board object (until it's
  # time to make a move) or the rules, just like the board doesn't have to know them.
  # This class is the one that ties it all together
  class Game
    # create board and players
    def initialize(); end

    # main game loop. Calls #turn below to have players take a turn,
    # and then checks win-states etc.
    def play; end

    # gets a player, and calls its #move method passing in some representation
    # of the board (it doesn't have to be *the* board object itself; it's mainly
    # so the computer player has something to work with)
    def turn; end
  end
end

I'm not saying this is "the one true way" of doing things. Haven't tried it myself, but it seems to make sense.

You may want to model a Cell class too, depending on how you want to handle the getting/setting of marks on the board. Having cells as actual objects could make a number of things simpler as you'll have object references to pass around.

You may also add a class just to pretty-print the board, but a generic to_s on the Board class itself should suffice.

Also, if the Computer and Human players have anything in common (name and mark, for instance), you should of course have a generic Player class, and inherit from that.

For checking if someone's won, it's just a matter checking the "winning cells" against the last player's mark, e.g. some_cells.all? { |cell| cell == last_player.mark }. Of course, you can skip the checks as long as there are less than 5 marks on the board.

Regarding what to pass to the players, the easiest thing is to just pass the board object itself. It's got all the methods the computer player needs to make decisions. Of course, it allows for "cheating" if the player objects can manipulate the board directly, but this is still Ruby: There's probably a way to do that anyway. It's hard to lock anything down - or at least, it's not worth the effort. But if you want to be strict about it, you can maybe make an immutable board of some sort, and pass that to the players, keeping the mutable version only with the game itself. But again: Worth it?

Lastly: In case of a tie between two computer players, the output should be: "A strange game. The only winning move is not to play. How about a nice game of chess?"