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

[Extra44]

C'est un graphe, certes, mais pas les mêmes règles.

Cest la "meme"logique oui, pas les mêmes règles, et pas le même langage.
On est bien d'accord

[ptijoz]

c'est bien si il y a beaucoup de participants
comment connaît-on notre numéro de participant ?
sinon je me demande si je ne suis pas un poisson rouge car malgré les explications je ne vois ce qu'il faut passer en paramètres. Enfantin a-t'on écrit

[critor]

Passer en paramètre où ça ?

Tu as juste à décider des bonnes valeurs à retourner par la fonction ia() :

• numéro de corniche voisine ciblée
• et ce que tu veux faire avec : y aller (0) ou y tirer (1)

[critor]

@ptitjoz tu as le même numéro que pour les défis précédents.

[Pavel]

Serait-il possible de voir le script utilisé pour l'évaluation?

J'essaye de trouver une solution pour initialiser les variables globales au début de chaque simulation mais c'est un peu trop difficile sans voir le script utilisé pour l'évaluation.

[legmask]

Oh mais c'est vrai c'est des graphe, j'ai vu ça ce matin

[critor]

@LeGmask Exact, nous avions bien conçus 3 défis en rapport avec les programmes de Seconde, puis Première, puis Terminale.
Mais ça reste largement abordable sans être en terminale. Pas besoin de comprendre les graphes pour par exemple juste décider de reculer en cas de danger, ce que l'IA aléatoire fournie ne fait pas.

@Pavel Voici le web.py modifié que l'on utilise actuellement pour l'évaluation.
Il n'a pas l'affichage graphique, et renvoie 1 mot pour permettre d'identifier facilement et compter les différentes issues possibles :

Code: Select all

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

#---
# RNG

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

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)]

#---


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
  if r:
    print("win " + str(s3), file=sys.stderr)
  else:
    if pfs0 & m_l:
      print("leviathan", file=sys.stderr)
    elif pfs0 & m_p:
      print("well", file=sys.stderr)
    elif s3 >= maxcoups:
      print("lowpower", file=sys.stderr)
    elif s4 < 0:
      print("exception", file=sys.stderr)
  return r, s2, s3

Et voici maintenant le script bash utilisé pour appeler ce web.py en boucle et compter :

Code: Select all

#! /usr/bin/bash

if [[ ! "$2" ]]; then
  echo "usage: $0 <nb of simulations> <l?.py file num>" >&2
  exit 1
fi

base_file="l""$2"
script_file="$base_file"".py"
infos_file="$base_file"".txt"
timestamp="$(date +"%s")"
# First seed for the tests
base_seed="$2"
# Web size for the tests
web_size=36
# Web density for the tests
web_density=.05
# Pits density for the tests
pits_density=.1
# Bats density for the tests
bats_density=.15
# Number of tests
test_count="$1"
# Total time spent escaping
escape_time=0
# Number of successful escapes, falls in wells, leviathan mishaps, exceptions
escapes=0
well=0
leviathan=0
exception=0
lowpower=0

RANDOM=$base_seed

# Upper bound is the number of tests
for i in $(seq 1 $test_count); do
  percent=$(echo "scale=2; $i*100/$test_count" | bc)
#  echo -ne "\rseed: $i/$test_count ($percent%)..." >&2
  result=$(python3 "$script_file" $RANDOM $web_size $web_density $pits_density $bats_density 2>&1 >/dev/null)

  case "$result" in
    "win "*)
      escape_time=$(($escape_time+${result#* }))
      escapes=$(($escapes+1));;
    "well")
      well=$(($well+1));;
    "leviathan")
      leviathan=$(($leviathan+1));;
    "lowpower")
      lowpower=$(($lowpower+1));;
    "exception")
      exception=$(($exception+1));;
  esac
  cat <<EOF > "$infos_file"
  $timestamp #date
  $test_count #total simulations
  $i #simulations
  $base_seed #seed
  $web_size #web size
  $web_density #web density
  $pits_density #pits density
  $bats_density #bats density
  $escapes #successes
  $escape_time #successes total steps
  $leviathan #fails by Leviathan
  $well #fails by well
  $lowpower #fails by low power
  $exception #fails by exception
EOF
done

printf "\r%40s\r" "" >&2

[critor]

La Critor's IA leval 1 a le défaut de souvent de commettre des erreurs fatales.

Je vous présente maintenant ma nouvelle création, la Critor's IA Level 2, surnommée "la peureuse".

Pour corriger cela, nous lui rajoutons une mémoire de la corniche précédente (la corniche d'où elle vient). Lorsqu'elle sent un danger (puits ou Léviathan), elle retourne à la corniche dont elle vient, forcément sûre.

Testons avec 100'000 simulations sur des graphes de taille 36.

Rien qu'avec ça nous avons une amélioration fantastique du taux de succès :

	Type	Déplacement normal	Déplacement si clé trouvée après porte	Déplacement en cas de danger	Déplacement en cas de blocage	Condition de tir	Succès
Exemple fourni	aléatoire	corniche voisine au hasard				jamais	≈7,3%
critor's IA level 1 "l'attaquante"	réactive	corniche voisine au hasard				corniche voisine au hasard quand Léviathan détecté 2 fois de suite	≈8,5%
critor's IA level 2 "la peureuse"	réactive	corniche voisine au hasard		corniche précédente si puits ou Léviathan détecté		corniche voisine au hasard quand Léviathan détecté 2 fois de suite	≈22,9%

[Pavel]

@Pavel Voici le web.py modifié que l'on utilise actuellement pour l'évaluation.

Merci pour les scripts! C'est très clair pour moi maintenant.

[cent20]

@Pavel Voici le web.py modifié que l'on utilise actuellement pour l'évaluation.

Merci pour les scripts! C'est très clair pour moi maintenant.

Moi je n'ai rien compris au script d'évaluation ...
Bon après il est vrai que je ne l'ai pas encore lu