Discussion :

[seigneur_anubis]

Bonsoir.
Cela fait un moment que je bute sur une fonction et une erreur que me renvoie Caml. Le but de la fonction est de créer un arbre pour ensuite effectuer un tri et choisir le meilleur choix possible pouvant être fait par l'ordinateur (dans le but de coder une IA pour un jeu de dame).

La fonction est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
let rec construction_arbre plateau_actuel joueur n = match n with
|0->(0,plateau_actuel,[])
|n->(0,plateau_actuel,construction_arbre2 (liste_possibilite plateau_actuel joueur;) joueur (n-1))
 
and construction_arbre2 liste joueur n = match liste with
|[]->failwith "Ne doit pas arriver"
|[t]->(0,t,construction_arbre t joueur n)
|t::q->(0,t,construction_arbre t joueur n)::construction_arbre2 q joueur n
;;

Pour ce qui est des variables,
- plateau_actuel est une matrice d'entier
- joueur est un entier
- n est un entier
- liste_possibilite plateau_actuel joueur est une liste de matrice

L'erreur que je reçoit est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
Toplevel input:
>|t::q->(0,t,construction_arbre t joueur n)::construction_arbre2 q joueur n
>                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This expression has type 'a list,
but is used with type (int * int vect vect * (int * int vect vect * 'a list)) list.

En espérant que vous puissiez m'éclairer sur mon erreur.
Merci d'avance.

[prgasp77]

Bonjour,
je ne suis pas sûr de ce que j'affirme, mais quelque chose me semble étrange. Ta fonction construction_arbre2 n'est-elle pas censée retourner une liste de quelque chose ? Si oui, la ligne 7 devrait être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

| [t] -> [(0,t,construction_arbre t joueur n)]

Edit :
Peut-être puis-je te suggérer une solution plus flexible et plus facile à maintenir : créer un module pour ton 'a arbre et ensuite créer un sous-module pour ton arbre de je-ne-sais-pas-quoi. Peut-être peux-tu partir sur quelque chose de ce style :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#type comparison = Less | Equal | Greater;;
type comparison = Less | Equal | Greater
 
#module type ORDERED_TYPE =
   sig
     type t
     val compare: t -> t -> comparison
   end;;
module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end
 
#module Tree =
   functor (Elt: ORDERED_TYPE) ->
     struct
       type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
       let empty = Empty
       let rec insert tree elt =
         match tree with
           Empty -> Node(elt, Empty, Empty)
         | Node(e, left, right) ->
             if Elt.compare elt e = Less
             then Node(elt, insert right e, left)
             else Node(e, insert right elt, left)
       exception Tree_is_empty
       let rec remove_top = function
           Empty -> raise Tree_is_empty
         | Node(elt, left, Empty) -> left
         | Node(elt, Empty, right) -> right
         | Node(elt, (Node(lelt, _, _) as left),
                           (Node(relt, _, _) as right)) ->
             if Elt.compare lelt relt = Less
             then Node(lelt, remove_top left, right)
             else Node(relt, left, remove_top right)
       let extract = function
           Empty -> raise Tree_is_empty
         | Node(elt, _, _) as tree -> (elt, remove_top tree)
     end;;

Il te faudra donc créer un module pour ton type ordonné (puisque tu parles de tri, je suppose que ce que tu mets dans ton arbre est ordonné). Une fois que tu aura un module MyType qui colle au type ORDERED_TYPE, tu pourra créer le sous-module module MyTree = Tree(MyType).

Cordialement,

[seigneur_anubis]

Merci prgasp77 pour ta réponse.

J'ai essayé la modification que tu m'as proposé pour la ligne 7 de ma fonction mais j'ai malheureusement toujours la même erreur.

Dans le général, ce que j'essaye de faire, c'est de développer tous les cas possibles et de les mettre dans un arbre pour ensuite utiliser l'algorithme MinMax à cet arbre. C'est pour cela que j'initialise d'abord la valeur de l'entier qui se trouve en début de couple à 0.

Merci également pour ce que tu m'a proposé pour la suite mais le problème c'est que je n'ai jamais programmé avec des modules jusqu'à présent. Nous avons jusque là vu les arbres et les automates en cours, d'où la réalisation de l'arbre que j'essaye de faire.

[Cacophrene]

Bonsoir,

La correction proposée par prgasp77 est une partie de la solution. En fait, le cas [t] dans construction_arbre2 indique à caml que la fonction renvoie un triplet et non une liste, c'est pour ça qu'il y a une erreur de typage sur le troisième cas du filtrage. En passant, as-tu vraiment besoin de traiter séparément le cas du singleton [t] ?

Cordialement,
Cacophrène

[seigneur_anubis]

J'ai réfléchi à ce que tu as dit à propos de l'erreur de typage et j'en suis donc arrivé au code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
let rec construction_arbre plateau_actuel joueur n = match n with
|0->(0,plateau_actuel,[])
|n->(0,plateau_actuel,construction_arbre2 (liste_possibilite plateau_actuel joueur) joueur (n-1))
 
and construction_arbre2 liste joueur n = match liste with
|[]->[]
|t::q->(construction_arbre t (adversaire joueur) n)::(construction_arbre2 q joueur n)
;;

Celui semble plus juste que celui de la fonction précédente mais je me retrouve toujours avec une erreur de type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Toplevel input:
>|t::q->(construction_arbre t (adversaire joueur) n)::(construction_arbre2 q joueur n)
>                                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This expression has type 'a list,
but is used with type (int * int vect vect * 'a list) list.

Je ne comprend pas trop cette erreur, la fonction construction_abre2 renvoie bien quelque chose du type (int * int vect vect * 'a list) list.

Je pense que l'erreur de type se trouverait dans les cas simple des 2 fonctions récursives mais je n'en suis pas sur.

[gasche]

Vous avez raison tous les deux : la liste d'arbres renvoyée est bien de type ('a list), où ('a) est le type des arbres, mais aussi de type ((int * int vect vect * 'a list) list). Le problème vient du fait que, dans ton programme, le type des arbres est récursif : c'est le type ('a) qui vérifie l'équation récursive ('a = (int * int vect vect * 'a list) list).

Le typeur d'OCaml ne supporte pas ce genre de récursivités par défaut. Pour utiliser des types récursifs, il faut passer par une déclaration de type algébriques (qui eux ont le droit d'être récursifs, en intercalant un "constructeur" entre chaque "couche de récursivité").

Pour donner un autre exemple concret, plus simple, le type ('a = 'a list) n'est pas accepté par Caml par défaut, par contre tu peux écrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

type t = T of t list

(Ici la récursion est "protégée" par le constructeur "T". (t) n'est pas directement égal à (t list), il y a le constructeur qui fait la transition entre les deux; on parle de type "iso-récursif")

Pour résoudre ton problème de typage, tu peux passer à OCaml l'option -rectypes, qui lui dit « accepte les types "équi-récursifs" », c'est-à-dire les types vérifiant une équation récursive directe, sans type algébrique interposé. Elle n'est pas activée par défaut car elle rend le système de typage trop expressif, et des choses qu'on aurait envie de rejeter deviennent acceptées, avec un type bizarre.

Tu peux aussi, et c'est ce que je te conseille, et c'est ton seul choix en Caml Light qui ne supporte pas -rectypes, rendre la récursion explicite en utilisant un type algébrique:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

type 'a arbre = Noeud of (int * 'a * 'a arbre list)

Ensuite dans ton code, il faut placer le constructeur au bon endroit (là où avant tu avais un simple triplet représentant un nœud de l'arbre):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let rec construction_arbre plateau_actuel joueur n = match n with
|0-> Noeud (0,plateau_actuel,[])
|n->
  let enfants =
    let possibilites = liste_possibilite plateau_actuel joueur in
    construction_arbre2 possibilites joueur (n - 1) in
  Noeud (0, plateau_actuel, enfants)
 
and construction_arbre2 liste joueur n = match liste with
|[]->[]
|t::q->
  (construction_arbre t (adversaire joueur) n)::(construction_arbre2 q joueur n)

Tu as peut-être l'impression que c'est pénible parce que ça oblige à faire des filtrages :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec taille t =
  match t with Arbre (_, _, enfants) ->
    List.fold_left (+) 1 (List.map taille enfants)

mais en fait non :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
let rec taille (Arbre (_, _, enfants)) =
  List.fold_left (+) 1 (List.map taille enfants)

[seigneur_anubis]

Merci gasche.

Donc pour ce type de programmation il faudra obligatoirement définir un type qui est récursif dans lui même (si on peut dire ça comme ça).

Je peux de nouveau continuer à avancer sur la programmation du jeu, merci beaucoup à vous !

J'aurais une dernière question, elle n'a pas de rapport avec la fonction ci dessous mais est-il possible d’accélérer la vitesse d'exécution d'un programme avec Caml ? Mon prof d'informatique nous avait parlé par exemple d'une fonction qui fait "sauter" les sécurité sur les vecteurs par exemple, mais ou il fallait être sur de son programme pour ne pas avoir de plantage.

[Cacophrene]

Bonjour,

Effectivement, le compilateur accepte un certain nombre d'options qui visent à améliorer les performances (l'exemple que tu cites à propos des tableaux est -unsafe qui désactive les contrôles d'accès hors limites sur les tableaux et les chaînes de caractères). Il est exact que ces options doivent être manipulées avec prudence et exclusivement sur du code éprouvé car les exceptions sont alors remplacées par des erreurs de segmentation.

En pratique, sauf cas particulier, ces options ne transformeront pas un programme lent en programme rapide, mais ça, je suppose que le sais déjà. La meilleure optimisation se passe en amont, par le choix d'un algorithme adapté et performant, puis par son implémentation efficace. Lorsque tout est bon de ce côté-là, on peut commencer à jouer avec ces options (première étape avant de commencer à réécrire certaines portions de code en C si les performances sont vraiment critiques ).

Bref, il n'y a pas de quoi s'emballer pour l'instant, d'autant que sauf erreur de ma part ça concerne surtout OCaml (j'ai souvenir d'un bytecode Light plutôt lent, mais je peux me tromper).

Cordialement,
Cacophrène

[seigneur_anubis]

D'accord

Merci beaucoup pour vos aides, grâce à vous j'aurais appris quelques trucs utiles pendant mes vacances .

Cordialement,
Anubis.