Vier Gewinnt
-
Upss, mein letzter Beitrag war natürlich nix
volkard schrieb:
im spiel
4 4
4 4
4 4
5 5?
5??
fällt mir auf, daß der kollege einen sieg in nur drei halbzügen übersieht.Ja stimmt, den Fehler müsste ich noch ausräumen. Das liegt daran, dass der Computer nur nach einem Sieg sucht, aber nicht darauf achtet, wie schnell er gewinnen könnte. Dadurch braucht er aber nicht ganz so lange für die Berechnung, wie wenn er den schnellsten Sieg sucht. Aber du hast recht, wenn er in 3 anstelle 20 Halbzügen gewinnen könnte, dannn sollte er erstere Variante wählen...
-
DerFrosch schrieb:
Naja, der Quelltext ist noch ein ziemliches Chaos, außerdem kaum kommentiert und ich glaube es macht nicht so viel Sinn 12.000 Zeilen zu posten. Eine Beschreibung der eingesetzten Verfahren ist meines erachtens sinnvoller. Wenn Interesse besteht, dann könnte ich mich da mal dranmachen...
Mußt den Code ja nicht hier posten. Aber tue ihn bei dem Download einfach mit bei. Ich würde gerne mal sehen warum man 12.000 LOCs für 4 gewinnt braucht.
Deep Blue^^
-
NDEBUG schrieb:
DerFrosch schrieb:
Naja, der Quelltext ist noch ein ziemliches Chaos, außerdem kaum kommentiert und ich glaube es macht nicht so viel Sinn 12.000 Zeilen zu posten. Eine Beschreibung der eingesetzten Verfahren ist meines erachtens sinnvoller. Wenn Interesse besteht, dann könnte ich mich da mal dranmachen...
Mußt den Code ja nicht hier posten. Aber tue ihn bei dem Download einfach mit bei. Ich würde gerne mal sehen warum man 12.000 LOCs für 4 gewinnt braucht.
Deep Blue^^ich muss für die schule gerade ein viergewinnt Programm schreiben.
ich hab aber keine Ahnung wie ich damit anfangen soll.
kannst du deinen quelltext mal hochladen, vllt. kann ich ja damit was anfangen.
-
12.000 Zeilen. Vielelicht kannst du ja etwas zusammenfassen, modularisieren etc. Mir scheint das arg viel fuer 4Gewinnt. Ok ich weiss auch nicht wie du Spielstrategie implementierst hast ... aber es ist trotzdem viel.
-
knivil schrieb:
12.000 Zeilen. Vielelicht kannst du ja etwas zusammenfassen, modularisieren etc. Mir scheint das arg viel fuer 4Gewinnt. Ok ich weiss auch nicht wie du Spielstrategie implementierst hast ... aber es ist trotzdem viel.
Naja, der Code ist halt ziemlich auf Speed getrimmt, da muss man halt viele Schleifen einsparen, bei denen oft unnötige Berechnungen stattfinden. Ein Großteil des Codes ist sowieso auf 6 Funktionen (wichtig für die Zugsortierung in höheren Ebenen des Spielbaums) aufgeteilt, den ich sowieso nicht selbst geschrieben habe, sondern mit einem selbst geschrieben Programm erzeugt habe.
Naja, ich werd mal den Quelltext ein bisschen in Ordnung bringen und kommentieren, dann lad ich das ganze mal hoch, vllt. noch diese Woche. Aber dann bitte nicht wie die Wölfe über mich herfallen, ich bin halt auch noch ein ziemlicher Anfänger in C.
-
hm, ich hab mal ein paar partien gegen dein Programm gespielt und alle verloren.
dannach habe ich das mal gegen mustrum spielen lassen und da hat es auch alle spiele gewonnen,
der scheint ja schon ziemlich perfekt zu sein, aber manchmal erkennt er siege in wenigen zügen nicht, obwohl er trotzdem am ende gewinnt.
vor allen dingen is dein teil ja tausendmal schneller als mustrum...aber ich glaub ich mach noch nen paar partien um zu sehen, ob der wirklich so perfekt spielt...
-
Naja, 4 Gewinnt ist komplett geloest. Gab auch mal ne Anleitung fuer perfektes Spielen im Internet. Links sind bei Wikipedia zu finden. Mustrum sollte eigentlich auch perfekt spielen, kommt halt drauf an, wer beginnt (glaube).
-
DerFrosch schrieb:
Ja stimmt, den Fehler müsste ich noch ausräumen. Das liegt daran, dass der Computer nur nach einem Sieg sucht, aber nicht darauf achtet, wie schnell er gewinnen könnte. Dadurch braucht er aber nicht ganz so lange für die Berechnung, wie wenn er den schnellsten Sieg sucht. Aber du hast recht, wenn er in 3 anstelle 20 Halbzügen gewinnen könnte, dannn sollte er erstere Variante wählen...
bisher kann er, sobald ein sieg gefunden ist, den rest abschneiden. und ich vermute mal, dazu muß er pro ebene normalerweise nur zwei oder so probieren.
mit siegentfernungsbewertung müßte er trotzdem weitersuchen, aua.also vielleicht dazu iterative deepening benutzen, vermutlich kaum zusatzkosten, aber er kann den schnellsten sieg nehmen. die vorberechneten tabellen kannste ja leicht nach steinezahl auftrennen und die nicht angucken, die hinterm hotizont sind. klingt aber irgendwie dümmer, als die siegentfernungen immer mitzurechnen.
da bin ich mal gespannt, wie du es lösen wirst.
-
volkard schrieb:
DerFrosch schrieb:
Ja stimmt, den Fehler müsste ich noch ausräumen. Das liegt daran, dass der Computer nur nach einem Sieg sucht, aber nicht darauf achtet, wie schnell er gewinnen könnte. Dadurch braucht er aber nicht ganz so lange für die Berechnung, wie wenn er den schnellsten Sieg sucht. Aber du hast recht, wenn er in 3 anstelle 20 Halbzügen gewinnen könnte, dannn sollte er erstere Variante wählen...
bisher kann er, sobald ein sieg gefunden ist, den rest abschneiden. und ich vermute mal, dazu muß er pro ebene normalerweise nur zwei oder so probieren.
mit siegentfernungsbewertung müßte er trotzdem weitersuchen, aua.also vielleicht dazu iterative deepening benutzen, vermutlich kaum zusatzkosten, aber er kann den schnellsten sieg nehmen. die vorberechneten tabellen kannste ja leicht nach steinezahl auftrennen und die nicht angucken, die hinterm hotizont sind. klingt aber irgendwie dümmer, als die siegentfernungen immer mitzurechnen.
da bin ich mal gespannt, wie du es lösen wirst.
Hm, ich habe Iterative Deepening schon ausprobiert. Du hast natürlich recht, dass er dann schnelle Siege bereits nach wenigen Iterationen findet, ABER: ich habe noch keine Möglichkeit gefunden, dass iterativ deepening im Normalfall schneller läuft, also wenn der Spielbaum fast bis zum Ende berechnet wird. Im Gegenteil: Es ist dauert mehr als doppelt so lange. Natürlich habe ich meine Hashtable zur Zugsortierung genutzt, um die besten Züge von vorherigen Iterationen zu nutzen, aber letztendlich ist iterativ deepening langsamer, wie eine direkte komplette Berechnung des Spielbaums.
volkard schrieb:
bisher kann er, sobald ein sieg gefunden ist, den rest abschneiden. und ich vermute mal, dazu muß er pro ebene normalerweise nur zwei oder so probieren.
mit siegentfernungsbewertung müßte er trotzdem weitersuchen, aua.Ganz genau, da hast du recht, er würde zwar den schnellsten Sieg überhaupt finden, aber dieser könnte ja trotzdem in 20 Halbzügen Entfernung liegen. Und das macht den Alpha-Beta-Algortihmus unnötig langsam, da viel mehr Knoten durchsucht werden müssen.
Ich habe mir da etwas anderes überlegt, ist zwar nicht optimal, aber einigermaßen zu gebrauchen:
Ich tue einfach vor der richtigen Berechnung einen Spielbaum bis zur Tiefe 10(dauert nur einen Bruchteil einer Sekunde) aufbauen und dann prüfen ob 1000(der Wert für einen sicheren Gewinn) zurückgegeben wird. Ist dies der Fall, dann kann ich mir die komplette Berechnung ersparen...
-
Dieser Thread wurde von Moderator/in rüdiger aus dem Forum ANSI C in das Forum Projekte verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
DerFrosch schrieb:
Ich tue einfach vor der richtigen Berechnung einen Spielbaum bis zur Tiefe 10(dauert nur einen Bruchteil einer Sekunde) aufbauen und dann prüfen ob 1000(der Wert für einen sicheren Gewinn) zurückgegeben wird. Ist dies der Fall, dann kann ich mir die komplette Berechnung ersparen...
da fällt mir ein:
vereinfachter ist-zustand:
du initialisiertst die maxsuchtiefe mit 42 und läßt ihn im ersten zug bis 42 suchen. und machst maxsuchtiefe-=2, damit du im nächsten zug nur bis 40 musst.im jedem weiteren zug suchst du jeweils bis maxsuchtiefe und machst maxsuchtiefe-=2, damit du im nächsten zug wieder 2 weniger tief mußt.
meine idee:
im jedem weiteren zug suchst du jeweils
besterzug=-1
while bis maxsuchtiefe ein sieg gefunden wird,
{
besterzug=gefundenerSiegZug
maxsuchtiefe-=2
}
if besterzug=-1
return zufall;//oder return trivialeAbwehr mit suchtiefe 5
else
return besterZugdas müßte dafür sorgen, daß, solange kein sieg gefunden wird, der ganze laden 1.3-mal so lange braucht. und sobald der compi auf der siegerstraße ist, geht die post ab. die gesamtüberlegzeit pro spiel dürfte sogar sinken.
und mach bitte eine funktion rein, daß man den letzten zug zurücknehmen kann. dazu recht ja, daß du ein char history[43] mitführst. beim speichern wird das array schnell noch nullterminiert und rausgeschrieben. laden ist einfach den string lesen bis '\0' und jeweils den zug setzten und maxzugtiefe-=1. zurücknehmen kannste machen als '\0' auf den letzten zug schreiben und dann den string laden. dabei vergißt er zwar die bereits herazsgefundene maxzugtiefe, die evtl kleiner als 42-zugnimmer ist, aber wen juckt's?
-
benutzt du minimax oder negamax?
ich hab damals um 1990 mich intensiver mit 4-gewinnt beschäftigt. ich kam zu folgendem verrückten gedanken:
immer, wenn ich eine siegstellung finde, speichere ich sie in einer hashtable-datei mit wert 1000-finaleZugnummer. so sind schnelle siege besser als langsame.
verluststellungen halt mit -1000+finaleZugnummer. und unentschieden mit 0.
dabei benutze ich iterative deepening und beschränke die suchzeit auf ein paar minuten (damals!).ja, mein compi war sogar lernfähig! er hat nie zweimal den selben fehler gemacht. und wenn ich dann lange genug rechner gegen rechner spielen lasse, wird er irgendwann klug. gelegentlich läßt man einen cleaner über die datei laufen, der sich jede stellung anschaut und mit ganz kurzer suchtiefe schaut, ob die gespeicherten folgestellungen bei optimalem computerspiel überhaupt gezogen werden können und gegebenenfalls löscht.
man könnte das erweitern zu mehreren rechnern, die lernen und dazu einem prog, das die datenbanken vereinigt (englisch to merge trifft vielleicht besser). also meine idletime (ca 3h pro tag @ 2GHz) kannste schonmal haben, falls du den gedanken weiterführen magst.
aber meiner hat nur suchtiege 7 oder so geschafft. damals war pro hashlookup ein festplattenzugriff nötig. und er wurde ums verrecken nicht klüger. die einfachste zugumstellung hat ihn wieder total blind gemacht.
die größe der entstehenden datei hatte ich auf 40MB abgeschätzt. utopisch, weil die gesamte festplatte nur 40MB hatte und der rechner mir gar nicht gehörte.
-
Aufgrund der Tatsache, dass der Thread verschoben wurde, musste ich mich registrieren um überhaupt noch etwas bearbeiten zu können. Nicht besonders optimal. Naja....
volkard schrieb:
da fällt mir ein:
vereinfachter ist-zustand:
du initialisiertst die maxsuchtiefe mit 42 und läßt ihn im ersten zug bis 42 suchen. und machst maxsuchtiefe-=2, damit du im nächsten zug nur bis 40 musst.im jedem weiteren zug suchst du jeweils bis maxsuchtiefe und machst maxsuchtiefe-=2, damit du im nächsten zug wieder 2 weniger tief mußt.
meine idee:
im jedem weiteren zug suchst du jeweils
besterzug=-1
while bis maxsuchtiefe ein sieg gefunden wird,
{
besterzug=gefundenerSiegZug
maxsuchtiefe-=2
}
if besterzug=-1
return zufall;//oder return trivialeAbwehr mit suchtiefe 5
else
return besterZugDas habe ich ehrlich gesagt nicht verstanden, könntest du das vllt. nochmal ein wenig anders formulieren, für Leute die nicht unbedingt zum Kreis der Intellektuellen gehören...
Die Suchtiefe verringert sich doch sowieso nach jedem Zug um 2... Aber vermutlich habe ich das ganz falsch verstanden...volkard schrieb:
das müßte dafür sorgen, daß, solange kein sieg gefunden wird, der ganze laden 1.3-mal so lange braucht. und sobald der compi auf der siegerstraße ist, geht die post ab. die gesamtüberlegzeit pro spiel dürfte sogar sinken.
Naja, wenn der Computer Anziehender ist, dann ist sowieso nur der 9te Halbzug zeitlich wichtig. Vor dem 9ten Zug kann ich auf das Wissen der Eröffnungsdatenbank zurückgreifen(Eine Datenbank mit allen Stellungen die sich aus 8 Steinen ergeben von John Tromp. Ich habe jetzt auch eine Datenbank mit allen Stellungen mit 10 Steinen berechnet, die ich jedoch noch nicht verwenden möchte) und nach dem 9ten Halbzug ist das Spiel ja schon einmal komplett durchgerechnet worden und man kann auf die Ergebnisse der Hash-Table zurückgreifen... Aber das habe ich wahrscheinlich auch komplett falsch verstanden...
volkard schrieb:
und mach bitte eine funktion rein, daß man den letzten zug zurücknehmen kann. dazu recht ja, daß du ein char history[43] mitführst. beim speichern wird das array schnell noch nullterminiert und rausgeschrieben. laden ist einfach den string lesen bis '\0' und jeweils den zug setzten und maxzugtiefe-=1. zurücknehmen kannste machen als '\0' auf den letzten zug schreiben und dann den string laden. dabei vergißt er zwar die bereits herazsgefundene maxzugtiefe, die evtl kleiner als 42-zugnimmer ist, aber wen juckt's?
Ja, das könnte ich machen, wenn sich die Zeit bietet...
-
volkard schrieb:
benutzt du minimax oder negamax?
Ich benutze den MiniMax-Algorithmus mit Beschneidung des Suchbaums durch das Alpha-Beta-Verfahren, also nicht ganz der NegaMax...
volkard schrieb:
ich hab damals um 1990 mich intensiver mit 4-gewinnt beschäftigt. ich kam zu folgendem verrückten gedanken:
immer, wenn ich eine siegstellung finde, speichere ich sie in einer hashtable-datei mit wert 1000-finaleZugnummer. so sind schnelle siege besser als langsame.
verluststellungen halt mit -1000+finaleZugnummer. und unentschieden mit 0.
dabei benutze ich iterative deepening und beschränke die suchzeit auf ein paar minuten (damals!).Das hört sich sehr interessant an. Ich habe zwar auch schon eine Datenbank mit allen legalen Stellungen mit 10 und 12 Steinen berechnet. Die Datenbank mit den 10 Steinen ist ca. 10MB groß(akzeptabel). Aber die Datenbank mit den 12 Steinen ist knapp 90MB groß und auch nur zu 99% vollständig. Und das Problem ist, was mir jetzt durch deinen Post erst richtig klar geworden ist, dass keine Angabe über die Entfernung zum Sieg oder Niederlage einer Stellung eine Aussage gemacht wurde, wodurch der Computer nicht zwischen schnellen Siegen oder Niederlagen unterscheiden kann, was besonders als Nachziehender fatal ist, wenn der Gegner perfekt spielt.
volkard schrieb:
ja, mein compi war sogar lernfähig! er hat nie zweimal den selben fehler gemacht. und wenn ich dann lange genug rechner gegen rechner spielen lasse, wird er irgendwann klug. gelegentlich läßt man einen cleaner über die datei laufen, der sich jede stellung anschaut und mit ganz kurzer suchtiefe schaut, ob die gespeicherten folgestellungen bei optimalem computerspiel überhaupt gezogen werden können und gegebenenfalls löscht.
Das hört sich auch recht interessant an, wobei ich nicht so an die lernfähigkeit eines Vier-Gewinnt Programmes glaube. Als Anziehender macht das Programm bei größter Suchtiefe ohnehin keinen Fehler(gewinnt also). Da könnte die Lernfunktion natürlich dazu verwendet werden um Bugs aus der KI zu entfernen. Dazu müsste dann aber ein komplett anderer Algorithmus verwendet werden, um das Spiel zu analysieren, der dann auch zu 100% Fehlerfrei sein muss. Wenn das Programm nicht bis zum Ende rechnen kann, dann sind solche Lernfunktionen geeignet und da würde es mich natürlich interessieren, wie du diesen Algorithmus implementiert hast.
Und als Nachziehender Lernfunktionen zu verwenden ist auch nicht besonders sinnvoll, da das Programm bei perfekten Spiel des Gegners so oder so verliert. Er kann dem Gegner das Spiel nur besonders schwer machen, um ihn zu Fehlern zu verleiten. Da müssen dann denke ich mal andere Strategien zum Einsatz kommen, die aber möglichweise beim erstellen einer Datenbank hilfreich sein könnten. Ein einfaches Beispiel: Der Computer ist Nachziehender und verliert das Spiel. Wenn er jetzt einen Halbzug macht, bei dem der Gegner im darauffolgenden Halbzug nur eine Möglichkeit für einen Gewinn hat, dann ist so ein Zug natürlich höher einzuschätzen als ein Halbzug, bei dem der Gegner im darauffolgenden Halbzug in jede beliebige Spalte setzen kann und dennoch gewinnt. Oder ein Halbzug, bei dem der Gegner in eine der äußersten Spalten ziehen muss um zu gewinnen ist auch höher einzuschätzen als wenn er in die Mitte ziehen muss.volkard schrieb:
man könnte das erweitern zu mehreren rechnern, die lernen und dazu einem prog, das die datenbanken vereinigt (englisch to merge trifft vielleicht besser). also meine idletime (ca 3h pro tag @ 2GHz) kannste schonmal haben, falls du den gedanken weiterführen magst.
Das wäre schon ziemlich spannend ein Programm zu haben, das perfekt spielt und sich im Grunde alles selber beigebracht hat, aber ich weiß nicht wie das mit der Rechenzeit aussieht, das wird wahrscheinlich zu einem ziemlich üblen Problem werden, da werden selbst 10 Rechner vermutlich nicht ausreichen. Aber vllt. kannst du ja das Gegenteil beweisen.
volkard schrieb:
aber meiner hat nur suchtiege 7 oder so geschafft. damals war pro hashlookup ein festplattenzugriff nötig. und er wurde ums verrecken nicht klüger. die einfachste zugumstellung hat ihn wieder total blind gemacht.
die größe der entstehenden datei hatte ich auf 40MB abgeschätzt. utopisch, weil die gesamte festplatte nur 40MB hatte und der rechner mir gar nicht gehörte.
Naja, der Speicher wird heutzutage nicht mehr so das Problem sein, obwohl eine Datenbank mit 100MB natürlich auch nicht so vorteilhaft sein dürfte.
Aber du hast schon einige sehr gute Anstöße gegeben, die man vllt. weiterverfolgen kann
-
DerFrosch schrieb:
Die Suchtiefe verringert sich doch sowieso nach jedem Zug um 2...
ja, klar.
falls er keinen sieg findet:
ich meinte, wenn er im 10. zug ist, dann ist die maxsuchtiefe=32. ich suche mit suchtiefe 32 znd finde keinen sieg. naja, dann mach ich halt irgendwas.
und ich hab nur die normale rechenzeit benötigt.falls er einen sieg findet:
ich meinte, wenn er im 11. zug ist, dann ist die maxsuchtiefe=32. ich suche mit suchtiefe 32 znd finde einen sieg. juhu. aber ich mache noch nicht den siegzug! ich suche erstmal mit suchtiefe 30. wenn ich da auch einen sieg finde, suche ich mit suchtiefe 28 und so weiter. mal angenommen, ich treibe kann so lange siege finden, bis ich bei sichtiefe 12 bin. bei suchtiefe 10 sehe ich keinen sieg mehr. dann gebe ich den zug aus, der mit suchtiefe 12 zum sieg führte.
und ich habe die doppelte rechenzeit benötigt. also wie bei reinmal iterative deepening. und ich kann mir merken, daß ich im nächsten zug nur bis suchtiefe 10 suchen muss.jetzt macht der user seinen zug.
und dann bin ich wieder dran. aus der letzten berechnung weiß ich noch, daß der sieg nicht weiter als 10 züge entfernt sein kann. also rechne ich blitzschnell bis 10. aber ich bin konsequent und schau auch bei 8 nach, ob's einen schnelleren sieg gibt. und falls es den gibt, schau ich auch bei 6...
das war jetzt man der verlauf, wenn das spiel im 23. zug endet. angangs genausoschnell wie bisher. beim entdecken des sieges einmal ein langsamer zug. ab dann blitzartig.
bei einem spiel, das unentschieden ausgeht, oder das der rechner verliert, sieht es so aus, daß der rechner genausoschnell ist wie bisher.
bei einem spiel, das im 41. zug gewonnen wird, würde der rechner immer zuerst einen sieh finden und dann mit suchtiefe-=2 keinen sieg finden. also mehrazfwand übers ganze spiel. aber nicht ganz so viel mehraufwand wie in jedem zug ein recursive deepening.
-
Achso, jetzt habe ich das alles kapiert...
Das werde ich mal ausprobieren...
-
volkard schrieb:
immer, wenn ich eine siegstellung finde, speichere ich sie in einer hashtable-datei mit wert 1000-finaleZugnummer. so sind schnelle siege besser als langsame.
verluststellungen halt mit -1000+finaleZugnummer. und unentschieden mit 0.
dabei benutze ich iterative deepening und beschränke die suchzeit auf ein paar minuten (damals!).ja, mein compi war sogar lernfähig! er hat nie zweimal den selben fehler gemacht. und wenn ich dann lange genug rechner gegen rechner spielen lasse, wird er irgendwann klug.
Erinnert mich etwas an Reinforcement Learning.
-
DerFrosch schrieb:
und ich glaube es macht nicht so viel Sinn 12.000 Zeilen zu posten.
12.000 Zeilen für ein 4-Gewinnt Spiel???
Ich habe zu meiner Schulzeit eins in Fortran geschrieben, brauchte aber
nur 700 Zeilen!
-
Bei automatisch generierten Source ist das keine Seltenheit. Mich interessiert das Tool mit dem die Umwandlung gemacht wurde und der Source :). Also das ganze Projekt. Ja ich habe Interesse :).