Une bonne représentation minimax à Gomoku?

Question

J'essaie de coder un jeu Gomoku (cinq conséquences) en Java en tant que projet individuel. Pour l'IA, je comprends que l'utilisation d'une fonction minimax avec l'élagage alpha-bêta est un bon moyen de l'approcher. Cependant, j'ai un peu de mal à imaginer comment cela fonctionnerait.

Ma question est la suivante: Qu'est-ce qu'une bonne représentation pour un nœud dans un arbre minimax?

Je pense que ma fonction d'évaluation "pèsera" tous les espaces vides du tableau. Il prendra ensuite la meilleure valeur de cette carte comme nœud de l'arbre de décision Minmax. Suis-je dans la bonne direction?

Et tous les autres conseils sont également les bienvenus! Merci d'avance!

Answer 1

La recherche d'espace d'État se fait par les différents états du conseil d'administration. Il y a beaucoup de mouvements, car vous pouvez placer une pierre n'importe où inoccupée. Chaque état peut être représenté comme une matrice EG 9x9, avec 3 valeurs - blanc, noir ou inoccupé. Avec une carte 9x9, il y a donc 3 ^ 81 états du conseil possible.

De n'importe quel état de conseil, le nombre de mouvements est le nombre de sommets inoccupés. Vous pouvez placer une pierre sur l'un de ces sommets. Vous ne pouvez jouer que votre propre couleur. Donc, tout au plus il y a 81 mouvements possibles .. 81 pour le premier mouvement, 80 pour le second, etc. Vous pouvez donc rechercher à la profondeur 5 raisonnablement, et peut-être plus .. pas trop mal.

La représentation appropriée est, comme mentionné, une matrice 2D - il peut s'agir d'un tableau 2D d'INTS, avec des valeurs par exemple 0 pour inoccupées, 1 pour le blanc, 2 pour le noir. ... int [9,9].

Votre fonction d'évaluation ne sonne pas très bien. Au lieu de cela, je donnerais des points pour les éléments suivants:

- Obtenez 5 d'affilée - donnez-lui essentiellement le score maximum pour celui-ci, car c'est une victoire - 4 conséquences avec 2 extrémités ouvertes - également un score maximum, car l'adversaire ne peut pas vous empêcher d'obtenir 5. - 4 de suite avec 1 extrémité ouverte - toujours une position très menacée, car l'adversaire doit jouer à un seul endroit pour bloquer. - 3 d'affilée avec 2 extrémités ouvertes - Score très élevé à nouveau --- 4, 3, 2, 1 avec les deux extrémités fermées - 0, car il ne peut jamais en faire 5 d'affilée.

etc.

Ensuite, vous appliquez simplement l'algorithme minimax standard - c'est-à-dire l'élagage alpha bêta - ce serait exactement le même que les échecs, mais vous avez un générateur d'espace d'état différent et une fonction d'évaluation.

Answer 2

Je considérerais une fonction d'évaluation du formulaire suivant: considérez chaque ensemble de, disons, 6 positions dans une ligne. (Sur une carte 19x19, il y en a 14 le long de chaque ligne et des nombres variables de 0 à 14 le long de chaque diagonale; je pense que cela vient à 742 d'entre eux sur toute la carte. Mon arithmétique peut être erronée.) Pour chaque ensemble, il y a 729 arrangements possibles d'espaces noirs, blancs et vides. Ou, euh, 378 si vous tirez compte de la symétrie de bout en bout. Ou, euh, euh, moins que cela, mais je ne peux pas être dérangé de déterminer combien de moins si vous prenez en compte la symétrie noire / blanc.

Alors maintenant, votre fonction d'évaluation consistera en un tableau de table pour chaque bloc de 6 pierres, dans une table d'éléments de 378 ou de manifeste (ou peut-être deux d'entre elles, une pour les lignes horizontales et verticales, une pour les lignes diagonales) . Additionnez les résultats et c'est votre évaluation de la position.

Il peut s'avérer qu'en réalité une table plus grande (dérivée d'une rangée plus longue de positions) fonctionne mieux.

Mais qu'est-ce qui se passe dans le tableau? Laissez votre programme résoudre cela. Commencez par des valeurs arbitraires dans le tableau (vous pourriez, par exemple, prendre EVAL (ligne) = #Black (ligne) - # White (ligne) ou quelque chose). Laissez votre programme jouer lui-même en utilisant la recherche Alpha-Beta. Maintenant, mettez à jour les entrées de table en fonction de ce qui se passe. Il existe de nombreuses façons différentes de le faire; Voici quelques-uns (décrits sketchily).

• Au cours de chaque jeu, gardez une trace du nombre de fois où chaque modèle s'est produit dans les positions de chaque joueur. Lorsque le jeu est terminé, ajustez le score de chaque modèle afin que les modèles vus plus souvent par le joueur gagnant soient plus beaux.
• Chaque fois que vous effectuez une recherche, ajustez les scores des modèles en position actuelle pour rapprocher le score statique actuel du score obtenu par recherche.
• Chaque fois qu'un mouvement est effectué, ajustez les scores de chaque modèle de la position "avant" pour faire en sorte que le score "avant" corresponde mieux au score "After".
• Ont beaucoup de tables différentes (d'où beaucoup de variantes différentes de la fonction d'évaluation). Laissez-les jouer les uns contre les autres. Appliquez une sorte d'évolution (par exemple, jouez tout contre tous, puis jetez les pires interprètes et remplacez-les par des mutants dérivés des meilleurs interprètes).

Pour une version plus sophistiquée de ces idées (appliquée aux échecs, mais les mêmes idées fonctionneraient bien pour Gomoku), jetez un œil à http://cs.anu.edu.au/~lex.weaver/pub_sem/publications/knightcap.pdf .