Discussion :

[Schpountz42]

Bonjour,
Je dois créer un dérivé du jeu de Nim. Pour le moment, le jeu tourne autant manuellement qu'avec une IA (algo minimax, et alpha-beta prévus).
Cependant, pour le moment l'ia ne peut évaluer que les fin de partie et doit donc parcourir tout l'arbre pour déterminer le meilleur coup, mais je voudrais permettre de définir une profondeur maximal de parcours de l'arbre de stratégie. Pour cela, il me faut une fonction d'évaluation heuristique que je ne trouve pas (ni de moi-meme ni sur google).

Je vais maintenant expliquer de quel dérivé du jeu de Nim il s'agit:
En général on représente le jeu de Nim comme une série d'allumettes auquelle on enlève 1, 2 ou 3 allumettes a une extrémité de la serie.
Mais dans mon jeu, on peut enlever ces allumettes en milieu de plateau mais toujours de façon adjacentes.

Exemple de coup :
||||| pourrait donner
=> |-|||
=> |---|
=> --|||
=> ||--|
...

Bref on peut se retrouver avec plusieurs série d'allumettes.


Quelqu'un peut m'aider à trouver une fonction heuristique efficace?

[Sylvain Togni]

Ça m'étonne qu'un simple minmax soit trop lent à parcourir tout l'arbre. Tu as combien d'allumettes au départ ?

Gères-tu bien les transpositions (positions identiques atteintes par deux chemins différents) ?

Parce que ça semble être un jeu qui se prête mal a une fonction d'évaluation ou a une quelconque heuristique, mais un jeu purement combinatoire.

[Schpountz42]

En fait ca lutte à partir de 7 allumettes au départ. Mais selon les tests, c'est le 1er coup de l'IA qui prend la totalité du temps, les autres sont instantanées. Cela vient donc de la création des objets composant l'arbre de stratégie. (je développe en Java)
Donc je voulais une fonction heuristique afin de permettre de ne pas avoir besoin de créer tout l'arbre d'un seul coup.

Et à propos des positions identiques, le même objet représent les 2 cas de chemin. Ce qui fait que chaque noeud de l'arbre peut avoir plusieur père, c'est donc plutot un graphe^^

[Sylvain Togni]

Bizarre, j'ai fait un petit essai rapide, j'arrive à explorer l'arbre (enfin le graphe) complet jusqu'à 20 allumettes (2-3 secondes). Avec 7 allumettes, le graphe n'a que 67 noeuds. N'as-tu pas fait une erreur quelque part ? (à moins que ça soit moi ?)

A noter que jusqu'à 25 allumettes (j'ai pas été plus loin), le joueur qui commence peut toujours s'arranger pour gagner.

[Schpountz42]

67 noeuds ca m'étonne mais c'est possible.
C'est pas l'exploration qui est long mais plutôt la création des objets utilisés. Car seul le 1er coup est long, les autres sont quasi instantannés puisque les objets sont déjà créer.
Donc on cherche comment réduire le nombre d'objets ou optimiser tout ca, mais en parralèlle une fonction heuristique nous permettrai de ne pas être obliger de créer tout l'arbre d'un coup. Ce qui partagerait sa création sur les différents coups et ca rendrai jouable sur un plus grand nombre d'allumettes.

Tu vois le principe?

[Schpountz42]

Je viens d'améliorer un truc qui allait pas (une méthode equals mal redéfinie), ce qui a bien accéléré le jeu. Maintenant la partie de 7 allumettes se joue en 0.4 seconde, mais à 11 allumettes il met 118 secondes, donc ça avance mais c'est pas fini.
(pour info, je fais mes test en lancant 2 IA qui joue ensemble)

Donc je suis toujours preneur pour une fonction heuristique^^

[Sylvain Togni]

Je ne suis pas sur qu'il existe une heuristique pour ce type de jeu, qui ne semble pas du tout être stratégique comme les échecs ou les dames, mais purement combinatoire. Comment savoir si un coup à plus de chance de mener à la victoire qu'un autre ? Mystère.

Par contre il y a moyen de bien accélérer le minmax en gérant bien toutes les transpositions. Par exemple les positions suivantes sont équivalentes en terme de solution : |--||, ||--|, |-||-, -||-|, ... Elles peuvent donc toutes être regroupées en un seul noeud dans le graphe.

En rajoutant ça à mon petit essai rapide j'en suis à moins d'une seconde pour 50 allumettes, ça commence à être intéressant, non ?

[Schpountz42]

Ui j'ai envisager cette solution avec mon binome. Mais vu que le jeu a pour but d'être afficher, on doit prévoir derrière quelque chose pour que l'affichage ne soit pas anarchique et que ça reste jouable.

Je ne voudrait pas qu'on passe de |||--|||| à ||----||| ou -||-|||-- au lieu de |||----|| (en enlevant 2 allumettes a droite).
Bref on y réfléchi, mais il doit y avoir autre chose quand même qui gène, on le cherche^^


EDIT :
Je viens de tilter un truc qui me coûte sûrement beaucoup de noeud. On caractérise un noeud par l'état du plateau à un instant t, ET le joueur qui a le tour.
Ce qui fait que que 2 tours de jeu qui auront le même plateau mais pas le même joueur courant, seront représentés par 2 noeuds eux aussi différents.
Tu penses que ça me coûte chère?

[Sylvain Togni]

Ui j'ai envisager cette solution avec mon binome. Mais vu que le jeu a pour but d'être afficher, on doit prévoir derrière quelque chose pour que l'affichage ne soit pas anarchique et que ça reste jouable.

Je ne voudrait pas qu'on passe de |||--|||| à ||----||| ou -||-|||-- au lieu de |||----|| (en enlevant 2 allumettes a droite).
Bref on y réfléchi, mais il doit y avoir autre chose quand même qui gène, on le cherche^^

Il suffirait peut-être de traiter le premier coup (celui qui va être affiché donc) différemment des suivants.

Je viens de tilter un truc qui me coûte sûrement beaucoup de noeud. On caractérise un noeud par l'état du plateau à un instant t, ET le joueur qui a le tour.
Ce qui fait que que 2 tours de jeu qui auront le même plateau mais pas le même joueur courant, seront représentés par 2 noeuds eux aussi différents.
Tu penses que ça me coûte chère?

Au maximum un facteur 2.