Tictactoe

Tic Tac Toe ist ein klasse Spiel, das sich eignet, verschiedene spieltheoretische Ansätze für Spieleprogrammierung bis hin zur KI zu entwickeln:

1. Man kann Gedanken eines Einsteigers einfach codieren: Wenn die Situation so ist, dann ... . Sozusagen ein Baumdiagramm in eine Programmiersprache übersetzt. Machbar und auch gar nicht doof, weil mann einfache Dinge am Ende sehr gut hinkriegt. Aber wenn man von Anfang an optimal sein will, ist das schon a bisserl uferlos. Aber man kann sich ja wie ein Einsteiger verhalten: erst mal probieren (also random-Strategie), dann, wenn's absehbar wird hart programmieren.
2. Durch Abstraktion kann man ähnliche Situationen zusammenfassen: "Wenn er am Eck anfängt, dann reagiere immer so und so. Dadurch werden auch Anfangssituationen bewältigbar.
3. Durch Rekursion kann man "vom Ende her denken" und immer das tun was zu "einer Gewinnstellung" führt. Gewinnstellungen sind wiederum die Stellungen, die dem Gegner nur "Verluststellungen" hinterlassen. Zu Ende gedacht, gibt es nur Gewinn- und Verluststellungen. Also ..., einfach nur zu Ende denken! (brute force)
4. Rekursion arbeitet den kompletten Entscheidungsbaum top-down ab, das verursacht manchmal Speicherüberläufe. Sogenannte iterative Algorithmen arbeiten den Baum left-right ab. Dauert vielleicht, muss aber keine offenen Probleme auf "einem Stack" bereithalten.
5. Ist das alles durch Speicher- oder Rechenleistung bewältigbar, könnte man sich das alles auch "merken", "vorbereiten" und in einer "Erfahrungsdatenbank" vorhalten und abfragen.
6. Schließlich könnte ein Algorithmus auch durch Erfahrung lernen und "Erfahrung" aufheben. Ein Algorithmus, der macht, was sich in der Vergangenheit bewährt hat oder unterlässt, was schlecht war. Das geht schon in Richtung KI. Er lernt. Wie "wirklich intelligent" er ist, hängt natürlich davon ab, wie gut er ähnliche Situationen erkennt! Sonst ist es nur ein "on-the-fly"-Erstellen der obigen Datenbanken.

1. http://www.lepirate-rosenheim.de/privat/tictactoe/tictactoe1.html
2. http://www.lepirate-rosenheim.de/privat/tictactoe/tictactoe2.html
3. http://www.lepirate-rosenheim.de/privat/tictactoe/tictactoe3.html
4. http://www.lepirate-rosenheim.de/privat/tictactoe/tictactoe4.html
5. http://www.lepirate-rosenheim.de/privat/tictactoe/tictactoe5.html