Vier Gewinnt

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.

volkard

ich kanns nicht runterladen.

volkard schrieb:

ich kanns nicht runterladen.

Dann probiers mal mit dem Hoster:

http://www.speedshare.org/download.php?id=5E2958423

volkard

DerFrosch schrieb:

volkard schrieb:

ich kanns nicht runterladen.

Dann probiers mal mit dem Hoster:
http://www.speedshare.org/download.php?id=5E2958423

der geht prima.

Für Kritiken und Tipps bin ich natürlich auch offen...

volkard

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...

NDEBUG

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.

knivil

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...

knivil

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).

volkard

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...

C++ Forumbot

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.

volkard

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 besterZug

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.

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?

volkard

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.

DerFrosch

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 besterZug

Das 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...