Prédire un évènement aléatoire

[Maks]

Salut à tous, j'ai besoin de quelques pistes pour résoudre un problème

Rapidement, un personnage peut effectuer une attaque critique. Imaginons qu'actuellement on utilise un random pour savoir si une attaque est critique (une chance sur 10) côté serveur.

Maintenant imaginons qu'on veuille le prédire côté client. La solution du random tombe à l'eau, car on ,ne pourra garantir qu'il sera le même côté client comme côté serveur. Se baser sur le timestamp apparait également difficile étant donné le temps de latence.

La solution par défaut étant d'estimer qu'il n'y a jamais de coup critique côté client, et de corriger si besoin est par le serveur ensuite.

Des idées ?

[Xenos]

Si c'est aléatoire, y'a aucune possibilité de le prévoir...
Se "baser sur le timestamp" ne changera rien, car les algorithmes pseudo aléatoires bien foutus sont capables de changer du tout au tout si on a ne serait-ce que 1ms d'écart. D'autant que certains algorithmes, avec un peu de pirouettes, peuvent avoir des aléatoires différents même si les algorithmes ont été initialisés avec le même timestamp (par exemple, à chaque initialisation, un compteur est incrémenté et toute nouvelle initialisation utilisera non seulement le timestamp comme seed de départ, mais aussi la valeur du compteur donc le même timestamp mais avec un compte différent ne produira pas la même séquence aléatoire).

Donc, non, pas d'idée, car le problème, "prédire un truc aléatoire" me semble tout simplement insolvable
Tout ce qu'on pourrait faire avec l'aléatoire, ce sont des statistiques...

[Maks]

Oui voilà l'idée c'est d'avoir un évènement aléatoire mais qui n'est pas basé sur une donnée aléatoire. Par exemple le timestamp de la dernière action certifié par le serveur, faire la somme de ses chiffres et une comparaison qui déterminera si le prochain coup est critique. J'imagines que les MMORPG qui utilisent la prédiction ont un méchanisme du genre ?

[Xenos]

D'accord, cela renverse le problème:
il ne s'agit donc plus de prédire un évènement aléatoire mais de donner une apparence aléatoire à un évènement prédictible.

Une première possibilité:
Coté serveur:
Choisir un algorithme pseudo aléatoire répandu (mersenne twister par exemple)
Choisir un seed pour cet algorithme (seed aléatoire si on veut)
Générer N valeurs et les stocker

Ensuite, il suffit d'envoyer au client le seed utilisé, l'algorithme choisi (ca, normalement, c'est "envoyé" au client via le code du javascript lui-même, en d'autres mots, il faut que l'algorithme pseudo aléatoire soit le même coté client et serveur) ainsi que le n° du dernier nombre tiré.
Connaissant ces données, le client peut générer la même liste que le serveur, et sachant quel est le dernier n° tiré, le client est capable de savoir quel sera le prochaine n° tiré.
On peut alléger le coté serveur en ne stockant que le seed et le n° du dernier tirage: ainsi, pour trouver le nombre suivant, il suffit d'initialiser l'algorithme pseudo aléatoire avec le seed stocké, et de faire défiler (n°) tirages aléatoires pour trouver le prochain nombre.

Exemple:
Coté serveur, je décide que d'utiliser mersenne twister. Je choisis le seed 1000 (lui-même aléatoire).
Le n° du dernier tirage est -1, puisque j'ai jamais fait de tirage.
J'envoie au client le couple (1000,-1), pour qu'il sache que le seed est 1000, et le dernier tirage -1.
Le client initialise l'algorithme mt_srand(1000). Il génère ainsi une grille de 100 nombres aléatoires:

Code :

0    753084335
1    1694858333
2    246975523
3    1310787424
4    115944203
5    2115752409
6    1123256280
7    774816128
8    283560872
9    327653942
10    1684423386
11    2130080352
12    87423252
13    1398537922
14    852968622
15    1775019291
16    500647570
17    1829113182
18    1807624438
19    919118209
20    1707760099
21    497724395
22    541247650
23    1947017330
24    1299836476
25    129545465
26    391392911
27    2113765122
28    543668698
29    211595471
30    2007229881
31    1755136974
32    236539833
33    1974903052
34    2045788262
35    305456159
36    1999615310
37    525128298
38    1248272920
39    1414251589
40    2097045177
41    1023438599
42    49866472
43    1753044770
44    729366374
45    516923397
46    624905388
47    911176403
48    777125072
49    358878892
50    2067115247
51    288349692
52    305756667
53    123643954
54    728438645
55    903863614
56    491393804
57    346019037
58    1189893294
59    1715179299
60    1900722616
61    44501693
62    217532971
63    843651190
64    22380431
65    2085033039
66    160109366
67    587035839
68    1612445686
69    554291827
70    1851511841
71    12113357
72    1498782743
73    1510943389
74    855138471
75    1600639048
76    1896490466
77    1988392749
78    1751168120
79    479794419
80    1209522032
81    429079554
82    38962237
83    1185711533
84    1484851500
85    333850514
86    1129654207
87    384589825
88    1864523984
89    66560555
90    224174178
91    189440053
92    181159731
93    682638453
94    1981280807
95    1375821209
96    2056964493
97    1465893082
98    941828119
99    792112746

Maintenant, un coup est porté. Le client sait que le dernier nombre est -1, et il sait donc que le serveur va tirer 753084335.
Le serveur exécute le code suivant:

Code PHP :

<?php

    //__LAST__ est le n° du dernier tirage effectué, ici, -1.

    mt_srand(1000);

    for ($i=0;$i<=__LAST__;$i++)

        mt_rand();

    return (mt_rand());

?>

[Maks]

J'aime bien l'idée de la liste pré-définie
Tout bêtement on pourrait réduire la liste à chaque coup porté. Cependant l'ordre d'arrivée des packets n'est pas toujours garanti (problème des packets perdus avec le protocole TCP).
Dans mon cas, il n'est pas possible d'"abandonner" réellement un combat (sauf en fuyant et encore)

Merci pour cette piste en tout cas

[Xenos]

?
La liste n'est jamais transférée. Seul le couple (seed, n°) est envoyé au début du combat... Voir même, tu n'envoies pas le n° si tu crées un nouveau seed pour chaque combat.
Et si le problème, c'est l'ordre d'arrivée des paques TCP envoyés par le client et disant "je porte un coup", il te suffit de numéroter le paquet avec le n° du coup selon ce que le client demande. Ainsi, le serveur sait quel est le n° de coup et donc le n° aléatoire associé.

[atra27]

Au passage, avec tcp les packets sont toujours reçus, et toujours dans l'ordre
pas de soucis de packets perdus/en retard/dupliqués.
tu confond avec udp (qui ne garanti, ni la réception, ni l'ordre, ni le nombre)

[niahoo]

+1 atra27, mais le problème est que en javascript tu peux faire des appels concurents (genre un DoT et en prallèle des coups) tandis que côté serveur tu peux tout traiter dans une file. là l'ordre d'arrivée peut varier (car on est à un bien plus haut niveau que la couche TCP). ça dépend de l'implémentation. Si c'est comme çà, on peut mettre les appels à la file côté JS et c'est réglé. ou numéroter les coups oui.

mais sinon la solution me paraît simple et élégante. Ensuite de savoir si on tire à l'avance X nombres pour le combat ou bien si on les tire un par un ne change pas grand chose.

[Maks]

Au passage, avec tcp les packets sont toujours reçus, et toujours dans l'ordre
pas de soucis de packets perdus/en retard/dupliqués.

J'avais lu un article qui semblait dire le contraire : http://blog.artillery.com/2012/06/websoc...mance.html (à propos des paquets perdus)

[atra27]

Après une lecture rapide Je ne vois pas ou cela est dit mais si ça y est c'est totalement faux

tcp a été conçu pour transmettre un flux, donc ordonné et continu.
tcp fonctionne en mode connexion et est plus long à transmettre car s'il manque un packet, touts les suivant sont discardés et doivent etre retransmis

udp à été conçu pour transmettre des datagrammes, ici chaque packet à sa propre existence, peut arriver ou non, etre dupliqué ou non, et les datagrammes peuvent emprunter des chemins différents (ordre non garanti)
udp ne nécessite pas de connexion entre emetteur et recepteur

pour les jeux d'action, on privilégiera udp pour la simple raison que seuls les données actuelles comptent, et peut importe si une est retardée car la suivante la remplace aussitôt

bon après udp n'est pas supporté par ws donc ça règle la question.

pour la question des requêtes parallèles, cela permet de ne pas attendre la réponse avant d'envoyer la seconde. par contre le navigateur optimise surement en utilisant la meme connexion, donc la réponse arrivera dans le meme ordre que les demandes. mais cela dépend aussi de l'implémentation du navigateur
De plus je doute qu'en js on ai le niveau de controle suffisant pour vérifier le nombre de connexions et prévoir cet ordre à coup sur.

désolé pour les fautes, j'écrit depuis mon telephone dans un aéroport donc c'est pas top ^^
A dans 8heures les gars (et filles)