Algorithme alpha-bêta : pseudo code

Bonjour,

Je voudrais une explication par rapport à ce code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int alphabêta(int depth, int alpha, int bêta) { if (game over or depth <= 0) return winning score or eval(); move bestmove ; for (each possible move m) { make move m; int score = -alphabêta(depth - 1, -bêta, -alpha) unmake move m; if (score >= alpha){ alpha = score ; bestMove = m ; if (alpha >= bêta) break; } } return alpha; }

---

En première lecture je pensais à une erreur d'indentation en ligne 6 , mais j'ai trouvé la même chose en différents endroits sur internet.
Je ne comprend pas : la première fois que l'on appelle alphabeta() on ne passe pas dans le if ligne 4 donc on commence systématiquement par jouer "bestmove" mais d'où sort-il ? On n'a pas encore déterminé m !

Je vous remercie par avance pour une explication éclairée :P

Bonjour,

Ligne 5 : En premier lieu je dirais qu'il y a un problème par rapport à ce code, je n'ai jamais vu de return a or b si a et b ne sont pas des booléens...

Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.

L'indentation du code semble donc correcte. Sinon je vous recommande un article de wikipedia qui m'a été très utile dans mes études et que je trouve un peu plus clair :

http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

OK,

C'est possible qu'il y ait un problème par rapport à ce code, mais comme je l'ai dit j'ai trouvé des choses identiques sur internet.

C'est un pseudo code proche du langage C puisque la fonction est typée en int, c'est le langage avec lequel je travaille.
Mais cela ne sert à rien que je commence à coder tant que je n'aurais pas compris l'algo !
Je ne m'étais pas arrêté sur la ligne 5 mais c'est vrai que ce n'est pas logique : il ne faut pas prendre "or" comme un opérateur !
En ligne 5 je comprends qu'il faut retourner le résultat de la fonction eval() donc un int.

Pour moi "move bestmove" (ligne 6) c'était jouer le meilleur coup parmi les m explorés et déterminé justement par l'algo : voir bestmove = m en ligne 13.

Citation:

---

Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.

---

Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.

Revenons à wikipédia (merci pour le lien):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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 = Val si Meilleur > A alors A = Meilleur si A ≥ B alors retourner Meilleur finsi finsi finsi finpour retourner Meilleur finsi fin

---

A partir de ce pseudo-code je voudrais faire apparaître les notions de simuler le coup et de déjouer le coup (exploration de l'arbre) ainsi que celle de jouer le meilleur coup une fois déterminé.
Ces 3 notions existent dans le premier pseudo-code indiqué et c'est pour cela que j'ai retenu celui-ci.
Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

Merci si vous pouvez me donner le complément ;)

Citation:

---

Envoyé par nanosoft

OK,

Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.

---

En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta() ; ensuite elle persiste durant toute l'exécution de l'intégralité du code. En effet, alphabeta() est une fonction récursive qui va être initialisée au sommet et s'appeler elle-même jusqu'à la condition d'arrêt.

Citation:

---

Envoyé par nanosoft

Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

Merci si vous pouvez me donner le complément ;)

---

Le pseudo-code dont vous avez besoin ici n'est donc autre que la fonction alphabeta(P,A,B) elle-même, initialisée pour tous les fils P du sommet de votre arbre, et avec A = - inf et B = + inf.

Hope it helps ! ;)

Merci mais je voudrais savoir si le premier pseudo-code de la discussion est correct ou non.
Et s'il n'est pas correct, cela serait super que quelqu'un puisse le corriger.

En l'état je ne le comprends pas puisqu'on commence par jouer le meilleur coup avant l'exploration et avant toute récursivité !

Citation:

---

En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta()

---

Mais au premier appel : elle n'est pas affectée !!!!

Bonjour,

Un if qui n'a pas d'accolade donc pas de corp.
le ; signifie la fin de l'instruction ça revient donc à écrire ceci.

Code:

---

1 2 3

if (game over or depth <= 0) return winning score or eval(); move bestmove ;

---

Il n'y a donc pas de probléme d'indentation.

Bonjour jouana,

Tout à fait d'accord et c'est bien là ce que je ne comprends pas :
la première instruction au premier appel de alphabeta() est "move bestmove" ! ?

C'est juste une déclaration : "move bestmove;" déclare une variable appelée "bestmove" de type "move".

--
Jedaï

Bonjour,

Merci Jedai, je vois une autre piste mais je ne comprends toujours pas tout.
Vous confirmez que ce pseudo code est correct ?
Une fonction récursive est assez difficile à tester unitairement, je ne voudrais pas partir sur une mauvaise base :zoubi:

Ce que je voudrais savoir maintenant c'est à quel moment on exploite cette variable bestmove (c'est à dire jouer réellement le coup) ?
On est bien d'accord que bestmove représente le coup à jouer parmi les coups m qui ont été explorés (il est déterminé en ligne 13) et , durant l'exploration, les coups sont joués puis déjoués systématiquement.
A quel moment on joue LE coup ? est-ce à l'extérieur de alphabeta() (bestmove serait une variable globale) ?

EDIT :
Avec cette nouvelle vision je suis retourné sur internet et il semblerait que cela soit la bonne piste.
Sur ce lien :
http://pageperso.lif.univ-mrs.fr/~li...i/MinMaxL2.pdf
On trouve :

Citation:

---

Il est nécessaire de retourner non seulement le score mais en plus le meilleur coup (en général, on décide de passer une variable par adresse qui contiendra le meilleur coup).

---

Dans ce cas dans le jeu, au moment de jouer : on appelle alphabeta() puis ensuite on joue "bestmove".

J'aimerais bien avoir l'avis et la confirmation d'un "expert" ;)

Bonjour,

Je voudrais savoir si l'implémentation en C de l'algo est correcte :

Code:

---

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 37 38 39 40

long int algoA_B(int prof, int jouR, long int alpha, long int beta) { long int score=0; long int retour; // le retour de la fonction int libre=1; // si il est possible de mettre un pion en x => libre = 1 int i=1; // le x à jouer (1 à 7) int fin=0; // flag de fin du jeu (toutes les colonnes sont pleines)   if (gameovera || prof<=0) { retour = valCoup(jouR); // heuristique d'évaluation } else { for(i=1;i<8;i++) // pour tous les coups possibles { libre=test_libre(i); // on teste si l'on peut mettre un pion dans cette colonne if (libre) { simule(i, jouR); // on joue le coup pour jouR score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2) efface(i); // on annule le coup if (score>=alpha) { alpha = score; // le meilleur coup jusqu'à maintenant bestmove = i; // le x à jouer if (alpha>beta) break; // inutile de poursuivre } }   else fullCol[i]=1; //cette colonne est pleine   } retour = alpha; // on retourne alpha fin = testCol(); // teste si toutes les colonnes sont pleines if(fin) gameovera=1; }   return retour; }

---

elle est appelée ainsi :

Code:

---

1 2	algoA_B(6, coul(joueurCour), -1000000, 1000000); joue_coup(bestmove);

---

Merci pour toute aide.

Bonjour,

Je n'ai pas encore réussi à faire une implémentation correcte :

La fonction algoA_B() renvoie une valeur mais elle ne retourne pas le coup à jouer. Jouer "bestmove" comme je l'ai indiqué ne marche pas, cela revient à jouer le dernier coup exploré.

J'envisage, lors d'un coup à jouer, d'appeler plusieurs fois la fonction algoA_B() pour chaque coup jouable (n coups) : j’obtiens alors n valeurs de retour de la fonction et je joue en définitive le coup ayant conduit à la valeur la plus forte.

Est-ce la bonne façon de faire ?

Citation:

---

Envoyé par nanosoft

Bonjour,

Je voudrais savoir si l'implémentation en C de l'algo est correcte :

Code:

---

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 37 38 39 40

long int algoA_B(int prof, int jouR, long int alpha, long int beta) { long int score=0; long int retour; // le retour de la fonction int libre=1; // si il est possible de mettre un pion en x => libre = 1 int i=1; // le x à jouer (1 à 7) int fin=0; // flag de fin du jeu (toutes les colonnes sont pleines) if (gameovera || prof<=0) { retour = valCoup(jouR); // heuristique d'évaluation } else { for(i=1;i<8;i++) // pour tous les coups possibles { libre=test_libre(i); // on teste si l'on peut mettre un pion dans cette colonne if (libre) { simule(i, jouR); // on joue le coup pour jouR score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2) efface(i); // on annule le coup if (score>=alpha) { alpha = score; // le meilleur coup jusqu'à maintenant bestmove = i; // le x à jouer if (alpha>beta) break; // inutile de poursuivre } } else fullCol[i]=1; //cette colonne est pleine } retour = alpha; // on retourne alpha fin = testCol(); // teste si toutes les colonnes sont pleines if(fin) gameovera=1; } return retour; }

---

---

1) L'algo est complexe.
2) Splitter la fonction en sous fonctions serait bien aussi (règle d'or)

Peut-être essayer d'écrire l'invariant serait utile. Dans ce cadre, tu t'apercevras que efface(i) devrait être placé das le else de if (score > alpha)
Le but est de retenir les coups supérieurs et d'oublier les inférieurs :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

if (libre) { simule(i, jouR); // on joue le coup pour jouR score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2) /* efface (i) , ancienne version */ if (score>=alpha) { alpha = score; // le meilleur coup jusqu'à maintenant bestmove = i; // le x à jouer if (alpha>beta) break; // inutile de poursuivre } else efface(i); // on annule le coup }

---

EDIT placement d'un commentaire dans le code proposé

Bonjour,

Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?

L'algo n'est pas très complexe, il est calqué sur ce pseudo-code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int alphabeta(int profondeur, int alpha, int beta) { if (game_over or profondeur <= 0) return eval(); move meilleur_coup; for (chaque coup possible m) { jouer le coup m; int score = -alphabeta(profondeur - 1, -beta, -alpha); annuler le coup m; if (score >= alpha) { alpha = score ; meilleur_coup = m ; if (alpha >= beta) break; } } return alpha; }

---

Je ne comprend pas la proposition suivante :

Citation:

---

Dans ce cadre, tu t'apercevras que efface(i) devrait être placé das le else de if (score > alpha)

---

Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).

Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?

Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?

Dans l'implémentation que j'ai faite : simule() et efface() sont en fait des manipulations sur un tableau image qui part de la situation du tableau de jeu réel.
Je retrouve bien mon tableau de départ après un appel à la fonction algoA_B() et ses simulations en profondeur.
J'ai fait des traces sur les retours de valCoup() et cela a l'air correct.

Je m'orienterais bien vers l'algo de wikipédia mais la fonction donnée renvoie une valeur. Comment joue t-on le coup ? et quel coup ?
Je retombe sur ma question d'hier avec le pseudo-code actuel ...

Citation:

---

Envoyé par nanosoft

Bonjour,

Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?

---

De rien, ton problème m'intéresse.

Citation:

---

Je ne comprend pas la proposition suivante :
Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).

---

Tu as raison de ne pas comprendre l'algo wiki ma fait mieux saisir le problème.

Citation:

---

Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?
Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?

---

[QUOTE=nanosoft;7894194]
A part make move m et umake move m et le break qui tient lieu de return alpha. C'est presque l'algo NegaMax de Aho et Ullman que retrouves en 2è position sur Wiki.
La seule différence est qu'une structure globale garde la trace des mouvements successifs dans ton pseudocode..
Mets les bestMove successifs dans une pile globale (ou les printf dans un premier temps), tu auras la suite des mouvements optimaux.

Citation:

---

Dans l'implémentation que j'ai faite : simule() et efface() sont en fait des manipulations sur un tableau image qui part de la situation du tableau de jeu réel.
Je retrouve bien mon tableau de départ après un appel à la fonction algoA_B() et ses simulations en profondeur.
J'ai fait des traces sur les retours de valCoup() et cela a l'air correct.

---

Bravo :)

Bonne suite. Donne-nous des nouvelles

Citation:

---

Envoyé par nanosoft

Bonjour,

Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?

---

De rien, ton problème m'intéresse.

Citation:

---

Je ne comprend pas la proposition suivante :
Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).

---

Tu as raison de ne pas comprendre l'algo wiki ma fait mieux saisir le problème.

Citation:

---

Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?
Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?

---

A part make move m et umake move m et le break qui tient lieu de return alpha, c'est le code qui provient de la page suggérée par jimmy.
Mais ce wiki m'a l'air complexe de nouveau. Je propose une alternative plus bas.

La seule différence globale est qu'une structure globale garde la trace des mouvements successifs dans ton pseudocode..
Mets les bestMove successifs dans une pile globale (ou les printf dans un premier temps), tu auras la suite des mouvements optimaux.

Tu peux trouver un algorithme beaucoup plus clair sur wiki chessprogramming :
http://chessprogramming.wikispaces.com/Alpha-Beta

Code:

---

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

alpha et beta sont des lower et upper bounds sur le score final. //optimiser le coup du joueur blanc int alphaBetaMax( int alpha, int beta, int depthleft ) { if ( depthleft == 0 ) return evaluate(); for ( all moves) { score = alphaBetaMin( alpha, beta, depthleft - 1 ); //voir la réponse du joueur noir if( score >= beta ) // l'upperbound peut être au moins augmentée return beta; // on choisit le coup qui augmente l'upperbound if( score > alpha ) // sinon, si on a trouvé le moyen de faire mieux que la lower bound, alpha = score; //alors on a au moins une nouvelle lower bound égale au score évalué et on renvoie cette valeur } return alpha; } //optimiser pour le joueur noir int alphaBetaMin( int alpha, int beta, int depthleft ) { if ( depthleft == 0 ) return -evaluate(); for ( all moves) { score = alphaBetaMax( alpha, beta, depthleft - 1 ); //voir la réponse du joueur blanc if( score <= alpha ) //la lowerbound peut être au moins diminuée return alpha; // on choisit le coup qui diminue la lowerbound if( score < beta ) // sinon, si on a trouvé le moyen de diminuer l'upper bound, beta = score; //on a donc une nouvelle upper bound égale au score évalué et on renvoie cette valeur } return beta; }

---

Il faut bien sûr appeler mone et unmove autour de l'appel récursif.

Bonne suite. Donne-nous des nouvelles

Bonjour,

Je m'interroge sur l'algorithme que tu as présenté le 01/09/2014.

Tout d'abord, 7 colonnes, éventuellement pleines, ça sent le puissance 4...
J'ai lu l'algo sous cette angle et ce d'autant plus que j'en ai fait un il y a une dizaine d'années.

Donc :
Question :
Quelle est l'utilité de la ligne 31 (else fullCol[i]=1; ) et de gameover ?
Si tu as besoin d'un indicateur des colonnes pleines l'occupation de la dernière case de chaque colonne ne suffit-elle pas ?
De plus, j'ai l'impression que fullCol et gameover sont des variables globales. On peut donc légitimement se demander quand reviens-tu en arrière ?
Suis le raisonnement suivant :
Tu lances ton algo à 6 coups de la fin (plus que 6 cases vides et une profondeur de 6 ou plus). Lors de la première décente, le jeu est plein quant a été évalué la toute première variante de 6 coups. Donc fullCol[i] == 1 pour tout i ! Et gameover = 1.
Quand il (l'algo) sera remonté au niveau 1 et qu'il voudra évaluer le deuxième coup, il n'en fera rien car le jeu et officiellement plein d'après tes deux indicateurs.
Sauf si tu les corriges dans efface(i). Mais je trouve dangereux de ne pas donner à une opération et à son inverse la même visibilité.

Première remarque :

Cella a déjà été relevé mais je reviens sur la variable globale bestmove. Si tu utilises la même variable pour tous les niveaux de recherche cela ne peut pas marcher. Supposes que ton meilleur coup soit le premier envisagé. Au niveau 1, il n'y aura jamais de réaffectation. Mais quand tu vas évaluer les autres branches, il va y avoir, aux niveau inférieurs, de multiples affectations de meilleur coup qui vont donner à ta variable bestmove une valeur presque aléatoire quand ton niveau un va répondre.

Soit tu utilises une pile comme cela a déjà été proposé, soit ta fonction doit retourner deux valeurs (un tableau int[] ?) soit tu gères le premier niveau différemment des suivants car au final, tu n'as besoin de conserver le meilleur coup pour pouvoir le jouer qu'au premier niveau. La seule chose qui t’intéresse au niveau 2 et suivant c'est l'évaluation de la grille.

Deuxième remarque :

Bon, là c'est du gagne petit. Mais pourquoi un >= en lieu et place d'un > dans if (score>=alpha) ?
Entre deux coup qui valent alpha autant garder le premier non ?

Bonjour,

Merci pour vos réponses, cela m’encourage à continuer.
J’ai failli abandonner car j’ai un algo perso (sans exploration d’arbre) qui marche assez bien.

Bien sur ce n’est pas l’arme ultime d’un mini-max avec une profondeur conséquente … mais il est plus rapide !
Oui, il s’agit bien d’un Puissance4 et déjà je ne gagne pas à tous les coups lorsque je joue contre l’I.A.

N’empêche que je n’ai toujours pas la réponse à ma question ! Pseudo-code correct ? :roll:

Citation:

---

Tu peux trouver un algorithme beaucoup plus clair sur wiki chessprogramming :

---

Je ne sais pas s’il est plus clair mais en Negamax il est différent :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

int alphaBeta( int alpha, int beta, int depthleft ) { if( depthleft == 0 ) return quiesce( alpha, beta ); for ( all moves) { score = -alphaBeta( -beta, -alpha, depthleft - 1 ); if( score >= beta ) return beta; // fail hard beta-cutoff if( score > alpha ) alpha = score; // alpha acts like max in MiniMax } return alpha; }

---

On commence par comparer score à beta et non à alpha.
Quel est le bon ?

Citation:

---

Quelle est l'utilité de la ligne 31 (else fullCol[i]=1; ) et de gameover ?

---

J’ai évolué depuis que j’ai posté ce premier code, dans la fonction final() j’évalue si un joueur a gagné, si la profondeur est atteinte ou si toutes les colonnes sont pleines (les colonnes sont actualisées en fonction de simule() et efface().

Code:

---

1 2 3 4

if (final(prof, jouR)) { retour = valCoup(jouR); // fonction d'évaluation }

---

Citation:

---

Si tu utilises la même variable pour tous les niveaux de recherche cela ne peut pas marcher.

---

Je l’ai découvert en débugant : bestmove est maintenant un tableau indexé sur la profondeur.
Mais je n’ai pas l’intention de le garder : j’oublie bestmove et je vais essayer de le lancer algoA_B() sur chaque coup et de jouer le meilleur. Je pense que c’est cette proposition dans :

Citation:

---

soit tu gères le premier niveau différemment des suivants car au final, tu n'as besoin de conserver le meilleur coup pour pouvoir le jouer qu'au premier niveau

---

Je pense que je vais finir par y arriver … si le pseudo code est correct. Quelqu’un peut-il me le confirmer ? :zoubi:

Bonjour,

Qu'entends tu par pseudo code correct ?

Le problème des pseudos codes c'est qu'ils sont là pour nous donner une idée de la démarche à suivre. On se permet donc souvent des facilités d'écriture qu'un compilateur bien élevé ne tolèrera pas.

Exemple dans ton premier pseudo code on a :

Code:

---

1 2 3

if (game over or depth <= 0) return winning score or eval();

---

On comprend bien que cela veut dire que si le jeu est terminé (gain ou plein) ou que l'on est arrivé au bout de la profondeur, il faut retourner respectivement le score gain/perte/nulle ou l'évaluation de la position.
Mais sauf à le vouloir explicitement, jamais une implémentation ne ressemblera à ça. D'ailleurs, à froid, je ne vois même pas comment faire.

De plus, tu as bien compris que la variable bestmove n'est pas très utile. Elle sert presque de commentaire :

Code:

---

1 2 3

alpha = score ; bestMove = m ;

---

On change la valeur d'alpha parce que l'on a trouvé un meilleur coup.

Le meilleur coup se trouvera en appelant cette méthode sur chaque coup du premier niveau et en prenant celui correspondant au meilleur score.

Donc ce premier pseudo code me semble correct. Mais le travail d'implémentation n'est pas neutre.

Celui de ton dernier message par contre ne me plait pas du tout :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

int alphaBeta( int alpha, int beta, int depthleft ) { if( depthleft == 0 ) return quiesce( alpha, beta ); for ( all moves) { score = -alphaBeta( -beta, -alpha, depthleft - 1 ); if( score >= beta ) return beta; // fail hard beta-cutoff if( score > alpha ) alpha = score; // alpha acts like max in MiniMax } return alpha; }

---

Où joue-t-on les coups, les enlève-t-on ? L'évaluation d'une position ne se fait qu'avec alpha bêta ? Et pourquoi la profondeur à 0 est le seul critère d'arrêt ? Le jeu n'est jamais plein ? Personne ne gagne ?

Par contre, comparer alpha ou bêta en premier c'est un peu du pareil au même. Si on garde à l'esprit que lorsque l'on arrive à ces if alpha est inférieur à bêta :
Pour score < alpha : on ne fait rien dans les deux algos.
pour alpha < score < bêta : on affecte la nouvelle valeur à alpha. (on le fait aussi pour alpha = score dans le premier...)
pour bêta <= score : on arrête tout et on renvoie score.

Par contre, je me permettrais une petite remarque : dans tes deux algos le choix de l'ordre des coups à tester a l'aire aléatoire. Et dans tes implémentations tu choisis de balayer les colonnes avec un compteur.

C'est le plus facile mais ce n'est pas le plus efficace. N'oublies pas que plus tu augmentes tes chances de trouver le bon coup vite plus l'élagage de l'arbre par l'alpha bêta est efficace.

Mais n'allons pas trop vite. Tu amélioreras ça quand le reste tournera.

Bonjour,

Je suis bien d’accord avec ta démarche, Vincent.
Voici l’implémentation actuelle :

Code:

---

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

long int algoA_B(int prof, int jouR, long int alpha, long int beta) { long int score=0; long int retour; // le retour de la fonction int libre=1; // si il est possible de mettre un pion en x => libre = 1 int i=1; // le x à jouer (1 à 7)   if (final(prof, jouR)) // plein ou gagné ou prof atteinte { retour = valCoup(jouR, prof); // fonction d'évaluation } else { for(i=1;i<8;i++) // pour tous les coups possibles { libre=test_libre(i); // on teste si l'on peut mettre un pion dans cette colonne if (libre) { simule(i, jouR, prof); // on joue le coup pour jouR score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2) efface(i, prof); // on annule le coup if (score>=alpha) { alpha = score; // le meilleur coup jusqu'à maintenant if (alpha>beta) break; // inutile de poursuivre } }   } retour = alpha; // on retourne alpha } return retour; }

---

J’appelle maintenant la fonction de cette manière :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

for(i=1;i<8;i++) { retourAB[i] = -100000; // pour les coups non libres if (test_libre(i)) // on teste si l'on peut mettre un pion dans cette colonne { simule(i ,coul(joueurCour),profondeur); retourAB[i] = -algoA_B(profondeur-1, 3-coul(joueurCour), -100000, 100000); efface(i, profondeur); }   }

---

et je joue le i qui retourne la plus grande valeur de retourAB[]

suite à ta remarque je ne vois pas comment je pourrais éviter de faire une simulation sur chaque colonne ? ni définir un ordre préférentiel ?

Là ton code commence à me plaire.

À priori ça devrait tourner.

Tu vas pouvoir commencer à t'amuser.

Ton dernier message se termine sur deux questions.

La première :

Citation:

---

Envoyé par nanosoft

suite à ta remarque je ne vois pas comment je pourrais éviter de faire une simulation sur chaque colonne ?

---

Mais c'est l'apha-bêta qui s'en charge! C'est donc déjà fait.

Pour l'essentiel.

Je reviendrais peut-être sur cette affirmation plus tard.

Mais dans l'immédiat voyons la seconde question*:

Citation:

---

Envoyé par nanosoft

ni définir un ordre préférentiel ?

---

Et là un monde nouveau s'ouvre à toi.

Mais pour te le présenter je vais d'abord attirer ton attention sur le nombre de nœuds de ton arbre.

Pour rester compréhensible il faut souvent se limiter à des exemples simples. Prenons donc une grille vide et appliquons une recherche de profondeur 6.

On ne dépassera jamais la capacité d'une colonne et on n'alignera jamais 4 jetons.

Donc avec un min-max de base, on balayerais tout l'arbre des possibilités.

Ça fait*: 7^1 + 7^2 + 7^3 + 7^4 + 7^5 + 7^6 = 137256
(suite géométrige)

Le dernier étage représentant 7^6=117349

Où tu voix que c'est vraiment les feuilles qui coûtent. Bon jusque là rien de nouveau.

Pour suivre l'évolution de ton alpha bêta, je t'invite à ajouter un petit compteur dans ton code. Pour visualiser le nombre de nœuds que tes implémentations vont t'épargner.

Maintenant revenons au puissance 4.

Voici une position :

------
------
------
------
--xx--
-xooo-

Aux croix de jouer. Nous voyons tous qu'il y a urgence à jouer dans la colonne 7. Mais combien de temps ton algorithme va mettre pour le comprendre ?

Dans un premier temps il va remplir la première colonne. Puis déplacer le rond du haut dans chacune des colonnes suivantes. Pour finir, il tombera sur la dernière. Mais n'en déduira rien d'autre que 5 coups dans la première colonne c'est mortel au sixième. Il recommencera avec 4 coups dans la première, une croix dans la deuxième et c'est reparti pour 7 coups de rond avant de retomber sur le problème.

Et si, au lieu de te contenter de l'alpha et du beta tu lui transmettais également les coups tueurs? Pour simplifier le raisonnement: disons que tu passes à l'étage du dessous la colonne (éventuellement pleine quand même) à tester en premier et qui correspondrais au meilleur de la variante précédente ?
Et bien on ne testera plus que le coup perdant (score = bêta à chaque premier coup). On passe de 7 coups à 1.

Mieux, beaucoup mieux, quand au premier niveau, ton algo aura fini d'analyser la première colonne comme premier coup. Il aura compris qu'il y a un coup tueur pour l'adversaire à la 7ième ( faudrait en plus conserver la profondeur de gain car toutes les variantes sont gagnantes).
Donc dès qu'il commence avec une croix dans la deuxième, il tente un rond dans la septième et c'est fini. Là c'est des centaines de nœuds que tu vires !

Le seul hic, c'est que cette méthode ne marche que quand le jeu a déjà bien commencer.

Il y a mieux. Mais plus compliqué.

Exemple de solution. Tu appliques une profondeur de 6. Donc quand l'adversaire répond, sauf au premier coup, tu as déjà partiellement étudier cette réponse avec une profondeur de 4!

Suppose que tu ais stocké l'évaluation des ces réponses ? Et bien tu les rejoues dans l'ordre décroissant.

Tu peux aussi ranger les coups en fonction du plus grand nombre de jetons alignés qui aboutissent à la case.

Faire des mixtes entre les solutions (plus grand alignement + coup tueur s'il y en un )

Les choix sont immenses. L'efficacité de chaque choix dépendant de ton algo d'évaluation de la position.

Bref, des heures de test en perspectives.

Bon courage.

Voilà cela tourne :mouarf1:

C’est presque trivial maintenant !

Je mets mon sujet en résolu et je vous fais partager mon expérience (je n’en ai pas vu beaucoup lors de mes premières recherches).

C’était ma première implémentation de fonction récursive, j’ai mis beaucoup de temps à tester et à mettre au point pour les raisons suivantes :
- la compréhension de ce foutu « move bestmove » :aie:
- difficulté de faire des tests « unitaires » : j’ai testé en jouant des parties !
- au début mes fonctions simule() et efface() n’étaient pas correctes : comme on ne déjoue pas dans le même ordre que le jeu, il faut tenir compte de la profondeur
- la fonction d’évaluation est très importante : si elle ne chiffre que les coups gagnants, en début de jeu et avec une profondeur limitée cela joue n’importe quoi

Actuellement avec une profondeur de 7 l’I.A. mets 7s. pour réfléchir , mais comme tu le dis cela ne veut pas dire 1s par niveau !
Je vais maintenant travailler sur mon algo déterministe sans exploration (je propose le choix entre cet algo rapide ou le mini-max dans mon jeu).
Après l’idée de mixer les deux, j’y ai déjà pensé mais ce n’est pas évident : dans mon algo perso je construit la situation d’évaluation au fur et à mesure des coups joués. Je ne peux pas l’exploiter dans le mini-max car le « déjeu » nécessaire serait trop compliqué.

J’aime bien l’idée d’enregistrer les branches déjà explorées, je vais y réfléchir …