import random random.seed(0.2) from pygraphlib import pygraph, algo from msg_parser import * import sys class Bot(object): def __init__(self, name): self.name = name self.location = 0 def dp(*args): return for x in args: print >> sys.stderr, x, print >> sys.stderr COP_BANK_WEIGHT = 300.0 ROBBER_BANK_WEIGHT = 1000 BANK_MONEY_WEIGHT = 1.0 def red(x): return '\x1b[31m%s\x1b[0m' % x def green(x): return '\x1b[32m%s\x1b[0m' % x def yellow(x): return '\x1b[33m%s\x1b[0m' % x class StateMachine(object): def __init__(self, wsk_text): 'Constructs a world based on wsk_text' w = world_skeleton_msg.parseString(wsk_text) self.name = w[0] self.robber = w[1] self.cops = w[2] c = self.coords = {} t = self.tags = {} self.hq = [] self.robbed_banks = {} # Get the locations and store coordinates for loc, tag, c1, c2 in w[3]: c[loc] = (c1,c2) t.setdefault(tag,[]).append(loc) if tag == 'bank': self.robbed_banks[loc] = 0 # Store edges foot = self.foot = pygraph.DGraph() car = self.car = pygraph.DGraph() for l1, l2, et in w[4]: car.add_edge(l1,l2) if et == 'foot': if l1 not in foot or l2 not in foot: foot.add_edge(l1,l2) if not foot.get_edge(l1,l2): foot.add_edge(l1,l2) if not foot.get_edge(l2,l1): foot.add_edge(l2,l1) assert et in ('car','foot') self.banks = {} self.bank_weight = {} self.coplocs = {} self.loccops = {} self.coptypes = {} self.cache = {} self.looted = 0 self.loot = 0 self.panik_count = 10 self.panik_count = 0 self.last_loc1 = self.tags['robber-start'] self.last_loc2 = self.tags['robber-start'] self.recently_robbed = '' def world_update(self, wsu): w = world_msg.parseString(wsu) self.n = w[0] for loc,val in w[2]: self.banks[loc] = int(val) # only robber for now, so no evidence or smell self.loccops.clear() for bot,loc,ptype in w[5]: if ptype == 'cop-foot' or ptype == 'cop-car': self.coplocs[bot] = loc self.loccops[loc] = bot self.coptypes[bot] = ptype elif ptype == 'robber': self.robberloc = loc else: assert False loot = int(w[1]) if self.loot != loot: self.looted += 1 self.robbed_banks[self.robberloc] += 1 self.recently_robbed = self.robberloc self.panik_count += 3 self.loot = loot def sp(self, g, s, t): 'Caching for shortest path computation' if (g,s,t) in self.cache: return self.cache[g,s,t] path = algo.shortest_path(g, s,t) # Cache intermediary results too n = len(path) for i in range(1,n-1): for j in range(i,n-1): self.cache[g, path[i][0], path[j][0]] = path[i:j+1] return path def spf(self, s, t): 'Return shortest path from s to t on foot' return self.sp(self.foot, s, t) def spc(self, c, l): 'Shortest path from cop c to location l' return self.sp(self.coptypes[c]=='cop-foot' and self.foot or self.car, self.coplocs[c], l) def dist(self, g, s, t): 'Distance from s to t' return float(len(self.sp(g,s,t))) - 0.9 def distf(self, s, t): 'Distance from s to t on foot' return float(len(self.sp(self.foot,s,t))) - 0.9 def distc(self, c, l): 'Distance from cop c to l' return float(len(self.spc(c,l))) - 0.9 def deadend(self, l): dp(green('CHECKING DEADNESS'),self.foot.out_edges(l), l) if len(self.foot.out_edges(l)) == 1: dp(green('DEADEND')) return True return False # return len(self.foot.out_edges(l)) == 1 def avoid_cops_move(self, desired_loc): # The idea here is to still move generally towards desired_loc, but at # the same time move in a non-optimal route so as to avoid cops. assert self.robberloc != desired_loc # outgoing = [self.foot.edge_tail(y) for y in # self.foot.out_edges(self.robberloc)] best_next_int = self.spf(self.robberloc, desired_loc)[1][0] assert best_next_int in self.choices.keys() outgoing = self.choices.keys() outgoing.remove(best_next_int) if not outgoing: # Sometimes we're trapped :( self.choices[best_next_int] += 1000 for out in outgoing: # Dist from cops dc = -6.0*sum([1.0/self.distc(x, out) for x in self.cops]) # Smell ds = -self.smells(out)*1.0 # Closess to desired spot dl = 30.0*1.0/self.distf(out, desired_loc) if self.deadend(out): dl -= 1000 self.choices[out] += 100*(ds+dc+dl) def move(self): dp(yellow('++++++++++++++++++++++++++++++++++++++PANIK')) dp(red('++++++++++++++++++++++++++++++++++++++PANIK')) dp(yellow('++++++++++++++++++++++++++++++++++++++PANIK')) dp(red('++++++++++++++++++++++++++++++++++++++PANIK')) dp(red('+++++++++++LOCATIOn'), self.robberloc) dp(red('+++++++++++LOOT:'), self.loot) # Each of the outgoing edges starts with 0 weight self.choices = dict([(self.foot.edge_tail(y),0.0) for y in self.foot.out_edges(self.robberloc)]) dp('out_nodes', self.choices.keys()) dp('out edges', self.foot.out_edges(self.robberloc)) # Perform an initial weighting pass WEIGHT_SMELL = 10.0 WEIGHT_COPS_ON_LOC = 100000.0 WEIGHT_BANK_DIST = 5.0 for choice in self.choices: w = 0.0 # How well-smelled is this intersection? w -= WEIGHT_SMELL * self.smells(choice) # Is there a cop on the intersection? if choice in self.coplocs.values(): w -= WEIGHT_COPS_ON_LOC # Sum the inverse distances; gives credit to moves that are closer # to multiple banks. dw = 0 for bank in self.banks.keys(): d = self.distf(self.robberloc, bank) if d == 0: continue # The -0.9 will cause banks that are one-away to get high # weights dw += 1.0/(self.distf(self.robberloc, bank)-0.9) w += WEIGHT_BANK_DIST*dw # And of course, a bit of randomness w += 2*(.5-random.random()) if self.deadend(choice): # Also penalize dead-end banks w -= 40 if self.last_loc2 == choice: dp(red('***************** WHAT THE FUCK')) w -= 5 if choice == 'quad-loop-#2': dp(yellow('NSOTHUSNOTHUSNOTHUON FUCKKKKKKKKKKKKKKKKKKKKKKKKKKK')) w -= 200000 self.choices[choice] = w # Weight the banks; we need this for later order = self.weight_banks() # Ok, now that we've given preliminary weights, lets try the specific # mode we're in. if self.panik(): # Ok, we're paniking. Move like we're paniking! move = self.panik_weight() else: # If we're not paniking, then give a bonus to the most desirable # bank. path = self.spf(self.robberloc, self.bank_ordering[0][0]) self.choices[path[1][0]] += 5 dp( 'path:', path, self.banks, self.robberloc, path) dp( 'outgoing:', [self.foot.edge_tail(y) for y in self.foot.out_edges(self.robberloc)]) # FIXME add random chance that we'll just try to run away from the cops # irrespective of anything. Perhaps just stick ourselves in panik mode # at random. # if random.random() < 0.06 and self.panik_count == 0: if False: dp(yellow('++++++++++++++++++++++++++++++++++++++PANIK')) dp(red('++++++++++++++++++++++++++++++++++++++PANIK')) dp(yellow('++++++++++++++++++++++++++++++++++++++PANIK')) dp(red('++++++++++++++++++++++++++++++++++++++PANIK')) self.panik_count = 3 # Now actually make the move ordering = self.choices.items() ordering.sort(lambda x,y: cmp(y[1],x[1])) move = ordering[0][0] print 'mov:', move, 'robber' for x,y in ordering: dp( ' edges',x,y) self.last_loc2 = self.last_loc1 self.last_loc1 = move def weight_banks(self): for bank in self.banks.keys(): # Inverse weighting law to give cops closer to bank higher weights # Also need to adjust for how much loot we've stolen # dp('bank:',bank) # dp('DIST:',len(self.spc(self.cops[0], bank))) dw = -sum([1.0/self.distc(x, bank) for x in self.cops]) # dp('*********************t', dw) self.bank_weight[bank] = dw * COP_BANK_WEIGHT # dp( 'copdist',self.bank_weight[bank]) # Now see how close we are to the banks dw = 1.0/self.distf(self.robberloc, bank) self.bank_weight[bank] += dw * ROBBER_BANK_WEIGHT # dp( 'robdist',self.bank_weight[bank]) # What if cops are camping out along the way to the bank? dw = 0 sp = self.spf(self.robberloc, bank) for l,d in sp: if l in self.loccops: dw -= 10 self.bank_weight[bank] += dw if self.deadend(bank): # Also penalize dead-end banks self.bank_weight[bank] -= 400 # Now weight the money in the bank. Note that we need to adjust for # how many times we've looted, as the total amount of money in the # game decreases. I've naively assumed that the money just # equalizes, because it is unlikely that we will rob multiple banks # within 4 turns. dw = BANK_MONEY_WEIGHT*self.banks[bank] * (6/5)**self.looted if dw: self.bank_weight[bank] += dw else: self.bank_weight[bank] -= 1000.0 # dp('moneyweight',self.bank_weight[bank]) # Penalize banks we've robbed before dw = -100*self.robbed_banks[bank] self.bank_weight[bank] += dw # Order the banks ordering = self.bank_weight.items() ordering.sort(lambda x,y: cmp(y[1],x[1])) for x,y in ordering: dp( ' bank ',x,y) self.bank_ordering = ordering return ordering def can_smell(self, cop, loc): if self.coptypes[cop] == 'cop-foot': return int(self.distc(cop,loc) <= 2.2) return int(self.distc(cop,loc) <= 1.2) def smells(self, loc): 'Return the number of cops that can smell loc' s = sum([self.can_smell(x, loc) for x in self.cops]) dp(red('*** Smells like'), loc, s) return s return sum([self.can_smell(x, loc) for x in self.cops]) def panik(self): 'Return True if we should panik' s = self.smells(self.robberloc) dp(yellow('SMELLY:'), s, self.panik_count) if s >= 1 and self.panik_count == 0: self.panik_count += 4 return True elif self.panik_count: return True def panik_weight(self): self.panik_count -= 1 # if self.panik_count <= 0: # Not completely paniked, still try to go towards highest # weighted bank # desired = self.bank_ordering[0][0] # dp(yellow('PANIK in yellow')) # return self.avoid_cops_move(desired) dp(red('PANIK in red')) # Otherwise, run like a horse with its tail on fire for out in self.choices.keys(): # FIXME weights dc = -20.0*sum([1.0/self.distc(x, out) for x in self.cops]) dp(' out:', out) for x in self.cops: dp(red(' '+x),self.distc(x, out)) # also away from the bank if self.recently_robbed: dc -= 20.0*1.0/self.distf(self.recently_robbed, out) ds = -self.smells(out)*20.0 if self.deadend(out): # dp(red('***************** WHAT THE FUCK')) ds -= 20 # if self.last_loc2 == out: # dp(red('***************** WHAT THE FUCK')) # ds -= 20 self.choices[out] += (ds+dc) if __name__ == '__main__': pass