© Shaiith/ Shutterstock.com
Classic Games Reloaded, Teil 15

Neuronen spielen „Schiffe versenken“ (1)


In diesem sowie dem nächsten Artikel werden wir uns mit einem klassischen Pen-and-Paper-Spiel befassen, mit dem sich jeder von uns wahrscheinlich schon einmal die Zeit vertrieben hat. Da sich der Programmieraufwand bei einem Spiel wie „Schiffe versenken“ sowohl von der Grafik als auch von der Spielsteuerung her in Grenzen hält, werden wir unser Augenmerk auf die Implementierung der KI-Routinen richten und uns überlegen, wie wir unseren Computer in einen würdigen Gegenspieler verwandeln können.

Vor Anbruch des Smartphonezeitalters galt „Schiffe versenken“ (engl. Bezeichnung: Battleship) wahrscheinlich als eines der beliebtesten Zwei-Personen-Spiele für den kurzweiligen Zeitvertreib. Dank des überaus einfach gestrickten Spielprinzips müssen keine komplizierten Spielregeln erlernt werden und es kann praktisch von jetzt auf gleich losgehen – vorausgesetzt natürlich, dass man ein Blatt Papier und einen Stift zur Hand hat. Die Größe des Spielrasters und die Anzahl sowie Länge der zu platzierenden bzw. der zu zerstörenden Schiffe, können selbstverständlich nach eigenem Gusto festgelegt werden. In unseren Programmbeispielen umfasst das Spielraster gemäß Abbildung 1 zehn mal zehn Felder (Tiles, Kästchen), auf denen die Spieler eine Flotte bestehend aus fünf Kriegsschiffen wahlweise horizontal oder vertikal platzieren müssen. Dabei beanspruchen das Schlachtschiff fünf, der Kreuzer vier, die Fregatte zwei und die beiden Zerstörer jeweils drei aneinandergereihte Spielfeldkästchen.

rudolph_games_1.tif_fmt1.jpgAbb. 1: Schiffe versenken – das Spielfeld

In unseren Spieleprototypen greifen wir für die Handhabung der einzelnen Kriegsschiffe auf jeweils eine Instanz der in Listing 1 vorgestellten CNavalEntity-Klasse zurück.

Listing 1: Klasse für die Handhabung der Schiffe

class CNavalEntity { public:  /* Zusatzinformation für eine mögliche horizontale Platzierung: */ int32_t MaxHorizontalLeftPos = 0;  /* Zusatzinformation für eine mögliche verticale Platzierung: */ int32_t MaxVerticalUpperPos = 0; int32_t Length = 1; bool Destroyed = false; int32_t *pPartPosArray = nullptr; int32_t *pPartPosXArray = nullptr; int32_t *pPartPosYArray = nullptr; CNavalEntity(); ~CNavalEntity();  // Kopierkonstruktor löschen: CNavalEntity(const CNavalEntity &originalObject) = delete;  // Zuweisungsoperator löschen: CNavalEntity & operator=(const CNavalEntity &originalObject) = delete; void Initialize(int32_t length); bool Set_RandomPos(int32_t *pInOutGameBoardData, CRandomNumbersNN *pRandomNumbers); void Check_Destruction(int32_t *pInOutGameBoardData);  // für Testzwecke: void Copy_To_GameBoard(int32_t *pInOutGameBoardData); void Set_HorizontalPlacementPosition(int32_t ixleft, int32_t iy); void Set_VerticalPlacementPosition(int32_t ix, int32_t iyTop); void Copy_Data(float *pInOutDataMap, float intactElementValue = 1.0f); void Copy_Data(int32_t *pInOutDataMap, int32_t intactElementValue = 1); void Copy_Data_If_Destroyed(float *pInOutDataMap, float destroyedElementValue = 1.0f); void Copy_Data_If_Destroyed(int32_t *pInOutDataMap, int32_t destroyedElementValue = 1); void Add_Data(float *pInOutDataMap, float intactElementValue = 1.0f); void Add_Data(int32_t *pInOutDataMap, int32_t intactElementValue = 1); void Add_Data_If_Destroyed(float *pInOutDataMap, float destroyedElementValue = 1.0f); void Add_Data_If_Destroyed(int32_t *pInOutDataMap, int32_t destroyedElementValue = 1); };

Besonders erwähnenswert sind in diesem Zusammenhang die beiden Klassenmethoden Set_HorizontalPlacementPosition() sowie Set_VerticalPlacementPosition(), die bei der Platzierung der Spielerschiffe zum Einsatz kommen, die Methode Set_RandomPos(), die im Zuge der von der KI durchgeführten Schiffsplatzierung aufgerufen wird, und ferner die Methode Check_Destruction(), mit deren Hilfe sich feststellen lässt, ob ein Schiff bereits vollständig zerstört wurde (Treffer, versenkt!). Bei der Implementierung der zugehörigen Spielschleife müssen wir dieses Mal etwas anders vorgehen, als wir es von unseren letzten Spieleprojekten her gewohnt sind. Sofern auf imposante Soundeffekte verzichtet und sich auf eine minimalistische grafische Aufmachung beschränkt wird, lässt sich ein Spiel wie „Schiffe versenken“ zwar problemlos in Form einer einfachen Win32-Konsolenanwendung implementieren, da die Spielsteuerung jedoch mit Hilfe der Maus erfolgen soll, lagern wir die Abfrage der Mausnachrichten (Mauszeigerposition sowie gedrückte Tasten) in einen zweiten Thread aus und greifen hinsichtlich der Handhabung der einzelnen Threads der Einfachheit halber auf die OpenMP-Schnittstelle zurück, wie in Listing 2 zu sehen ist.

Listing 2: OpenMP-Schnittstelle

#pragma omp parallel num_threads(2) { do { if (KEYDOWN(VK_ESCAPE) == true) break; int32_t threadID = omp_get_thread_num(); /* [Implementierung der Thread-basierten Programmabläufe] */ } while (true); } /* end of #pragma omp parallel num_threads(2) */

Der Master-Thread (Hauptprogramm-Thread) ist für die Handhabung der kompletten Spielelogik sowie für die Visualisierung des Spielgeschehens verantwortlich:

if (threadID == 0) { // [Spiele-Logik sowie Visualisierung] }

Die Abfrage der Mausnachrichten (Mauszeigerposition sowie gedrückte Tasten) erfolgt innerhalb eines separaten Threads:

else if (threadID == 1) InputHandling.Check_For_Input();

Vorstellung der einzelnen Spieleprototypen

Damit sich die einzelnen Aspekte des Spielgeschehens besser nachvollziehen und weiterentwickeln lassen, habe ich zusätzlich zu dem in Abbildung 2 gezeigten eigentlichen Spiel (menschlicher Spieler gegen KI-Spieler) im Vorfeld noch eine Reihe weiterer Prototypen implementiert. Im Rahmen des ersten Spieleprototyps hat man als Spieler lediglich die Möglichkeit, seine Kriegsschiffe auf dem Spielfeld zu platzieren (linke Maustaste: horizontale Platzierung; rechte Maustaste: vertikale Platzierung; mittlere Maustaste: sämtliche Schiffsplatzierungen werden wieder rückgängig gemacht). Der zweite Prototyp stellt eine KI-Testanwendung dar, in der die KI sich zunächst um die Platzierung der einzelnen Kriegsschiffe kümmert und im Anschluss daran versucht, die zuvor platzierten Schiffe wieder aufzuspüren und zu zerstören. Im Unterschied dazu muss bei unserer dritten Testanwendung der menschliche Spieler versuchen, die von der KI platzierten Kriegsschiffe zu finden und zu versenken. Im Rahmen von Spieleprototyp Nr. 4 wird der Spieß schließlich umgedreht, denn hier muss die KI demonstrieren, wie gut sie die vom menschlichen Spieler platzierten Kriegsschiffe aufspüren und vernichten kann. Bei unserem fünften Prototyp handelt es sich bereits um ein eigenständiges Spiel: Im Zuge eines Wettkampfs zwischen Mensch und Maschine offenbart sich, wer die vom Computer platzierten Kriegsschiffe mit weniger Fehlschüssen auffinden und zerstören kann. Auch der in Abbildung 3 vorgestellte Spieleprototyp Nr. 6 stellt ein eigenständiges Spiel dar. Der menschliche und der KI-Spieler treten wechselweise gegeneinander an. Im ersten Teil der Partie muss der KI-Spieler die vom menschlichen Spieler platzierten Schiffe vernichten, und im zweiten Teil der Partie muss der menschliche Spieler die vom KI-Spieler platzierten Schiffe aufspüren und zerstören.

rudolph_games_2.tif_fmt1.jpgAbb. 2: Herkömmliches Spiel: Mensch gegen KI
rudolph_games_3.tif_fmt1.jpgAbb. 3: Zweigeteilt: Mensch und KI treten wechselweise gegeneinander an

Obwohl man es gemeinhin als ein solches betrachtet, handelt es sich bei dem Spiel „Schiffe versenken“ genau genommen überhaupt nicht um ein echtes Zwei-Personen-Spiel, da die Kriegsschiffe der beiden Kontrahenten überhaupt nicht miteinander interagieren. Nachdem der eine Spieler seine Schiffe platziert hat, kann er fortan nur noch dabei zuschauen, wie der andere Spieler bei der Suche und Zerstörung der zuvor platzierten Schiffe vorgeht. Es entsteht nur der Eindruck eines Zwei-Personen-Spiels, weil beide Spieler parallel zueinander zunächst ihre Kriegsschiffe platzieren und im Anschluss daran die gegnerische Flotte zu zerstören versuchen. Die Regel, dass man so lange feuern kann, bis ein Schuss schließlich mal daneben geht (Wassertreffer), soll zwar für ein wenig zusätzliche Spannung sorgen, ich persönlich würde aber aus Fairnessgründen auf ihre Anwendung verzichten. Im ungünstigsten Fall könnte Spieler 1 die Flotte von Spieler 2 versenken, bevor dieser seinerseits auch nur einen einzigen Schuss abfeuern durfte. Mit ein wenig zusätzlichem Aufwand kann das klassische „Schiffe versenken“ allerdings ruckzuck in ein waschechtes Zwei-Personen-Spiel umgestaltet werden. Beispielsweise könnte jedes Kriegsschiff einen von der Schiffsgröße abhängigen Munitionsvorrat bunkern. Wird im Verlauf einer Partie nun ein Schiffsteil durch einen gegnerischen Treffer beschädigt, verringert sich der Munitionsvorrat. Derjenige Spieler, der als erstes keine Munition mehr zur Verfügung hat und die gegnerische Flotte noch nicht vollständig versenken konnte, hat die Partie verloren. Der Nachteil bei diesem Spielprinzip ist allerdings auch hier wieder die übermäßig starke Gewichtung der Zufallskomponente. Derjenige Spieler, der mit etwas Glück die beiden größten gegnerischen Kriegsschiffe frühzeitig vernichtet, hat einen nicht zu unterschätzenden Vorteil, da sich der Gegner aufgrund seines beträchtlich dezimierten Munitionsvorrats nur noch eine geringe Zahl an Fehlschüssen leisten kann. Ich persönlich finde das Spielprinzip, das im Rahmen des fünften Prototyps demonstriert wird, am reizvollsten, da beide Spieler in jeder Partie stets über die gleichen Siegchancen verfügen. In der Pen-and-Paper-Variante würde man allerdings einen dritten Mitspieler oder einen Spielleiter benötigen, der für die Platzierung der Kriegsschiffe verantwortlich wäre.

Anforderungen an einen guten KI-Gegner

Eine einfache Routine, die ihre Angriffsziele nach dem Zufallsprinzip auswählt, ist zwar schnell implementiert, allerdings wird sich wohl kein Spieler mit einer solchen KI über einen längeren Zeitraum messen wollen. Es bedarf schon eines würdigeren KI-Gegners, damit der Spielspaß nicht bereits nach der ersten Partie unwiderruflich verloren geht. Verschaffen wir uns doch gleich einmal einen Überblick über die einzelnen Fähigkeiten, mit denen wir so eine fortschrittliche KI nach Möglichkeit ausstatten sollten:

  • Die KI sollte herausfinden können, ob der Gegner bei der Platzi...

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