Discussion :

[bruce-willis]

Bonjour,

Je développe sous C et j'ai appris en théorie seulement les algorithmes de modélisation des jeux de réflexion (MINMAX, élagage ALPHA BETA) c'est à dire qu'il faut prédire à l'avance un certain nombre de coups de l'adversaire
Donc, dois-je savoir utiliser un ARBRE N-AIRE pour les mettre en pratique??

Enfin, othello, puissance 4 et tictactoe sont des jeux à somme nulle
Qu'en est-il du jeu d'échecs, dame (il y a un nombre fixe de pions qui diminue): somme nulle ou pas? Je ne sais pas si vous connaissez le jeu KONO, je ne crois que c'est à somme nulle, donc le MINMAX ne peut-il pas y être appliqué?

[PRomu@ld]

Donc, dois-je savoir utiliser un ARBRE N-AIRE pour les mettre en pratique??

A vrai dire non. Lorsqu'on applique ces algorithmes, bien souvent on ne construit pas physiquement les arbres, il sont implicitement construit par récursivité. Tu peux toujours les construire (avec une structure adéquat), mais ça ne présente que très peu d'intérêt.

Qu'en est-il du jeu d'échecs, dame (il y a un nombre fixe de pions qui diminue): somme nulle ou pas?

C'est un jeu a somme nulle et un MinMax/Alpha-Béta peut être utilisé.

[bruce-willis]

La récursivité toujours ou est-il possible d'utiliser la simple itération?

Le principe de l'arbre ne semble pas si parfait que cela, l'ordinateur est toujours battable même si on choisit bien le max pour l'ordi et le min pour l'humain, voyez le source du vainqueur d'un défi Delphi
http://delphi.ftp-developpez.com/sou...ueur%20exe.zip

Meme s'il exploite bien MinMax, on peut toujours battre l'ordi dans ce jeu PUISSANCE 4

[PRomu@ld]

Le problème du MinMax est la profondeur qui est fixée à l'avance. Au delà l'ordinateur est "aveugle". Ce qui est bon 3 coup à l'avance ne l'est pas forcément au quatrième.

La récursivité toujours ou est-il possible d'utiliser la simple itération?

C'est plus simple à écrire en récursivité, en itératif, il faut gérer la pile à la main, c'est relativement lourd à gérer.

[cedriku]

C'est plus simple à écrire en récursif mais lorsque le nombre d'appels récursifs est grand, la version iterative de l'algo peut s'avérer plus rapide et moins gourmande en memoire. Donc tout dépend de ce qui est programmé.

[bruce-willis]

L'arbre dans les tutos sur l'algo MinMax ne semble pas être complet

Par ex ici, pourquoi la racine n'a que 3 branches, pourquoi pas 9??

Le problème du MinMax est la profondeur qui est fixée à l'avance. Au delà l'ordinateur est "aveugle". Ce qui est bon 3 coup à l'avance ne l'est pas forcément au quatrième.

Ah bon, je ne le pense pas pour les exemples sur Morpion (TicTacToe)

Qu'en est-il de Negamax?? Est-ce meilleur que MinMax et l'élagage AlphaBeta?
Je ne comprend pas surtout les dires

on renvoie le max des opposes
des evaluations aux noeuds fils

Comment?

[PRomu@ld]

C'est plus simple à écrire en récursif mais lorsque le nombre d'appels récursifs est grand, la version iterative de l'algo peut s'avérer plus rapide et moins gourmande en memoire. Donc tout dépend de ce qui est programmé.

C'est de moins en moins un problème.

Par ex ici, pourquoi la racine n'a que 3 branches, pourquoi pas 9??

Parce que ça n'est qu'un exemple.

Ah bon, je ne le pense pas pour les exemples sur Morpion (TicTacToe)

Je parlais pour les jeux complexes comme pour les echecs où il n'est pas possible (sur des machines conventionnelles) de construire la totalité de l'arbre dans un temps raisonnable et dans un espace mémoire raisonnable.

Qu'en est-il de Negamax?? Est-ce meilleur que MinMax et l'élagage AlphaBeta?

Négamax c'est un minmax où tu ne cherches qu'à maximiser le résultat quelque soit le joueur. L'idée est d'inverser le signe à chaque tour. AlphaBeta est une optimisation applicable aussi à Négamax donc tu ne peux pas trop comparer (je ne suis pas un expert en MinMax/Negamax mais Negamax me semble juste plus simple a écrire, la complexité restant la même)

[bruce-willis]

Parce que ça n'est qu'un exemple.



AlphaBeta est une optimisation applicable aussi à Négamax donc tu ne peux pas trop comparer (je ne suis pas un expert en MinMax/Negamax mais Negamax me semble juste plus simple a écrire, la complexité restant la même)

D'accord !!!

Pourrait-on parler d'algorithmique ou d'IA sur MinMax et Negamax?

[PRomu@ld]

Pourrait-on parler d'algorithmique ou d'IA sur MinMax et Negamax?

Pour moi c'est clair et net, l'intelligence artificielle, c'est de l'algorithmique, quelque soit ce qui tourne derrière (MinMax, AlphaBeta, réseau de neurone, logique floue, ...).

[bruce-willis]

Je suis tout à fait d'accord!
Je souhaite qu'il y aura un vrai article Developpez.com expliquant le MinMax et AlphaBeta clairement autre que ceci! Ex: parmi les feuilles de l'arbre de jeu où le PC gagne, que choisit le PC?