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

[critor]

Il me semble que les 2 phases de réévaluation déjà décrites suffisent à établir une égalité que je trouve satisfaisante.

Au contraire, les tentatives en question sont hautement intéressantes.
La prochaine fois, peut-être on utilisera 2 graines aléatoires.
1 graine privée pour la génération, interdit d'y toucher.
Et 1 graine publique pour le déroulement de la partie que vous pourrez tenter de hacker comme vous voudrez.

Aucun besoin de pénaliser quiconque.

[Afyu]

Bref, c'est super tout ça, nous sommes contents que la manipulation de la chance vous ait intéressés, on en tiendra compte pour une prochaine fois.

Maintenant le seul et unique but du générateur aléatoire fourni ici, c'était pour vous permettre de reproduire et corriger les problèmes pendant la phase de participation.

Du coup c'est quoi la bonification pour ceux qui n'ont pas triché ?

Les mauvaises langues diront qu'on a pas su comment faire, mais en fait on est juste honnête nous !

La bonification c'est de ne pas avoir de détérioration (c'est quoi le contraire de "bonification" ?)

Moi j'avoue : j'ai pas su comment faire

[Tituya]

Bravo ! C'est la fin du concours de la rentrée, bravo aux participants qui le méritent amplement.
Merci beaucoup aux auteurs évidemment, un projet aussi gros doit être un enfer à gérer, et comme d'habitude, rien à dire !

Maintenant on veut les explications de chacun !

[Pavel]

Maintenant on veut les explications de chacun !

La plupart du temps, mon processus de développement a été assez chaotique. Les premières versions de mes scripts n'étaient pas très bien structurées. J'ai essayé d'ajouter et de supprimer des lignes de code, et j'ai imprimé et analysé les labyrinthes que mes scripts n'avaient pas réussi à résoudre.

J'ai commencé par implémenter les algorithmes que je pensais nécessaires pour résoudre ce labyrinthe:

• pour trouver les chemins les plus courts j'ai implémenté l'algorithme de remplissage par diffusion (flood-fill, https://www.youtube.com/watch?v=Zwh-QNlsurI). A ma connaissance, cet algorithme est très souvent utilisé pour naviguer dans des labyrinthes. Par exemple dans les compétitions de robots micromouse.
• pour identifier les corniches potentiellement dangereuses, j'analyse les corniches voisines et les voisines des voisines
• pour identifier la corniche avec la plus grande probabilité d'avoir Léviathan, je prends la corniche qui a plus de corniches voisines déjà visitées

Vers la fin du concours, j'ai plus ou moins débogué la plupart de mon code et j'ai réussi à trouver un algorithme relativement bien structuré qui fonctionne pas trop mal:

• mettre à jour les informations disponibles
• identifier la clé, les corniches potentiellement dangereuses et Léviathan
• calculer les poids de toutes les corniches (la clé et la porte ont les poids les plus élevés, les corniches sûres ont des poids plus élevés que les corniches dangereuses, etc)
• aller vers la corniche avec le poids le plus élevé
• si la corniche de destination n'est pas sûre et que le héros a une flèche, et qu'une corniche avec la plus forte probabilité d'avoir Léviathan est identifiée, alors attaquer Léviathan

Cet algorithme explore d'abord en profondeur les corniches sûres. Je n'ai utilisé aucun appel récursif car je pense que Python n'est pas optimisé pour ça.

Voici un diagramme de cet algorithme:


Vu les résultats de ce défi, je dirais que la plupart de cet algorithme fonctionne bien à l'exception des calculs de poids pour les puits. J'espère pouvoir améliorer cette partie en m'inspirant du code de CrimsonDeus.

Je tiens aussi à mentionner les parties les plus amusantes pour moi de ce défi:

• tester mes scripts sur TI-Nspire CX II (j'ai adoré l'aspect jeu vidéo de ce défi)
• prendre le contrôle mental des chauves-souris

[critor]

Ah, vous souhaitez déjà commencer les explications, bien.

Donc pour tout-le-monde.

Ce serait bien de préciser le type d'algorithme de parcours de graphe implémenté si connu : itératif / récursif, et largeur / profondeur.

Et pour illustrer les stratégies adoptées par votre IA, un diagramme serait à mon avis très pertinent. Par exemple :

[Pavel]

Et pour illustrer les stratégies adoptées par votre IA, un diagramme serait à mon avis très pertinent. Par exemple :

Avec quel programme peut-on dessiner des diagrammes comme celui-ci?

[NeOtuX]

Draw.io, en ligne ou en local. C'est de la bombe.

Gratuit, Open Source (Apache V2), stockage local uniquement etc etc.

[critor]

Et pour illustrer les stratégies adoptées par votre IA, un diagramme serait à mon avis très pertinent. Par exemple :

Avec quel programme peut-on dessiner des diagrammes comme celui-ci?

Moi c'est fait bêtement à la main sous LibreOffice, mais on peut sûrement trouver mieux.

[Pavel]

Merci. J'ai dessiné un diagramme dans PowerPoint Inkscape et mis à jour mon explication.

[critor]

Super, merci beaucoup à toi.