Strange code in random move generation

[dsmic]

Sorry, but I found

  int r=rand->getRandomInt(board->getPositionMax());
  int d=rand->getRandomInt(1)*2-1;
  for (int p=0;p<board->getPositionMax();p++)

which seems to be strange. What was the idea of int d, as in this way it is allways -1...

[Francois van Niekerk]

You are correct. It should be:

int d=rand->getRandomInt(2)-1;

The idea is to choose a random location and direction for searching.

[dsmic]

I see.

Were you following a impementation from a paper here? Reason I ask is:

This way touching moves in horizontal direction are overestimated by a factor depending on group size in this direction....

Might be not the very best random moves

[Francois van Niekerk]

No, not from a paper.

I agree, not 100% uniform random, although the few random tries before this are meant to improve that. Just couldn't think of a better way to do this very fast at the time.

[dsmic]

OK,

the random tries before help for sure. I did not understand them and thought it was for performance reasons:(

maybe a prime which is not dividing the board size might be better, but probably not too important.

[dsmic]

This is what I try: but will be difficult to check for improvenment :(

const int directions[6]={-4,-2,-1,1,2,4}; //no even board sizes, therefore powers of 2 should be safe
  int rp=rand->getRandomInt(board->getPositionMax());
  //int d=rand->getRandomInt(2)*2-1;
  int d=directions[rand->getRandomInt(6)];
//fprintf(stderr,"d= %d\n",d);
  for (int p=0;p<board->getPositionMax();p++)
  {
    //int rp=(r+p*d);
    rp+=d;

[Francois van Niekerk]

I am very hesitant to implement such a method for three reasons:

1. It is only a better workaround, instead of a "proper" solution.
2. Oakfoam performs no check to make certain that no even board sizes are used (it is valid).
3. Remember that the board representation uses "OFFBOARD" positions which drastically alter the number of coordinates, possibly making 9x9 or 19x19 a problem.

[dsmic]

ups, you are absolutely right, especially point 3! I once again forgot to take into account :(

for point 1: I would not call it a workaround, but a improvenment of the pseudo random numbers. And with this approach we need pseudo random numbers, which cover all points within PositionMax.

Therefore steps sizes which have no common divisor with PositionMax are the possible ones. Especially not using 1 might be important, as the board has a very high correlation with 1 (due to the group rules) I would expect.

[dsmic]

Interestingly I just checked: PositionMax is 1+(s+1)*(s+2)

which is a prime in case of 19x19 and 13x13 :)

So in this cases one could use just any number smaller than PositionMax to iterate through the board. It might be even an idea to do the NextPrime(PositionMax) and cound >=PositionMax as invalid move.

I think this way the random numbers would be quite good?!

[Francois van Niekerk]

To be exact, you need numbers that are relatively prime with positionMax (have a greatest common divisor (GCD) of 1).

If a wide selection of numbers are generated and cached somewhere, it could be quite a fast, but good solution.

[dsmic]

Yes, I wanted to do it more easy:

do not take PositionMax, but the next prime after PositionMax. If you want to produce random number from 0 to NextPrime(PositionMax) than every number smaller than NextPrime(PositionMax)-1 would be relatively prime with NextPrime(PositionMax)!

Now we only have a few numbers, which are not valid moves and we drop it as we drop all not valid moves during this generation...

We only have to have a list of NextPrimes for all possible boardsizes, say 3 to 31 or so (and put a warning to our 1+(s+1)*(s+2), that this depends on this list from now on:)

[Francois van Niekerk]

Something like you suggested sounds good, just remember that this is still not uniform random.

[dsmic]

hmm, it is not? I can not prove it is, but I thought it should be?!

  int rp=rand->getRandomInt(board->getPositionMax());
  int NextPrime=board->getNextPrimePositionMax();
  int d=rand->getRandomInt(NextPrime);
  //fprintf(stderr,"d= %d rp= %d np= %d\n",d,d,NextPrime);
  for (int p=0;p<NextPrime;p++)
  {
    //int rp=(r+p*d);
    rp+=d;
    // only positive d here: if (rp<0) rp+=NextPrime;
    if (rp>=NextPrime) rp-=NextPrime;
    if (rp<board->getPositionMax() && doapproachmoves)
      this->replaceWithApproachMove(settings,board,col,rp);
    if (rp<board->getPositionMax() && validmoves->get(rp) && !this->isBadMove(settings,board,col,rp,params->playout_avoid_lbrf1_p,params->playout_avoid_lbmf_p, params->playout_avoid_bpr_p, passes, NULL, 0, critarray))

the steps are uniform random and the starting point is uniform random, what might be the reason vor the result being not uniform random?!

[Francois van Niekerk]

A "simple" proof that it isn't uniform random: uniform random selects from n! orderings of n moves, whereas this approach only has 2*n*n orderings (you can modify your proposed code to either add or subtract the value for the factor of 2).

Another, perhaps more straight-forward, proof: in the array {0, 1, 2, ..., 100}, your approach cannot result in the sequence {31, 0, 1, 2, ..., 29, 30, 32, 33, ..., 100} (referring to the sequence the moves are considered in).

[dsmic]

your are right, the sequence it produces in one try is not truely random, but that is not what we need.

We only need the first valid move to be uniform random!

[Francois van Niekerk]

Good point. I'll have to think about it a bit more and get back to you.