| von nisita |
ok, weiß endlich, was du meinst.. allerdings glaube ich immer noch, dass die 2^42 falsch sind.. denn das würde auch unterscheiden, was für ein gelber stein auf dem feld x-y liegt.. und die reihenfolge, die bei dir berücksichtigt wird, spielt nunmal keine rolle..
st |
| von Ori |
Es geht doch darum, herauszufinden, wie viele Anordnungsmöglichkeiten es für ein Unentschieden gibt. Die Anzahl läst sich bestimmen, indem man alle Spiele spielt und zählt, wie viele unterschiedliche Anordnungen es bei einem Unentschieden gibt.
Das ist aber sehr zeitaufwändig. Daher wird nach einer besseren Möglichkeit gesucht, diese Anzahl zu ermitteln. Ich bin mittlerweile zu der Überzeugung gelangt, dass dies nicht anders geht. Zu prüfen, ob eine Anordnung von Spielsteinen ein entschiedenes Spiel ist oder nicht, schafft mein Code innerhalb von Millisekundenbruchteilen.
Es werden pro Sekunde etliche tausend Spiele geprüft. Aber da es insgesamt 2^42 mögliche Spielsteinanordnungen gibt (ohne Berücksichtigung, dass man abwechselnd zieht, also je gleich viele rote wie gelbe Steine im Feld sind), dauert diese Methode sehr lange und führt, wie ich bereits erwähnte, zu einem falschen Ergebnis.
Die echte Methode dauert allerdings noch länger. |
| von nisita |
hm.. irgendwie versteh ich nicht, was du meinst.. nach welchen lösungen suchst du denn??? ich dachte, du würdest nur danach suchen, ob untenschieden oder gewonnen.. und das macht mein code ja auch..
was meinst du mit alle lösungen zu erwischen??? wenn du so ein spiel stein für stein durchspielst, was bringt dir das? denn auf ein unentschieden wirst du wohl nur selten stoßen..
aber so ein spiel durch zu spielen, ist ja auch nicht soo das ding.. brauchst halt random(6)+1, für jeden wurf, und dann muss überprüft werden, welcher der höchste stein ist, und dort dann drüber fliegt er rein..
sorry, aber bin irgendwie gerade durcheinander..
mfg
st |
| von Ori |
Dass ich zweimal den gleichen Code für die Diagonalen benutzt habe, war ein Fehler (copy, paste and forget), den ich inzwischen korrigiert habe. Da ich den Fehler aber beim Durchlaufen bemerkt habe, als noch keine Lösungen gefunden wurden (es gab noch genug waagerechte und senkrechte Vierer, die es nicht zur Diagonalen-Prüfung kommen ließen)
Es geht nicht um die Überprüfung einer Lösung, sondern um die Überprüfung aller Lösungen, die drei Tage in Anspruch nimmt.
Die einzige Möglichkeit, alle Lösungen zu erwischen besteht in der Durchrechnung ebendieser.
Ergo: Wir werfen rekursiv Stein für Stein für Stein. Immer abwechselnd (Code folgt irgendwann). |
| von nisita |
hallo..
habe mir nochmal gedanken gemacht.. wegen der erdanziehungskraft.. das stimmt schon, hatte da wohl doch einen denkfehler.. allerdings macht das es ja eigentlich unmöglich, die möglichkeiten zu bestimmen..
die 69 sind wohl ebenfalls falsch.. es gibt zwar 69 möglichkeiten, einen "4-er" auf das feld zu legen, alldernings, gibt es ja für eine variante 68 ander, dafür wiederum 67 andere etc.. was ja bedeuten würde, dass es 69! möglichkeiten geben würde, irgendwie zu gewinnen.. das wiederum ist auch blödsinn, denn man gewinnt ja schon mit dem ersten vierer..
um das zu überprüfen, ob es nun ein unentschieden gibt, ja oder nein hier mal ein bisschen code.. ist jedoch flash, aber dürfte eigentlich alles klar sein.. die setzung hab ich erstmal erstmal nicht beigefügt, da das ja zum überprüfen nicht interesant ist.. bei mir dauert eine überprüfung nichtmal eine sekunde..
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136: |
//es gibt ein feld.. 2 dimensionaler array..
show = function(){
zw = "";
for(k=0; k < feld.length; k++) {
for(i=0; i < feld[0].length; i++) {
zw = zw add feld[k][i];
}
trace(zw);
zw = "";
}
}
//ist eigentlich nur dazu da, um das feld anzuzeigen..
show();
//////////////
//überprüfung:
//////////////
//durchsucht den string "zw" nach "xxxx" oder "oooo" (x = spieler 1, o = spieler 2)..
//wenn dieser string gefunden wird (!=-1), dann gibt es also einen 4er.. -eigentlich
//könnte hier jetzt alles abgebrochen werden..
durchsuchen = function(){
if(zw.indexOf("xxxx") != -1 || zw.indexOf("oooo") != -1){
trace("Es hat jmd. eine 4er Reihe!");
}
}
////////////
//waagerecht
////////////
//trace ist in flash sowas wie "ausgabe".. zum überprüfen von variablen oder ähnlichem..
trace("waagerecht");
//feld wird durchsucht, eine zeile bildet einen string, der mit "durchsuchen" überprüft wird
zw = "";
for(k=0; k < feld.length; k++) {
for(i=0; i < feld[0].length; i++) {
zw = zw add feld[k][i];
}
trace(zw)
durchsuchen();
zw = "";
}
///////////
//senkrecht
///////////
//eigentl. dasselbe wie bei waagerecht.. nur ist jetzt ein string eine spalte, und nicht eine reihe..
trace("senkrecht");
zw = "";
for(k=0; k < feld[0].length; k++) {
for(i=0; i < feld.length; i++) {
zw = zw add feld[i][k];
}
trace(zw)
durchsuchen();
zw = "";
}
/////////////////
//Diagonal nw->so
/////////////////
trace("Diagonal nw->so");
//beide diagonalen durchsuchungen, kann man bestimmt noch optimieren..
//x und y, stellen die start variablen dar.. es fängt somit links unten
//in der ecke mit dem ersten string an.. natürlich brauch man die ersten 3
//und die letzten 3 strings nicht beachten, da sie ja nichtmal 4 "einheiten"
//langs sind..
//der startwert, wandert sozusagen am anfang nach unten (k--), und wenn
//ka dann 0 ist, wandert der startwert nach rechts (x=math.abs(k))
//in der while schleife, kommt es zu der eigentlichen scrägen durchlaufung
//des feldes (x++; y++;)
zw = "";
for(k=feld.length-1; math.abs(k) <= feld.length; k--) {
if(k==0){
x = math.abs(k)
y = 0;
}else{
x = 0;
y = k;
}
while(y < feld.length && x < feld[0].length) {
zw = zw add feld[y][x];
x++;
y++;
}
trace(+zw);
durchsuchen();
zw = "";
}
/////////////////
//Diagonal sw->no
/////////////////
trace("Diagonal sw->no");
//wie vorher, nur das nun der startwert unten rechts ist, er "wandert"
//dann nach oben, und dann nach links..
zw = "";
for(k=feld.length-1; math.abs(k) <= feld.length; k--) {
if(k<0){
//trace("123")
x = feld.length-math.abs(k);
y = 0;
}else{
x = feld.length;
y = math.abs(k);
}
//trace(x+","+y);
while(y < feld.length && x >= 0) {
zw = zw add feld[y][x];
x--;
y++;
}
trace(zw);
durchsuchen();
zw = "";
}
|
|
| von nisita |
7^(42) ist meines wissens falsch.. denn nach dir wäre es eine variation, diese berücksichtige jedoch die reihenfolge.. jedoch spielt die reihenfolge überhaupt keine rolle, deswegen würde ich sagen es ist eine kombination.. -> mein ergebnis siehe weiter oben..
somit, kannst du deine abfrage wohl auch "ein wenig" verkürzen..
bin zurzeit noch nicht sicher, ob es sinn macht, es so wie du zumachen.. ich habe mir gerade was anderes überlegt.. muss mal schauen, ob ich das jetzt noch hinbekomme..
wegen der erdanziehungskraft etc..
natürlich kann es sein, dass die untere reihe komplett rot ist.. nur dann hat der rote gewonnen, und es zählt dann zu einer möglichkeit zum gewinnen.. und natürlich, wird es nicht zu so einem spiel kommen, da man ja gewinnen will.. aber trotzdem gibt es die möglichkeit eine komplette reihe rot, und darüber eine komplette gelbe..
steinigt mich, wenn ich was falsches geschrieben habe
st
PS:
@ori
warum hast du no-sw 2 mal.. vorallem beides mal mit dem selbe code??? |
| von NetDrag |
dafür gibts ne datenbank
http://members.tripod.com/~MHabermann/VierGewinnt.html |
| von languitar |
| So und nun möchte ich mit diesen Grundlagen eine Simulation, die mir jeden Möglichen Spielstand (d.h. Gewinn bzw. Unentschieden) grafisch ausgibt. Und zwar so, dass das Teil keine 3 Jahre rechnet. |
| von NetDrag |
ich war bei diesem scheiß noch nie gut 
|
| von Ori |
Bei einem UNENTSCHIEDEN sind ALLE Felder gefüllt. Es gibt also für jedes der 7*6 Felder genau 2 Möglichkeiten: Rot oder gelb. Beide Farben kommen genau 21-mal vor, da abwechselnd eingeworfen wird. Es gibt daher 2 ^ 42 = 4.398.046.511.104 Kombinationen, von denen aber viele nicht den folgenden, geforderten Bedingungen entsprechen.
Aussortieren muss man alle, bei denen es mindestens eine Vierer-Reihe gibt
und die, die nicht entstanden sein können, weil die Steine nach unten fallen und nicht frei positioniert werden können (-> languitar).
Spielzugvarianten gibt es deutlich mehr, da ja 42-mal ein Stein eingeworfen wird. Da aber die Spalten irgendwann voll sind, sind es leider auch nicht 7 ^ 42 = Spielverläufe, sondern deutlich weniger (-> NetDrag). |
| von languitar |
| aber es gibt fälle, die eifnach nicht gehen. es können z.B. die unteren drei Reihen nicht komplett rot und die oberen drei komplett gelb sein. Ist zwar eine Möglichkeit das Feld zu füllen, aber keine die entstehen kann, wenn man immer abwechselnd reinwirft. |
| von NetDrag |
die anziehungskraft ist ja eigentlich egal, su schaust dir einfach das spiel an wenn es fertig ist.
ob in eine spalte dann rot-rot-gelb eingewurfen wurde oder gelb-rot-rot ist dann relativ egal.
es gibt insgesamt also 7^(7*6) kombinationen. von denen mußt du alle weckzählen bei denen eine kombination von 4 steinen drin ist. |
| von languitar |
| das kann aber auch nicht so einfach gehen, da es ja, wie gesagt, die erdanziehungskraft gibt und man schlecht einen stein unter einen anderen "legen" kann. |
| von languitar |
| 4-gewinnt ist glaube ich 7*6 |
| von NetDrag |
meinst du jetzt die anzahl aller möglichkeiten überprüfen, oder über prüfen ob das aktuelle spiel als unentschieden ausgegangen ist?
Soweit ich weiß ist ein 4 gewinnt spiel 7*7 groß, die Anzahl aller Lösungen ergibt sich also aus 7^(7*6)
|
| von Ori |
Da es ein Unentschieden nur geben kann, wenn alle Felder belegt sind, kann man das auf recht brutale Weise herausfinden.
Man rechnet alle Varianten durch, bei denen
a) alle Felder belegt sind,
b) je 21 Steine jeder Farbe benutzt wurden
und überprüft, ob
c) es nur Reihen aus höchstens 3 gleichen Steinen gibt.
Die Darstellung des Feldes würde ich aus programmiertechnischen Gründen von einem Boole'schen Array mit 42 Stellen übernehmen lassen. Dann werden alle Möglichkeiten durchgerechnet und gezählt.
Ich kann da ja zum Spaß mal kurz etwas schreiben und rechnen lassen.
---
20:40 Uhr:
Nach ersten Schätzungen dauert auch eine Optimierung noch deutlich zu lange (rund anderthalb Jahre), um schnell ein zufrieden stellendes Ergebnis zu liefern.
---
20:51 Uhr:
Genial einfach, einfach genial: Starke Optimierung bringt enormen Geschwindigkeitszuwachs, es dauert nur noch rund 3 Tage.
---
21:17 Uhr:
Zugegeben, nicht alle die auf diese Weise berechneten Lösungen sind zwangsläufig möglich, da durch die Gravitation bedingt nicht alle durch abwechselndes Werfen erreicht werden können. Wenn man allerdings das auch noch berücksichtigt, braucht man bedeutend länger, da das Ganze rekursiv berechnet werden muss, jeweils mit 7 Wurfmöglichkeiten. Dabei werden aber gleiche Endlösungen mehrmals durchgekaut, da ja nicht die Wurfreihenfolge, sondern die Lage der Spielsteine bei einem Unentschieden wichtig ist.
---
21:55 Uhr:
Für Verbesserungsvorschläge im Code bin ich dankbar...
(Programmiert mit C#, der erste Ausschnitt steht im Rumpf einer von System.Windows.Forms.Form erbenden Klassen, der zweite im Konstruktor)
1:
2: | private long[] zweiHoch = new long[43];
private const long startwert = 2203814451; |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111: | Show(); // Fenster anzeigen
bool[] feld = new bool[42];
int zaehler = 0;
int feldzaehler = 0;
int vierzaehler = 0;
int prozentler = 0;
// Zweierpotenzen berechnen
zweiHoch[0] = 1;
for (int i = 1; i < 43; i++)
zweiHoch[i] = (long) zweiHoch[i-1] * 2;
// %startwert in bool-Array umsetzen und ausgeben
for (int j = 0; j < 42; j++)
{
feld[j] = ((startwert / zweiHoch[j]) % 2 == 1);
Console.Write(feld[j] ? 1 : 0);
}
Console.WriteLine(string.Empty);
for (long i = startwert; i < 4398046511104; i++)
{
if (prozentler == 65536)
{
prozentler = 0;
Text = i.ToString() + " = " + ((float) (100f * ((float) i + 1f) / 4398046511104f)).ToString("0.0000") + "% ~ " + zaehler;
Application.DoEvents();
}
else
prozentler++;
// Felder setzen
for (int j = 0; j < 42; j++)
{
feld[j] = ! feld[j];
if (feld[j]) break;
}
// genau 21 Felder true
feldzaehler = 0;
for (int j = 0; j < 42; j++)
if (feld[j]) feldzaehler++;
if (feldzaehler != 21) continue;
// auszählen
// waagerecht (w-o)
for (int j = 0; j < 42 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 3; l++)
{
if (feld[j + k + l] == feld[j + k + l + 1])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// senkrecht (n-s)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 7 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 21; l += 7)
{
if (feld[j + k + l] == feld[j + k + l + 1])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// diagonal 1 (no-sw)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 24; l += 8)
{
if (feld[j + k + l] == feld[j + k + l + 8])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// diagonal 1 (no-sw)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 24; l += 8)
{
if (feld[j + k + l] == feld[j + k + l + 8])
vierzaehler++;
else
break;
}
}
if (vierzaehler < 3)
{
zaehler++;
Console.WriteLine(i.ToString());
}
}
Text = "fertig ~ " + zaehler; |
|
| von languitar |
| ähm ok, bin gerade gedanklich zu den Möglichkeiten eines Sieges gekommen. |
| von nisita |
| aber das spiel ist doch zuende, wenn alle felder belegt sind.. und dann gibt es auch keine lücken mehr.. |
| von languitar |
Das gibt aber die Möglichkeit von Lücken, und zwar nur in einer bestimmten Weise.
"kein Stein" ist schließlich auch eine mögliche Belegung eines Feldes. Vorausgesetzt darüber kommt kein weiterer Stein. |
| von nisita |
| ändert das den was??? schließlich können ja trotzdem alle steine überall liegen -oder? |
| von languitar |
Ich wollte auch das reale vier-gewinnt, bei dem nicht alle Steine auf ein mal irgendwie in dem Feld sind, sondern halt mit Gravitation  |
| von nisita |
habe mir mal gedanken gemacht..
die einzigste sinnvolle variante das zu berechnen ist wohl die 2.möglichkeit von michaelh..
ich glaube ein standartfeld ist 7*6 (7reihen,6spalten groß) ->42felder.. jeder spieler hat 21 steine.. ich denke mir mal, das jeder stein, überall sein kann, auch wenn man sie ja eigentlich von oben "reinfallen lässt".. wenn dem nicht so ist, müsste man da wohl erstmal was ändern..
bei 21 steinen auf 42felder macht das mit der kombinatorik 42über21.. -> (42!)(21!*(42-21)!) = 538257874440 möglichkeiten die steine auf dem feld aufzuteilen..
die möglichkeiten zu gewinnen..
hozizontal:
in einer reihe gibt 4 möglichkeiten -> *6 -> 24 möglichkeiten
vertikal:
in einer spalte 3 möglichkeiten -> *7 -> 21 möglichkeiten
schräg1 (von links nach rechts, oben nach unten):
2 6er reihen -> 6möglichkeiten
2 5er reihen -> 4möglichkeiten
2 4er reihen -> 2möglichkeiten
->12 möglichkeiten
schräg2 (von links nach rechts, unten nach oben)
wie bei schräg 1
->12möglichkeiten
-> 24+21+12+12=69 möglichkeiten
538257874440 - 69= 538257874371 möglichkeiten
ja.. klingt irgendwie ziemlich sinnlos.. vorallem die anzahl der möglichkeiten zu gewinnen scheint mir irgendwie so wenig..
st |
| von michaelh |
Möglichkeiten:
- Alle Kombinationen ausprobieren 
- Anzahl der möglichen Kombinationen (Gewinn, verlieren oder unentschieden) minus denen bei denen ein Spieler gewinnen bzw. verlieren kann.
Wieviel Felder hatte denn 4 Gewinnt nochmal?
7 Spalten und 7 Zeilen? |
| von languitar |
| das haut aber ab spätestens vier feldern in eine Richtugn nicht mehr hin, deine Rechnung, weils dann irgendwann 4-gewinnt gibt. |
| von sili |
bei 2 feldern gibt es 2 möglichkeiten
2 -> 2
4 -> 5
usw...
rechnen kannst du selber ;) |
| von languitar |
Wie würdet ihr es angehen die Anzahl aller Möglichkeiten eines Unentschiedens bei 4-Gewinnt herauszufinden.
Ideen und Pseudo-Code gefragt. |
|
