YWF and AIs

alphabeta_com.rb

#!/usr/bin/env ruby

require_relative "board"
require_relative "game"

module YWF
  class AlphaBetaCom
    def initialize(color, depth=3)
      @color = color
      @opponent = (color == Board::BLACK) ? Board::WHITE : Board::BLACK
      @depth = depth
    end

    def select(board)
      current_select = nil
      current_select_value = -1000
      opponent_best_value = 1000
      board.legal_actions.each do |action|
        value = calculate_action_value(board, action, @depth, current_select_value, opponent_best_value)
        if value > current_select_value
          current_select = action
          current_select_value = value
          if current_select_value >= opponent_best_value
            break
          end
        end
      end

      puts "#{current_select[0].to_s} #{current_select[1]}."
      current_select.flatten
    end

    private

    def calculate_action_value(board, action, depth, self_best_value, opponent_best_value)
      command, place = action
      new_board = case command
                  when :pass
                    board.pass
                  when :play
                    board.play(*place)
                  when :change
                    board.change(*place)
                  end
      if (depth == 1) || new_board.game_end?
        if new_board.win?(@color)
          100
        elsif new_board.win?(@opponent)
          -100
        else
          new_board.count(@color) - new_board.count(@opponent)
        end
      else
        # NOTE:
        # if new board turn is player's color,
        # the player should make action value higher.
        # otherwise, the player should make action value lower.
        # so, if new baord turn is player's color,
        # set initial value to current best value, which is
        # opponent_best_value of original board, and update value
        # only if (value > opponent_best_value).
        # otherwise, set initial value to current best value,
        # which is opponent_best_value of original board,
        # and update value only if (value < opponent_best_value),
        # its equivalent to (-value > -opponent_best_value).
        #
        # by setting 'sign' to 1 if new board turn is player's color
        # and to -1 otherwise, update value only if
        #   (value * sign) > (current_value * sign)

        sign = (new_board.turn == @color) ? 1 : -1

        new_board.legal_actions.each do |action|
          value = calculate_action_value(new_board, action, depth - 1, opponent_best_value, self_best_value)
          if (value * sign) > (opponent_best_value * sign)
            opponent_best_value = value
          end

          # if (opponent_best_value * sign) >= (self_best_value * sign),
          # real opponent_best_value, which means this action's value,
          # is equal to or higher than current opponent_best_value,
          # so the turn player of original board cannot select this action
          # because this inequality means
          #   (self_best_value * original board sign)
          #       >= (this action's value * original board sign).
          # (note that opponent_best value is equal to this action value
          # and original board sign is equal to -sign)
          if (opponent_best_value * sign) >= (self_best_value * sign)
            break
          end
        end

        opponent_best_value
      end
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include YWF

  black_player = AlphaBetaCom.new(Board::BLACK)
  white_player = AlphaBetaCom.new(Board::WHITE)

  game = Game.new(black_player, white_player)
  game.start
end

board.rb

module YWF
  class Board
    ROW_MIN = 1
    ROW_MAX = 9
    COL_MIN = 1
    COL_MAX = 9

    WALL = -1
    EMPTY = 0
    BLACK = 1
    GRAY = 2
    WHITE = 3

    Direction = [
      [-1, -1], [-1,  0], [-1,  1],
      [ 0, -1],           [ 0,  1],
      [ 1, -1], [ 1,  0], [ 1,  1],
    ]

    def initialize(other=nil)
      @board = [
        [WALL, WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, GRAY , BLACK, WHITE, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, WHITE, GRAY , BLACK, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, BLACK, WHITE, GRAY , EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL],
      ]
      @move = 1
      @turn = BLACK
      @token = GRAY
      if other
        copy(other)
      end

      # to avoid appearing same situation by 'change'
      @previous = nil

      # cache (lazy)
      @count = Array.new(4)
      @legal_check_cache = Array.new(ROW_MAX*COL_MAX)
      @playable_places_cache = nil
      @changeable_places_cache = nil
      @board_hash_cache = nil
    end

    attr_reader :move, :turn, :token

    def board_hash
      if @board_hash_cache.nil?
        value = 0
        (ROW_MIN..ROW_MAX).each do |row|
          (COL_MIN..COL_MAX).each do |col|
            value += row * col * @board[row][col]
          end
        end
        @board_hash_cache = value
      end
      @board_hash_cache
    end

    def same_situation?(other)
      if @turn != other.turn
        return false
      end
      if @token != other.token
        return false
      end
      if self.board_hash != other.board_hash
        return false
      end
      (ROW_MIN..ROW_MAX).each do |row|
        (COL_MIN..COL_MAX).each do |col|
          if @board[row][col] != other.color(row, col)
            return false
          end
        end
      end
      true
    end

    def opponent
      (@turn + 2) % 4
    end

    def color(row, col)
      if (row < ROW_MIN) || (ROW_MAX < row)
        raise "invalid row. [row: #{row}]"
      end
      if (col < COL_MIN) || (COL_MAX < col)
        raise "invalid col. [col: #{col}]"
      end
      @board[row][col]
    end

    def count(color)
      if (color != EMPTY) && (color != BLACK) && (color != GRAY) && (color != WHITE)
        raise "invalid color. [color: #{color}]"
      end

      if @count[color].nil?
        count = 0
        (ROW_MIN..ROW_MAX).each do |row|
          (COL_MIN..COL_MAX).each do |col|
            if self.color(row, col) == color
              count += 1
            end
          end
        end
        @count[color] = count
      end

      @count[color]
    end

    def playable?(row, col)
      if self.color(row, col) != EMPTY
        return false
      end

      index = (row - 1) * COL_MAX + (col - 1)
      if @legal_check_cache[index].nil?
        @legal_check_cache[index] = has_color_from?(row, col)
      end
      @legal_check_cache[index]
    end

    def changeable?(row, col)
      if self.color(row, col) != GRAY
        return false
      end

      index = (row - 1) * COL_MAX + (col - 1)
      if @legal_check_cache[index].nil?
        if (@token != GRAY) && (@token != @turn)
          @legal_check_cache[index] = false
        else
          if has_color_from?(row, col)
            new_board = self.change(row, col, false)
            if new_board.has_same_situation_before?
              @legal_check_cache[index] = false
            else
              @legal_check_cache[index] = true
            end
          else
            @legal_check_cache[index] = false
          end
        end
      end
      @legal_check_cache[index]
    end

    def must_pass?
      (self.playable_places.size == 0) && (self.changeable_places.size == 0)
    end

    def playable_places
      if @playable_places_cache.nil?
        places = []
        (ROW_MIN..ROW_MAX).each do |row|
          (COL_MIN..COL_MAX).each do |col|
            if self.playable?(row, col)
              places.push [row, col]
            end
          end
        end
        @playable_places_cache = places
      end
      @playable_places_cache.clone
    end

    def changeable_places
      if @changeable_places_cache.nil?
        places = []
        if @token != opponent
          (ROW_MIN..ROW_MAX).each do |row|
            (COL_MIN..COL_MAX).each do |col|
              if self.changeable?(row, col)
                places.push [row, col]
              end
            end
          end
        end
        @changeable_places_cache = places
      end
      @changeable_places_cache.clone
    end

    def legal_actions
      actions = Array.new
      if self.must_pass?
        actions.push [:pass, nil]
      else
        self.playable_places.each do |place|
          actions.push [:play, place]
        end
        self.changeable_places.each do |place|
          actions.push [:change, place]
        end
      end
      actions
    end

    def play(row, col)
      unless self.playable?(row, col)
        raise "not playable. [row: #{row}, col: #{col}]"
      end

      new_board = self.class.new(self)
      new_board.put_piece(row, col)
      new_board.change_turn
      new_board.add_move

      new_board
    end

    def change(row, col, check=true)
      if check
        unless self.changeable?(row, col)
          raise "not changeable. [row: #{row}, col: #{col}]"
        end
      end

      new_board = self.class.new(self)
      new_board.put_piece(row, col)
      new_board.change_token
      new_board.change_turn
      new_board.set_previous(self)
      new_board.add_move

      new_board
    end

    def pass
      unless self.must_pass?
        raise "cannot pass."
      end

      new_board = self.class.new(self)
      new_board.change_turn
      new_board.add_move

      new_board
    end

    def game_end?
      if self.count(EMPTY) == 0
        return true
      end

      if self.must_pass?
        passed = self.pass
        if passed.must_pass?
          return true
        end
      end

      false
    end

    def win?(color)
      if (color != BLACK) && (color != WHITE)
        raise "invalid color. [color: #{color}]"
      end

      unless self.game_end?
        return false
      end

      if color == BLACK
        (self.count(BLACK) > self.count(WHITE)) ||
          ((self.count(BLACK) == self.count(WHITE)) && (@token == BLACK))
      else
        (self.count(BLACK) < self.count(WHITE)) ||
          ((self.count(BLACK) == self.count(WHITE)) && (@token == WHITE))
      end
    end

    protected

    attr_reader :previous

    def has_same_situation_before?
      ancestor = @previous
      while (ancestor != nil)
        if self.same_situation?(ancestor)
          return true
        else
          ancestor = ancestor.previous
        end
      end
      false
    end

    def put_piece(row, col)
      @board[row][col] = @turn

      color_diff = (@turn == BLACK) ? -1 : +1
      Direction.each do |direction|
        if has_color_from_to?(row, col, direction)
          traverse_to(row, col, direction) do |step_count, traverse_row, traverse_col, traverse_color|
            if traverse_color == @turn
              break
            else
              @board[traverse_row][traverse_col] += color_diff
            end
          end
        end
      end
    end

    def change_turn
      @turn = self.opponent
    end

    def change_token
      @token += (@turn == BLACK) ? +1 : -1
    end

    def set_previous(other)
      @previous = other
    end

    def add_move
      @move += 1
    end

    private

    def copy(other)
      (ROW_MIN..ROW_MAX).each do |row|
        (COL_MIN..COL_MAX).each do |col|
          @board[row][col] = other.color(row, col)
        end
      end
      @move = other.move
      @turn = other.turn
      @token = other.token
    end

    def has_color_from?(row, col)
      Direction.each do |direction|
        if has_color_from_to?(row, col, direction)
          return true
        end
      end
      return false
    end

    def has_color_from_to?(row, col, direction)
      traverse_to(row, col, direction) do |step_count, traverse_row, traverse_col, traverse_color|
        if traverse_color == @turn
          if step_count == 1
            return false
          else
            return true
          end
        end
      end
      return false
    end

    def traverse_to(row, col, direction, &block)
      # NOTE:
      # 'traverse_to' accesses to 'WALL',
      # so 'color' cannot be used.
      traverse_row = row + direction[0]
      traverse_col = col + direction[1]
      traverse_color = @board[traverse_row][traverse_col]
      step_count = 1
      while (traverse_color != WALL) && (traverse_color != EMPTY)
        block.call(step_count, traverse_row, traverse_col, traverse_color)
        traverse_row += direction[0]
        traverse_col += direction[1]
        traverse_color = @board[traverse_row][traverse_col]
        step_count += 1
      end
    end
  end

  module BoardViewer
    COL_INDEX = "     1   2   3   4   5   6   7   8   9"
    LINE      = "   +---+---+---+---+---+---+---+---+---+"

    def view(board)
      puts "[#{sprintf '%03d', board.move}] turn: #{mark(board.turn)}, token: #{mark(board.token)}"
      puts COL_INDEX
      puts LINE
      (Board::ROW_MIN..Board::ROW_MAX).each do |row|
        print " #{row} "
        (Board::COL_MIN..Board::COL_MAX).each do |col|
          color = board.color(row, col)
          print "| #{mark(color)} "
        end
        puts "|"
        puts LINE
      end
    end

    def mark(color)
      case color
      when Board::EMPTY
        " "
      when Board::BLACK
        "O"
      when Board::GRAY
        "-"
      when Board::WHITE
        "X"
      else
        raise "invalid color. [color: #{color}]"
      end
    end

    module_function :view, :mark
  end
end

game.rb

module YWF
  class Game
    def initialize(black_player, white_player)
      @black_player = black_player
      @white_player = white_player
    end

    def start
      board = Board.new
      done = loop do
        BoardViewer.view(board)

        if board.game_end?
          break true
        end

        if board.must_pass?
          puts "pass!"
          board = board.pass
        else
          if board.turn == Board::BLACK
            command, row, col = @black_player.select(board)
          else
            command, row, col = @white_player.select(board)
          end

          case command
          when :play
            board = board.play(row, col)
          when :change
            board = board.change(row, col)
          when :exit
            break false
          end
        end
      end

      puts "----------"
      if done
        puts "black: #{board.count(Board::BLACK)}, white: #{board.count(Board::WHITE)}"
        if board.win?(Board::BLACK)
          puts "#{BoardViewer.mark(Board::BLACK)} win."
        elsif board.win?(Board::WHITE)
          puts "#{BoardViewer.mark(Board::WHITE)} win."
        else
          puts "draw."
        end
      else
        puts "exit."
      end
    end
  end
end

greedy_com.rb

#!/usr/bin/env ruby

require_relative "board"
require_relative "game"

module YWF
  class GreedyCom
    def initialize(color)
      @color = color
      @opponent = (color == Board::BLACK) ? Board::WHITE : Board::BLACK
    end

    def select(board)
      current_select = nil
      current_select_value = -1000
      board.legal_actions.each do |action|
        command, place = action
        new_board = case command
                    when :pass
                      board.pass
                    when :play
                      board.play(*place)
                    when :change
                      board.change(*place)
                    end
        new_board_value = calculate_board_value(new_board)
        if new_board_value > current_select_value
          current_select = action
          current_select_value = new_board_value
        end
      end

      puts "#{current_select[0].to_s} #{current_select[1]}."
      current_select.flatten
    end

    private

    def calculate_board_value(board)
      if board.win?(@color)
        100
      elsif board.win?(@opponent)
        -100
      else
        board.count(@color) - board.count(@opponent)
      end
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include YWF

  black_player = GreedyCom.new(Board::BLACK)
  white_player = GreedyCom.new(Board::WHITE)

  game = Game.new(black_player, white_player)
  game.start
end

minmax_com.rb

#!/usr/bin/env ruby

require_relative "board"
require_relative "game"

module YWF
  class MinMaxCom
    def initialize(color, depth=3)
      @color = color
      @opponent = (color == Board::BLACK) ? Board::WHITE : Board::BLACK
      @depth = depth
    end

    def select(board)
      current_select = nil
      current_select_value = -1000
      board.legal_actions.each do |action|
        value = calculate_action_value(board, action, @depth)
        if value > current_select_value
          current_select = action
          current_select_value = value
        end
      end

      puts "#{current_select[0].to_s} #{current_select[1]}."
      current_select.flatten
    end

    private

    def calculate_action_value(board, action, depth)
      command, place = action
      new_board = case command
                  when :pass
                    board.pass
                  when :play
                    board.play(*place)
                  when :change
                    board.change(*place)
                  end
      if (depth == 1) || new_board.game_end?
        if new_board.win?(@color)
          100
        elsif new_board.win?(@opponent)
          -100
        else
          new_board.count(@color) - new_board.count(@opponent)
        end
      else
        # NOTE:
        # if new board turn is player's color,
        # the player should make action value higher.
        # otherwise, the player should make action value lower.
        # so, if new baord turn is player's color,
        # set initial value very low and update value
        # only if (value > current_value).
        # otherwise, set initial value very high and update value
        # only if (value < current_value), its equivalent to
        # (-value > -current_value).
        #
        # by setting 'sign' to 1 if new board turn is player's color
        # and to -1 otherwise,
        # set initial value to very low (or very high) by
        #   current_value = (very low value) * (sign)
        # and update value only if
        #   (value * sign) > (current_value * sign)

        sign = (new_board.turn == @color) ? 1 : -1

        current_value = -1000 * sign
        new_board.legal_actions.each do |action|
          value = calculate_action_value(new_board, action, depth - 1)
          if (value * sign) > (current_value * sign)
            current_value = value
          end
        end

        current_value
      end
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include YWF

  black_player = MinMaxCom.new(Board::BLACK)
  white_player = MinMaxCom.new(Board::WHITE)

  game = Game.new(black_player, white_player)
  game.start
end

random_com.rb

#!/usr/bin/env ruby

require_relative "board"
require_relative "game"

module YWF
  class RandomCom
    def select(board)
      select = board.legal_actions.sample
      puts "#{select[0].to_s} #{select[1]}."
      select.flatten
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include YWF

  game = Game.new(RandomCom.new, RandomCom.new)
  game.start
end