Codingame: Great Escape bot in Ruby - Follow-up

This is a follow-up to Codingame: Great Escape bot in Ruby.

As mentioned there, my first reasonably sized Ruby project is a bot for CodinGame's Great Escape contest (here is a sample gameplay video).

Following the answers to my first question, I made the code much more Ruby-esque, and split it up into several classes. Now, I'm running up against the time limit (100ms) on the programming challenge server, so I would like to get tips on how to improve the performance of my code. Of course, other comments are also welcome.

#!/usr/bin/env ruby
STDOUT.sync = true # DO NOT REMOVE

require 'set'
require 'forwardable'
require 'ruby-prof'

class Array
  include Comparable # Defining the <, <=, >, >= operators on arrays in terms of the already-defined <=> operator
end

module GreatEscape

  class BinaryHeap
    extend Forwardable

    def initialize
      @elements = []
    end

    # Use @elements.size and @elements.empty?
    def_delegators :@elements, :size, :empty?

    def clear
      @elements.clear
      self
    end

    def push(element)
      @elements << element
      bubble_up(@elements.size - 1)
      self
    end

    alias :<< :push

    def pop
      return nil if empty?

      root = @elements[0]

      @elements[0] = @elements[@elements.size - 1]
      @elements.pop
      trickle_down(0)

      root
    end

    def peek
      return nil if empty?
      @elements[0]
    end

    def inspect
      "<#{self.class}: size=#{size}, peek=#{peek || "nil"}>"
    end

    private

    def bubble_up(i)
      p = parent(i)

      while i > 0 && comp(i, p) < 0
        swap(i, p)
        i = p
        p = parent(i)
      end
    end

    def trickle_down(i)
      loop do
        j = -1
        r = right_child(i)
        l = left_child(i)

        if r < @elements.size && comp(r, i) < 0
          j = comp(l, r) < 0 ? l : r
        elsif l < @elements.size && comp(l, i) < 0
          j = l;
        end

        swap(i, j) unless j < 0
        i = j

        break if i < 0
      end
    end

    def left_child(i)
      2 * i + 1
    end

    def right_child(i)
      2 * i + 2
    end

    def parent(i)
      (i - 1) / 2
    end

    def swap(i, j)
      @elements[i], @elements[j] = @elements[j], @elements[i]
    end

    def comp(i, j)
      @elements[i] <=> @elements[j]
    end
  end

  Player = Struct.new(:id, :row, :col, :walls_left)

  Wall = Struct.new(:row, :col, :dir) do
    def to_s
      "#{col} #{row} #{dir}"
    end
  end

  Node = Struct.new(:row, :col, :left, :right, :up, :down, :dists, :successors) do
    def to_s
      "(#{row}, #{col})"
    end

    def inspect
      "(#{row}, #{col}) ds:#{dists.inspect}"
      # l:#{left.to_s} r:#{right.to_s} u:#{up.to_s} d:#{down.to_s}
      # ss:#{successors.map.with_index { |s, i| successor_string(i) }.to_s}
    end

    def neighbours
      [left, right, up, down].compact
    end

    def successor_string(id)
      case successors[id]
      when nil then "nil"
      when left then "LEFT"
      when right then "RIGHT"
      when up then "UP"
      when down then "DOWN"
      end
    end
  end

  NodeDistWrapper = Struct.new(:node, :player_id) do
    def <=> (other)
      node.dists[player_id] <=> other.node.dists[player_id]
    end
  end

  class GameState
    attr_reader :grid # [[Node]]
    attr_reader :players # [Player]
    attr_reader :walls # Set(Wall)
    attr_reader :w
    attr_reader :h
    attr_reader :turn # Integer

    def initialize(w, h, player_count, turn)
      @w = w
      @h = h
      @turn = turn
      @players = Array.new(player_count) { |id| Player.new(id) }
      @walls = Set.new

      @grid = Array.new(h) { |row| Array.new(w) { |col| Node.new(row, col) } }

      (0..h - 1).each do |row|
        (0..w - 1).each do |col|
          node = @grid[row][col]
          node.left = @grid[row][col - 1] unless col == 0
          node.right = @grid[row][col + 1] unless col == w - 1
          node.up = @grid[row - 1][col] unless row == 0
          node.down = @grid[row + 1][col] unless row == h - 1
          node.dists = [w - col - 1, col]
          node.dists << h - row - 1 if player_count > 2
          node.successors = [node.right, node.left]
          node.successors << node.down if player_count > 2
        end
      end
    end

    # Main gameplay options: move or place a wall
    # These return the new GameState

    def take_action(action)
      if action.is_a?(MoveAction)
        case action.dir
        when "LEFT"
          move_player(0, -1)
        when "RIGHT"
          move_player(0, 1)
        when "UP"
          move_player(-1, 0)
        when "DOWN"
          move_player(1, 0)
        end
      elsif action.is_a?(WallAction)
        add_wall(action.wall)
      end
    end

    def move_player(d_row, d_col)
      g = clone
      g.players[@turn].row += d_row
      g.players[@turn].col += d_col
      g.inc_turn
      g
    end

    def add_wall(wall)
      g = clone
      g.add_walls([wall])
      g.players[@turn].walls_left -= 1
      g.inc_turn
      g
    end

    # Queries

    def valid_wall?(row, col, dir)
      # Within the grid
      return false if row < 0 || row > @h-1
      return false if col < 0 || col > @w-1
      return false if dir == "V" && row == @h-1
      return false if dir == "H" && col == @w-1

      # Does not intersect existing walls
      @walls.each do |wall|
        if wall.dir == dir
          return false if dir == "V" && col == wall.col && (row - wall.row).abs < 2
          return false if dir == "H" && row == wall.row && (col - wall.col).abs < 2
        else
          return false if dir == "V" && col == wall.col + 1 && row == wall.row - 1
          return false if dir == "H" && col == wall.col - 1 && row == wall.row + 1
        end
      end

      # Does not cut off a player's last path
      @players.each do |p|
        return false unless verify_destination_still_reachable_with_wall(row, col, dir, p.id)
      end

      true
    end

    def player_won?(player)
      case player.id
      when 0
        player.col == @w - 1
      when 1
        player.col == 0
      when 2
        player.row == @h - 1
      end
    end

    def player_active?(player)
      player.col >= 0 && !player_won?(player)
    end

    def ended?
      @players.select { |p| player_active?(p) }.size <= 1
    end

    # Methods that modify this GameState

    def update_player(player_id, new_row, new_col, new_walls_left)
      p = @players[player_id]
      p.row = new_row
      p.col = new_col
      p.walls_left = new_walls_left
    end

    def add_walls(walls)
      invalid = []

      walls.each do |wall|
        next unless @walls.add?(wall)
        invalid.concat(add_wall!(wall))
      end

      compute_new_paths(invalid) unless invalid.empty?
    end

    def inc_turn
      loop do
        @turn = (@turn + 1) % @players.size
        break if player_active?(@players[@turn])
      end
    end

    # Make sure clone and dup create deep copies
    def initialize_copy(other)
      super

      @players = deep_array_copy(@players)
      @walls = @walls.clone # Note: wall objects are not copied, just the references. This doesn't matter, as long as we never modify these.

      grid_copy = Array.new(@h) { |row| Array.new(@w) { |col| Node.new(row, col) } }

      (0..@h - 1).each do |row|
        (0..@w - 1).each do |col|
          original_node = @grid[row][col]
          node = grid_copy[row][col]

          node.left = grid_copy[row][col - 1] if original_node.left
          node.right = grid_copy[row][col + 1] if original_node.right
          node.up = grid_copy[row - 1][col] if original_node.up
          node.down = grid_copy[row + 1][col] if original_node.down

          node.dists = original_node.dists.clone
          node.successors = original_node.successors.map do |succ|
            case succ
            when original_node.left
              node.left
            when original_node.right
              node.right
            when original_node.up
              node.up
            when original_node.down
              node.down
            end
          end
        end
      end

      @grid = grid_copy
    end

    private

    # Breaks the connections in the grid crossing this wall
    # Returns the list of invalidated cells
    def add_wall!(wall)
      invalid = []

      if wall.dir == "V"
        # Wall starts at the top left corner of (row, col) and continues down for 2 cells
        invalid.concat(break_connection(wall.row, wall.col - 1, wall.row, wall.col))
        invalid.concat(break_connection(wall.row + 1, wall.col - 1, wall.row + 1, wall.col))
      else # H
        # Wall starts at the top left corner of (row, col) and continues right for 2 cells
        invalid.concat(break_connection(wall.row - 1, wall.col, wall.row, wall.col))
        invalid.concat(break_connection(wall.row - 1, wall.col + 1, wall.row, wall.col + 1))
      end

      invalid
    end

    # Breaks the connections in the grid between these cells
    # Returns the list of invalidated cells
    def break_connection(row1, col1, row2, col2)
      if row1 == row2
        node1 = @grid[row1][col1 < col2 ? col1 : col2]
        node2 = @grid[row1][col1 < col2 ? col2 : col1]

        return [] unless node1.right

        node1.right = nil
        node2.left = nil
      else
        node1 = @grid[row1 < row2 ? row1 : row2][col1]
        node2 = @grid[row1 < row2 ? row2 : row1][col1]

        return [] unless node1.down

        node1.down = nil
        node2.up = nil
      end

      # Now that we broke the connection, collect all the nodes whose shortest paths we impacted
      invalid = []

      @players.each do |p|
        invalid.concat(invalidate_cell(node1, p.id)) if node1.successors[p.id] == node2
        invalid.concat(invalidate_cell(node2, p.id)) if node2.successors[p.id] == node1
      end

      invalid
    end

    # Invalidates the given node and all nodes whose shortest path go through it
    # Returns the list of invalidated cells
    def invalidate_cell(node, player_id)
      node.successors[player_id] = nil

      # Check if we can reroute
      node.neighbours.each do |n|
        if n.dists[player_id] == node.dists[player_id] - 1
          node.successors[player_id] = n
          return []
        end
      end

      # No rerouting possible. Invalidate this and predecessors
      node.dists[player_id] = nil

      invalid = [[node, player_id]]

      node.neighbours.each do |n|
        invalid.concat(invalidate_cell(n, player_id)) if n.successors[player_id] == node
      end

      invalid
    end

    # Updates the shortest paths of the given (cell, player_id) pairs
    def compute_new_paths(invalid)
      player_cells = Array.new(players.size) {[]}

      invalid.each do |node, id|
        player_cells[id] << node
      end

      @players.each do |p|
        compute_new_paths_for_player(player_cells[p.id], p.id)
      end
    end

    # Updates the shortest paths of the given cells
    def compute_new_paths_for_player(invalid, player_id)
      frontier = BinaryHeap.new()

      # Add all non-invalidated neighbours to our frontier
      invalid.each do |node|
        node.neighbours.each do |neighbour|
          frontier << NodeDistWrapper.new(neighbour, player_id) if neighbour.dists[player_id]
        end
      end

      # Expand the closest frontier node until they're out
      until frontier.empty?
        node = frontier.pop.node

        node.neighbours.each do |neighbour|
          if neighbour.dists[player_id].nil? || neighbour.dists[player_id] > node.dists[player_id] + 1
            neighbour.dists[player_id] = node.dists[player_id] + 1
            neighbour.successors[player_id] = node
            frontier << NodeDistWrapper.new(neighbour, player_id)
          end
        end
      end
    end

    def verify_destination_still_reachable_with_wall(row, col, dir, player_id)
      visited = Array.new(@h) { Array.new(@w) }
      explore(@players[player_id].row, @players[player_id].col, player_id, row, col, dir, visited)
    end

    # DFS with preference towards the destination side
    def explore(row, col, player_id, wall_row, wall_col, wall_dir, visited)
      node = @grid[row][col]
      return true if node.dists[player_id] == 0

      visited[row][col] = true

      neighbours =
        case player_id
        when 0
          [node.right, node.up, node.down, node.left]
        when 1
          [node.left, node.up, node.down, node.right]
        when 2
          [node.down, node.left, node.right, node.up]
        end

      neighbours.compact.each do |n|
        next if wall_blocks(wall_row, wall_col, wall_dir, node, n) || visited[n.row][n.col]
        return true if explore(n.row, n.col, player_id, wall_row, wall_col, wall_dir, visited)
      end

      false
    end

    def wall_blocks(wall_row, wall_col, wall_dir, node, neighbour)
      if node.row == neighbour.row
        wall_dir == "V" && wall_col == [node.col, neighbour.col].max && (wall_row == node.row || wall_row == node.row - 1)
      else
        wall_dir == "H" && wall_row == [node.row, neighbour.row].max && (wall_col == node.col || wall_col == node.col - 1)
      end
    end

    def deep_array_copy(array)
      result = array.clone
      result.clear
      array.each { |v| result << v.clone }
      result
    end
  end

  MoveAction = Struct.new(:dir) do
    def to_s
      dir
    end
  end

  WallAction = Struct.new(:wall) do
    def to_s
      wall.to_s
    end
  end

  class Agent
    def self.find_best_move(game)
      # DEBUG
      me = game.players[game.turn]
      myDist = game.grid[me.row][me.col].dists[me.id]
      opponents = game.players.select { |p| p.id != game.turn && game.player_active?(p) }
      oppDists = opponents.map { |o| game.grid[o.row][o.col].dists[o.id] }.sort

      STDERR.puts "myDist: #{myDist} oppDists: #{oppDists}"

      top_level_alpha_beta(game, 2 * (1 + opponents.size))
    end

    private

    NEGATIVE_INFNITY = [-1000000, -1000000]
    POSITIVE_INFINITY = [1000000, 1000000]

    def self.top_level_alpha_beta(game, depth)
      best_val = NEGATIVE_INFNITY
      best_action = nil

      my_possible_actions(game).each do |action|
        val = alpha_beta_search(game.take_action(action), game.turn, depth, best_val, POSITIVE_INFINITY)
        STDERR.puts "Value of #{action} is #{val}"

        if val > best_val
          best_val = val
          best_action = action
        end
      end

      best_action
    end

    def self.alpha_beta_search(game, my_id, turns_left, alpha, beta)
      return evaluate(game, my_id) if turns_left == 0 || game.player_won?(game.players[my_id]) || game.ended?

      if game.turn == my_id
        # Maximize
        best_val = NEGATIVE_INFNITY
        my_possible_actions(game).each do |action|
          val = alpha_beta_search(game.take_action(action), my_id, turns_left - 1, alpha, beta)
          best_val = val > best_val ? val : best_val
          alpha = val > alpha ? val : alpha

          break if beta <= alpha
        end
      else
        # Minimize
        best_val = POSITIVE_INFINITY
        opponent_actions(game, my_id).each do |action|
          val = alpha_beta_search(game.take_action(action), my_id, turns_left - 1, alpha, beta)
          best_val = val < best_val ? val : best_val
          beta = val < beta ? val : beta

          break if beta <= alpha
        end
      end

      best_val
    end

    WIN_SCORE = 1000
    LOSE_SCORE = -1000

    def self.evaluate(game, my_id)
      me = game.players[my_id]
      myDist = game.grid[me.row][me.col].dists[me.id]

      opponents = game.players.select { |p| p.id != my_id && p.col >= 0 }

      if opponents.size == 1
        return [LOSE_SCORE, WIN_SCORE] if myDist == 0

        opp = opponents[0]
        oppDist = game.grid[opp.row][opp.col].dists[opp.id]
        [LOSE_SCORE, oppDist == 0 ? LOSE_SCORE : oppDist - myDist]
      else # 2 alive opponents
        return [WIN_SCORE, WIN_SCORE] if myDist == 0

        oppDists = opponents.map { |o| game.grid[o.row][o.col].dists[o.id] }.sort
        oppDists.map { |oppDist| oppDist == 0 ? LOSE_SCORE : oppDist - myDist }
      end
    end

    def self.my_possible_actions(game)
      me = game.players[game.turn]
      myDist = game.grid[me.row][me.col].dists[me.id]

      actions = [MoveAction.new(game.grid[me.row][me.col].successor_string(me.id))] # Follow the shortest path

      # Try to block opponents that will beat me if left unopposed
      if me.walls_left > 0
        game.players.select { |p| p != me && game.player_active?(p) }.each do |o|
          dist = game.grid[o.row][o.col].dists[o.id]
          actions.concat(block_opponent(game, o, 4, 4)) if dist < myDist || (dist == myDist && o.id < me.id)
        end
      end

      actions

      # Block people

      # All moves

      # Protect my path

      # TODO: order
      # If I'm winning, consider move along shortest path first
      # And protecting wall placements second
      # Otherwise, consider blocking wall placements first
    end

    def self.opponent_actions(game, my_id)
      opp = game.players[game.turn]

      # Move along the shortest path
      actions = [MoveAction.new(game.grid[opp.row][opp.col].successor_string(opp.id))]

      # Block me
      actions.concat(block_opponent(game, game.players[my_id], 1, 8)) if opp.walls_left > 0

      actions
    end

    def self.block_opponent(game, opponent, max_blocks, max_lookahead)
      # Try to block each move of the upcoming shortest path
      block_actions = []
      node = game.grid[opponent.row][opponent.col]
      succ = node.successors[opponent.id]

      max_lookahead.times do
        break if succ.nil? || block_actions.size >= max_blocks

        block_actions.concat(block_connection(game, node, succ))

        node = succ
        succ = node.successors[opponent.id]
      end

      block_actions
    end

    def self.block_connection(game, node, succ)
      if node.row == succ.row
        col = [node.col, succ.col].max
        tryWall(game, node.row, col, "V") + tryWall(game, node.row - 1, col, "V")
      else
        row = [node.row, succ.row].max
        tryWall(game, row, node.col, "H") + tryWall(game, row, node.col - 1, "H")
      end
    end

    def self.tryWall(game, row, col, dir)
      game.valid_wall?(row, col, dir) ? [WallAction.new(Wall.new(row, col, dir))] : []
    end
  end

  class Interface
    def self.run_game
      # w: width of the board
      # h: height of the board
      # player_count: number of players (2 or 3)
      # my_id: id of my player (0 = 1st player, 1 = 2nd player, ...)
      w, h, player_count, my_id = gets.split(" ").map(&:to_i)

      game = GameState.new(w, h, player_count, my_id)

      # game loop
      loop do
        player_count.times do |id|
          # x: x-coordinate of the player
          # y: y-coordinate of the player
          # walls_left: number of walls available for the player
          col, row, walls_left = gets.split(" ").map(&:to_i)
          game.update_player(id, row, col, walls_left)

          STDERR.puts "#{col} #{row} #{walls_left}"
        end

        wall_count = gets.to_i # number of walls on the board
        STDERR.puts "#{wall_count}"

        walls = []
        wall_count.times do
          # wall_x: x-coordinate of the wall
          # wall_y: y-coordinate of the wall
          # wall_orientation: wall orientation ('H' or 'V')
          wall_x, wall_y, wall_orientation = gets.split(" ")
          walls << Wall.new(wall_y.to_i, wall_x.to_i, wall_orientation)
          STDERR.puts "#{wall_x} #{wall_y} #{wall_orientation}"
        end

        game.add_walls(walls)

        puts GreatEscape::Agent.find_best_move(game).to_s
      end
    end
  end

  GreatEscape::Interface.run_game

end #module

Running the code

The bot communicates over standard in and out, using a cryptic format defined by the competition software:

The first line of the input is given once at the start of the game and sets these variables:

• w: width of the board
• h: height of the board
• player_count: number of players (2 or 3)
• my_id: id of my player (0 = 1st player, 1 = 2nd player, ...)

Every game turn, my program expects the following input:

• One line per player, containing:
  • col: x-coordinate of the player
  • row: y-coordinate of the player
  • walls_left: number of walls available for the player
• A line containing the number of walls present
• One line per wall, containing:
  • wall_col: x-coordinate of the wall
  • wall_row: y-coordinate of the wall
  • wall_orientation: wall orientation ('H' or 'V')

The program gives one line of output, either:

• A direction to move in (LEFT, RIGHT, UP, or DOWN); or
• A new wall placement putX putY putOrientation

The following input makes for a good performance test case:

9 9 2 0
6 2 9
3 0 7
4
7 0 V
7 2 V
3 0 V
5 3 H

Profiling

I ran ruby-prof on the main loop by replacing it with

      # game loop
      #loop do
        player_count.times do |id|
          # x: x-coordinate of the player
          # y: y-coordinate of the player
          # walls_left: number of walls available for the player
          col, row, walls_left = gets.split(" ").map(&:to_i)
          game.update_player(id, row, col, walls_left)

          STDERR.puts "#{col} #{row} #{walls_left}"
        end

        wall_count = gets.to_i # number of walls on the board
        STDERR.puts "#{wall_count}"

        walls = []
        wall_count.times do
          # wall_x: x-coordinate of the wall
          # wall_y: y-coordinate of the wall
          # wall_orientation: wall orientation ('H' or 'V')
          wall_x, wall_y, wall_orientation = gets.split(" ")
          walls << Wall.new(wall_y.to_i, wall_x.to_i, wall_orientation)
          STDERR.puts "#{wall_x} #{wall_y} #{wall_orientation}"
        end

        RubyProf.start
        game.add_walls(walls)

        puts GreatEscape::Agent.find_best_move(game).to_s
        result = RubyProf.stop

        File.open("profile_data.txt", 'w') { |file| RubyProf::FlatPrinterWithLineNumbers.new(result).print(file) }
        File.open("profile_data_graph.html", 'w') { |file| RubyProf::GraphHtmlPrinter.new(result).print(file) }
        File.open("profile_data_stack.html", 'w') { |file| RubyProf::CallStackPrinter.new(result).print(file) }
      #end

According to this, the most time-consuming methods are the following:

%self      total      self      wait     child     calls  name
10.30      0.136     0.057     0.000     0.079    32320   Array#map
 4.08      0.029     0.023     0.000     0.006    45960   Struct#==
 3.80      0.047     0.021     0.000     0.026    96660   Kernel#===
 3.62      0.020     0.020     0.000     0.000   149375   GreatEscape::Node#left
 3.17      0.023     0.018     0.000     0.006    18197   GreatEscape::GameState#wall_blocks
 3.08      0.017     0.017     0.000     0.000   123532   GreatEscape::Node#dists
 3.00      0.029     0.017     0.000     0.013     4524   Kernel#loop
 2.65      0.030     0.015     0.000     0.016    14595   GreatEscape::Node#neighbours
 2.45      0.014     0.014     0.000     0.000   120317   GreatEscape::Node#right