Discussion :

[80chris]

Bonjour, je suis étudiant en licence informatique 3 et j'ai un module d'intelligence artificielle ou je lutte un peu à vrai dire. Pour ceux qui connaisse je dois savoir dérouler l'algorithme MTD (qui se sert de alphabeta) et de l'algorithme Scout.

Pour MTD j'ai vraiment du mal à comprendre exactement le fonctionnement, et sur le net je n'arrive pas à trouver des bonnes explications.

Pour Scout je sais que l'algorithme est séparé en deux modules, un module évaluation et un module test. Mais idem j'ai du mal à dérouler l'algorithme correctement.

J'aimerais bien des explications claires pour ceux qui s'y connaissent.

Voici un exemple d'arbre avec l'application de Scout (je ne sais pas si il est correct) :



Merci d'avance !

[Franck Dernoncourt]

http://en.wikipedia.org/wiki/MTD-f ?

[davcha]

Pour ce qui est du PVS (scout), tu fais une hypothèse supplémentaire par rapport à un alpha beta classique : tu supposes que tes coups sont "bien triés" et que le meilleur va, statistiquement, être le 1er testé.

Dans le cas de MTD(f), tu as globalement la même approche. Plutôt que de rechercher "le meilleur coup", tu cherches une borne sup ou inf de ton meilleur coup, en lançant des alphabeta avec une fenêtre nulle.

Globalement dans les deux cas, tu as des heuristiques. Ce qui peut être un peu perturbant quand on y est pas habitué par rapport à un alphabeta qui retourne une valeur "exacte". Mais dis-toi qu'alphabeta ne retourne que le meilleur coup à une profondeur donnée selon un objectif donné. Objectif qui est une heuristique. Et le paramètre de profondeur est lui aussi arbitraire.