Vor ein paar Jahren habe ich als kleine Programmierübung an mich selber einen selbstlernen Tic-Tac-Toe-Automaten in Java geschrieben.
Der Code kann hier eingesehen werden.
Das damalige Experiment diente mir vor allem als genau das - als Experiment, dennoch konnte ich einige interessante Daten aus der Übung mitnehmen, die ich gerne, bei Interesse auch später teilen kann.
Aber genug von der Vergangenheit. Worum soll es hier heute gehen?

Revisit Tic-Tac-Toe

Ich möchte den damaligen Automaten jetzt in Go - mit frischem KnowHow - nachbauen und dabei das in den letzten Jahren gelernte auch weiter anwenden.
Dazu gehören Themen wie:

  • Test Driven Development
  • Domain Driven Design
  • Continuos Build und Deployment (sobald es etwas installierbares gibt)

Was möchte ich genau machen?
Ich möchte die “KI” gern in Go nachbauen und aus den daraus entwickelten Spiel-Strategien eine Implementierung des Spiels Tic-Tac-Toe mit hinreichend intelligenter KI online zur Verfügung stellen. Bis dahin ist aber noch ein langer Weg.

Starting the Process

Lasst uns also anfangen.
Heute würde ich gern kurz über mein grundlegendes SetUp gehen, bevor ich in einem zweiten, späteren, Beitrag die ersten Implementierungen vorstelle.

Das Setup
Als IDE nutze ich Visual Studio Code(VSCode) da es für meine Zwecke die größte Felxibilität liefert. Um auf meinem Basissystem nicht unnötig Installationen und Updates durchführen zu müssen, nutze ich die in VSCode integrierte Möglichkeit der Development-Container. DevContainer erlauben die Arbeit in isolierten kleinen Systemen, so genannten Container, die alle notwendigen Installationen bereits beinhalten. VSCode legt die notwendigen Informationen im Projekt-Verzeichnis in der Datei .devcontainer/devcontainer.json ab.
Die von mir initial genutzte Datei beinhaltet folgenden Inhalt:

{
	"name": "Go",
	"image": "mcr.microsoft.com/devcontainers/go:0-1.20-buster",
	"features": {
		"ghcr.io/devcontainers/features/docker-outside-of-docker:1": {}
	}
}

Ein Go-Projekt anzulegen ist recht einfach. Es muss lediglich in der Kommandozeile in neues Go-Modul erzeugt werden. De Befehl dazu lautet:

$ go mod init example.com/m

und legt eine Datei go.mod an. Golang speichert hier alle notwendigen Meta-Informationen des Projekts, wie Name, Abhängigkeiten, genutzte Go-Version usw.

Als dritte wichtige Datei für den initialen Aufbau ist die Definition der kontinuierlichen Build-, Test- und Release-Prozesse zu nennen.
Da ich das Projekt auf meinem GitLab-Server verwalten werden, werden diese Prozesse in der Datei .gitlab-ci.yml verwaltet.
Für den Anfang werden wir keine großen Prozesse benötigen, weshalb die Datei initial noch recht übersichtlich aussieht:

unit-test:
  image: 
    name: docker.io/golang #definiert welches Container-Image für den Job (unit-test) verwendet werden soll
  script: # definiert die einzelnen Konsolen-Aufrufe um die gewünschten Ergebnisse zu bekommen
  - go test -json ./... | go run github.com/jstemmer/go-junit-report/v2 > report.xml
  artifacts:
    when: always
    paths: 
    - report.xml
    reports: # speichert die Testergebnisse im GitLab
      junit: report.xml

Wie funktioniert die KI?

Die grundlegende Idee der Funktionalität habe ich in einem mittlerweile 5 Jahre alten Stand-up Maths Youtube-Video gesehen.
Im Grunde genommen werden alle möglichen Spielzustände in einer Datenbank gespeichert und die entsprechenden Züge, wenn das Spiel gewonnen bzw. verloren wurde, belohnt (bzw. bestraft).
Das Spiel wird dann einige Tausend mal wiederholt, indem die KI gegen sich selber spielt. Sie trainiert sich also selber.
Für Tic-Tac-Toe ist eine derartige Ablage der Daten recht überschaubar, da es insgesamt lediglich maximal 9! (362.880) mögliche Spielzustände gibt. Real sind es weniger Zustände, da ein Subset dieser bereits die Win-Condition erfüllt haben, bevor alle 9 Plätze belegt sind.

Der Spieler (die KI) ermittelt auf Basis der bisherigen Zugliste alle möglichen neuen Züge. Aufgrund vorheriger Spiele kann dann ein neuer Zug durch gewichtete zufällige Auswahl des nächsten Feldes ausgewählt werden - genaueres dazu später.

Ich hoffe das das Thema auf Interesse stößt und ich damit zum einen selber etwas lerne, aber vll. auch ein paar interessante Punkte weiterreichen kann.