Künstliche Intelligenz für Reversi
Othello (oft Reversi genannt) ist ein 2-Spieler Brettspiel, bei dem die Spieler abwechselnd weiße und schwarze Steine auf ein 8x8 Felder großes Brett legen. Falls du das Spiel nicht kennst, lies dir die Regeln auf Wikipedia durch. In heutigen Spielen kann man meistens auch gegen einen Computergegner, eine sogenannte „KI“ (Künstliche Intelligenz) spielen. Diese soll nun Schritt für Schritt erstellt und verbessert werden.
Computer und das menschliche Gehirn haben unterschiedliche Stärken. Beschreibe in 2-3 Sätzen, in welchen Bereichen Computer dem Menschen überlegen sind und in welchen das menschliche Gehirn noch Vorteile hat.
Die KI soll nach dem sogenannten Minimax-Algorithmus aufgebaut werden. Dieser bewertet bis zu einer bestimmten Tiefe die Stellung nach allen möglichen Zügen und wählt bei eigenen Zügen den besten für sich (Maximum) und bei gegnerischen Zügen den besten für den Gegner (Minimum) aus. Unten siehst du ihn als Pseudocode. Markiere die Bestandteile der Rekursion und beschrifte sie mit den Fachbegriffen.
Die KI benötigt eine Methode mit der sie die aktuelle Stellung bewerten kann. Je besser die Stellung für die KI ist, desto höher soll der berechnete Wert sein.
Lade dir auf Github die Projektvorlage "Othello-BlueJ-Projekt" herunter und implementiere die Methode stellungBewerten(int[][] spielfeld). Teste deine Methode mit 2 Stellungen.
Was passiert, wenn man die ersten beiden Zeilen des minimax Algorithmus aus Teilaufgabe b) weglässt?
Vervollständige den Minimax-Algorithmus im Projekt. Die Klasse Spiel hat nützliche Funktionen, die du dabei verwenden kannst.
Spiele eine Runde gegen deine KI auf verschiedenen Rechentiefen. Bei welcher Tiefe kannst du sie noch besiegen?
Wie viele Züge muss die KI für eine Rechentiefe von 6, 7 und 8 Spielzügen (also 3-4 Runden) berechnen, wenn es ungefähr 8 Möglichkeiten pro Spielzug gibt? Wie lang braucht ein Computer dafür, wenn er pro Sekunde 1 Million Züge prüfen kann?
(optional) Im Moment zieht die KI in der gleichen Stellung jedes Mal den gleichen Zug. Baue einen Zufallsmechanismus ein, der das Verhalten ein wenig abwandelt.
(optional) Informiere dich über Strategien bei Othello und versuche damit die Methode stellungBewerten() zu verbessern, indem du beispielsweise die Wichtigkeit von den unterschiedlichen Feldern gewichtest.
Schreibe in dein Heft 2-3 Sachen, die du neu gelernt hast, oder bei denen du Schwierigkeiten hattest.