Wichtige Ankündigung zum Programmierwettwerb

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.

Bewertungssystem

Wie wäre es denn mit einer Art ELO system wie beim Schach. http://de.wikipedia.org/wiki/Elo-Zahl

Das würde den Algorithmus doch stärker in den Vordergrund rücken da so die Spiele gegen alle Bots eine genauere Bewertung bekommen.

KI auf Speed

Oh mei, da hab ich ja was losgetreten ^^
Meine erste eingereichte Version war ziemlich langsam und hat wohl jemanden erschreckt :D. Dafür was mein Bot alles zu berücksichtigen versuchte fand ich die Laufzeit noch ok.

Laufzeit war bisher ja kein Thema (da < 1Min äußerst großzügig war), zuverlässig und robust sollte jedes Spiel gewonnen werden.
Wenn jetzt die Zeit gewertet wird, denk ich fast drüber nach einiges wieder auszubauen... der Zufall spielt schließlich mehr rein als jede noch so verfeinerte Logik. Ein Bot mit schlechterer (da weniger berücksichtigt) Auswertelogik kann also im Endeffekt besser abschneiden.

Eine neue Herausforderung, der ich mich leider erst ab Sonntag wieder stellen kann. :(

Wird da ggf. der Einsendeschluß verlängert? Ich weiß nicht wieviele Leute jetzt schon losgelegt haben, und ob andere die Änderung der Anforderungen auch ein wenig aus dem Konzept bringt.

ELO etc.

Also, was ELO ist, habe ich - zumindest ansatzweise verstanden - aber ich weiß nicht, wie wir das auf den Wettbewerb anwenden könnten. Vor allem einen fairen Basiswert zu ermitteln wird schwer, denke ich.

Wenn es nur um die Wertung mit 1:0.5:0 geht, dann ist das - bis auf Skalierung - identisch zu 2:1:0 (2-Punkte-Regel). Bisher ergibt sich dadurch keinerlei Unterschied in der Reihenfolge. Auch ein Wechsel zu 2:0:-2 ergibt keine Änderung.

Und keine Sorge, krosmarc, die meisten sehr guten eingesandten Programme sind relativ langsam. Da nicht das Los entscheiden soll und 2 Punkte Unterschied bei der reinen Wertung (ohne Dauer) eher auf "schlechte" Spielfelder zurückzuführen sind, brauchen wir ein zusätzliches Kriterium.

Und aller Voraussicht wird der Einsendeschluss um zwei Wochen verlängert, ja.

Viele Grüße

Dominik Wagenführ
freiesMagazin-Redaktion