Schere, Stein, Papier Programmierwettbewerb

[BlackJack]

Unter Rock Paper Scissors Programming Competition gibt es gerade einen Programmierwettbewerb für künstliche Intelligenzen die Schere, Stein, Papier spielen können. Und dabei gegen nicht rein zufällig spielende Gegner (a.k.a. die meisten Menschen) möglichst besser als Durchschnitt sein sollten.

Programmiersprache des Wettbewerbs ist Python. Was auch sonst.

[microkernel]

Sehr interessant! Aber "kämpft" man jetzt gegen Computer oder gegen Menschen?

[BlackJack]

@microkernel: Na gegen die anderen Programme. Anders wären die Turniere mit bis zu 1000 Durchgängen wohl auch kaum möglich.

[theliquidwave]

Moment. Wie kann man denn da durch Mathematik bitte Vorteile erlangen? Das Spiel ist doch nur - ähm - Zufall?

[Barabbas]

Naja, steht ja bei BlackJack und in der Aufgabenbeschreibung des Wettbewerbes: Es gibt eben nicht nur zufällig spielende Gegner, sondern auch welche, die ein System haben (immer Schere, immer Stein, bestimmte Reihenfolgen etc.).

Deine AI soll also in der Lage sein zu sagen "Armer Bart, immer nimmt er den Stein" . Damit solltest du gegen nicht-zufällig spielende Gegner eine Quote erreichen, die deutlich über dem zu erwartenden Zufallsdurchschnitt liegt.

Besten Gruß,

brb

[EyDu]

@theliquidwave: Das Spiel hat nichts mit Zufall zu tun. Wenn beide Spieler optimal spielen, dann endet es immer unentschieden.

[lunar]

@EyDu: Doch wohl nur statistisch, oder? Sprich, wenn beide Spieler optimal spielen, dann enden im Mittel alle Spiele unentschieden, oder?

[EyDu]

Ach verdammt, ich war gerade beim falschen Spiel

[theliquidwave]

Ach so. Also müsste mein Bot zum Beispiel in den ersten paar Spielen erkennen, welches Muster der Gegner verfolgt, es erkennen und entsprechend drauf reagieren. Ich verstehe

[derdon]

Ja, so sieht es aus. Gibt auch eine Online-Seite, wo so ein Bot existiert. Vllt. kennt die ja jmd. und kann die posten, ich hab die Adresse leider vergessen.

[Leonidas]

Ach verdammt, ich war gerade beim falschen Spiel

Etwa das?

[Nocta]

Mal eine ganz dumme Frage:
Ist es nicht völlige Glückssache, wenn man mal von billig-Bots mit einem bestimmten Muster absieht?

Wenn ich einen Bot schreiben würde, würde er in erster Linie auf dem Zufall basieren.
Falls ich nebenbei noch ein Muster ekennen könnte, würde ich testweise meine Taktik danach ausrichten und falls es Erfolg hat, weiter so machen, ansonsten wieder zufällig spielen.

Im Optimalfall spielt also jeder vernünftige Bot zufällig, wobei aber zufallsbedingt ein Bot ein scheinbares Muster aufweisen könnte, welches der andere eben als Muster erkennt, obwohl es keines ist.
Falls dieser Bot das nicht schnell genug erkennt, wird jetzt evtl. der andere Bot ein Muster erkennen, da der erste Bot jetzt wirklich nicht mehr zufallsgesteuert spielt.
Aber das ist eben auch nur Glück, da sowohl der eine, als auch der andere Bot auf ein scheinbares Muster reinfallen könnten.


Dass ein guter Bot zufällig spielen muss, sollte ja wohl klar sein: Egal wie ausgeklügelt das System ist, man muss zumindest theoretisch einplanen, dass es überlistet wird. Zufall kann man nicht überlisten.
Man hat damit also die beste Verteidigung, allerdings keinen "Angriff", da man den gegnerischen Bot nicht verarschen kann, außer er zeigt ein Muster und man weicht vom Zufallsprinzip ab.
Das ist aber irgendwie irrelevant, da dieser andere Bot auch auf die beste Verteidigung sprich Zufall setzen sollte.


Klärt mich auf, wenn ich irgendwas falsch sehe

[Barabbas]

Du liegst nicht falsch, aber darum geht es in diesem Fall einfach nicht...

[BlackJack]

@Nocta: Wenn das Mustererkennen irrelevant wäre, dann dürfte es keine Bots geben die ≈80% der Matches gewinnen. Solche gibt es aber.

[Nocta]

Du liegst nicht falsch, aber darum geht es in diesem Fall einfach nicht...

"Du hast Recht, aber eigentlich doch nicht" - Hilft mir grad nicht weiter, meinen Fehler zu erkennen

@Nocta: Wenn das Mustererkennen irrelevant wäre, dann dürfte es keine Bots geben die ≈80% der Matches gewinnen. Solche gibt es aber.

Ja vielleicht deshalb, weil zu viele Bots auf Muster setzen.

Generell ist das Spiel ja vollkommen fair für beide Parteien. Wenn beide auf Zufall setzen, gewinnt jeder im Schnitt 500 von 1000 Spielen, wenn man jetzt Unentschieden der Einfachheit halber rauslässt.
Wenn ein Bot A auf ein primitives Muster setzt, wie zum Beispiel nur Schere, dann sollte er gegen den Bot B, der vollkommen zufällig ist, auch im Schnitt 500:500 spielen.
Nur wenn Bot B das primitive Muster von Bot A austrickst, kann er sich einen Vorteil verschaffen.
Dabei wird Bot B aber wiederum anfällig für Angriffe von Bot A usw.
Folglich wäre es am sinnvollsten, wenn jeder auf den Zufall setzen würde und dann wäre es eben dem Zufall überlassen, wer gewinnt
Ich meine, was will der ausgeklügelste Bot gegen ein simples `random.randint(1, 3)` machen? Da kann er im optimalen Fall auch nur 500:500 spielen (im Mittel wohlgemerkt).

Wer einen logischen Fehler findet - bitte aufklären

[BlackJack]

@Nocta: Wenn Bot B auf Muster reagiert, wieso ist er dann anfällig(er) für Angriffe von Bot A? Wie kann sich A dadurch einen Vorteil verschaffen? Wenn A zufällig spielt, kann B kein Muster erkennen und folgt damit selber auch keinem erkennbaren Muster: beide sind also zufällig. Wenn A ein Muster spielt ist er gegen B erst einmal im Nachteil. Wenn B das Muster erkannt hat, dann verliert A öfter. Weiss dann vielleicht was B als Antwort auf das eigene Muster spielen wird und kann deswegen ein paar mal gewinnen. Das merkt B doch aber und passt sich entsprechend an. Was hätte A damit denn jetzt wirklich gewonnen? Wo siehst Du da einen Vorteil?

Gegen ein simples `randint(1, 3)` könnte man versuchen den zugrunde liegenden Seed-Wert heraus zu bekommen und wenn man den hat, 100% der Züge des Gegners vorher zu sagen. Ist also die Frage wie schwierig das ist und ob es sich für diesen Sonderfall überhaupt lohnt.

[gkuhl]

Wer einen logischen Fehler findet - bitte aufklären

Es geht in dem Contest darum besser als 50% zu sein. Und das geht eben nur wenn du nicht mehr total zufällig spielst, sondern versuchst das Spielsystem des Gegners zu entschlüsseln. Natürlich birgt das die Gefahr, dass dein Gegner dein System entschlüsselt und du verlierst.

Diese Begründung ist auch auf der Internetseite nachzulesen:

If playing randomly is the optimal strategy, what is the point of a RPS competition? It is actually possible to do much better than a random player when the contest involves non-random competitors. This is because a strong player can consistently beat predictable players, while a random player will win about half of its matches. This means that random players will tend to rank around the middle of a competition leaderboard, while strong players will consistently rank higher.

Wenn man ins "Leaderboard" schaut, sieht man, dass die guten Spieler eine "Win rate" von etwa 80% haben.

Grüße
Gerrit

[Nocta]

Wenn Bot B auf Muster reagiert, wieso ist er dann anfällig(er) für Angriffe von Bot A? Wie kann sich A dadurch einen Vorteil verschaffen?

A kann sich einen Vorteil dadurch verschaffen, dass B jetzt berechenbar spielt, da er auf das Muster von A reagiert. Das könnte also sozusagen eine "Falle" sein. Aber selbst wenn das nicht geplant ist, macht sich B in jedem Fall anfälliger, wenn er vom Zufall abweicht - Ob A das ausnutzen kann, ist eine andere Frage.
Es ist also kein Vorteil, wie du es ausdrückst, aber eine eventuelle Chance.

Wenn A zufällig spielt, kann B kein Muster erkennen und folgt damit selber auch keinem erkennbaren Muster: beide sind also zufällig

Stimmt genau. Außer ein Bot erkennt fälschlicherweise ein Muster, welches aber nur zufallsbedingt entstanden ist.

Gegen ein simples `randint(1, 3)` könnte man versuchen den zugrunde liegenden Seed-Wert heraus zu bekommen und wenn man den hat, 100% der Züge des Gegners vorher zu sagen.

Okay ich gehe aber mal davon aus, dass das nicht bei 1000 Spielen möglich sein wird, oder?

Es geht in dem Contest darum besser als 50% zu sein. Und das geht eben nur wenn du nicht mehr total zufällig spielst, sondern versuchst das Spielsystem des Gegners zu entschlüsseln.

Das ist mir klar.
Ich weiß nicht genau, wie ich das erklären soll.
Das ganze funktioniert doch nur genau dann, wenn mindestens ein "Idiot" bei dem Contest mitmacht, der eben NICHT auf Zufall setzt.

Gehen wir mal davon aus, dass 10 Mathematiker dieses Problem überdenken und ihre Schlussfolgerungen immer richtig sind.
Zu welchem Schluss käme einer von ihnen dann wohl?
Er muss davon ausgehen, dass die Gegner keine Schwachstellen bieten wollen und wird denken, dass sie kein Muster implementieren, sondern komplett zufällig spielen.
So jetzt ist es vollkommen egal was man selbst macht, wenn man davon ausgeht, dass der Gegner komplett zufällig spielt.
Immer Schere, abwechselnd Schere und Stein, auch komplett zufällig ... Es wird sich immer auf 1:1 belaufen.
Da er aber weiß, dass die anderen das selbe von ihm erwarten, wie er von ihnen, wird er auf keinen Fall ein Muster bieten, denn die anderen könnten dafür einen Konter eingebaut haben.

Ergo: Der Contest dürfte normalerweise nicht auf komplexe Bots hinauslaufen, wenn es alle "richtig" machen würden.

Aber klar, da nicht alle so spielen - wär ja langweilig - lassen sich komplexe Bots bauen, die solche "dummen" Bots mit einem Muster schlagen können.
Das Motto könnte also Lauten "Wer macht die meisten Idioten fertig, die nicht zufällig spielen?"


Das ist eben mein Problem mit dem Contest, da es erst jemanden geben muss, der "dumm" (ohne Zufall) spielt, damit sich andere Bots absetzen können.

[BlackJack]

@Nocta: B spielt nicht wirklich berechenbar für A wenn B ein Muster erkannt hat. Denn sobald A nicht mehr nach dem erwarteten Muster spielt, ändert sich ja auch das Spielverhalten von B und damit weiss auch A nicht mehr wie er ihn schlagen kann. Es ist ja nicht so dass B 100 Spiele abwartet, dann die Züge von A analysiert und ein Muster erkennt, und dann die nächsten 900 Züge so antwortet als wenn A weiterhin das in den ersten 100 Zügen erkannte Muster spielt. Selbst eine sehr einfache Version von B wird mit Wahrscheinlichkeiten arbeiten und für jeden Zug eine gewichtete Zufallsentscheidung treffen, die auf den allen vorangegangenen Zügen von A basiert.

Die Annahme das es nur ”Genies” in dem Wettbewerb gibt, lässt sich ganz einfach widerlegen wenn man sich mal das untere Ende der Rangliste anschaut. Es gibt da auch Bots, die immer nur Schere spielen. Man kann sich die Quelltexte ja anschauen.

Und wenn wirklich nur 10 geniale Mathematiker an dem Wettbewerb teilnehmen, dann ist Dein Schluss trotzdem falsch, denn dann wird mindestens einer auf die Idee kommen *absichtlich* einen dummen Spieler hoch zu laden, um den mit einem eigenen, intelligenteren Bot schlagen zu können, damit er aus dem 50% Mittelmässigkeitssumpf heraus kommen kann.

[Nocta]

B spielt nicht wirklich berechenbar für A wenn B ein Muster erkannt hat. Denn sobald A nicht mehr nach dem erwarteten Muster spielt, ändert sich ja auch das Spielverhalten von B und damit weiss auch A nicht mehr wie er ihn schlagen kann.

Na ja du hast sicher Recht, dass das kein allzu großes Problem ist, aber allgemein ist B dann angreifbar. Wie lange und ob A das ausnutzen kann ist etwas völlig anderes, aber er hat sozusagen seine Deckung verlassen. Das wollte ich damit sagen

Die Annahme das es nur ”Genies” in dem Wettbewerb gibt, lässt sich ganz einfach widerlegen wenn man sich mal das untere Ende der Rangliste anschaut.

Deckt sich irgendwie nicht ganz mit deinem letzten Satz, da ein Genie doch auch einen schlechten Bot erstellt hätte
Dass wir es in der Realität nicht mit Genies zu tun haben, würde ich aber auch so sagen.

Nun ja, es ist ja offensichtlich so, dass man mit einem ausgeklügelten System weiter kommt, aber ich finde die Ausgangssituation dieses Wettbewerbes etwas unsinnig.
Da würde ich mir lieber ein fiktives Brettspiel ausdenken, etwa eine simplere Version von Schach. Aber das wär vielleicht wiederum zu schwer bzw zeitintensiv für die meisten.