Fragen und Antworten zum Programmierwettbewerb

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
  22. # 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.

  23. 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.
  24. 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.
  25. 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).
  26. 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.
  27. 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.

noch ein paar Kleinigkeiten

Hallo zusammen,

mir sind noch zwei kleine Fragen gekommen:

1) Darf eine KI fm-ai1.bin bzw. fm-ai2.bin ausführen?

2) Hat Spieler 1 gewonnen, wenn er im ersten Durchgang gewinnt, dabei noch 30 Lebens- und 10 Schildpunkte hatte und im zweiten Durchgang dann Spieler 2 gewinnt, allerdings nur noch 10 Lebens- und 2 Schildpunkte übrig hatte? Oder kürzer: Ist "1. Runde gewonnen, 2. verloren" immer ein Unentschieden?"

Meine Wenigkeit wäre dafür, dass es in diesen Fällen unentschieden wird. Allerdings ist ein Unentschieden (fast) genauso schlecht wie ein Verlust, immerhin wird der Gesamtsieger durch die Anzahl der Siege ermittelt.

Vorschlag: Das ganze läuft wie beim Fußball ab: Sieg: 3 Punkte, Remis 1 Punkt und Verlust 0 Punkte. Von mir aus auch 2 für den Sieg, das soll mir noch egal sein. Bei Gleichstand zählt eben der direkte Vergleich, notfalls wird ein Entscheidungsspiel gespielt.

Grüße, Keba.

Beantwortung der Fragen

Ich habe die Fragen oben in die FAQ eingefügt und dort beantwortet.

Zur zweiten Fragen etwas genauer: Aktuell teste ich anhand 100 Wettbewerbsfelder wie sich KI1 gegen KI2 schlägt. Dies sind insgesamt 100 Felder a 2 Runden = 200 Spiele. Von diesen 200 wird ermittelt, wie viele Spiele welche KI gewonnen hat. Die Idee mit dem Unentschieden ist nicht schlecht, über die Wertung bin ich mir aber noch nicht im klaren. Ggf. werde ich die Zwei-Punkte- oder Drei-Punkte-Regel in Betracht ziehen. (Unter Umständen ist das aber sogar egal.)

Viele Grüße

Dominik Wagenführ
freiesMagazin-Redaktion

2 weitere Fragen

Hallo

Meine ersten Botentwürfe kämpfen schon untereinander und erzeugen fleißig Statistiken. Dabei kamen mir ein paar Fragen:

1. Darf ein Bot eine Logdatei führen (auch über mehrere Kämpfe hinweg) um zu "erkennen" wie der gegnerische Bot tickt? Wie dieses Erkennen aussieht weiß ich noch selbst nicht :)

2. Wenn zwei Bots sich gegenseitig nicht packen und ungefähr 50:50 als Ergebnis kommt, werden dann andere Botkämpfe zum Ermitteln des besseren Bots hergenommen? Z.B. erscheint es mir bei 49 vs. 51 Siege so das die zwei Bots gleich gut sind (die nachrückenden Spielsteine sind hier eher entscheidend als die Bots an sich). Momentan vergleiche ich dann immer die Ergebnisse von beiden Bots gegen einen dritten Bot (der ersten Entwicklungsstufe) und erkläre den zum Sieger der hier eindeutig vorne lag.

Ich frage deswegen, da ich immer mehr merke je komplizierter die Auswertelogik jedes Spielzuges wird, desto besser werden die Bots gegen die der "ersten Generation", aber gegen Bots ein oder zwei Entwicklungsstufen vorher tut sich nix und es kommt beinahe immer ein Unentschieden heraus. Wenn also jeder Bot ideale Züge abgibt entscheidet nur der Zufall über den Gewinner. Bei simpleren Spielen wie Tic-Tac-Toe sorgen ideale Spielzüge ja dafür das kein Spieler gewinnen kann.

Ich befürchte je mehr Bots sich bei diesem Spiel ideale Züge ausrechnen, desto mehr Unentschieden resultieren schließlich. Ohne ein anderes Kriterium wie: Mehr Siege gegen einen relativ "dummen" Referenzbot, finde ich keine Sieger mehr nach den Kämpfen.

2 weitere Antworten

zu 1. Gerne. Das wird sicher interessant und die KI kann sich vielleicht auch an eine gute Position setzen, wenn sie weiß, was der Gegner treibt.

zu 2. 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). Ich werde wohl tatsächlich das aktuelle Wertungssystem des DFB nutzen, also 3 Punkte für einen Sieg und 1 für ein Unentschieden. Sollten zwei KIs dann immer noch gleich platziert sein in der Tabelle, muss ich mir noch eine Wertung überlegen. Dann spielt vielleicht noch die Höhe des Sieges (also wie viele Lebenspunkte noch übrig sind) eine Rolle.

> Wenn also jeder Bot ideale Züge abgibt entscheidet nur der Zufall über den Gewinner.

Das ist in der Tat so, da das Spiel eben eine Zufallskomponente besitzt. Dadurch, dass aber alle Spiele (auch gegen andere KIs) in die Abschlusswertung einfließen, ist das nicht ganz so tragisch.

> Ich befürchte je mehr Bots sich bei diesem Spiel ideale Züge ausrechnen, desto mehr Unentschieden resultieren schließlich.

Wir haben bisher nicht viele Einsendungen (zwei Stück plus zusätzlich vier KIs von mir, um die Stärke der anderen zu testen), insgesamt sind die Ergebnisse aber sehr durchwachsen. Ich denke, dass es auch nicht immer so sein wird, dass wenn KI 1 gegen KI 2 gewinnt und KI 2 gegen KI 3, dass dann auch KI 1 gegen KI 3 gewinnt. Vielleicht verliert sie ja, weil die Taktik eine ganze andere ist.

Ich habe beide Fragen oben in Kurzform in die FAQ eingefügt.

Ich bin gespannt auf Ihre Einsendung

Dominik Wagenführ
freiesMagazin-Redaktion

krosmarc schrieb: Ich frage

krosmarc schrieb:
Ich frage deswegen, da ich immer mehr merke je komplizierter die Auswertelogik jedes Spielzuges wird, desto besser werden die Bots gegen die der "ersten Generation", aber gegen Bots ein oder zwei Entwicklungsstufen vorher tut sich nix und es kommt beinahe immer ein Unentschieden heraus. Wenn also jeder Bot ideale Züge abgibt entscheidet nur der Zufall über den Gewinner. Bei simpleren Spielen wie Tic-Tac-Toe sorgen ideale Spielzüge ja dafür das kein Spieler gewinnen kann.

Sehr schön, zu dem gleichen Ergebnis bin ich auch gekommen. Das Verhältnis von Codezeilen für die Umsetzung eines neuen Verhaltens zur Gewinnchance zur jeweiligen Vorgänger-AI wird mit zunehmender Versionsnummer ungünstiger.

Sehr interessant das alles.

Frage zum Tausch von Steinen

Hallo,

ich hab mich einmal an dem Spiel versucht. Allerdings ist mir noch nicht klar wann ein Zug illegal ist.

Hier ein Beispiel, Ich möchte die Bombe5 (Feld 9,6) mit B (Feld 9,7)
Player's 2 turn!
| 0 1 2 3 4 5 6 7 8 9
--+--------------------
9 | B Y L 2 Y B R L 4 G
8 | R B Y Y R Y L G Y Y
7 | Y G L B 5 R Y R 3 B
6 | G Y G G B B L B 3 5
5 | G R L Y L G R R L Y
4 | B R 2 Y L Y G L L R
3 | G L B R G L L R B L
2 | R G R L Y B 3 B R L
1 | B L G Y L G R Y G R
0 | Y L Y G G 5 L Y L Y

Game::doStart() info: swap 9 6 with 9 7
Game::doStart() Illegal move: loose 5 life

Warum ist der Zug verboten?

Gruß,
Marten

Re: Illegaler Zug

Weil durch den Tausch keine drei oder mehr gleichen Steine zusammengefügt wurden. 1 8 mit 1 9 wäre z.B. legal, weil man dann in Zeile 8 eine Y-Reihe erstellt.

Dominik Wagenführ
freiesMagazin-Redaktion

Waagerecht, Senkrecht, Diagonal

Dürfen die Spielsteine nur Waagerecht und Senkrecht getauscht werden, oder ist auch ein
Diagonaler Tausch erlaubt?

mfg

Nicht diagonal

Es ist nur ein Tausch waagerecht und senkrecht erlaubt.

Viele Grüße

Dominik Wagenführ
freiesMagazin-Redaktion