Writing bugs

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dann Corbit
Posts: 9901
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Writing bugs

Post by Dann Corbit » Mon Jan 14, 2019 7:32 pm

I use the Mersenne Twister.
I actually think they should use the biggest Mersenne prime because it would offer further improvement.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Ras
Posts: 1140
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Writing bugs

Post by Ras » Mon Jan 14, 2019 11:37 pm

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.
Rasmus Althoff
https://www.ct800.net

mar
Posts: 1987
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Writing bugs

Post by mar » Tue Jan 15, 2019 9:16 am

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.
Martin Sedlak

Joost Buijs
Posts: 932
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Writing bugs

Post by Joost Buijs » Wed Jan 16, 2019 10:38 am

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;
		}
	};
Attachments
marsaglia_8bit_small.png
marsaglia_8bit_small.png (65.19 KiB) Viewed 1222 times

odomobo
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Writing bugs

Post by odomobo » Mon Jan 21, 2019 7:38 am

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;
}

mar
Posts: 1987
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Writing bugs

Post by mar » Mon Jan 21, 2019 9:16 am

this:

Code: Select all

        ttEntry.Score = beta;
Martin Sedlak

odomobo
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Writing bugs

Post by odomobo » Mon Jan 21, 2019 7:28 pm

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.

Post Reply