Journal Résolution naïve d'un jeu de société

Posté par Aluminium95 le 20 juillet 2015 à 21:29. Licence CC By‑SA.

Étiquettes :

juil.

2015

Sommaire

Explication du jeu
- Évaluation des stratégies
  - En avant
  - En arrière
Exploration naïve vers l'avant
Mise en perspective

Bonjour nal,
Aujourd'hui je vais te parler de résolution naïve d'un problème combinatoire, en explorant un arbre. Le problème vient d'un jeu de société, et la résolution se fera en Haskell, illustrant des notions intéressantes : Anamorphisme et Deforestation_(computer_science).

Explication du jeu

Le jeu du Ricochet Robots est un jeu de société constitué d'une grille de jeu, comportant des cases, avec des murs certains côtés, et certaines cases ayant un symbole d'une certaine couleur.

Quatre Robots (chacun d'une couleur différente) sont placés sur la grille à leur emplacement de départ.

Un objectif est tiré au hasard, il s'agit d'amener le robot désigné, sur la case désignée.

Pour amener le robot sur cette case, les joueurs peuvent utiliser tous les robots, et les déplacer sur la grille librement, en respectant « les mouvements des robots » :

Les robots se déplacent en ligne droite jusqu'à rencontrer un obstacle (mur/autre robot)

Les joueurs tentent de trouver une manière d'amener le robot sur la case. Le premier qui en trouve une annonce le nombre de coups nécessaires. Un chronomètre est alors déclenché et permet aux autres joueurs de disposer de 50 secondes pour améliorer le nombre de coups annoncés.

À la fin des 50 secondes, le joueur avec le moins de déplacements remporte le point et bouge effectivement les pièces sur le plateau, et un autre objectif est tiré.

Évaluation des stratégies

Un exemple de résolution

En avant

Un être humain va plutôt se concentrer sur les moyens de bouger la pièce concernée par l'objectif, et utiliser les autres comme « cales », afin de permettre certains mouvements. Cette méthode est compliquée à expliquer et théoriser, on va donc en extraire l'essence la plus simple.

On dit qu'à partir d'une configuration donnée, on regarde les mouvements possibles de toutes les pièces, et sélectionne les branches qui semblent mener à une combinaison plausible (ce qui vient avec l'expérience), ce en partant principalement sur des branches avec la pièce concernée par l'objectif.

L'arbre des mouvements possibles est un arbre de facteur de branchement 16, puisqu'à chaque étape il est possible de faire 16 mouvements (sans compter les mouvements inutiles à cause des murs) : 4 pièces et 4 directions sont possibles.

En arrière

Une autre stratégie est de regarder d'où peut provenir une pièce qui arriverait sur la case voulue, et chercher des mouvements plausibles (en mettant des cales, etc …) pour y arriver. Cette méthode est un peu moins intuitive à coder, mais pour un être humain, il est parfois « facile » de déterminer d'où peut probablement provenir la pièce, et remonter ainsi le chemin vers une case qui est plus facilement accessible.

Néanmoins, il faut noter que le joueur humain oscille souvent entre les deux méthodes, l'une permettant d'avancer, l'autre de simplifier le problème.

Exploration naïve vers l'avant

Le choix le plus simple est celui de la résolution en avant, puisqu'une description sous forme d'arbre est directement disponible.

L'idée est donc de faire une exploration intelligente de l'arbre, de manière à atteindre le plus facilement possible une solution, et de préférence optimale. Les deux types de parcours les plus courants sont :

Le parcours en largeur : efficace en temps
Le parcours en profondeur : efficace en espace

Le parcours en largeur permet de trouver facilement une solution optimale le plus rapidement possible. Contrairement au parcours en profondeur, qui ne trouvera pas directement une solution avec le moins de coups possible.

Définition de l'arbre

On commence par définir un arbre sans information dans les nœuds, et avec étiquettes de transitions, de la manière la plus simple possible :

data Tree a = N [(a, Tree a)]

Construction d'un arbre

Si on regarde le type de construction, on se rend compte que

N :: [(a, Tree a)] -> Tree a

Si on « généralise le type » on arrive à une fonction à deux paramètres :

data Tree' a b = N' [(a, b)]
N' :: [(a, b)] -> Tree' a b

On a la correspondance Tree a = Fix (Tree' a) pour ceux qui connaissent cet opérateur. En effet, on se rend compte que :

Tree a = Tree' a (Tree a) = Tree' a (Tree' a (Tree a)) ...

L'idée est donc de « faire pousser un arbre » avec l'opérateur N' appliqué un certain nombre de fois. La fonction de « pousse » aura donc le type :

pousse :: (b -> [(a, b)]) -> b -> Tree a

Prenant une fonction qui va générer un nœud de type Tree' à partir d'une graine b, et d'une graine initiale.

Pour des raisons de types, on n'arrivera jamais à transformer le type Tree' en Tree avec un nombre « fini » d'étapes, donc il faut changer de stratégie, et utiliser une définition récursive pour notre fonction pousse :

pousse branche graine = N $ map traiteSousBranche liste 
    where
        liste                            = branche graine 
        traiteSousBranche (x,sousGraine) = (x, pousse branche sousGraine)

Fonction de construction

Maintenant que l'on a un moyen de faire pousser naturellement des arbres, on peut se demander si cette fonction est assez générique pour construire le seul arbre qui nous intéresse ici : l'arbre des déplacements !

On commence par donner les deux trois choses importantes :

data Piece = Rouge | Vert | Bleu   | Gris deriving (Eq,Show,Read,Enum)
data Depl  = Haut  | Bas  | Droite | Gauche deriving (Eq,Show,Read,Enum)

data Move = Move Piece Depl deriving (Eq,Show,Read)

Ensuite, on peut se demander quelles sont les options à chaque branche :

options :: [Move]
options =  [ Move p d | p <- [Rouge .. Gris],
                        d <- [Haut  .. Bas ] ]

Maintenant une question se pose : quel est le type de notre fonction de construction ?

On sait déjà qu'elle doit avoir une signature dans la famille b -> [(a,b)], avec b le type d'une graine qui génère une branche, et a les étiquettes qui seront vraiment dans l'arbre.

L'arbre que l'on veut construire est du type Tree Move, donc a = Move, la question est donc : mais que « vaut » b ? En réalité, n'importe quel type convient, car à chaque branchement, on a exactement les mêmes mouvements possibles (comme expliqué au début) : aucune graine n'est nécessaire !

Le type sera donc rien : b = ().

arbreFunc :: () -> [(Move, ())]
arbreFunc _ = map (flip (,) ()) options

Remarque : l'arbre que l'on construit ici est infini parce qu'à
chaque étape on ajoute de nouvelles branches. Si on veut un arbre
fini, il faut que pour chaque branche, on arrive un jour à une liste vide …

Parcours en largeur

L'idée du parcours en largeur est la suivante : à chaque étape, je parcours les nœuds d'un étage. Quand je le fais, je note les nœuds de l'étage suivant, ce qui me permet de savoir quel étage traiter à l'étape suivante. Pour cela on utilise souvent une file, en ajoutant au fur et à mesure les fils.

Ici, on va procéder différemment, on ne va pas coder un parcours en profondeur, mais simplement une fonction, qui va « suivre » certaines branches. On veut descendre d'un niveau dans l'arbre, en gardant pour chaque branche une information additionnelle : l'historique des modifications, et la disposition du plateau qui en résulte (pour ne pas la recalculer à chaque fois). Le type de donnée que l'on veut est alors tout simplement :

branchesSuivies :: [ (b, Tree a) ]

Avec b une information additionnelle (ici l'historique des mouvements pour simplifier).

Pour passer au niveau suivant, c'est alors très simple, mais il faut savoir ce que l'on veut. On veut aussi modifier l'historique, donc on veut une fonction du type :

nouvellesBranchesSuivies :: (b, Tree a) -> [ (b, Tree a) ]

Cette fonction permettant de dire comment ajouter les nouvelles branches qui sont suivies. Le type de la fonction « suivre » est alors tout simple

suivre :: ((b,Tree a) -> [(b,Tree a)]) -> [(b, Tree a)] -> [(b, Tree a)]

Cette signature un peu compliquée peut se généraliser facilement pour mieux en comprendre l'essence :

suivre :: (c -> [c]) -> [c] -> [c]

On dispose alors de fonctions très génériques qui vont faire le travail à notre place :

map :: (a -> b) -> [a] -> [b]
concat :: [[a]] -> [a]

Une simple analyse nous montre alors que :

l :: [c]
f :: (c -> [c])

map f l :: [[c]]

concat (map f l) :: [c]

Par conséquent un candidat évident (et qui est la bonne manière de faire en plus) est

suivre f = concat . map f

Notre fonction de suivi

Reste maintenant à écrire notre fonction de suivi de branches, c'est relativement simple, puisque l'on sait ce que l'on veut :

On veut un historique [Move]
L'arbre est de type Tree Move

On code donc assez naturellement la fonction

suivreBranches :: [Move] -> Tree Move -> [([Move], Tree Move)]
suivreBranches historique (N l) = map (\(x,y) -> (x : historique, y)) l

Mettre de l'ordre dans tout cela

Où en est-on de la résolution du problème ? Et bien en réalité on a presque terminé … Enfin, il reste seulement une étape (pénible et très peu théorique) : à chaque fois que l'on descend d'un niveau, il faut vérifier si on a bien une solution gagnante.

Pour cela il faut :

Avoir une grille (la construire)
Savoir déplacer les robots dessus (ie : calculer les nouvelles positions)
Avoir un objectif
Faire que tout marche bien …

Ce n'est pas dur, simplement long.

Mise en perspective

On peut remarquer qu'à partir du moment où on sait déjà bouger des robots sur la grille, on sait si des mouvements sont impossibles (ie : ne bougent en réalité pas le pion), ce qui permet de tuer un certain nombre de branches directement. Les robots ne pouvant se stopper que contre un obstacle, il y a très souvent une des directions qui n'est pas possible, ce qui fait tomber de « branching-factor » à 12 (ce qui est non négligeable !).

Ainsi, plutôt que de construire un arbre Tree Move on peut construire un arbre de type Tree ([Move], Placement) qui permet à notre fonction qui fait pousser l'arbre d'avoir accès au placement, et donc de tuer directement les branches inutiles (et permet d'avoir une fonction d'aplatissement encore plus simple !).

De même, on peut remarquer que construire l'arbre est inutile, et qu'on peut le faire pousser en même temps que l'on regarde si on trouve des solutions ! À ce moment là, on comprend pourquoi le type list est aussi dit « monade non-déterministe » :

options :: [Move]

cheminsPossibles :: ([Move], Placement) -> [([Move], Placement)]

avancer :: [([Move], Placement)] -> [([Move], Placement)]
avancer = concat . map cheminsPossibles 

trouveSolution :: [([Move], Placement)] -> Maybe ([Move], Placement)

resolution l = case trouveSolution l of 
                    Nothing -> resolution (avancer l)
                    Just s  -> s

Ce qui est un code plus concis où l'arbre intermédiaire a été retiré. On parle ici de « déforestation », c'est à dire suppression des structures intermédiaires de calcul dans un programme.

# Version ASP (Answer Set Programming)

Posté par eingrossfilou le 20 juillet 2015 à 22:13. Évalué à 2.

Si ça t'intéresse, tu as une modélisation de ton problème en Answer Set Programming (ASP) ici.
- [^] # Re: Version ASP (Answer Set Programming)
  
  Posté par Aluminium95 le 20 juillet 2015 à 23:37. Évalué à 1.
  Merci, c'est intéressant.
  Je ne connaissait pas ASP, mais après une rapide recherche, c'est purement déclaratif, et donc c'est « l'interpréteur » qui s'occupe de faire la véritable exploration si j'ai bien compris, alors que mon objectif était de faire un parcours en largeur à gros coup de concat . map.
  
  Après, c'est un avis personnel, mais c'est assez déconcertant de lire les « programmes » proposés sur la page wikipédia Answer set programming. C'est sûrement une question d'habitude toutefois.
  
  Du coup, quel est l'avantage d'ASP par rapport à une bibliothèque de résolution en python par exemple ? Parce qu'il y a quand même des désavantages :
  1. Pas d'interaction utilisateur possible en restant déclaratif
  2. Le debug du programme se fait via les options fournies pas l'interpréteur
  3. Quid de l'intégration dans un véritable programme (par exemple en tant qu'IA dans un jeu interactif) ?
  - [^] # Re: Version ASP (Answer Set Programming)
    
    Posté par eingrossfilou le 21 juillet 2015 à 01:25. Évalué à 4.
    Je ne connaissait pas ASP, mais après une rapide recherche, c'est purement déclaratif, et donc c'est « l'interpréteur » qui s'occupe de faire la véritable exploration si j'ai bien compris, alors que mon objectif était de faire un parcours en largeur à gros coup de concat . map.
    
    C'est à peu près ça, même si on va dire que la définition française proposée par Wikipédia est très limitée. La version anglaise est mieux.
    L'idée ici était surtout de te proposer une autre manière de rechercher des solutions à ricochet robots (essentiellement à des fin de comparaison, mais aussi parce ricochet robots c'est cool et qu'il n'y a pas beaucoup d'IA pour ce jeu)
    
    ASP est un formalisme qui permet de faire de la programmation par contrainte et de l'optimisation au travers de la programmation logique. Généralement, on s'en sert pour résoudre de problème NP-complet. Ton programme ASP est une description de ton problème sous forme logique. Ensuite cherche des solutions à ton problème en utilisant un solveur auquel tu donneras la définition du problème, les données, et éventuellement une stratégie de recherche (comme un parcours en largeur ou en profondeur de l'espace de recherche par exemple).
    
    Si le sujet t'intéresse davantage, tu pourras consulter les cours disponibles ici quand sourceforge tombera en marche.
    
    Du coup, quel est l'avantage d'ASP par rapport à une bibliothèque de résolution en python par exemple ? Parce qu'il y a quand même des désavantages :
    
    ASP est prévu pour faire de la programmation logique, comme python est prévu pour faire de la programmation impérative. En fonction de ce que tu cherches à faire, l'un est plus adapté que l'autre, mais rien ne t'empêche de faire un solveur en python (ou haskell), c'est un bon exercice. D'ailleurs je trouve ta démarche super bien.
    Pas d'interaction utilisateur possible en restant déclaratif
    Alors, ça c'est hors de la partie résolution du problème. Généralement, tu branches le solveur à autre chose. Par exemple tu peux utiliser ASP (gringo et clasp) avec python. Après, en fonction de ton solveur, tu as des fonctions de contrôle pour interagir avec le solveur lui-même (par exemple interrompre le calcul ou obtenir un résultat intermédiaire suboptimal)
    Le debug du programme se fait via les options fournies pas l'interpréteur
    Normalement, ton programme est un ensemble de définitions mathématiques. Pour vérifier que tout fonctionne bien, tu fais des preuves. Au pire tu utilises des exemples représentatifs de tes différents cas de figure. Si tu as un soucis avec les résultats, c'est soit que qu'il y a un problème dans tes définitions, soit que le solveur contient une erreur. Il arrive aussi que tu te plantes dans le résultat attendu d'un de tes exemples.
    Quid de l'intégration dans un véritable programme (par exemple en tant qu'IA dans un jeu interactif) ?
    Là encore, ça ne dépend que de comment tu modélises ton IA. Le solveur est juste une brique à laquelle tu te branches à l'aide de bibliothèques ou de wrappers et à laquelle tu va faire des "requêtes". En fonction de tes contraintes, tu choisiras un solveur plutôt qu'un autre. Dans le cas de ricochet robots,tu peux visez un solveur qui, pour chaque cible, te donnes une réponse (1) optimale quand il a parcouru tout l'espace de recherche ou (2) une réponse suboptimale (et peut-être optimale) quand tu lui demandes (comme au bout des 50 secondes après la réponse du premier joueur).
    Tu peux aussi envisager que ton solveur ne parcours pas tout l'espace de recherche, mais parcours juste ton espace de recherche de façon aléatoire. Dans ce cas, tu ne pourras jamais dire qu'il n'a pas de solution, mais dans le cas de ricochet robots, il me semble qu'il existe toujours une solution.
    
    J'espère que c'est assez clair.
    - [^] # Re: Version ASP (Answer Set Programming)
      
      Posté par Aluminium95 le 21 juillet 2015 à 14:05. Évalué à 1.
      C'est très clair merci, en gros tu fais des requêtes un peu comme avec une BDD, sur du code qui est écrit en ASP.
      
      La question est donc la suivante : est-ce que l'apprentissage du langage est vraiment un plus ?
      
      Il faut apprendre plusieurs langages et les faire cohabiter, ce qui fait plus de dépendances pour le programme à l'installation, et nécessite un apprentissage supplémentaire
      
      Il y a une dépendance à un outil externe de résolution sur lequel il est difficile d'avoir du contrôle (en tout cas moins de contrôle que sur une bibliothèque). Si jamais on veut une nouvelle option, il faut soit :
      
      La demander au développeur et attendre qu'elle soit intégrée
      
      La coder soi-même, vraisemblablement dans un troisième langage, en reprenant le code du projet
      
      Je vois tout de même certains avantages :
      
      Un langage unifié pour ce type d'algorithme
      
      Un langage spécifique qui facilite la description/résolution du problème
      
      Une décorrélation entre la résolution et le reste du programme
      
      Pour l'instant, je ne pense pas que les avantages justifient les inconvénients pour mon utilisation.
- [^] # Re: Version ASP (Answer Set Programming)
  
  Posté par benoar le 23 juillet 2015 à 14:19. Évalué à 3.
  
  Au début je me suis dit « Tiens c'est quoi ce nouveau truc », puis je suis allé voir : en fait, c'est vieux comme le monde, c'est un dérivé de Prolog…
# une proposition

Posté par palm123 (site web personnel) le 21 juillet 2015 à 09:15. Évalué à 2.

s/ajouter les nouvelles qui sont branches suivies/ajouter les nouvelles branches qui sont suivies

ウィズコロナ
- [^] # Re: une proposition
  
  Posté par Benoît Sibaud (site web personnel) le 21 juillet 2015 à 09:42. Évalué à 3.
  
  Corrigé, merci.
# Remarques

Posté par barmic le 21 juillet 2015 à 09:49. Évalué à 6. Dernière modification le 21 juillet 2015 à 09:50.
J'ai 4 petites remarques :
- il me semble important de savoir déterminer s'il existe une solution (si la case cible est au milieu et qu'il n'y a aucun mur alors il n'y a pas de solution par exemple)
- comment t'assure-tu de ne pas boucler ?
- j'aurais plutôt tendance à créer un arbre de configuration (chaque nœud de l'arbre est un ensemble de 4 coordonnées)
- il est possible de faire de la mémoïsation pour encore tronçonner le parcours de ton arbre (en fait sur un parcourt en largeur ça permet surtout d'éviter les boucles)
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
- [^] # Re: Remarques
  
  Posté par Guillaume Rossignol le 21 juillet 2015 à 11:34. Évalué à 3.
  
  il me semble important de savoir déterminer s'il existe une solution (si la case cible est au milieu et qu'il n'y a aucun mur alors il n'y a pas de solution par exemple)
  
  Pas tout à fait, il est possible d'empiler les robots les uns sur les autres, puis retirer le premier de l'empilement pour qu'il se réempile par dessus. Du coup, même un objectif au milieu peut être atteignable.
- [^] # Re: Remarques
  
  Posté par Aluminium95 le 21 juillet 2015 à 12:48. Évalué à 2.
  il me semble important de savoir déterminer s'il existe une solution (si la case cible est au milieu et qu'il n'y a aucun mur alors il n'y a pas de solution par exemple)
  
  Ce n'est pas un problème si facile : pour déterminer si une position est impossible à atteindre, soit on cherche une solution et on en trouve pas (ce qui ne veut pas dire grand chose vu que l'arbre est infini). Soit on part de la fin et on fait la méthode « en arrière » :
  - Pour arriver à cette case, quels sont les directions possibles
  - Pour chacune des directions, quelles sont les cases concernées où je dois amener le pion pour pouvoir faire ce mouvement
  - Pour chaque case concernée, quelles sont les « cales » possibles ?
  - Pour chaque couple (pion,cale) avec un pion différent du pion initial, on a un nouvel objectif
  - appel récursif
  Remarque : ici je ne prend pas en compte les murs, il faudrait ajouter, pour le premier mur rencontré dans chaque direction, un objectif.
  
  On s'arrête quand on trouve :
  1. Une solution triviale (le pion à déplacer est sur une des directions)
  2. Un mouvement impossible : et là, comment le déterminer ? On revient au problème de départ, à priori, je n'ai pas de méthode simple pour déterminer un mouvement impossible … Sauf si à une étape on ne change pas l'ensemble des objectifs à atteindre : ce qui veut dire que l'on est dans une « boucle de dépendance » du jeu qui ne terminera jamais.
  comment t'assure-tu de ne pas boucler ?
  
  Dans le code naïf proposé, on repasse parfois par les mêmes placements de pions, mais c'est en largeur, du coup ce n'est pas vraiment une boucle, seulement, on est certain d'avoir branches à l'étape ce qui est très peu intéressant.
  
  Étant donné qu'un placement est simplement un 4-uplet, on peut facilement faire un ensemble des positions déjà rencontrées, pour éviter de refaire les mêmes mouvements plusieurs fois. Je ne sais pas à quel est le gain réel de cette méthode, mais elle est facile à mettre en place.
  
  Le coût d'une telle méthode est relativement moindre, puisqu'on va enregistrer des couples, et qu'à l'étape on aura au pire un nombre de configuration de l'ordre de grandeur de , ce qui ne change donc pas la complexité spatiale du programme.
  
  j'aurais plutôt tendance à créer un arbre de configuration (chaque nœud de l'arbre est un ensemble de 4 coordonnées)
  
  C'est intéressant, mais la réponse attendue n'est pas le placement final des pions, mais bien la suite de mouvements qui y mène … Donc si tu disposes seulement des placements, il te faut ensuite calculer les mouvements qui font la transition entre deux placements … Alors que l'autre sens est « trivial » (calculer le placement final à partir des mouvements).
  
  il est possible de faire de la mémoïsation pour encore tronçonner le parcours de ton arbre
  
  Donc, cela rejoint la mise en place d'un ensemble de positions déjà vues, pour ne pas créer des branches inutiles. À moins qu'il existe un autre moyen de mémoïser ?
  - [^] # Re: Remarques
    
    Posté par Patrick Nicolas le 21 juillet 2015 à 13:54. Évalué à 2.
    
    Le nombre de situations possibles est égal au nombre de cases puissance le nombre de pions (moins en réalité puisqu'ils ne peuvent pas se superposer).
    On est donc à 4*10^9, il est donc possible de mémoriser les situations déjà visitées et donc déterminer si une situation est atteignable.
    - [^] # Re: Remarques
      
      Posté par Aluminium95 le 21 juillet 2015 à 14:11. Évalué à 1.
      
      On est donc à 4*10^9, il est donc possible de mémoriser les situations déjà visitées et donc déterminer si une situation est atteignable.
      
      C'est peut-être évident … mais comment expliques-tu le « donc » dans ta phrase ?
      
      J'avais proposé (pour la méthode en arrière) :
      
      Sauf si à une étape on ne change pas l'ensemble des objectifs à atteindre : ce qui veut dire que l'on est dans une « boucle de dépendance » du jeu qui ne terminera jamais.
      
      Ce qui serait l'équivalent de (pour la méthode en avant) de : « on ne trouve pas de nouvelles branches à visiter ». Dès lors, avec l'amélioration proposée (qui permet de ne pas revisiter des placements) il suffit de vérifier si à une étape la liste des branches à suivre est vide.
      
      C'est bien ce à quoi tu pensais ?
      - [^] # Re: Remarques
        
        Posté par barmic le 21 juillet 2015 à 14:44. Évalué à 4.
        
        C'est peut-être évident … mais comment expliques-tu le « donc » dans ta phrase ?
        
        Si ton arbre est constitué de configurations comme j'en parlais dans mon premier commentaire, tu va itérer sur les les configurations possibles depuis tes configurations possibles en ayant retirer les configurations que tu as déjà calculées.
        
        Je sais pas si c'est bien clair, mais l'idée c'est que si tu fais attention à ne pas calculer quelque chose que tu as déjà calculer, alors ton calcul est nécessairement fini.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: Remarques
        
        Posté par Aluminium95 le 21 juillet 2015 à 15:27. Évalué à 1.
        
        Donc j'avais bien compris : pour savoir s'il y a une solution, tu dois parcourir intégralement l'arbre (dans un sens ou dans l'autre), or retirant les doublons, il est fini, donc il est possible de savoir s'il existe une solution. Mais du coup c'est le même algorithme qui donne la solution et l'existence d'une solution.
        
        [^] # Re: Remarques
        
        Posté par Patrick Nicolas le 21 juillet 2015 à 17:43. Évalué à 1.
        
        Effectivement c'est pas aussi direct.
        La taille acceptable du nombre de situations permet de terminer l'exploration si on atteint une situation qui a déjà été atteinte. On peut donc continuer à explorer jusqu'à ce que la solution soit trouvée ou toutes les branches se terminent sur une position déjà parcourue.
  - [^] # Re: Remarques
    
    Posté par barmic le 21 juillet 2015 à 14:50. Évalué à 4.
    
    Dans le code naïf proposé, on repasse parfois par les mêmes placements de pions, mais c'est en largeur, du coup ce n'est pas vraiment une boucle, seulement, on est certain d'avoir 16ⁿ branches à l'étape n ce qui est très peu intéressant.
    
    Par boucle j'entends : comment vérifie tu que tu n'a pas de cycle dans ton arbre.
    
    Étant donné qu'un placement est simplement un 4-uplet, on peut facilement faire un ensemble des positions déjà rencontrées, pour éviter de refaire les mêmes mouvements plusieurs fois. Je ne sais pas à quel est le gain réel de cette méthode, mais elle est facile à mettre en place.
    
    C'est gratuit quand c'est l'essence de ton arbre et je vois pas d'autre manière de garantir que tu n'ai pas de cycle dans ton arbre.
    
    C'est intéressant, mais la réponse attendue n'est pas le placement final des pions, mais bien la suite de mouvements qui y mène … Donc si tu disposes seulement des placements, il te faut ensuite calculer les mouvements qui font la transition entre deux placements … Alors que l'autre sens est « trivial » (calculer le placement final à partir des mouvements).
    
    C'est un calcul trivial (déterminer un coup à partir de 2 configurations est très simple), d'une complexité linéaire. Donc ça ne change pas grand chose à ce niveau là.
    
    Donc, cela rejoint la mise en place d'un ensemble de positions déjà vues, pour ne pas créer des branches inutiles. À moins qu'il existe un autre moyen de mémoïser ?
    
    Il en existe peut être d'autre, mais c'est ce que j'avais en tête.
    
    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
    - [^] # Re: Remarques
      
      Posté par Aluminium95 le 21 juillet 2015 à 15:33. Évalué à 1.
      Par boucle j'entends : comment vérifie tu que tu n'a pas de cycle dans ton arbre.
      
      Je ne comprends pas … Un arbre ne peut pas contenir de cycle (enfin, sinon c'est plus un arbre) : Arbre_(graphe).
      
      Donc, ce que je comprend quand tu dis « cycle », c'est retrouver une même configuration à deux niveaux différents dans l'arbre (qui auront donc les mêmes fils) :
      
      A ---> B ---> ... C ---> ... D ---> A ---> Ici on aura encore le même arbre
      
      Et là je suis totalement d'accord avec toi sur la suite : il faut les retirer !
      - [^] # Re: Remarques
        
        Posté par barmic le 21 juillet 2015 à 16:03. Évalué à 4.
        
        Par boucle j'entends : comment vérifie tu que tu n'a pas de cycle dans ton arbre.
        
        Je ne comprends pas … Un arbre ne peut pas contenir de cycle (enfin, sinon c'est plus un arbre) : Arbre_(graphe).
        
        Désolé je suis aller un peu vite la phrase précise aurait était « comment vérifie-tu que tu parcourt bien un arbre et pas un graphe ? »
        
        Donc, ce que je comprend quand tu dis « cycle », c'est retrouver une même configuration à deux niveaux différents dans l'arbre (qui auront donc les mêmes fils) :
        
        Pour être précis (du coup) c'est qu'il ne faut pas avoir 2 configurations identiques dans une même branche.
        
        A ---> B ---> E C ---> ... D ---> F ---> E Ici on aura encore le même arbre
        
        est un arbre.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: Remarques
        
        Posté par Aluminium95 le 21 juillet 2015 à 17:11. Évalué à 1. Dernière modification le 21 juillet 2015 à 17:12.
        
        « comment vérifie-tu que tu parcourt bien un arbre et pas un graphe ? »
        
        Je ne le vérifie pas justement :-). Par construction c'est un arbre : il n'y a pas de « pointeurs » vers un étage plus haut, à chaque fois c'est un véritable nouveau nœud qui est crée, donc on ne peut que descendre. Par contre, on rencontre des nœuds qui contiennent la même information, ce qui est redondant pour l'exploration.
        
        Aussi, comme précisé, comme je ne supprime pas les informations redondantes, il est infini (mais en haskell cela ne pose pas de problème).
        
        [^] # Re: Remarques
        
        Posté par barmic le 21 juillet 2015 à 18:19. Évalué à 6.
        
        Je parlais de la logique et pas de l'implémentation. Donc ce que tu fais c'est parcourir un graphe avec une API d'arbre. C'est ce qui fait que ton arbre est infini.
        
        mais en haskell cela ne pose pas de problème
        
        Le fait qu'haskell soit fainéant n'empêche pas de trancher ton arbre pour :
        
        s'assurer que ton algorithme termine
        
        optimiser le temps de recherche
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# Intéressant, mais Haskell

Posté par Thibault Taillandier le 21 juillet 2015 à 12:57. Évalué à 4.

Salut,

Alors j'aime beaucoup ton journal car ça parle algorithmie et parce que je connais bien Ricochet Robots.

En revanche, je n'ai quasiment aucune notion de programmation fonctionnelle, et je ne connais Haskell que de nom. Du coup toute la partie intéressante devient assez obscure. Dommage pour moi.

Merci en tout cas pour cette belle recherche !

Bonne journée,
- [^] # Re: Intéressant, mais Haskell
  
  Posté par j_m le 21 juillet 2015 à 13:26. Évalué à 5.
  
  C'est justement le Haskell et le fonctionnel qui font l'intérêt du journal. Le procédural tout le monde connaît, pas besoin d'en parler.
  - [^] # Re: Intéressant, mais Haskell
    
    Posté par Aluminium95 le 21 juillet 2015 à 13:53. Évalué à 2.
    
    En effet, c'était un prétexte pour parler de unfold pour les arbres et bind pour les listes.
    
    Mais sa remarque est quand même pertinente, car un langage plus connu aurait peut-être rendu le contenu plus accessible …
- [^] # Re: Intéressant, mais Haskell
  
  Posté par Aluminium95 le 21 juillet 2015 à 13:49. Évalué à 4.
  Du coup toute la partie intéressante devient assez obscure. Dommage pour moi.
  
  Aïe, c'est dommage, je ne voulais pas que ce soit un obstacle … J'avais pourtant essayé de ne pas trop faire de trucs abscons …
  
  Le problème, c'est que la plus grande partie du code est basée sur les types, qui permettent de se guider pour coder les fonctions. D'ailleurs, cela permet de ne pas s'embrouiller, et de « matérialiser » les idées autrement que par le code : on ne désire pas coder une fonction, mais trouver une fonction qui a le type X, si possible en combinant des briques déjà présentes.
  
  J'aurais pu le faire en python, mais il est plutôt laxiste sur les types (ce qui est parfois très utile), donc raisonner sur les types aurait été plutôt étrange.
  
  Sinon, pour faire court, la fin (où on a retiré l'arbre intermédiaire) s'écrit très simplement en python par exemple (ici c'est naïf, aucune optimisation) :
```
pions = ["Rouge", "Bleu", "Vert"  , "Gris"]
direc = ["Haut" , "Bas" , "Droite", "Gauche"]

# branchesSuivies :: [ [(pion,direc)] ]
# liste des historiques des branches (sans le placement des pions)
def avance (branchesSuivies):
    t = []
    for historique in branchesSuivies:
        for p in pions:
            for d in direc:
                t.append ([(p,d)] + historique)
    return t

def estUneBonneConfig (pion,case,historique):
    ... # ici il faut avoir une grille et vraiment déplacer les pions
    return False / True

def trouveBonneConfig (pion,case,branchesSuivies):
    for b in branchesSuivies:
        if estUneBonneConfig (pion,case,b):
            return b
    return False

def resolution (pion,case):
    b = [ [] ] # Branches initiales : une vide !
    while True:
        b = avance (b)
        f = trouveBonneConfig (pion,case,b)
        if f != False:
            return f
```
  Mais ici, on voit bien que j'ai « recodé » toutes les fonctions à la main, et sans trop m'intéresser aux types …
  
  Sinon, est-ce que tu pourrais indiquer donner les passages qui posent problème, pour pouvoir les ré-écrire dans un style plus compréhensible ?
  
  Bonne journée aussi !
  - [^] # Re: Intéressant, mais Haskell
    
    Posté par Anthony Jaguenaud le 21 juillet 2015 à 14:22. Évalué à 5.
    Le début ça va à peu près, mais je lache sur la construction de l’arbre avec N' et Tree'.
```
Tree a = Tree' a (Tree a) = Tree' a (Tree' a (Tree a)) ...
```
    - [^] # Re: Intéressant, mais Haskell
      
      Posté par Aluminium95 le 21 juillet 2015 à 16:09. Évalué à 2.
      Oh, ce n'est pas vraiment spécifique à Haskell ça. En fait, tu as un type récursif :
      
      data Tree a = Node [(a,Tree a)]
      
      Or traiter un type récursif c'est pas toujours facile. Du coup tu généralise, en regardant son homologue non récursif :
      
      data Tree' a b = Node' [(a,b)]
      
      On remarque que le deuxième est un type « normal », c'est à dire non récursif. Tu peux ensuite (formellement) écrire
      
      Tree a <=> Tree' a (Tree a)
      
      Car on remplace b par Tree a et on a des structures identiques (au nom du constructeur près).
      
      Pour simplifier, on peut prendre le type liste :
      
      data Liste a = Cons a (Liste a) | Vide
      
      Sa contrepartie non-récursive est
      
      data Paire a b = Cons' a b | Vide
      
      Et on remarque bien que : Liste a <=> Paire a (Liste a).
      Mieux tu peux définir le type récursif comme étant le type T a tel que Paire a (T a) = T a. Ce qui se comprend comme : une liste c'est un type tel que si je le met dans une paire, c'est encore une liste.
      
      Quel intérêt ? Et bien, cela donne automatiquement une manière de « faire pousser » la structure. Pour nous c'était un arbre, pour la liste c'est pareil, il existe une fonction unfold qui permet de le faire.
      
      Par exemple, on déduit la signature de unfold pour les listes :
      
      Paire a b = Cons' a b | Vide Liste a <=> Fixe (Paire a) unfoldFinal :: b -> Liste a -- Ce que l'on veut f :: (b -> Paire a b) -- Ce que l'on sait faire unfold :: (b -> Paire a b) -> b -> Liste a
      
      Mieux, tu as aussi l'inverse (ie : partir d'une liste et arriver à une valeur).
      
      foldFinal :: Liste a -> b -- Ce que l'on veut f :: Paire a b -> b -- Ce que l'on sait faire fold :: (Paire a b -> b) -> Liste a -> b -- Exemple d'utilisation quand a = b = Nombre somme :: [Nombre] -> Nombre -- Ce que l'on veut add :: Paire Nombre Nombre -> Nombre -- Ce que l'on sait faire add Vide = 0 add (Cons' x y) = x + y somme liste = fold add list
      
      Il faudrait que je retrouve un article qui en parlait de manière plus générale. En tout cas la page wikipédia anglaise est assez bien faite.
      - [^] # Re: Intéressant, mais Haskell
        
        Posté par Anthony Jaguenaud le 21 juillet 2015 à 17:43. Évalué à 3. Dernière modification le 21 juillet 2015 à 17:43.
        
        J’ai lu sur haskell principalement apprendre haskell vous fera le plus grand bien et on trouve une explication à la syntaxe ici.
        Je suis plus géné par la grammaire que je maîtrise mal (très mal?). Les types récursifs, en C on le fait avec des pointeurs, en C++ on doit pouvoir en générer avec des templates pour quelque chose de statique.
        
        Je vais reprendre posément pour essayer de comprendre.
        
        [^] # Re: Intéressant, mais Haskell
        
        Posté par chimrod (site web personnel) le 21 juillet 2015 à 20:48. Évalué à 3.
        
        Il ne faut pas réduire le fonctionnel à des types récursifs…
        
        C'est aussi une plongée dans la théorie des types et les concepts mathématiques qui peuvent être peuvent être mis en application par ailleurs. Si ton but est comprendre ses concepts, je te recommande chaudement la lecture du typeclassopedia qui devrait te donner une vision beaucoup plus avancée du langage.
        
        [^] # Re: Intéressant, mais Haskell
        
        Posté par Aluminium95 le 21 juillet 2015 à 21:14. Évalué à 2.
        
        Les types récursifs, en C on le fait avec des pointeurs
        
        Je crois comprendre la difficulté alors. Le fait est que en C tu penses à la construction effective du type, alors que là c'est purement théorique. On peut même l'écrire « mathématiquement » de manière indépendante du langage sous-jacent : un type est un ensemble de valeurs, et un type paramétré est une fonction qui prend en argument des types pour en construire un autre.
        
        Quand tu parles de pointeurs, tu rentres déjà dans le détail de la réalisation. C'est le constructeur ! Par exemple, quand on écrit :
        
        data Tree a = Node [(a, Tree a)]
        
        On dit au compilateur : quelque soit le type a que tu me donnes, je peux construire un nouveau type Tree a, et pour le construire j'utilise la fonction Node, à laquelle je donne une liste de couples de type (a, Tree a). La définition est récursive, car pour construire un élément de type Tree a, je peux avoir besoin d'en construire un de type Tree a … Mais en pratique, la construction se fait « à la main » de manière très simple :
        
        vide :: Tree a -- ici le type a est quelconque, vide est un élément « commun à tous les types d'arbres » vide = Node [] -- C'est bien un arbre valide, selon la construction donnée simple :: Tree Int -- ici on spécifie le type simple = Node [(8, vide)] -- C'est bien un arbre, car vide est un arbre !
        
        Au final, ce sont effectivement des pointeurs : la structure Node contient un pointeur vers une liste, qui est elle même simplement chaînée par des pointeurs. Les valeurs de la listes sont des pointeurs vers des couples de pointeurs … etc. Mais cette considération est « inutile » au niveau où on travaille.
        
        [^] # Re: Intéressant, mais Haskell
        
        Posté par Anthony Jaguenaud le 21 juillet 2015 à 23:35. Évalué à 2.
        
        Je crois comprendre la difficulté alors.
        
        Nous voyons tous le monde à travers nos connaissances… Ce que je voulais exprimer c’était surtout que la grammaire du C ne permettait pas ce genre de construction simple.
        
        Sur des constructions comme ça, il faut réfléchir quand on manque d’habitude, et ce n’est pas simple. Mais j’essaye de progresser quand même ;-)
      - [^] # Re: Intéressant, mais Haskell
        
        Posté par max22 le 23 juillet 2015 à 20:29. Évalué à 1.
        
        Je ne comprends pas trop pourquoi tu dis que traiter un type récursif n'est pas facile. Les listes en Haskell c'est un type récursif, c'est pas dur à traiter pourtant.
        
        [^] # Re: Intéressant, mais Haskell
        
        Posté par Aluminium95 le 23 juillet 2015 à 22:50. Évalué à 2.
        
        En fait, c'est pour construire la fonction : raisonner directement sur le type récursif est moins évident que d'utiliser sa contrepartie qui ne l'est pas. On peut plus facilement trouver les idées qui vont mener au code : ici pour savoir « comment faire pousser un arbre ». On peut le faire sans, mais à mon avis l'enchaînement logique est beaucoup plus simple (ça coule tout seul) quand on regarde la version non récursive.
        
        D'ailleurs, en haskell, on utilise souvent pour les listes les fonctions fold, unfold, filter, map. Or les deux dernières se codent à partir d'un fold facilement, donc on les enlève. Maintenant, regardons le type de fold et unfold, que font ces fonctions ?
        
        fold :: (b -> a -> b) -> b -> [a] -> b
        
        unfold :: (b -> Maybe (a,b)) -> b -> [a]
        
        Elles permettent toute deux de prendre une fonction « simple » (qui travaille sur les types a et b directement) et d'en faire une fonction « compliquée » sur une liste. Mais … Cette fonction simple, sur quoi est-elle en train de travailler plus précisément ?
        
        Maybe (a,b) <=> Paire a b = Cons a b | Nil …. Précisément la « contrepartie non-récursive » de la liste
        
        (b -> a -> b) <=> (a,b) -> b : ici il nous manque un Maybe, tout simplement parce qu'il vient de l'autre argument ! (b -> a -> b) -> b pour la définition de fold est équivalent à Maybe (a,b) -> b.
        
        Regardons maintenant ce que cela donne :
        
        fold :: (Paire a b -> b) -> [a] -> b
        
        unfold :: (b -> Paire a b) -> b -> [a]
        
        De manière systématique, on peut prendre des fonctions simples qui « réduisent » des paires, pour réduire des listes. De manière identique, on peut prendre des fonctions qui construisent des paires, pour construire des listes. On a bien réduit le problème à une chose « plus simple ».
        
        Il est toutefois vrai que c'est exagéré de dire qu'un type récursif, c'est compliqué. Il n'y pas bien grande différence entre foldr (+) 0 et sum [] = 0 ; sum (x:xs) = x + sum xs.
        
        J'espère avoir répondu à ta question :-).
  - [^] # Re: Intéressant, mais Haskell
    
    Posté par Michaël (site web personnel) le 21 juillet 2015 à 21:10. Évalué à 4.
    
    Le problème, c'est que la plus grande partie du code est basée sur les types, qui permettent de se guider pour coder les fonctions. D'ailleurs, cela permet de ne pas s'embrouiller, et de « matérialiser » les idées autrement que par le code : …
    
    Tout le monde connaît la fameuse équation algorithms + data structures = program en revanche peu de gens comprennent son sens, à savoir que l'art de la programmation consiste, partant d'un programme, à choisir si on va exprimer telle partie ou telle autre par un algorithme ou par une donnée!

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.