Free-Hack Coding Contest - A New Begining

CONTEST BEENDET - AUSWERTUNG FOLGT

Lang ists her da gab es einen kleinen Jungen im Pijama - er hatte eine Vision von einem Coding Contest bei dem die Elite der Freifallholzfäller ehrenhaft um die goldene Axt des Ponnies zu kämpfen glaubten. Doch es kam alles anders als man es sich ausgemalt hatte. Der Kampf war heftig und ausgeglichen. Viele Unicode Chars fielen im sinnlosen Gemetzel um Semikolons und Funktionsdefinitionen. Gar der kleine Junge, der mitlerweile zu einem wahrhaften König aufgestiegen ist konnte sich die Erinnerungen nicht mehr aus seinem begrenzten Arbeitsspeicher entfernen - die Garbagecollectors waren einfach zu schwach für eine Erinnerung solchen Rings.
Viele Sekunden später wagte es jedoch ein extrem reaktionsträges Edelgas erneut zu einem Treffen der Giganten aufzurufen. Dieses mal sollten Zeichen geschont werden und ISO über alle wachen. So rufe ich also erneut zu einem Coding Contest auf, diesmal soll das Versprechen aber wahr sein, dass es bei reger Teilnahme weitere Schlachten geben werde.

So genug getrollt, jetzt kommen harte delikate Fakten, wie sie unser Nerdherz (aka Logik) liebt.

So nachdem ich mich nun nochmals mit Blackberry abgesprochen habe stehen die genauen Regeln des ganzen.

Welche Sprachen sind erlaubt
Alle Sprachen, die die Eingabe und Ausgabemethoden unterstützen (so ziemlich alle [sogar Ook!!!]).

Was wird gecodet
Diesmal ist die Aufgabe, einen möglichst intelligenten Tic Tac Toe (nein nicht die "Verpiss dich"-Band, sondern das Logikspiel) "Bot" zu programmieren.

Was muss beachtet werden
Um die Bots gegeneinander spielen zu lassen müssen sie alle das gleiche Format unterstützen, das später erklärt wird. Ausserdem sollten die Bots auf einigermassen moderater Hardware lauffähig sein. Es sind keine Teams erlaubt.

Wie wird bewertet
Die Bewertung wird nach einem normalen Tabellensystem gehandhabt. Jedes Programm tritt gegen jedes andere zehn Mal an. Bei fünf Runden hat Programm #1 den ersten Stein (erster Stein: X), die restlichen fünf Mal Programm #2. Wer am Schluss die meisten Siege hat gewinnt das Duell. Für den Sieger gibt es jeweils zwei Punkte, für den Verlierer 0. Gibt es ein Unentschieden gibt es für beide Parteien je einen Punkt. Falls ein Programm nicht korrekt funktioniert verliert es automatisch das Duell.
Die Quelltexte werden eingezogen, tragen aber nichts zur Bewertung bei.

Was bekommt/-en der/die Sieger
Vermutlich nur Ruhm und Ehre. Ausserdem natürlich die goldene Freifallholzfällerspezialextremaxt!

Wo gebe ich mein Programm ab
Per PN bei mir (krypt0n, der Fette Dude mit der Lightgun!). Pro Teilnehmer darf ein Programm abgegeben werden, bessere Versionen, die die alte ersetzen sind jedoch ausdrücklich erlaubt (so lange ihr es nicht übertreibt!).

Detailliertere Beschreibung des Problems
Euer Programm muss in der Lage sein pro Ausführung einen Zug in einem Tic Tac Toe Match auszuführen. Die Übergabe der aktuellen Spielsituation erfolgt per Commandline Argument (in vielen Sprachen argv genannt). Dieses ist folgendermassen aufgebaut:

Länge: neun ASCII Chars
Format: "_________" (ohne die Anführungs- und Schlusszeichen) dabei stehen die ersten drei ASCII Chars für die erste Reihe des Tic Tac Toe Felds, die zweiten drei für die zweite Reihe und die letzten drei für die dritte Spalte.
_ steht dabei für ein nicht besetztes Feld, X für ein vom ersten Programm besetztes Feld, O (ooh nicht null!) für ein vom zweiten Programm besetztes Feld.
Beispiel: "_X_OOX_X_" steht für folgendes Feld:

_ X _
O O X
_ X _

Ein leeres Feld wird demnach folgendermassen übergeben: "_________"
Die Eingabe kann als korrekt angenommen werden und muss nicht überprüft werden.
Das Programm muss als erstes feststellen, welcher Buchstabe am Zug ist und einen korrekten Zug für diesen Buchstaben ausführen. Danach muss das neue Spielfeld im gleichen Format wie die Eingabe, gefolgt von einem Zeilenvorschub (Windows Format: Carriage Return Line Feed ["\r\n", CRLF etc.]) ausgegeben werden. Ist ein unzulässiger Zug vollzogen worden, das Resultat im falschen Format etc. wird das Spiel forfait für das andere Programm gewertet.

Wie lange habe ich Zeit
Abgabetermin ist 1272232799 (aka Sonntag, der 25. April 2010 um 23:59:59)

Weiteres
Falls Fragen bestehen können diese hier in diesen Thread gepostet werden, ich und meine diabolischen Helfer werden euch aufklären.

Teilnehmer
... letzte Seite :D

falls zeit mit perl am start

Wenn Zeit, mit C bzw. C++ oder C# mit dabei.

MfG Interceptor

Zitat:

---

Zitat von Interceptor

Wenn Zeit, mit C bzw. C++ oder C# mit dabei.

MfG Interceptor

---

Wie oben gesagt, falls Zeit kommt VB.NET!

Gruß

Slawa

Diese WOche? und nächste? dann mit c# :D

Zitat:

---

Zitat von flensburg

Diese WOche? und nächste? dann mit c# :D

---

@flensburg, wir können auch was zuasmmen coden

So Regeln/Contestdetails mit BB abgesprochen.

Passt ja wunderbar, da ich mich gerade ausgiebig mit Bots beschäftige :)
Hört sich eigentlich nicht schwer an, mir gehen schon 1000 Ideen durch den Kopf..

Lg br00_pwn

Sicher, dass wir Gewinner haben werden?
Soweit ich weiß, kommt doch eh immer unentschieden raus, wenn die Bots gut sind ^^.
Aber ich bin dabei (wenn ich bis dahin Zeit finde) und wenn, dann werd ichs euch nicht leicht machen xD

Wie sieht das aus, bei zu viel Gleichständen, mit Bewertungskritiken wie Codelänge, Algorithmuseffektivität (vllt. 1mio. laufen lassen und Zeit messen) etc...?

Ansonsten: Ich bin mit C dabei!

Zitat:

---

Zitat von AlterHacker

Sicher, dass wir Gewinner haben werden?
Soweit ich weiß, kommt doch eh immer unentschieden raus, wenn die Bots gut sind ^^.
Aber ich bin dabei (wenn ich bis dahin Zeit finde) und wenn, dann werd ichs euch nicht leicht machen xD

---

Ich bin mir bewusst, dass Tic Tac Toe gerade für Bots extrem einfach ist. Aber da ich nicht weiss, wie das Codingniveau hier im Allgemeinen so ist habe ich mir gedacht, dass wir für den ersten Contest (der eigentlich der 2. ist) eine einfachere Aufgabe stellen. Wenn ihr Vorschläge für weitere habt könnt ihr mir die BTW immer mitteilen ;)

So und jetzt nochmals kurz zum Ablauf, da es scheinbar irgendwelche Unklarheiten gibt. Hier ein Beispiel für den Ablauf eines Matches:

Es treten an: Mein Programm pwner.exe und BlackBerries Programm rottenegs.exe

1. Spiel
Aufruf per CMD: "pwner.exe _________" Rückgabe: "____X____\r\n"
Aufruf per CMD: "rotteneggs.exe ____X____" Rückgabe: "___OX____\r\n"
Aufruf per CMD: "pwner.exe ___OX____" Rückgabe: "_X_OX____\r\n"
Aufruf per CMD: "rotteneggs.exe _X_OX____" Rückgabe: "_X_OXO___\r\n"
Aufruf per CMD: "pwner.exe _X_OXO___" Rückgabe: "_X_OXO_X_\r\n"
Gewinner: pwner.exe (mittlere Reihe horizontal)

2. Spiel
Ablauf wie das erste nur, dass dieses mal rotteneggs.exe als erstes aufgerufen wird und deshalb den Buchstaben X besitzt.

Das ganze wird dann noch vier Mal auf die gleiche Art durchgeführt, so dass beide Programme je fünf Mal anfangen durften (und deshalb den Buchstaben X hatten) und fünf mal den zweiten Zug durchführen durften (mit dem Buchstaben O).

Falls weitere Fragen sind diese einfach stellen.

Zitat:

---

Zitat von GregorSamsa

Wie sieht das aus, bei zu viel Gleichständen, mit Bewertungskritiken wie Codelänge, Algorithmuseffektivität (vllt. 1mio. laufen lassen und Zeit messen) etc...?

Ansonsten: Ich bin mit C dabei!

---

Das wollen wir aufgrund von Objektivität erstmal weglassen! Falls es wirklich nur Unentschieden geben sollte werden wir uns für nächstes mal ein einigermassen objektives Kriterium ausdenken, das auf alle Sprachen angewandt werden kann.

Bin eventuell dabei.

Ich bin mit Java dabei .
Ich fände ja Viergewinnt cooler :P
Vorallem gibt es da sicher nicht so viele Unentschieden.
MfG

Zitat:

---

Zitat von NSGR

Ich bin mit Java dabei .
Ich fände ja Viergewinnt cooler :P
Vorallem gibt es da sicher nicht so viele Unentschieden.
MfG

---

War anfangs auch eine Möglichkeit, jedoch wäre das wohl auf stupides Bruteforcing hinausgelaufen weil ein intelligenter Algorithmus viel schwieriger zu implementieren wäre.

So schauts aus ^^.
Wüsste jetzt gar nicht mal so einfach, wie man das machen soll. Oka Bot programmieren ist jetzt nicht so mein Spezialgebiet, aber ich glaub alleine bei XXO läufts schon auf 2.5k if-abfragen hinaus.

evtl auch dabei --> perl

Zitat:

---

Zitat von Hu5eL

evtl auch dabei --> perl

---

Wie man hier sieht, sind schon einge gute Programmiersprachen dabei, ich denke das wird was!

Gruß

Slawa

schade -.- bin da erst seit 3 tagen fertig mim abi, sonst wär ich dabei =(

Bin evtl. mit vb.net dabei

Zitat:

---

Das Programm muss als erstes feststellen, welcher Buchstabe am Zug ist

---

Wenn die Programme jedesmal neu aufgerufen werden, kann man bei einem Feld mit (Anzahl(Buchstabe ≠ "_") >1 )nicht mehr erkennen, wer dran ist ;)

Zitat:

---

Aufruf per CMD: "pwner.exe ___OX____" Rückgabe: "_X_OX____\r\n"

---

Code:

---

___
OX_
___

---

hier könne sowohl X wie O dran sein ;)

PS: da Scriptsprachen zugelassen sind: wie schaut es mit "benutzerdefinierten" Aufrufen aka "Interpreter script.x argument" ?

Zitat:

---

Zitat von EBFE

hier könne sowohl X wie O dran sein ;)

---

Schön mitgedacht :)
krypt0n hat aber definiert, dass X immer anfängt (siehe "X für ein vom ersten Programm besetztes Feld" im Spoiler).
Insofern weiß man also, dass jetzt wieder X dran wäre.

Pseudocode:
if (AnzahlX > AnzahlO)
// O am Zug
else
// X am Zug

Ok, dann wäre das ja erledigt (stand auch etwas versteckt im Text *sich ausred* ) :)

Zitat:

---

Zitat von EBFE

Wenn die Programme jedesmal neu aufgerufen werden, kann man bei einem Feld mit (Anzahl(Buchstabe ≠ "_") >1 )nicht mehr erkennen, wer dran ist ;)

---

Nein es beginnt immer X und dementsprechend kann O nie mehr Felder besetzen als X es tut.

Zitat:

---

Zitat von EBFE

PS: da Scriptsprachen zugelassen sind: wie schaut es mit "benutzerdefinierten" Aufrufen aka "Interpreter script.x argument" ?

---

Solange es einen Interpreter für Windows (eventuell auch Linux, muss aber noch schauen wie ich das mit den VB Heinis etc. regel) gibt, geht das klar. Ausgabe muss aber auch da passen.

wird nur Sieg oder Niederlage gewertet?
also spielt das Konzept keine rolle?

Zitat:

---

Zitat von Steiger_mp

wird nur Sieg oder Niederlage gewertet?
also spielt das Konzept keine rolle?

---

Bei den Leuten die bisher mitmachen, werden die Bots warscheinlich eh so gut sein, dass es nur unentschieden gibt. Wie dann ein Gewinner gefunden wird, ka.

Mfg

Zitat:

---

Zitat von AlterHacker

Sicher, dass wir Gewinner haben werden?
Soweit ich weiß, kommt doch eh immer unentschieden raus, wenn die Bots gut sind ^^.
Aber ich bin dabei (wenn ich bis dahin Zeit finde) und wenn, dann werd ichs euch nicht leicht machen xD

---

Macht keinen Unterschied ob Vier-Gewinnt oder Tic Tac Toe, beide zählen zu den gelösten spielen ;) Ein Tic Tac Toe spiel geht im Optimalfall halt Unentschieden und ein Vier Gewinnt Spiel zugunsten des Beginners aus.

Wenn es wirklich lauter Unentschieden geben wird könnte man zum jetztigen Zeitpunkt noch darüber diskutieren, ob man noch eine zusätzliche Regel einführen will, nach welchem Kriterium eventuelle Unentschieden gewertet werden. Dies ist jedoch sehr schwierig, weil so ziemlich alle Sprachen akzeptiert werden und darum ein einheitliches Kriterium sehr schwierig zu finden ist.
Einzige Möglichkeit wäre meines erachtens, dass Bruteforcing ganz verboten wird oder bei einem Unentschieden das Programm mit einem "intelligenten" Lösungsverfahren zwei Punkte anstatt einem bekommt.
Was sagt ihr dazu?

Zitat:

---

Zitat von $_staX

Macht keinen Unterschied ob Vier-Gewinnt oder Tic Tac Toe, beide zählen zu den gelösten spielen ;) Ein Tic Tac Toe spiel geht im Optimalfall halt Unentschieden und ein Vier Gewinnt Spiel zugunsten des Beginners aus.

---

Ja ok stimmt. Aber ich glaube bei Viergewinnt kann man nicht einfach nur mit dem Minimax arbeiten , sondern muss ihn erweitern . Mann kann auch Dame spielen :)

Zitat:

---

Zitat von krypt0n

Wenn es wirklich lauter Unentschieden geben wird könnte man zum jetztigen Zeitpunkt noch darüber diskutieren, ob man noch eine zusätzliche Regel einführen will, nach welchem Kriterium eventuelle Unentschieden gewertet werden. Dies ist jedoch sehr schwierig, weil so ziemlich alle Sprachen akzeptiert werden und darum ein einheitliches Kriterium sehr schwierig zu finden ist.
Einzige Möglichkeit wäre meines erachtens, dass Bruteforcing ganz verboten wird oder bei einem Unentschieden das Programm mit einem "intelligenten" Lösungsverfahren zwei Punkte anstatt einem bekommt.
Was sagt ihr dazu?

---

Nur, wie definierst du intelligent ? Fest einprogramierte Algos? Weil ein Bot, der dann wieder ein paar Möglichkeiten berechnet, wäre dann ja quasi ein Bruteforcer ^^.
Gibt ja nur 9! (58.980) mögliche Spielverläufe, die man dann im ersten Zug berücksichtigen könnte. Theoretisch gibt es für den ersten Zug ja nur 3 Felder, der rest wiederholt sich(drehung um 90°)
XX_
_X_
___
Also ist quasi ein "Bruteforce" Ding ~= ein inteligentes Tool.
&& Wenn die 'Algos' fest drinne sind, dann ist es ja auch nicht mehr so das intelligente Prog, sondern nur der Algo ^^.

Das ist ja das Problem des Ganzen, darum wird erstmal sicher nach Punkten entschieden.
Wie gesagt: Vorschläge für den nächsten Contest sind jederzeit willkommen.

unentscheiden müsste anders gewichtet werden, da ein "passiver" Bot schon sehr viele Punkte einnimmt, falls dieser die "Gewinnsumme" 15 beim Gegner erfolgreich verhindert.

Zitat:

---

Zitat von AlterHacker

Gibt ja nur 9! (58.980) mögliche Spielverläufe

---

So kann man das nicht rechnen!
"Für Tic Tac Toe gibt es 255.168 verschiedene Spielverläufe, von denen 131.184 mit einem Sieg des ersten Spielers enden, 77.904 mit einem Sieg des zweiten Spielers und 46.080 mit einem Unentschieden. " (Quelle: [ame="http://de.wikipedia.org/wiki/Tic_Tac_Toe"]Tic Tac Toe – Wikipedia[/ame])

Zitat:

---

Zitat von Steiger_mp

unentscheiden müsste anders gewichtet werden, da ein "passiver" Bot schon sehr viele Punkte einnimmt, falls dieser die "Gewinnsumme" 15 beim Gegner erfolgreich verhindert.

---

Darüber könnte man eventuell diskutieren.

find das ist ne richtig gute idee, allerdings kommt doch eigentlich eh immer unentschieden raus?
ich finde man hätte sich für 4 gewinnt entscheiden sollen das funktioniert ja nach dem gleichen prinzip nur paar felder mehr und der stein muss "runterrutschen" :D

Zitat:

---

Zitat von reddragon1212

find das ist ne richtig gute idee, allerdings kommt doch eigentlich eh immer unentschieden raus?
ich finde man hätte sich für 4 gewinnt entscheiden sollen das funktioniert ja nach dem gleichen prinzip nur paar felder mehr und der stein muss "runterrutschen" :D

---

Ziel ist es ja einen Bot zu programmieren, der gewinnt. Hier gehts nicht um den passiven Bot, den ich im Post vorher angesprochen habe.

Vorschlag für nächsten Contest? 'Corewars' - Dummerweise aber nur in Assembler.

btw wieso ist als Tag 'phpisgay' ? :D

Ich verstehe schon, was ihr für Bedenken habt. Ich werde das mit BlackBerry nochmals kurz besprechen.

Bin dabei. :P
Hab nur noch ne Frage unzwar muss unser Programm prüfen ob jemand gewonnen hat und dann nen entsprechenden return Wert geben oder einfach immer nur Steine setzen und der Schiedsrichter wertet das dann aus ?!

Bin auch dabei.

Aktuell muss es einfach nur Steine setzen. Ein Programm von mir wird eure Programme dann gegeneinander antreten lassen und prüft den gewinner etc.