π
<-
Chat plein-écran
[^]

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

Online

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

Unread postby critor » 14 Dec 2020, 17:35

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. :p

Aucun besoin de pénaliser quiconque. :)
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 17.7%
 
Posts: 37933
Images: 10892
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

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

Unread postby Afyu » 14 Dec 2020, 18:00

cent20 wrote:
critor wrote: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" ?) :D

Moi j'avoue : j'ai pas su comment faire ^^
User avatar
AfyuVIP++
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 13.2%
 
Posts: 255
Images: 17
Joined: 30 Oct 2019, 19:17
Gender: Male
Calculator(s):
Class: plutôt, oui :)

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

Unread postby Tituya » 15 Dec 2020, 22:14

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 ! :p
User avatar
TituyaPremium
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 80.5%
 
Posts: 13
Joined: 15 Nov 2019, 00:02
Gender: Male
Calculator(s):
Class: DUT Info 1e Année

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

Unread postby Pavel » 16 Dec 2020, 23:12

Tituya wrote:Maintenant on veut les explications de chacun ! :p


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:
Image

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
Last edited by Pavel on 17 Dec 2020, 15:26, edited 6 times in total.
User avatar
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 46.9%
 
Posts: 85
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

Online

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

Unread postby critor » 16 Dec 2020, 23:41

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 :
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 17.7%
 
Posts: 37933
Images: 10892
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

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

Unread postby Pavel » 17 Dec 2020, 11:48

critor wrote: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?
User avatar
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 46.9%
 
Posts: 85
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

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

Unread postby NeOtuX » 17 Dec 2020, 12:00

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

Gratuit, Open Source (Apache V2), stockage local uniquement etc etc.
User avatar
NeOtuX
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 47.7%
 
Posts: 181
Joined: 18 May 2012, 08:58
Gender: Male
Calculator(s):

Online

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

Unread postby critor » 17 Dec 2020, 12:18

Pavel wrote:
critor wrote: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. :)
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 17.7%
 
Posts: 37933
Images: 10892
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

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

Unread postby Pavel » 17 Dec 2020, 13:04

Merci. J'ai dessiné un diagramme dans PowerPoint Inkscape et mis à jour mon explication.
Last edited by Pavel on 17 Dec 2020, 15:34, edited 2 times in total.
User avatar
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 46.9%
 
Posts: 85
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

Online

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

Unread postby critor » 17 Dec 2020, 13:31

Super, merci beaucoup à toi. :)
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 17.7%
 
Posts: 37933
Images: 10892
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti
GitHub: critor

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 10 guests

-
Search
-
Social
-
Featured topics
Remplace ton ancienne fx-92 Collège ou Graph 35 par la Graph 90+E couleur. Pour tout achat, Casio te rembourse 10€ en cas de retour de ta fx-92 Collège, ou 15€ en cas de retour de ta Graph 35. Etiquette de retour fournie, pas de frais de port à payer, même les anciens modèles et machines non fonctionnelles sont acceptées. En partenariat avec les Restos du coeur.
10€ remboursés par Casio sur l'achat de ta calculatrice Graph 35 d'ici le 30 Septembre 2021
Reprise de ton ancienne fx-92 Collège à 5€ ou Graph 35 à 10€. Même non fonctionnelle ou ancien modèle. Etiquette de retour fournie, pas de frais de port à payer. En partenariat avec les Restos du coeur.
Comparaisons des meilleurs prix pour acheter sa calculatrice !
25€ remboursés par Casio sur l'achat de ta calculatrice fx-CP400 d'ici le 31 Octobre 2021
3€ remboursés par Casio sur l'achat de ta calculatrice fx-92 Collège d'ici le 30 Septembre 2021
Découvre les nouvelles fonctionnalités en Python de l'OS 5.5 pour la 83PCE/84+C-T Python Edition
Découvre les nouvelles fonctionnalités en Python de l'OS 5.2 pour les Nspire CX II
Omega, le fork étendant les capacités de ta NumWorks, même en mode examen !
123456789
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
493 utilisateurs:
>484 invités
>4 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)