Der Vier Gewinnt Server zur iBuildings Challenge
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 😉
Habe jetzt von deinen KIs beginnend bei 1 bis 4 aufsteigend je ein Spiel gespielt und auf Anhieb gewonnen 🙂
alopix
27 Mrz 11 at 12:18
Bist der zweite heute der es geschafft hat gegen meine KI (den Spieler Michael Kliewe). 16 andere Spiele hat mein Script gewonnen.
Dann würde ich sagen ist deine nächste Aufgabe, selbst eine KI zu schreiben, die auch gegen alle 4 gewinnen kann 😉 Schnapp dir den Konsolen Client als Basis und leg los!
Michael Kliewe
27 Mrz 11 at 12:23
Ich find es interessant, aber das Frontend könnte moderner sein. 🙂
Oliver
27 Mrz 11 at 17:29
Ich habe es jetzt auch ein paar mal gegen Nummer 4 versucht und nur einmal gewonnen. Nicht schlecht.
Christian Kaps
27 Mrz 11 at 20:21
Wieso ist denn Dein Spieler immer der erste? Das erhöht die Gewinn Chance natürlich auch deutlich.
Kevin
28 Mrz 11 at 14:00
Hm, sorry – ich hab vorhin zig mal neu geladen und war immer Player 2. Jetzt hat es sich plötzlich geändert. Ich bin aber offensichtlich auch kein guter Vier Gewinnt Spieler – auch sorum verliere ich 😉
Kevin
28 Mrz 11 at 14:03
@Oliver: Ich bin kein Grafiker und bin froh, überhaupt ein paar Bilder gemacht bekommen zu haben. Wie ich ja schrieb, die API ist offen, ihr könnt gern eigene Frontends dafür bauen und auf eure Homepage einbauen oder so.
@Kevin: Es sollte 50/50 sein wer anfängt. Kannst auch mal in der History nachschauen, da ist er des öfteren zweiter.
Ich hoffe ihr arbeitet selbst schon an einer KI, die Chance das iPad zu gewinnen ist ja in allen 3 Kategorien gleich hoch (ich trete in 4+ an). Und wie man sieht ist mein Spieler nicht unschlagbar, da geht also noch was.
Michael Kliewe
28 Mrz 11 at 14:35
Hatte grade ein Match ohne Sieger gegen deine KI – da hat sich Micheal Kliewe einfach selbst zum Sieger ernannt o_O – sollte vielleicht noch gefixt werden 🙂
Quetsch
29 Mrz 11 at 11:25
„The Game is solved: White Wins“, Victor Allis http://www.connectfour.net/Files/connect4.pdf
Wenn man das implementiert sollte der Wettbewerb gewonnen sein – man spielt schließlich immer *perfekt* 😉
max
29 Mrz 11 at 15:51
@Quetsch: Du hast Recht, irgendwie erkennt mein Server die Unentschieden noch nicht korrekt.
Michael Kliewe
29 Mrz 11 at 22:37
@max: Das gilt nur für 7*6, für die Challenge ist allerdings eine KI gefragt die auch mit anderen Größen klarkommt 😉 Und so einfach dürfte die Umsetzung nicht werden denke ich.
Michael Kliewe
29 Mrz 11 at 22:51
[…] sitzt zwar alle gerade wahrscheinlich vor eurer neuen PHPStorm Version oder programmiert eine Vier-Gewinnt-KI, aber trotzdem gibt es hier einige neue Präsentationen. Vom 6. bis zum 11. März 2011 fand zum […]
Confoo 2011, die Mega Konferenz | PHP Gangsta - Der PHP Blog
30 Mrz 11 at 08:16
gewonnen xD
tjado
31 Mrz 11 at 17:20
@tjado Whao, wie hast du das denn gemacht, du hast ja 26 Mal in Folge gewonnen, ist das deine KI? Machst du auch mit bei der Challenge?
Michael Kliewe
31 Mrz 11 at 18:23
Jo ist meine KI. Hatte nur zwei Tage zeit, da ich erst durch deinen Blog Eintrag auf die Challenge aufmerksam geworden bin, aber eben knapp die Lösung abgeschickt 😀 Meine KI denkt und bewertet X Schritte im Voraus. Wie funktioniert deine?
tjado
31 Mrz 11 at 18:32
Interesante KI 🙂 man muss schon gut aufpassen.
Havyrl
4 Apr 11 at 15:30
Also „ich“ habe eben im 6×7 gegen die stärkste KI auf Anhieb gewonnen. Schreiben werd ich trotzdem keine eigene 😀
m0f
18 Apr 11 at 11:35
Sehr interessant.. Da würde ich gern mal den Source sehen. Wie lang bist du dran gesessen?
Viele Grüße,
Ahmet
Ahmet Topal
20 Jun 11 at 10:05
Hay
Nasti
20 Jul 11 at 20:02
[…] hat wieder eine Challenge veranstaltet, und ich habe wieder mitgemacht. Letztes Jahr galt es eine Vier-Gewinnt-Spieler-KI zu erstellen, diesmal ging es darum einen Notifier für den Continuous Testing Server Sismo von […]
iBuildings Challenge: Mein Sismo Notifier für C2DM | PHP Gangsta - Der PHP Blog mit Praxisbezug
6 Jun 12 at 00:37