David Jones avatar David Jones committed cc9387e

adding files.

Comments (0)

Files changed (3)

+#!/usr/bin/env python
+# -*- py-indent-offset: 2; -*-
+# I know... it started as 2,  so I left it as 2.
+
+"""
+Bot for the Fall 2010 Google AI Challenge:  Planet Wars
+
+This bot would break with more than two players.
+"""
+
+
+import sys
+import logging
+import time
+import copy
+
+from logging import debug
+from PlanetWars import *
+from math import ceil, sqrt, hypot, log, exp
+
+class OutOfTime(Exception):
+  """Break from the logic when time runs out."""
+  pass
+
+def flip_planetwars(pw):
+  """Flip the values in the game state to change players."""
+  result = pw.copy()
+  for p in result.planets:
+    if p.owner > 0:
+      p.owner = 3 - p.owner
+  for f in result.fleets:
+    f.owner = 3 - f.owner
+  return result
+
+
+def sort_by_key(xs, key):
+  """Utility to sort a list of dicts by key"""
+  ys = [(x[key], x) for x in xs]
+  ys.sort()
+  return [y for (junk, y) in ys]
+
+def debug_list(name, xs):
+  """Debug utility"""
+  debug("looking at list: %s", name)
+  for i, x in enumerate(xs):
+    debug("%d : %s", i, x)
+
+def debug_int_list(name, xs):
+  """Debug utility"""  
+  debug("%s: %s", name, " ".join(["%3d" % x for x in xs]))
+  
+  
+def resolve(counts,owner):
+  """
+  Resolve a battle.
+
+  Counts is a list of incoming fleets [neutral, me, opponent].  owner
+  is the current owner.
+
+  Returns the new owner and resulting number of ships.
+  """
+  
+  if counts[0] < counts[1]:
+    a,b = 0,1
+  else:
+    a,b = 1,0
+  if counts[b] < counts[2]:
+    c = 2
+  elif counts[2] < counts[a]:
+    b,c = a,b
+  else:
+    b,c = 2,b
+  d = counts[c] - counts[b]
+  if d == 0:
+    return owner, 0
+  else:
+    return c, d
+
+
+def find_closest(pw, x, ys):
+  """
+  Find the closest planet in the list ys to the planet x.
+  Returns the planet id, and the distance.
+  """
+  if not ys: return None
+  ys = set(ys)
+  for (d,p) in pw.planets[x].neighbors:
+    if p in ys:
+      return p, d
+  return None
+
+
+def find_max_distance(pw,verbose=False):
+  """Find the maximum distance between any pair of planets."""
+  max_distance = 0
+  np = (len(pw.planets))
+  if verbose:
+    debug_int_list("dist  ", range(np))
+    for i in xrange(np):
+      debug_int_list("%3d   " % i, pw.planets[i].dists)
+      
+  for i in xrange(np):
+    for j in xrange(i+1,np):
+      d = pw.planets[i].dists[j]
+      if d > max_distance:
+        max_distance = d
+  return max_distance
+
+def make_empty_arrays(max_turn):
+  """Create a list of three lists of zeros.  Needed
+  for other functions."""
+  return ([0], [0] * max_turn, [0] * max_turn)
+
+
+def load_fleets(planets, fleets,max_turn):
+  result = [make_empty_arrays(max_turn) for p in planets]
+  for f in fleets:
+    if f.turns_remaining < max_turn:
+      result[f.destination_planet][f.owner][f.turns_remaining] += f.num_ships
+  return result
+
+def run_planet(planet, fleets):
+  turn = 0
+  i = 0
+  owner, ships, rate = planet.owner, planet.num_ships, planet.growth_rate
+
+  junk, mine, enemy = fleets
+  M = len(mine)
+  
+  result = [(0,owner,0)]
+
+  if owner > 0:
+    ships += fleets[owner][0]
+    ships -= fleets[3-owner][0]
+  for t in xrange(1,M):
+    result.append((t,owner,ships))
+    if owner > 0:
+      ships += rate
+      if t == M : break
+    counts = [0,mine[t] ,enemy[t]]
+    counts[owner] += ships
+    owner,ships = resolve(counts,owner)
+
+
+
+  return result
+
+def log_game_state(futures,fleets):
+  debug("looking at the future")
+  debug_int_list("     turn:", [x[0] for x in futures[0]])
+  for (idx,future) in enumerate(futures):
+    debug(" == planet %d == ", idx)
+    debug_int_list("    owner:", [x[1] for x in futures[idx]])
+    debug_int_list("     nums:", [x[2] for x in futures[idx]])
+    debug_int_list("my_fleets:", fleets[idx][1])
+    debug_int_list("en_fleets:", fleets[idx][2])      
+
+
+
+def find_available_conservative(future, rate, owner=1):
+  """find the number I can send without losing a planet
+  too quick."""
+  # don't mess with stuff that I don't own the whole time.
+  # debug("trying to find future: %s", future)
+  
+  # work backwards, and find the last time I don't own it.
+
+  if future[-1][1] != owner: return None
+  
+  for first_turn in xrange(len(future) - 1 , 0, -1):
+    if future[first_turn-1][1] != owner:
+      break
+  else:
+    first_turn = 0
+
+  tmp = [0 for x in future]  
+
+  t = 0
+  for i in xrange(len(future)-1,first_turn-1,-1):
+    t += (future[i][2] - future[i-1][2])
+    tmp[i] = max(t,0)
+    if t > 0:
+      t = 0
+
+  t += future[first_turn][2]
+  tmp[i] = max(t,0)      
+
+
+  # debug("tmp: %s", tmp)
+  return  tmp
+
+def update_available(available, futures, pw, owner=1):
+  for idx in xrange(len(pw.planets)):
+    if available[idx] is None: continue
+    for n in available:
+      if n > 0:
+        break
+    else:
+      # never anything to do here
+      continue
+    av = available[idx]
+    closest_en = len(av)
+    # find the quickest an enemy can get here.
+    for (d,n) in pw.planets[idx].neighbors:
+      if d >= closest_en: break
+      if n == idx: continue
+
+      fut = futures[n]
+      for i in xrange(1,len(fut)):
+        if fut[1] > 0 and fut[1] != owner:
+          tmp = i + d - 1
+          if tmp < closest_en:
+            closest_en = tmp
+      
+    for i in xrange(closest_en, len(av)):
+      av[i] = 0
+      
+
+def find_number_on_aggressive(pw, futures, idx, owner):
+  max_turn = len(futures[1])
+  res = [0] * max_turn
+  
+  np = len(futures)
+  dst = idx
+  for (dist, src) in pw.planets[idx].neighbors:
+    future = futures[src]
+    if src == dst: continue
+    best = 0
+    for t in xrange(1,max_turn-dist):
+      junk,o,n = future[t]
+      if o == owner and n > best:
+        best = n
+      res[t+dist-1] += best
+  return res
+
+def find_number_on_available(pw, available, idx, max_turn,srcs=None):
+  np = len(pw.planets)
+  if srcs is None:
+    srcs = [n for n in xrange(np)]
+    
+  res = [0] * max_turn
+
+  dst = idx
+  for (dist, src) in pw.planets[idx].neighbors:
+    if src == dst: continue
+    av = available[src]
+    if av is None: continue
+    dist = pw.planets[src].dists[dst]
+    for t in xrange(1,max_turn-dist):
+      res[t+dist-1] += av[t]
+
+  for i in xrange(1,len(res)):
+    res[i] += res[i-1]
+  # debug_int_list("    turn:", range(len(result[1])))
+  # debug_int_list("my_on[1]:", result[1])
+  return res
+
+
+
+class Analysis:
+  def __init__(self, pw=None,first_turn=None, max_turn=None, end_time=None):
+
+    if pw is None:
+      pass
+    else:
+      self.pw = pw
+      self.end_time = end_time
+      self.max_turn = max_turn
+      if self.max_turn is None:
+        self.max_turn = find_max_distance(pw,first_turn) + 2
+
+      self.pidx = xrange(len(pw.planets))
+
+      self.reserved = [[0] * self.max_turn for p in self.pidx]
+      self.shots = []
+      self.orders = []
+
+      
+  def log_planet_state(self, idx, show=False):
+    if show:
+      future= self.futures[idx]
+      fleet = self.fleets[idx]
+
+      my_on = self.get_my_on(idx)
+      en_on = self.get_en_on(idx)
+      debug("status for planet: %d", idx)
+      debug_int_list("     turn:", [x[0] for x in future])
+      debug_int_list("    owner:", [x[1] for x in future])
+      debug_int_list("     nums:", [x[2] for x in future])
+      debug_int_list("my_fleets:", fleet[1])
+      debug_int_list("en_fleets:", fleet[2])
+      debug_int_list("    my_on:", my_on)
+      debug_int_list("    en_on:", en_on)
+
+
+  def get_end_rates(self):
+    counts = [0,0,0]
+    tmp = [(fut[-1][1], fut[-1][2], i, self.pw.planets[i].growth_rate)
+           for (i,fut) in enumerate(self.futures)
+           if fut[-1][1] > 0]
+
+    # for (xxxx,xxx,i, xx) in tmp:
+    #   self.log_planet_state(i, True)
+      
+    debug("in score_end_count: %s", tmp)
+    rates = [0, 0, 0]
+    for owner, ships, planet, rate  in tmp:
+      rates[owner] += rate
+      counts[owner] += ships
+    return counts, rates
+      
+    
+  def find_closest_distance(self):
+    """Update information about the distance between the players
+    must be called after futures is calculated.
+    """
+
+    # find the closet from me to the enemy
+    mine = [idx for idx in self.pidx if self.futures[idx][-1][1] == 1]
+    enemy = set(idx for idx in self.pidx if self.futures[idx][-1][1] == 2)
+
+    if not mine or not enemy:
+      self.closest_distance = -1
+      return
+
+    best_d = self.max_turn + 10
+    for m in mine:
+      for (d, n) in self.pw.planets[m].neighbors:
+        if d >= best_d: break
+        if n in enemy:
+          self.best_pair = (m, n)
+          best_d = d
+    self.closest_distance = best_d
+    
+        
+      
+    
+  def update_state(self):
+    if time.time() > self.end_time:
+      raise OutOfTime()
+    pw = self.pw
+    self.fleets = load_fleets(pw.planets, pw.fleets, self.max_turn)
+    self.futures = [run_planet(self.pw.planets[i], self.fleets[i])
+                    for i in self.pidx]
+    self.find_closest_distance()
+    
+    self.my_available = [find_available_conservative(self.futures[idx],
+                                                     self.pw.planets[idx].growth_rate)
+                         for idx in self.pidx]
+
+    self.en_available = [find_available_conservative(self.futures[idx],
+                                                     self.pw.planets[idx].growth_rate, 2)
+                         for idx in self.pidx]
+
+
+    # update_available(self.my_available, self.futures, self.pw, owner=1)
+    # update_available(self.my_available, self.futures, self.pw, owner=2)    
+    
+
+  def score_growth(self):
+    values = [(self.futures[i][-1][1], self.pw.planets[i].growth_rate)
+              for i in self.pidx]
+    values = [(x,y) for (x,y) in values if x > 0]
+    
+    debug("score: values %s", values)
+
+    counts = [0,0,0]
+    for (x,y) in values:
+      counts[x] += y
+    
+    return [counts[1] - counts[2], -counts[2]]
+
+  def score_end_count(self):
+    counts, rates = self.get_end_rates()
+    if self.closest_distance < 1:
+      rate_mult = 0
+    else:
+      rate_mult = 5 + 2 * self.closest_distance
+
+    if counts[1] == 0:
+      score = -9999999
+    elif counts[2] == 0:
+      score =  9999999
+    else:
+      score = (counts[1] - counts[2]) + rate_mult * (rates[1] - rates[2])
+
+    debug("rate_mult: %s, counts: %s, rates: %s, score: %s",
+          rate_mult, counts, rates, score)
+    
+    # return [score, -counts[2]]    
+    if score > 0:
+      return [score, -counts[2]]
+    else:
+      return [score, counts[2]]
+
+  def score(self):
+    return self.score_end_count()
+    # return self.score_exponential()
+  
+
+  def do_turn(self, end_time):
+    self.update_state()
+    for k in xrange(20):
+      prev_time = time.time()
+      target = self.make_decision()
+      debug("loop time was : %s", time.time() - prev_time)
+      if time.time() > end_time:
+        break
+      if target is None:  break
+      
+    for (src,dst,num) in self.shots:
+      debug("firing %d %d %d", src, dst, num)
+      self.pw.IssueOrder(src,dst,num)
+    
+  def get_my_on(self, idx, srcs=None):
+    return find_number_on_available(self.pw, self.my_available, idx, self.max_turn,
+                                    srcs)
+  def get_en_on(self, idx):
+    return find_number_on_available(self.pw, self.en_available, idx,
+                                    self.max_turn, None)
+                           
+
+  def find_neutrals(self, neutrals):
+    result = []
+    for idx in neutrals:
+      debug("looking at neutral: %d", idx)
+      rate = self.pw.planets[idx].growth_rate
+
+      if rate < 1: continue
+
+      fleets = self.fleets[idx]
+      future = self.futures[idx]
+      my_on = self.get_my_on(idx)
+      en_on = self.get_en_on(idx)
+
+      
+      self.log_planet_state(idx, False)
+      
+      # BUG HERE ... sometimes takes neutrals too early.
+
+      for my_t in xrange(1,self.max_turn-1):
+        if fleets[2][my_t] > 0: continue
+        if my_on[my_t] > future[my_t+1][2]:
+          needed = future[my_t+1][2]
+          num = needed + 1 # TODO:  account for sending more! my_on[my_t]
+          break
+      else:
+        # cannot take.  pass
+        continue
+
+      for en_t in xrange(my_t):
+        if en_on[en_t] > 0:
+          en_t = -1000
+          break
+      else:
+        for en_t in xrange(my_t,self.max_turn):
+          if en_on[en_t] > (en_t - my_t) * rate + 1:
+            break
+
+      cost = num + (my_t - en_t) * rate
+
+      first_turn = 0
+      for t in xrange(self.max_turn):
+        if fleets[2][t] > 0:
+          first_turn = t
+          
+      if cost < 0:
+        # Easy neutral.  I can take it and earn the growth
+        # before the enemy can reach it.
+        result.append({"planet": idx,
+                       "first_turn": my_t,
+                       "target_turn": my_t,
+                       "num": num,
+                       "cost": cost,
+                       "rate": rate})
+      else:
+        # harder neutral.  time to think through this a little more.
+        for earliest_enemy_landing in xrange(self.max_turn):
+          if en_on[earliest_enemy_landing] > 0:
+            break
+
+        # Maybe only look at things we can beat the enemy to by
+        # sum number of moves?
+        take_limit = 5
+
+        
+        delay =  max(int(ceil(1.0 * needed / rate)), 1)
+        # debug("delay is %d, needed %d, rate %d", delay, needed, rate)
+        cost = 9e99
+        for i in xrange(1, take_limit+1):
+          if my_t + i >= self.max_turn:
+            break
+          if i > 1:
+            extra = my_on[my_t+i-1] - num
+          else:
+            extra = 1
+          diff = extra + rate  * i - en_on[my_t + i]
+          if diff < 0:
+            debug("enemy can stop us at turn %d", my_t + i)
+            break
+
+        else:
+          debug("hard neutral: my_t: %d, diff: %d, take_turn %d, delay: %d, rate:%d",
+                my_t, diff, my_t + i, delay, rate)
+
+          result.append({"planet": idx,
+                         "first_turn": my_t,
+                         "target_turn": my_t,
+                         "num": num,
+                         # max(num, num + en_on[en_t] - (en_t - my_t)*rate ), # num
+                         "rate": rate})
+          debug(result[-1])
+    return result
+
+  def find_defend_at_last_moment(self, mine):
+    result = []
+    if not mine:
+      return result
+
+    for idx in mine:
+      t = self.run_defend(idx)
+      if t:  result.append(t)
+    return result
+
+
+  def find_enemies(self, enemies, offset=0,all_in=True):
+    result = []
+    if not enemies:
+      return []
+    srcs = dict([(en, None) for en in enemies])
+    
+    if not all_in:
+      mine = [p for p in self.pidx
+              if self.futures[p][-1][1] == 1 or
+              self.futures[p][1][1] == 1]
+
+      debug("mine: %s", mine)
+      debug("enemies: %s", enemies)
+
+      tmp = [(m,find_closest(self.pw, m, enemies)) for m in mine]
+      tmp = [(m, d) for (m, (junk,d)) in tmp]
+      closest = dict(tmp)
+      debug("closest: %s", closest)
+      for idx in enemies:
+        srcs[idx] = [m for m in mine
+                     if self.pw.planets[m].dists[idx] < closest[m] + 5]
+      
+    for idx in enemies:
+      t = self.run_enemy(idx,offset,srcs[idx])
+      if t:
+        result.append(t)
+        debug(t)
+    return result
+    
+
+  def run_enemy(self, idx, offset, srcs):
+    debug("looking at enemy: %d", idx)
+    rate = self.pw.planets[idx].growth_rate
+    fleets = self.fleets[idx]
+    future = self.futures[idx]
+    my_on = self.get_my_on(idx, srcs)
+    en_on = self.get_en_on(idx)
+
+    # SUBMIT_CHECK
+    self.log_planet_state(idx, True)
+
+    for turn in xrange(1, self.max_turn-1):
+      # don't consider when the enemy doesn't own it.
+      if future[turn+1][1] != 2: continue
+
+      # assume they delay a turn to fire.
+      # we will deal with possible launches later.
+
+      if turn < offset: continue
+      # if offset > -1:
+      needed = en_on[turn - offset]
+      # else:
+      #   needed = 0
+          
+      fut = future[turn+1]
+      if fut[1] == 2:
+        needed += fut[2] + 1
+      else:
+        needed -= fut[2]
+
+      if needed <= 0:
+        continue
+
+      if my_on[turn] < needed: continue
+      
+      dist = turn
+      while my_on[dist-1] >= needed:
+        dist -= 1
+
+
+        
+      if my_on[dist] >= needed:
+        # find the first turn to strike
+        first_turn = turn
+        # First turn is
+        #  - never when the planet is neutral
+        #  - the first time I own it
+        #  - else when I can take it.
+        for first_turn in xrange(1, turn):
+          if future[first_turn][1] == 1:
+            break
+        
+        return {"planet": idx,
+                "first_turn": first_turn,
+                "target_turn":turn, 
+                "dist": dist,
+                "num": needed,
+                "rate": rate}
+    return None
+
+  def fire(self, target):
+    debug("trying to attack: %s", target)
+    
+    dists = [(d,p) for (d,p) in self.pw.planets[target["planet"]].neighbors
+             if self.my_available[p]]
+    if True:
+      for (d, p) in dists:
+        debug("planet: %d, distance: %d, av: %s", p, d, self.my_available[p])
+
+
+        
+    num = target["num"]
+    first_turn = target["first_turn"]
+    target_turn = target["target_turn"]
+    dst = target["planet"]
+    debug("dists: %s", dists)
+
+    do_debug = False
+
+    for (d,src) in dists:
+      if d  > target_turn:
+        debug("%d is too far", src)
+        break
+      if num <= 0: break
+      
+      av = self.my_available[src]
+      if not av:
+        # debug("HERE %d %s",src, self.my_available)
+        continue
+      
+      for i in xrange(1,self.max_turn):
+        if (i - 1) + d > target_turn:
+          break
+        n = min(av[i], num)
+        if n > 0:
+          # put a negative fleet arriving the turn this one would take off.
+          debug("moving %d ships on %d at turn %d to a future landing on %d at turn %d",
+                n, src, i, dst, target_turn)
+          
+          arrive = max(i+d-1, first_turn)
+          self.orders.append((i, src, dst, n, d, first_turn))
+          self.pw.fleets.append(Fleet(1,-n,src,src,i-1,i-1))
+          self.pw.fleets.append(Fleet(1,n,src,dst,arrive, arrive)) 
+          num -= n          
+          do_debug = True
+      if do_debug:
+        debug("after launching from %s, num is %d", src, num)
+    if num > 0:
+      self.shots = None
+      
+    # if do_debug:
+    #   debug_list("fleets", self.pw.fleets)
+
+  def update_available(self):
+    for p in self.pidx:
+      if self.available[p] == None: continue
+      for en_turn in xrange(self.max_turn):
+        if en_on[en_turn] > 0: break
+    
+  def move_forward(self):
+    futures = self.futures
+    srcs = [i for i in self.pidx
+            if futures[i][-1][1] == 1]
+
+    enemies = [i for i in self.pidx
+               if futures[i][-1][1] == 2]
+
+    if not srcs or not enemies: return None
+
+    debug("scrs: %s, enemies: %s", srcs, enemies)
+    my_locations = set([])
+    for en in enemies:
+      my,junk = find_closest(self.pw, en, srcs)
+      debug("closest to %d is %d at dist %d", en, my, junk)
+      my_locations.add(my)
+
+    en_dists = {}
+    for m in self.pidx:
+      junk, d = find_closest(self.pw, m, enemies)
+      en_dists[m] = d
+      
+    debug("my_locations: %s", my_locations)
+    self.shots = []
+    for src in self.pidx:
+      if self.pw.planets[src].owner != 1: continue
+      if src in my_locations: continue
+      dest, dist= find_closest(self.pw, src, list(my_locations))
+      debug("closest from my_locations: %d, dist: %d", dest, dist)
+
+      if dist >= en_dists[dest] or dist <= en_dists[src] / 2:
+        debug("closest to %d:  %d (dist: %d", src, dest, dist)
+        debug("try moving from %d to %d", src, dest)
+        av = self.my_available[src]
+        if av and av[1]:
+          self.shots.append((src, dest, av[1]))
+        
+        # if av and av[1]:
+        #   self.launch(src,dest,av[1])
+
+  def get_planets_for_player(self, player):
+    """Find all planets a player owns at the end of futures."""
+    return [p for p in self.pidx if self.futures[p][-1][1] == player]
+
+  def make_decision(self, ignored=None, offset=0, take_neutrals=True):
+    if ignored is None:
+      targets = list(self.pidx)
+    else:
+      targets = [x for x in self.pidx if x not in ignored]
+    
+    # defend what I can
+    # protect what I can
+    # attack enemy planets
+    # move forward
+    # self.shots = []
+    self.update_state()
+    # defend planets I own
+
+    #
+    # Attack enemy planets
+    #
+
+    enemies = self.find_enemies([i for i in targets if self.futures[i][-1][1] > 1],
+                                offset, False)
+
+    # enemies = [x for x in enemies if x["target_turn"] < self.max_turn / 2 + 2]
+    
+    for x in enemies:
+      # x["best_est"] = - 2*x["rate"] * (self.max_turn - x["target_turn"]) + x["num"]
+      x["best_est"] = x["target_turn"] + x["num"] / (2*x["rate"]  + 0.01)
+
+    debug_list("enemies", enemies)
+    all_targets = list(enemies)
+    
+
+    if take_neutrals:
+      neutrals = self.find_neutrals([i for i in targets
+                                     if self.futures[i][-1][1] == 0])
+
+      # neutrals = [x for x in neutrals if x["target_turn"] < self.max_turn / 2 + 2]
+      for x in neutrals:
+        x["best_est"] = x["target_turn"] + x["num"] / (x["rate"]  + 0.01)      
+        # x["best_est"] = - x["rate"] * (self.max_turn - x["target_turn"]) + x["num"]
+
+      debug_list("neutrals", neutrals)
+
+      all_targets.extend(neutrals)
+
+    all_targets = sort_by_key(all_targets, "best_est")
+    debug_list("all_targets", all_targets)
+
+    if all_targets:
+      self.fire(all_targets[0])
+      return all_targets[0]["planet"]
+
+    # should we need this here?  I don't think so...
+    # self.move_forward()
+
+    return None
+
+def neg(xs):
+  return [-x for x in xs]
+
+class Bot1Ply:
+  def __init__(self, pw, end_time):
+    self.pw = pw
+    self.end_time = end_time
+    self.ignored = set()
+    self.logger = logging.getLogger("1ply")
+    
+  def enemy_move(self, pw, beta, limit=20):
+    end_time = self.end_time
+    best_score = [-9e99,-9e99]
+    ignored = set()
+    logger = self.logger
+    logger.debug("in enemy move, beta=%s", beta)
+    state = Analysis(pw,False, end_time=end_time)
+    state.update_state()
+    best_score = state.score()
+    logger.debug("score for enemy doing nothing: %s", best_score)
+    
+    for kk in xrange(limit):
+      target = state.make_decision(ignored)
+      state.update_state()
+      score = state.score()
+      logger.debug("en_move: looking at target: %s, score is %s", target, score)
+      if score >= best_score:
+        # this move was good.  keep it, and
+        # update the pw state
+        logger.debug("en_move: new best score.")
+        best_score = score
+        pw = state.pw
+      else:
+      # elif state.shots is None:
+        logger.debug("en_move: not using that shot...")
+        # this move was bad.  move on.
+        ignored.add(target)
+      if best_score > beta:
+        logger.debug("en_move: exceeded beta.  leaving now.")
+        # beta how much i can get.  once this os over, quit.
+        return state, best_score
+      if target is None:
+        break
+
+      if kk < limit - 1:
+        state = Analysis(pw,False, end_time=end_time)
+        state.update_state()
+
+    return state, best_score
+
+  def fire_orders(self, state, orders):
+    """Actually fire the orders.  also... move them around better."""
+    logger = self.logger
+    # Figure out which planets are always mine.  We are
+    # going to use them as way points.
+
+    mine = []
+    for idx in state.pidx:
+      is_mine = False
+      for (junk, owner, junk2) in state.futures[idx]:
+        if owner == 2: break
+        if owner == 1: is_mine = True
+      else:
+        if is_mine:
+          mine.append(idx)          
+    debug("planets that are always mine: %s", mine)
+
+    for (turn, src, dst, num, dist, first_turn) in orders:
+      if turn == 1 and dist >= first_turn:
+        logger.debug("ACTUAL FIRING (AA) s:%d d:%d n:%d", src, dst, num)
+        state.pw.IssueOrder(src,dst,num)
+      elif turn == 1:
+        # try to hop the shot...
+        # find another of my planets, closer to dst than src,
+        # such that i can hop to the middle planet, and still
+        # get where I need to be at first_turn.
+        planet = state.pw.planets[dst]
+        best_d, best_m = None, None
+        for m in mine:
+          if m == src: continue
+          if planet.dists[m] >= planet.dists[src]: continue
+          tmp = state.pw.planets[m]
+          d = tmp.dists[src] + tmp.dists[dst]
+
+          if d > first_turn: continue
+          
+          if best_d is None or d < best_d:
+            best_d, best_m = d, m
+        if best_d is not None:
+          logger.debug("firing from %s to %s via %s", src, dst, best_m)
+          state.pw.IssueOrder(src, best_m, num)
+
+  def go(self, first_turn=False):
+    end_time = self.end_time
+    # upper bound on best move.
+    beta = [9e99, 9e99]
+    best_score = [-9e99, -9e99]
+    ignored = set()
+    pw = self.pw
+    logger = self.logger
+
+    logger.debug("in bot1ply.go.")
+    a = Analysis(pw, first_turn, end_time=end_time)
+    a.update_state()    
+    state, best_score = self.enemy_move(flip_planetwars(pw), neg(best_score))
+    best_score = neg(best_score)
+    logger.debug("score of doing nothing: %s", best_score)
+
+    try:
+      for kk in xrange(20):
+        pw_copy = pw.copy()
+        state = Analysis(pw_copy, False, end_time=end_time)
+        logger.debug("searching for a move")
+
+        # state.update_state()
+        # counts, rates = state.get_end_rates()
+        # logger.debug("foobar counts: %s, rates: %s", counts, rates)
+        # target = state.make_decision(ignored, take_neutrals=(counts[1] < counts[2]))
+
+        target = state.make_decision(ignored, take_neutrals=(best_score[0] < -1))
+
+        logger.debug("foobar found move, target:%s, orders: %s", target, state.orders)
+
+
+
+        new_state, score = self.enemy_move(flip_planetwars(state.pw), neg(best_score))
+        score = neg(score)
+        logger.debug("MINE: target: %s score: %s  (Best: %s)", target, score, best_score)
+
+
+        if score >= best_score: # and state.orders is not None:
+          logger.debug("got a new best score: %s  (old %s)", score, best_score)
+          logger.debug("making moves")
+          logger.debug("state.orders: %s", state.orders)
+          best_score = score
+          self.fire_orders(state, state.orders)
+          # for (turn, src, dst, num, dist, first_turn) in state.orders:
+          #   if turn == 1 and dist >= first_turn:
+          #     logger.debug("ACTUAL FIRING (AA) s:%d d:%d n:%d", src, dst, num)
+          #     pw.IssueOrder(src,dst,num)
+          pw = state.pw
+        else:
+          logger.debug("ignoring target: %s", target)
+          ignored.add(target)
+        if target is None:
+          break
+
+    except OutOfTime:
+      debug("ran out of time.")
+    state = Analysis(pw, False, end_time=end_time)
+    state.update_state()
+    state.move_forward()
+    for (src,dst,num) in state.shots:
+      logger.debug("ACTUAL FIRING s:%d d:%d n:%d", src, dst, num)
+      pw.IssueOrder(src,dst,num)
+        
+
+def main_do_turn(map_data, turn, end_time):
+  start_time = time.time()
+
+  pw = PlanetWars(map_data)
+
+  if False and turn == 1:
+    weights = create_weights(pw)
+    output = ["{x: %f, y: %f, idx: %d, rate: %d, weight: %.1f}" %
+              (p.x, p.y, p.planet_id, p.growth_rate, weights[i])
+              for (i,p) in enumerate(pw.planets)]
+    debug("weights: \n[%s]", ",\n".join(output))
+
+  # if turn == 1:
+  # find_max_distance(pw, True)
+
+  counts = [0,0,0]
+  rates = [0,0,0]
+  for p in pw.planets:
+    counts[p.owner] += p.num_ships
+    rates[p.owner] += p.growth_rate
+  for f in pw.fleets:
+    counts[f.owner] += f.num_ships
+
+  if turn % 5 == -1:          
+    logging.info("turn number: %d", turn)
+    logging.info("player 1: %d/%d", counts[1], rates[1])
+    logging.info("player 2: %d/%d", counts[2], rates[2])
+  else:
+    logging.debug("aaa turn number: %d", turn)
+    logging.debug("aaa player 1: %d/%d", counts[1], rates[1])
+    logging.debug("aaa player 2: %d/%d", counts[2], rates[2])            
+
+  try:
+    # bot = BotAlphaBeta(pw, end_time)
+    bot = Bot1Ply(pw, end_time)
+    #bot = BotEnFirst(pw, end_time)        
+    bot.go(turn==1)
+  except OutOfTime:
+    debug("caught out of time")
+    pass
+
+  pw.FinishTurn()
+  end_time = time.time()
+  logging.debug("finished with turn... took %f seconds awaiting data",
+                end_time - start_time)
+
+
+import sys
+
+    
+def main(turn_time=0.8):
+  """
+  Collect the input data and run the bot.
+  """
+  
+  turn = 0
+  while(True):
+    map_data = []
+    turn += 1
+    while True:
+      current_line = raw_input()
+      if len(current_line) >= 2 and current_line.startswith("go"):
+        start_time = time.time()
+        end_time = start_time + turn_time
+        s = "\n".join(map_data)
+        logging.debug("turn %d\n%s\ngo\n", turn, s)
+        main_do_turn(map_data, turn, end_time)
+        
+        break
+      
+      else:
+        map_data.append(current_line)
+
+if __name__ == '__main__':
+  try:
+    import psyco
+    # SUBMIT_CHECK
+    psyco.full()
+    pass
+  except ImportError:
+    pass
+  try:
+    argv = sys.argv[1:]
+    # SUBMIT_CHECK
+    turn_time = 0.8
+    if len(argv) > 0:
+      # TURNFUDGE = 1
+      logging.basicConfig(filename=argv[0],
+                          level=logging.DEBUG,
+                          filemode="w")
+      logger = logging.getLogger()
+      ch = logging.StreamHandler()
+      ch.setLevel(logging.INFO)
+      logger.addHandler(ch)
+      debug("starting logging")
+      if len(argv) > 1:
+        turn_time = float(argv[1])
+    main(turn_time)
+  except KeyboardInterrupt:
+    print 'ctrl-c, leaving ...'
+  except EOFError:
+    logging.debug("end of input")
+  except:
+    logging.exception('Crash')
+    
+
+
+#!/usr/bin/env python
+
+
+"""
+Updated version of the starter kit code.  Added some
+functionallity, and teaked it.
+"""
+
+
+from math import ceil, sqrt
+from sys import stdout
+import copy
+
+import logging
+
+class Fleet:
+  def __init__(self, owner, num_ships, source_planet, destination_planet, \
+   total_trip_length, turns_remaining):
+    self.owner = owner
+    self.num_ships = num_ships
+    self.source_planet = source_planet
+    self.total_trip_length = total_trip_length
+    self.turns_remaining = turns_remaining
+    self.destination_planet = destination_planet
+
+  def __repr__(self):
+    return "F (o:%d, n:%d, s:%d, d: %d, t:%d, r:%d)" % (
+      self.owner, self.num_ships, self.source_planet,
+      self.destination_planet, self.total_trip_length,
+      self.turns_remaining)
+
+  def __lt__(self,other):
+    return self.turns_remaining < other.turns_remaining
+  def __eq__(self,other):
+    return self.turns_remaining == other.turns_remaining
+  def __gt__(self,other):
+    return self.turns_remaining > other.turns_remaining    
+  
+class Planet:
+  def __init__(self, planet_id, owner, num_ships, growth_rate, x, y):
+    self.planet_id = planet_id
+    self.owner = owner
+    self.num_ships = num_ships
+    self.growth_rate = growth_rate
+    self.x = x
+    self.y = y
+    self.neighbors = []
+    self.dists = []
+  def copy(self):
+    result = Planet(self.planet_id, self.owner, self.num_ships,
+                    self.growth_rate, self.x, self.y)
+    result.neighbors = self.neighbors
+    result.dists = self.dists
+    return result
+  def __repr__(self):
+    return "id: %d, owner: %d, ships: %d, growth: %d" % (self.planet_id,
+                                                         self.owner,
+                                                         self.num_ships,
+                                                         self.growth_rate)
+def sortFleetsByTime(fleets):
+  tmp = [(f.turns_remaining, f) for f in fleets]
+  tmp.sort()
+  return [f for (junk,f) in tmp]
+
+
+class PlanetWars:
+  def __init__(self, gameState=None):
+    self.planets = []
+    self.fleets = []
+    if gameState is not None:
+      r = self.ParseGameState(gameState)
+      if r != 1:
+        logging.debug("error parsing game state")
+      pidx = xrange(len(self.planets))
+      for i in pidx:
+        # stole this from bocsimacko's lisp starter kit.
+        dists = [self.Distance(i,j) for j in pidx]
+        self.planets[i].dists = dists
+        neighbors = zip(dists, pidx)
+        neighbors.sort()
+        self.planets[i].neighbors = neighbors
+      
+  def copy(self):
+    result = PlanetWars()
+    result.planets = [p.copy() for p in self.planets]
+    result.fleets = copy.deepcopy(self.fleets)
+    return result
+  
+    
+  def MyPlanets(self):
+    return [p for p in self.planets if p.owner == 1]
+
+  def NeutralPlanets(self):
+    return [p for p in self.planets if p.owner == 0]
+
+  def EnemyPlanets(self):
+    return [p for p in self.planets if p.owner == 2]
+
+  def NotMyPlanets(self):
+    return [p for p in self.planets if p.owner != 1]
+
+  def MyFleets(self):
+    return [p for p in self.fleets if p.owner == 1]    
+
+  def EnemyFleets(self):
+    return [p for p in self.fleets if p.owner == 2]        
+
+  def __repr__(self):
+    s = ''
+    for p in self.planets:
+      s += "P %f %f %d %d %d\n" % \
+       (p.x, p.y, p.owner, p.num_ships, p.growth_rate)
+    for f in self.fleets:
+      s += "F %d %d %d %d %d %d\n" % \
+       (f.owner, f.num_ships, f.source_planet, f.destination_planet, \
+        f.total_trip_length, f.turns_remaining)
+    return s
+
+  def Distance(self, source_planet, destination_planet):
+    source = self.planets[source_planet]
+    destination = self.planets[destination_planet]
+    dx = source.x - destination.x
+    dy = source.y - destination.y
+    return int(ceil(sqrt(dx * dx + dy * dy)))
+
+  def IssueOrder(self, source_planet, destination_planet, num_ships):
+    stdout.write("%d %d %d\n" % \
+     (source_planet, destination_planet, num_ships))
+    stdout.flush()
+
+  def IsAlive(self, player_id):
+    for p in self.planets:
+      if p.Owner() == player_id:
+        return True
+    for f in self.fleets:
+      if f.owner == player_id:
+        return True
+    return False
+
+  def ParseGameState(self, lines):
+    planets = []
+    fleets = []
+    
+    planet_id = 0
+
+    for line in lines:
+      line = line.split("#")[0] # remove comments
+      tokens = line.split(" ")
+      if len(tokens) == 1:
+        continue
+      if tokens[0] == "P":
+        if len(tokens) != 6:
+          return 0
+        p = Planet(planet_id, # The ID of this planet
+                   int(tokens[3]), # Owner
+                   int(tokens[4]), # Num ships
+                   int(tokens[5]), # Growth rate
+                   float(tokens[1]), # X
+                   float(tokens[2])) # Y
+        planet_id += 1
+        planets.append(p)
+      elif tokens[0] == "F":
+        if len(tokens) != 7:
+          return 0
+        f = Fleet(int(tokens[1]), # Owner
+                  int(tokens[2]), # Num ships
+                  int(tokens[3]), # Source
+                  int(tokens[4]), # Destination
+                  int(tokens[5]), # Total trip length
+                  int(tokens[6])) # Turns remaining
+        fleets.append(f)
+      else:
+        return 0
+    logging.debug("fleets: %s", fleets)
+
+    self.fleets = sortFleetsByTime(fleets)
+    self.planets = planets
+    return 1
+
+  def FinishTurn(self):
+    stdout.write("go\n")
+    stdout.flush()
+"""
+example of how i ran my bot in pdb.
+"""
+
+
+import MyBot
+import time
+import logging
+import pdb
+import sys
+
+def go(filename):
+    s = open(filename).readlines()
+    logging.basicConfig(filename="bot.log",
+                        level=logging.DEBUG,
+                        filemode="w")
+
+    logging.debug('test')
+    MyBot.main_do_turn(s, 1, time.time() + 9e99)
+
+pdb.run('go("state.txt")')
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.