Re: Regarding the Random Number Seed

[Klaas van Schelven]

Hi all,

Here is my attempt at explaining pseudorandomness as it is used in Tabbie. Pseudo Random means: to a casual observer it looks random, but a mathematic genious may crack the code because it's really just a fixed list.

Say for this example that we use the digits of the number Pi as our pseudo random numbers.

{3}.
1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273

to ease our example we will now hussle up a list of 10 elements ABCDEFGHIJ
first we take the first two numbers: 1 & 4: swap elements 1 and 4: DBCAEFGHIJ
next: 1 & 5: EBCADFGHIJ
9 & 2: EICADFGHBJ
6 & 5: EICAFDGHBJ
3 & 5: EIFACDGHBJ
etc. etc.

Tabbie works like this: first all teams are sorted in order of their standing, and then their team_id. Note that this list will almost certainly be different from round to round. Only one difference is enough to radically change the final outcome of the draw.
The teams are then swapped, only swapping teams that are possible to swap. This is done for a randomly high number of 5000 times. That's 100 lines of PI digits for you.
This is the initial situation, from which the algorithm optimizes in a deterministic way.

So once again: a team is never assigned a "ranking" of any kind.

Klaas

On Dec 5, 2007 6:00 AM, Deepak Jois <deepa...@gmail.com > wrote:

Hi
Two things:

* I was chatting to Ciaran, and he still isnt fully satisfied with the explanation regarding the pseudorandom number generation that happens inside Tabbie. He has this notion that somehow the teams are advantaged/disadvantaged at the beginning of the tournament and that affects how pull up and pull down happens.

Do you think you could attempt a non-geeky explanation that might help allay his fears. I know this random number generation thing is geeky, and I find it difficult to come up with a layman explanation myself,

* Talking about random number generation, this whole issue prompted me to go lookup wikipedia about random number seeds and pseudo random number generation. Here are a few things I observed with relation to Tabbie. Pls correct me if I am wrong

  - in the draw_silver_line method, you use srand(0) to seed the random number generator with 0. Is there any place else you are seeding the random number generator?

  - If not, i would say it is not optimal because any random number generation that happens after seeding it with 0 will be the same for all rounds from 2 to 9? So in effect the randomness is FIXED not only for multiple redraws but also across multiple rounds..

  - Thinking about alternative solutions, along with the requirement of generating the same draw even on multiple redrawing during a round how about
     - a combination of the current date and the current round number as the random number seed. I would say that would increase the pseudorandom properties of the draw generation and also satisfy the requirement of the same draw being generated upon multiple redrawing.

  - Another more optimal strategy is to generate the seed using ( microtime() * 10000000) and cache it for subsequent redrawing.

Deepak

[Deepak Jois]

Hmmm
I would have rather that Klaas did not include the text of the mail I sent, because the second point in the mail actually seems to imply exactly what Ciaran was suggesting, but in actual fact it isnt.

So, please ignore the second point for the benefit of simplicity. I do not think it has any bearing on THIS specific discussion.

Deepak

[Klaas van Schelven]

Hi all,

To amend all possible fears of the situation being the same from round to round we have created a final change:

the starting number (the seed) is now the round number. So: new round, new pseudo randomness.

Klaas