sim.py

# spacegoo game engine tweaked to allow future predictions on the game client
from copy import deepcopy
from math import ceil, sqrt

def distance(self, other):
    xdiff = self.x-other.x
    ydiff = self.y-other.y
    return int(ceil(sqrt(xdiff*xdiff + ydiff*ydiff)))

def combine_fleets(fleet1, fleet2):
    fleet1.ships = map(lambda f1,f2: f1+f2, fleet1.ships, fleet2.ships)

def battle_round(attacker,defender):
    #nur eine asymmetrische runde. das hier muss mal also zweimal aufrufen.
    numships = len(attacker)
    defender = defender[::]
    for def_type in range(0,numships):
        for att_type in range(0,numships):
            multiplier = 0.1
            absolute = 1
            if (def_type-att_type)%numships == 1:
                multiplier = 0.25
                absolute = 2
            if (def_type-att_type)%numships == numships-1:
                multiplier = 0.01
            defender[def_type] -= (attacker[att_type]*multiplier) + (attacker[att_type] > 0) * absolute
        defender[def_type] = max(0,defender[def_type])
    return defender

def battle(s1,s2):
    ships1 = s1[::]
    ships2 = s2[::]
    while sum(ships1) > 0 and sum(ships2) >0:
        new1 = battle_round(ships2,ships1)
        ships2 = battle_round(ships1,ships2)
        ships1 = new1
        
    ships1 = map(int,ships1)
    ships2 = map(int,ships2)
    return ships1, ships2

def win(s1,s2):
    n1,n2 = battle(s1,s2)
    return sum(n1) > 0 and sum(n2)==0

def fleet_land(state, self):
    global planet_map
    target = planet_map[self.target]
    # print "fleet landing"
    if target.owner_id == self.owner_id:
        target.ships = map(lambda infleet,onplanet: infleet+onplanet, self.ships,target.ships)
    else:
        #battle!
        attacker,defender = battle(self.ships,target.ships)
        if sum(defender) > 0:
            target.ships = defender
        else:
            target.ships = attacker
            target.owner_id = self.owner_id

def calc_next_enemy(state):
    own_id = state.player_id
    other_id = state.other_id
    for p in state.planets:
        p.nearest_enemy = None

    for p0 in state.planets:
        nearest_dist = 1000000
        if p0.nearest_enemy != None:
            nearest_dist = distance(p0, p0.nearest_enemy)
        if p0.owner_id == other_id:
            continue
        p0_id = p0.owner_id
        for p1 in state.planets:
            if p1.owner_id != other_id:
                continue
            pdist = distance(p0, p1)
            if pdist < nearest_dist:
                nearest_dist = pdist
                p0.nearest_enemy = p1
                p1.nearest_enemy = p0

def sim(fromstate, to_round):
    calc_next_enemy(fromstate)
    state = deepcopy(fromstate)
    global planet_map
    planet_map=dict()
    for planet in state.planets:
        planet_map[planet.id] = planet

    res = dict()
    for round in range(state.round+1, to_round):
        for planet in state.planets:
            if planet.owner_id == 0:
                continue
            planet.ships = map(lambda s,p: s+p, planet.ships, planet.production)

        land_on_planet = {}
        for fleet in state.fleets:
            if fleet.eta != round:
                continue
            # combine fleets
            state.fleets.remove(fleet)
            target = fleet.target
            if target not in land_on_planet:
                land_on_planet[target] = []
            land_on_planet[target].append(fleet)

        highest_owner = 2
        for planet,fleets in land_on_planet.iteritems():
            fleets_of_players = [[] for _ in range(highest_owner + 1)]
            for fleet in fleets:
                fleets_of_players[fleet.owner_id].append(fleet)
            for playerfleets in fleets_of_players:
                if len(playerfleets) > 1:
                    for other in playerfleets[1:]:
                        combine_fleets(playerfleets[0], other)
                if playerfleets:
                    fleet_land(state, playerfleets[0])
        roundresult = deepcopy(state)
        calc_next_enemy(roundresult)
        res[round] = roundresult
    return res

snak3.py

#!/usr/bin/env python
# encoding: utf-8
import socket, json
import random, sys
import time
from collections import namedtuple
from copy import deepcopy
from math import ceil, sqrt
from sim import distance, sim, win
from random import randint

lastlog = open("lastlog.txt", "w")

def send(state, data, show=True):
    if show:
        # display some statistics
        ships = [0,0,0]
        prod = [0,0,0]
        for planet in state.planets:
            ships[planet.owner_id] += sum(planet.ships)
            prod[planet.owner_id] += sum(planet.production)
        for fleet in state.fleets:
            ships[fleet.owner_id] += sum(fleet.ships)
        print "%s: %4s:%4s [%4s:%4s] %s" % (state.round, prod[state.player_id], prod[state.other_id], ships[state.player_id], ships[state.other_id], data)
    io.write('%s\n' % (data,))
    io.flush()

def safe(state, future, our, neutral):
    d_on = distance(our, neutral)
    predicition = None
    for p in future[state.round + d_on].planets:
        if p.id == neutral.id:
            predicition = p
            break
    if predicition == None:
        print "No predicition?!?"
        return None

    price = sum(map(lambda x:x/5, predicition.ships)) * 3
    # no nearest enemy, assume it is safe
    if our.nearest_enemy is None:
        return d_on*3 - sum(neutral.production)
    if predicition.nearest_enemy is None:
        return d_on*3 - sum(neutral.production)

    o_t = our.nearest_enemy
    n_t = predicition.nearest_enemy
    d_ot = distance(our, o_t)
    d_nt = distance(neutral, n_t)
    # enemy nearer than neutral, don't even start
    if d_ot < d_nt:
        return None

    gain = (min(d_ot, d_nt) - d_on) * sum(neutral.production)
    return d_on*3 - sum(neutral.production)

def get_attack_fleet(our, dest):
    need = [
        min(our[0], dest[1]),
        min(our[1], dest[2]),
        min(our[2], dest[0])
    ]
    for i in range(0,3):
        if need[i] - our[(i+2) % 3] > 0:
            need[i] += min(need[i]-our[(i+2)%3], our[i])

    steps = 0
    while not win(need, dest):
        need[randint(0,2)] += 1
        steps += 1
        if steps > 20:
            # no win
            return None
    if need[0] > our[0] or need[1] > our[1] or need[2] > our[2]:
        # not enough ships
        return None
    return need

# helper foo for more convenient json access
class Empty(object):
    def __repr__(self):
        return str(self.__dict__)
    def __str__(self):
        return str(self.__dict__)

# helper foo for convenient json access (I don't use namedtuple as then the
# fields can't be changed later)
def make_object(d):
    res = Empty()
    for key,value in d.iteritems():
        setattr(res, key, value)
    return res

def make_move(data):
    state = json.loads(data, object_hook=lambda d: make_object(d))
    lastlog.write("%s: %s\n" % (state.round, data))
    winner = state.winner
    own_id = state.player_id
    if own_id == 1:
        other_id = 2
    else:
        other_id = 1
    state.other_id = other_id
    if winner:
        if winner == own_id:
            print "WON!"
        else:
            print "LOST!"
        sys.exit()

    future = sim(state, state.round+70)

    lastlog.write("round %s:\n" % state.round)
    best_own = None
    best_other = None
    bestvalue = 10000
    neutrals = []
    takeovers = []
    for ourplanet in state.planets:
        if ourplanet.owner_id != own_id:
            continue
        for planet in state.planets:
            if planet == ourplanet:
                continue
            # get predicition for time of flight arrival
            eta = state.round + distance(ourplanet, planet)
            predicted = None
            predicted2 = None
            for p in future[eta].planets:
                if p.id == planet.id:
                    predicted = p
                    break
            if predicted == None:
                print "No prediction?!?"
                continue
            for p in future[eta+1].planets:
                if p.id == planet.id:
                    predicted2 = p
                    break
            if predicted2 == None:
                print "No prediction?!?"
                continue
            if predicted2.owner_id == 0:
                # Neutral planet see if it safe
                price = safe(state, future, ourplanet, planet)
                if price is not None:
                    neutrals.append( (price, ourplanet, planet) )
                continue
            # No need to do anything if we will take the planet anyway
            if predicted2.owner_id == own_id:
                continue
            value = sum(predicted.ships) + distance(ourplanet, planet)*3
            if value < bestvalue:
                best_other = planet
                bestvalue = value
                best_own = ourplanet
            # can we send enough ships?
            need = get_attack_fleet(ourplanet.ships, predicted.ships)
            if need is not None:
                takeovers.append( (ourplanet, planet, need) )

    if len(takeovers) > 0:
        takeovers = sorted(takeovers, key=lambda (fromp,top,_): distance(fromp, top)*3 - sum(top.production))
        dest = takeovers[0]
        (ourplanet, planet, need) = dest
        lastlog.write("takeover %s -> %s (pred %s) need %s have %s\n" % (ourplanet, planet, predicted, need, ourplanet.ships))
        cmd = "send %s %s %s %s %s" % (ourplanet.id, planet.id, need[0], need[1], need[2])
        lastlog.write("%s\n" % (cmd,))
        send(state, cmd)
        return

    if len(neutrals) > 0:
        neutrals = sorted(neutrals, key=lambda x:x[0])
        best = neutrals[0]
        for (price,fromp,top) in neutrals:
            if fromp.ships[0] == 0 or fromp.ships[1] == 0 or fromp.ships[1] == 0:
                continue
            lastlog.write("stichel neutral %s -> %s\n" % (fromp, top))
            cmd = "send %s %s %s %s %s" % (fromp.id, top.id, 1, 1, 1)
            send(state, cmd)
            return

    if best_other != None:
        # sticheln
        lastlog.write("stichel enemy %s -> %s\n" % (best_own, best_other))
        cmd = "send %s %s %s %s %s" % (best_own.id, best_other.id, 1, 1, 1)
        send(state, cmd)
        return

    lastlog.write("%s: Nothing to do\n" % (state.round,))
    send(state, "nop")

if "test" in sys.argv:
    data = open("sampledata.txt").read()
    io = sys.stdout
    make_move(data)
    sys.exit()

USERNAME = "snak3"
PASSWORD = "not_in_the_gist"

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
dest = ("127.0.0.1", 6000)
if "real" in sys.argv:
    dest = ("spacegoo.gpn.entropia.de", 6000)
print "Connecting to (%s,%s)" % dest
s.connect(dest)
io = s.makefile('rw')
io.write('login %s %s\n' % (USERNAME, PASSWORD))
io.flush()
print "logged in"
while 1:
    data = io.readline()
    if not data:
        break
    if data[0] == "{":
        start = time.time()
        make_move(data)
        print "took %2fs" % (time.time()-start,)

print "done"