Und wieder ein Gastbeitrag von Sebastian Wagner, der sich fleißig darum bemüht, verschiedene Informatik-Wettbewerbe etwas bekannter zu machen – meinen Dank dafür.



Vierter Programmierwettbewerb des freien Magazins

Das freie Magazin, von dem jeden Monat eine Ausgabe veröffentlicht wird, richtet sich hauptsächlich an Interessierte aus der OpenSource- und Linux-Welt. Themen sind beispielsweise Programmvorstellungen oder kleine Einführungen in Programmiersprachen und -stile. Unerfahrene Entwickler auf Nicht-Unix-Systemen werden es bei diesem Wettbewerb zugegebenermaßen schwieriger haben als Entwickler auf Unix-Plattformen.

Das Spielprinzip des vierten Programmierwettbewerbs wird auf der Homepage so illustriert:

Ein Multimillionär verdient täglich so viel Geld, dass er gar nicht mehr weiß, wohin damit. Anstatt einen neuen Geldspeicher zu bauen, will er das Geld lieber in einem Experiment unter die Leute bringen. Dazu lädt er zwei Testsubjekte ein und begrüßt sie mit den Worten:

“Ich habe hier 1000 Euro. Das Geld gebe ich Testsubjekt A. Dieses muss dann einen selbst festgelegten Betrag X zwischen 0 und 1000 dem Testsubjekt B anbieten. Das kann also auch alles oder nichts sein! Testsubjekt B hat nun zwei Möglichkeiten: Entweder es akzeptiert den Betrag X. Dann erhält Testsubjekt B den Betrag X und Testsubjekt A natürlich den Restbetrag 1000-X. Testsubjekt B kann das Angebot aber ablehnen. Dann bekommt keiner die 1000 Euro und ich behalte das Geld. Damit es ausgeglichen ist, gebe ich danach Testsubjekt B ebenfalls 1000 Euro, welches auf die gleicher Art und Weise handeln muss.”

Beide Testsubjekte schauen erstaunt und wollen sich schon miteinander abstimmen, um einen größtmöglichen Gewinn zu erhalten, aber da springt der Millionär dazwischen: “Na na, Reden ist verboten. Ihr werdet beide in verschiedene Räume gesetzt und könnt nur über eine reine Zahlentastatur miteinander kommunizieren und die Beträge anbieten, annehmen oder ablehnen.” Die beiden Testsubjekte sind enttäuscht, aber machen dennoch mit, schließlich gibt es viel Geld zu gewinnen.

“Ach, noch was.” sagt der Millionär. “Das Spielchen wiederholen wir insgesamt 2500 Mal, weil es so viel Spaß macht. Ich bin gespannt, wer von Euch beiden mit mehr Geld nach Hause geht.”

Die Aufgabe ist nun einen möglichst intelligenten Bot zu entwerfen, dessen Ziel sein soll, die Taktik des Gegners (der auch immer ein Computer ist) zu erkennen und diesen dann auszutricksen. Infolgedessen ist es nötig, Muster in der Taktik des Gegners zu erkennen und mit verschiedenen Muster darauf zu reagieren: Nur eine implementierte Taktik allein wird also kaum zum Sieg führen! Es wird auch explizit auf Ähnlichkeiten zum Ultimatumspiel sowie zum Gefangenendilemma (beides stammt übrigens aus der Spieltheorie) hingewiesen, die Lektüre der entsprechenden Wikipedia-Artikel sollte also hilfreich sein.

Dadurch, dass nur die Standardein- bzw. -ausgabe verwendet wird, kann jede beliebige Programmiersprache verwendet werden. Für die Spielengine (in C++) ist allerdings ein C++-Compiler erforderlich. Der Wettbewerb läuft vom 1. Oktober 2011 bis zum 30. November 2011. Die ersten drei Plätze erhalten einen Amazon-Gutschein, dessen Höhe von der Anzahl der erreichten Punkte abhängt. 

Happy Coding!



CCC ’11 Vienna

Seit 2007 veranstaltet die Linzer Firma Catalysts mindestens 1-mal jährlich einen Programmierwettbewerb, den Catalysts Coding Contest. Heuer fanden bereits die Spring Callenge (online) und der CCC ’11 in Linz statt. Der CCC ’11 Linz war der bisher größte mit 180 Teilnehmern, die 4 Stunden lang im Linzer Schloss um die Wette programmiert haben. Nun wurde auch ein CCC in Wien für den 21. Oktober angekündigt.

Die Wettbewerbe funktionieren folgendermaßen: Der Programmierer bekommt nicht eine Problemstellung, für die er die gegebene Zeit (in Wien dann 2 Stunden) aufwenden kann, sondern muss sich in Levels hochkämpfen, d.h. die Probleme werden immer größer und auch komplexer. Ziel ist es also, einen möglichst ausbaufähigen Code zu erstellen, um sich nicht selbst zu verwirren. Es gewinnt, wer am meisten Levels schafft und diese am schnellsten absolviert. Da jeder sein eigenes Notebook mitnimmt, darf jeder in seiner/ihrer Lieblingsprogrammiersprache programmieren sowie Dokumentationen verwenden.

1 / 2 / Auf einer Seite lesen

Kommentare (24)

  1. #1 Dr. Webbaer
    Oktober 4, 2011

    Testsubjekt B kann das Angebot aber ablehnen. Dann bekommt keiner die 1000 Euro und ich behalte das Geld. (“freies Magazin”)

    Ein ganz ähnliches Turnier (“Round-Robin” vs. 2er-Match) gab es schon mal vor etlichen Jahren; die übliche “liberale” Strategie ist “Tit for Tat” und, um aus Dead-Ends herauszukommen: “Tit for Tat+Toleranz”. Dr. W sieht jetzt nicht, wie die variable “Setzhöhe” das Spiel taktisch/strategisch ändert – von den letzten Spielen der 2.5k-Serie mal abgesehen…

  2. #2 Dr. Webbaer
    Oktober 4, 2011

    Nachtrag:
    Wenn es wirklich nur darum geht in einer Zweiersitzung am Ende einen Cent mehr zu haben als der Gegner – “Das Spielchen wiederholen wir insgesamt 2500 Mal, weil es so viel Spaß macht. Ich bin gespannt, wer von Euch beiden mit mehr Geld nach Hause geht.” – scheint Destruktivität das Mittel der Wahl – auf Fehler des Gegners in den ersten Spielen hoffend. – Aber “irgendwie” wäre das unpointiert, es endet unentschieden bei beiderseitig bestem Spiel, vllt wurde das Spiel nicht verstanden, lol, …

  3. #3 MartinB
    Oktober 4, 2011

    “vllt wurde das Spiel nicht verstanden”
    Richtig. Es handelt sich nämlich nicht um ein iteriertes Gefangenendilemma, weil die Auszahlungsmatrix andere Eigenschaften hat.

  4. #4 Dr. Webbaer
    Oktober 4, 2011

    @MartinB
    Danke für die “relevante” Wiederholung, kommen Sie zu einem anderen Schluss als dass das Spiel nicht spielbar ist?

  5. #5 MartinB
    Oktober 4, 2011

    “kommen Sie zu einem anderen Schluss als dass das Spiel nicht spielbar ist?”
    Da es sich um ein Standard-Spielmodell handelt, das seit Jahren verwendet und untersucht wird, offensichtlich ja.

  6. #6 Dr. Webbaer
    Oktober 4, 2011

    @MartinB
    Zu welchem Schluss kommen Sie denn bezogen auf das Spiel? Oder wollen oder können das nicht mitteilen? – Die webbaersche Analyse jedenfalls steht oben für Sie bereit.

    Und selbstverständlich wird diese Spiel-Modellierung “offensichtlich” nicht “seit Jahren verwendet und untersucht“, jedenfalls nicht, wenn eine “Blockade-Variante” beider Spieler und ein n*500 (0 <= n <= 2.500) Vermögen beider Spieler am Ende zwingend ist bei korrektem Spiel.

  7. #7 Dr. Webbaer
    Oktober 4, 2011

    … Vermögen beider Spieler am Ende zwingend ist bei korrektem Spiel.

    In den runden Klammern wird n auf größer gleich 0 und kleiner gleich 2.500 begrenzt, offensichtlich mag oder kann das Publikationssystem nicht alle Vergleichsoperatoren, lol.

  8. #8 pseudonymus
    Oktober 4, 2011

    Danke für den Hinweis auf die Wettbewerbe!

    P.S.: Falls es Fragen zu den Wettbewerben gibt, gebe ich gerne Auskunft in den Kommentaren!

    Na, davon mache ich gerne beim Ultimatumspiel vom Freien Magazin Gebrauch.

    Ein Bot-Prozess läuft also ein Match durch und man kann über die 2500 Runden hinweg Informationen im Hauptspeicher halten. Wie ist es aber über alle n (n-1) Matches und über die 100 Wiederholungen der n (n-1) Matches hinweg? Unter welchen Pfaden kann man auf Disk schreiben und wie lange bleibt so eine Datei erhalten (alle Matches einer Wiederholung, alle Wiederholungen) ?

    Wie wird die Reihenfolge der Matches pro Wiederholung gebildet? Zufällig? Oder trifft man in jedem x.ten Match einer jeden Wiederholung immer auf denselben Bot?

    In die gleiche Richtung (ob man an der Reihenfolge der Matches andere Bots erkennen kann) die Frage: In einer Wiederholung gibt es “Hin- und Rückrunde”, also zwei Matches: Spieler A trifft auf B und B auf A. Finden Hin- und Rückrunde immer in einem bestimmten Muster statt, also zum Beispiel Hinrunde x.tes Match ( x < n ) und Rückrunde dann (n – 1 + x).tes Match?

  9. #9 sebix
    Oktober 4, 2011

    @pseudonymus:
    Über die 2500 Runden hindurch wird das Programm nicht beendet, die Spielengine kommuniziert während dieser Zeit über stdin/stdout mit den Bots.
    Bei den Wiederholungen ist es anders: Die Programme werden also 100 Mal (mit gleichem Gegner gestartet, um Zufälle statistisch zu minimieren (Das Ergebnis der Wiederholungen wird dann gemittelt).

    Auf der Disk schreiben und lesen ist nicht erlaubt, du hast werden der 2500 Runden den Speicher zu Verfügung.

    Jeder Bot tritt gegen jeden an, und das dann 100mal. Wenn viele mitmachen, haben die Verantwortlichen ein Problem mit 100*(n^n) Programmaufrufen 😀 (davon gehe ich aber nicht aus)

    Wer bei den Runden beginnt, erschließt sich nicht aus dem Text. Ich vermute, dass bei den Wiederholungen abgewechselt immer wird (dann das Muster, das du beschrieben hast). Dennoch habe ich mich diesbezüglich per Mail an die Redaktion gewandt. Könnte ja auch anders sein.

    @ Dr. Webbaer:
    Wenn der Gegener eine Tit-for-Tat Strategie fährt, sollte das Ziel sein, diese auszunutzen. Wie? Das überlege ich gerade… (Wenn es nicht geht, wird es langweilig)

    http://de.wikipedia.org/wiki/Die_Evolution_der_Kooperation

  10. #10 Dr. Webbaer
    Oktober 4, 2011

    @sebix
    Kleine Vorteile mitnehmen geht. [1] “Tit for Tat” kann wie sein sozialer Widerpart “die verhältnismässigkeitswahrende Kooperationshandlung” ja gegen niemanden gewinnen. 🙂

    “Tit for Tat” ist aber gut viele Punkte zu sammeln und dann so Turniere (!, sind’s keine 2-Matches mit jeweiliger Abrechnung? [2]) zu gewinnen.

    MFG
    Dr. Webbaer

    [1] gegen Ende der Kooperationsserien “zubeißen”
    [2] wäre nett, wenn das geklärt werden könnte, als 2er-Match mit anschliessender Abrechnung (1 für Sieg, 0 für Nieerlage bspw.) bringt die Aufgabenstellung nix

  11. #11 sebix
    Oktober 4, 2011

    Ich hoffe ich habe deinen Kommentar richtig interpretiert.

    Kleine Vorteile mitnehmen geht nur dann, wenn der Gegner nicht auch genau so spielt. Entscheiden wird also, wer sich besser anpasst oder Fehler im gegnerischen Algorithmus ausnutzt (könnte ja durchaus vorkommen)

    Die Abrechnung erfolgt über die Punkte bzw. das gewonnene fiktive Geld. Ein Beispiel ist auch auf der Website: http://www.freiesmagazin.de/vierter_programmierwettbewerb#auswertung

  12. #12 Dr. Webbaer
    Oktober 4, 2011

    “Für jedes Spiel zweier Bots wird die Punktzahl gespeichert, welche diese erreicht haben. Nachdem alle Bots gegeneinander gespielt haben, wird diese Punktezahl addiert. Wer dann die meisten Punkte hat, hat gewonnen.” – hatte Dr. Webbaer noch gefehlt, danke!

    Verstehen Sie das Spiel ruhig erst einmal als nacktes Tit for Tat, Spieler A wird wohl kaum mehr als 500 anbieten (501? 🙂 und 500 wäre fair. Am besten wäre es also erst einmal 500-500 zu spielen bis sich der Spaß der 2.500er-Grenze nähert (vorheriges “Schlauwerden” generiert Mißtrauen, wenn sich ein gegnerischer Bot querstellt, können sehr viele Punkte verloren gehen, die in der Turnierauswertung dann schmerzlich fehlen), vielleicht sogar ein “Tit for Tat” “+”, also sich gelegentlich abmeiern lassen, solange es nicht zuviel wird.
    In den letzten Spielen bietet es sich an auf einmal nur noch bspw. 400 zu bieten.

    Wichtig auf jeden Fall die Kooperation bestmöglich aufrecht zu halten und keine Eskalation zu fahren, bei diesem Spiel gilt: Wer eskaliert, verliert.

  13. #13 Dr. Webbaer
    Oktober 4, 2011

    Nachtrag:
    *Hmm* Man könnte auch auf die Idee kommen als Spieler A grundsätzlich etwas weniger als 500 zu bieten ohne dass es zu Kooperationsbrüchen kommt, denn was macht der Gegner sagen wir mal bei 450 oder 400. Der nimmt doch an, oder? Im nächsten Spiel ist der dann A und kann etwas mehr für sich nehmen, der hätte dann sozusagen den Service.

    Jedenfalls in der Theorie, wenn Sie es mit Bots zu tun haben, müssen Sie aber mit dem schlimmsten rechnen, also langanhaltender Vergeltung, lol.

    Das ist natürlich auch ein Psycho-Spiel, d.h. Sie müssen die Gegner kennen und die Gegnerparameter (es gibt wohl mehr als 1 Match gegeneinander?) persistieren und auswerten. Es gibt nicht Die richtige Strategie. Grundsätzlich aber kooperieren…

  14. #14 sebix
    Oktober 4, 2011

    Ob nun 500 oder 400 angeboten werden, ist grundsätzlich egal (wenn der Gegner Tit-for-tat verwendet). Ich habe langsam das Gefühl, dass es daruf hinauslaufen wird, wer die bessere Taktik gegen Nicht-Tit-for-Tat-Spieler hat

    Von einem “Tit for Tat” “+” halte ich wenig, da ist das normale Tit for Tat besser geeignet, denn das gelegentliche Einstecken bringt eigentlich nichts.

    “es gibt wohl mehr als 1 Match gegeneinander?” Über die 2500 Runden hinweg sollte sich die gegnerische Taktik erkennen und die gegnerische anpassen lassen. Die 2,5k Iterationen sind dafür mehr als genug.

    Wie wäre es mit einer Art binären Suche, mit der man die Toleranzgrenze des Gegners herausfindet (gilt nur für Tit for Tat gegner). Wenn man so auf Fehler im Algo stößt, könnte man diese dann gezielt ausnutzen.

  15. #15 Dr. Webbaer
    Oktober 4, 2011

    Es wird darauf hinauslaufen, dass Kooperationsbrüche durch Spieler B bei zu geringem Angebot beiden Spielern das Genick brechen, wenn sie zu oft passieren, und andererseits ein Gehacke um die Angebote von Spieler A einsetzt (Erläuterung: Spieler 1 ist manchmal Spieler A und manchmal Spieler B), die geringer, aber annehmbar sein müssen, zumal sich Spieler 2 revanchieren kann, wenn er den “Service” hat.

    Wie das nun genau zu implementieren ist? Tja…

    BTW: Im Unterschied zu dem originalspiel, das Dr. Webbaer kennt, spielt hier das sich anbahnende Ende einer 2500er-Serie eine eher geringe Rolle, denn man kann ja nicht direkt auf Kosten des anderen Spielers profitieren, also selbst Plus machen und der andere Punkteminus…

    Die Entwicklung so eines Bots dürfte herausfordernd sein. 🙂

  16. #16 Dr. Webbaer
    Oktober 4, 2011

    Nur eine letzte Idee: Wenn Sie als Spieler 1 zuerst das Angebot machen (Sie wären dann nach bisheriger Sprachregelugn Spieler A) und Onkel Webbaer ist Spieler 2 bzw. Spieler B, was passiert eigentlich, wenn Dr. W Ihr Angebot IMMER annimmt, dann aber im Gegenzug das Angebot in gleicher Höhe an Sie wiederholt?

  17. #17 sebix
    Oktober 4, 2011

    Ich dachte, um diese Taktik dreht sich zur Zeit alles?
    Kann man dann natürlich alles ein wenig anpassen, zB. lehnt man ab einer Grenze alles ab, bzw. nimmt an und das gleiche Angebot macht man dann selbst auch dem Anderen.

    Ich frage mich aber, ob so kleine Modifikationen wie diese im End-Ergebnis einen Unterschied machen können?

  18. #18 Dr. Webbaer
    Oktober 4, 2011

    Ist halt Brainstorming um dem Spielgedanken zumindest nahe zu kommen. Spielt das Nash-Equilibrium hier hinein? Welche Gleichgewichte bestehen ggf.? Was ist fair? Welche reale Situation ist hier nachgebaut? Die von handelnden sich regelmäßig treffenden Bauern, da wo alles noch per Handschlag geht?

    Dann ist es womöglich noch so, dass man gegen die meisten Spieler verlieren sollte, sozusagen ohne Selbstachtung, um im Schnitt immer wieder den 500 möglichst nahe zu kommen (während die Konkurrenz sich in Sanktionen verzettelt), das wäre bei so einer Simulation nicht unüblich, also bei Wirtschaftssimulationen, das ist eine davon.

    Würd erst mal längere Zeit nachdenken und vielleicht mal in die Theorie schaun…

  19. #19 pseudonymus
    Oktober 4, 2011

    @sebix:
    Danke! Dass man nichts auf Disk speichern kann war für mich aus der Anleitung nicht ersichtlich.

    Wenn nichts über ein einzelnes Match (einen Prozesslauf) hinaus gespeichert werden kann, erübrigen sich die beiden anderen Fragen natürlich. Man kann sich dann ja auch nicht das Verhalten anderer über Matches und Wiederholungen hinweg merken und braucht auch nicht darüber nachdenken, selbst so etwas wie Vertrauen über mehrere Matches hinweg aufzubauen.

    Hier ein Hinweis auf einen Artikel, der eine Simulation verschiedener Lernstrategien im Ultimatum-Spiels untersucht, vor allem Abschnitt 3.5 (beide Spieler lernen gleichzeitig). Die Strategien dort entwickeln sich gegen Angebote die etwa 10% über der Hälfte des Maximalangebots liegen. Eine Erklärung können die Autoren nicht liefern:
    Zhong, “Cooperative Agent Systems: Artificial Agents Play the Ultimatum Game”
    http://www.hicss.hawaii.edu/HICSS_35/HICSSpapers/PDFdocuments/INCDE03.pdf

    (So, jetzt implementieren die Konkurrenten bestimmt solche Strategien und mein Bot kann die ausnutzen 😉

  20. #20 pseudonymus
    Oktober 4, 2011

    … war zu schnell im letzten Kommentar: Die 55% (nicht 60%) in der Formulierung dort würden einem Angebot von 45% des Maximums in der Formulierung hier im Wettbewerb entsprechen.

  21. #21 sebix
    Oktober 4, 2011

    @pseudonymus:
    Das muss ich auch gleich wieder revidieren. Denn es ist erlaub, etwas zu speichern. Möchte aber gleich hinzufügen, dass es nichts bringt. Denn wer der Gegner ist, ist ja nicht bekannt und muss jedes Mal neu erkannt werden. Insofern stimmt deine Schlussfolgerung auch wieder.

    Es wurde übrigens eine FAQ veröffentlicht: http://www.freiesmagazin.de/vierter_programmierwettbewerb#faq Wichtig ist nur, dass Dateien grundsätzlich gespeichert werden dürfen.

    Wo kommen bei dir 60% vor?

    Interessantes Paper, bin gespannt ob ichs kapier 😀

  22. #22 Dr. Webbaer
    Oktober 5, 2011

    Das Paper rät u.a. zur Entwicklung eines “fair agents”, der nicht zu “smart” sein soll, dabei wurden prototypisch Agents entwickelt und in einem Kampf “jeder gegen jeden” aufeinander losgelassen, wobei die genaue Spezifikation der Attribute (“fair”, “smart” etc.) unterblieb. – D.h. auf gut Deutsch: Die Biotope der Wettbewerbsveranstaltung sind zu antizipieren und einzuarbeiten…

    Nicht uninteressant, dass das Gedächtnis der an den Start zu bringenden Bots oder Agents eine wichtige Rolle spielt und sozusagen das Bewusstsein der Wettbewerbskandidaten darstellt. Hier gilt es entsprechend vorzuarbeiten, aber das wissen i.p. Teilnahme und Entwicklung Interessierte natürlich schon längst.

    Onkel Webbaer rät also noch einmal den gemeinten und nachempfundenen Sachverhalt der Realität (“Sachlichkeit” – “Entitäten”, “Konzepte” etc.) bestmöglich zu erkennen und dementsprechend vorzusorgen.

    MFG
    Dr. Webbaer

  23. #23 sebix
    Oktober 17, 2011

    Catalysts hat nun bekanntgegeben, wie die Preisgelder aufgeteilt werden:
    Platz: Preisgeld (EUR)
    1: 1.100
    2: 900
    3: 800
    4-5: 700
    6-7: 600
    8-10: 500
    11-14: 400
    15-18: 300
    19-25: 200
    26-30: 100

    Also die ersten 30 🙂

  24. #24 leo
    Dezember 12, 2011

    Und die Ergebnisse vom freiesMagazin sind da, Gelegenheit für einen Strategievergleich:
    http://www.freiesmagazin.de/20111211-gewinner-des-vierten-programmierwettbewerbs