Page 7 of 7

Re: Writing bugs

Posted: Mon Jan 14, 2019 7:32 pm
by Dann Corbit
I use the Mersenne Twister.
I actually think they should use the biggest Mersenne prime because it would offer further improvement.

Re: Writing bugs

Posted: Mon Jan 14, 2019 11:37 pm
by Ras
mar wrote:
Sun Jan 13, 2019 3:08 pm
This is what I get with the ISO multiplier, not much better (still 8 PRNG calls for each byte):
Just out of curiosity, can you please post the corresponding images for MS-rand and ISO-rand using the 8 LSBs from the RNG directly for each byte, i.e. with one RNG call per byte and so that the LSB of the RNG is also the LSB of the greyscale value? The image I had made was something entirely different with (x,y) plots.

Re: Writing bugs

Posted: Tue Jan 15, 2019 9:16 am
by mar
Ras wrote:
Mon Jan 14, 2019 11:37 pm
Just out of curiosity, can you please post the corresponding images for MS-rand and ISO-rand using the 8 LSBs from the RNG directly for each byte, i.e. with one RNG call per byte and so that the LSB of the RNG is also the LSB of the greyscale value? The image I had made was something entirely different with (x,y) plots.
I see, so you generated the image in a different way.
I simply choose a setup where the correlations are clearly visible without having to post very large images.

I could post the images, but MS LCG exhibits no problems up to 512x512 when I map 8 LSBs directly so I assume the same will hold for ISO multiplier.
You would notice no problems at 256x256.

I have uploaded a 256x256 subset of 1kx1k to show when it starts to break (should still be well below the period of the generator):

KISS still 1 bit per sample
Image

Microsoft LCG 8 bits per sample:
Image

LCG with ISO multiplier 8 bits per sample:
Image

One would ideally utilize all the bits generated by the PRNG, using 1 bit per call is wasteful, even for HQ generators it still reduces the period.
Even in the case where I grab full byte (assuming RAND_MAX is 32k), I still waste 7 bits so it would be better to accumulate.
In C++, using uniform_int_distribution not only gives you uniform distribution but also accumulates the output for you so for the range of <0,1> no bit would be wasted.

Nevertheless, I would say that LCG is ok for small number of samples, like generating Zobrist keys, but I prefer to avoid it in general.

As for Mersenne Twister, it generates very high quality sequences and has insane period (2^19k?) + amortized relatively low cost. Still a small burst each 625 values if I remember correctly but one can't go wrong with MT.

Re: Writing bugs

Posted: Wed Jan 16, 2019 10:38 am
by Joost Buijs
In the past I used a 64 bit Mersenne Twister, because it was rather slow and bulky I replaced it by a 64 bit RNG derived from Marsaglia's KISS.

Code: Select all

	class rnd64_t // 64 bit RNG based on Marsaglia's KISS
	{
	private:

		uint64_t c, x, y, z;

	public:

		rnd64_t()
		{
			c = 0x01B69AB0AFF2F240;
			x = 0x112210F4B16C1CB1;
			y = 0x0507A1F38CB440C4;
			z = 0x0003C9A83566FA12;
		}

		uint64_t get()
		{
			uint64_t t;

			t = (x << 58) + c;
			c = x >> 6;
			x += t;
			c += (x < t) ? 1 : 0;
			y ^= y << 13;
			y ^= y >> 17;
			y ^= y << 43;
			z = z * 0x19BAFFBED + 0x12D687;

			return x + y + z;
		}
	};

Re: Writing bugs

Posted: Mon Jan 21, 2019 7:38 am
by odomobo
Speaking of writing bugs, I spent 2 days trying to figure out why adding transposition tables weakened my engine. See if you can spot the error. It's subtle... apparently... >_<

Code: Select all

Search(...) {
    ...
    
    // save to tt
    if (searchMode != SearchMode::Quiescence)
    {
        TTEntry ttEntry;
        ttEntry.Hash = hash;
        if (alpha > originalAlpha)
            ttEntry.NodeType = TTEntryType::PvNode;
        else
            ttEntry.NodeType = TTEntryType::AllNode;

        ttEntry.Score = beta;
        ttEntry.CentiDepth = static_cast<uint16_t>(centidepth);
        engine.TranspositionTable_.MaybeSetEntry(ttEntry);
    }

    return alpha;
}

Re: Writing bugs

Posted: Mon Jan 21, 2019 9:16 am
by mar
this:

Code: Select all

        ttEntry.Score = beta;

Re: Writing bugs

Posted: Mon Jan 21, 2019 7:28 pm
by odomobo
mar wrote:
Mon Jan 21, 2019 9:16 am
this:

Code: Select all

        ttEntry.Score = beta;
Yep, an unfortunate side-effect from copy-pasting my cutoff logic. When I saw it, I couldn't believe that it took me so long to find it -- I had even looked through all my new changes line-by-line when troubleshooting.