Frage:
Ist Angry Birds deterministisch?
Thomas Bonini
2011-12-29 22:30:31 UTC
view on stackexchange narkive permalink

Als ich versuchte, 3 Sterne auf den komplexeren Levels zu bekommen (die mit vielen zerstörbaren Einheiten), bemerkte ich, dass ich selbst nach mehr als 50-maligem Spielen desselben Levels, immer das Gleiche zu tun, noch nie dasselbe gesehen habe Endergebnis. Etwas läuft immer anders.

Führt dieselbe Eingabe immer zu derselben Ausgabe, oder gibt es dort einen Zufallsfaktor?

Wie können Sie sicher sein, dass Ihre Eingabe zu 100% identisch ist?
Die perfekte Eingabe kann über die Emulation eines Telefons, über spezielle Programme oder einfach über die Desktop-Version des Spiels mit der Maus erfolgen, wie dies bei agent86 der Fall ist.
Fünf antworten:
#1
+465
agent86
2011-12-29 22:47:10 UTC
view on stackexchange narkive permalink

Der -Algorithmus ist deterministisch, aber es ist fraglich, ob das Gesamtergebnis beim Starten eines Vogels effektiv nicht deterministisch ist, da er auf (außerordentlich sensiblen) Benutzereingaben beruht.

Um den Algorithmus und die Auswirkungen von Benutzereingaben zu testen, habe ich das folgende Verfahren angewendet:

  • Laden Sie die Google Chrome-Version von Angry Birds
  • Laststufe 1-1
  • Ziehen Sie die Maus zurück zu einer bestimmten XY-Koordinate. (Dies war nach dem Punkt "Vollziehen" für den Vogel.)
  • Lassen Sie den Vogel los und warten Sie, bis das Spiel einen stabilen Zustand erreicht hat.

To Messen Sie meine XY-Koordinate. Ich öffnete ein Chrome-Hintergrundfenster und navigierte zu dieser Seite. Ich habe die beiden Fenster so ausgerichtet, dass ich die X- und Y-Positionen der Maus sehen konnte, während ich beim Loslassen des Vogels noch etwas bewirken konnte. Ich richtete meinen Mauszeiger auf die untere linke Ecke des Feldes um diese beiden Zahlen aus und ließ sie dann los. Ich habe dann die Position meines Mauszeigers notiert (da die Anzeige nur aktualisiert wird, wenn die Maus nicht losgelassen wird und sich der Cursor über diesem Fenster befindet) und dann die resultierende Punktzahl in Angry Birds notiert. Wenn Sie Probleme mit der genauen Mauspositionierung haben, können Sie eine von Ihrem Betriebssystem angebotene Eingabehilfenoption ausprobieren, z. B. Maustasten unter Windows.

Ich habe die gleiche Punktzahl erhalten. Solange sich mein Cursor genau an der Stelle befand wie bei früheren Iterationen.

Bevor ich einen erweiterten Prüfstand entwickelte, mit dem ich die Position meines Cursors messen konnte Als Pixel habe ich dieses Experiment ungefähr 10 Mal ausgeführt, wobei ich einen Referenzpunkt im Hintergrundbild des Spiels verwendet habe. Ich bekam Punkte, indem ich den ersten Vogel abfeuerte, der zwischen 8.000 und 11.000 Punkten variierte. Wenn ich bei Verwendung der erweiterten Teststrategie um ein einzelnes Pixel versetzt war, konnte ich Punktedifferenzen zwischen 150 und 500 Punkten erwarten.

Ich werde feststellen, dass sich der Cursor jenseits des Randes des Spielbereichs außerhalb des Browserfensters befand, weit jenseits der maximalen Entfernung, über die der Vogel zurückgezogen werden kann, und ich bemerkte immer noch Unterschiede beim Bewegen meines Vogels Cursor sogar ein einzelnes Pixel.

Außerdem habe ich Screencaps für einen Extremfall erstellt, in dem sich mein Cursor auf einem anderen Monitor als im Spielfenster befand, und Es wurden mehrere Iterationen ausgeführt, bei denen ich den Cursor an derselben Stelle hielt oder ihn leicht bewegte. Nach meinen Berechnungen (basierend auf der Messung der Entfernung von Screencaps) konnte das Spiel ein anderes Ergebnis (Punktzahl 32960 gegenüber 31520) erzielen, basierend auf einem Höhenunterschied von einem Pixel (544 gegenüber 545 Pixel) über eine Entfernung von ungefähr 1.284 Pixel Breite. Dies ergibt eine Winkeldifferenz von 0,03 Grad.

Ich würde sagen, dass Sie für alle praktischen Zwecke erwarten können, dass Sie dieselbe allgemeine Strategie wiederholt auf derselben Ebene anwenden und stark unterschiedliche Ergebnisse erwarten. Die Empfindlichkeit der Bedienelemente ist so extrem, dass es keinen praktischen Weg gibt, sie zweimal dazu zu bringen, dasselbe zu tun. Dies wird durch die Tatsache verschärft, dass es außerordentlich schwierig ist, dieselben Bewegungen bis auf das einzelne Pixel zu reproduzieren, wenn Sie auf einem Touchscreen spielen.

Ein Pixel * kann * leicht einen großen Unterschied in der Punktzahl bedeuten. Das ist keine Antwort darauf, ob es deterministisch ist oder nicht; Sie müssen sicher sein, dass Ihre Eingabe identisch ist.
Selbst in deterministischen Szenarien kann ein winziger Unterschied im Startzustand zu einem massiven Unterschied im Endzustand führen. Es heißt [Chaostheorie] (http://en.wikipedia.org/wiki/Chaos_theory).
@MyrddinEmrys, Wie ich bereits erwähnt habe, habe ich das Experiment bis auf die Pixelgenauigkeit wiederholt. Ich stellte fest, dass der verursachte Schaden der gleiche war, wenn ich so genau war. Ich würde sagen, für alle praktischen Zwecke des Spielens sind die Steuerelemente so genau, dass Sie erwarten können, dass das endgültige Verhalten des Systems für jedes "normale" Szenario der Verwendung menschlicher Eingaben effektiv nicht deterministisch ist. Das Spiel selbst ist jedoch deterministisch.
Zu beachten ist, dass es für einen Menschen aufgrund einfacher ständiger Zuckungen in der Hand praktisch unmöglich ist, genau dieselbe Berührungseingabe zu erzeugen. Die Realität ist der Zufallsfaktor, nicht Angry Birds, wie Sie gefunden haben.
Angry Birds: Ein Millimeter-Spiel auf einem Zentimeter-Gerät. Wahnsinn.
Wenn Sie dieses Experiment ausprobieren möchten, können Sie [mein Userscript installieren] (https://gist.github.com/raw/1536489/angrierbird.user.js). Auf der Seite Angry Birds werden Felder hinzugefügt, die die genaue Cursorposition verfolgen. Eine Vorschau des Skripts finden Sie [hier] (https://gist.github.com/1536489).
@splatteredbits das ist so ziemlich mein Eindruck davon
Sehr geehrter Agent86, Sie haben geschrieben: "Ich habe Punkte erzielt, indem ich den ersten Vogel abgefeuert habe, der zwischen 8.000 und 11.000 Punkten schwankte." Ist es möglich, den Test mit der aktuellen Version auszuführen und festzustellen, ob die Ergebnisse systenatisch höher sind?
@GilKalai Sie können verschiedene Ebenen nicht so vergleichen, es hängt ganz davon ab, wohin der Test gerichtet war.
Nun ist die Frage ... auf Ebenen mit semidynamischen Entitäten (wie Laserkanonen und beweglichen Plattformen auf * Angry Birds Star Wars *), inwiefern ist es deterministisch?
Diese Antwort ist ein wissenschaftliches Experiment.
Warten Sie, Sie haben das alles für Arquade getan?!+342!
Ich glaube, die Natur des Spiels ist chaotisch.Ein chaotisches System ist deterministisch, aber kleine Änderungen der Anfangsbedingungen haben massive Änderungen des Ergebnisses zur Folge.
#2
+196
Pubby
2011-12-30 01:32:07 UTC
view on stackexchange narkive permalink

Angry Birds verwendet die Box2D -Bibliothek für die Physik.

Ist Box2D deterministisch? Für denselben Eingang und dieselbe Binärdatei reproduziert Box2D jede Simulation. Box2D verwendet keine Zufallszahlen und basiert auch nicht auf zufälligen Ereignissen (wie Timern usw.).

Menschen wünschen sich jedoch häufig einen strengeren Determinismus. Die Leute wollen oft wissen, ob Box2D auf verschiedenen Binärdateien und auf verschiedenen Plattformen identische Ergebnisse erzielen kann. Die Antwort ist nein. Der Grund für diese Antwort hängt damit zusammen, wie Gleitkomma-Mathematik in vielen Compilern und Prozessoren implementiert ist. Ich empfehle, diesen Artikel zu lesen, wenn Sie neugierig sind: http://www.yosefk.com/blog/consistency-how-to-defeat-the-purpose-of-ieee-floating-point.html

http://code.google.com/p/box2d/wiki/FAQ#Determinism

Das ist großartig (danke, dass Sie sich tatsächlich bei der Quelle erkundigt haben); Haben Sie der Vollständigkeit halber eine Referenz, dass Angry Birds Box2D verwendet? Und woher haben Sie dieses Zitat?
@MarkTrapp http: // www.geek.com / articles / mobile / box2d-Schöpfer-fragt-Rovio-nach-wütenden-Vögeln-Kredit-bei-GDC-2011032 / und http://en.wikipedia.org/wiki/Box2D
Und ich wette, dass die Physik-FPS aufgrund zahlreicher Faktoren (nicht genügend CPU, Überhitzung, Seitenfehler usw.) ebenfalls variieren, was sich auf die „Genauigkeit“ der Simulation auswirkt. :) :)
Die zweite Aussage ist mehrdeutig; Ich gehe davon aus, dass Sie möglicherweise nicht genau das gleiche Ergebnis erzielen, wenn Sie dieselbe Simulation auf mehreren Architekturen ausführen, aber pro Plattform wird jede Simulation jedes Mal auf dieselbe Weise ausgeführt.
@muntoo das ist nicht unbedingt wahr, da Entwickler das Spiel auch bei niedrigeren Frameraten die gleiche Anzahl von Simulationsschritten ausführen lassen können. Bei tatsächlichen Prozessorfehlern wird diese Möglichkeit in Spielen normalerweise ignoriert, da sie so selten ist. Wenn Sie sich für das Thema deterministische Simulationen interessieren, können Sie mehr in [gamesfromwithin blog] (http://gamesfromwithin.com/casey-and-the-clearly-deterministic-contraptions) lesen oder einfach googeln. :) :)
@agent86 Ich würde Ihren Wortlaut in "[...] ändern, aber pro Plattform und ** pro Box2D-Version ** wird jede Simulation jedes Mal auf die gleiche Weise ausgeführt." (Dieser "gleiche binäre" Teil im ersten Absatz scheint dies anzuzeigen).
@JoãoPortela, guter Punkt. Ich ging davon aus, dass "release" keine Variable ist, die sich in diesem Fall ändern darf.
Verstehe den ersten Absatz der Qoute nicht. Ist Box2D also deterministisch oder nicht?
@Jake Ja, es ist deterministisch, aber mit den im zweiten Absatz genannten Einschränkungen.
Immer noch verwirrt. Warum heißt es "Box2D reproduziert JEDE Simulation" anstatt "GLEICHE" Simulation? Ich schreibe eine Server-Client-Lockstep-Sim und führe 2 derselben client.exe aus, die nur dann dieselbe Simulation liefert, wenn keine Kollisionen vorliegen.
@Jake Ich bin mir nicht sicher, versuchen Sie es vielleicht mit Stack Overflow.
#3
+34
Matthew Read
2011-12-30 00:26:43 UTC
view on stackexchange narkive permalink

Einige Level sind kurz nach Beginn des Levels zufälligen Explosionen ausgesetzt, und einige Steine ​​können von selbst fallen, bevor Sie jemals einen Vogel geworfen haben. Diese Ereignisse treten selten auf, aber wenn Sie jedes Level in jedem Spiel mit drei Sternen ausgezeichnet haben, werden Sie es wahrscheinlich ein paar Mal gesehen haben, wie ich es getan habe.

Ich würde erwarten, dass dies aufgrund des Timings auftritt Probleme, möglicherweise im Zusammenhang mit Threading. Ich bin mir ziemlich sicher, dass Sie, wenn Sie einen Test durchgeführt haben, bei dem Sie jedes Level ein Dutzend Mal geladen und 30 Sekunden gewartet haben, mindestens einmal eine Punktzahl ungleich Null erhalten würden. Angesichts der Antwort von Pubby kann ich nur davon ausgehen, dass die Angry Birds-App zu Beginn eines Levels nicht immer die gleichen Eingaben für die Box2D-Funktionen liefert.

#4
+11
Joseph KaraokeGuy Holtzinger
2014-12-22 02:26:47 UTC
view on stackexchange narkive permalink

Ich habe auf Facebook mit einem Makrorecorder gespielt. Ich startete den Rekorder, ging zum Fenster der wütenden Vögel, zoomte heraus und spielte die ersten beiden Vögel. Ich habe dann den Rekorder angehalten. JEDES Mal ging die Maus auf die exakten Pixel und wurde mit genau der gleichen Leistung usw. freigegeben. Sie musste, weil die aufgezeichnete Mausbewegung jedes Mal das Gleiche tut, Pixel für Pixel. Jedes Mal, wenn ich eine andere Punktzahl bekam, und nicht jedes Mal, wenn die gleiche Anzahl von Schweinen getötet wurde usw. Dieses Spiel ist inkonsistent

#5
-4
Myrddin Emrys
2011-12-29 23:08:26 UTC
view on stackexchange narkive permalink

Ich habe 10 Tests durchgeführt und jedes Mal den gleichen Punkt erreicht (auch Chrome Angry Birds, Stufe 1, wie in den Tests von agent86).

Red Crosshair of test spot

Ich habe nie erhalten zweimal die gleiche Punktzahl, obwohl darauf geachtet wird, genau an die gleiche Stelle zu ziehen und dies ungefähr gleich nach Beginn des Levels zu tun. Ich glaube, Angry Birds ist sehr wenig deterministisch.

Dies ist ziemlich einfach zu erklären: Es wurde für kleine Touchscreens entwickelt. Wenn es deterministisch wäre, könnten Benutzer Bewegungen aufgrund der begrenzten Genauigkeit des Eingabegeräts leicht wiederholen. Dies könnte insofern schlecht sein, als ihr Gerät buchstäblich nicht die Präzision haben könnte, die erforderlich ist, um genau auf den gewünschten Winkel und die gewünschte Leistung zu zielen. Durch ein leichtes Wackeln der Ergebnisse und aufgrund der Eingabe eines „Fingers“ würden Benutzer den Mangel an Präzision nicht bemerken, und sie würden auch nicht frustriert sein, wenn sie niemals in der Lage wären, einen gewünschten Schuss zu machen.

Der zusätzliche Test von agent86 zeigt, dass ich mich irren könnte. Ich werde es erneut testen, wenn ich nach Hause komme, da ich mir ziemlich sicher war, dass ich meinen Cursor präzise platziert hatte.
Ich denke du liegst falsch. Der Touchscreen macht es tatsächlich extrem schwierig, jedes Mal die gleiche Eingabe zu erhalten. Zum Beispiel hat das iPhone 614400 Pixel. Jeder von diesen würde eine unterschiedliche Ausgabe erzeugen.
@Daenyth: Sind Sie sicher, dass die Genauigkeit der Eingangsauflösung 1 Pixel beträgt? Es mag sein, aber ich sage, dass es nicht unbedingt ist.
@Daenyth nicht unbedingt jeder von ihnen. Sobald Sie die maximale Entfernung überschritten haben, befindet sich möglicherweise eine Reihe von Pixeln im gleichen Winkel von der Mitte, von denen vernünftigerweise angenommen werden kann, dass sie identisch sind
@AndreasBonini, Weitere Tests scheinen darauf hinzudeuten, dass es so präzise ist, dass ein einzelnes Pixel selbst über verrückte Entfernungen zu unterschiedlichen Ergebnissen führen kann - siehe die neuesten Änderungen meiner Antwort.
Dies ist eher ein Beispiel für Chaos (winzige Änderungen der Eingabe, die zu großen Änderungen des Ergebnisses führen) als für Nichtdeterminismus


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...