Mon champion du prologin 2016 qui a terminé 4ème

phases.py

from api import *
import utils
import timeutils
import random

#Strategie d'attaque
#`targets` contient les cibles potentielles : au debut ca contient les tuyaux directement a cote de la base adversaire, puis un echantillon aleatoire de tuyaux de l'adversaire
#La fonction score est assez lente (j'ai mesure environ 0.05s) donc il y a des risques de timeout que le code anticipe
def attack(hm):
    if points_action() < COUT_DESTRUCTION:
        return
    N = 10
    randomPipes = sorted(utils.tuyaux(False), key=lambda x: len([p for p in utils.nearCases(x) if est_tuyau(p)]))[:N]
    random.shuffle(randomPipes)
    targets = list(filter(est_tuyau, utils.flatten([utils.nearCases(p) for p in base_ennemie()]))) + randomPipes
    currentDiff = utils.diffPlasma(hm)
    def score(pos):
        if timeutils.elapsedTime() > 0.5:
            return -float("inf")
        err = detruire(pos)
        if err == erreur.OK:
            r = utils.diffPlasma(utils.genHeatmap()) - currentDiff
            annuler()
            return r
        else:
            return -float("inf")

    if targets:
        best = max((score(p), p) for p in targets)
        if best[0] > 5:
            detruire(best[1])

#Strategie d'aspiration
#En gros, on evalue sur quelle case c'est le mieux d'ajouter une aspiration, quelles cases n'ont pas besoin d'aspiration, et on bouge
#Pour cela on utilise la heatmap
def changerAspi(hm):
    def aTuyauACote(pos):
        return [p for p in utils.nearCases(pos) if est_tuyau(p)] != []

    casesNul = list(filter(lambda p: not aTuyauACote(p) and puissance_aspiration(p) > 0, ma_base()))
    if casesNul:
        posn = casesNul[0]
        best = None
        bestPos = None
        for p in ma_base():
            if aTuyauACote(p) and puissance_aspiration(p) < LIMITE_ASPIRATION:
                assert(deplacer_aspiration(posn, p) == erreur.OK)
                delta = utils.genHeatmap()[p[0]][p[1]][0] - hm[p[0]][p[1]][0]
                if best == None or delta > best:
                    best = delta
                    bestPos = p
                annuler()
        if bestPos != None:
            assert(deplacer_aspiration(posn, bestPos) == erreur.OK)

#Strategie de reconstruction de tuyaux
#Si le tuyau qu'on a detruit est a cote de la base ou si ca vaut le coup qu'on le reconstruise, bah on le reconstruit
#Pour le renforcer, je fais en plus un tuyau dans une des 8 cases autour
#Ca peut sembler naif, mais de maniere surprenante ca marche tres tres bien : au final il double les tuyaux la ou c'est utile
#Certains champions doublent les tuyaux des le debut, mais j'ai decide de ne pas le faire et aller chercher du plasma le plus vite pour attaquer plus vite
def handleBrokenPipe(pos):
    scoreBefore = utils.diffPlasma(utils.genHeatmap())
    deblayer(pos)
    construire(pos)
    scoreAfter = utils.diffPlasma(utils.genHeatmap())
    if scoreAfter <= scoreBefore and not case_type.BASE in map(type_case, utils.nearCases(pos)):
        annuler()
        annuler()
        return
    cases = [p for p in utils.nearCasesDiag(pos) if est_libre(p)]
    if cases:
        construire(cases[0])

#Fonction qui construit des tuyaux vers des endroits bien
#Pour aller chercher les tuyaux qui rapportent plus meme s'ils sont un peu plus loin, on affecte un score de "coolitude" aux cases pres des pulsars
#Le score de la case est `longueur du plus court chemin allant a la case` - constante*`score de coolitude`
#bestScore sert a renormaliser le score de coolitude pour travailler sans dimension
def makePipes():
    bestScore = max(map(lambda p: utils.pulsarScore(info_pulsar(p))[0], liste_pulsars()))
    pos2 = utils.flatten([utils.nearCases(p) for p in liste_pulsars() if utils.pulsarScore(info_pulsar(p))[0] > 0])
    pa = points_action()
    lastpa = pa + 1
    def caseScore(pos):
        return sum(utils.pulsarScore(info_pulsar(p))[0] for p in utils.nearCases(pos) if est_pulsar(p))/bestScore
    while lastpa > pa:
        pos1 = utils.tuyaux(True)
        paths = utils.bfs(pos1, pos2)
        if paths:
            c = min(paths.items(), key=lambda x: len(x[1]) - 5*caseScore(x[0]))[1]
            for p in c[:4]:
                construire(p)
        pa, lastpa = points_action(), pa

prologin.py

# coding: utf-8
# This file has been generated, if you wish to
# modify it in a permanent way, please refer
# to the script file : gen/generator_python.rb

"""
##     #######  ##### ###### ######            #####      #  #  ####
##     ##   ##  ##    ##     ##   ##           #   #      #  #     #
##     ##   ##  ##### #####  ######     #   #  #   #      ####  ####
##     ##   ##     ## ##     ## ##       # #   #   #  ##     #  #
###### ####### ###### ###### ##  ##       #    #####  ##     #  ####


O
Toi,
Monsieur
Relecteur,
Voici mon champion,
Puisse-t-il emplir ton coeur de joie
Car ceux qui entendent son nom vantent ses exploits.

(prolofib par Theophile & Garance)
(un fib est un poeme dont le nombre de syllabes suit la suite de fibonacci)

Fichiers :
    - phases.py :    Contient les fonctions pour les differentes phases de reflexion (reconstruction, attaque, ...)
    - utils.py :     Plein de fonctions utilitaires pratiques
    - timeutils.py : Fonctions pour gerer le temps (ie. pour pas timeout)

Quelques conventions de nom de variables que j'ai utilise :
    - pos : position "importante" (par ex, donnee en argument)
    - p : souvent une position qui apparait dans une boucle, ou comme argument dans un lambda (idem pp s'il y a deja un p)
    - l : souvent une liste
    - res : resultat qu'on renvoie a la fin
    - result : idem
    - hm : la heatmap (cf. utils.py)
Les noms sont parfois en francais ou en anglais, selon mon humeur...

J'ai essaye de faire un truc pas trop complique, il y a donc environ 160 lignes de code utiles
Il est au final assez agressif, et marche pas trop mal :-)
"""

from api import *
import utils
import phases
import timeutils

def partie_init():
    pass

def jouer_tour():
    #On met a jour l'horloge
    timeutils.newTurn()
    #On reconstruit
    if hist_tuyaux_detruits():
        phases.handleBrokenPipe(hist_tuyaux_detruits()[0])
    hm = utils.genHeatmap()
    #On bouge les aspirations
    phases.changerAspi(hm)
    #On attaque !
    phases.attack(hm)
    #On construit des tuyaux avec les points d'action qui restent
    phases.makePipes()

def partie_fin():
    pass

timeutils.py

import time

#Bon, la je pense pas avoir grand chose a expliquer

t = 0
def newTurn():
    global t
    t = time.clock()

def elapsedTime():
    return time.clock() - t

utils.py

from api import *
from collections import deque

#Renvoie un tuple de deux scores pour un pulsar
#Le premier est utile pour le long terme, c'est le nombre de plasmas que va donner le pulsar jusqu'a la fin du jeu
#Le second est utile pour le court terme, c'est le nombre de plasmas par seconde que donne le pulsar (je ne l'utilise pas malheureusement :-( )
def pulsarScore(pulsar):
    return pulsar.puissance * min(pulsar.pulsations_restantes, int((NB_TOURS - tour_actuel())/pulsar.periode)), pulsar.puissance/pulsar.periode

#Renvoie les 4 cases non interdites autour de pos
def nearCases(pos):
    x, y = pos
    return [p for p in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] if type_case(p) != case_type.INTERDIT]

#Idem mais renvoie les 8 cases
def nearCasesDiag(pos):
    x, y = pos
    return [p for p in [(x-1, y), (x-1, y-1), (x, y-1), (x+1, y-1), (x+1, y), (x+1, y+1), (x, y+1), (x-1, y+1)] if type_case(p) != case_type.INTERDIT]

#Renvoie la concatenation d'une liste de listes
def flatten(liste):
    return [x for inner in liste for x in inner]

#Calcule pour moi et mon adversaire, le nombre de plasma qu'il va gagner si les tuyaux restaient comme ca jusqu'a la fin de la partie, puis renvoie la difference
#(on peut voir ca comme un score de la position actuelle)
def diffPlasma(hm):
    return sum(map(lambda p: hm[p[0]][p[1]][0], ma_base())) - sum(map(lambda p: hm[p[0]][p[1]][0], base_ennemie()))

#Renvoie une grille qui contient sur chaque case :
#   - (0, 0) si la case n'est pas un tuyau
#   - (a, b) si la case est un tuyau, avec `a` le nombre de plasmas qui vont passer dans le tuyau si on changeait rien, et `b` le nombre de plasmas par seconde qui vont passer dedans
#(c'est un peu comme pulsarScore mais pour les tuyaux quoi)
#L'implementation est faite avec un dfs
#Pourquoi c'est appele `heatmap` ? Au debut je voulais ajouter de la "diffusion de chaleur" pour assigner un score aux cases autour des tuyaux mais finalement je n'en ai pas eu besoin
def genHeatmap():
    def propagate(grid, score, pos):
        a, b = score
        c, d = grid[pos[0]][pos[1]]
        grid[pos[0]][pos[1]] = (c+a, d+b)
        l = directions_plasma(pos)
        for p in l:
            propagate(grid, (a/len(l), b/len(l)), p)

    grid = [[(0, 0)]*TAILLE_TERRAIN for _ in range(TAILLE_TERRAIN)]
    for p in liste_pulsars():
        score = pulsarScore(info_pulsar(p))
        for pp in nearCases(p):
            if est_tuyau(pp):
                propagate(grid, score, pp)
    return grid

#Renvoie un dictionnaire dont les cles sont les elements de lpos2 et la valeur est un chemin allant d'un element de lpos1 a la cle
#Comme le nom l'indique, c'est fait avec un bfs
#Pour simplifier le code, dans la queue je garde des couples (position, chemin), meme si c'est pas tres tres beau
def bfs(lpos1, lpos2):
    seen = set(lpos1)
    done = set()
    result = {}
    queue = deque(map(lambda p: (p, []), lpos1))
    while queue and done != lpos2:
        p, c = queue.popleft()
        for p2 in nearCases(p):
            if p2 not in seen and est_libre(p2):
                if p2 in lpos2:
                    done.add(p2)
                    result[p2] = c + [p2]
                seen.add(p2)
                queue.append((p2, c + [p2]))
    return result

#Si moi = True, renvoie les tuyaux qui envoient les plasma vers ma base (et si moi = False, ceux de mon adversaire)
#C'est fait avec un dfs
def tuyaux(moi):
    res = []
    resset = set()
    def propagate(res, resset, pos):
        res.append(pos)
        resset.add(pos)
        for p in nearCases(pos):
            if p not in resset and est_tuyau(p) and pos in directions_plasma(p):
                propagate(res, resset, p)

    if moi:
        base = ma_base()
    else:
        base = base_ennemie()
    for p in ma_base():
        propagate(res, resset, p)
    return res