# Tic-Tac-Toe implementation where computer should not lose

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

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

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

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

end


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.

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.

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:

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

• Thank you for the feedback! Your feedback in addition to Uri's gives me enough to totally rethink my design. Awesome group of people we have here. – yangtheman Apr 20 '14 at 8:13