Question:
Angry Birds est-il déterministe?
Thomas Bonini
2011-12-29 22:30:31 UTC
view on stackexchange narkive permalink

En essayant d'obtenir 3 étoiles sur les niveaux les plus complexes (ceux avec beaucoup d'entités destructibles), j'ai remarqué que même après avoir joué au même niveau plus de 50 fois, en faisant toujours la même chose, je n'ai jamais vu la même chose résultat final. Quelque chose se passe toujours différemment.

La même entrée aboutit-elle toujours au même résultat, ou y a-t-il un facteur aléatoire?

Comment pouvez-vous être sûr que l'entrée que vous donnez est identique à 100%?
Une entrée parfaite peut être donnée via l'émulation d'un téléphone, des programmes spéciaux ou, simplement, la version de bureau du jeu avec la souris, comme l'a fait l'agent86.
Cinq réponses:
#1
+465
agent86
2011-12-29 22:47:10 UTC
view on stackexchange narkive permalink

L ' algorithme est déterministe, mais on peut soutenir que le résultat global du lancement d'un oiseau est effectivement non déterministe car il repose sur une entrée utilisateur (extrêmement sensible).

Pour tester l'algorithme et l'effet des entrées utilisateur, j'ai utilisé la procédure suivante:

  • Charger la version Google Chrome de Angry Birds
  • Niveau de charge 1-1
  • Ramenez la souris sur une coordonnée XY spécifique. (Cela dépassait le point de "tirage complet" de l'oiseau.)
  • Relâchez l'oiseau et attendez que le jeu atteigne un état stable.

Pour mesurer ma coordonnée XY, j'ai ouvert une fenêtre Chrome d'arrière-plan et l'ai parcourue jusqu'à cette page. J'ai aligné les deux fenêtres pour que je puisse voir les positions X et Y de la souris tout en étant toujours capable de provoquer quelque chose lorsque j'ai relâché l'oiseau. J'ai aligné le curseur de ma souris avec le coin inférieur gauche de la boîte autour de ces deux nombres, puis relâché. J'ai alors noté la position du curseur de ma souris (car l'affichage ne se met à jour que lorsque la souris n'est pas relâchée et que le curseur est au-dessus de cette fenêtre), puis j'ai noté le score résultant dans Angry Birds. Si vous rencontrez des problèmes avec le positionnement exact de la souris, vous pouvez essayer une option d'accessibilité proposée par votre système d'exploitation, par exemple, les touches de la souris sous Windows.

J'ai le même score, tant que mon curseur était au exactement au même endroit que lors des itérations précédentes.

Avant de proposer un banc d'essai amélioré qui me permettait de mesurer la position de mon curseur le pixel, j'ai exécuté cette expérience environ 10 fois, en utilisant un point de référence dans l'image d'arrière-plan du jeu. J'ai obtenu des scores en tirant le premier oiseau qui variait entre 8 000 et 11 000 points. En utilisant la stratégie de test améliorée, si j'étais distancé d'un seul pixel, je pourrais m'attendre à des différences de score comprises entre 150 et 500 points.

Je noterai que le curseur se trouvait au-delà du bord de la zone de jeu , à l'extérieur de la fenêtre du navigateur, bien au-delà de la distance maximale à laquelle l'oiseau peut être reculé, et j'ai toujours remarqué des différences lors du déplacement de mon curseur même un seul pixel.

De plus, j'ai pris des captures d'écran pour un cas extrême où mon curseur était sur un moniteur différent que la fenêtre du jeu, et a exécuté plusieurs itérations où j'ai gardé mon curseur au même endroit ou l'ai légèrement déplacé. D'après mes calculs (basés sur la mesure de la distance à partir des captures d'écran), le jeu a pu créer un résultat différent (score 32960 vs 31520) basé sur une différence de hauteur d'un pixel (544 vs 545 pixels) sur une distance d'environ 1284 pixels de largeur. Cela équivaut à une différence angulaire de 0,03 degrés.

Je dirais que pour toutes fins pratiques, vous pouvez vous attendre à utiliser la même stratégie générale au même niveau à plusieurs reprises et à espérer des résultats extrêmement variables. Le niveau de sensibilité des commandes est si extrême qu'il n'y a aucun moyen pratique de lui faire faire la même chose deux fois. Ceci est exacerbé par le fait que si vous jouez sur un écran tactile, il serait extrêmement difficile de reproduire les mêmes mouvements jusqu'au pixel individuel.

Un pixel * peut * facilement signifier une grande différence de score. Ce n'est pas une réponse à la question de savoir si c'est déterministe ou non; vous devez être certain que votre entrée est identique.
Même dans les scénarios déterministes, une minuscule différence dans l'état de départ peut entraîner une énorme différence dans l'état final. Elle s'appelle [théorie du chaos] (http://en.wikipedia.org/wiki/Chaos_theory).
@MyrddinEmrys, comme je l'ai mentionné que je prévoyais de le faire, j'ai relancé l'expérience avec la précision des pixels. J'ai trouvé que les dégâts étaient les mêmes, si j'étais aussi précis. Je dirais que pour toutes les raisons pratiques de jouer au jeu, les commandes sont si exactes que vous pouvez vous attendre à ce que le comportement final du système soit effectivement non déterministe pour tout scénario d'utilisation "normal" des entrées humaines. Le jeu lui-même est cependant déterministe.
Juste à noter, en raison de simples secousses constantes dans la main, il est effectivement impossible pour un humain de générer exactement la même entrée tactile. La réalité est le facteur aléatoire, pas Angry Birds, comme vous l'avez constaté.
Angry Birds: un jeu millimétrique sur un appareil centimétrique. Exaspérant.
Si vous voulez essayer cette expérience, vous pouvez [installer mon usercript] (https://gist.github.com/raw/1536489/angrierbird.user.js). Il ajoute des boîtes qui suivent la position exacte du curseur sur la page Angry Birds. Un aperçu du script est disponible [ici] (https://gist.github.com/1536489).
@splatteredbits c'est à peu près mon impression
Cher agent86, vous avez écrit "J'ai obtenu des scores en tirant le premier oiseau qui variait entre 8 000 et 11 000 points." Est-il possible d'exécuter le test avec la version actuelle et de voir si les scores sont systématiquement plus élevés?
@GilKalai Vous ne pouvez pas comparer différents niveaux comme ça, cela dépend entièrement de la destination du test.
Maintenant, la question est ... sur les niveaux avec des entités semi-dynamiques (comme les canons laser et les plates-formes mobiles sur * Angry Birds Star Wars *), en quoi est-ce déterministe?
Cette réponse est à la limite d'une expérience scientifique.
Attends, tu as fait tout ça pour Arquade?!+342!
Je pense que la nature du jeu est chaotique.Un système chaotique est un système déterministe, mais de petits changements dans les conditions initiales ont des changements massifs dans les résultats.
#2
+196
Pubby
2011-12-30 01:32:07 UTC
view on stackexchange narkive permalink

Angry Birds utilise la bibliothèque Box2D pour la physique.

Box2D est-il déterministe? Pour la même entrée, et le même binaire, Box2D reproduira n'importe quelle simulation. Box2D n'utilise aucun nombre aléatoire et ne base aucun calcul sur des événements aléatoires (tels que des minuteries, etc.).

Cependant, les gens veulent souvent un déterminisme plus strict. Les gens veulent souvent savoir si Box2D peut produire des résultats identiques sur différents binaires et sur différentes plates-formes. La réponse est non. La raison de cette réponse a à voir avec la façon dont les mathématiques en virgule flottante sont implémentées dans de nombreux compilateurs et processeurs. Je vous recommande de lire cet article si vous êtes curieux: 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

C'est génial (merci de vérifier avec la source); Par souci d'exhaustivité, avez-vous une référence selon laquelle Angry Birds utilise Box2D? Et d'où avez-vous tiré cette citation?
@MarkTrapp http: // www.geek.com / articles / mobile / box2d-creator-ask-rovio-for-angry-birds-credit-at-gdc-2011032 / et http://en.wikipedia.org/wiki/Box2D
Et je parie que le FPS physique varie également, en raison de nombreux facteurs (pas assez de CPU, surchauffe, défauts de page, etc.), affectant ainsi la «précision» de la simulation. :)
Le genre d'ambiguïté de la deuxième déclaration; ce que je suppose, c'est que si vous exécutez la même simulation sur plusieurs architectures, vous n'obtiendrez peut-être pas exactement le même résultat, mais par plate-forme, chaque simulation fonctionnera de la même manière à chaque fois.
@muntoo ce n'est pas nécessairement vrai, car les développeurs peuvent faire exécuter le jeu le même nombre d'étapes de simulation même à des fréquences d'images inférieures. En ce qui concerne les erreurs de processeur réelles, cette possibilité est généralement ignorée dans les jeux car elle est si rare. Si vous êtes intéressé par le sujet des simulations déterministes, vous pouvez en savoir plus sur [gamesfromwithin blog] (http://gamesfromwithin.com/casey-and-the-clearly-deterministic-contraptions) ou simplement sur Google. :)
@agent86 Je changerais votre formulation en "[...] mais par plate-forme et ** par version Box2D ** chaque simulation fonctionnera de la même manière à chaque fois." (cette partie "même binaire" dans le premier paragraphe semble l'indiquer).
@JoãoPortela, bon point. Je supposais que "release" n'était pas une variable autorisée à changer dans ce cas.
Je ne comprends pas le premier paragraphe de la qoute. Alors Box2D est-il déterministe ou non?
@Jake Oui, c'est déterministe mais avec les limitations mentionnées dans le deuxième paragraphe.
Encore confus. Pourquoi dit-il "Box2D reproduira TOUTE simulation" plutôt que "MÊME" simulation? J'écris une simulation de lockstep de client de serveur et exécutant 2 du même client.exe donne la même simulation seulement s'il n'y a pas de collisions.
@Jake Je ne suis pas sûr, essayez peut-être Stack Overflow.
#3
+34
Matthew Read
2011-12-30 00:26:43 UTC
view on stackexchange narkive permalink

Certains niveaux sont sujets à des explosions aléatoires peu de temps après le début du niveau, et certaines briques peuvent tomber d'elles-mêmes avant même que vous ayez jeté un oiseau. Ces événements se produisent rarement, mais au moment où vous avez joué trois étoiles à chaque niveau de chaque jeu, vous l'aurez probablement vu à plusieurs reprises, comme moi.

Je m'attendrais à ce que cela se produise à cause du timing problèmes, probablement liés au threading. Je suis tout à fait sûr que si vous faisiez un test où vous chargiez chaque niveau une douzaine de fois et attendiez trente secondes, vous vous retrouveriez avec un score non nul au moins une fois. À la lumière de la réponse de Pubby, je ne peux que supposer que l'application Angry Birds ne fournit pas toujours la même entrée aux fonctions Box2D au début d'un niveau.

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

J'ai joué sur Facebook en utilisant un enregistreur de macros. J'ai démarré l'enregistreur, je suis allé à la fenêtre des oiseaux en colère, puis j'ai fait un zoom arrière et j'ai joué les deux premiers oiseaux. J'ai ensuite arrêté l'enregistreur. À CHAQUE fois, la souris est allée aux pixels exacts et a été relâchée avec exactement la même puissance, etc. Il le fallait, car le mouvement de la souris enregistré fait la même chose à chaque fois, pixel pour pixel. A chaque fois j'ai un score différent, et pas à chaque fois le même nombre de porcs tués etc. Ce jeu EST incohérent

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

J'ai fait 10 tests, tirant au même point à chaque fois (également Chrome Angry Birds, niveau 1, comme dans les tests d'agent86).

Red Crosshair of test spot

Je n'ai jamais reçu le même score deux fois, en prenant soin de tirer exactement au même endroit et de le faire à peu près dès le début du niveau. Je pense qu'Angry Birds n'est pas du tout déterministe.

C'est assez facile à expliquer: il a été conçu pour fonctionner sur de petits écrans tactiles. S'il était déterministe, les utilisateurs pourraient facilement répéter les mouvements en raison de la précision limitée du périphérique d'entrée. Cela pourrait être mauvais, car leur appareil pourrait littéralement ne pas avoir la précision nécessaire pour viser exactement l'angle et la puissance qu'ils souhaitent. En le faisant légèrement secouer les résultats, et grâce à la saisie d'un «doigt», les utilisateurs ne remarqueraient pas le manque de précision, et ils ne seraient pas non plus frustrés de ne jamais pouvoir prendre la photo souhaitée.

Le test supplémentaire de l'agent86 indique que je pourrais bien me tromper. Je ferai un nouveau test quand je rentrerai à la maison, car j'étais assez certain d'avoir placé mon curseur avec précision.
Je crois que tu as tort. L'écran tactile rend en fait extrêmement difficile d'obtenir la même entrée à chaque fois. Par exemple, l'iphone a 614400 pixels. Chacun de ceux-ci produirait un résultat différent.
@Daenyth: êtes-vous sûr que la précision de la résolution d'entrée est de 1 pixel? C'est peut-être le cas, mais ce que je dis, c'est que ce n'est pas nécessairement le cas.
@Daenyth pas nécessairement _chacun_ d'entre eux. Une fois que vous avez dépassé la distance maximale, il peut y avoir un ensemble de pixels au même angle par rapport au centre qui pourrait raisonnablement être supposé causer des
@AndreasBonini, D'autres tests semblent indiquer qu'il est si précis qu'un seul pixel peut provoquer des différences dans les résultats, même sur des distances folles - voir les dernières modifications apportées à ma réponse.
Ceci est un exemple de chaos (de minuscules changements dans les intrants menant à d'énormes changements dans les résultats) plutôt que de non déterminisme


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...