Diese Frage geht besonders an alle Stochastiker da draußen.
Ich habe mich mit der Frage beschäftigt: Wie viele Möglichkeiten gibt es ein XXO-Spiel (auch Tick-Tack-Toe genannt) zuende zu spielen. Dabei sollte auf die Regeln geachtet werden (sobald das erste mal 3 Steine in einer Reihe liegen ist das Spiel vorbei), es darf noch leere Felder geben und es soll alle Möglichkeiten angeben, also nicht die raus lassen, die sich durch Spiegelungen o.ä. wiederholen lassen.
Ich habe es mehrfach versucht mit verschiedenen Ansätzen, aber habe jedes mal verschiedene Ergebnisse herausbekommen (die werde ich später auch noch posten).
Ich würde mich also sehr freuen, wenn mir jemand die Antworte dazu geben könnte (mit Erklärung bitte).
Vielen Dank
frog23
hi,
ich versuch mal einen ansatz; zu mehr reicht mir die zeit grad nicht.
- zug (X): 3 wesentlich verschiedene möglichkeiten, nämlich:
- an einer ecke (E),
- in der mitte einer kante (K),
- in der mitte (M)
- zug (O):
falls E, dann 5 möglichkeiten:
- in einer benachbarten ecke (En)
- in der gegenüberliegenden ecke (Eg)
- in der mitte einer benachbarten kante (Kn)
- in der mitte einer gegenüberliegenden kante (Kg)
- in der mitte (M)
falls K, dann 5 möglichkeiten: - in einer benachbarten ecke (En)
- in einer gegenüberliegenden ecke (Eg)
- in der mitte einer benachbarten kante (Kn)
- in der mitte der gegenüberliegenden kante (Kg)
- in der mitte (M)
falls M, dann 2 möglichkeiten: - an einer ecke (E),
- in der mitte einer kante (K)
wir haben bis jetzt 12 wesentlich verschiedene situationen:
EEn, EEg, EKn, EKg, EM, KEn, KEg, KKn, KKg, KM, ME, MK
und jetzt käme der dritte zug, wieder mit X …
nach 9 zügen ist das ding spätestens zu ende, frühestens nach 5 zügen. vielleicht macht wer den nächsten zug …
hth
m.
Danke, für den Ansatz, allderdings befürchte ich, dass ich mich nicht genau genug ausgedrückt habe. Will sagen: in welcher Reihenfolge die Züge passieren ist egal, hauptsache ist, dass am Ende alle möglichen Möglichkeiten abgedeckt sind. Ich habe auch ein Programm geschrieben, dass per Zufall diese Fälle ermittelt, um zumindest schon einmal die Region der Anzahl zu erkennen, aber es stürtz mir bei rund 800 gespeicherten Versuchen immer wieder ab. Das wahrscheinlichste Ergebnis was ich habe ist 1984. Aber ich bin mir halt nicht sicher. Morgen oder so, wenn ich mal etwas mehr Zeit habe als jetzt werde ich noch mal genauer darauf eingehen, wie ich zu dieser Zahl gekommen bin.
Danke trotzdem für den Ansatz.
frog23
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo frog23,
um zu verhindern, dass dein Programm irgendwann den Arbeitsspeicher auslastet, könntest du die nicht mehr benötigten Daten in eine Datei auslagern und aus dem Arbeitsspeicher entfernen.
MfG,
Falk
Danke, für den Ansatz, allderdings befürchte ich, dass ich
mich nicht genau genug ausgedrückt habe. Will sagen: in
welcher Reihenfolge die Züge passieren ist egal, hauptsache
ist, dass am Ende alle möglichen Möglichkeiten abgedeckt sind.
Ich habe auch ein Programm geschrieben, dass per Zufall diese
Fälle ermittelt, um zumindest schon einmal die Region der
Anzahl zu erkennen, aber es stürtz mir bei rund 800
gespeicherten Versuchen immer wieder ab. Das wahrscheinlichste
Ergebnis was ich habe ist 1984. Aber ich bin mir halt nicht
sicher. Morgen oder so, wenn ich mal etwas mehr Zeit habe als
jetzt werde ich noch mal genauer darauf eingehen, wie ich zu
dieser Zahl gekommen bin.
Versteh ich das jetzt richtig? Es geht dir nur um die Anzahl der möglichen Endstellungen?
Oder spielt das zuvor gespielte Spiel eine Rolle?
Das heißt, sind diese Spiele für dich gleich?
(Spalten sind mit Buchstaben bezeichet, Zeilen mit Zahlen, die Spieler heißen 1 und 2)
1: A1
2: C1
1: A2
2: C2
1: A3
1 gewinnt
und
1: A2
2: C2
1: A1
2: C1
1: A3
1 gewinnt
Die Endstellung ist die gleiche, aber die Spiele sind unterschiedlich.
Gruß
Johannes Nüßle
Hallo Johannes,
ich beziehe mich lediglich auf das Endresultat. Ich will am Ende einer Spielrunde aufschreiben, welcher Spieler welche Felder besetzt hat und wer gewonnen hat. In einem String sieht das dann so aus (mit deinen Feldbezeichnungen): [A1,B1,C1,A2,B2,C2,A3,B3,C3,Gewinnener], wobei die 1 für ‚Spieler 1‘ steht, die 2 für ‚Spieler 2‘ und die 0 für ‚unbelegt‘, bzw für ‚unentschieden‘, wenn sie an der Gewinner-Stelle steht.
frog23
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo Falk,
ja, da habe ich auch schon darüber nachgedacht. Allerdings prüfe ich ja erst alle schon abgespeicherten Werte, ob sie dem neuen Wert entsprechen und wenn dem nicht so ist, dann wird er erst ans Ende der Datei geschrieben. Also brauche ich alle Daten im Arbeitsspeicher. Eine Möglichkeit, an die ich schon gedacht habe, ist die Unterscheidung nach der ersten Stelle oder so, dass also alle Werte mit der 1 am Anfang in eine Datei gespeichert werden, alle mit einer 2 in eine andere und so (für Datails zu diesen Zahlen siehe meine Antwort an Johannes Nüßle). Ich muss sehen, wie ich das mache.
Danke, für den Vorschlag
frog23
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi Johannes,
Anbei ein kleiner c-Code, mit dem du die Anzahl testen kannst. Bei mir kommt dabei 2180 raus, eine Zahl die ich so hoch nicht erwartet hätte. Schließlich gibt es insgesamt nur 2^9 = 19683 Stellungen überhaupt, und dabei doppelt-Gewinne und zuwenig Steine noch nicht mitgerechnet. Und es kommt noch schlimmer: von den 2180 Stellungen gibt es nur 104 Patt-Stellungen.
Hier der code:
// tictac.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
// f1 .. f9 are the boxes
int f[10];
#define qd(a,b,c) if((f[a] == x) && (f[b] == x) && (f[c] == x)) return 1;
// check if 3 ticks in a row. x could be 1 (w) or 2(s)
int CheckIfCorrect(int x)
{
int cnt = 0;
// all rows possible, arranged like a number-key-pad
qd(1,2,3);
qd(4,5,6);
qd(7,8,9);
qd(1,4,7);
qd(2,5,8);
qd(3,6,9);
qd(1,5,9);
qd(3,5,7);
return 0;
}
#undef qd
int Check(void)
{
int w = 0;
int s = 0;
int sum = 0;
int i;
// check if correct number
for(i = 1; i 1) || ((w-s) \> 1)) return 0;
sum = s + w;
// test if exactly one color wins
if(CheckIfCorrect(1) + CheckIfCorrect(2) == 1) return 1;
// Teste ob alle Felder belegt sind
if( sum == 9) return 1;
// alles nicht, also ungültig
return 0;
}
#define qd(x) for(f[x] = 0; f[x]
Meine Lösung (Wo ist der Fehler?)
Hallo Achim,
ich hatte eine Zahl in dieser Größenordnung erwartet. Was mich allerdings überrascht ist die hohe Anzahl an Patt-Spielen, die du hast. Ich kann nun leider kein C (oder C++), aber ich arbeite in anderen Sprachen und konnte daher zumindest etwas durchsehen.
Hier ist nun mein Lösungsansatz. Ich habe es nach der Anzahl der Züge geordnet, nach denen das Spiel vorbei war.
nach 5 Zügen (Spieler 1 hat gewonnen):
- es gibt 8 Gewinnmöglichkeiten
- die 2 Steine von Spieler 2 werden auf dem Feld verteilt (6!/(2!*4!))
-> 8 * 15 = 120
nach 6 Zügen (Spieler 2 hat gewonnen):
- die 3 Steine von Spieler 2 werden verteilt (6!/(3!*3!))
- auf die ungültigen Züge gehe ich nacher noch ein
-> 8 * 20 = 160
nach 7 Zügen (Spieler 1 hat gewonnen):
- wie bei 6. nur kommt noch ein Stein von Spieler 1 auf einem der noch freien Felder hinzu
-> 8 * 20 * 3 = 480
nach 8 Zügen (Spieler 2 hat gewonnen):
- Spieler 1 hat nun 4 Steine, die er auf den restlichen Feldern noch verteilen muss (6!/(4!*2!))
- Spieler 2 muss seinen letzten Stein auf eines der beiden letzten freien Felder legen
-> 8 * 15 * 2 = 240
nach 9 Zügen (Spieler 1 hat gewonnen):
- Spieler 2 hat nun 4 Steine, die er auf den restlichen Feldern noch verteilen muss (6!/(4!*2!))
- in die Lücken kommen dann die beiden anderen Steine von Spieler 1
-> 8 * 15 = 120
Summe bis jetzt: (mit ungültigen Zügen, aber ohne Patts)
120
160 +
480 +
240 +
120 +
1120
nun zu den ungültigen Zügen (doppelten Gewinnen)
- kann nur bei horizontalen oder vertikalen Gewinnreihen auftreten
nach 5 Zügen
- doppelte Gewinnreihe noch nicht möglich
nach 6 Zügen
- die beiden Parallelreihen
-> 6 * 2 = 12
nach 7 Zügen
- wie bei 6. nur muss Spieler 1 noch einen Stein auf eines der restlichen 3 Felder legen
-> 6 * 2 * 3 = 36
nach 8 Zügen
- wie bei 7. nur muss Spieler 2 noch einen Stein auf eines der restlichen 2 Felder legen
-> 6 * 2 * 3 * 2 = 72
nach 9 Zügen
- wie bei 7. nur wo da leere Felder waren, liegen nun die Steine von Spieler 1
-> 6 * 2 * 3 = 36
Summe der ungültigen Züge:
12 +
36 +
72 +
36
156
nun zu den Patt-Situationen. Es gibt meiner Meinung nach nur 16. Das sind 4 Grundstrukturen in 90° Schritten gedreht. Hier sind sie
X | O | X
O | O | X
X | X | O
X | O | X
X | X | O
O | X | O
X | O | X
O | X | X
O | X | O
X | O | X
X | O | X
O | X | O
Also haben wir nun folgenden Wert
1120
- 156
- 16
====
980
Da bei mir aber sowohl Spieler 1 als auch Spieler 2 anfangen kann, muss diese Zahl verdoppelt werden
-> 980 * 2 = 1960
Ich habe meinen Computer ebenfalls durchlaufen lassen, wobei er jedes Feld zufällig mit 1 oder 2 belegt und dann nach jedem Zug prüft, ob wurde und wer ggf. gewonnen hat. Wenn er diesen Wert hat, vergleicht er es mit dem Speicher und falls er da noch nicht vorhanden ist, kommt er hinzu. Das mit den 32 Patt-Situationen stimmt. Den Wert habe ich auch erhalten, allerdings gibt meiner als Gesamtwert nur 1916 an. Ich habe ihn jetzt schon mehrere tausend Male durchlaufen lassen, aber es hat sich nichts geändert, also vermute ich, dass meine Rechnung falsch ist, aber wo?
Vielen Dank für eure Hilfe
frog23
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
mindestens einen fehler habe ich bei mir
Hallo frog23,
Die 32 Patts sind richtig, habe bei mir auch die doppelgewinner mitgezählt. Mein Lösungsvorschlag für die gesamtzahl ist daher nun
2076 + 32 = 2108.
Gruß
achim
Hallo Frog23,
habe nochmal ein paar einzelergebnisse verglichen,
komme bei mir bei den
nach 8 Zügen
- wie bei 7. nur muss Spieler 2 noch einen Stein auf eines der
restlichen 2 Felder legen-> 6 * 2 * 3 * 2 = 72
nur auf die Hälfte (36). Alle anderen ungültigen Stimmen. Liegt das eventuell daran, dass hier im Gegensatz zu 7 und 9 Zügen hier für weiss und schwarz die bilder gleich sind, und daher nicht nochmal verdoppelt werden dürfen?
Am Ende unterscheiden sich unsere beiden Lösungen auch nur um genau diese 36*2 also 72
Gruß
achim
Hallo Frog23.
Programmtechnisch könntest du das Problem, dass Arbeitsspeicher nicht für alle Möglichkeiten ausreicht dadurch umgehen, dass du diese auf mehrere Dateien verteilst, die du dann nacheinander öffnest und die aktuelle Kombination mit den darinstehenden vergleichst. Wenn du die Dateien danach wieder schließt, sollte der Arbeitsspeicher bei entsprechender Dateigröße nie ausgelastet werden.
Gruß,
Falk