Random vs random vs random

[andygrant]

Random vs random vs random

[CMCanavessi]

The new rand64 version scores exactly the same as the old one:

Score of TrueEtherRand vs EtherTrueRand_new: 793 - 793 - 8414 [0.500] 10000
Elo difference: 0.00 +/- 2.71
Finished match

[Mk-Chan]

Well I'm flummoxed, I ran a simple C++ program that runs both our RNGs for a billion values and that gives a pretty even distribution for rand(), Andy's rand64() [seeded the same way he did] and C++11's random library. So that test clearly failed.

The only other thing I could think of is you didn't play enough games because it's logically impossible for random movers to be so far apart.

[AndyGrant]

Is is possible Teki was making illegal moves or losing on time? 10,000 games with that kind of confidence internal... I would be AMAZED if that was just statistical noise.

Some people encode Promotions as one move, some as four. If you encode as one then maybe that is the issue?

I'm not hell bent on finding the difference, but I am very confused.

[AndyGrant]

My last thought ... and this seems like It really cannot be true -- Do the probabilities change because you are generating psuedo legal moves instead of legal ones?

[Mk-Chan]

No I have 4 separate moves for promotions and while I do generate pseudo-legal moves, I remove any encountered illegal move in case I'm unable to make the move and regenerate a random number so I don't think it should have an effect.

It is possible that Teki is losing on time or making illegal moves. Could you check the PGN @CMCanavessi ?

[CMCanavessi]

Losing on time definitely not, because the games are played at TC=infinite. They are very fast anyways, as both engines are instant movers.

I checked the pgn for the word "illegal" and found nothing. Anyways, I have attached the pgn so you can check it if you want. If you have any problems extracting the pgn file, rename it to .7z (as it didn't let me attach 7z files, i just renamed it to .zip).

Mind you, this is the previous Ethereal Random version, the one with rand() and not rand64(), and 10.000 games. I can make a new match of 100.000 games with the new rand64 version vs teki again if needed, will take a couple of hours.

TestRandom.zip

[Mk-Chan]

Hmm... No illegal, no forfeit. This is really just weird. How about any other random movers?

[CMCanavessi]

Well, it's not easy to find them. The POS engines can make random moves, but they need to be executed with --brain-mode random (or something like that), which I couldn't make it work in cutechess (using arg="--brain-mode random" does not seem to work).
Brutus RND is another one, but it crashes in my pc. Maybe it's related to my ryzen processor.
And Randscacs doesn't move instantly, so it takes longer to test it.

[CMCanavessi]

Wait, I just realized that the zip I attached earlier was the one with Ethereal old vs Ethereal new. It seems I deleted the old pgn I did with Ethereal old vs Teki.

I have started a new match with Ethereal new vs Teki, 100.000 games. Should be done in a couple of hours.

From what I'm seeing, it's already starting to show the same behaviour.

[CMCanavessi]

You can already see the trend, it's exactly the same as before

[CMCanavessi]

[CMCanavessi]

I stopped as it was exactly the same result as before, but got an idea that, as I was playing the matches without opening book, then maybe Ethereal had better opening knowledge (besides random) so I made a new test, using 8-move opening book and playing reverse games. The results are identical:

Score of Ethereal True Random rand64 vs Teki Random Mover: 1249 - 652 - 8099 [0.530] 10000
Elo difference: 20.77 +/- 2.95
Finished match

[CMCanavessi]

games.zip

[Mk-Chan]

I have one idea but it's probably stupid. Lemme arrange teki's movegen to match the order of ethereal's I'll try that out and do some matches

[Mk-Chan]

This is hilarious.
Changing the move ordering seemed to be the solution. Take a look at this:

I changed the move generation order from:
piece captures, pawn captures, quiet promotions, castling, piece quiets, pawn quiets
to:
quiet promotions, pawn captures, pawn quiets, piece captures, piece quiets, castling

and got:
Score of EtherTrueRand 9.21 vs Teki: 981 - 723 - 8296  [0.513] 10000
Elo difference: 8.97 +/- 2.80
Finished match

It seems the random number gods are at work with varying movelist size and random number generators. No doubt that different move ordering will further change the result.

[AndyGrant]

Since that seemed to have an affect. Can you do legal move generation instead, and then pick from that list. Instead of picking from the psuedoes until you get a legal.

I feel like that changes things.

[Mk-Chan]

I agree now, it really might make a difference! But it seems very counter-intuitive to me still. I'll just try it

[Mk-Chan]

Legal movegen Teki:

Score of EtherTrueRand 9.21 vs Teki: 882 - 794 - 8324  [0.504] 10000
Elo difference: 3.06 +/- 2.78

You're right, but it still baffles me how this makes a difference

[AndyGrant]

So here is my thought. Take a look at a pinned queen. This queen likely only has a few legal moves, but has a large list of illegal ones. So if our random number falls within the queen list, we will likely have to generate a new one. For some reason (im postulating) the RNG is less likely to produce another number which sits in the queens list, thus making it more likely to move a lower valued piece.

I would venture to guess that having a mobile queen in random games is what wins things. If the queen is out, you have many more capture possibilities. And for random games all we can really do is hope to take enough material to stumble upon a mate.

Right or wrong, still extremely un-intuitive. Thanks for taking the time to investigate here. I think I'll close this now.

@CMCanavessi If you want a version of Ethereal which matches they way Teki does things, I can do that for you.

[Mk-Chan]

We can finally bury the beaten horse:

https://github.com/Mk-Chan/Teki/blob/master/src/utils.h#L54

Reseeding the RNG everytime with the same value every millisecond => same index picked from the movelist. After removing an illegal move, it just picks the next move (which is further along the movelist and definitely not random).

That reasonably explains the weird behaviour.

Found by @kz04px on ##chessprogramming irc.

[Safrad]

Well, it's not easy to find them. The POS engines can make random moves, but they need to be executed with --brain-mode random (or something like that), which I couldn't make it work in cutechess (using arg="--brain-mode random" does not seem to work).
Brutus RND is another one, but it crashes in my pc. Maybe it's related to my ryzen processor.
And Randscacs doesn't move instantly, so it takes longer to test it.

I have created another instant random mover engine: https://sx.rosada.cz/projects/sxrandom
Brutus RND crashes also on Intel CPU.