Concours de rentrée 2020 - défi Python du Léviathan

[ptijoz]

Non.

Ce sont les corniches que tu peux atteindre depuis ta corniche actuelle.
C'est-à-dire celles avec lesquelles il y a une passerelle, comme dessiné.

merci Critor. voila déjà un doute de levé. donc c'est plutôt corniches accessibles que voisines...

[critor]

Nouvelles IA des participants n°2 et 37, direct à suivre dès maintenant :
https://tiplanet.org/concours_rentree20 ... &invalid=1

[critor]

Egalement, nouvelle IA inventée par le n°10. En direct de suite :
https://tiplanet.org/concours_rentree20 ... &invalid=1

[critor]

Nouveau IA du n°10 à nouveau, le direct vient de démarrer :
https://tiplanet.org/concours_rentree20 ... &invalid=1

[citorva]

Voici un script de benchmark que j'ai crée. Il est capable de prendre en charge la nom réponse du script avec un temps maximum de 20 secondes et de vous retourner les résultats dans une magnifique fenêtre
Edit du 14/11/2020: Il est désormais possible de modifier le temps d'attente ainsi que le nombre de tests
Edit du 15/11/2020: Il est désormais possible de fermer la fenêtre à tout moment en cliquant sur le bouton fermer et il existe deux modes d'affichages de la gauge. La première affiche les succès/echecs sur toute la gauge et la seconde alloue un espace proportionel pour f'affichage des données précédentes au nombre de tests effectués sur le nombre total de tests.
Edit du 15/11/2020 20h: L'affichage du temps restant est corrigé et le programme fait un décompte du temps d'exécution. C'est peut⁻être rien mais c'est pratique pour savoir où en est le programme.



Voici les fichiers:

bench.py

Code: Select all

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import pygame
import threading
import time
import importlib
import math
import sys

import web

# Paramètres du progamme
module = sys.argv[1] if len(sys.argv) > 1 else "web_test"
N = int(sys.argv[2]) if len(sys.argv) > 2 else 100000
duree_max = int(sys.argv[8]) if len(sys.argv) > 8 else 20

web_test = importlib.import_module(module)

pygame.init()

ecran = pygame.display.set_mode((320,240))
police_titre = pygame.font.Font(pygame.font.get_default_font(),25)
police = pygame.font.Font(pygame.font.get_default_font(),12)

couleur_texte = (192,192,192)
couleur_victoire = (40,167,69)
couleur_exeption = (245,232,0)
couleur_energie = (127,127,127)
couleur_puit = (255,128,60)
couleur_leviathan = (247,64,59)
couleur_non_reponse = (255,0,0)

couleur_arriere_plan = (24,24,24)
couleur_arriere_plan_gauge = (33,33,33)

marge = 8
hauteur_gauge = 24
police_principal = 20
police_texte = 10

total = 0

total_exeption = 0

total_energie = 0

total_puit = 0

total_leviathan = 0

total_non_reponse = 0

total_victoire = 0

trajet_moyen = 0

exeption = None
arret_demande = False
affichage_absolu = False

heure_depart = time.time()
heure_fin = 0

def cree_jauge(surface, donnees, couleur, rect):
    w = rect.width

    total = 0
    N = len(donnees)
    gauges_sz = [0]*N
    g_w = 0

    for i in donnees:
        total += i
   
    for i in range(N-1):
        t = int(w*donnees[i]/total)
        gauges_sz[i] = t
        g_w += t
   
    gauges_sz[-1] = w-g_w

    g_w = 0

    for i in range(N):
        surface.fill(couleur[i], (rect.x+g_w,rect.y,gauges_sz[i],rect.height))
        g_w += gauges_sz[i]
# Affiche l'ordre de grandeur du temps restant
def rendu_temps(temps):
    minutes = temps//60 % 60
    heures = temps//3600 % 24
    jours = temps//86400
    if jours != 0:
        return "~%d jour%s" % (jours, "s" if jours != 1 else "")
    if heures != 0:
        return "~%d heure%s" % (heures, "s" if heures != 1 else "")
    if minutes != 0:
        return "~%d minute%s" % (minutes, "s" if minutes != 1 else "")
    return "< 1 minute"

def format_duree(duree):
    duree = int(math.floor(duree))
    return "{}{:02d}s".format(
        "{}{:02d}min".format(
            "{}{:02d}h".format(
                "{}j".format(duree//86400) if duree//86400 != 0 else "",
                duree//3600 % 24
            ) if duree//3600 != 0 else "",
            duree//60 % 60
        ) if duree//60 != 0 else "",
        duree%60
    )

def affichage_donnees():
    total_echec = total_exeption + total_energie + total_puit + total_leviathan + total_non_reponse
    total_victoire = total - total_echec
    temps_restant = math.ceil(duree_max - temps_exec_unitaire)

    duree = time.time()-heure_depart
    temps_exec = duree*(N/total-1)

    score = 1000*(total_victoire-2*total_non_reponse-total_exeption//2)*web.web_dim/total - trajet_moyen*web.web_dim/total

    largeur = 512
    hauteur = marge

    texte_compteur = police_titre.render("Simulation %d sur %d (%0.00f%%)"%(total, N, 100.*float(total)/float(N)), True, couleur_texte)
    largeur = max(largeur,texte_compteur.get_width())
    hauteur += texte_compteur.get_height() + marge
    texte_score = police.render("Score: %d"%(score), True, couleur_texte)
    largeur = max(largeur,texte_score.get_width())
    hauteur += texte_score.get_height() + marge
    texte_victoire = police.render("%0.00f%% de victoires (%d). Trajet moyen: %d"%(100*total_victoire/total,total_victoire,trajet_moyen),True, couleur_victoire)
    largeur = max(largeur, texte_victoire.get_width())
    hauteur += texte_victoire.get_height() + marge
    texte_temps_annulation = None
    texte_temps_restant = None
    if total != N:
        texte_temps_restant = police.render("Temps restant: %s. Écoulé %s"%(rendu_temps(math.ceil(temps_exec)),format_duree(duree)), True, couleur_texte)
        texte_temps_annulation = police.render("Temps restant avant annulation: %d seconde%s"%(temps_restant if temps_restant > 0 else 0, "s" if temps_restant > 1 else ""),True, couleur_texte if temps_restant > 5 else couleur_leviathan)
    else:
        texte_temps_restant = police.render("Tests effectués en %s"%(format_duree(heure_fin-heure_depart)), True, couleur_victoire)
        texte_temps_annulation = police.render("",True,couleur_texte)
    largeur = max(largeur,texte_temps_annulation.get_width())
    hauteur += texte_temps_annulation.get_height() + marge
    largeur = max(largeur,texte_temps_restant.get_width())
    hauteur += texte_temps_restant.get_height() + marge
   
    texte_echec = []
    valeur_gauge = [total_victoire]
    couleur_gauge = [couleur_victoire]
    if total_non_reponse != 0:
        texte_echec.append(police.render("%0.00f%% ne répondant pas (%d, %d%% des échecs)"%(100*total_non_reponse/total, total_non_reponse, 100*total_non_reponse/total_echec), True, couleur_non_reponse))
        valeur_gauge.append(total_non_reponse)
        couleur_gauge.append(couleur_non_reponse)
    if total_exeption != 0:
        texte_echec.append(police.render("%0.00f%% à cause d'une exeption (%d, %d%% des échecs)"%(100*total_exeption/total, total_exeption, 100*total_exeption/total_echec), True, couleur_exeption))
        valeur_gauge.append(total_exeption)
        couleur_gauge.append(couleur_exeption)
    if total_energie != 0:
        texte_echec.append(police.render("%0.00f%% par manque d'énergie (%d, %d%% des échecs)"%(100*total_energie/total, total_energie, 100*total_energie/total_echec), True, couleur_energie))
        valeur_gauge.append(total_energie)
        couleur_gauge.append(couleur_energie)
    if total_puit != 0:
        texte_echec.append(police.render("%0.00f%% tombé dans un puit (%d, %d%% des échecs)"%(100*total_puit/total, total_puit, 100*total_puit/total_echec), True, couleur_puit))
        valeur_gauge.append(total_puit)
        couleur_gauge.append(couleur_puit)
    if total_leviathan != 0:
        texte_echec.append(police.render("%0.00f%% mangé par leviathan (%d, %d%% des échecs)"%(100*total_leviathan/total, total_leviathan, 100*total_leviathan/total_echec), True, couleur_leviathan))
        valeur_gauge.append(total_leviathan)
        couleur_gauge.append(couleur_leviathan)
    if affichage_absolu:
        valeur_gauge.append(N-total)
        couleur_gauge.append(couleur_arriere_plan_gauge)
   
    for i in texte_echec:
        hauteur += i.get_height() + marge
        largeur = max(largeur, i.get_width())

    hauteur += hauteur_gauge + marge
    largeur += 2*marge

    surface = pygame.Surface((largeur, hauteur))
    surface.fill(couleur_arriere_plan)

    y = marge
    surface.blit(texte_compteur, (largeur/2-texte_compteur.get_width()/2,y,texte_compteur.get_width(),texte_compteur.get_height()))
    y += texte_compteur.get_height() + marge
    surface.blit(texte_score, (largeur/2-texte_score.get_width()/2,y,texte_score.get_width(),texte_score.get_height()))
    y += texte_score.get_height() + marge
    cree_jauge(surface, valeur_gauge, couleur_gauge, pygame.Rect(marge, y, largeur-2*marge, hauteur_gauge))
    y += hauteur_gauge + marge
    surface.blit(texte_temps_restant, (largeur/2-texte_temps_restant.get_width()/2,y,texte_temps_restant.get_width(),texte_temps_restant.get_height()))
    y += texte_temps_restant.get_height() + marge
    surface.blit(texte_victoire, (marge,y,texte_victoire.get_width(),texte_victoire.get_height()))
    y += texte_victoire.get_height() + marge

    for i in texte_echec:
        surface.blit(i, (marge,y,i.get_width(),i.get_height()))
        y += i.get_height() + marge

    surface.blit(texte_temps_annulation, (largeur/2-texte_temps_annulation.get_width()/2,y,texte_temps_annulation.get_width(),texte_temps_annulation.get_height()))
   
    return surface
   
def fonction_affichage():
    global arret_demande,affichage_absolu

    temps_mise_a_jour = 0
    duree_mise_a_jour = 1/60
    debut_clic = False

    while not arret_demande:
        if total != 0 and time.time() - temps_mise_a_jour >= duree_mise_a_jour:
            surface = affichage_donnees()
            ecran = pygame.display.set_mode((surface.get_width(),surface.get_height()))
            ecran.blit(surface, (0,0,ecran.get_width(),ecran.get_height()))
            pygame.display.flip()
            temps_mise_a_jour = time.time()
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                arret_demande = True
            elif event.type == pygame.MOUSEBUTTONDOWN:
                debut_clic = True
            elif event.type == pygame.MOUSEBUTTONUP and debut_clic:
                affichage_absolu = not affichage_absolu
                debut_clic = False

def fonction_test():
    global trajet_moyen,total_victoire,total_puit,total_leviathan,total_exeption,total_energie
    web_test.init()
    (victoire, type_defaite, _, nombre_coups) = web.parcourir_selon(web_test.ia)

    if victoire:
        trajet_moyen = (trajet_moyen * total_victoire + nombre_coups) / (total_victoire + 1)
        total_victoire += 1
    else:
        if type_defaite & 1:
            total_puit += 1
        if type_defaite & 2:
            total_leviathan += 1
        if type_defaite & 4:
            total_exeption += 1
        if type_defaite & 8:
            total_energie += 1


x = threading.Thread(target=fonction_affichage)
x.start()

while total != N and not arret_demande:
    y = threading.Thread(target=fonction_test)
    y.start()

    if exeption != None:
      time.sleep(.5)
      total_exeption = exeption

    action_annulee = False
    temps_exec_unitaire = 0
    temps_depart = time.time()

    while y.is_alive() and not arret_demande and not action_annulee:
        temps_exec_unitaire = time.time()-temps_depart
        if temps_exec_unitaire > duree_max:
            action_annulee = True

    if action_annulee or arret_demande:
      exeption = int(total_exeption)
      del y
      total_non_reponse += 1
      temps_exec_unitaire += 0.5
    else:
      exeption = None

    total += 1

if exeption != None:
    total_exeption = exeption
heure_fin = time.time()

if not arret_demande:
    x.join()

pygame.quit()


web.py

Code: Select all

from math import pi, cos, sin, floor
import sys

rnd_seed = int(sys.argv[3]) if len(sys.argv) > 3 else 0xc0ffee
web_dim = int(sys.argv[4]) if len(sys.argv) > 4 else 36
web_density = float(sys.argv[5]) if len(sys.argv) > 5 else .05
pits_density = float(sys.argv[6]) if len(sys.argv) > 6 else .1
bats_density = float(sys.argv[7]) if len(sys.argv) > 7 else .15

# Implémentation de fonctions personnalisé de random

def rnd():
  global rnd_seed
  rnd_max = 0x7fff
  rnd_seed = (rnd_seed * 214013 + 2531011) % 4294967296
  return ((rnd_seed // (2*rnd_max + 1)) & rnd_max)

def random():
  return rnd() / 0x7fff

def randint(a,b):
  return rnd() % (b-a+1) + a

def choice(l):
  return l[randint(0, len(l)-1)]

# Fin de l'implémentation

screen_h = 240
m_p, m_l, m_k, m_b, m_d, m_a, m_m = 1, 4, 16, 64, 256, 1024, 4096

def insertinto(l1, l2):
  for v in l1:
    if v not in l2:
      l2.append(v)
  return l2

def removefrom(l1, l2):
  for v in l1:
    try:
      l2.remove(v)
    except:
      pass
  return l2

def connectPlatforms(s1, s2):
  global web
  web[s1][s2], web[s2][s1] = 1, 1

def get_reachable_platforms_from_platforms(l, safe):
  lv = []
  for s in l:
    for i in range(dimweb):
      if web[s][i]:
        if i not in lv and (not(safe) or not (platforms[i] & m_p)):
          lv.append(i)
  return lv

def cango(s1, s2, safe):
  lvo1, lvi1, lvo2, lvi2, t_inter, k = [], [s1], [], [s2], 0, 0
  while not (t_inter) and len(lvi1) and len(lvi2):
    lvo1, lvo2 = insertinto(lvo1, lvi1), insertinto(lvo2, lvi2)
    for v in lvo1:
      if v in lvo2:
        return k
    lvi1, lvi2 = get_reachable_platforms_from_platforms(lvo1, safe), get_reachable_platforms_from_platforms(lvo2, safe)
    lvi1, lvi2 = removefrom(lvo1, lvi1), removefrom(lvo2, lvi2)
    k += 1
  return 0

def my_bitor(a, b):
  return ~(~a & ~b)

def init_web(d, p_p, p_b):
  global web, platforms, mwspr, mhspr, zoom, mwc, screen_w, screen_h
  yweb, l0 = screen_h / 2, list(range(dimweb))
  l0.remove(0)
  web, platforms, conn, dconn, i_k = [], [0 for k in range(dimweb)], [0], list(range(1, dimweb)), choice(l0)
  for j in range(dimweb):
    web.append([0 for k in range(dimweb)])
  while len(dconn):
    s = dconn[randint(0, len(dconn) - 1)]
    connectPlatforms(conn[randint(0, len(conn) - 1)], s)
    dconn.remove(s)
    conn.append(s)
  for j in range(dimweb-1):
    for i in range(j + 1, dimweb):
      if floor(d + random()):
        connectPlatforms(i, j)
  i_d = choice(l0)
  platforms[i_d] = my_bitor(platforms[i_d], m_d)
  l1 = list(l0)
  for v in get_reachable_platforms_from_platforms([0], 0):
    l1.remove(v)
  if not(len(l1)):
    l1 = l0
  l2 = list(l1)
  for v in get_reachable_platforms_from_platforms(get_reachable_platforms_from_platforms([0], 0), 0):
    try:
      l2.remove(v)
    except:
      pass
  if not(len(l2)):
    l2 = l1
  i_l = choice(l2)
  platforms[i_l] = my_bitor(platforms[i_l], m_l)
  platforms[i_k] = my_bitor(platforms[i_k], m_k)
  for i in l1:
    if i != i_k and i != i_d and floor(p_p*dimweb/len(l1) + random()):
      if cango(0, i_k, 1) and cango(0, i_d, 1):
        platforms[i] = my_bitor(platforms[i], m_p)
    if floor(p_b*dimweb/len(l1) + random()):
      platforms[i] = my_bitor(platforms[i], m_b)

def parcourir_selon(ia):
  global dimweb, platforms, web_dim, web_density, pits_density, bats_density
  dimweb = web_dim
  maxcoups = dimweb**2 * 2
  init_web(web_density, pits_density, bats_density)

  s0, s1, s2, s3, s4, s5, s6, s7 = 0, 0, m_a, 0, 1, -1, 0, 0
  pfs0, pfs5 = platforms[s0], 0
  while s4 > 0  and (not (s2 & (2 * m_k)) or not (pfs0 & m_d)):
    if s5 < 0:
      s5 = 0
    else:
      try:
        k, k2 = ia(s0, voisines, dimweb, s1, s2)
        if pfs5 & (2 * m_b):
          while s0 == s5:
            s0 = randint(0, dimweb - 1)
          pfs0, pfs5 = my_bitor(platforms[s0], m_b), pfs5 & ~(3 * m_b) & ~m_m
        else:
          if k2:
            if s2 & m_a:
              v = platforms[k]
              if v & m_l:
                v, s2 = v & ~m_l, my_bitor(s2, 2 * m_l)
                platforms[k] = my_bitor(v, 2 * m_l)
              s2 = s2 & ~m_a
              s2 = my_bitor(s2, 2 * m_a)
          else:
            if k in voisines:
              s0 = k
              if pfs5 & m_b:
                pfs5 = my_bitor(pfs5, 2 * m_b)
              pfs0, pfs5 = platforms[s0], pfs5 & ~m_m
          s3 += 1
          if s3 >= maxcoups:
            s4 = 0
        if pfs0 & m_k:
          pfs0 = pfs0 & ~m_k
          s2 = my_bitor(s2, 2 * m_k)
        if pfs0 & my_bitor(m_p, m_l):
          s4 = 0
          pfs0 = my_bitor(pfs0, 2 * m_m)
        platforms[s5] = pfs5
      except Exception as t_excpt:
        s4 = -1
        print(t_excpt)
    pfs0 = my_bitor(pfs0, m_m)
    s1, voisines = pfs0, get_reachable_platforms_from_platforms([s0], 0)
    platforms[s0] = pfs0
    for v in voisines:
      t = my_bitor(m_p, m_l)
      t = platforms[v] & my_bitor(t, m_k)
      s1 = my_bitor(s1, t)
    for v in get_reachable_platforms_from_platforms(voisines, 0):
      t = platforms[v] & m_l
      s1 = my_bitor(s1, t)
    s, sold = my_bitor(s1, s2), my_bitor(s6, s7)
    s5, s6, s7, pfs5 = s0, s1, s2, pfs0
  r = s4 > 0 and s3 < maxcoups
  s1 = 0
  if not r:
    if pfs0 & m_l:
      s1 |= 2
    elif pfs0 & m_p:
      s1 |= 1
    elif s3 >= maxcoups:
      s1 |= 8
    elif s4 < 0:
      s1 |= 4
  return r, s1, s2, s3


Le script web.py a été modifié pour fonctionner correctement

Le script bench.py peut s'appeler sans argument ou avec les arguments dans cet ordre:

• nom du module sans l'extension (par defaut web_test). Une fonction init est nécessaire et veuillez retirer la ligne parcourir_selon(ia)
• nombre de tests à effectuer (par defaut 100000)
• seed du monde (par defaut 0xc0ffee)
• le nombre de corniches (par defaut 36)
• la densité de corniches voisines (par defaut .05)
• la densité de puits (par defaut .1)
• la densité de chauves souris (par defaut .15)
• durée maximum d'un test en seconde avant d'être considéré comme sans réponse (par defaut 20)

[critor]

Merci à toi, c'est super sympa.

[cent20]

C'est quoi déjà la formule qui donne le score ? Je l'ai vu passer, mais sur le chat il me semble.

[Afyu]

Pour vous aider à adopter la meilleure stratégie, je donne la formule de calcul retenue :

Code: Select all

# j = nombre de parties jouées
# s = nombre de parties gagnées
# t = total du nombre de coups joués pour les seules parties gagnées
# dimweb = nombre de corniches dans le cratère du volcan
score = 1000*s*dimweb/j - t/s/dimweb

Voilà
C'est page 3, dans les commentaires.

[citorva]

Cool, je vais pouvoir l'ajouter au script

[cent20]

Cool, je vais pouvoir l'ajouter au script

Merci c'est ce que j'espérais. Je n'ai pas encore tout compris sur comment fonctionne ton script, je creuse ça bientôt.

score = 1000*s*dimweb/j - t/s/dimweb

Le score maximal est de 36 000 apparemment. (il y a bien 36 corniches non ?)
L'impact de - t/s/dimweb me parait insignifiant.