Discussion :

[Gouyon]

Salut

C'est avec un grand interrêt que j'ai lu l'article sur l'algorithme min max et alpha beta de "fearyourself". Je l'ai d'ailleurs utilisé pour une variante du jeu de dame. Par contre je voudrais l'utiliser pour un jeu dans lequel il y a 4 joueurs. C'est à dire qu'il peut y avoir jusqu'à 3 IA et un joueur humain. La question que je me pose alors est comment gérer les noeuds min ? En effet pour chaque IA il y a 1 noeud max et 3 noeuds min par tour de jeu. Sachant que chaque joueur ne va pas faire en sorte de jouer le coups qui mettra son adversaire dans une situation difficile comme il est postulé dans le cas d'un jeu avec seulement deux joueurs.

A+

Rémi

[Sivrît]

Pourquoi ne pas évaluer une position sous la forme d'un quadruplet ? Chaque joueur pourrait les évaluer en retirant à la valeur de sa position (son nombre de pions ou je ne sais quoi) la somme des scores de ses adversaires. D'autre fonctions sont possibles, par exemple se comparer seulement au max des scores adverses ou au contraire essayer de taper sur le plus faible

Sinon avec une seule valeur il faut considérer que l'on est seul contre tous mais ce n'est pas réaliste car les adversaires ne coopèrent généralement pas... du moins au début.

Si l'évaluation d'une position est plus compliquée et ne permet pas d'avoir un score par joueur, il faudrait remonter la position visée pour refaire les calculs du point de vu de chaque joueur mais ça sera peu performant.

[fearyourself]

C'est avec un grand interrêt que j'ai lu l'article sur l'algorithme min max et alpha beta de "fearyourself". Je l'ai d'ailleurs utilisé pour une variante du jeu de dame. Par contre je voudrais l'utiliser pour un jeu dans lequel il y a 4 joueurs. C'est à dire qu'il peut y avoir jusqu'à 3 IA et un joueur humain. La question que je me pose alors est comment gérer les noeuds min ? En effet pour chaque IA il y a 1 noeud max et 3 noeuds min par tour de jeu. Sachant que chaque joueur ne va pas faire en sorte de jouer le coups qui mettra son adversaire dans une situation difficile comme il est postulé dans le cas d'un jeu avec seulement deux joueurs.

C'est de loin pas un problème évident à faire... Si tu veux une solution adéquate, il faudrait taper dans Equilibrium Points in N-person Games de John Nash.

Sa conclusion était que pour gagner il ne fallait pas viser à faire perdre tout le monde sauf toi mais de tenter de faire que tout le monde gagne mais moins...

Bien sûr, programmer un comportement tel n'est pas forcément évident (quoi que...)

Une solution qui semble donné un résultat (dans mon humble expérience) est de faire un min-max en considérant un meta-adversaire qui est composé des évaluations de tous les adversaires...

Du coup, on peut faire différentes combinaisons :

- Une moyenne des évaluations de chaque adversaire avec le cas particulier de la victoire de l'adversaire qui provoque le pire des scores (en gros, si un adversaire gagne alors on considére que le meta-adversaire gagne)...

- Le meilleur score des adversaires est pris comme score du meta-adversaire.

Ensuite, on peut s'amuser lors du calcul du coup de l'IA. Il peut aussi considérer les autres joueurs ordis comme des ennemis ou alors il peut considérer les autres ordis comme des alliés... Cela dépend du type de jeu...

Voilà, c'est un début de réflexion...
Jc

[EDIT]
Wow , j'ai presque (voir entièrement fait du plagiat du post de Sivrît sans l'avoir vu...
Et avec le temps entre les deux posts, j'ai presque pas d'excuses...
Désolé
[/EDIT]

[Sivrît]

Equilibrium Points in N-person Games de John Nash.

Mais j'avais pas du tout la théorie


Après une nuit de sommeil, je déconseille plutôt la somme des scores des adversaires. Cela indiquerait mathématiquement qu'un échange de pion est neutre ce qui n'est pas le cas car on en a trois fois moins que les gens d'en face. En fait ce serait bénéfique au deux joueurs restés en dehors du coup, ce qui n'était pas mon intention.

Utiliser le max est mieux... mais on risque de se sacrifier pour rabaiser le meilleurs joueur et là encore les deux autres en profitent. La moyenne me semble plus équilibrée.

C'est peut-être déjà le cas mais l'heuristique d'évaluation devrait prendre en compte la proxilité des pions à la dame. Si l'on est A contre B et C et que l'on compte les pions, un échange de pions avec B n'affecte pas C... sauf si on lui dégage un chemin vers la dame. Donc il faudrait dans ce cas que le score de C soit affecté à la hausse. Le min max devrait le voir mais avec le nombre de coups possibles (avoir 4 joueurs ne va pas aider) on risque un effet d'horizon assez pervers.

[fearyourself]

Après une nuit de sommeil, je déconseille plutôt la somme des scores des adversaires. Cela indiquerait mathématiquement qu'un échange de pion est neutre ce qui n'est pas le cas car on en a trois fois moins que les gens d'en face. En fait ce serait bénéfique au deux joueurs restés en dehors du coup, ce qui n'était pas mon intention.

En effet, cela dépend du jeu (qui a parlé de pion??). Mais si l'évaluation prend en compte le nombre de pion des adversaires alors :

- Les deux qui sont restés en dehors y gagne (il y aura moins de pions)
- Les deux qui ont fait l'échange gagne un peu et perde un peu (il y a des pions en moins mais ils en ont moins aussi)

Je pense que cela dépend vraiment du jeu...

Utiliser le max est mieux... mais on risque de se sacrifier pour rabaiser le meilleurs joueur et là encore les deux autres en profitent.

Exact

La moyenne me semble plus équilibrée.

Oui mais on peut supposer avoir un joueur très fort et un joueur très nul du coup l'évaluation dit que c'est moyen ce qui n'est pas juste non plus...

C'est peut-être déjà le cas mais l'heuristique d'évaluation devrait prendre en compte la proxilité des pions à la dame.

De quel jeu tu parles maintenant?

Si l'on est A contre B et C et que l'on compte les pions, un échange de pions avec B n'affecte pas C... sauf si on lui dégage un chemin vers la dame. Donc il faudrait dans ce cas que le score de C soit affecté à la hausse. Le min max devrait le voir mais avec le nombre de coups possibles (avoir 4 joueurs ne va pas aider) on risque un effet d'horizon assez pervers.

Il est clair que l'algorithme du Min-Max est un algorithme théorique, ensuite il faut passer au Alpha-Beta ou à un A* pour faire quelque chose de plus sérieux...

Jc

[Gouyon]

Tout d'abord merci pour tous ces avis et conseils. Pour concrétiser un peu plus les réflexions le jeu en question est le Djambi ou échec de Machiavel ou vous pouvez trouvez les règles ici:http://ludism.free.fr/Regles/fr/Djambi.htm Elles sont simple et pas longues à lire.
Pour la fonction d'évaluation j'attribue à chaque pion du camps dont c'est le tour de jouer une valeur positive variable en fonction de son importance (comme aux échec une dame vaux plus qu'un cavalier) et à chaque pion du camps adverse une valeur négative et j'en fait la somme. De plus cette somme peut varier en fonction de la position de certains pions comme le chef (voir règles) et d'autre part la perte de pièces particulières comme la nécromobile (voir règles).
Donc je m'oriente plus vers un algorithme min-max (en fait plutôt un alpha beta) la où se situe le problème c'est qu'à moins de considérer que toutes les IA sont contre l'humain (Il y a un Smith dans le programme ) chaque IA n'a pas forcément intérêt à jouer le coup le plus défavorable au joueur humain pour gagner. D'autant plus qu'à 3 contre un la victoire risque d'être facile et donc le jeu de peu d'intérêt. Dans ce jeu la meilleure stratégie est de faire en sorte que vos adversaires se combattent entre eux et une fois qu'ils sont suffisamment faible vous prennez le pouvoir .


Je vais essayer de regerder ce livre (Equilibrium Points in N-person Games de John Nash). Sinon c'est quoi un algorithme A* ?