Vier Gewinnt

[talas]

Hi,

wie wäre es mit Quelltext?
Außerdem bist du anscheinend im falschen
Forum? C++?

MfG Jonas

[DerFrosch]

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

[DerFrosch]

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.

[DerFrosch]

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.

[DerFrosch]

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.

[DerFrosch]

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.

[DerFrosch]

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

[CBeginer]

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.

[DerFrosch]

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.

[Profill]

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.

[DerFrosch]

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?