# Problem of the DayA new programming or logic puzzle every Mon-Fri

## Tic-Tac-Toe

HAPPY MONDAY!!!

Today's Problem of the Day is to implement an automated version of our favorite childhood game, tic-tac-toe. Your program can assign random moves for X and O or you can implement some AI to favor one over the other. When someone wins print out the board and who won. If the game is going to be a draw print out the board and print out that it will be a draw.

Based on these conditions your program should never print out a full board unless the final move is a game winning move. If a game is going to end in a draw just print out the board. The program should run until X or O has won 10 games.

Also don't forget, if you have any fun problems you'd like to see on here then please submit them at http://www.problemotd.com/suggest/

• gulliverbear - 3 years, 2 months ago

random choice moves

import random

class board(object):
def __init__(self):
self.n_row = 3
self.n_col = 3
self.n_pos = self.n_row * self.n_col
self.grid = [''] * self.n_pos

def print_grid(self):
for i in range(self.n_row*self.n_col):
if self.grid[i] == '':
print '-',
else:
print self.grid[i],
if (i+1) % self.n_col == 0 and i > 0:
print '\n'

def random_move(self,symbol):
pos = random.choice(self.get_available_moves())
self.grid[pos] = symbol

def get_available_moves(self):
return [i for i in range(self.n_pos) if self.grid[i] == '']

def check_board(self):
paths = self.get_all_paths()

for i in paths:
temp_string = ''
for j in i:
temp_string += self.grid[j]
if temp_string == 'XXX':
return True
elif temp_string == 'OOO':
return True
return False

def get_all_paths(self):
'''
returns a list of lists of all possible winning paths to check
'''
paths = []
# get the column paths
for i in range(self.n_col):
temp_path = []
for j in range(self.n_row):
temp_path.append(i+j*self.n_col)
paths.append(temp_path)

# get the row paths
for i in range(self.n_row):
temp_path = []
for j in range(self.n_col):
temp_path.append(i*self.n_col+j)
paths.append(temp_path)

# get the diagonal going top right to bottom left
temp_path = []
for i in range(self.n_row):
j = self.n_col - 1 - i
temp_path.append(i*self.n_col+j)
paths.append(temp_path)

# get the diagonal going top left to bottom right
temp_path = []
for i in range(self.n_row):
temp_path.append(i*self.n_col+i)
paths.append(temp_path)
return paths

def tictactoe():
b = board()
symbol = 'X'
x_wins = 0
o_wins = 0
draws = 0
game = 0
while x_wins < 10 and o_wins < 10:
if len(b.get_available_moves()) == 0:
b.print_grid()
print 'Draw'
draws += 1
b = board()
game += 1
b.random_move(symbol)
if b.check_board() and symbol == 'X':
b.print_grid()
print 'X wins game ',game
b = board()
x_wins += 1
game += 1
elif b.check_board() and symbol == 'O':
b.print_grid()
print 'O wins game ',game
b = board()
o_wins += 1
game += 1
if symbol == 'X':
symbol = 'O'
else:
symbol = 'X'
print 'X wins: ',x_wins
print 'O wins: ',o_wins
print 'Draws:  ',draws

• Max Burstein - 3 years, 2 months ago

Nicely done!

• Pearce Keesling - 3 years, 2 months ago

I wrote a Tic Tac Toe AI recently, if someone wants to see a (probably bad) example of how to do TicTacToe AI feel free to look. https://github.com/h3ckboy/TicTacToe

• Hueho - 3 years, 2 months ago

Mammoth of a program, but it's because it uses minimax decision trees to play, plus a lil bit of randomness.

I think they probably work, at least the program doesn't crash and output correct games.

STATES = [:cross, :circle, :blank]

module Math
def self.max(a, b)
a > b ? a : b
end

def self.min(a, b)
a < b ? a : b
end
end

class Field
def initialize
@values = Array.new(9, :blank)
end

def [](i, j)
values[i * 3 + j]
end

def []=(i, j, state)
values[i * 3 + j] = state
end

def each_square(state)
0.upto(2) do |i|
0.upto(2) do |j|
yield i, j if self[i, j] == state
end
end
end

def sample_square(state, threshold = 0.3)
loop do
self.each_square(state) do |i, j|
if rand <= threshold
return i, j
end
end
end
end

def game_status
if game_win(:cross)
:cross
elsif game_win(:circle)
:circle
elsif has_blanks?
:continue
else
:draw
end
end

def game_win(status)
return true if values.each_slice(3).any? do |slice|
slice.all? { |s| s == status }
end

return true if 0.upto(2).any? do |col|
0.upto(2)
.map { |row| self[row, col] }
.all? { |s| s == status }
end

return true if 0.upto(2)
.map { |i| self[i, i] }
.all? { |s| s == status }

return true if 0.upto(2)
.map { |i| self[2 - i, i] }
.all? { |s| s == status }

false
end

def has_blanks?
values.any? { |s| s == :blank }
end

def clone
result = Field.new
values.each_with_index { |e, i| result.values[i] = e }
result
end

def inspect
result = "-------\n"
@values.each_slice(3) do |slice|
pretty = slice.map { |st| state_to_s st }
result << ("|" + pretty.join("|") + "|\n")
end
result << "-------\n"
end

def hash
values.hash
end

def ==(other)
values == other.values
end

alias_method :to_s, :inspect

private
def state_to_s(state)
case state
when :circle then "O"
when :cross then "X"
when :blank then " "
end
end
end

class Forks
def initialize
@forks = Array.new(9) { nil }
end

def [](i, j)
forks[i * 3 + j]
end

def []=(i, j, fork)
forks[i * 3 + j] = fork
end

def each_fork
forks.each do |e|
yield e unless e.nil?
end
end

def best_fork
a, b = 0, 0
0.upto(2) do |i|
0.upto(2) do |j|
next if self[i, j].nil?
a, b = i, j if self[a, b].nil? || self[i, j].score > self[a, b].score
end
end
return a, b
end
end

class DecisionTree

attr_reader :maximizing_player, :field, :forks, :game_status, :score

def initialize(player, new_field = nil)
@field = new_field || Field.new
@forks = Forks.new
@maximizing_player = player
end

def self.build(maximizing_player, starting_player)
result = DecisionTree.new(maximizing_player)
result.build_all(starting_player)
result
end

def self.opposite_player(player)
case player
when :cross then :circle
when :circle then :cross
end
end

def finish?
game_status ||= field.game_status
game_status != :continue
end

def generate(next_move)
unless finish?
@field.each_square(:blank) do |i, j|
fork = DecisionTree.new(maximizing_player, field.clone)
fork.field[i, j] = next_move
forks[i, j] = fork
fork.generate DecisionTree.opposite_player(next_move)
end
end
end

def generate_score(maximize = true)
if finish?
if game_status == maximizing_player
@score = 1
elsif game_status == :draw
@score = 0
else
@score = -1
end
else
if maximize
best_score = -Float::INFINITY
forks.each_fork do |fork|
best_score = Math.max(fork.generate_score(!maximize), best_score)
end
@score = best_score
else
best_score = Float::INFINITY
forks.each_fork do |fork|
best_score = Math.min(fork.generate_score(!maximize), best_score)
end
@score = best_score
end
end

@score
end

def build_all(starter)
generate(starter)
generate_score(starter == maximizing_player)
end

end

def main
circle_decisions = {
first: DecisionTree.build(:circle, :circle),
second: DecisionTree.build(:circle, :cross)
}

cross_decisions = {
first: DecisionTree.build(:cross, :cross),
second: DecisionTree.build(:cross, :circle)
}

circle_wins, cross_wins = 0, 0

loop do
first = rand(2) == 0 ? :circle : :cross

circle_tree = if first == :circle
circle_decisions[:first].clone
else
circle_decisions[:second].clone
end

cross_tree = if first == :cross
cross_decisions[:first].clone
else
cross_decisions[:second].clone
end

player_data = {
cross: cross_tree,
circle: circle_tree
}

field = Field.new
player = first
while field.game_status == :continue
i, j = if rand(10) < 5
player_data[player].forks.best_fork
else
field.sample_square(:blank)
end
field[i, j] = player

player_data[:cross] = player_data[:cross].forks[i, j]
player_data[:circle] = player_data[:circle].forks[i, j]
player = DecisionTree.opposite_player(player)
end

puts field
case field.game_status
when :cross then
puts "Cross won!"
cross_wins += 1
when :circle then
puts "Circle won!"
circle_wins += 1
when :draw then puts "Draw!"
end

exit if circle_wins >= 10 || cross_wins >= 10
end
end

main

For anybody wanting to run it: - RAM heavy, be careful. - I used RubiniusX to speed up a bit

Content curated by @MaxBurstein