Stein, Schere, Papier (zum Mitmachen)

Am Ende der 10. Klasse sollen die Schüler in Informatik an einem umfangreicheren Projekt möglichst selbstständig arbeiten. Dazu ist eigentlich keine Zeit, die meisten Informatiklehrer kommen so gerade mal über die Runden dieses Jahr – das erste Jahr mit Informatik in dieser Jahrgangsstufe. Aber für ein klitzekleines Projekt habe ich noch Zeit.

Selbst Wikipedia weiß wenig über die Geschichte des Spiels Stein, Schere, Papier. Ich stelle mir gerne vor, dass schon die alten Germanen so etwas spielten. Jedes Jahr wird die Weltmeisterschaft darin ausgetragen. Man gewinnt durch psychologische Einschätzung des Gegners; am seltensten wird dabei (mit 29,6%) die Schere gewählt. Eine echte Zufallsstrategie würde das Spiel zu einem reinen Glücksspiel werden lassen, aber der Mensch ist zur Erzeugung von Zufallsreihen nicht geeignet.

Meine zehnte Klasse soll sich ein Modell für so ein Turnier einfallen lassen und das dann in Java umsetzen. Allerdings sollen nicht Menschen gegeneinander spielen, sondern vorbereitete Strategien der Schüler (in Form von Java-Klassen). Die besseren Schüler erarbeiten die Infrastruktur des Turniers; wer sich weniger zutraut, soll nur eine Strategie ins Rennen schicken und kann eine Tafel Schokolade gewinnen.

Solch eine Strategie kann sein: „Ich spiele immer Stein.“ Oder: „Ich spiele abwechselnd Stein-Schere-Papier, immer in dieser Reihenfolge.“ Oder man macht die eigene Entscheidung von den vergangenen Entscheidungen des Gegners abhängig. Ich stelle mir das ganze so vor, und jetzt wird es leider technisch:

stein-schere-papier

(Erklärung: # protected, -private, +public. Kursiv: abstract. Nach dem Doppelpunkt: Typ des Rückgabewerts bzw. des Attributs. Die Methode duellbestimmen(Duell) wird für die Verbindung mit anderen Klassen des Turniers gebraucht und ist hier nicht wichtig)

Zur Erläuterung des Diagramms: Es gibt eine Oberklasse Strategie mit den wichtigsten Methoden. Die Klasse ist abstrakt, es soll also gar keine Strategie-Objekte geben können. Vor allem ist die Methode entscheidungMitteilen() als abstrakt definiert. Das heißt, dass jede Unterklasse von Strategie dazu gezwungen wird, diese Methode selbst zu definieren.

Im einfachsten Fall sieht die zu programmierende Unterklasse so aus wie dieses Beispiel zur Ich-wähle-immer-Stein-Klasse:

public class Stein extends Strategie ( ) {
  //Attribute

  //Konstruktoren
  public Stein (String n) {
    super(n);
  }

  //Methoden
  public String entscheidungMitteilen ( ) {
    return "Stein";
  }
}

Die einzigen Bedingungen für die Schüler-Strategien: 1. Sie müssen im Konstruktor ihrer Klasse das Attribut name mit einem Wert versehen, so dass jedes Objekt ein eindeutiges Namen-Attribut erhalten kann. Das macht die Siegerehrung leichter. 2. Es muss natürlich die Methode entscheidungMitteilen() definiert werden, mit dem vorgegebenen Rückgabewert String. Erlaubt sind nur „Stein“, „Schere“ und „Papier“, aber eventuelle Fehler können die durchführenden Turnierklassen abfangen.

Zu klären ist noch die Spielweise. Ich will das Spiel möglichst einfach halten und schlage deshalb vor:

  • Jede Strategie spielt einmal gegen jede andere.
  • Ein Duell zwischen zwei Strategien dauert 100 Runden, also Entscheidungen. (Statt der üblichen, umständlicheren two out of three.)
  • Der Gewinner einer Runde erhält 2 Punkte, der Verlierer 0, bei gleicher Entscheidung gibt es jeweils 1 Punkt.
  • Reine Zufallsstrategien sind – aus Gründen – nicht erlaubt. (Vermutlich möchte ich auch Strategien ausschließen, die Zufall nur als ein Element im Algorithmus benutzen.) Lediglich ich als Lehrer schicke eine solche ins Rennen. Die Schüler sind sich noch uneins, ob das ein Vorteil für mich ist oder keiner. Das ist tatsächlich eine interessante Frage. Es ist keiner, hoffe ich.
  • Wer am Schluss am meisten Punkte hat, gewinnt.

Ich will deshalb 100 Runden, damit kluge Strategie Zeit haben, die Entscheidungen weniger kluger Strategien zu analysieren und sich darauf einzustellen.

Die Methoden der übergeordneten Klasse Strategie werden natürlich an die Kind-Strategien weitervererbt. Die wichtigsten lauten:

  • rundeErfragen() – in der wievielten Runde sind die Spieler gerade (Runde 0 bis 99, der Einfachkeit halber)
  • rundenzahlErfragen() – wieviele Runden gibt es insgesamt (100, eigentlich überflüssig, aber so bleiben wir flexibel)
  • punkteErfragen() – wieviel Punkte hat man selber im Moment

Und vor allem:

  • entscheidungErfragen(int r) – wie hat man sich in Runde r entschieden (falls man mitzählen möchte)
  • entscheidungGegnerErfragen(int r) – wie hat sich der Gegner in Runde r entschieden (falls man mitzählen möchte) – in beiden Fällen muss r natürlich kleiner sein als rundeErfragen()

Mit der letzten Methode kann man zum Beispiel ab Runde „1“ die Tit-for-tat-Strategie spielen, also immer die gleiche Entscheidung treffen wie der Gegner in der jeweils vorhergehenden Runde. Für Runde „0“ muss man sich noch etwas einfallen lassen:

public String entscheidungMitteilen() {
   return entscheidungGegnerErfragen(rundeErfragen()-1));
}

Ich schreibe das hier nur relativ skizzenhaft, weil es eh ein wenig technisch ist, und weil die Schüler sich das ja selber einfallen lassen sollen, statt hier abzuschreiben. Es kann also sein, dass die Methoden anders heißen werden, aber das lässt sich leicht anpassen. Zumindest irgendwelche Methoden dieser Art wird es geben.

Ich stelle das hier andererseits so ausführlich da für den Fall, dass hier jemand mitliest, der auch ein bisschen Java kann und Lust hat, selbst eine Strategie ins Rennen zu schicken. Der Gewinner kriegt eine Tafel Schokolade!

— Lose Gedanken zum Schluss:

  1. Ja, ich habe mich bei diesem Projekt vom Gefangenendilemma inspirieren lassen.
  2. Gerade bei konkurrierenden Strategien und gezählten Punkten ist das Prinzip der Datenkapselung wichtig. Sonst würde ja eine Strategie der anderen in die Entscheidungen pfuschen.
  3. Fortgeschrittene Schüler können ein Syndikat gründen und solche Strategien entwickeln, die – etwa anhand der ersten 10 Entscheidungen – sich gegenseitig erkennen und jeweils einer davon danach alle Punkte zuschustern. Gibt sicher noch mehr raffinierte Einfälle.
  4. Eine perfekte Strategie kann es demnach nicht geben, da der Erfolg jeder Strategie von der Zusammensetzung der Teilnehmer abhängt.
  5. Den BlueJ-Ordner oder eine Jar-Datei maile ich auf Wunsch zu, falls jemand zu Hause damit herumspielen und eigene Strategien erproben will.

Nachtrag: Hier gibt es mein Stein-Schere-Papier interaktiv.

14 Antworten auf „Stein, Schere, Papier (zum Mitmachen)“

  1. Wie lange läuft der Wettbewerb? Erfolgt die Zusendung der Tafel Schokolade für externe Gewinner elektronisch? ;-)

  2. Der Wettbewerb läuft noch bis… Ende Juli? Vielleicht um den 20. herum? Das ist schwer zu sagen, Informatik ist nur zweistündig, und aus diesen und jenen Gründen zerfleddert das Schuljahr spätestens ab Anfang Juli – Klassenfahrten, Orchesterproben, Sitzungen, da weiß man selten, wieviel Zeit noch bleibt. Die externe Schokolade schicke ich per Post.

    (Andreas, Mail geht heute abend raus.)

  3. Mich würde ja interessieren woher diese ominöse Zahl für Schere kommt. Ihc hab die jetzt schon mehrfach gelesen, aber auch schon eine andere Theorie gehört. Nach dieser Theorie, wählt jeder, der mit einem unbekannten spielt (und nicht gerade an jene Theorie denkt) beim ersten Mal Schere, weil keine Bewegung hält er/sie für zu einfach und Papier ist eine zu große Bewegung. In meiner (empirisch natürlich vollkommend wertlosen) Beobachtung funktioniert das wirklich gut. Wenn ich mit Leuten spiele die die Theorie nicht kennen gewinn ch shcon mal Runde 1 mit Stein (der mitspieler Schere)….

    Aber gut, bei dem oft wiederholten spiel ist dieser Gedanke natürlich überflüssig. Aus spieltheoretischer Sicht, glaube ich trotzdem an das einzige Nashequilibrium bei p=1/3 für alle Typen. Und da die Leute nicht verhandeln dürfen müssten alle Abweichungen nicht lohnenswert sein. Meine These daher: Wenn einer mit einer festen Strategie (wie auch immer die aussieht), also einer festen Reihenfolge von Aktionen (die wiederum natürlich abhängig sein können, von der Historie), dann kann er gegen den Randomizer nur gewinnen, wenn ér gegen einen anderen spielt, der eine nicht durchdachte Strategie wählt, die zufälligerweise der des ersten unterlegen ist. Würde jeder Teilnehmer alle Strategiemöglichkeiten der anderen miteinbeziehen und diese als gleichwahrscheinlich einstufen (gleichverteilt also), dann lohnt auschließlich Randomization…..zumindest aus Spieltheoretischer Sicht….wenn ein anderes Ergebnis rauskommt, dann müssten die Teilnehmer einen Bias in irgendeine Richtung haben, den einer sehr gut herausgefunden hat….Ich bin gespannt auf die Ergebnisse….

  4. NACHTRAG: Ich bin mir nur noch halb-sicher hinsichtlich der Nash-Equilibria.
    Einerseits glaube ich, dass das Spiel, da die Dilemma Situation wegfällt (die 2 Punkte werden immer vergeben), tatsächlich nur ein Nash-Equilibrium hat, andererseits bin ich mir bezüglich der mathematischen Nachweisbarkeit, dieser Tatsache unsicher geworden…der Beweis hat auf jeden Fall fürs erte nicht funktioniert.

    Was funktioniert hat ist backward induction. Das heißt, das Spiel von hinten aufrollen. Da das endlich ist, geht das gut. Und das einzige subgame perfect Nash equilibrium ist tatsächlich das randomisieren….Ich bleibe also bei meinem Postulat von oben, wenn auch theoretisch auf etwas wackeligen Füßen….

  5. In Japan ist das Spiel so üblich für die verschiedensten Entscheidungen, dass Japaner meist gegen Ausländer gewinnen.
    Mein Sohn behauptet ja, dass auch Jobs und Kaufverträge über das Spiel vergeben werden und dass sich daraus die Unzugänglichkeit des japanischen Marktes ergibt.
    Ob man die Japaner überreden könnte, das Spiel gegen ein elektronisches Programm zu spielen?
    Ich fürchte freilich, dann würden nicht deutsche, sondern indische Informatiker gewinnen. ;-)

  6. Da der Wettbewerb offenbar noch ein paar Tage dauert, wäre ich ebenfalls an den Sourcen interessiert.

  7. „Reine Zufallsstrategien sind – aus Gründen – nicht erlaubt. (Vermutlich möchte ich auch Strategien ausschließen, die Zufall nur als ein Element im Algorithmus benutzen.) Lediglich ich als Lehrer schicke eine solche ins Rennen. Die Schüler sind sich noch uneins, ob das ein Vorteil für mich ist oder keiner. Das ist tatsächlich eine interessante Frage. Es ist keiner, hoffe ich.“

    Nein, das ist natürlich für keinen ein Vorteil. Sobald einer von zwei Spielern eine reine Zufallsstrategie wählt, ist das Spiel für BEIDE Beteiligten absolut zufällig. Denn egal, was ich gewählt habe, ob ich gewinne oder nicht, hängt ja dann nur vom Ergebnis Ihres Zufallsexperiments ab.
    Insofern sollten Sie diese Strategie vielleicht gleich ganz außen vor lassen, da alle Spiele gegen diese Strategie (völlig unabhängig von der eigenen Strategie) immer 50%-Chancen wären.

  8. Zwei Kopien habe ich schon verschickt, der erste Bug ist gefunden, heute abend schicke ich eine neue Fassung, Zera.

    Gruenblinder, ich denke, du hast recht mit deinen beiden Kommentaren. Bin aber Laie, habe gerade da und dort mal in populärwissenschaftlichen Texten zur Spieltheorie was von Nash-Equilibrium aufgeschnappt. Viel hängt davon ab, ob irgendein Schüler eine Strategie schreibt, die den Bias der anderen Strategien (je nachdem, wie die geschrieben sind) ausnutzt.

    Fabi, bei einzelnen Spielen haben Sie auf jeden Fall recht. Wenn es bei einem Turnier allerdings syndikathafte Absprachen gibt, oder einen Unterschied zwischen naiven und raffinierten Strategien, dann hat Random im Turnierspiel sogar weniger Chancen. Wenn Nur-Schere, Nur-Papier und Random gegeneinander antreten, wird Nur-Schere das Turnier gewinnen.
    Aber ich rechne eher mit ausgeglichenen Strategien und keinem nennenswerten Vorteil für einzelne. Aber mal schauen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.