Problem of the Day -- Tic-Tac-Toe

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/

Permalink: http://problemotd.com/problem/tic-tac-toe/

Comments:

gulliverbear - 10 years, 8 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

reply permalink

Max Burstein - 10 years, 8 months ago

Nicely done!

reply permalink
Pearce Keesling - 10 years, 8 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

reply permalink

Hueho - 10 years, 8 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
  attr_reader :values
  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
  attr_reader :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

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Tic-Tac-Toe

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri