URL: https://www.overclockers.at/coding-stuff/checkwhowinstictactoe_82524/page_1 - zur Vollversion wechseln!
Hi,
ich suche einen eleganten Algorithmus der mir bei einem TicTacToe Spiel das in einem 2-dimensionalen Array gespeichert ist sagt wer gewinnt.
Einfach alle durchprobien ist eh klar, ich hab auch schon darüber nachgedacht mir die position des zuletzt gesetzten mitzugeben und abhängig davon nur die in frage kommenden Reihen zu überprüfen. Das bringt mir zwar einen Performancevorteil 
aber ist nicht sehr elegant weil sehr programmieraufwendig.
tictactoe (im klassischem stil) gehört eigentlich zu den spielen die man nicht gewinnen/verlieren kann.
außer du spielst 3x3x3 oder 4x4x4...
um das gehts aber nicht. es ist möglich wenn der andere einen fehler macht, und das muss ich abprüfen
rno ownz jaja die faulen studenten. machs einfach in 2 schleifen alle senkrecht, alle waagrecht und dann noch die 2 diagonalen. fertig.
btw mach die uebung auch grad obwohl ich schon genug punkte fuer eine positive note hab.
hmmm brauchst nicht lang mehrere letzte züge merken... FÜR JEDEN KLICK prüfst eigentlich (bei der 4gewinnt variante):
ausgehend vom aktuell gesetzten punkt, nur ob da eine horizontale/vertikale/diagonale 4er reihe is
dh du brauchst nicht die ganze reihe und was sonst noch prüfen... es genügt, vom punkt aus a paar rekursive funktionen durchlaufen:
long zähleN(pkt, player) zählt immer genau 1 dazu wenn vom angegebenen pkt der nördliche auch vom player besetzt is und ruft sich selba rekursiv auf - result = anzahl aller berührenden gewählten in Nord-Richtung
ebenso zähleS, zähleO, zähleW, zähleNO, zähleSW, zähleSO, zähleNW
danach addierst s immer paarweise (zähleN + zähleS und so weiter, immer nur die beiden gegenüberliegenden)
Nun subtrahiere 1 (weil du ja den startpunkt nun in beiden funktionen gezählt hast statt einmal
und wenn mindestens ein paar nun die summe 4 oder größer ergibt, GEWONNEN!
was is da aufwändig??
wie kommst du da auf 4 in einer reihe?? es geht um tic tac toe(3 gewinnt)
also maximal die 3 senkrechten die 3 waagrechten oder die 2 diagonalen
Zitat von xdfkrno ownz
btw mach die uebung auch grad obwohl ich schon genug punkte fuer eine positive note hab.
den standard kann eh jeder sofort hinschreiben habts mips und x86 assembler programmiert? multi war eh ganz einfach aber bei addition und subtraktion hats mi nimmer gschert.
i hab nur den mips gmacht, hab für den pentium ka zeit /nich tgenug lust gehabt. War ziemlich heftig, aber dafür hab ichs lustiger gfunden als verilog
also bei einer TicTacToe Gewinnabfrage würd ich schon gscheit auf die Laufzeit sch*issn
Ich mein in einer kleinen Matrix die Anordnung von drei gleichartigen Werten zu finden .. ich glaub das geht sogar irgendwie rekursiv (mit Nachbarn finden usw. viel Spass wenn du das probierst) aber wenn du es nicht so arg machen willst dann programmier dir eben diese 4 IF Anweisungen und die 2 FOR schleifen schnell (2 IFs innerhalb jeweils einer For 1-3 für horizontal und vertikal, 2 für die beiden Diagonalen .. fertig)
jaja, hab eh schon mitkriegt das ichs mir sparen kann
thx anyway
bei einem größeren spielfeld lohnt es sich zu optimieren, aber bei einem 3x3 spielfeld, eine 3er folge ausgehend vom zuletzt gesetzten feld zu suchen heißt max 6 weitere überprüfungen, oft sogar nur 4, weil die diagonalen brauchst nur prüfen, wennst ein stein in der mitte oder an enem der eckpunkte gesetzt hast.
mußt du ein komplettes spielfeld prüfen, glaube ich nicht daß man die lösung vom 8-damen problem (bei dem man quasi jedesmal eine reihe, spalte und diagonale sperrt) übernehmen kann.
du kannst aber direkt mit vergleichen nach so einer 3er kombination suchen, oder du verwendest die arithmetik:
spielfeld:
f11 f12 f13
f21 f22 f23
f31 f32 f33
0 nicht gesetzt
1 X
2 O
z1=f11+f12*3+f13*9
z2=f21+f22*3+f23*9
z3=f31+f32*3+f33*9
s1=f11+f21*3+f31*9
s2=f12+f22*3+f32*9
s3=f13+f23*3+f33*9
d1=f11+f22*3+f33*9
d2=f31+f22*3+f13*9
ist eines der ergebnisse 13, so hat X gewonnen
ist eines der ergebnisse 26, so hat O gewonnen
(natürlich wird man das in eine schleife packen, und nicht so ausschreiben, dann kann man vorzeitig abbrechen, wenn gewonnen wurde)
tip für die schleifenprogrammierung: natürlich ist x1+x2*3+x3*9 = x1*3^0 + x2*3^1 + x3*3^2 = ((x3*3)+x2)*3+x1
--
im spiel kommt es natürlich öfters vor, daß du nicht gewinnst, als daß du gewinnst (was ja genau 1 mal vorkommt, in max 9 möglichen zügen).
sollte es also einen algorithmus geben, der günstiger verläüft bzw der vorzeitig terminieren kann, und trotzdem beweißt, daß man nicht gewonnan haben kann, dann währe evt dieser vorzuziehen.
hier könnte man sich evt anleihen am 8 damen problem nehmen: zb:
- eine reihe/spalte/diagonale kann nicht gewinnausschlaggebend sein, wenn dort sowohl der eine als auch der andere spieler einen stein gesetzt haben.
- eine reihe/spalte/diagonale kann nicht gewinnausschlaggebend sein, wenn sie nicht vollständig ist.
also entweder markierst du dir für jede r/s/d ob bereis spieler 1 oder 2 oder 1+2 zeichen gesetzt haben, oder du realisierst es mit einem counter: für X ziehst du 1 ab, für ein O addierst du 1 zu jedem counter der spalte/reihe/diagonale für jeden (neuen) gesetzten stein. erreicht ein counter den absolut-wert von 3 , dann hat einer der spieler gewonnen (bei -3 ist es X, bei +3 ist es O), jeder andere wert bedeutet, daß diese r/s/d nicht gewinnbringend sein kann.
aber zahlt sich all der aufwand tatsächlich für ein 3x3 spielfeld aus ?
Zitat von xdfkhabts mips und x86 assembler programmiert? multi war eh ganz einfach aber bei addition und subtraktion hats mi nimmer gschert.
Zitat von RingdingWas könnte einfacher sein als Addition und Subtraktion? Wo ist das Problem?
Zitat von RingdingWas könnte einfacher sein als Addition und Subtraktion? Wo ist das Problem?
as alexsb said mussten wir eine fpu nachbauen.
overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025