• Advertisement

Archived

This topic is now archived and is closed to further replies.

Co-operative Random Number Generator?

This topic is 5269 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

OK, I''m probably going to be making some sort of peer to peer game soonish, and I was wondering about a good way of doing a co-operative random number generator. The basic idea being that the two computers will generate random numbers that cannot be tampered with to the benifit of either player. Any ideas? It''s pretty tricky. If you assume both machines are hostile to one another, if your random number is generated by your own machine, then the opponent could be generating favourable random numbers continuiously. If the random number for you is generated remotly, it could be generated to be bad for you. If the generation is shared between machines, then a machine could get the segment from the oponent, and generated their own segment that would still create the desired result for them. One idea is having a "random number list" that is stepped through. However this is not nearly random enough. Perhaps a variation on that theme?
Free Game: Yet Another Falling Block Game

Share this post


Link to post
Share on other sites
Advertisement
However you do it, it will be open to tampering, even if it was just modifed to completely ignore the random generator and always choose the "best" value.

but if you really want to do it, how about (for example)

both machines generate a random 64 bit number

each machine sends that 64 bit number to the other machine

each machine XOR''s the 2 numbers together ( "^" operator in C/C++)

one machine uses the top 32 bits of the result, the other uses the bottom 32 bits, also each machine then knows what the other got so could check the result to try to detect cheating.

Share this post


Link to post
Share on other sites
Perhaps if each machine generated a random number, sent it to the peer, and the peer XORed them together for the final number?

I wrote a littlle program which generates two random numbers and XORs them together - results over 10k tries show that the numbers are about as random as can be expected; 100 possible numbers, all numbers occured between 80 and 123 times, most fall between 90 and 110.

EDIT: Crap, Narcist beat me to it while i was trying out my theories...

Member of the Un-Ban nes8bit Association (UNA) (to join put this in your sig)

We are at war with Iraq. We have always been at war with Iraq. I love Big Brother.
- DakeDesu

[edited by - Valderman on November 14, 2003 9:05:41 AM]

Share this post


Link to post
Share on other sites
> ... some sort of peer to peer game ...
> ... co-operative random number generator.

If the random number generation is not the same across peers, each peer's game simulation will diverge and things start to get out-of-sync; typically, orders from opponents become inconsistent with the your game state. Exchanging game state CRCs at some set frequency can help detecting cheaters as the game evolves. Check Terrano's article.

-cb

[edited by - cbenoi1 on November 14, 2003 10:07:24 AM]

Share this post


Link to post
Share on other sites
why dont you just make your own random number generator and seed both systems with the same value, and every once in a while check that they are producing the same "random" values?

that way you wouldn''t need to worry about the network communications performance so much, as soon as you detect an out-of-sync random number, assume they have cheated, and disconnect the cheater. but they wouldnt actually need to exchange data continuesly to generate the ''random'' values.

Share this post


Link to post
Share on other sites
Something you *could* do would be this:

Assuming it is a 2-player game, have each client generate their their own random number.

Next, send the chosen number to the other person.

Then, have the program randomly pick which of the random numbers to use on the client.

-Greven

Share this post


Link to post
Share on other sites
if you really care about cheating, the only safe thing to do would be to seed them both with the same number and check that they are the same (as aboeing said). the other methods can still be cheated.

Share this post


Link to post
Share on other sites
Could you maybe have your programs get their random numbers directly from one of the many online random number generators out there, that give out random numbers as a webservice or something?

Share this post


Link to post
Share on other sites
@AndreTheGiant

Sounds really slow, and wouldn't work in many situations you have peer to peer connections (lan/lan party w/o net access, or, you don't want the things using net access.)

XOR thing, sounds bad - all one would have to do is XOR their desired value by the 1st value, and send that new value off, then when both sides XOR it it would have player 2's original value. You need to have some sort of random number generator, which takes a seed, and doesn't have to be reseeded (hopefully, not a requirement though)
I would check out the mersenne twister, there was a cotd at flipcode awhile ago, or you could just search for it on google. It has a period 2 to the 19937 power, minus 1. It's also fairly fast.

-Michael

Someone mentioned storing calculated positions based on game physics, and checking to make sure the other player was within the bounds - this sounds like the best way to make sure there isn't a cheater.


[edited by - thr33d on November 14, 2003 1:22:21 PM]

Share this post


Link to post
Share on other sites
Lets look at the problems:

You want to have random number generation. Lets assume it''s for a turn based game like Risk (the roll of the dice determines the outcome of battles). This means there are two ways to cheat:

*By modifiying the "random" numbers to ones that are most favorable.

*By knowing the "random" numbers in advance (such as if they are from a list or from a seed known at the beginning of the game) and using the knowledge to make better moves (only attacking when you know the outcome will be in your favor).


Obviously you can''t have any list or a predefined seed, because players can use that to completely override the "random" elements by knowing what they are in advance.

The other option brought up here was to have both players send a value, and have those values combined to form a single random value. However this opens it up again to number tampering. One player can wait until the other player has sent his piece, then figure out what he should send in order to make the outcome he wants (even with a complex algorithm that could not be reversed, a machine could still try random values for X seconds, then send the value which gave the best result).


So here is a new option which allows for a more secure game:

At the beginning both machines select seperate seed values, which will be used with the same random number generator. These values are secret until the end of the game, at which point both players will send their seed value. Each time a random value is required both players send the next value from their seed and it is combined as described above (the complexity of trying to come up with a valid seed number at the end becomes infinitely complex as the number of values sent goes up). This can also be further secured (assume that your random generator was crypto analysed and found to have a flaw such that you could determine a seed that would have given the values you sent) by having each machine generate 10 or 100 (some amount that would be used up in 1 or 2 minutes of play) random values at a time from the seed and cache them. It would then send an MD5 hash of the entire list before any values from the list where sent. Once the list was exhausted both players could check that the values matched the hash (at the moment MD5 cannot be reversed, and there is no easy way to come up with matching values for an MD5 list)

Share this post


Link to post
Share on other sites

  • Advertisement