Discussion :

[Bathou]

BONJOUR!!
je cherche à ecrire l'algorithme informel (puis le programmer en pascal sur delphi) de l'algorithme negamax. J'ai fait un brouillon mais je ne suis pas sure de l'exactitude de ce que j'ai fait :

Si la profondeur est atteinte
Alors
Retourner le résultat
Sinon
Généré la liste de coups possibles
Tant que l'on n'a pas étudié tous les coups possibles faire
simuler le jeu du coup étudié
//appel récursif
retirer le coup simulé
retourner le coup correspondant à l'opposé du maximum de ses fils

voilà, si vous pouviez m'aider rapidement... merci beaucoup

[PRomu@ld]

A première vue ça m'a l'air bon (je rajouterai juste le cas où on arrive sur une feuille avant que la profondeur soit atteinte) Le plus dur étant bien entendu trouver une fonction adéquate pour ceci :

Retourner le résultat

[Bathou]

cool merci!
par contre je n'ai pas compris ce que tu as dit la :

(je rajouterai juste le cas où on arrive sur une feuille avant que la profondeur soit atteinte)

et je pars en quête de cette fonction...

[jobherzt]

en gros, ca veut dire qu'il faut prevoir le coup ou il n'y a plus de coup possible, donc meme si tu n'as pas atteint la profondeur max, il faut arreter la recursion.

note que si tu t'interesse a ca, la variante alpha-beta couplé au principe de l'approfondissement progressif sont simple a mettre en place et apportent un gain enorme en profondeur !!!

[Bathou]

c'est ce à quoi je dois arriver à la fin mais on m'a dit de maitriser d'abord le negamax tout cours (la prof lol)

[jobherzt]

bien sur, bien sur, d'autant plus que ces evolutions consistent essentiellement a ajouter des choses au negamax de base, donc ca ne pose aucun probleme de faire les choses progressivement.. je tenais juste a signaler le coup de l'approfondissement progressif qui est une astuce tres tres simple et hyper efficace pour booster l'alpha-beta

[Bathou]

ok!
autre question... je me demandais quel type d'arbre utiliser : un arbre binaire c'est pas possible... un arbre 234 ca me semble d'aucune utilité vu que ce n'est pas classé... un AVL inutile... bref je ne connais que ces trois la et je suis perplexe... (ou alors une autre structure de donnée??)
deuxième question : il me reste un point obscur pour l'alpha béta à savoir pour quand on coupe...J'ai cru comprendre que si le noeud de profondeur 3 par exemple était supérieur au noeud racine on cooupait mais je crois qu'il y a une autre condition...
voila merci d'avance à ceux qui voudront bien prendre le temps de m'éclairer...

[jobherzt]

sauf erreur, tu n'as pas besoin d'arbre du tout que comptais tu faire ? creer l'arbre des coupes possibles et ensuite parcourir cet arbre ? pourquoi ne pas dircetement faire une fonction negamax recursive ?

pour alpha beta, je ne vois pas trop ce que tu veux dire. le principe est assez simple, regarde un exemple detaillé ici : http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

[Bathou]

euh ben si je comptais en faire un d'arbre moi!! parce que si on prend le pseudo code que voila (trouvé sur ta super page web)

fonction ALPHABETA(P, A, B) /* A < B */
si P est une feuille alors
retourner la valeur de P
sinon
Meilleur = –INFINI
pour tout fils Pi de P faire
Val = -ALPHABETA(Pi,-B,-A)
si Val > Meilleur alors
Meilleur = Valeur
si Meilleur > A alors
A = Meilleur
si A > B alors
retourner Meilleur
finpour
retourner Meilleur

il y a besoin d'un arbre... et euh je ne vois pas comment faire sans la... ca me dépasse.
sinon j'ai compris l'élagage alleluia merci
mais sur le pseudo code je ne comprends pas ce qui est en rouge... quel est l'intéret de retourner meilleur à la fin??

[jobherzt]

non, tu n'as pas besoin d'un arbre, quand tu rentre dans ta fonction, tu construis la liste des coups possibles a partir de cette position, et tu lance la fonction recursivement sur chacun de ces coups possibles !

et la partie en rouge, c'est logique : dans sa boucle, l'algo cherche a elaguer. c'est le role de

Code :

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

1
2
3
 
si A > B alors
retourner Meilleur

qui veut dire "pas besoin d'aller jusqu'a la fin de la boucle, on coupE et on renvoit tout de suite Meilleur". mais si tu n'elague rien, tu vas aller jusqu'au bout de ta boucle, et a la fin il faut bien que tu retourne quelque chose !!! et donc tu retourne le meilleur coup que tu as trouvé. en fait, le code rouge c'est ce qui se passe dans le pire des cas, quand tu n'as pas d'elaguage alpha beta.

[Bathou]

ok pour le rouge mais euh... ce que tu as mis avant euh... toujours pas compri... dsl

[jobherzt]

je m'exprime mal, mais je te jure que c'est simple.

en gros l'idee c'est qu'au lieu de faire :

Code :

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

1
2
3
 
pour chaque fils faire ....
     et on lance recursivement sr chacune des fils

ce qui implique que tu a deja construit un arbre, tu fais :

Code :

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

1
2
3
4
5
 
tableau T= GenererTousLesCoupsPossiblesAPartirDeCettePosition()
 
pour chaque element de T faire ....
     et on lance recursivement sur chacune des elements de T

En fait, dans ton idee, tu vas faire une premiere fonction recursive qui va construire l'arbre et le stocker, et une autre qui va parcourir l'arbre et faire le negamax... l'idee c'est simplement de faire les 2 d'un coup ! et donc tu n'as plus besoin de stocker l'arbre !

[Bathou]

ok merki j'ai compris!!! super

(tu m'as sauvé la vie parce que ma bibi sinon elle me frappe ; c'est une méchante ferrue d'info )

en fait euh j'ai encore une question... un tableau ça a une taille fixe et par rapport à mon jeu, je vais avoir un nombre de coups qui diminue donc la structure ne sera pas fixe...donc je prends un tableau avec le nombre maximum de coups possibles ou bien je prends une structure avec une taille variable genre fille d'attente??

[marie rose]

en ce qui concerne l'algorithme negamax, je te conseille un ABR 2-3-4 vu en cours. N'oublie pas que c'est -1 point par jour de retard pour rendre ton rapport... Tu ferais mieux de faire un peu travailler ta binome, c'est un travail à deux je te rappelle. Essaye une matrice dynamique d'adjacence pour mieux visualiser le processus de conceptualisation.

[PRomu@ld]

Il n'y a pas besoin d'arbre pour implémenter l'algorithme, il se trouve que pour l'expliquer il est très commode de faire un arbre.

L'arbre existe en fait, il s'agit des empilements des appels récursifs de la fonction négamax (il en va de même pour le simple minmax ou alpha-béta).

[Bathou]

n'étant pas sûres de ce que nous avions fait et n'ayant qu'une semaine pour rendre le rapport (à l'heure!!) avec un partiel et une interro, il nous a semblé sage de demander conseil pour nous permettre d'avancer plus vite...

nous avons finalement opté pour un tableau avec deux champs : un pour le nombre de coups et l'autre du type tableau (un tableau dans un tableau dans un tableau...)

merci à ceux qui nous ont aidé