Wie ein krosmarc in diesen Kommentar bemerkt hat, werden die Spiele zweier KIs, die eine ähnliche Taktik haben, meistens unentschieden ausgehen. Oft ist es dann nur davon abhängig, welche Steine von oben nachrutschen, die dann über Sieg oder Niederlage einer KI entscheiden.

Das bedeutet, dass es neben der bisherigen Wertung eine zusätzliche Wertung geben muss. Die aktuelle Wertung wird folgendermaßen berechnet:

1. Jede KI muss gegen jede andere KI auf 100 Wettbewerbsfeldern antreten. Dabei fängt einmal KI 1, danach KI 2 auf dem gleichen Feld an.
2. Gewinnt eine KI beide Spiele, zählt dies als Sieg, verliert sie beide, zählt es als Niederlage und gewinnt einmal KI 1, danach KI 2 (oder umgekehrt), ist das Spiel unentschieden.
3. Für jeden Sieg einer KI gibt es 3 Punkte, für jedes Unentschieden einen Punkt.
4. Spiele gegen sich selbst (die ja normalerweise in 100 Unentschieden enden), werden nicht gewertet.

Wenn zwei KIs gleich stark sind, ist oft die Ausführungszeit (vor allem für mich als Wettbewerbsleiter) wichtig. Aus diesem Grund soll diese auch mit eine Rolle spielen. Schnelle Programme werden also belohnt, langsame Berechnungen etwas bestraft. Da natürlich die verwendete Programmiersprache auch wichtig ist, soll die Wertung so moderat vorgenommen werden, dass keinem Programmierer in einer bestimmten Sprache ein Nachteil entsteht.

Aus diesem Grund soll folgendes Verfahren angewendet werden (n = Anzahl der KIs):

1. Für jede KI wird aus der Zeit, die sie gegen die anderen KIs gespielt hat, der Mittelwert M_i berechnet, i=1,...,n.
2. Von den Mittelwerten M_1 bis M_n wird die Standardabweichung wieder der Mittelwert S berechnet.
3. Daraus wird ein Wert R = ROUND((S-M_i)/10) berechnet. Die Teilung durch 10 soll dabei für eine annähernde Gleichberechtigung verschiedenen Sprachen sorgen.
4. Dieser Wert R wird zur erreichten Punktzahl addiert.

Auf diese Weise werden schnelle KIs etwas bevorzugt und langsame KIs etwas benachteiligt. Aber nur in so einem Maße, dass es das eigentliche Ergebnis (KI spielt gut oder schlecht, siehe oben, denn dies ist vorrangig von Bedeutung) nicht zu sehr verfälscht.

Wenn jemand eine bessere Idee für eine faire Wertung der Laufzeit hat, soll er sich bitte melden. Irgendeine Abstufung sollte es aber geben, um die Programmierer, die einen Algorithmus besser umgesetzt haben als andere, zu belohnen.

Update 18.04.2009: Kleine Änderungen an der Spielmechanik, was die Bewertung betrifft, wenn eine KI illegale Züge zurück gibt oder gar nicht mehr reagiert.

Update 17.04.2009: Neue FAQ-Einträge 22 - 25.

Update 12.04.2009: Neue FAQ-Einträge und neue Version mit DEBUG-Schalter.

Update 11.04.2009 (Teil 2): Es gab in der Spielmechanik noch einen recht großen Bug, der in der neuen Version ausgebessert wurde.

Update 11.04.2009: Es gibt eine neue Version mit kleinen Ausgabeverbesserungen.

Seit dem Start des Programmierwettbewerbs sind ein paar Fragen bei uns eingegangen, die wir hiermit auch für alle anderen Leser beantworten wollen.

1. Wenn ein Spieler drei oder mehr Steine entfernt und es rutschen neue Steine nach, die zufällig
   zusammenpassen, werden diese dann ebenfalls dem Spieler angerechnet?
   Ja, nachrutschende passende Steine werden ebenfalls dem Spieler angerechnet, der für diese Kaskade zuständig war.
   Dies erklärt auch, wieso Spieler 1 bei der Referenz-KI beim ersten Zug von Spieler 2 plötzlich nur noch 4 Schildpunkte hat.
2. Wohin muss ich meine Implementierung schicken?
   Bitte schicken Sie diese per E-Mail an die Redaktion.
3. Wird die Gültigkeit einer Implementierung vor dem eigentlichen Wettbewerb geprüft?
   Der Wettbewerb selbst ist fortlaufend und startet nicht erst nach Abgabeschluss. In der Zeit wird natürlich geprüft, ob die Implementierung korrekt funktioniert und gegebenenfalls Rückmeldung an den Autor gegeben. Es werden aber keine Hinweise gegeben, ob eine andere KI besser oder schlechter ist.
4. Gibt es eine Webseite für den Wettbewerb, wo man die Regeln nochmal nachlesen kann? Oder vielleicht ein Forum oder ein Wiki zum Diskutieren?
   Die Webseite findet man unter diesem Link. Ein Forum oder Wiki wird hierfür aber nicht eringerichtet, da der Aufwand zu hoch ist.
5. Ich glaube, ich habe einen kleinen Fehler in Eurer Schnittstellenspezifikation aufgetan.
   In der Tat ist beim Herausschreiben der Spielerinformationen player.dat ein Dreher aufgetreten, sodass die Zeilen für gelbe und grüne Steine vertauscht wurden.
6. Steht während des Spiels die spiefeld.dat mit den 10000 Zeilen zur Verfügung bzw. darf die KI sie lesen?
   Nein, es stehen nur die kleinen 10x10-Spielfelder zur Verfügung.
7. Kann es passieren, dass man ein Spielfeld (10x10) vorgesetzt bekommt, bei dem es keine gültige Tauschmöglichkeit gibt?
   Theoretisch ja. Es wird inzwischen aber nach jedem Zug überprüft, ob es noch tauschbare Steine gibt. Falls nicht, werden die untersten Zeilen so lange entfernt, bis wieder ein spielbares Feld entsteht.
8. Kann es passieren, dass zwei KIs solange spielen, dass die nachrückenden 9900 Zeilen des vorberechneten Spielfeldes nicht ausreichen?
   Ja, das kann passieren. In dem Fall bricht das Spiel ab und der Sieger wird danach gekürt, wer noch die meisten Lebenspunkte übrig hat.
9. Die Gamelogik ruft ja fm-ai1.bin und fm-ai2.bin auf. Können das auch Shell-Skripte sein, die dann die eigentliche KI in Sprache XYZ aufrufen?
   Selbstverständlich. Ein Skript für die Referenz-KI kann zum Beispiel so aussehen:
   
#!/bin/bash
fm-ai/fm-ai.bin
exit $?

   und wird als fm-ai1.bin abgespeichert. Die Ausführrechte (mit chmod +x fm-ai1.bin) natürlich nicht vergessen!
10. Darf eine KI die gegnerische KI austauschen oder das Spielfeld verändern?
    Nein, dies wäre kein faires Vorgehen und wird von uns durch Schreibsperren zusätzlich unterbunden.
11. Gibt es eine Möglichkeit, manuell gegen eine KI zu spielen, um diese zu testen?
    Ja, hier hilft wieder ein kleines Bash-Skript:
    
#!/bin/bash
echo "Geben Sie die zu tauschenden Felder ein (der Art \"0 2 0 3\"):"
read EINGABE
echo $EINGABE > result.dat
exit $?

    Dieses speichert man dan dann z.B. direkt als zweite KI fm-ai2.bin ab und macht die Datei ausführbar.
    Daneben hat ein Leser eine GUI in Java programmiert, die man natürlich nutzen kann.
12. Was passiert, wenn die KI eine ungültige Tauschkombination abgibt?
    In dem Fall verliert derjenige Spieler fünf Lebens- bzw. Schildpunkte und ist nicht erneut an der Reihe.
13. Können pro Teilnehmer mehrere KIs in den Wettbewerb gehen?
    Nein, aber das eingereichte Programm kann mehrfach verbessert werden.
14. Wann ist Abgabeschluss?
    Am 10. Mai 2009. Sollte genügend Interesse bestehen, wird der Stichtag um zwei Wochen nach hinten verschoben.
15. Werden die KIs veröffentlicht?
    Ja, es werden alle KIs auf den Server hochgeladen und je nachdem wie viele es sind, auch alle vom jeweiligen Autor im Magazin kurz beschrieben.
16. Eine Fünfergruppe an Steinen gibt nicht automatisch einen weiteren Zug pro Runde wie bei Puzzle-Quest, oder?
    Nein, wir wollten das Spiel nicht zu komplex gestalten.
17. Wie gestaltet sich der Wettkampf? Erprobt Ihr die Skripte und Programme im KO-Verfahren?
    Nein, jede KI muss mit mehreren Beispielfeldern gegen alle anderen KIs antreten. Daraus wird ermittelt, wer die meisten Spiele gewonnen hat. Ein KO-Verfahren wäre zu selektiv.
18. Darf eine KI die jeweils andere ausführen?
    Nein, denn wenn beide KIs das machen, gibt es eine schöne Endlosschleife. Es ist aber natürlich erlaubt, aus dem vorherigen Zug des Gegners (Veränderung des Spielfeldes) dessen Taktik abzuleiten.
19. Ist "1. Runde gewonnen, 2. verloren" immer ein Unentschieden?
    Es ist noch nicht entschieden, ob ein Sieg/Niederlage-Spiel zu einem Unentschieden führt. Falls ja, ist auch noch nicht bestimmt, wie die Wertung dann aussehen wird.
20. Wenn man 16 rote Steine ergattert hat, wird Schaden verursacht und der Wert fällt auf 0 oder auf 1?
    Auf 1. Erhaltene Steine gehen nicht verloren.
21. Wie wird der eigentliche Wettbewerb gestartet?
    Hier helfen ein paar Bash-Befehle:
    
# Felder erstellen
for (( I=1; $I <= 100; I++ )); do ./fm-game.bin wettbewerbsfeld$I.dat create; sleep 2; done

# Felder abarbeiten
( date && ( for (( I=1; $I <= 100; I++ )); do ./fm-game.bin wettbewerbsfeld$I.dat; done ) && date ) > results

Das Datum wird eingepflegt, um später auch die Dauer eines kompletten Laufs über

egrep CEST results

auszugeben. (Subtrahieren der Zeiten muss man selbst.)
Um die results-Datei zu analysieren, hilft ein weiteres Bash-Skript:

#!/bin/bash
let LINECOUNTER=0
let S=0
let U=0
let N=0
for LINE in `egrep "dead" $1` ; do
    if [ $LINE == "1" -o $LINE == "2" ] ; then
        let LINECOUNTER=$LINECOUNTER+1
        let RESULT=$LINECOUNTER%2
        if [ $RESULT -eq 1 ] ; then
            let LOOSER=$LINE
        else
            if [ $LOOSER == $LINE -a $LOOSER == "1" ] ; then
                let N=$N+1
            elif [ $LOOSER == $LINE -a $LOOSER == "2" ] ; then
                let S=$S+1
            else
                let U=$U+1
            fi
        fi
    fi
done
echo $S " : " $U " : " $N

Dieses ruft man z.B. per ./check results auf.

22. Wenn ein Stein sowohl horizontal als auch vertikal in eine Dreierreihe bzw. -spalte passt, wird die Reihe oder die Spalte bevorzugt?
    Weder noch. Sowohl die Reihe als auch die Spalte werden gleichzeitig entfernt und gewertet. Das bedeutet, dass der Stein zweifach gewertet wird.
23. Darf eine KI eine Logdatei führen, um zu "erkennen", wie die gegnerische KI arbeitet?
    Gerne sogar. Solche selbstlernenden KIs sind im Wettbewerb sicher selten und sorgen für Abwechslung.
24. Wenn zwei KIs gegenseitig etwa gleich stark sind und nur Unentschieden spielen, werden dann andere Kämpfe zum Ermitteln der besseren KI genommen?
    Jede KI muss gegen jede andere KI antreten. Daraus werden Punkte für jedes gewonnene und unentschieden ausgegangene Spiel errechnet, die dann zu einer Abschlussplatzierung führen (siehe oben).
25. Gibt es nach dem Einsenden einer KI Hinweise, wie man gegen die anderen KIs abschneidet?
    Nein. Es wird nur das Spielergebnis auf den 100 Wettbewerbsfeldern gegen die Referenz-KI an den Autor weitergegeben. Natürlich wird aber auf Programmierfehler (falsche Züge etc.) hingewiesen.
26. Darf ein Zug der KI wirklich eine Minute brauchen?
    Nein, bitte nicht. Ein realistischer Maximalwert sind 20 Sekunden für ein ganzes Spiel. Das bedeutet, dass ein Wettbewerbslauf gegen eine andere KI circa eine Stunde dauert, was mehr als genug ist, schließlich soll auch noch gegen andere KIs gespielt werden.

Die oben gelisteten Fehler wurden in einer neuen Version der Spielmechanik behoben bzw. wurde durch neue Ausgaben während des Spiels für mehr Transparenz gesorgt. Die Dateien liegen wie bisher im FTP-Verzeichnis: Download per FTP oder per HTTP.

Bitte zögern Sie nicht, weitere Fragen zu stellen oder auf Fehler hinzuweisen, damit wir diese umgehend ausbessern können.

PS: Diese Nachricht wird ggf. im Laufe des Monats um weitere Einträge erweitert.

Heute ist die Aprilausgabe von freiesMagazin erschienen. Falls Sie hinter einer Firewall sitzen, die FTP nicht zulässt, ist das Magazin auch per HTTP-Zugriff auf das FTP-Verzeichnis zu erreichen.

Auch diesen Monat gibt es wieder eine HTML-Ausgabe für Mobilgeräte ohne Bilder und mit Bildern (ca. 1,4 MB). Unter der Adresse http://freiesmagazin.de/mobil/ finden Sie immer die aktuelle und alle bisher erschienenen Mobil-Ausgaben.

Inhalte der Ausgabe 04/2009 sind u.a.

• Openmoko - Free your phone
• gNewSense - Das freie Ubuntu
• Das Dateisystem ext4
• Ein Tuz für den Kernel
• Programmieren in KBasic - Eine kurze Einführung
• Datensammlung mit Tellico
• Kurztest: Etherpad
• Linux-Herstellerunterstützung: DVD-Brenner-Update
• Rezension: Coding for Fun - IT-Geschichte zum Nachprogrammieren
• Veranstaltungskalender, Leserbriefe und vieles mehr

Das vollständige Inhaltsverzeichnis finden Sie wie immer auf der Webseite der aktuellen Ausgabe. Leserbriefe mit Lob, Kritik, Anregungen oder Fragen können an die Redaktion geschickt werden.

Besonderes auf den Programmierwettbewerb wollen wir diesen Monat aufmerksam machen, bei dem es auch einen 25-Euro-Buchgutschein zu gewinnen gibt.

Wer jeden Monat an die neue Ausgabe erinnert werden will, kann auch den RSS-Feed abonnieren. Über den Tab Magazin können die letzten drei Ausgaben von freiesMagazin abgerufen werden, ältere Ausgaben finden Sie in unserem Archiv.

Die Auswertung der freiesMagazin-Umfrage letzten Monat hat gezeigt, dass sich sehr viele Leser Programmierthemen wünschen. Man kann (mit etwas gutem Willen) aus diesem Wunsch auch ablesen, dass es da draußen sehr viele (Hobby-)Programmierer gibt. Und gegebenenfalls gibt es sogar welche, die nach etwas Programmierarbeit lechzen. All diese wollen wir diesen Monat ansprechen -- und damit auch gleich alle Leser befriedigen. Als Ansporn gibt es auch eine Kleinigkeit zu gewinnen.

Die Programmieraufgabe ist prinzipiell sehr einfach gestrickt. Es geht darum, für ein sehr simples Zwei-Personen-Spiel die künstliche Intelligenz (KI), d.h. den computergesteuerten Spieler, zu erstellen. Diese soll nach Übergabe einiger Daten die (in den Augen des Programmierers) beste Zugmöglichkeit herausfinden. Auf diese Art spielen zwei künstliche Intelligenzen gegeneinander. Der Programmierer mit der besten, d.h. dominierensten KI (siehe unten für genaue Kriterien), gewinnt den Wettbewerb. Die Programmiersprache ist dabei dem Programmierer überlassen, nur unter einer freien Lizenz muss das Programm stehen.

Alle Details zur Aufgabe findet man auf einer eigenen Webseite.

Der Stichtag für das Wettbewerbsende ist der 10. Mai 2009. Bis dahin müssen alle Programme bei der Redaktion eingegangen sein. Sollte die Resonanz bis dahin extrem positiv ausfallen und wir mit Programmen überschüttet werden, gibt es vielleicht auch eine Verlängerung bis zum 24. Mai 2009. Der Sieger wird dann in der Juniausgabe von freiesMagazin mitgeteilt.

Wichtig: Jeder Teilnehmer darf nur ein Programm einreichen. Natürlich darf er aber seine KI bis zum Stichtag gerne mehrfach nachbessern.

Wie oben erwähnt gibt es als Ansporn auch eine Kleinigkeit zu gewinnen: einen Gutschein im Wert von 25 Euro für den Online-Handel Bookzilla.de. Es wurde sich für diesen Händler entschieden, da durch den Verkauf der Bücher 5% des Erlöses an die Free Software Foundation Europe gespendet werden. Diese Unterstützung Freier Software wollen wir natürlich auch unterstützen.

Wir wünschen allen Teilnehmern viel Erfolg und freuen uns über zahlreiche Programme, die dann zum Duell gegeneinander antreten.

Ihre freiesMagazin-Redaktion

Nachtrag: Auch wenn heute der 1. April ist, handelt es sich nicht um einen Aprilscherz.

Das Leben ist kein Wunschkonzert? Doch, ab und zu schon. In der freiesMagazin-Umfrage von Januar 2009 haben wir danach gefragt, welche Themen im Magazin fehlen bzw. über welche Themen die Leser gerne mehr erfahren würden. Die Resonanz war überwältigend!

Da wir selbst kein festes Autorenteam haben, die die Themen übernehmen könnten, wir aber auch nicht wollen, dass die Ergebnisse in der Versenkung irgendeiner OpenOffice.org-Liste verschwinden, haben wir die Wünsche auf einer Webseite nach Themen geordnet veröffentlicht.

Wenn Sie also als Autor bei freiesMagazin tätig werden wollen und noch nicht genau wissen, worüber Sie etwas schreiben sollen, schauen Sie doch einmal in die Wunschliste. Vielleicht finden Sie ein Thema, was Sie interessiert.

Wir - und die Leser sicher auch - freuen uns über neue Artikel und neue Autoren.