PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Archive for the ‘Vier Gewinnt KI’ tag

Der Vier Gewinnt Server zur iBuildings Challenge

with 20 comments

ibuildings hat Anfang diesen Jahres einen Wettbewerb gestartet bei dem man ein möglichst gut spielendes Vier-Gewinnt PHP-Script erstellen soll. Der Einsendeschluss ist der 31.03.2011, ihr könnt also auch noch teilnehmen! Da ich auch eine KI erstellt habe (bin sehr gespannt auf das Ergebnis des Turniers) möchte ich hier meine kleine Vier-Gewinnt-Webseite vorstellen, die ich während der Umsetzung erstellt habe. Man kann hier gegen meinen Vier-Gewinnt-Server spielen, entweder auf der Webseite mit einem Javascript-Vier-Gewinnt-Frontend, oder aber mit einem PHP-Konsolen-Client.

Ihr könnt euch also auch an dieser Aufgabe probieren, eine KI in PHP zu erstellen, und dann gegen den Server anzutreten. Auf dem Server habe ich aktuell 4 Gegenspieler implementiert, die verschiedene Schwierigkeitsstufen haben:

  • Spieler 1: Rudi Random. Rudi wählt einfach per Zufall eine Spalte, die noch nicht voll ist, und wirft seinen Spielstein in die entsprechende Spalte. Dies entspricht der einfachsten Strategie, die auch bei der Challenge als Beispiel beigelegen hat.
  • Spieler 2: Philipp Percent. Philipp nutzt eine kleine Funktion, in der die mittleren Spalten eine höhere Wahrscheinlichkeit bekommen haben als die äußeren Spalten. So versucht er, zuerst Steine in der Mitte unterzubringen, und erst dann mit geringerer Wahrscheinlichkeit die äußeren zu belegen.
  • Spieler 3: Andi Avoid. Ähnlich Philipp Percent beruht die Strategie von Andi darauf, die innen liegenden Spalten bevorzugt zu belegen. Jedoch besitzt er die Fähigkeit, gegnerische Reihen aus 3 Spielsteinen zu erkennen und verhindert die Platzierung eines vierten Steins. Wenn er eine eigene Reihe aus 3 Steinen entdeckt, setzt er den 4. Stein und gewinnt.
  • Spieler 4: Michael Kliewe. Meine eingereichte Lösung zur ibuildings Challenge.

Die ersten drei Spieler haben offensichtliche Mängel und dienen dem leichten Aufwärmtraining. Gegen Spieler 4 habe ich erst wenige Spiele gewinnen können (als Mensch), mal sehen ob es jemand von euch mit der eigenen KI schafft.

Alle weiteren Informationen zur API usw. findet ihr auf der Webseite. Falls ihr einen weiteren Konsolenclient erstellt habt der schöner aussieht, oder einen besseres Javascript-Frontend gebaut habt, nur her damit, ich baue diese dann gern ein. Ihr könnt auch gern mein Git-Repository forken und dort den Konsolen-Client verbessern. Wer ein starkes Spielerscript erstellt hat kann mit den Code auch zukommen lassen, dann füge ich diesen als weiteren Gegenspieler zum Server hinzu.

Ich arbeite aktuell noch an einer Spieler-gegen-Spieler Variante, sodass ihr auch direkt gegeneinander spielen könnt. Das dauert aber wohl noch etwas. Auch würde ich noch gern eine Berechnung der ELO-Stärke aller Spieler einbauen, dazu müßte ich die Formeln aber erstmal verstehen 😉

Written by Michael Kliewe

März 27th, 2011 at 11:17 am