Vier Gewinnt
-
Hallo Zusammen,
dieser Beitrag richtet sich an alle KI bzw. Vier Gewinnt Interessierte...
Ich habe Heute meine erste halbwegs lauffähige Version von Vier Gewinnt fertiggestellt(In C programmiert). Die einzelnen Sonderfunktionen im Programm sind noch nicht implementiert, dass Menü ist also im Augenblick relativ nutzlos. Natürlich wird diese Version noch ziemlich verbuggt sein. Daher habe ich das Spiel mal auf einen Hoster geladen und jeder, der möchte, kann sich mal mit dem Programm anlegen. Zurzeit ist es für den menschlichen Spieler nur möglich als Nachziehender zu spielen. Das hat den Grund, dass man so Fehler in der KI am leichtesten erkennen kann, da der Computer als Anziehender (theoretisch) gewinnen müsste. Wenn einer einen Fehler in der KI oder sonstige Fehler findet, kann er, muss aber nicht, eine Fehlerbeschreibung hier abgeben.
Achso, es könnte sein, dass es manchmal so aussieht, als ob das Programm hängen würde, wenn der Computer gerade rechnet. Einfach ein bisschen Geduld haben. Wenn ein Zug jedoch länger als zwei Minuten dauert, handelt es sich aber vermutlich um einen Bug. Und falls es Jemanden stört, dass man nach jedem Spiel das Programm beenden und dann neustarten muss, dann müsste ich vllt. den Menüpunkt "Spiel Neu Starten" noch mit der entsprechenden Funktion ausstatten.
Wie gesagt, ich möchte keinen als Versuchskaninchen missbrauchen, aber vllt. interessiert sich doch der ein oder andere dafür und Ihr möchtet kann ich auch eine grobe(oder auch genauere) Funktionsweise des Programms posten, damit andere Programmierer von Vier Gewinnt auf ihre Kosten kommen.
Der DownloadLink:
-
^^wo ist der quelltext? oder sollen wird das selber disassemblieren? hier ist doch'n programmierer-forum.
-
Hi,
wie wäre es mit Quelltext?
Außerdem bist du anscheinend im falschen
Forum? C++?MfG Jonas
-
~fricky schrieb:
^^wo ist der quelltext? oder sollen wird das selber disassemblieren? hier ist doch'n programmierer-forum.
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...
-
talas schrieb:
Außerdem bist du anscheinend im falschen
Forum? C++?MfG Jonas
Der Großteil des Programms ist in C geschrieben, nur für die Oberfläche habe ich C++(Borland C++ Builder) verwendet.
-
ich kanns nicht runterladen.
-
volkard schrieb:
ich kanns nicht runterladen.
Dann probiers mal mit dem Hoster:
-
DerFrosch schrieb:
volkard schrieb:
ich kanns nicht runterladen.
Dann probiers mal mit dem Hoster:
http://www.speedshare.org/download.php?id=5E2958423der geht prima.
-
Für Kritiken und Tipps bin ich natürlich auch offen...
-
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.
-
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.
-
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...