4 Gewinnt KI?

[bruce85]

Hallo,
ich habe ein 4 Gerwinnt Spiel geschrieben, leider finde ich es nicht so gut ohne einen richtigen Gegner zu spielen.

Wie kann ich ohne grosse aufwand einen richtigen Gegner Programmieren?

1. Prüfe ob Computer gewinnen kann.
2. Prüfe ob Spieler gewinnen kann, wenn ja, dann dementsprechend blockieren.
3. Wenn keins von beiden zutrifft, dann den Stein für den Computer an einer gewissen stelle plazieren und die beste möglichkeit für den Computer finden um zu gewinnen.

Mein Spiel ist folgendermaßen aufgebaut:
Wenn ein Spieler auf irgendein Feld klickt, so wird der Stein von oben heruntergefallen, ist der Stein angekommen, dann ist der Computer an der reihe.

Für die berechnungen der KI bräuchte ich eigentlich nur die X-Variable zu verändern, wo der Stein dann hinein fallen soll.

Gibt es Vielleicht schon fertige Codeschnippsel oder könnt ihr mir Helfen wie ich das ambesten lösen kann?

Eine gute möglichkeit über Minmax gibt es ja, nur kenne ich mich leider nicht so gut aus damit.


Ich bedanke mich schonmal für die Hilfe.

MfG

 

[Noctarius]

Wenn du den Gegner nahezu unendlich stark machen willst kannst du das Ganze mit 2 If-Abfragen und einer Randbedingung lösen. Noch stärker kannst du ihn machen, wenn der Computer "vorraus denkt" also quasi Züge durchrechnet und bestimmt was wohl als nächstes passieren könnte / würde. Also eine Art Heuristik. Dann wird der menschliche Spieler aber nahezu nie gewinnen.

Der entscheidende Punkt bei einer KI ist immer: Nicht zu stark und nicht zu schwach. Ein PC muss sich also auch mal irren können.

 

[Tharsonius]

Ich habe vor ner halben Ewigkeit mal in einem Programmierpraktikum ein Tic Tac Toe programmiert, dort hatten wir auch eine KI. Eine starke (die ist definitiv nicht zu schlagen und verliert nie) und eine schwache, die sich ab und an mal vertan hat.

Wir (mein Team und ich) haben das damals so gelöst, dass wir jedes mögliche Feld bewertet haben. Dabei haben wir verschiedene Punkte vergeben. Wenn durch dieses Feld gewonnen werden konnte gabs 100, wenn ein Sieg des Gegners dadurch verhindert wird 90 und so weiter. Alles in allem haben wir dann am Ende eine Prioritätenliste der Felder erstellt und immer in das mit der höchsten Priorität gesetzt (in der schweren variante) oder halt auf random 3 (leichte Variante) gesetzt.


Ich würde das ähnlich machen. Ich würde für jedes Feld verschiedene Prioritäten vergeben. Belegte Felder und die, wo nicht reingesetzt werden kann bekommen 0, ansonsten in der Umgebung schauen.

3 eigene in einer Reihe = max Priorität (hier würde man ja gewinnen)
3 gegnerische in einer Reihe = zweithöchste Priorität
etc.

Wird natürlich etwas komplizierter, wenn es darum geht zu schauen was für Optionen der Gegner durch den platzierten Stein bekommt, aber am Ende hast Du halt dann eine Liste und kannst dann auf die entsprechenden Felder setzen.

 

[ARadauer]

die ist definitiv nicht zu schlagen und verliert nie

das bezweifle ich. wenn man bei tic tac toe richtig anfängt und keinen fehler macht... kann man nicht verlieren, nur gleichstand
noch nie wargames gesehen?

 

[Tharsonius]

Deswegen sagte ich ja auch nicht "gewinnt immer" sondern "verliert nie".
Die KI im schweren Modus gewinnt entweder oder spielt unentschieden. Sie verliert aber nie.

 

[Landei]

"Vier gewinnt" ist komplett durchgerechnet, und der erste Spieler kann immer gewinnen.

The game was solved mathematically by James D. Allen (1 October 1988), and independently by Victor Allis (16 October 1988).[2] With perfect play, the first player can force a win by starting in the middle column. By starting in the two adjacent columns, the first player allows the second player to reach a draw; by starting with the four outer columns, the first player allows the second player to force a win.

There are a few programs that claim the ability to play a perfect game of connect four; Mustrum (Lars Bremer), Velena (Giuliano Bertoletti), and TitOT (David Halabi) are three such programs that can be downloaded as freeware.

Connect Four - Wikipedia, the free encyclopedia

 

[Marco13]

Eigentlich braucht man für eine "gute" KI nur zweieinhalb Sachen:
Man muss Züge ausführen können (das ist die halbe )
Man muss Züge rückgändig machen können
Man muss das Spielfeld "bewerten" können.

Das ist bei Vier Gewinnt alles ziemlich einfach. Der Rest ist dann nur noch das MinMax-Schema, das man da "drumdstrickt", oder Alpha-Beta, wenn's etwas besser sein soll...

 

[bruce85]

Vielen Dank für die antworten.

Leider verstehe ich das nicht ganz mit Minimax/Alpha-Beta.

Hier ist meine Methode, wenn der Computer an der reihe ist:
[JAVA=1]public void computerZug() {
for (int y=0; y<6; y++) {
for (int x=0; x<7; x++) {
//Wenn der Spieler hier gewinnen kann, dann blockieren
if (spielFeld[x][y] == 1) {
if ((spielFeld[x+1][y] == 1) && (spielFeld[x+2][y] == 1) && (spielFeld[x+3][y] == 0) && (spielFeld[x+3][y+1] > 0)) {
steinFeldX = x+3;
}
}
}
}
//u.s.w........
steinMove = true;
steinPX = 0;
steinFeldY = -1;
steinPosX = 17+(steinFeldX*26)+(steinFeldX/1)*4;
steinPosY = getHeight()-203+(steinFeldY*26)+(steinFeldY/1)*4;
}[/code]

So in dieser art habe ich mir das vorgestellt.
Wie könnte ich das mit Minimax lösen?
Könnte mir Vielleicht jemand einen beispiel Code posten?

Ich wäre euch sehr dankbar dafür.

MfG

 

[Schumi]

Alpha-beta pruning - Wikipedia, the free encyclopedia

In kurz (und evtl. auch nicht ganz korrekt, ist doch schon sehr lange her) Der PC stellt einen Baum auf der unterschiedlichen Spielzugmöglichkeiten und schneidet dann die sinnlosen Äste ab. Der Algorithmus an sich ist recht einfach, das Herzstück bei solchen ist dann immer die Evaluationsfunktion. An der kann man sich dann beliebig austoben. (Sollte bei 4-Gewinnt aber nicht so schwierig sein.)

 

[Marco13]

Du könntest vielleicht mit Minimax - Wikipedia, the free encyclopedia anfangen: Der ist etwas einfacher (und insbesondere: Einfacher zu debuggen) als der AlphaBeta, benötigt aber (in bezug auf das Spiel) die gleichen Funktionen, d.h. kann später "leicht" zu AlpahBeta verbessert werden. Und für VierGewinnt reicht er allemal: Wie viele Züge denkt man bei so einem Spiel schon voraus? Ich glaube, eine KI die 3 Halbzüge voraus denkt würde unter "normalen" Bedingungen schon die meisten Spieler schlagen.

EDIT: Auf Minimax-Algorithmus ? Wikipedia ist der Pesudocode etwas ausführlicher (weniger Pseudo ), d.h. kann wohl "direkter" nach Java übersetzt werden...