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?