Archiv verlassen und diese Seite im Standarddesign anzeigen : Tic Tac Toe
Moinsen
klingt krank aber mich beschäftigt im mom die Maximale Anzahl an Zügen bei dem Spiel Tic Tac Toe....
Wenn ich mir alle im mom einfallenden Möglichkeiten aufzeichne komme ich auf 20 Endbilder.. sollte doch auch 20 Wegen dorthin entsprechen oder ?(
xoo oox oxo oxo
oxx xxo xxo oxx
oxo oxo oox xoo
---------------
oxx xxo xox xox
xoo oox oox xoo
xox xox xxo oxx
---------------
xox oxx oxo xxo
xox xoo xox oox
oxo oxx xox xxo
---------------
xox oox oxo xoo
oxo xxo oxo oxx
oxo oox xox xoo
---------------
xxo xox oox oxo
oxx oxx xxo xxo
xoo oxo oxx xox
Kann mir einer eine Plausieble Formel geben wie ich aus den 9 Feldern, 2 Spielern und der Bedingung das keine 3 in einer Reihe sein Dürfen ?
xoo oox oxo oxo
oxx xxo xxo oxx
oxo oxo oox xoo
sind ja alle gleich, nur gespiegelt oder gedreht. ergo haben sie alle den gleichen weg.
das prob ist aber, dass es mehrere wege zu einer endsituation gibt. z.b.:
--> --> --> --> --> --> --> -->
--- --- --o x-o x-o x-o x-o x-o xoo
o-- ox- ox- ox- ox- oxx oxx oxx oxx
--- --- --- --- --o --o o-o oxo oxo
--o --o -oo xoo xoo xoo xoo xoo xoo
--- --x --x --x o-x oxx oxx oxx oxx
--- --- --- --- --- --- --o -xo oxo
MeltDown
02.12.2001, 23:40
Der erste Spieler hat 9 Möglichkeiten sein Kreuz zu setzen, der zweite findet 8 freie Felder vor, der erste dann 7 und so fort.
Es gibt insgesamt für die Besetzung aller Felder 9*8*7*6*5*4*3*2*1 = 9! = 362 880 mögliche Züge.
Diese große Anzahl ist mehr theoretisch, weil weder Symmetrien noch Strategien berücksichtigt sind.
@MeltDown:
du hast etwas übersehen:
-x- --- --- ---
--- == --x == --- == x--
--- --- -x- ---
diese 4 varianten unterscheiden sich ned grundsätzlich. sind alles drehungen des 1.
sa gibt in der ersten runde nur 3 varianten (ecke, seite oder mitte)
danach gibts in der 2. runde je nach variante in der 1. runde wieder verschieden viele möglichkeiten....
Also... ich hab mir mal die Mühe gemacht alle Combinationen bis zum 4ten Zug aufzumalen :D
Also der erste Zug erlaubt 3 möglichkeiten...
als nächstes habe ich einen dieser möglichkeiten genommen und daraus den 2ten zug durchgespielt...
aus einem der ersten 3 möglichkeiten ergeben sich 8 weiter möglichkeiten.
d.h. doch dann 3^8 möglichekeiten bei 2 erlaubten zügen oder?
dann der 3te zug brachte 7 möglichkeiten wenn ich wieder eine möglichkeit des 2ten zuges betrachtet habe..
also (3^8)^7 ?? wenn das so wäre wurde das am ende so aussehen
3^(8*7*6*5*4*3^2*2) wenn das spiel nach 9 zügen zuende ist...
und das is doch etwas viel.. :rolleyes:
*kopfkratz*
mir ist auch aufgefallen das bei einigen zügen die symmetrie eine masse an möglichkeiten wegfallen.. jedoch bei anderer platzierung sind wieder alle möglichkeiten offen.. wie bekommt man den kram unter einen hut??
sorry
hab da mist gebaut...
3*8*7*6*5*4*3*2*1
müsste es sein... aber das gibt bei weitem noch nicht alle bedingungen wieder...
und die Summe aus dem Produkt von 9Urmöglichkeiten kanns ja auch ned sein.. dividiert durch die anfangsmöglichkeiten
denn das spiel is ja schon bei manchen wegen nach 5 Zügen gewonnen und es gibt letzendlich nur 5 endbilder die ein unendschieden zulassen... allein diese wege zu berechnen versengt mir die birne...
ich hau mich erstma pennen :D
bis morgen...
Also wenn man die Symmetrie und die Spielregel (wenn 3 in einer reihe sind is ende) mit berücksichtigt, dann sehe ich da keine regelmässigkeit die man in einer definition ausdrücken könnte...
zB es gibt 3 möglichkeiten für den ersten zug, aus 2en von denen ergeben sich 8 und aus einem nur 2.. und aus einem der 2 ergeben sich 7. weiter....
aus allen 7 ergeben sich jeweils wieder 2*6 + 3*5 + 2*4 ...
also ich seh echt keine chance das allgemneingültig auszudrücken...
ich schliess mich da MAfuba an. hab das vor einiger zeit schon mal versucht, da bleibt wohl echt nix übrig, als alle varianten durch zu machen (oder denken).
eigentlich koennt man ja ein proggie schreiben, welches per zufall die moeglichen felder setzt, und nach jeder runde den status zurueckgibt... d.h. bei ner schnellen cpu hast du das ergebnis in ein paar minuten... :D
waere nur mal so eine ueberlegung... das ganze muss ja dann nicht grafisch sein...
greetz
Codeq sag bitte bescheid falls du weiter gekommen bist.
hast mein interesse geweckt :D
Derzeit bleibt mir wohl echt nichts anderes übrig als alles per Prog durchspielen zu lassen... :(
Also die Anzahl der Züge
Der erste Spieler hat 9 Möglichkeiten sein Kreuz zu setzen, der zweite findet 8 freie Felder vor, der erste dann 7 und so fort.
Es gibt insgesamt für die Besetzung aller Felder 9*8*7*6*5*4*3*2*1 = 9! = 362 880 mögliche Züge.
Diese große Anzahl ist mehr theoretisch, weil weder Symmetrien noch Strategien berücksichtigt sind.
Alle Muster bestehen aus 5 Kreuzen und 4 Kreisen
Es müssen also auf 9 Felder 5 Kreuze und 4 Kreise verteilt werden. Zu diesem Zweck werden die Muster durch eine neunstellige Zahl im Zweiersystem dargestellt: = 011 100 101
Ein Computer zählt im Dualsystem von 0 bis 111 110 000 und siebt dabei alle Zahlen mit 5 Einsen und 4 Nullen aus und registriert diese.
Ergebnisse: Es gibt 126 verschiedene Muster.
Diese Anzahl n = 126 ergibt sich auch aus der Theorie. Es handelt sich um eine "Permutation von 9 Elementen auf 2 Arten". Von der einen Art sind 5, der anderen Art 4 vorhanden.
Dafür gilt die Formel: n= 9! : (4! * 5!) =126.
! steht für Faktultät :D
Von den 126 Mustern erscheinen nur 17 Muster (7,9%) bei einem Unentschieden. Diese Muster erscheinen bei normalem Spiel am Ende.
Spiegelt man die Muster (Quadrate) an allen möglichen Symmetrieachsen, so ist es möglich, dass sie sich nicht verändern.
Zählt man diese symmetrischen Quadrate nur einmal, so reduziert sich die Zahl 126 auf 23 Muster.
Die Zahl 126 setzt sich zusammen aus 10*8 + 11*4+2*1. Der 1. Faktor gibt die Anzahl der Klassen symmetrischer Quadrate an, der 2.Faktor die Anzahl symmetrischer Quadrate in einer Klasse.
Einmalig sind die allseitig symmetrischen Muster 010 111 010 und 101 010 101.
OK nu isses komplett...
hab nen netten JavaScript Spource :D
<HTML><HEAD><title></title>
<SCRIPT LANGUAGE="JavaScript">
step = 0;
diff=3;
function clear_all(form) {
step = 0;
for (i=0;i<9; ++i) {
position="a"+i;
form[position].value="";
}
}
function clickit(field) {
if (step == -1) {alert("Noch mal spielen!"); return;}
position=field.name.substring(1,2,1);
position = ´a´+position;
if (field.form[position].value !="") {alert("Geht nicht!"); return;}
field.form[position].value="X";
if (eval_pos(field.form)) {
field.form.output.value="Sieg!";
step = -1;
return;
}
position=get_move(field.form);
field.form.output.value=´I moved to ´ + position.substring(1,2,1);
if (position=="") {
field.form.output.value="Kein Gewinner.";
step = -1;
return;
}
field.form[position].value="O";
if (eval_pos(field.form)) {
field.form.output.value="Verloren!";
step = -1;
}
}
function eval_pos(form) {
if ((form.a0.value!="" && form.a0.value==form.a3.value && form.a0.value==form.a6.value)||
(form.a0.value!="" && form.a0.value==form.a1.value && form.a0.value==form.a2.value) ||
(form.a0.value!="" && form.a0.value==form.a4.value && form.a0.value==form.a8.value) ||
(form.a1.value!="" && form.a1.value==form.a4.value && form.a1.value==form.a7.value) ||
(form.a2.value!="" && form.a2.value==form.a5.value && form.a2.value==form.a8.value) ||
(form.a2.value!="" && form.a2.value==form.a4.value && form.a2.value==form.a6.value) ||
(form.a3.value!="" && form.a3.value==form.a4.value && form.a3.value==form.a5.value) ||
(form.a6.value!="" && form.a6.value==form.a7.value && form.a6.value==form.a8.value))
return true;
else
return false;
}
function f(a) {
if (a == "") return "."; else return a;
}
function comp_move(form,player,weight,depth) {
var cost;
var bestcost=-2;
var position;
var newplayer;
if (player=="X") newplayer="O"; else newplayer="X";
if (depth==diff) return 0;
if (eval_pos(form)) return 1;
for (var i=0; i<9; ++i) {
position=´a´+i;
if (form[position].value != "")
continue;
form[position].value=player;
cost = comp_move(form,newplayer, -weight, depth+1);
if (cost > bestcost) {
bestcost=cost;
if (cost==1) i=9;
}
form[position].value="";
}
if (bestcost==-2) bestcost=0;
return(-bestcost);
}
function get_move(form) {
var cost;
var bestcost=-2;
bestmove="";
if (step++ == 0)
if (form.a4.value=="")
return "a4";
else
if (form.a0.value=="")
return "a0";
for (var i=0; i<9; ++i) {
localposition=´a´+i;
if (form[localposition].value != "")
continue;
form[localposition].value="O";
cost=comp_move(form,"X", -1, 0);
if (cost > bestcost) {
if (cost==1) i=9;
bestmove=localposition;
bestcost=cost;
}
form[localposition].value="";
}
return bestmove;
}
function complain(field) {
field.form.output.focus();
alert("Nicht die Spielfelder direkt veraendern!");
}
</SCRIPT></HEAD>
<BODY><CENTER>
<FORM>
<INPUT SIZE=2 NAME="a0" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b0" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a1" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b1" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a2" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b2" OnClick="clickit(this)">
<BR>
<INPUT SIZE=2 NAME="a3" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b3" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a4" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b4" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a5" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b5" OnClick="clickit(this)">
<BR>
<INPUT SIZE=2 NAME="a6" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b6" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a7" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b7" OnClick="clickit(this)">
<INPUT SIZE=2 NAME="a8" OnFocus="complain(this)">
<INPUT TYPE="button" NAME="b8" OnClick="clickit(this)">
<BR>
<BR>
Aussage: <INPUT NAME="output" TYPE="text"><BR>
Schwierigkeit: <SELECT NAME="difficulty" OnChange="diff=form.difficulty[form.difficulty.selectedIndex].value;">
<OPTION VALUE=1> Ricky-Niveau
<OPTION VALUE=2> Lee-Niveau
<OPTION VALUE=3 SELECTED> Jazzy-Niveau
<OPTION VALUE=4> Otto Rehhagel-Niveau
</SELECT>
<BR>
<INPUT TYPE="button" VALUE="Computer zieht zuerst" OnClick=" if (!step++) this.form.a4.value=´O´;">
<BR>
<INPUT TYPE="reset" VALUE="Neu" OnClick="clear_all(this.form)">
</FORM>
</CENTER></BODY></HTML>
Ich sag nur !!!!F-R-E-A-K!!!!
Bibolorean
18.12.2001, 19:21
Dieser Meinung kann ich mich nur anschliessen!
Ich selbst habe dies schon länger ausprobiert, kam aber nie auf ein richtig brauchbares Resultat...
!!!FREAK!!!
Aber... Das is gut so :]
http://www.coding-board.de/tutorials/javascript/tictactoe/ttt.html
wers mal online testen will
mir ist aufgefallen das aus den ' ein ´geworden ist... also ersetzen falls ihr den source kopieren wollt...
:cool:
vBulletin® v3.8.6, Copyright ©2000-2012, Jelsoft Enterprises Ltd.