Problem of the Day
A 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/

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

Comments:

  • gulliverbear - 3 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 - 3 years, 8 months ago

    Nicely done!

    reply permalink

  • Pearce Keesling - 3 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 - 3 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

Content curated by @MaxBurstein