Licht am Ende des Quoridors

Manchmal sieht man den Ausgang vor lauter Wänden nicht … oder etwa doch? Im letzten Programmierwettbewerb der dotnetpro wurde Taktikern und kühnen Planern die Aufgabe gestellt, eine KI zu entwickeln.

Diese KI sollte in der Lage sein, dass Brettspiel Quoridor gegen andere Computergegner zu spielen und natürlich im Idealfall auch gegen alle anderen Teilnehmer zu gewinnen. Insgesamt sieben kühne Strategen waren letztendlich angetreten, um sich den Sieg zu sichern.

Um zu ermitteln, wer sich denn nun den Titel des besten Quoridor Bots auf die Fahnen schreiben darf, traten alle Kontrahenten jeweils gegeneinander an. Dabei mussten sie je einmal mit der unteren und einmal mit der oberen Startposition zurechtkommen. Bei sieben Teilnehmern ergaben sich also insgesamt 42 Spielpaarungen, die in Bild 1 visualisiert sind. In dieser Matrix kann man auch gleichzeitig sehen, wer das entsprechende Spiel gewonnen hat und warum. Die Spielbedingungen waren die gleichen wie in der Testumgebung PlayerVsBot: 60 Sekunden maximale Denkzeit und ein Spielabbruch nach 100 Zügen eines Bots.

Folgende Gründe für einen Sieg waren möglich:

Interessehalber wurden während des laufenden Turniers neben den Siegen und Niederlagen der Teilnehmer noch verschiedene Statistiken mitgeloggt. Diese sind in Tabelle 1 und Tabelle 2 zusammengefasst. Interessanterweise haben nicht alle Bots die maximal erlaubte Zugzeit ausgenutzt, um sich beispielsweise möglichst lange einen Spielbaum mit potenziell vorteilhaften Zügen zu errechnen. Die schnellste KI hatte hierbei eine mittlere Zugzeit von gerade einmal 0,002 Sekunden. Das andere Extrem dagegen war eine mittlere Zugzeit von 59,51 Sekunden.

Auch bei der Zuganzahl der verschiedenen Bots fanden sich große Unterschiede. So sind es knapp elf Züge Unterschied bei durchschnittlicher Zuganzahl bei siegreichen Spielen. Im ganzen Turnier wurden insgesamt 1963 Züge gespielt. Die letzten Kennzahlen, die noch mitprotokolliert wurden, verrieten etwas über den Einsatz der zu Verfügung stehenden Wände. Insgesamt wurden im Verlaufe des Wettkampfes 487 Wände platziert.

Doch genug der ganzen Statistiken und Theorie! Soweit man es nachvollziehen konnte, hielten sich alle Einsendungen an eine faire Spielweise. Kein Bot hat versucht, den gegnerischen Prozess zu beenden oder dem Gegner wertvolle Rechenzeit zu klauen.

Nachdem alle teilnehmenden Bots sich bis auf die letzte zu setzende Wall duelliert hatten, ergaben sich folgende Platzierungen (Tabelle 3): Den ersten Platz belegt der Bot QMinatorBotJochenBaier von Jochen Baier. Somit darf er sich über eine Freedev-Premium Lizenz für IncrediBuild freuen. IncrediBuild beschleunigt Builds, Testläufe, Paketierung und vieles mehr um das bis zu 30-Fache. An neuen Quoridor-Strategien darf fortan Lukas Slizik tüfteln, denn er sichert sich mit seinem virtuellen Strategen LukasBot den zweiten Platz und damit ein Quoridor Mini als Brettspiel. Den dritten Platz gewinnt Stefan Boos mit seinem nach ihm benannten Bot. Er erhält dafür ein Buch zum Thema Softwareentwicklung aus dem Fundus der Redaktion. Die Redaktion gratuliert den Gewinnern herzlich und sagt Danke für die tollen Einsendungen.

Im dotnetpro-Repository [1] des Contests findet sich jetzt eine logHistory.txt. In dieser Datei finden Sie alle Spiele des Turniers in Form von komprimierten Zeichenketten. Diese Strings können in den Replayviewer des OpenQuoridor Frameworks geladen werden. So können alle Interessierten noch einmal die Spiele nachverfolgen. Der Sourcecode des OpenQuoridor Frameworks lässt sich auch auf Github unter [2] finden. Die Autoren freuen sich, wenn sich der ein oder andere Teilnehmer dazu entschließen sollte, den entwickelten Bot per Pull Request in das Projekt mit einzubringen.