© Shaiith/Shutterstock.com
Classic Games Reloaded –Teil 16

Neuronen spielen „Schiffe versenken“ (Teil 2)


Im zweiten Artikel über das klassische Pen-and-Paper-Spiel „Schiffe versenken“ werden wir die zuletzt erörterten Ansätze rund um das Thema künstliche Intelligenz noch ein wenig vertiefen und mit diesen Bausteinen einen würdigen Computergegner erschaffen, der zumindest einem Gelegenheitsspieler durchaus die Schweißperlen auf die Stirn treiben sollte.

Inwieweit Zwei-Personen-Spiele für den kurzweiligen Zeitvertreib mit Anbruch des Smartphonezeitalters an Bedeutung verloren haben, vermag ich offen gestanden nicht zu sagen, nichtsdestotrotz dürften die meisten von uns schon einmal die eine oder andere Partie „Schiffe versenken“ (engl. Bezeichnung: Battleship) gespielt haben.

Nun ja, zumindest aus dem Blickwinkel eines KI-Programmierers ist „Schiffe versenken“ nach wie vor ein durchaus faszinierendes Spiel, da es so ganz anders ist als Spiele wie beispielsweise Schach, bei denen wir die Spielstärke des KI-Gegners mit zusätzlicher Rechenleistung im Prinzip beliebig steigern können. Lässt man einmal das Thema künstliche Intelligenz außen vor, so ist die Implementierung eines einfachen Battleship-Klons durchaus auch von einem passionierten Hobbyprogrammierer zu stemmen, sofern man auf imposante Soundeffekte verzichtet und sich beispielsweise auf die minimalistische grafische Aufmachung einer einfachen Win32-Konsolenanwendung (Abb. 1) beschränkt.

rudolph_battleships_1.tif_fmt1.jpg Abb. 1: Schiffe versenken (Screenshot)

In unseren Programmbeispielen umfasst das Spielraster gemäß Abbildung 2 so wie im Allgemeinen üblich zehn mal zehn Spielfeldkästchen (Tiles), auf denen die Spieler eine Flotte bestehend aus fünf Kriegsschiffen wahlweise horizontal oder vertikal platzieren müssen, wobei das Schlachtschiff fünf, der Kreuzer vier, die Fregatte zwei und die beiden Zerstörer jeweils drei aneinandergereihte Spielfeldkästchen beanspruchen. Dem einfachen Spielprinzip und den wenigen Regeln, die es zu befolgen gilt (beide Spieler dürfen abwechselnd das gegnerische Spielfeld bombardieren und im Falle eines Treffers ein weiteres Angriffsziel aufs Korn nehmen), ist es geschuldet, dass zumindest der Einstieg in die KI-Programmierung nicht übermäßig kompliziert ist und man sich praktisch von Anfang an auf das Wesentliche konzentrieren kann: Auf welche Spielfeldkästchen sollte man schießen, um die gegnerische Flotte mit so wenigen Fehlschüssen wie möglich zu versenken und wie vermeide ich es im Gegenzug, dass der Gegner meine eigenen Schiffe allzu schnell aufspüren kann?

rudolph_battleships_2.tif_fmt1.jpg Abb. 2: Schiffe versenken – Spielfeld

Im Rahmen des letzten Artikels sind wir zwar darauf zu sprechen gekommen, wie unnötige Fehlschüsse vermieden werden können und wie sich beschädigte Schiffe zielgerichtet zerstören lassen, doch es hat sich auch gezeigt, dass die Beantwortung dieser Fragestellungen alles andere als eine triviale Angelegenheit ist. Jeder einzelne Fehlschuss und jeder Treffer liefert der KI beständig neue Informationen, auf deren Grundlagen sich immer zuverlässigere Vorhersagen über die möglichen Positionen der feindlichen Kriegsschiffe treffen lassen. Zu Beginn eines neuen Spiels kann die KI bei der Zielauswahl allerdings lediglich auf statistische Überlegungen zurückgreifen, die besagen, dass die Wahrscheinlichkeit, dass sich im Zentrum des Spielfeldes ein feindliches Schiff verbirgt, aufgrund der großen Anzahl an Platzierungsmöglichkeiten am höchsten ist, wohingegen die Trefferwahrscheinlichkeit in den Spielfeldecken vergleichsweise klein ausfällt. Für eine KI ist es daher folgerichtig ein probates Mittel, ihre ersten Schüsse in unmittelbarer Nähe zum Spielfeldzentrum zu platzieren. Im Zuge der weiteren Zielauswahl müssen allerdings auch zusätzliche Informationen wie die Anzahl der einzelnen Fehlschüsse und Treffer sowie ihre jeweiligen Positionen berücksichtigt werden, da ein menschlicher Spieler den KI-Gegner ansonsten früher oder später austricksen würde, indem er seine Kriegsschiffe einfach vorzugsweise dort platziert, wo die KI sie (unter statistischen Gesichtspunkten) nicht vermutet: in der Nähe der Spielfeldränder.

Damit sich eine KI gegen einen menschlichen Spieler behaupten kann, muss sie die menschliche Natur zu einem gewissen Grad in ihre Entscheidungsfindung miteinbeziehen. Die Idee, dass ein Spieler seine eigenen Schiffe am Spielfeldrand platziert, basiert nicht auf irgendwelchen mathematischen Überlegungen, sondern soll den gegnerischen Spieler schlicht und einfach in die Irre führen. Und genau aus diesem Grund haben wir uns bereits im letzten Artikel so viele Gedanken über das Thema (menschliche) Platzierungsstrategien gemacht und genau aus diesem Grund werden wir das besagte Thema im Laufe des heutigen Artikels noch einmal vertiefen.

Klassische versus lernfähige künstliche Intelligenz

Eine lernfähige KI, der wir als Eingabewerte lediglich die Positionen der Fehlschüsse, der beschädigten Schiffsteile sowie die Positionen der bereits zerstörten Schiffe übergeben müssen und die uns als Ergebnis ihrer Berechnungen die Koordinaten des Spielfeldkästchens liefert, welches als Nächstes beschossen werden soll, wäre zweifelsohne der Hammer. Die Entwicklung einer solchen KI ist zumindest vom intellektuellen Standpunkt her eine überaus reizvolle Herausforderung. Aber würde sich eine solche KI überhaupt effektiv trainieren lassen? Vermutlich nicht. Und auch den Entwicklungsaufwand sollte man nicht unterschätzen.

Zunächst einmal benötigt jede lernfähige KI einen Lehrmeister. Und da der Mensch als Trainingspartner ausfällt (wer möchte schon Zigtausend Partien „Schiffe versenken“ gegen einen Computer spielen) benötigen wir als Alternative einen klassischen KI-Spieler, der ebenfalls über eine überdurchschnittlich hohe Spielstärke verfügt (und mit dessen Implementierung wir uns augenblicklich befassen). Auch wenn eine klassische KI nicht, bzw. nur eingeschränkt lernfähig ist, und damit irgendwie zum alten Eisen zu gehören scheint, orientiert man sich auch bei der Entwicklung eines solchen Systems in erster Linie am menschlichen Lernprozess: Die allermeisten, die noch niemals eine Partie „Schiffe versenken“ gespielt haben, werden wahrscheinlich heutzutage zunächst einmal das Internet zurate ziehen und nach Kriterien suchen, die man bei der Auswahl seiner Angriffsziele wenn möglich berücksichtigen sollte. Als (klassische) KI-Programmierer müssen wir uns dann vereinfacht gesagt „nur noch“ damit auseinandersetzen, wie sich die besagten Handlungsanweisungen in eine mehr oder weniger große Anzahl von Programmroutinen übersetzen lassen.

Vorverarbeitung der Spieldaten

Die Tatsache, dass sich der Spielverlauf einer Partie „Schiffe versenken“ mit nur fünf einfachen Zahlenwerten samt den zugehörigen Koordinaten beschreiben lässt, klingt auf den ersten Blick eigentlich nach einer guten Nachricht:

static constexpr int32_t ConstGameBoard_Water = 0; static constexpr int32_t ConstGameBoard_WaterShot = 1; static constexpr int32_t ConstGameBoard_IntactElement = 2; static constexpr int32_t ConstGameBoard_DamagedElement = 3; static constexpr int32_t ConstGameBoard_DestroyedElement = 4;

Tatsächlich sind das jedoch, zumindest für eine KI, bereits viel zu viele Informationen, um die aktuelle Spielsituation effizient beurteilen zu können. Die Informationsflut, die im täglichen Leben auf uns einprasselt, ist natürlich ungleich größer, nichtsdestotrotz können wir den Trick, mit dem sich unser Gehirn dieser Situation entgegenstellt, selbstverständlich auch im Rahmen der KI-Programmierung gewinnbringend einsetzen: Im Vorfeld einer Entscheidungsfindung werden die hierfür irrelevanten Informationen einfach ausgeblendet. In der Regel handelt es sich hierbei um einen vollkommen autonom ablaufenden Prozess, in machen Situationen (beispielsweise bei einer Partie Schach oder eben „Schiffe versenken“) machen wir das allerdings auch ganz bewusst. Bei unserer KI verhält es sich nicht anders. Jede CNeuronV2-Instanz bewertet unterschiedliche Aspekte des Spielgeschehens und benötigt demzufolge nur einen Bruchteil der Informationen. In diesem Zusammenhang greifen wir zum Speichern der jeweiligen Teilinformationen auf die nachfolgend genannten Arrays zurück:

static float GameBoardData_DestroyedElements[10][10]; static float GameBoardData_WaterShots[10][10]; static float GameBoardData_WaterShotsAndHits[10][10]; static float GameBoardData_WaterShotsAndDestroyedElements[10][10]; static float GameBoardData_DamagedElements[10][10];
  • Im GameBoardData_DestroyedElements-Array, mit dessen Daten wir nach zerstörten Schiffen in der direkten Nachbarschaft eines möglichen Angriffsziels Ausschau halten, wird für jedes zerstörte Schiffsteil ein Wert von 1.0f und in allen anderen Fällen ein Wert von 0.0f hinterlegt:

    Copy_DestroyedElementData(GameBoardData_DestroyedElements[0], GameBoardData[0], /*destroyedElementValue:*/ 1.0f);
  • Im GameBoardData_WaterShots-Array, auf dessen Daten wir zur Vermeidung von unnötigen Fehlschüssen zurückgreifen, wird für jeden Fehlschuss ein Wert von 1.0f und in allen übrigen Fällen ein Wert von 0.0f gespeichert:

    Copy_WaterShotData(GameBoardData_WaterShots[0], GameBoardData[0], /*watershotValue:*/ 1.0f);
  • Im GameBoardData_WaterShotsAndHits-Array, auf dessen Daten wir im Rahmen der Suche nach der vom Spieler verwendeten Platzierungsstrategie zurückgreifen, wird für jeden Fehlschuss ein Wert von -1.0f, für jeden Treffer (also für jedes beschädigte oder zerstörte Schiffsteil) ein Wert von 1.0f und in allen anderen Fällen ein Wert von 0.0f hinterlegt:

    Copy_WaterShotAndHitData(GameBoardData_WaterShotsAndHits[0], GameBoardData[0], /*watershotValue:*/ -1.0f, /*hitValue:*/ 1.0f);
  • Im GameBoardData_WaterShotsAndDestroyedElements-Array, auf dessen Daten wir bei der Suche nach den Spielfeldkästchen mit einer möglichst hohen Trefferwahrsch...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang