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 rubySTDOUT.sync = true # DO NOT REMOVErequire 'set'require 'forwardable'require 'ruby-prof'class Array  include Comparable # Defining the <, <=, >, >= operators on arrays in terms of the already-defined <=> operatorendmodule 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_gameend #moduleRunning the codeThe 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 boardh: height of the boardplayer_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 playerrow: y-coordinate of the playerwalls_left: number of walls available for the playerA line containing the number of walls presentOne line per wall, containing:wall_col: x-coordinate of the wallwall_row: y-coordinate of the wallwall_orientation: wall orientation ('H' or 'V')The program gives one line of output, either:A direction to move in (LEFT, RIGHT, UP, or DOWN); orA new wall placement putX putY putOrientationThe following input makes for a good performance test case:9 9 2 06 2 93 0 747 0 V7 2 V3 0 V5 3 HProfilingI 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) }      #endAccording to this, the most time-consuming methods are the following:%self      total      self      wait     child     calls  name10.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
Codingame: Great Escape bot in Ruby - Follow-up
performance;programming challenge;ruby;pathfinding;ai