There’s a real surprise for you! The examples for using
std::seed_seq often go along the lines of:
std::seed_seq seed2 = {102,406,7892};
Too bad it doesn’t compile on VS2010. Compiler Error
C2552.
Somebody actually had it right and I found it here:
They give you a number of ways to do it. This is the one
that worked:
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::seed_seq s4(a, a + 10); // can use iterators
I didn’t try the stream one.
Why bother with std::seed_seq? I came to the conclusion
that a 32 bit seed only offers a measly 4294967296 unique deals. In real life,
a deal of a deck of cards can take on 52! unique permutations. That’s a very
big number. This programmer says there
are 2^225 unique ways to deal a deck of cards.
I would need a 225 bit seed to approximate real life but
I don’t feel like tackling that problem right now. I hope to get to it. A good
intermediate step is to seed std::mersenne_twister with 64 bits. As best I can
tell, you need to use std::seed_seq. Here’s my seed code:
QueryPerformanceCounter( &lCount );
lCount.HighPart += sBaseSeed;
sStartCtr = lCount.QuadPart;
if (sLastStartCtr == sStartCtr)
{
sStartCtr = sLastStartCtr+1;
}
sLastStartCtr = sStartCtr;
if (!mSeed)
{
mSeed = sStartCtr;
}
int lPart1(static_cast<int>(mSeed));
int lPart2(static_cast<int>(mSeed>>32));
int lArray[2] = {lPart1, lPart2};
std::seed_seq lSeq(lArray, lArray + 2); // can
use iterators
mGenerator.seed(lSeq);
The s variables are statics and mSeed is __int64. sBaseSeed is time(NULL) with the sum of the characters
of the computer name added to it. This gives a different playing experience for
most computers even if you power up your computers at the exact same time! Haha!
I think you would have to have a really fast computer to get sLastStartCtr ==
sStartCtr but I put that in just to make sure. With 64 bits, I can get over 18,446,744,073,709,551,616
unique deals. I think that is in excess of 18 quintillion deals. Still far
short of 52 prime but what the heck!
Needless to say, I’m skeptical of the whole process of
generating pseudo-random numbers using algorithms that are generally available.
This gives you pause:
The Guardian and The New York Times have reported that the National Security Agency (NSA) inserted a CSPRNG into NIST SP 800-90A that had a backdoor which allows the NSA to readily decrypt material that was encrypted with the aid of Dual_EC_DRBG. Both papers report[7][8] that, as independent security experts long suspected,[9] the NSA has been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top secret documents leaked to the Guardian by Edward Snowden. The NSA worked covertly to get its own version of the NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor." In spite of the known potential for a backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as RSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.[10] RSA Security received a $10 million payment from the NSA to do so.[11]
Which really calls into question the whole business of
attempting to generate unique solitaire deals! Who knew? So I play a million
hands and give it different seeds and I have no good way of verifying that the
same deal didn’t come up twice. The odds of this happening are astronomical and
if that happens, you can rest assured your random number generator is either
crap or the NSA has their fingers in that pie. The next step is to verify that
I get unique deals. With 8 gig RAM, the most I can verify with available memory
is around 4 million deals. If I want to verify more, I’ll have to swap to disk
and I won’t be doing that soon. Nonetheless, I don’t want to leave the computer
running for hours and wait for the result. I am impatient. So I’m back to
std::map and using a checksum to create lists of deals. The checksum is just
the cards in the play stack added up. Each card in the deck is assigned a
number from 1 to 52 and then I add up the cards. I posit that if a deal
matches, the checksums would be identical. I use this as my key to my std::map.
Here it is:
std::map<short,
std::vector<std::pair <__int64,
std::vector<Stack>>>> sStackList;
As games are played, I put the deal into this list as
follows:
short lSum(calcChecksum());
sStackList[lSum].push_back(std::make_pair(getSeed(), mCardStacks));
I wanted to log the potentially offending seeds which is
why it is an std::pair. After however many games are played, I then look for
duplicates:
void
Game::checkForDuplicates()
{
size_t lStacksCompared(0);
bool lDupFound(false);
std::map<short,
std::vector<std::pair <__int64,
std::vector<Stack>>>>::iterator lIter = sStackList.begin();
for (; lIter != sStackList.end();
++lIter)
{
std::vector<std::pair <__int64,
std::vector<Stack>>> &lStackList(lIter->second);
for (size_t i = 0; i <
lStackList.size()-1; i++)
{
for
(size_t j = i+1; j < lStackList.size(); j++)
{
if
(lStackList[j].second == lStackList[i].second)
{
std::wstringstream lStream;
lStream << _T("Duplicate deal! ") << lStackList[j].first
<< _T(" ") <<
lStackList[i].first;
displayString(lStream.str());
lDupFound = true;
break;
}
lStacksCompared++;
if
((lStacksCompared%100000000) == 0)
{
std::wstringstream lStream;
lStream << _T("Stacks compared ") <<
lStacksCompared;
displayString(lStream.str());
}
}
if
(lDupFound)
{
break;
}
}
if (lDupFound)
{
break;
}
}
if (!lDupFound)
{
std::wstringstream lStream;
lStream << _T("No duplicates
found! ");
displayString(lStream.str());
}
}
Both std::tr1::mt19937 and std::tr1::mt19937_64
passed a million deal check (i.e. no duplicates were found). What a hobby this
has become! It has it all. Coding challenges galore and international intrigue
and skullduggery to boot!
No comments:
Post a Comment