Gomoku Array-basierten AI-Algorithmus?

StackOverflow https://stackoverflow.com/questions/2753399

Frage

Way Weg zurück (man denke 20+ Jahre) stieß ich auf ein Gomoku Spiel Quellcode in einem Magazin, dass ich in meinen Computer eingegeben und hatten viel Spaß mit.

Das Spiel war schwierig, gegen zu gewinnen, aber der Kern-Algorithmus für die Computer-KI war wirklich einfach und berücksichtigten nicht viel Code. Ich frage mich, ob jemand diesen Algorithmus kennt und hat einige Links zu einer Quelle oder Theorie über sie.

Die Dinge, die ich war nicht vergessen, dass es im Grunde ein Array zugeordnet, die das gesamte Brett abgedeckt. Dann, wenn ich, oder es, ein Stück platziert, wäre es eine Anzahl von Gewichten an alle Standorte auf dem Brett hinzufügen, dass das Stück würde möglicherweise Auswirkungen.

Zum Beispiel (beachten Sie, dass die Gewichte definitiv falsch sind, wie ich erinnere mich diese nicht): 

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

Dann einfach das Array für eine offene Stelle mit dem niedrigsten oder höchsten Wert abgetastet wird.

Dinge, die ich bin fuzzy auf:

  • Vielleicht hatte es zwei Reihen, eine für mich und eine für sich und es gab eine Min- / Max-Gewichtung?
  • Es könnte dich mehr zu dem Algorithmus, aber in seinem Kern war es im Grunde ein Array und gewichtete Zahlen

Ist dieser Ring eine Glocke mit jemandem überhaupt? Jeder bekommt alles, was helfen würde?

War es hilfreich?

Lösung

Lese Ihre Beschreibung, und ein wenig darüber nachzudenken, ich denke, es wahrscheinlich mit einem einzelnen Array funktioniert, genau so, wie Sie beschrieben.

, um das Ziel zu erreichen des Erhaltens fünf-in-a-Zeile, die Sie (a) haben verhindert, dass der Gegner erfolgreich verläuft und (b) gelingt selbst.

selbst Um erfolgreich zu sein, müssen Sie Platz Steine ??in der Nähe von anderen Steinen Sie bereits auf dem Brett, so dass es Sinn macht, eine positive Bewertung für Felder hinzufügen neben dem Stein, die in einer Reihe teilnehmen konnten. Entweder ist die lineare Beispiel gab dir, oder etwas quadratische wäre wahrscheinlich gut funktionieren.

Um zu verhindern, dein Gegner erfolgreich verläuft, müssen Sie Platz Steine ??neben sein / ihr Steine. Es ist besonders gut, wenn man mit einem einzigen Stein zwei Vögel schlagen, so gegnerischen Steine ??auf den Wert der umliegenden Felder der gleichen Art und Weise Sie tun erhöhen sollten - die mehr Steine, die er bereits hat aufgereiht, desto höher die Punktzahl, und desto wahrscheinlicher ist die Algorithmus wird versuchen, den Gegner aus zu schneiden.

Das Wichtigste hier ist die Gewichtung der einzelnen Felder, und ob die Steine ??des Gegners unterschiedlich gewichtet werden als deine. Leider kann ich nicht helfen mit, dass, aber die Werte sollte relativ einfach sein Versuch und Irrtum, wenn das Spiel, um herauszufinden, über sich selbst geschrieben wird.

Dies ist jedoch ein sehr einfacher Ansatz, und würde von einem Baum Suchalgorithmus übertroffen wird. Google-Suche, gibt es einen Zusammenhang Papier auf Threat Suche , die für Gomoku gut funktioniert offenbar. Das Papier ist hinter einer Pay-Wand aber: /

Andere Tipps

Ich habe den Artikel nicht, aber aus der Beschreibung würde meine Vermutung irgendeine Form der Minimax Algorithmus

ich diesen Algorithmus haben Sie erwähnt - es war ziemlich einfach und schnell (kein Rückzieher :-)), und es hat sehr gut gespielt :-) Ich muss die Quelle irgendwo haben, aber es ist vor vielen Jahren ... Es waren Gewichte Ihre Steine ??je nachdem, wie viel von anderen Steinen waren in der Nähe, und Gewichte von oponent Steinen. Diese waren niedriger, so der Algorithmus die angreifende Strategie bevorzugt.

Aber das ist natürlich sehr triviale Algorithmus. Gewinnstrategie wurde bereits gefunden. Sehen Sie dieses Papier: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens. Go-Moku und Threat-Raum-Suche . Es hat mir sehr geholfen, als ich mein eigenes Programm writting. Auf diese Weise werden Sie zu Schreibprogramm in der Lage, die beim Angriff auf den Gegner ist sehr gut und die Suche nach einer Gewinnkombination.

Es ist ein altes Spiel - ich den Code gefunden auf Planeten Source Code . Ich spielte dieses Spiel während des Studiums und in 286 Tagen hatte eine BASIC Version davon.

Hier ist das Programm, das Sie suchen ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw /gomoku.c

Es ist fast 40 Jahre alt

Arbeiten auf einer Open-Source-Version für das iPhone.

Hit me up bei Interesse an einem Beitritt!

https://github.com/kigster/kigomoku

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top