Forum: Mikrocontroller und Digitale Elektronik Tic Tac Toe


von Logic (Gast)


Lesenswert?

Hallo,
Ich habe vor als Abschlussprojekt ein Tic Tac Toe Spiel zu realisieren.
Mit einem Bedienungsfeld (9 Taster) und einem Anzeigefeld mit 2 farbigen
LED's.
Nun wollte ich hier mal fragen ob ihr mir Tipps geben koennt wie ich
das ganze mal angehen soll.

von Stefan Heinbockel (Gast)


Lesenswert?

Nun, am besten mit nem Mikrocontroller. Kennst du dich da schon etwas
aus? Sonst bring es dir am besten anhand dieser Seite bei, gibt n
tolles AVR-Tutorial :)
Dann musst du dir noch überlegen, was genau du machen willst: Soll man
gegeneinander spielen? Oder (wahlweise?) gegen die KI - dann musst du
die auch noch programmieren.
Mach dir für die LEDs ne (Treiber nicht vergessen, die AVRs können
meist mehr Strom senken als ausgeben) Matrix, und für die Taster auch.
Dann noch n Start-Taster und n paar Auswahl-Taster und -anzeigen, je
nach Bedarf, und ein Controller wie der ATMEga8 dürfte sowohl Pin- als
auch von der Prozessorleistung nicht überfordert sein.

von Logic (Gast)


Lesenswert?

Hallo,
mit Mikrocontrollern kenn ich mich aus. Hab auch schon ne Laufschrift
selber programmiert mit 320 LED's alle gemultiplext.


Erstmal will ich es Mensch gegen Mensch hinbekommen.

Mein erster Gedanke wie ich die Software realisiere war mit If's und
Case Bedingungen.
Oder gibts da noch ne bessere Möglichkeit?

von peter dannegger (Gast)


Lesenswert?

Für nur 9 Tasten und 18 LEDs lohnt sich noch kein Multiplexen, einfach
direkt ansteuern.


Peter

von Sven (Gast)


Lesenswert?

>>Für nur 9 Tasten und 18 LEDs lohnt sich noch kein Multiplexen, einfach
direkt ansteuern.

Wifo? Das sind schon 27 Pins, also mindestens ATmega16 in 40pol, Mit
Multiplex dürfte es ein ATmega 8 oder ein ATtiny2313 tun. Und so viel
umständlicher ist das auch nicht.

Sven

von Logic (Gast)


Lesenswert?

Man muss bedenken das die LED's ja 3 Füße haben weil die ja 2 farben
anzeigen können.

Das ganze wollte ich dann noch in 3D machen :-D also 3 ebenen und dann
kann man auch gewinnen wenn man z.b immer ein X in jeder ebene in der
linken oberen Ecke hat.
Aber ich denk das wird dann zu Kompliziert.

Kann mir noch einer sagen wie ich das mit der Software anstellen soll
(Case und IF's) oder was ganz anderes

von Malte _. (malte) Benutzerseite


Lesenswert?

Also ich habe letztens ein 4 Gewinnt auf einem AVR geschrieben.
Um ein Spielende zu erkennen wurde für jedes Feld auf dem ein Stein war
überprüft ob dieser links, rechts, oben, unten, und in den
entsprechenden schrägen drei weitere Felder mit der Farbe besetzt
waren. Ist dies der Fall, so hat ein Spieler gewonnen. Gleichzeitig
wird in einem Bit gespeichert ob es irgendwann ein leeres Feld gab. Hat
niemand gewonnen und wurde das Bit nicht geändert ->unentschieden.
Die KI setzt testeshalber auf jedes Feld und führt die obige Funktion
aus. Je nach Resultat entscheidet sie sich dann. Wobei die
Test-platzierungen Rekursiv immer weiter geführt werden wenn die obige
Bewertung sagt dass das Spiel noch nicht zu ende ist.  Leider benötigt
die Rekursion schnell sehr viel Rechenzeit und auch der Stack bleibt
nicht ganz klein.
Irgendwo gab es für die Methode einen schönen Artikel in Wikipedia, den
ich nur leider nicht wiederfinde.

von Logic (Gast)


Lesenswert?

Ok habs mir anders überlegt ich mach das doch net in 3D wird nach
längerem überlegen glaub doch zu kompliziert. Mach das jetzt in 2D mit
paar Features wie LCD Display in dem es den Spielstand Gewinner bla bla
bla anzeigt.

von Logic (Gast)


Lesenswert?

Hat schon jemand ne Ki in Bascom geschrieben. Oder ein Tic Tac Toe spiel

von Wegstaben V. (wegstabenverbuchsler)


Lesenswert?

"Hat schon jemand ne Ki in Bascom geschrieben. "

Ich hab neulich einen Einstein-Simulator in LISP für einen 16F84
geschrieben. Den kannst du auf ne Solarium-Karte hochladen. Da
allerdings der Speicherplatz etwas knapp wahr, mußte ich ein paar der
KI-Routinen draussen lassen. Jetzt spricht mein Einstein nur noch 7
Sprachen und hat nur noch einen IQ von 128.

von Philipp Sªsse (Gast)


Lesenswert?

Ich würde wohl ein signed char Feld[3][3] definieren, daß für null leer
ist, für Kreuz 1 und für Kreis minus eins. Dann noch zwei Felder
Reihe[3] und Spalte[3] sowie Diagonale1 und Diagonale2. Am Anfang ist
alles null. In der Variable "Spieler" steht nun eine 1 oder -1, je
nachdem wer dran ist.

Für jedes gesetzte Feld Feld[x][y] kommt nun

  Feld[x][y] = Spieler
  erhöhe(&Reihe[x])
  erhöhe(&Spalte[y])
  if x = y then erhöhe(&Diagonale1) endif
  if x = 3 - y then erhöhe(&Diagonale2) endif

(Achtung! Ich weiß nicht, in was Du programmieren willst, deswegen
schreibe ich hier in Pseudosprache. In C würden x und y von 0 bis 2
laufen, also müßte die Abfrage if (x=2-y) heißen etc.)

Und dann noch das Unterprogramm erhöhe(*Variable) macht jetzt
folgendes:
*Variable = *Variable + Spieler
if *Variable = 3 OR *Variable = -3 then gewonnen = true endif


Auf die Art mußt Du nicht nach jedem gesetzten Stein eine riesige
if-Orgie lostreten für alle Kombinationsmöglichkeiten.

Für eine KI hast Du die Wahl entweder für jede "vorausgedachte"
Spielebene eine Kopie der ganzen Variablen anzulegen oder nur zu
speichern, wohin der Zug ging (und dann das Feld wieder auf null zu
setzen und Reihe, Spalte und ggf. Diagonalen minus Spieler zu setzen).
Ich vermute, letzteres wird nicht nur viel weniger Speicher brauchen,
sondern auch schneller sein.

Bei geschickter Programmierung eine tiny2313-Aufgabe.

von Logic (Gast)


Lesenswert?

Wuerded ihr fuer eine KI eher den Minimax oder den Alpha Beta
Algorithmus verwenden

von Marco Genise (Gast)


Lesenswert?

Der AlphaBeta ist dem Minimax vorzuzuiehen, da AlphaBeta den Suchbaum
und somit die gesamte Rechenzeit/Platzbedarf deutlich reduziert.
Letztendlich ist ja AlphaBeta recht ähnlich dem Minimax, bis auf die
Tatsache, dass bei AlphaBeta "schlechte" Teilbäume erst garnicht
weiter betrachtet werden, während Minimax stur weitermacht. Die daruch
erzielten Cut-Offs machen den Gewschwindigkeits und Platzvorteil von
AlphaBeta aus.
Ausserdem lässt sich AlphaBeta durch PV & Zugsortierung deutlich
verbessern, was allerdings bei 4 Gewinnt denke ich nicht soooo
ausschlaggebend sein wird.
Wichtig ist bei beiden Algorithmen schnelle und schlanke Routinen für
die Feldberechnung sowie die Stellungsbewertung zu haben, da gerade
diese doch recht häufig aufgerufen werden.

Ansonsten schau mal in die Wikipedia unter diesen beiden Algorithmen -
dort finden sich recht detaillierte Informationen zu beiden sowie auch
ein Perfomancevergleich.

Grüße,

Marco.

von Logic (Gast)


Lesenswert?

Kann ich sowas in Bascom realisieren

von Philipp S. (philipp)


Lesenswert?

Wie soll man sich denn da AlphaBeta vorstellen? Schließlich gibt es
keine Bewertungen, sondern nur "gewonnen" oder "nicht gewonnen". Es
geht doch nur um TicTacToe!

Und natürlich geht das in Bascom.

von Marco Genise (Gast)


Lesenswert?

Bei TicTacToe macht AlphaBeta sicherlich wenig Sinn, da man den gesamten
Spielbaum auch mit Minimax relativ schnell durchrechnen kann. Trotzdem
lässt sich AlphaBeta hier anwenden!

Und klar kann man AlphaBeta auch in Bascom umsetzen :)

von LogicX (Gast)


Lesenswert?

Hat sowas schonmal jemand in Bascom gemacht?
Ich habe schon einige Pseudocodes über Google in verschiedenen pdf
files gefunden. Aber ich komme irgendwie nicht dahinter. Wie ich das
dann anstellen soll in zusammenhang mit meiner LED Matrix bzw.
Tastaturmatrix.

von Marco G. (kaffeedoktor)


Lesenswert?

Naja, die Darstellung ist doch total unabhängig vom Algorithmus.
Ausserdem sollte Dir der Pseudocode doch im Prinzip genug verraten um
eine Implementierung in der von Dir vorgesehenen Programmiersprache
machen zu können.

Versuch doch erstmal zu verstehen was MiniMax macht, wie es
funktioniert, wie der Spielbaum aufgebaut und verwendet wird. Dann
erschliesst sich auch relativ schnell die Bedeutung der
Bewertungsfunktion. Hast Du das Prinzip verstanden, dann ist es auch
einfach die mit AlphaBeta eingeführte Verbesserung zu verstehen.
Wenn Du dann den Alogrithmus verstanden hast, sollte es auch kein
Problem sein dass entsprechend umzusetzen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.