alzaimar hat folgendes geschrieben:

[edit] Und wenn Du dann noch Lust hast, lassen wir uns die Bewertungsfunktion vom Computer optimieren [/edit]

Also das würde mich nun wirklich interessieren, wie man das macht! Aber zunächst: Ich habe der Bewertung eine "Stelle" hinzugefügt, 1 Feld vor der Spieler-Grundlinie mit der Gewichtung 70:

Bringt das etwas, ist etwas falsch daran oder bin ich so auf dem richtigen Weg? Wenn ja, kann ich ja noch überlegen, welche Massnahmen noch sinnvoll wären!

//Edit: So ist das falsch...

Hi,

Wenn ein Stein in der vorletzten (nicht unbedingt der 7.) Reihe ist, dann ist das nicht unbedingt erstrebenswert, denn es kommt drauf an, was da sonst noch in der Gegend ist. Wenn Du solche speziellen 'Muster' in die Stellungsfunktion einbaust, dann musst Du das genau machen.

Eigentlich wird ja nicht die Bewertungsfunktion optimiert, sondern die Koeffizienten. Man lässt einfach den Compute gegeneinander spielen, und zwar mit unterschiedlichen Koeffizienten, und zwar ungefähr so ('evolutionär'):

Sei A der Satz von Koeffizienten.

1. Erstelle eine Kopie (B) von A.
2. Mutiere B, indem Du irgendeinen Koeffizienten veränderst.
3. Lass A gegen B spielen (10x) und dann B gegen A (auch 10x).
4. Wenn B öfter gewonnen hat, als A, dann ist wohl der veränderte Koeffizientensatz besser. Ersetze A mit B und mach bei 1 weiter.
5. Wenn B öfter verloren hat, war B wohl keine gute Idee, mach bei 1 weiter.

Anmerkung zu 2: Die Veränderung sollte nach der Gaußschen Verteilung geschehen. Ich meine, in der Math-Unit ist so eine Random-Funktion.

Man merkt sich aber die letzten 100 Koeffizientensätze. Zwischendurch lässt man den aktuell besten Koeffizientensatz noch gegen eine ältere Version antreten, zur Kontrolle. Es kann nämlich sein, das die 'Evolution' in eine Sackgasse führt (siehe Dinosaurier ).

alzaimar hat folgendes geschrieben:

Wenn ein Stein in der vorletzten (nicht unbedingt der 7.) Reihe ist, dann ist das nicht unbedingt erstrebenswert, denn es kommt drauf an, was da sonst noch in der Gegend ist.

Ich dachte nur, wenn das Feld auf der Grundlinie des Spielers frei ist, und der Computer das erkennt, sollte er diesen Zug ausführen, denn damit gewinnt er das Spiel.

Was die "Evolution" angeht: Das Prinzip verstehe ich, aber wie immer hapert's an der Umsetzung!

Mojn,

Is mir schon klar, was Du willst. Der Computer führt diesen Zug auch so aus, denn er gewinnt ja damit (das ist ja die maximale Punktzahl). Ich weiss jetzt nicht, welche Version du hast, aber mit ist Folgendes aufgefallen: Nehmen wir an, der Computer hat einen Stein in der 7.Reihe und könnte im nächsten Zug gewinnen. Er kann aber auch im übernächsten Zug gewinnen, denn er kann ja zunächst irgend einen blöden Zug machen, und den Gewinnzug erst im nächsten Zug. Für den Minimax-Algorithmus ist das egal, denn beide Züge ergeben eine Gewinnstellung, die mit 100000 Punkten bewertet wird. Um den Computer dazu zu bringen, *sofort* den Gewinnzug auszuführen, muss die Gewinnstellung umso mehr Punkte erhalten, desto 'eher' dieser Zug in der Vorausschau ausgeführt wird. Der Parameter 'Level' wird ja pro Zugtiefe erhöht. Eine mögliche Bewertung bei einer Gewinnstellung wäre also z.B. : 100000 + 100 - Level. Je kleiner Level, desto höher die Bewertung. Wenn Du es umgekehrt machst (100000 + Level), dann wird der Computer dich 'zappeln' lassen, also seinen Gewinnzug zum spätestmöglichen Zeitpunkt ausführen.

Noch ein wichtiger Effekt:
Bei der Vorausschau kommt es aber zu sog. Horizonteffekten: Wenn die maximale Zugtiefe erreicht ist, dann wird ja eine Stellungsbewertung durchgeführt, egal, was der Gegner dann noch ziehen kann. Und wenn dann die Stellung für Spieler A sehr gut ist, aber B im nächsten Zug gewinnen würde, dann sieht das die Stellungsfunktion nicht. Ich denke, deine Erweiterung würde diesen Effekt um 2 Halbzüge 'nach hinten' verschieben. Mit anderen Worten: Wenn Du korrekt prüfst, hast Du die Stellungsfunktion in der Tat verbessert!

Man sollte im Endspiel (also z.B. wenn es mindestens einen Stein gibt, der in der 6. oder 7. Reihe steht) die maximale Zugtiefe erhöhen, damit die Spiele bis zum bitteren Ende analysiert werden. Ich habe hier einen Laptop mit 1.5GHz M, und da können ohne Probleme 1 Mio Stellungen geprüft werden (1-2 Sekunden).

Anfangs sollte das Programm strategisch spielen, um die Spielstellung zu verbessern, später dann jedoch mit mehr 'Schmalz', also höheren 'MaxLevel'.

Mittlerweile finde ich dieses Spiel ziemlich interessant, weil es so obersimpel ist, aber dennoch viele der Probleme eines komplexeren Spiels (a.k.a. Schach) schon aufzeigt (Horizonteffekt, Eröffnung, Endspiel, etc.)

Besser als der Minimax- ist ohnehin der Negascout-Algorithmus, der allerdings eine Vorsortierung der Zugliste voraussetzt, sodaß vermeindlich gute Züge zuerst ausgeführt werden. Damit verringert sich dann die Anzahl der zu prüfenden Stellungen sehr stark (ohne das die Spielstärke leidet). Das bedeutet, das die Zugtiefe erhöht werden kann, ohne die Wartezeit nennenswert zu erhöhen.

Um mit der Evolution voranzukommen, schreibe mal eine Prozedur, die den Computer gegen sich selbst spielen lässt (bis zum Ende) und dann zurückliefert, ob plComputer, plHuman oder gar keiner gewonnen hat.

alzaimar hat folgendes geschrieben:

Noch ein wichtiger Effekt: Bei der Vorausschau kommt es aber zu sog. Horizonteffekten: Wenn die maximale Zugtiefe erreicht ist, dann wird ja eine Stellungsbewertung durchgeführt, egal, was der Gegner dann noch ziehen kann. Und wenn dann die Stellung für Spieler A sehr gut ist, aber B im nächsten Zug gewinnen würde, dann sieht das die Stellungsfunktion nicht. Ich denke, deine Erweiterung würde diesen Effekt um 2 Halbzüge 'nach hinten' verschieben. Mit anderen Worten: Wenn Du korrekt prüfst, hast Du die Stellungsfunktion in der Tat verbessert!

Darum werde ich mich später kümmern; muss erst herausfinden, wie man das genau programmiert, denn bei der Bewertung blicke ich nicht wirklich durch (ok, beim Minimax-Algorithmus auch nicht!)

alzaimar hat folgendes geschrieben:

Man sollte im Endspiel (also z.B. wenn es mindestens einen Stein gibt, der in der 6. oder 7. Reihe steht) die maximale Zugtiefe erhöhen, damit die Spiele bis zum bitteren Ende analysiert werden. Ich habe hier einen Laptop mit 1.5GHz M, und da können ohne Probleme 1 Mio Stellungen geprüft werden (1-2 Sekunden).

Meiner braucht für 3,5 Mio Züge ca. 16 Sekunden, ist ein 1.2 GHz-Rechner...

alzaimar hat folgendes geschrieben:

Anfangs sollte das Programm strategisch spielen, um die Spielstellung zu verbessern, später dann jedoch mit mehr 'Schmalz', also höheren 'MaxLevel'.

Auf Anhieb fällt mir zu "später" nur ein, die Steine zu zählen und ab einer gewissen Anzahl dann den Wert zu erhöhen. Meine Frau sagt jedenfalls, sie könne im höchsten Level (Level 6) fast immer gewinnen. Ich hab's noch nie versucht. Aber da kommen wir dann gleich schon zur Evolution.

alzaimar hat folgendes geschrieben:

Um mit der Evolution voranzukommen, schreibe mal eine Prozedur, die den Computer gegen sich selbst spielen lässt (bis zum Ende) und dann zurückliefert, ob plComputer, plHuman oder gar keiner gewonnen hat.

Ist fertig. Dazu habe ich einfach die Prozedur MakeComputerMove umgeschrieben:

Wenn "rot" gewinnt, setzt ich eine Byte-Variable Winner einfach auf 1, bei Patt auf 0, bei "blau" hat gewonnen auf 2. Geht vielleicht auch besser, aber so läuft das jetzt erst mal.

Ich dachte mir das so: Ich erstelle eine Kopie der Funktion Score und vom Array coeffs (meinetwegen coeffs1) und ändere dort einen oder mehrere Wert(e), aber welche und um wieviel?
"Rot" soll mit der Kopie spielen. Wie ich das jetzt genau hinbekomme - daran arbeite ich noch.

Erst mal zum besseren Verständnis einmal meine Version des Spiels:

galagher hat folgendes geschrieben:

Ich dachte mir das so: Ich erstelle eine Kopie der Funktion Score und vom Array coeffs (meinetwegen coeffs1) und ändere dort einen oder mehrere Wert(e), aber welche und um wieviel? "Rot" soll mit der Kopie spielen. Wie ich das jetzt genau hinbekomme - daran arbeite ich noch.

Das habe ich jetzt, aber was ich ich auch verändere, es gewinnt immer jene Farbe, die den 1. Zug macht. Ich habe es jetzt allerdings so programmiert, dass "Blau" mit der Kopie spielt.

Hi,

Ein Dickes Lob an euch beide für das geile Spiel. Hab es jetzt schon zum 10 mal gespielt ind auf sehr stark gewonnen
Also zur Verbesserung solltet ihr euch unbedingt die Anfangsstellung neu überlegen, weil die KI bei mir immer erst die erste Reihe nach vorne zieht und das lässt sich taktisch ausnutzen.
Bei meinem zweiten Spiel auf sehr stark ist mir auch das Problem aufgefallen, dass der Gegner nicht den schnellsten Sieg wählt, wenn ich ihm innerhalb dieser Züge sowieso nichts anhaben kann,womit ich ihn fast gekriegt hätte, hätte ich noch einen Zug mehr gehabt
So jetzt wird erst mal das nächste lvl ausprobiert

[quote="[user]Ein Dickes Lob an euch beide für das geile Spiel. Hab es jetzt schon zum 10 mal gespielt ind auf sehr stark gewonnen [/quote]
Danke! Aber das "Herz" des Spiels (bewertung, KI usw.) hat alzaimar allein programmiert. Ich hab's ein wenig umgeschrieben, so, wie ich die Oberfläche will. Ist aber noch lange nicht fertig!

@alzaimar: Es spielt jetzt zwar gegen sich selbst, aber es kommt dabei vor, dass es die Meldung "Ich passe" oder "Du musst passen" ausgibt, und zwar immer 1 Zug vor dem Sieg, also auf einem vorletzten gegnerischen Feld, obwohl beide Farben noch ziehen könnten. (??)

galagher hat folgendes geschrieben:

... Meine Frau sagt jedenfalls, sie könne im höchsten Level (Level 6) fast immer gewinnen...

6 Halbzüge in die Tiefe ist aber auch nicht die Welt. Ich fürchte, wir müssen zu drastischeren Mitteln greifen (Zugliste sortieren und Negascout-Algorithmus). Mal sehen was das bringt.

Was die nicht funktionierende Evolution anbelangt, würde ich mal annehmen, das ....
... die Änderungen im Koeffizientenarray nicht drastisch genug sind, um eine positive Änderung des Spielverhaltens herbeizuführen,
... die Stellungsbewertung nicht 'filigran' genug ist
oder schlicht und ergreifend
... die Koeffizienten nicht weiter zu verbessern sind.

Wenn Deine Frau so gut ist, das Programm ständig zu schlagen, dann hat sie bestimmt eine Strategie (außer gutes Nachdenken ). Die kann man analysieren und das in die Bewertungsfunktion einfließen lassen.

Ich habe in den nächsten Tagen leider nicht genug Zeit, dir KI weiter zu verbessern. Eine Kleinigkeit habe ich aber: Das Programm ist 'feige'. Wenn es merkt, das es verliert, sagt es fälschlicherweise:'Ich passe'. Da ist ein kleiner Fehler in der KI, den ich verbessert habe. Die Parameterliste der Routine FindBestMove habe ich etwas verkürzt. Das kleine blinkende Rechteck ist nun besser sichtbar, und ein zweites Spielbrett hab ich noch gebastelt.

Ich poste mal meine Version, die kannst Du bei dir ja einbauen. (Das Menü ist beim 'Computer'-Label, einfach raufklicken)

@Balmung: Die Anfangsaufstellung ist wirklich langweilig: Ich habe beide Reihen jeweils um eins nach vorne gezogen. Die Software ist immer noch blöd und zieht die Reihe nach vorne. Aber so kommt man schneller zur Sache. Man darf nicht vergessen, das die Stellungsbewertung, also das Herz des Programms, noch sehr schlicht ist.

Die Tatsache, das das Programm dich zappeln lässt, liegt daran, das es der KI egal ist (war), wann es gewinnt

Probiere mal die neue Version.

Ach ja: Ich poste keine kompletten EXEN mehr, sondern nur noch Verbesserungen in der KI, schließlich wollte galagher das Spiel, also schreibt und verwaltet er es auch.

Juhu, letzte Stufe gemeistert )

Macht weiter so!

Und warum gewinnt immer die Farbe, die den 1. Zug hatte bei Computer gegen Computer?

galagher hat folgendes geschrieben:

Und warum gewinnt immer die Farbe, die den 1. Zug hatte bei Computer gegen Computer?

Vermutlich, weil es einfach schlecht ist, anzufangen. Lass mal Computer gegen sich selbst spielen, einmal mit Stufe 2 und einmal mit 4, dann siehst Du, das das höhere Level schon etwas besser ist...

Ich experimentiere gerade (ja, ja, kaum Zeit, aber das Drecksteil macht *süchtig* ) mit einer Verbesserung der Stellungsfunktion: Für jede Spalte, die mit mindestens einem Stein belegt ist (und damit ist sie ja unpassierbar) gibts auch noch einen Bonus. Und für zwei nebeneinanderliegende Spalten noch mehr. Umgekehrt bedeutet das, daß die KI es vermeidet, offene Spalten zu erzeugen, durch die man einfach durchmarschieren kann. Klappt ganz gut, aber beim Testen gibt es den Effekt der 'Self fullfilling prophecies', also wenn ich denke, das das Programm gut ist, dann spiele ich unbewusst entsprechend schwach. Deshalb ist es so wichtig, das unparteiische Spieler das Teil testen.

Morgen mehr. Jetzt gehts ins Kooooma.

alzaimar hat folgendes geschrieben:

Vermutlich, weil es einfach schlecht ist, anzufangen. Lass mal Computer gegen sich selbst spielen, einmal mit Stufe 2 und einmal mit 4, dann siehst Du, das das höhere Level schon etwas besser ist...

Aber der Computer fängt doch an! Mit beiden Farben kann ich das "Computer-geben-Computer"-Spiel durchführen; im Moment noch per Buttonklick, später sicher anders. Man klickt, und das Programm fängt an.

Aber zunächst mal vielen Dank, dass du dich so einsetzt!

//Edit: Verstehe schon, was du meinst!

galagher hat folgendes geschrieben:

Und warum gewinnt immer die Farbe, die den 1. Zug hatte bei Computer gegen Computer?

Jetzt ist es genau umgekehrt: Es gewinnt, bei gleicher Spielstärke (Variable Level) für beide Farben, immer die Farbe, die NICHT den 1. Zug machte!

alzaimar hat folgendes geschrieben:

Vermutlich, weil es einfach schlecht ist, anzufangen. Lass mal Computer gegen sich selbst spielen, einmal mit Stufe 2 und einmal mit 4, dann siehst Du, das das höhere Level schon etwas besser ist...

Das klappt jetzt: Rot=2, Blau=4: Blau gewinnt und umgekehrt; wie es zu erwarten ist, gewinnt die Farbe mit dem höheren Level. Wenn aber eine Farbe 1 hat, spielt die andere Farbe gar nicht, sondern gibt immer "Ich passe" aus... Mit allen anderen Werten dürfte es gehen

Ich habe das einfach so gemacht:


Bei der "Evolution" hänge ich auch noch ziemlich ergebnislos rum!

Und noch eine Frage (eine von vielen): Ich möchte prüfen, ob das Feld geradeaus in der Gegner-Grundlinie frei ist und ob das Feld davor von plPlayer besetzt ist. Ich mache das so:

Stimmt das so oder übersehe ich da etwas? Ich kann es ja nicht per Haltepunkt nachprüfen, da das Programm ja ständig diesen "Zustand erzeugt", wenn es rechnet!

Hi

bei der _Score-Funktion musst Du bedenken, das es die Bewertung immer aus Sicht eines beliebigen Spielers geschieht. Es gibt also keine 7. Reihe. Dafür ist das Feld 'iRows' gedacht. In der _Score-Funktion laufe ich mit 'i' die Zeilen durch und entnehme aus iRows die entsprechende Zeile in 'r', sowie die darüberliegende (aus Sicht des Spielers) in r1. Die eigene Grundlinie ist in iRows[aPlayer,0], die Grundlinie des Gegners entsprechend in iRows[aPlayer,7].

Mittlerweile habe ich die KI ein wenig umgestrickt, schau mal rein: Ich zähle noch mit, ob eine Spalte mit keinem eigenen Stein belegt ist und ob zwei nebeneinanderliegende Spalten unbelegt sind. Weiterhin schaue ich nach, ob ein Stein durchmarschieren kann. Das ist aber nicht ganz korrekt, was ich da fabriziert habe, aber jetzt geht mir die Puste aus.

Hier mal eine Version, die den Evolutionsmechanismus rudimentär implementiert: Es verändert wahllos einen der Koeffizienten und spielt 500 mal gegen sich selbst. Wenn der veränderte Koeffizientensatz mehr als 55% der Spiele gewonnen hat, isser wohl besser.

Alle 50 Versuche wird gegen ein ältere Version gespielt, um zu verifizieren, das wirklich eine Verbesserung stattgefunden hat. Alle 500 Versuche wird gegen den Originalsatz gespielt, um sicherzustellen, das das Programm wirklich besser ist. Ich hab keine Ahnung, was passiert, wenn man das die Nacht über laufen lässt, aber kannste ja mal testen.

Ach, ich wollte ja eigentlich keine EXE per posten, aber egal. Die 'Evolution' startest du mit diesem häßlichen kleinen Button oben.

Hallo,

die Evolution oder die KI ist suboptimal

Wenn der erste Koeffizient sehr gross wird, gewinnt diese Version scheinbar immer, oder irgendwas laeuft schief.

Gruss Horst
Edit:

Ich habe die Koeffizienten eingetragen und schon hatte der Komputer ohne Spielzug gewonnen

Muuuuhaaaa!
Alles klar, so ein Hirnriss von mir: Die Bewertung für 'Gewonnen' ist 100.000... Irgendwie klar, wenn ein Stein so viel Wert ist, dann ist die erste Bewertung schon so hoch, das der Computer denkt:"Och, schon gewonnen?"... Na ja...

Hotfix geht so:


Weiterhin sollte man offensichtlich noch die Koeffizienten 'deckeln', also eine einigermaßen sinnvolle Obergrenze wählen....

Das kommt davon, wenn man frickelt

-winscore - 1 ist -1000000001, oder möchtest du -(winscore - 1) bzw (winscore) - 1 * (-1)

das ist ein unterschied

@alzaimar, @Horst_H: Danke für eure Mühen! Hab' leider jetzt keine Zeit, mir die neue Version anzusehen (es gibt abseits vom Computer ja auch noch ein Leben, jaja, Tatsache! ), aber ich werde das schon nachholen!

So, jetzt habe ich mal Alpha-Beta-Pruning eingebaut, das reduziert die Anzahl der zu prüfenden Stellungen drastisch. Mittlerweile kann man mit Level 8-12 spielen (8 am Anfang, 12 gegen Ende). Allerdings ist das noch nicht zuende getestet...

Die Fehler, die Horst_H entdeckt hat, sind hoffentlich behoben.

Testet doch mal.