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.

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]

> ... 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]

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

@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]

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)