basée sur la baie Gomoku AI-algorithme?

Question

Chemin du retour à sens unique (pensez 20+ ans) je rencontrais un code source du jeu Gomoku dans un magazine que je tapé pour mon ordinateur et a eu beaucoup de plaisir avec.

Le jeu était difficile de gagner contre, mais l'algorithme de base pour l'ordinateur AI était vraiment simple et ne tenait pas compte beaucoup de code. Je me demande si quelqu'un sait cet algorithme et a des liens vers une source ou d'une théorie à ce sujet.

Les choses que je me souviens est que fondamentalement alloué un tableau qui couvrait l'ensemble du conseil. Ensuite, chaque fois que je, ou, placé un morceau, il ajouterait un certain nombre de poids à tous les endroits sur la carte que la pièce serait peut-être l'impact.

Par exemple (notez que les poids sont certainement tort que je ne me souviens pas ceux):

1   1   1
 2  2  2
  3 3 3
   444
1234X4321
  3 3 3
 2  2  2
1   1   1

Ensuite, il suffit de numériser le tableau pour un emplacement ouvert avec la plus faible valeur ou.

Ce que je suis floue sur:

• Peut-être avait deux tableaux, un pour moi et un pour lui-même et il y avait un min / max pondération?
• Il pourrait avoir été plus à l'algorithme, mais à sa base, il était essentiellement un tableau et nombres pondérés

Est-ce une cloche avec anneau qui que ce soit? Quelqu'un at-il quelque chose qui pourrait aider?

Answer 1

La lecture de votre description, et de penser un peu, je pense que cela fonctionne probablement avec un seul tableau, la façon dont vous exactement décrit.

Pour atteindre l'objectif d'obtenir cinq en une ligne que vous devez (a) empêcher l'adversaire de réussir et (b) vous réussir.

Pour vous réussir, vous devez pierres place à proximité d'autres pierres que vous avez déjà sur la carte, il est donc logique d'ajouter un score positif pour les champs à côté de vos pierres qui pourraient participer à une rangée. Soit l'exemple linéaire vous a donné, ou du second degré quelque chose serait probablement bien fonctionner.

Pour éviter que votre adversaire de réussir, vous devez placer des pierres à côté de ses / ses pierres. Il est particulièrement bon si vous frappez deux oiseaux avec une seule pierre, de sorte que les pierres de l'adversaire devrait augmenter la valeur des champs environnants de la même manière à vous faire - plus de pierres qu'il a déjà alignés, plus le score, et plus il est probable algorithme va essayer de couper l'adversaire.

La chose la plus importante est ici la pondération des différents domaines, et si les pierres de l'adversaire sont pondérées différemment que le vôtre. Malheureusement, je ne peux pas aider, mais les valeurs doivent être raisonnablement simples à comprendre par essais et erreurs une fois que le jeu lui-même est écrit.

Cependant, cette approche est très basique, et serait dépassé par un algorithme de recherche d'arbre. Recherche Google, il y a un papier sur la recherche des menaces , qui fonctionne apparemment bien pour Gomoku. Le papier est derrière un mur de paie cependant: /

Answer 2

Je n'ai pas lu l'article, mais de la description je pense serait une forme de Minimax algorithme

Answer 3

J'ai vu cet algorithme vous avez mentionné - il était assez simple et rapide (pas de retour arrière :-)) et il a joué très bien :-) Je dois avoir quelque part la source, mais il est il y a quelques années ... Il y avait beaucoup de poids pour vos pierres en fonction de combien d'autres pierres étaient près, et le poids des pierres oponent. Ceux-ci ont été plus faibles si l'algorithme préféré la stratégie d'attaque.

Mais cela est de l'algorithme bien sûr très trivial. Stratégie gagnante a déjà été trouvé. Voir cet article: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens. Go-Moku et Threat-Space Recherche . Il m'a beaucoup aidé quand j'ecrivais mon propre programme. De cette façon, vous serez en mesure de programme d'écriture qui est très bon pour attaquer l'adversaire et de trouver des combinaisons gagnantes.

Answer 4

Il est un ancien jeu - j'ai trouvé le code sur planète Source code . Je jouais ce jeu au cours de collège et 286 jours avait une version de base de celui-ci.

Answer 5

Voici le programme que vous recherchez ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw /gomoku.c

Il est près de 40 ans

Answer 6

travail sur une version open source pour iPhone.

Hit me up si vous êtes intéressé à vous joindre!

https://github.com/kigster/kigomoku