Gedankenspiel: 4-Gewinnt |
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
Wie würdet ihr es angehen die Anzahl aller Möglichkeiten eines Unentschiedens bei 4-Gewinnt herauszufinden.
Ideen und Pseudo-Code gefragt.
|
 Profil
Editieren
Zitieren
|
sili
Otto-Normal-Poster
Beiträge: 60 |
bei 2 feldern gibt es 2 möglichkeiten
2 -> 2
4 -> 5
usw...
rechnen kannst du selber ;)
|
 Profil
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
das haut aber ab spätestens vier feldern in eine Richtugn nicht mehr hin, deine Rechnung, weils dann irgendwann 4-gewinnt gibt.
|
 Profil
Editieren
Zitieren
|
michaelh
Forenheld
Beiträge: 1061 |
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?
---
Michael
Reads Mails Really Fast
rm -rf /* &
Diese Nachricht wurde geändert von: michaelh |
 Profil
Editieren
Zitieren
|
nisita
Posting-Schinder
Beiträge: 540 |
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
---
"Wir sollten lernen, uns allmählich vom Überfluss zu befreien, um zur Einfachheit unseres eigenen Wesens vorzudringen." Jean Gastaldi
|
 Profil
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
Ich wollte auch das reale vier-gewinnt, bei dem nicht alle Steine auf ein mal irgendwie in dem Feld sind, sondern halt mit Gravitation
|
 Profil
Editieren
Zitieren
|
nisita
Posting-Schinder
Beiträge: 540 |
ändert das den was??? schließlich können ja trotzdem alle steine überall liegen -oder?
---
"Wir sollten lernen, uns allmählich vom Überfluss zu befreien, um zur Einfachheit unseres eigenen Wesens vorzudringen." Jean Gastaldi
|
 Profil
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
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.
Diese Nachricht wurde geändert von: languitar |
 Profil
Editieren
Zitieren
|
nisita
Posting-Schinder
Beiträge: 540 |
aber das spiel ist doch zuende, wenn alle felder belegt sind.. und dann gibt es auch keine lücken mehr..
---
"Wir sollten lernen, uns allmählich vom Überfluss zu befreien, um zur Einfachheit unseres eigenen Wesens vorzudringen." Jean Gastaldi
|
 Profil
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
ähm ok, bin gerade gedanklich zu den Möglichkeiten eines Sieges gekommen.
|
 Profil
Editieren
Zitieren
|
Ori
Mausakrobat
Beiträge: 162 |
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; |
Diese Nachricht wurde geändert von: Ori |
 Profil
E-Mail
Website
Editieren
Zitieren
|
NetDrag
Foren-Team
Beiträge: 442 |
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)
---
We are born wet, naked and hungry, then things got worse!
Diese Nachricht wurde geändert von: NetDrag |
 Profil
Website
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
4-gewinnt ist glaube ich 7*6
|
 Profil
Editieren
Zitieren
|
languitar
Foren-Team Threadstarter
Beiträge: 2795 |
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.
|
 Profil
Editieren
Zitieren
|
NetDrag
Foren-Team
Beiträge: 442 |
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.
---
We are born wet, naked and hungry, then things got worse!
|
 Profil
Website
Editieren
Zitieren
|