search

jinnaiyuu / Hash-Distributed-Astar

Hash Distributed A*
https://sites.google.com/site/yuujinnaishomepage/home/parallel-search
MIT License
3 stars 1 forks source link

TODO: Check the fairness of rand() function #33

Closed jinnaiyuu closed 9 years ago

jinnaiyuu commented 9 years ago

Obviously rand() function is not random. It tries to be random, but it is not.

Our algorithm is pretty sensitive to the randomness of the random function. If there is some kind of pattern, then the outcome of the algorithm would be distorted. The "bind" of the HDA* might be caused by this randomness.

Let's try out other random function such as boost::rand.

jinnaiyuu commented 9 years ago

Parallel Random generator http://www.sitmo.com/article/parallel-random-number-generator-in-c/

jinnaiyuu commented 9 years ago

Mersenne twister random It is implemented in C++11. http://en.wikipedia.org/wiki/Mersenne_twister

jinnaiyuu commented 9 years ago

boost random A tons of randoms http://www.boost.org/doc/libs/1_56_0/doc/html/boost_random/reference.html#boost_random.reference.generators

jinnaiyuu commented 9 years ago

Very deep discussion about random generators. http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf

jinnaiyuu commented 9 years ago

Trying

  1. rand() in stdio
  2. std::uniform_int_distribution

Seems the second works better.

jinnaiyuu commented 9 years ago

hmm, seems it is NOT fair in the size of open list. Is it because the distribution itself is uneven, or just because of random walk?

Let's try out very very simple experiment with f(x) = (seed + 1) mod tnum

jinnaiyuu commented 9 years ago

Well, std::uniform_int_distribution provides pretty well random function.

Also, the unevenness do persist even if the hash function is f(x) = (seed + 1) mod tnum

jinnaiyuu commented 9 years ago

Assume that the distribution of the work is even with random hash function. Then, what is the cause of unevenness? Each node has different size of job. Some is just a duplicate while other generate three processor nodes. If this is the cause of the unevenness, then the fact that the bind would not go huge is resonable as it is NOT because of the hash distribution. It is not systematic unevenness, rather it is random unevenness. Thus, it might not be so profitable to justify the distribution by outsourcing.

jinnaiyuu commented 9 years ago

Results

cyclic distribution < random (std::uniform_int_distribution) < Zobrist Hashing

Therefore, there is a chance of improvement in Zobrist Hashing. However, the difference in evenness is slight that it might be able to just neglect. Even if we manipulate them to even out, it might not make a big impact.