[FreecivDev] Re: Two patches
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Jeff Mallatt <jjm@xxxxxxxxxxxx> wrote:
> At 2000/06/28 16:28 , Kero van Gelder wrote:
> >First patchs improves the shuffle_players() to perfect randomness (it
> >was close, but n! is not a perfect divisor of n^n), save the
> >randomness of my_rand().
>
> I don't understand this patch. The new code seems to me to have the same
> effect as the old code.
Patch was:
diff ru freeciv/server/civserver.c dev/server/civserver.c
 freeciv/server/civserver.c Sun Jun 25 12:26:37 2000
+++ dev/server/civserver.c Wed Jun 28 20:31:24 2000
@@ 844,7 +844,8 @@
}
for(i=0; i<game.nplayers; i++) {
 pos = myrand(game.nplayers);
+ /* for each run: shuffled[ <i ] is already shuffled [Kero] */
+ pos = game.nplayers  myrand(game.nplayers)  1;
tmpplr = shuffled[i];
shuffled[i] = shuffled[pos];
shuffled[pos] = tmpplr;
I believe Kero has the right idea, and the current code is wrong,
but Kero's implementation is off. Patch should be: (untested)
 for(i=0; i<game.nplayers; i++) {
+ for(i=0; i<game.nplayers1; i++) {
 pos = myrand(game.nplayers);
+ /* for each run: shuffled[ <i ] is already shuffled [Kero+dwp] */
+ pos = i + myrand(game.nplayersi);
That is:
 current code goes to each index, and chooses random one from
all indicies;
 new code goes to each index (except last), and chooses random
one from remaining ones (ie, this index and higher indices).
The difference is subtle but there. To elicidate Kero's explanation,
consider the case where nplayers==3. With old code, get
rand(3)*rand(3)*rand(3) = 27 equally likely outcomes, many of which
are diplicate orderings. In fact there are only 6 unique orderings.
Since 6 does not go into 27, these six orderings cannot be equally
likely. QED. (Well, that shows the old method is wrong; the proof
that the new method is right is left as an exercise ;)
 David, BSc etc...

