Perfekte KI für Vier Gewinnt
-
Hallo zusammen,
ich bin im Moment dabei, für die Schule ein Vier Gewinnt in C++ zu programmieren. Es geht vor allem um die KI. Ziel ist es eine perfekte KI zu erhalten.
Mein Lehrer meinte, dass das ein triviales Problem darstellen sollte. Doch hatte ich schon ziemliche Probleme eine KI zu schreiben, die 20 Züge weit berechnet (dauert fast eine Minute pro Zug).
In dem Programm habe ich im Moment die AlphaBeta-Suche eingebaut, sowie einige Verbesserungen wie Hash-Tabellen und eine einfache Zugsortierung (Züge von innen nach außen ausprobieren).
Aber das scheint nicht zu reichen.Jetzt zu meiner Frage:
Gibt es Optimierungen, die das Programm noch wesentlich beschleunigen könnten?
Ich habe z.B. was von Bitboards gehört, aber damit kann ich im Moment nichsts anfangen (bzw. ich verstehe das nicht).Über Ideen wäre ich sehr dankbar, da die Zeit langsam relativ eng wird....
-
Hi,
AlphaBeta-Suche kenne ich nicht. Eine Hashmap bei so einem kleinen Spielfeld erscheint mir ziemlich uebertrieben.
Ich wuerde die KI schrittweise aufbauen. Ein (hypothetischer) Spielzug sollte erstmal natuerlich schauen, ob er irgendwo 4x vollmachen kann. Geht das nicht, sollte er schauen, ob 4x zu verhindern ist. Wenn das auch nicht der Fall ist, sollte er versuchen irgendwo etwas Vorhandes zu erweitern. Wenn das nicht geht, Randomzug.
Das waere schon Mal sehr grundlegend. Na ja und dann wuerde ich diesen Zug fuer Dich selbst und fuer die CPU mehrfach ausfuehren im Hintergrund und dann hast Du ja ganz viele Kombinationen.
Ich weiss nicht, ob Du gerade jedes einzelne Feld durchprobieren laesst, aber wenn Du nach o.g. Regeln die Zuege machst und dafuer durchgehst, sollte es schneller gehen.
Dann erhaeltst du ganz viele Pfade und jeder Pfad der zu deinem Verlust wird, stirbt natuerlich. Wenn das Performanceprobleme gibt, koennte man die Berechnung evtl. in Dateien speichern. Auch schlau ist, fuer den naechsten Zug die vorherigen Daten zu nutzen, z.B., indem du sie in einem Baum speicherst o.ae.
Wenn Du das alles schon hast, tut's mir natuerlich Leid. Dass bei 20 Zuegen schon so viel Rechenzeit drauf geht, find ich eigentlich krass. Es sind ja nur 49 Felder und bei 20 Zuegen (also fuer mich sind das 40 Chipeinwuerfe) hast Du ja schon 40 Felder voll. Und wenn auch noch Pfade wegfallen und Du immer "nur" den optimalen Zug nimmst, sollte das doch machbar sein.
-
Online durchrechnen kannste das noch nicht.
Aber es hat schon einer offline gemacht.
Aber nur mit (voll GUT Mathe UND voll GUT Computerfux) UND voll VIEL Zeit.
Dafür ist es schon saulange her.
Such erstmal nach "connect 4 perfect play".
Danach such, ob dein Lehrer einen Sockenschuss hat. Ich nehme an, er hat einen so großen, daß es schon in Wikipedia dokumentiert ist.
Such nach "Sockenschuss" und schau, ob bei den Quellen ein Link auf Deinen Lehrer ist.
Die perfekte KI für 4-Gewinnt ist sowas von exorbitant jenseits der Schule,ich fasse es ja nicht.
Deine Minute für 20 Züge sind ja noch ok (die sind gar nicht mal so schlecht!), bis 42 Züge sind's dann extrem gut alpha-beta-geschnippelt 2^22 Minuten? Sind ja nur 8 Jahre.Ich nehme an, Du willst eine 1 haben. Aber hier ist wohl kein fruchtbarer Boden. Rede sofort mit ihm. Kläre, daß Du selbstverständlich eine 1 kriegst, wenn deine KI besser spielt als er. Und das ist schon größenwahnsinnig. Oder nimm ein anderes Thema. Schau mal, was die Mädchen so nehmen und mach es besser.
-
Das was volkard sagt, aber weniger poetisch. Da er mir zuvor gekommen ist, ein kleiner Tipp: Frag deinen Lehrer, ob du das Spielfeld verkleinern kannst. Das mindert in keinster Weise die Leistung die du für die Entwicklung der KI aufbringen musst, reduziert aber ganz gewaltig die nötige Rechenleistung. Auf dem Standard 7x6 Feld hat man 4531985219092 mögliche Positionen, das ist auch für heutige Computer noch viel zu viel um alles Live zu berechnen, selbst offline muss man fortschrittliche Suchalgorithmen benutzen um da die siegbringenden Züge zu finden. Aber auf einem 5x4 Brett sind es nur noch 3945711 Möglichkeiten, eine Millionen mal weniger und eine Größenordnung die ein heutiger Computer in ein paar Minuten Bruteforcen kann. Mit einer alphabeta-Suche (die für Schulunterricht schon anspruchsvoll genug ist) sollte deine KI das praktisch sofort berechnen können.
-
ToniToni schrieb:
Gibt es Optimierungen, die das Programm noch wesentlich beschleunigen könnten?
Klar. Genau die selben wie beim Schach-Programmieren. Einen oder zwei Züge wirst Du durch die Killer-Heuristik raushauen können. Nee, bei mir war es eher nur einer.
Ich habe z.B. was von Bitboards gehört, aber damit kann ich im Moment nichsts anfangen (bzw. ich verstehe das nicht).
Reine Optimierung für Schach, auf einmal passen alle 64!!! Zugmöglichkeiten in einen 64!!!-bittigen Integer. Das schreit!!! danach, daß man mal damit experimentiert, daß nicht mehr pro Feld die Bits sagen, welche Figuren oder Bauern drauf sind, sondern pro Figur oder Bauer die Bits sagen, wo sie stehen. !!!. Geile Idee. !!. Und die ganze Geschichte weniger schleifen-lastig wird, sondern mehr &-lastig.
Naja, am Ende ist der Gewinn nicht so wild. Aber die Optimierung ist in ihrer Eleganz so total faszinierend, es ist einfach der Hammer. So was absolut überraschendes. Naja, bringt schon was, und ist einfach irgendwie hübsch.
-
Aber wieso wollt ihr das perfektionieren. Wenn das Ding halbwegs vernuenftige Zuege macht und dabei ein bisschen im Voraus ueberlegt und so viel wie moeglich vll. noch in einem anderen Thread rechnet, waehrend der Gegenspieler nachdenkt, kriegt man doch ein halbwegs ordentliches Ergebnis hin.
Die optimale Strategie... Kannste ja auch basteln, denn einfaches Bruteforce ohne Intelligenz geht ja schneller. Dann kannste ihm das zeigen, nur kann er das dann alleine in seinem Kaemmerchen spielen, bis er halt in Rente geht oder darueber hinaus.
-
Ich weiß nicht, ob da ein perfekter Spieler rauskommt, aber ich hatte 4 Gewinnt mit AlphaBeta programmiert, wobei ich eine Suchtiefe von 7 benutzt hatte. Mit entsprechender Bewertungsfunktion ist die KI mit dieser Suchtiefe schon sehr stark. Ich hatte immer verloren, wenn der Rechner das Spiel angefangen hat.
Bzgl Beschleunigen, vielleicht bringt es noch etwas, wenn Du die Suchtiefe schrittweise erhöhst und Du Dir die sogenannte "Diagonale" merkst. Das Wegschneiden uninteressanter Teilbäume über AlphaBeta funktioniert ja besonders gut, wenn man zuerst die besseren Züge probiert und danach die weniger versprechenden Züge. Was ein guter Zug ist, ergibt sich aus einer vorherigen Suche mit geringerer Suchtiefe. Das heißt, den Pfad von Wurzel bis Blatt des Zustandsbaums, der bei Suchtiefe 4 rauskomt, könntest Du Dir merken und diesen für eine höhere Suchtiefe wieder zuerst einschlagen. So kann der Rechner auch unter Zeitdruck spielen. Wenn Du nach und nach die Suchtiefe erhöhst und Dir immer die bisher beste Lösung merkst, kann man den Rechner auch zum Zug zwingen (nimmt dann einfach die bisher beste Lösung). Ich glaube, so machen das die meisten Schachprogramme auch.
-
volkard schrieb:
Oder nimm ein anderes Thema. Schau mal, was die Mädchen so nehmen und mach es besser.
Ach, schön! Danke, das war dann doch ein guter Start in den Tag!
-
Da ich mich auch mal mit dem Thema beschäftigt habe (allerdings als Spieler) empfehle ich dir die Masterarbeit von Victor Allis:
"A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins"
http://www.connectfour.net/Files/connect4.pdf
(Source code gibts an diversen Stellen im Netz.)In seiner Arbeit bekommst du die komplette Theorie, um eine perfekte (sprich: unschlagbare) KI für 4 gewinnt zu schreiben*. Brute-force/Alpha-Beta Algorithmen sind unnötig.
* Dies gilt natürlich nur sofern die KI den ersten Zug erhält. Der Spieler mit dem ersten Zug gewinnt bei 4-gewinnt immer sofern er keinen Fehler macht.
-
antialias schrieb:
Da ich mich auch mal mit dem Thema beschäftigt habe (allerdings als Spieler) empfehle ich dir die Masterarbeit von Victor Allis:
"A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins"
http://www.connectfour.net/Files/connect4.pdf
(Source code gibts an diversen Stellen im Netz.)In seiner Arbeit bekommst du die komplette Theorie, um eine perfekte (sprich: unschlagbare) KI für 4 gewinnt zu schreiben*. Brute-force/Alpha-Beta Algorithmen sind unnötig.
* Dies gilt natürlich nur sofern die KI den ersten Zug erhält. Der Spieler mit dem ersten Zug gewinnt bei 4-gewinnt immer sofern er keinen Fehler macht.
Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?
Seite 81:The evaluation function was not powerful enough to determine the game-theoretical value of
the standard 7 x 6 board. After some search techniques were implemented, it became clear, that the
search tree would become very large. Still it was possible, using 2 Sun-4 computers of the Vrije
Universiteit of Amsterdam, to show that the initial position can be won by white.
Mostly due to hardware problems and wrong choices of variations by the author more than 1000
hours of CPU-time were used. The four winning variations described in chapter 13, together took
about 350 hours of CPU-time
-
Gut, ich bedanke mich schon mal für die vielen Antworten.
Also kann ich davon ausgehen, dass eine perfekte KI so ohne weiteres nicht möglich ist...
Vllt. rede ich dann doch mal mit meinem Lehrer und frag ihn, was er dazu sagt, wenn die KI dann doch nicht perfekt spielt (gegen die KI gewinnen konnten bis jetzt nur andere Programme).
Aber das mit dem "Sockenschuss" lass ich glaub ich weg.....
Und zu dem was die Mädchen in unserem Kurs machen....
Naja, was soll man da sagen. Ist doch klar, dass die Erwartungen da ein bisschen geringer sind. Ansonsten wären die beiden auch schon wech...Von den Killermoves habe ich auch schon etwas gelesen. Bei Vier Gewinnt scheinen diese aber nicht besonders hilfreich zu sein. Deswegen habe ich mich nicht weiter damit beschäftigt.
SeppJ schrieb:
ein kleiner Tipp: Frag deinen Lehrer, ob du das Spielfeld verkleinern kannst.
Das wäre auch eine Möglichkeit, würde aber natürlich einige grundlegende Änderungen bedeuten. Dann hätte ich vllt. sogar eine perfekte KI...
Eisflamme schrieb:
Hi,
AlphaBeta-Suche kenne ich nicht. Eine Hashmap bei so einem kleinen Spielfeld erscheint mir ziemlich uebertrieben.
Naja, es werden ja vielmehr Stellungen mit ihren Bewertungen in der Hash-Tabelle abgelegt. Auf die kann man zugreifen, wenn man zu einem anderem Zeitpunkt wieder die gleiche Stellung erreicht. Daher sind die schon sinnvoll
antialias schrieb:
Da ich mich auch mal mit dem Thema beschäftigt habe (allerdings als Spieler) empfehle ich dir die Masterarbeit von Victor Allis:
"A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins"
http://www.connectfour.net/Files/connect4.pdf
(Source code gibts an diversen Stellen im Netz.)Ohh, das scheint aber ziemlich hartes Zeug zu sein. Das lass ich mal lieber...
Aber noch mal was anderes:
Es gibt ja offensichtlich Programme, die perfekt spielen (mustrum, 4inarow...). Wie haben die das denn geschafft?
Mustrum scheint ja eine Datenbank zu verwenden. Vllt. gibt es ja irgendwo im Internet eine, die ich auch verwenden kann. Da muss ich nochmal suchen...
Oder vllt. weiß ja einer von euch wo man die findet....Nochmals Danke für die Antworten...
-
Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?
Kapitel 5-8 beschäftigen sich mit threats und welche davon wie vereitelt werden können (bzw. welche überhaupt keine threats sind und eigentlich völlig ignoriert werden können). Man muss sehr wenig 'suchen' um eine Siegstrategie zu erhalten. Menschliche 4-gewinnt Spieler gehen ja auch nicht durch den Suchraum sondern nutzen dieses Vorwissen (und den Zugzwang) um die Anzahl der zu untersuchenden Variationen zu minimieren.
Kapitel 13 gibt einen Einblick in Anfangszüge/Situationen (von denen es erstaunlich wenige gibt bis es völlig trivial wird durch Zugzwang zu gewinnen)
Es gibt implementationen unter Java die in Sekunden den bestmöglichen Zug liefern.
Ich hab jetzt selbst noch kein 4-gewinnt Programm geschrieben, aber aus der hohlen Hand würde ich das über Threat-analyse und Zugzwang-vorwissen machen. Es ist dafür nicht nötig Züge im Voraus zu berechnen.
-
antialias schrieb:
Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?
Kapitel 5-8 beschäftigen sich mit threats und welche davon wie vereitelt werden können (bzw. welche überhaupt keine threats sind und eigentlich völlig ignoriert werden können). Man muss sehr wenig 'suchen' um eine Siegstrategie zu erhalten. Menschliche 4-gewinnt Spieler gehen ja auch nicht durch den Suchraum sondern nutzen dieses Vorwissen (und den Zugzwang) um die Anzahl der zu untersuchenden Variationen zu minimieren.
Kapitel 13 gibt einen Einblick in Anfangszüge/Situationen (von denen es erstaunlich wenige gibt bis es völlig trivial wird durch Zugzwang zu gewinnen)
Es gibt implementationen unter Java die in Sekunden den bestmöglichen Zug liefern.
Ich hab jetzt selbst noch kein 4-gewinnt Programm geschrieben, aber aus der hohlen Hand würde ich das über Threat-analyse und Zugzwang-vorwissen machen. Es ist dafür nicht nötig Züge im Voraus zu berechnen.
Ich glaube trotzdem nicht, daß man Alpha-Beta-Pruning durch die gute aber nicht vollkommene Bewertungsfunktion komplett los wird.
Selbst als Mensch wirst Du es nicht los. Du schaust Dir doch die Threads an. Und dann guckst Du, wo Du reinwerfen mußt oder nicht reinwerfen darfst. Oder genauer: Du guckst, wo der Stein landen würde und ob das eher gut oder eher schlecht ist. Und wenn zwei gleichwertige Züge möglich sind, schaust Du, was der Gegner drauf machen würde und wie Du antworten würdest.
-
ToniToni schrieb:
Es gibt ja offensichtlich Programme, die perfekt spielen (mustrum, 4inarow...). Wie haben die das denn geschafft?
http://www.ce.unipr.it/~gbe/velena.html
schreibt, daß die Datenbank deswegen so "winzig" (nur 60000 Stellungen) sein kann, weil die Regeln von Allis so stark sind.
-
Auf http://homepages.cwi.nl/~tromp/c4.html unter
Opening Game Tree ("Joseki")
ist eine recht hübsche Eröffnungsbibliothek.
Die würde ich vielleicht noch per Hand reinfummeln.
-
Stimmt..die Joseki-charts hatte ich ganz vergessen. Die sind gut und zeigen auch sehr hübsch welche Spiele 'langweilig' sind und welche interessant.
Du schaust Dir doch die Threads an. Und dann guckst Du, wo Du reinwerfen mußt oder nicht reinwerfen darfst. Oder genauer: Du guckst, wo der Stein landen würde und ob das eher gut oder eher schlecht ist. Und wenn zwei gleichwertige Züge möglich sind, schaust Du, was der Gegner drauf machen würde und wie Du antworten würdest.
Lustigerweise macht man das als Spieler nicht (zumindest nicht so wie im Schach, wo man sich Antworten auf gegnerische Züge überlegt und dann wieder Antworten darauf etc.). Bei 4-Gewinnt hast du als Spieler einfach einige Punkte im Kopf auf die du auf keinen Fall bei der derzeitigen Situation einen Stein schmeissen darfst (Aji). Daraus ergibt sich in den allermeisten Fällen genau einen Zug den du machen darfst (Atari) um weiterhin siegesgewiss zu sein (odr als schwarz genau einen Zug in dem du nicht vorzeitig verlierst).
Kurz mal den Gedankengang den ein halbwegs fähiger Spieler durchmacht*: Dein Threat muss immer unterhalb des des Gegners sein (für Weiß in 'ungeraden' Positionen für Schwarz in 'geraden' Positionen). Threats auf den anderen Positionen aufzubauen ist für die Katz. Da du in jeder Situation sowieso nur (höchstens) 7 mögliche Züge hast beschränkt das deine Auswahl. Threats weiter oben zu bauen wenn es noch Möglichkeiten gibt für den Gegner gleichzeitig einen tieferen Threat aufzubauen ist ebenfalls sinnlos. Insofern fällt das ganze 'Fallen stellen' - wie beim Schach - weg. Sprich: du musst nie ein ganzes Spiel im Kopf durchspielen sondrn allerhöchstens bis zum Auffüllen deiner nächstmöglichen Threat-Ebene. Unbeteiligte Kolumnen können völlig vernachlässigt werden da sie höchstens tit-for-tat von beiden Spielern aufgefüllt werden um das unausweichliche zu verzögern.
Die allermeisten Spiele unter fähigen Kontrahenten laufen auf 'auffüllen' hinaus (abwechselndes Werfen in eine unbeteiligten Kolumne bis diese voll ist um das Setzen in eine der oben genannten 'verbotenen' Positionen zu vermeiden). Durch Zwang zu gewinnen (also wenn es egal ist was der Kontrahent unter mehreren Möglichkeiten wirft) ist absolut unüblich und kommt nur vor wenn einer einen totalen Schnitzer macht. Nur wenn man so einen Zwang aufbauen kann ist es überhaupt nützlich Threats auf geraden (weiß) oder ungeraden (schwarz) Positionen aufzubauen. Aber wenn du das kannst dann hast du den anderen Spieler sowieso so derart im Griff dass du Kreise um ihn spielen kannst.
In einem Spiel mit guten Kontrahenten zieht also weiß immer so, dass sein Threat (im langwierigsten Fall auf Reihe 6) am leben bleibt und schwarz muss dauernd so ziehen, dass weiß keinen Threat auf einer früheren Reihe aufbauen kann. Nur wenn einer einen groben (und meist leicht ersichtlichen) Fehler macht kann sich das ändern. Züge im voraus werden dazu nicht mental berechnet. Dass ist eher Pattern-matching.
Es ist sogar meist nach wenigen Zügen klar in welche Position der Siegstein gespielt werden wird (ich kann bei vielen Spielen mit Neulingen nach 4-5 Zügen genau sagen wo ich gewinnen werden - selbst wenn der ab dann perfekt weiterspielt). Selbst bei Profis ist das meist recht früh klar. Ab da braucht man nicht weiter strategisch zu spielen. Das Auffüllen übernimmt den Rest (sprich: hier muss ein Programm auch nicht mehr irgend welche Entscheidungsbäume durchlaufen)
*Ich würd mich jetzt mal frecherweise als 'halbwegs guter Spieler' bezeichnen - allerdings nicht als perfekt.
-
Ein normales Backtracking mit einer einfachen Bewertungsfunktion reicht aus für eine nahezu perfekte KI.
Ich habe so etwas mal vor 17 Jahren gemacht und die Rechenzeiten waren kein Problem. Eine Rechentiefe von 5 Zügen war ausreichend. Höhere Rechentiefen brachten keine besseren Ergebnisse, sondern nur höhere Rechenzeiten.
-
Gut. OP stellt seine CPU fertig, dann packst Du deine vom Dachboden und einer von euch postet dann den Termin, wo wir uns das alles Life über irgendein public desktop sharing anschauen können.
*holt das Popcorn raus*
-
MichelRT schrieb:
Ein normales Backtracking mit einer einfachen Bewertungsfunktion reicht aus für eine nahezu perfekte KI.
Ich habe so etwas mal vor 17 Jahren gemacht und die Rechenzeiten waren kein Problem. Eine Rechentiefe von 5 Zügen war ausreichend. Höhere Rechentiefen brachten keine besseren Ergebnisse, sondern nur höhere Rechenzeiten.Um einen durchschnittlichen menschlichen Spieler wie mich zu schlagen reichen mit Sicherheit 5 oder 6 Züge Rechentiefe. Aber ein "halbwegs guter Spieler" wie antialias würde so ein Programm in der Luft zerreißen, es sei denn das Programm hätte sonst noch irgendwelche intelligenten Algorithmen drin....
Naja, ich habe auf der Seite mustrum.de eine Eröffnungsdatenbank mit bis zu 12 Steinen gefunden und heruntergeladen. Jetzt muss ich erstmal versuchen die zu komprimieren und dann mein Programm zu erweitern. Wenn ich das noch schaffe, dann würde das Programm zumindest für die ersten 12 Züge perfekt spielen. Ich hoffe mal, dass das Durchsuchen der Datenbank nicht zu lange dauert, weil da sind schon einige Stellungen drin.
Vllt. traue ich mich dann noch an die BitBoards dran, aber das wird vermutilich extrem aufwendig...
-
Das kommt sicherlich auch auf die Bewertungsfunktion an. Wie gesagt, meine alte Vier-Gewinnt-KI war (glaub'ich) relativ stark mit Suchtiefe 7. Die Bewertungsfunktion war simpel aber effektiv. Für jeden eigenen Stein und für jede Orientierung (waagerecht, senkrecht, diagonal, ...), gab es einen Punkt, falls der Stein in dieser Orientierung noch zu einem 4er ausbaufähig war.
Beispiel:
[ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][X][ ][ ][ ]X: 4 Punkte
Beispiel 2:
[ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][O][ ][ ][ ] [ ][ ][ ][X][ ][ ][ ]X: 3 Punkte
O: 4 PunkteBeispiel 3:
[ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][O][ ][ ][ ] [ ][ ][X][X][ ][ ][ ]X: 3+2 Punkte (3 vom ersten und 2 vom zweiten
O: 4 PunkteBeispiel 4:
[ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][X][ ][ ][ ] [ ][ ][ ][O][ ][ ][ ] [ ][ ][ ][X][ ][ ][ ]X: 3+4 Punkte (3 vom ersten und 4 vom zweiten
O: 3 Punkteu.s.w.
Der Wert, den die Bewertungsfunktion zurück gibt, ist die Differenz der Punktzahlen oder INT_MAX bzw INT_MIN falls eine der beiden Parteien gewonnen hat.Zumindest habe ich nie gewonnen, wenn die KI angefangen hat. Dabei habe ich u.a. auch "gemogelt" (mich von anderen 4-Gewinnt-KIs beraten lassen).
kk
