Endlosschleife oder zu grosser Baum?

Kvida_1409af · 8. November 2019 um 09:41

Hallo!

Eigentlich geht’s um C++, aber das Problem ist wohl allgemein…
Es geht um folgendes: Ich soll einen Baum aufbauen, der alle Spielsituationen des Spiels „Drei gewinnt“ (auf einem 4x4-Feld) beinhaltet, also 4 Nachfolger (1 pro Slot) für jeden Knoten.

Wenn ich das Programm nun ausführe (kompiliert mit g++ 3.4 oder so unter SuSE Linux 9.1), stürzt es auch nicht ab, sondern belegt einfach immer mehr Speicher, bis es von Linux „abgeschossen“ (killed) wird.

Rein theoretisch könnte der Baum ja 4 hoch 16 Blätter haben… das wären etwa 4 Milliarden und ein paar Zerquetschte.

Habe ich eine Endlosschleife gebaut? Oder ist der Computer nicht leistungsfähig genug? (Athlon 1.53 Ghz, 512 MB RAM)

Ausserdem traue ich den 4 Milliarden nicht, da der Baum ja an manchen Ästen auch schon bei Tiefe 4 endet… also weiss ich nicht, wieviel Knoten das Ganze hat, also fällt es mir auch schwer, was konkretes über die asymptotische Laufzeit zu sagen…

*seufz*

Und angenommen, es ist eine Endlosschleife, wie finde ich denn dann den Fehler… mit g++ kann ich nicht debuggen (ich sage ‚ich kann es nicht‘, nicht ‚es geht nicht‘)? :-/
Ich weiss einfach nicht, ob ich nach dem Fehler suchen, einfach alles neu schreiben, oder es auf einem Supercomputer laufen lassen soll…

Kvida

Peter_TOO · 8. November 2019 um 09:42

Hallo Kvida,

Eigentlich geht’s um C++, aber das Problem ist wohl
allgemein…

Ja,

Es geht um folgendes: Ich soll einen Baum aufbauen, der alle
Spielsituationen des Spiels „Drei gewinnt“ (auf einem
4x4-Feld) beinhaltet, also 4 Nachfolger (1 pro Slot) für jeden
Knoten.

Aha.

Wenn ich das Programm nun ausführe (kompiliert mit g++ 3.4
oder so unter SuSE Linux 9.1), stürzt es auch nicht ab,
sondern belegt einfach immer mehr Speicher, bis es von Linux
„abgeschossen“ (killed) wird.

Ach …

Rein theoretisch könnte der Baum ja 4 hoch 16 Blätter haben…
das wären etwa 4 Milliarden und ein paar Zerquetschte.

= 4’294’967’296

Habe ich eine Endlosschleife gebaut? Oder ist der Computer
nicht leistungsfähig genug? (Athlon 1.53 Ghz, 512 MB RAM)

Tja.

Ausserdem traue ich den 4 Milliarden nicht, da der Baum ja an
manchen Ästen auch schon bei Tiefe 4 endet… also weiss ich
nicht, wieviel Knoten das Ganze hat, also fällt es mir auch
schwer, was konkretes über die asymptotische Laufzeit zu
sagen…

*seufz*

Hmm…

Und angenommen, es ist eine Endlosschleife, wie finde ich denn
dann den Fehler… mit g++ kann ich nicht debuggen (ich sage
‚ich kann es nicht‘, nicht ‚es geht nicht‘)? :-/
Ich weiss einfach nicht, ob ich nach dem Fehler suchen,
einfach alles neu schreiben, oder es auf einem Supercomputer
laufen lassen soll…

Woher soll ICH jetzt wissen was du für einen Sch… programmiert hast ???

MfG Peter(TOO)

Okinaptz_Uglwf_88cbac · 8. November 2019 um 09:42

Hallo.

Eigentlich geht’s um C++, aber das Problem ist wohl
allgemein…

Dann stell doch mal die Source hier ins Forum, sonst raten wir uns den Wolf - es kann an einer unbeabsichtigten Rekursion liegen, an mangelndem Arbeitsspeicher oder beidem, oder an einer Endlosschleife oder …?

Gruß kw

Kvida_1409af · 8. November 2019 um 09:42

Dann stell doch mal die Source hier ins Forum, sonst raten wir
uns den Wolf - es kann an einer unbeabsichtigten Rekursion
liegen, an mangelndem Arbeitsspeicher oder beidem, oder an
einer Endlosschleife oder …?

Gruß kw

Hallo!

Äh, stimmt natürlich, ich war gestern abend wohl ein bisschen verpeilt (sprich, verzweifelt).
Also hier ist er.
Ich denke der Code ist ausführlich genug kommentiert…

---- CODE ANFANG ----

/\* Drei Gewinnt
 \*
 \* Zuordnungen: 
 \* Mensch/Minzug -1
 \* Unentschieden/Leer 0
 \* Computer/Maxzug 1
 \*
 \* Das Spielfeld ([4][4]) wird mit der unteren linken Ecke auf den
 \* karthesischen Koordinatenursprung gelegt, so dass das unterste 
 \* Feld im ersten Slot [0][0] ist, und Slot 3 voll ist, wenn
 \* in [2][3] keine 0 steht.
 \*
 \* Jeder Knoten kopiert jeweils das Spielfeld seines Vorgängers 
 \* und macht dann seinen eigenen passenden Zug.
 \*
 \*/

/////////////////////////////// INCLUDES //////////////////////////////////////
#include 
using namespace std;

///////////////////////// KLASSE DER BAUMKNOTEN //////////////////////////////
/\* Struktur: 
 \*
 \* int data; // Min/Max seiner Kinder
 \* int who; // Wer diesen Zug gemacht hat
 \* int feld[4][4]; // Das aktuelle Spielfeld
 \* node\* slot[4]; // Die Nachfolger
 \* node\* parent; // Der Vorgaenger
 \*
 \* Methoden:
 \*
 \* init\_node(); // Initialisiere alle Werte mit 0en 
 \* play(int slot, int who); // Macht einen Zug fuer who in slot
 \* is\_game\_over(int a); // Kontrolliert, ob a gewonnen hat
 \* is\_slot\_full(int slot); // Kontrolliert, ob slot voll ist
 \* is\_feld\_full(); // Kontrolliert, ob Spielfeld voll ist
 \*/

struct node
{
 // Werte des Knotens
 int data;
 int who;
 int feld[4][4];
 node\* slot[4];

 // Den Knoten initialisieren
 int init\_node()
 {
 for(int i=0 ; iwho == 1) // Falls vorhin der eine dran war, 
 whonow = -1; // dann jetzt der andere, 
 else 
 whonow = 1; // andernfalls doch der eine.

 node\* uk[4]; // Alle neuen Unterknoten (in einem Array zum Schleifen)


 for(int i=0 ; iinit\_node();

 uk[i]-\>who = whonow; // who in den Unterknoten abspeichern

 k-\>slot[i] = uk[i]; // Slotpointer von k auf die neuen Uk umsetzen

 if(k-\>is\_game\_over(k-\>who)) // Falls jemand in k gewonnen hat 
 {
 uk[i] = NULL; // dann hat k keine Unterknoten!
 continue;
 }

 if(k-\>is\_slot\_full(i)) // Falls der aktuelle Slot schon in k voll ist
 {
 uk[i] = NULL; // dann gibts an der Stelle auch keinen Uk!
 continue;
 }

 for (int m=0; mfeld[m][n] = k-\>feld[m][n];

 uk[i]-\>play(i, k-\>who); // den naechsten Zug machen
 }

 // Wenn dann alle Unterknoten da sind,
 for(int j=0 ; jslot[i]) // Falls kein Nachfolger da ist
 continue; // mach mit dem naechsten weiter

 if (k-\>who == 1) // Computer -\> Maxzug
 {
 // k-\>data = -1;
 if (k-\>data slot[i]-\>data)
 k-\>data = k-\>slot[i]-\>data;
 }
 else // Mensch -\> Minzug
 {
 // k-\>data = 1;
 if (k-\>data \> k-\>slot[i]-\>data)
 k-\>data = k-\>slot[i]-\>data;
 }
 }

 for(int j=0 ; jslot[j]);

 return 0;
}

///////////////////////////////// MAIN ////////////////////////////////////////

int main()
{
 //// Den Baum aufbauen ////

 cout who = -1; // Der menschliche Spieler macht den ersten Zug
 
 for(int a=0 ; afeld[a][b] = 0;


 cout data) // Solange root noch unbeschrieben ist,
 label\_tree(root); // weiter aufrufen
 
 cout

Semjon_Michailowitsch_580bb3 · 8. November 2019 um 09:42

Hi,

Ergänzend zu den anderen Antworten folgendes!

Es geht um folgendes: Ich soll einen Baum aufbauen, der alle
Spielsituationen des Spiels „Drei gewinnt“ (auf einem
4x4-Feld) beinhaltet, also 4 Nachfolger (1 pro Slot) für jeden
Knoten.

Programmiere ein „3 gewinnt“ auf einem 3x3-Feld.
Das ist überschaubar.
Was ist mit den Zügen des Gegners? Werden die zunächst „ignoriert“
ein „new“ für neue Knoten dauert ziemlich lange. Vermeide es,
indem Du allen Speicher für Knoten vorher in einem Array der
Knoten alloziierst.
beschreibe „Pseudocodeartig“ deine Lösung, die Du verwendest.
Oder Poste den wesentlichen Teil des Quelltextes. Sonst
wird das hier nix

Grüße

CMБ

Kvida_1409af · 8. November 2019 um 09:42

Hallo Semjon!

Programmiere ein „3 gewinnt“ auf einem 3x3-Feld.
Das ist überschaubar.

Warum überschaubarer als ein 4x4-Feld? Schliesslich hat der Baum dann immer noch Tiefe 9, jeweils drei Nachfolger… aufzeichnen ist da nicht… ich hab mir aber den Baum für ein „2 gewinnt, aber nicht diagonal“ auf einem 2x2-Feld aufgemalt, das war sehr übersichtlich
Naja, das Resultat habe ich halt auf den grossen Baum angewandt.

Was ist mit den Zügen des Gegners? Werden die zunächst
„ignoriert“

Nein, es werden ja alle möglichen Spielsituationen in den Baum geschrieben. Das heisst, von der Wurzel zur ersten „Knotenebene“ macht der Mensch seine 4 mögliche Züge, von dieser zur zweiten „Knotenebene“ werden alle möglichen Züge des Gegners (wieder 4) einkodiert, und so weiter, bis in einem Knoten eine Gewinnsituation auftritt oder der Slot voll ist und in dieser Richtung keine passenden Züge mehr gemacht werden können.

ein „new“ für neue Knoten dauert ziemlich lange. Vermeide
es, indem Du allen Speicher für Knoten vorher in einem Array der
Knoten alloziierst.

Und wie gross muss dieses Array dann etwa sein? Ich weiss nämlich nicht, wie ich die Grösse des Baumes abschätzen soll…

beschreibe „Pseudocodeartig“ deine Lösung, die Du
verwendest.
Oder Poste den wesentlichen Teil des Quelltextes. Sonst
wird das hier nix

Ich hab ihn grad gepostet, als Antwort auf die zweite Antwort meines Postings.

Kvida

Semjon_Michailowitsch_580bb3 · 8. November 2019 um 09:42

Hi,

beschreibe „Pseudocodeartig“ deine Lösung, die Du
verwendest.
Oder Poste den wesentlichen Teil des Quelltextes. Sonst
wird das hier nix

Ich hab ihn grad gepostet, als Antwort auf die zweite Antwort
meines Postings.

Frage nach dem ersten Draufschauen; wozu in aller Welt
hat jeder Node deines Baumes *nochmal* ein
komplettes Spielfeld 4x4 als Membervariable.

Das klappt nicht (Oder ich habs nicht verstanden).

Grüße

CMБ

Kvida_1409af · 8. November 2019 um 09:42

Hallo, vielen Dank für die schnelle Antwort!

Frage nach dem ersten Draufschauen; wozu in aller Welt
hat jeder Node deines Baumes *nochmal* ein
komplettes Spielfeld 4x4 als Membervariable.

Das klappt nicht (Oder ich habs nicht verstanden).

Naja, weil ich nicht weiss, wie es anders gehen soll… wie soll ich denn bei einem beliebigen Knoten im Baum herausfinden, ob da z.B. jemand gewonnen hat?
Das brauch ich ja, weil dieser Knoten ja dann keine Unterbäume mehr hat, und die grow_tree(node* k) Funktion dann aufhören soll.

Also kopiert ein Knoten immer das Spielfeld seines Vorgängers, und macht dann einen Zug in den Slot, dem er selber entspricht… und so decke ich dann alle Fälle ab.

Natürlich hab ich mir überlegt, nur ein einziges externes Spielfeld zu haben, aber ich bin mir gar nicht so sicher, dass da keine Fehler entstehen, wenn durch die Rekursion plötzlich 5 Ebenen hochgesprungen wird und in eine ganz andere Richtung weitergemacht wird… wäre (wenn es denn funktioniert) wesentlich effektiver, aber eigentlich auch unübersichtlicher…

Kvida

Ralph_c4cbba · 8. November 2019 um 09:42

Hallo,
habe ich das Spiel richtig verstanden?
Man hat ein Spielfeld 4x4=16 Felder. Darauf setzen zwei Spieler abwechselnd. Wer zuerst 3 nebeneinander hat, gewinnt?

Wenn das das Spiel ist, dann ist es doch sinnlos, das der Anfangende eine Gewinnstrategie hat. (Setze in ein mittleres Feld,…)

???

Ralph

Kvida_1409af · 8. November 2019 um 09:42

Hallo Ralph!

habe ich das Spiel richtig verstanden?
Man hat ein Spielfeld 4x4=16 Felder. Darauf setzen zwei
Spieler abwechselnd. Wer zuerst 3 nebeneinander hat, gewinnt?

Wenn das das Spiel ist, dann ist es doch sinnlos, das der
Anfangende eine Gewinnstrategie hat. (Setze in ein mittleres
Feld,…)

Ich denk schon, dass du’s richtig verstehst… eben statt „4 gewinnt“ auf einem 7x?-Feld ist es „3 gewinnt“ auf einem 4x4 Feld.

Ich versteh aber nicht ganz was du meinst…?
Mir ist klar, das der Spielverlauf immer eindeutig wird, und manchmal macht der Computer auch recht unsinnige Züge, weil er von einem perfekten Gegenspieler ausgeht… ist es da, was du meinst?
Und deswegen gibt es ja dann auch Spielserien, mit denen man *immer* gewinnt… was bei einem menschlichen Spieler kaum der Fall wäre.

Kvida

Ralph_c4cbba · 8. November 2019 um 09:42

Und deswegen gibt es ja dann auch Spielserien, mit denen man
*immer* gewinnt… was bei einem menschlichen Spieler kaum der
Fall wäre.

Spiel gegen mich, ich gewinn immer gegen dich, wenn ich anfange…

Ich setze auf ein Feld, welches nicht am Rand liegt. Danach setzt du auf ein anderes Feld. Dann setze ich auf ein anderes noch nicht besetztes mittleres Feld, so dass an dessen Enden beide Randfelder frei sind. Jetzt bist du in einer Zwischmühle. Setzt du auf die eine Seite setze ich auf die andere…

Wenn du mir nicht glaubst, dann können wir ja mal ein paar Runden per E-Mail spielen

Ralph

Kvida_1409af · 8. November 2019 um 09:42

Hallo!

Ich setze auf ein Feld, welches nicht am Rand liegt. Danach
setzt du auf ein anderes Feld. Dann setze ich auf ein anderes
noch nicht besetztes mittleres Feld, so dass an dessen Enden
beide Randfelder frei sind. Jetzt bist du in einer
Zwischmühle. Setzt du auf die eine Seite setze ich auf die
andere…

Ehm, du weisst aber, dass die Spielsteine in den Slots quasi „runterfallen“ wie beim echten Spiel?

Ich zeichne mal dein Bsp. auf:

Du X, ich O, Ziffern für die Reihenfolge.
Du fängst an mit X1.

[][][][] [][][][]
[][][][] oder [][][][]
[][][X2][] [][][][]
[][X1][O1][] [O1][X2][X1][]

Also ich seh da keine Zwickmühle, und ich finde auch kein Beispiel…?

Kvida

Lars_12015b · 8. November 2019 um 09:44

Velena ?
Hallo Kvida,

für Vier gewinnt gibt es bereits einen Algorithmus für den „perfekten“ Computer-Spieler. Fängt der Computer an, kannst Du nur verlieren.
Das Prog heisst Velena und gibt’s hier samt Sourcen: http://www.ce.unipr.it/~gbe/velena.html
In einem anderen Brett hier bei W-W-W ging es darum, dass bei 9Live eben dieses Velena eingesetzt würde, damit der Anrufer gar nicht gewinnen kann (Mutmaßung oder Realität ? Immerhin fängt immer der/die Moderator/in an !)

Schau Dir den Code an, vielleicht findest Du dort, wie man’s effizienter machen kann.

Ciao, Lars

Moritz_fe1b4f · 8. November 2019 um 09:44

Hallo,
das Programm ist faszinierend
Aber es basiert nicht auf Tiefensuche wie das Programm des OP, sondern auf Regelwerken (wenn da und dort Steine der Farbe liegen, setze in Reihe x).

Wen die Theorie interessiert:
http://homepages.cwi.nl/~tromp/c4.html
(englisch) ist m.E. sehr gut .

Grüße,
Moritz (der sonst in 4 Gewinnt nicht schlecht ist

Kvida_1409af · 8. November 2019 um 09:44

Hallo!

das Programm ist faszinierend
Aber es basiert nicht auf Tiefensuche wie das Programm des OP,
sondern auf Regelwerken (wenn da und dort Steine der Farbe
liegen, setze in Reihe x).

Ja, das ist auch das Problem… wie auf der Velena-Homepage erklärt wird, kann man 4 Gewinnt nicht als Baum aufbauen, weil man 7,1 * 10^13 Knoten bräuchte… *ähem* Kein Wunder, dass die das lieber mathematisch lösen. Leider besteht meine Aufgabe (jep, Hausaufgabe ) darin, den Baum aufzubauen.

Ok, ich hab leider auch keine gute Abschätzung für die Zahl der Knoten in meiner Version, jedenfalls ist die Obergrenze bei 5,7 * 10^9 Knoten.(= Summe über 4^i für i=0…16)

Kvida

Moritz_fe1b4f · 8. November 2019 um 09:44

Hallo,

Ja, das ist auch das Problem… wie auf der Velena-Homepage
erklärt wird, kann man 4 Gewinnt nicht als Baum aufbauen, weil
man 7,1 * 10^13 Knoten bräuchte… *ähem* Kein Wunder, dass
die das lieber mathematisch lösen. Leider besteht meine
Aufgabe (jep, Hausaufgabe ) darin, den Baum aufzubauen.

Sicher dass das so viele sind? ich hab mir mal ein Programm 'runtergeladen (Mustrum heißt es) das den ganzen Baum aufbaut und damit perfekt spielt. OK, das aufbauen hat auf meiner Kiste (700 MHZ, 256MB RAM) 1.5 Stunden gedauert

Ok, ich hab leider auch keine gute Abschätzung für die Zahl
der Knoten in meiner Version, jedenfalls ist die Obergrenze
bei 5,7 * 10^9 Knoten.(= Summe über 4^i für i=0…16)

Du hast ein 4x4-Feld, ja?
dann hast du am Ende, wenn alle Felder belegt sein sollten, 8 aus 16 Steine einer bestimmten Farbe. Das sind 12870, also _deutlich_ weniger.

Jetzt ist die Frage: mußt du einen Baum/Graph für alle möglichen Spiele oder für alle Möglichen Stellungen aufbauen?

Grüße,
Moritz (der Tic-Tac-Toe gelöst hat - nur nicht als erster:wink:

wortfuchs · 8. November 2019 um 09:45

Ja, das ist auch das Problem… wie auf der Velena-Homepage
erklärt wird, kann man 4 Gewinnt nicht als Baum aufbauen, weil
man 7,1 * 10^13 Knoten bräuchte… *ähem* Kein Wunder, dass
die das lieber mathematisch lösen. Leider besteht meine
Aufgabe (jep, Hausaufgabe ) darin, den Baum aufzubauen.

Wenn der Berg nicht zum Propheten kommt, dann geht der Prophet zum Berg!

Hast du schon einmal daran gedacht, nicht den kompletten Baum zu erstellen sondern nur einen Ausschnitt daraus? Wenn du dir den kompletten Baum vorstellst, gibt es im Programm immer nur einen Pfad von der Wurzel bis zu einem Zweig. Ein Algorithmus ändert den Pfad von Blatt zu Blatt, deine Aufgabe ist es nur den Pfad zu bewerten. Bei einem guten Pfad gewinnst du, bei einem schlechten dein Gegner oder es ist Remis. Dein Speicherbedarf ist so sehr gering. Bei 4x4 Feldern (=16) hat dein Baum also nur max. 16 Knoten…

Gruß Markus

Kvida_1409af · 8. November 2019 um 09:46

Hallo!

Sicher dass das so viele sind? ich hab mir mal ein Programm
'runtergeladen (Mustrum heißt es) das den ganzen Baum aufbaut
und damit perfekt spielt. OK, das aufbauen hat auf meiner
Kiste (700 MHZ, 256MB RAM) 1.5 Stunden gedauert

Ich hab’s von der Seite…

Du hast ein 4x4-Feld, ja?
dann hast du am Ende, wenn alle Felder belegt sein sollten, 8
aus 16 Steine einer bestimmten Farbe. Das sind 12870, also
_deutlich_ weniger.

Jetzt ist die Frage: mußt du einen Baum/Graph für alle
möglichen Spiele oder für alle Möglichen Stellungen aufbauen?

Hm, ich seh natürlich was du meinst… aber angenommen, es ginge auch mit den Spielen (also die weniger aufwendige Variante), wie würdest du dann die Pointer rekursiv setzen, so dass es sie auf die richtigen Knoten zeigen?

Kvida