StartseiteVon Bits und Bytes

Gastbeitrag: vierter Programmierwettbewerb des freien Magazins und Catalysts Coding Contest ’11

Von / 3. Oktober 2011 / 24 Kommentare / Seite 2 von 2 / Auf einer Seite lesen
Mehr

Der Wettbewerb in Wien wird 2 Stunden dauern, von 14:00 bis 16:00 in der Raiffeisen Bausparkasse, nähere Details gibt es auf der Homepage. Ich weise darauf hin, dass es nur 80 Plätze Vor-Ort gibt! Dabei sein lohnt sich: Es gibt insgesamt 12.000€ an Preisgeldern, mindesten 20 TeilnehmerInnen werden laut Ankündigung mit Preisen heimkehren.

Für alle dabei sein wollen, aber nicht nach Wien kommen wollen/können: Es gibt zeitgleich auch einen Online-Wettbewerb, allerdings ohne Preise. Außerdem sind Teilnahmen im Team möglich (bis zu 3 Personen). Wer üben oder sich die Aufgaben ansehen möchte, kann dies auf CatCoder tun.

Catalysts unterstützt mit dem Wettbewerb übrigens auch den Nachwuchs (hierzu zählt auch der Autor): Für jeden Teilnehmer fließen 10 Euro an die Informatik-Olympiade (in Österreich).

Wer wissen möchte, worum es bei der Olympiade geht, kann sich den Gastbericht von der Internationalen Olympiade in Thailand 2011 durchlesen.

Ferner können Teilnehmer ihren Code über die Open-Commons Initiative der Stadt Linz ihren Code (freiwillig) Forschern zur Verfügung stellen.

Ich würde mich freuen, Leser des Von Bits und Bytes-Blogs in Wien kennen zu lernen!

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

1 / 2
Stichworte: ,
Mehr

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)

    https://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: https://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”
    https://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: https://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:
    https://www.freiesmagazin.de/20111211-gewinner-des-vierten-programmierwettbewerbs