ich bin gerade dabei, ein TicTacToe Spiel zu programmieren, und möchte nun die Computergegner-Stärke berechnen.
Ich habe mir gedacht, dass ich die Stärke in Prozent berechne.
Und zwar, wie viel Prozent er schon von den möglichen Zügen kennt.
(ich speicher jeden Zug, den der Pc gelernt hat, in eine Datenbank ab)
Nun wollte ich wissen, wie viele möglichen Züge es bei TicTacToe gibt?
Ich denk’ mir 9! = 362 880, oder?
Und wie viele mögliche Züge gibt es pro Runde?
Runde: 9 mögliche Züge, da ja jedes Feld besetzt werden kann
Runde: 8*8 ? es können ja 8 Felder besetzt werden, da schon eins durch runde 1 besetzt ist…
Wenn auf das Feld oben Links gesetzt wurde, kann man auf die weiteren 8 setzen, außer ObenLinks. Wenn aber obenMitte gesetzt wurde ja auf die weiteren 8 außer obenMitte…
Aber wie läuft es bei den nächsten 7 runden ab?
Ich kann mir leider die Rechnung gerade nicht herleiten.
pro Runde stehen alle Felder zur Verfügung, die noch nicht belegt sind. Da es insgesamt 9 Felder sind und pro Runde eines belegt wird, hast du pro Runde noch 9 - (Nummer der Runde - 1) Felder, zwischen denen du dich entsceiden kannst. Macht insgeasmt also 9! Züge.
also, in Runde 9 habe ich 9-(9-1) = 1 möglichen Zug, oder?
Ok, mögliche Züge, von wegen, wie viel Auswahl ich noch hab.
Wie sieht die Rechnung aus, wenn ich berechnen will, wie viele verschiedene „Muster“ es gibt?
in Runde 1 gibt es schon mal 9^1=9, da jedes Feld entweder von X, oder von Y besetzt sein kann.
Gibt es dann
in Runde 2 9^2=81,
in Runde 3 9^3=729,
in Runde 4 9^4=6561,
in Runde 5 9^5=59049,
in Runde 6 9^6=531441,
in Runde 7 9^7=4782969,
in Runde 8 9^8=43046721,
in Runde 9 9^9=387420489
mögliche verschiedene Muster?
Wobei man ab Runde 5 schauen muss, ob dort schon Gewonnen wurde, da die X-O-Konstelazionen, die schon 3 in einer Reihe haben, ja nicht weiter gespielt werden können.
Muss es dann ab Runde 5 immer mit 6^runde weiter gehen? es Stehen ja 3 Positionen je Runde nichtmehr zur verfügung.
in Runde 2 9^2=81,
in Runde 3 9^3=729,
in Runde 4 9^4=6561,
in Runde 5 6^5=7776
in Runde 6 6^6=46656
in Runde 7 6^7=279936
in Runde 8 6^8=1679616
in Runde 9 6^9=10077696
Ich hoff, ich hab jetzt nicht irgend einen kompletten Denkfehler drinnen.
mfg Kevin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
ich bin gerade dabei, ein TicTacToe Spiel zu programmieren,
und möchte nun die Computergegner-Stärke berechnen.
Ich denke da gibt es nix zu berechnen - wenn er flasch begonnen hat,
dann hat er verloren?
Du solltest das Problem durch eine gezielte Recherche angehen, wenn DU was dabei lernen willst. Es ist ziemlich sicher, dass alle Aspekte dieses Spiels von oben nach unten, von links nach rechte im Netz behandelt sind.
z.B. http://lernen.bildung.hessen.de/informatik/material/…
Die Software steht schon komplett, das einzige, was ich noch machen wollte ist, für die High-Score zu berechnen, wie viel Prozent der Züge der Computer schon gespeichert hat.
Wollte dafür auch wissen, wie viele Züge er für z.b. Runde 3 in der Datenbank haben muss, um Alle möglichen Runde-3-Muster zu kennen.
Ich seh mir die Datei aber noch etwas durch.
vll hab ich auf die Schnelle etwas übersehen
Nun wollte ich wissen, wie viele möglichen Züge es bei
TicTacToe gibt?
Ich denk’ mir 9! = 362 880, oder?
wesentlich weniger, wenn du drehungen und symmetrien beachtest.
im ersten zug gibt es zb. nur drei mögliche züge: eck-, mittel- oder seitenfeld.
im zweiten gibt es wiederum einige möglichkeiten, die durch drehung oder spiegelung ineinander überführt werden können.
des weiteren wird dir die bloße anzahl der züge nicht reichen, denn es gibt viele offensichtlich unsinnige zugmöglichkeiten, die in einem spiel selbst gegen einen anfänger nicht vorkommen werden.
also, in Runde 9 habe ich 9-(9-1) = 1 möglichen Zug, oder?
Ok, mögliche Züge, von wegen, wie viel Auswahl ich noch hab.
genau.
Wie sieht die Rechnung aus, wenn ich berechnen will, wie viele
verschiedene „Muster“ es gibt?
Für den Endzustand sind es (9 über 5)+(9 über 4) = 2*(9 über 5) = 252.
in Runde 1 gibt es schon mal 9^1=9, da jedes Feld entweder von
X, oder von Y besetzt sein kann.
Gibt es dann
in Runde 2 9^2=81,
in Runde 3 9^3=729,
in Runde 4 9^4=6561,
in Runde 5 9^5=59049,
in Runde 6 9^6=531441,
in Runde 7 9^7=4782969,
in Runde 8 9^8=43046721,
in Runde 9 9^9=387420489
mögliche verschiedene Muster?
nein, denn in der 2. Runde hat der andere keine 9 Felder mehr zur Auswahl, sondern nur noch 8.
Du kannst dir das einafch so vorstellen: Nach Zug x hat der eine x1 Felder, die er aussuchn kann, der andere x2, wobei x1+x2 = x gilt.
Für Zug 3 wäre das dann z.B. (9 über 2) * (7 über 1) * 2, da einmal 2 X und 1 O oder anders herum aufgezeichnet sind.
Daraus ergibt sich, dass nach geraden Züge weniger Muster entstehen, weil es gleich viele X und O gibt.
Wobei man ab Runde 5 schauen muss, ob dort schon Gewonnen
wurde, da die X-O-Konstelazionen, die schon 3 in einer Reihe
haben, ja nicht weiter gespielt werden können.
Muss es dann ab Runde 5 immer mit 6^runde weiter gehen? es
Stehen ja 3 Positionen je Runde nichtmehr zur verfügung.
das wäre jetzt zu einfach. Es gibt 16 Kombinationen im 5. Zug, die einen Sieg ergeben. Im 6. Zug gibt es noch 4 freie Felder, daraus folgt, dass 4*16 Muster eigentlich schon einen Sieg beinhalten und deswegen nicht gespielt werden würden. Deswegen ergibt sich nach dem 6. Spielzug (9 über 3)*(6 über 3) - 16*4 Muster. Das musst du dann immer so weiter rechnen.
Vorher gibt an wie der Zug davor aussah (ist in Runde 3 der „JETZT“)
Jetzt gibt an, wie das Spielfeld nach dem SteinSetzen auf „gesetzt“ aussah
Die Bewertung wird während des Spielens immer wieder neu berechnet…
