secret

eregon / README

Last active 2010-03-31

This is a player I made for fun, normally compatible ruby 1.8.7 and 1.9
 
I hope you'll let me battle against others, while I'm posting my solution late
(anyway I can't win this time because I did last time ;) )

class String
  unless "".respond_to? :ord
    def ord
      self.unpack('c')[0]
    end
  end
end
 
class Coord < Struct.new(:x, :y)
  SIDE = 10
  
  N = Coord.new(0,-1)
  E = Coord.new( 1,0)
  S = Coord.new(0, 1)
  W = Coord.new(-1,0)
  DIRS = { :h => [W, E], :v => [N, S] }
  DIRECTIONS = [N, E, S, W]
  
  def initialize(*args)
    case args.length
    when 1
      args[0] =~ /\A([A-Z]+)([0-9]+)\z/
      x, y = $~.captures
      super(x.ord - 'A'.ord, y.to_i - 1)
    when 2
      super(*args)
    end
  end
  
  def to_s
    "#{(x+'A'.ord).chr}#{y+1}"
  end
  alias :inspect :to_s
 
  [:+, :-].each { |m|
    define_method(m) { |c|
      Coord.new(x.send(m,c.x), y.send(m,c.y))
    }
  }
 
  def * n
    Coord.new(x*n, y*n)
  end
 
  def neighbours
    DIRECTIONS.map { |dir| self + dir }
  end
 
  def distance(c)
    Math.sqrt( (x-c.x)**2 + (y-c.y)**2 )
  end
 
  def in?(o)
    case o
    when Array
      o.include?(self)
    when Hash
      o.keys.include?(self)
    else
      raise
    end
  end
 
  def valid?(ary = [])
    if ary.empty?
      (0...SIDE) === x and (0...SIDE) === y
    else
      (0...SIDE) === x and (0...SIDE) === y and not in?(ary)
    end
  end
 
  # 1: 8
  # 2: 8*2
  # 3: 8*3
  FREESPACE_LEVELS = Array.new(SIDE) { |i|
    l = i+1
    c = (N+W)*l # NW
    [E, S, W, N].inject([]) { |lvl, dir|
      (l*2).times {
        lvl << c
        c += dir
      }
      lvl
    }
  }
  
  def freespace_around(shots)
    FREESPACE_LEVELS.inject(0.0) { |i, lvl|
      continue = true
      lvl.each { |add|
        c = self+add
        next unless c.valid?
        if !c.in?(shots)
          i += 1.0 / self.distance(c) * (FREESPACE_LEVELS.index(lvl)+1)
        else
          continue = false
        end
      }
      return i unless continue
      i
    }
  end
end
 
if __FILE__ == $0
  require "test/unit"
 
  class TestCoord < Test::Unit::TestCase
    def setup
      @a = Coord.new(0,0)
      @c = Coord.new(2,3)
    end
    
    def c(actual, expected)
      assert_equal expected, actual
    end
    
    def test_new
      c Coord.new("A1").to_a, [0,0]
      c Coord.new("J10").to_a, [9,9]
      c [@c.x, @c.y], [2,3]
    end
    
    def test_to_s
      c @c.to_s, "C4"
      c Coord.new("D5").to_s, "D5"
    end
    
    def test_in?
      assert @c.in? [@a,@c]
      assert !@c.in?([@a])
      assert @c.in?({@c=>false, @a => nil})
      assert !@c.in?({@a => true})
    end
    
    def test_valid?
      assert @c.valid?
      assert @c.valid? []
      assert !@c.valid?([@c])
      assert !Coord.new(10,9).valid?
    end
    
    def test_neighbours
      c @c.neighbours, [Coord.new(2,2), Coord.new(3,3), Coord.new(2,4), Coord.new(1,3)]
    end
    
    def test_freespace_around
      shooted = %w{B1 D1 B3 C2}.map { |s| Coord.new(s) }
      
      s = 1/Math.sqrt(2)
      
      assert_equal 2+2*s, Coord.new("E1").freespace_around(shooted)               # 4
      assert_equal 1+4*s, Coord.new("B2").freespace_around(shooted)               # 5
      assert_equal 11.406135888745856, Coord.new("F1").freespace_around(shooted)  # 13
      assert_equal 69.79675884855767, Coord.new("J10").freespace_around(shooted)  # 78
      assert_equal 4+3*s, Coord.new("D3").freespace_around(shooted)               # 7
    end
  end
end
 
=begin
+----+---+---+---+---+---+---+---+---+---+---+
|    | A | B | C | D | E | F | G | H | I | J |
+----+---+---+---+---+---+---+---+---+---+---+
| 1  |   | X |   | X |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 2  |   |   | X |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 3  |   | X |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 4  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 5  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 6  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 7  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 8  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 9  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 10 |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
=end

require File.expand_path('../coord', __FILE__)
 
class Array
  def other(than)
    find { |o| o != than }
  end
  
  def select_max_by
    best = map { |e| yield(e) }.max
    select { |e| yield(e) == best }
  end
  
  # 1.8 problems for Hash
  def keys
    map(&:first)
  end
  
  unless [].respond_to? :each_with_object
    def each_with_object(obj)
      self.each { |e|
        yield(e, obj)
      }
      obj
    end
  end
  
  unless [].respond_to? :sample
    def sample
      self[rand(size)]
    end
  end
end
 
class Player
  attr_reader :name, :shots, :fired
  
  NAME = /\w+/
  SIDE = 10
  ALL_COORDS = (SIDE**2).times.map { |i| Coord.new(i % SIDE, i / SIDE) }
 
  def initialize(name, ships = [5, 4, 3, 3, 2])
    @name = name
    @ships = ships
    @ships_cells = []
    @shots = []
    @fired = {}
    @sinking = []
  end
 
  def fire(coord, hit)
    @fired[Coord.new(coord)] = (hit.to_sym == :hit)
  end
 
  # Only for ourselves
  def place_ships
    ships = "SHIPS"
    @ships.each { |size|
      begin
        current_ship_cells = []
        if rand < 0.5 # Horizontal
          d = :H
          x = rand(SIDE-size)
          y = rand(SIDE)
        else # Vertical
          d = :V
          x = rand(SIDE)
          y = rand(SIDE-size)
        end
        size.times { |i| current_ship_cells << Coord.new( x + (d == :H ? i : 0), y + (d == :V ? i : 0) ) }
      end until (@ships_cells & current_ship_cells).empty?
 
      @ships_cells += current_ship_cells
      ships << " #{size}:#{Coord.new(x, y)}:#{d}"
    }
    ships
  end
  
  def shot!(n)
    targets = []
    @sinking = @fired.select { |c,r| r }.keys
    
    # 1 Sinking
    while hit = @sinking.pop
      targets += sink_that_ship!(hit)
      targets.uniq!
      if targets.length >= n
        targets = targets[0...n]
        break
      end
    end
    
    # 2 Secure perimeter
    if targets.length < n
      targets += shots_around_hits((n-targets.length)/2)
    end
    
    @shots += targets
    
    # 3 Try new locations
    while targets.length < n
      targets << shot
    end
    
    raise "We've got a problem: #{@fired.keys & shots}" if !(@fired.keys & targets).empty?
    
    "SHOTS #{targets.map(&:to_s).join(' ')}"
  end
  
  def shots_around_hits(n)
    @fired.select { |c, v|
      v
    }.keys.map { |c|
      Coord::DIRECTIONS.map { |d| c+d }
    }.flatten.uniq.select { |c|
      c.valid?(@fired)
    }.shuffle[0...n]
  end
  
  def find_same_dir(start, dir)
    Coord::DIRS[dir].each_with_object([start]) { |add, coords|
      c = start
      while c += add and c.valid? and @fired[c]
        coords << c
      end
    }
  end
  
  def sink_that_ship!(start)
    # Find shooted H and V
    dirs = {
      :h => find_same_dir(start, :h),
      :v => find_same_dir(start, :v)
    }
    dirs.each_value { |dir| @sinking -= dir }
    if dirs[:h].length == dirs[:v].length
      # We got only one coord, or there are as much tries in H & V. So we choose random dir
      dir = rand < 0.5 ? :h : :v
      shooted = dirs[dir]
    else
      # We know which direction is more interesting
      dir, shooted = dirs.max_by { |_,d| d.length }
    end
 
    coords = Coord::DIRS[dir].map { |add|
      shooted.map { |s| s+add }.find { |c|
        c.valid?(@fired)
      }
    }.compact.select { |c| c.valid?(@fired) }
    
    n_shoots = ((@ships.inject(:+) - @fired.count { |_,r| r }) / @ships.size + 0.5).to_i
    
    if coords.size == 1 # we know which way to go, let's shoot a max !
      way_to_go = coords.other(start)-start
    else # we go both side
      way_to_go = Coord::DIRS[dir].sample
    end
 
    n_shoots.times { |i|
      c = start + way_to_go*(i+1)
      if c.valid?(@fired)
        coords << c
      else
        break
      end
    }
 
    coords
  end
  
  def shot
    free = ALL_COORDS - @shots
    # free = free.shuffle[0..(free.size/2)] # To make it quicker ... but less accurate
    free.select_max_by { |c| c.freespace_around(@shots) }.sample.tap { |s| @shots << s }
  end
  
  def random_shot
    begin
      shot = Coord.new(rand(SIDE), rand(SIDE))
    end while shot.in?(ALL_COORDS - @shots)
    shot
  end
end
 
if __FILE__ == $0
  require "test/unit"
 
  class TestPlayer < Test::Unit::TestCase
    def setup
      @p = Player.new('test_player')
      
      @p.fire('B1', :miss)
      @p.fire('B3', :hit)
      @p.fire('C3', :hit)
    end
    
    def test_sink
      assert_equal [Coord.new('B3'), Coord.new('C3')], @p.find_same_dir(Coord.new('B3'), :h)
      assert_equal [Coord.new('B3')], @p.find_same_dir(Coord.new('B3'), :v)
    end
    
    def test_shot
      assert_equal "SHOTS A3 D3", @p.shot!(2)
      
      p = Player.new('test_player')
      p.fire('F6', :hit)
      r = p.shot!(2)
      assert ["SHOTS F5 F7", "SHOTS E6 G6"].include?(r), r
      
      p = Player.new('test_player2')
      p.fire('H2', :hit)
      p.fire('G2', :hit)
      p.fire('I2', :miss)
      expected = "SHOTS F2 E2"
      assert_equal expected, p.shot!(5)[0...expected.length]
    end
  end
end
 
=begin
+----+---+---+---+---+---+---+---+---+---+---+
|    | A | B | C | D | E | F | G | H | I | J |
+----+---+---+---+---+---+---+---+---+---+---+
| 1  |   | 0 |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 2  |   |   |   |   |< >|< >|<1>|<1>|<0>|   |
+----+---+---+---+---+---+---+---+---+---+---+
| 3  |< >|<1>|<1>|< >|   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 4  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 5  |   |   |   |   |   | ? |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 6  |   |   |   |   |<?>|<1>|<?>|   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 7  |   |   |   |   |   | ? |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 8  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 9  |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
| 10 |   |   |   |   |   |   |   |   |   |   |
+----+---+---+---+---+---+---+---+---+---+---+
=end

$stdout.sync = true
 
@name = File.basename(__FILE__, '.rb')
 
require File.expand_path('../../lib/eregon/player', __FILE__)
 
ARGF.each_line do |line|
  case line
 
  when /\AACTION SHIPS\b/
    # We have been asked to place our ships, so we send a valid response:
    ##puts "SHIPS 5:A1:H 4:A2:H 3:A3:H 3:A4:H 2:A5:H"
    puts @self.place_ships
 
  when /\AACTION SHOTS (\d)/
    shots = @self.shot!($1.to_i)
    puts shots
 
  when /\AACTION FINISH\b/
    # We don't save data, so we just need to tell the server we are done:
    puts "FINISH"
 
  when /\AINFO SETUP players:(#{Player::NAME}),(#{Player::NAME}) board:(?:\d+)x(?:\d+) ships:((?:[0-9]+,?)+)/
    n1,n2=$1,$2
    @ships = $3.split(',')
 
    p1 = Player.new(n1)
    p2 = Player.new(n2)
 
    @self, @opp = [p1,p2].partition { |p| p.name == @name }.map(&:first)
 
 
  when /\AINFO SHOTS (#{Player::NAME})((?: ?\w+\d+:(?:hit|miss))+)/
    player, shots = $1, $2.split(' ').map { |shot| shot.split(':') }
    shots.each do |shot|
      [@self, @opp].find { |p| p.name == player }.fire(*shot)
    end
 
  when /\AINFO WINNER (#{Player::NAME})/
    
  end
end