Sunday, December 31, 2017

Quiddler Solitaire

I received Quiddler as a Christmas gift. Looking to play a solitaire version of Quiddler, I made up my own. The official version of Quiddler Solitaire is here:

https://www.setgame.com/sites/default/files/instructions/QUIDDLER%20SOLITAIRE%20INSTRUCTIONS%20-%20ENGLISH.pdf

I devised my own before Googling the one above. It's a bit different. I play with half the deck. The half deck contains 59 cards.

The number of times each letter is repeated in the half deck is:
A-5, B-1, C-1, D-2, E-6, F-1, G-2, H-1, I-4, J-1, K-1, L-2, M-1,
N-3, O-4, P-1, Q-1, R-3, S-2, T-3, U-3, V-1, W-1, X-1, Y-2, Z-1,
QU-1, IN-1, ER-1, CL-1, TH-1.

My version involves dealing 7 cards off the deck face up. Spell one word and discard the letters used for the word. Replace the cards discarded from the deal deck. Continue until you can't spell a word. To win, all cards must be used to spell real words.

I use traditional Scrabble rules to spell words. No proper nouns or abbreviations are allowed. I allow single letter words although you can try it with "a" and "I" not allowed.

I think mine is better because you don't have to shuffle 118 cards at a time and then spend time dealing out 48 cards. It is also more difficult with only 7 letters to choose from. It is also more like traditional solitaire in that the deck is 59 cards and you have 7 columns of cards. You can also play a variation with 8 cards up at a time. This makes it a bit easier.  Their version is better because of the unpredictability of using two decks.






Wednesday, March 15, 2017

Aces Up!

Four card solitaire described here:
https://en.wikipedia.org/wiki/Aces_Up

Video of someone playing a hand here:
https://www.youtube.com/watch?v=Y5c_nzx6p4k

The odds are long on winning a hand of this game of solitaire. With the wind storm last week, I lost power and then the power came back on but no cable, internet or land phone over the weekend. With no internet, I resorted to playing hands of solitaire and branched out into four card solitaire. I coded up a player and it boasts a winning rate of roughly one in 39 hands or a winning rate of 2.56%. The average number of cards remaining is about 14.3. This game is exceedingly simple and easy to code up. The only strategy involved is moving cards to empty spaces. The algorithm is as follows:

1.    Move a card lower than the same suit above it to the empty space.
2.    Move a card lower than a card on another pile with same suit to the empty space.
3.    Look back one into the piles and move a card below it that will result in creating another empty space.
4.    The ace strategy seems to work as moving any ace available to the empty spot that results in a discard is then made.
5.    Move any card that results in a discard.
6.    Move any ace to the empty spot.
7.    Move any card available to the empty spot.

That’s it. I’ll search for further refinement as I move forward.

Sunday, January 10, 2016

Powerball Madness

The Powerball is heading towards a 1 billion dollar pot. I was watching some program on TV last night and the guy was claiming that you can increase your odds of winning the lottery by not choosing numbers that have already come up. Let's put this theory to the test. Powerball historical results can be found here:

http://www.powerball.com/powerball/pb_nbr_history.asp

I downloaded to a flat text file. Unfortunately, numerical analysis of all 1900 drawings is not easily done. The rules have changed quite frequently. The number of balls used for the drawing has changed frequently.

https://en.wikipedia.org/wiki/Powerball

If you wanted to use the full sample for analysis, you would have to go through all these rule changes and weight the balls accordingly throughout the history of the game. Something I am not going to do on a Sunday morning. The last rule change was October 7th of 2015. This gives me a meager sample of 28 drawings. Nonetheless, I generate the numbers based on this set of drawings. I wacked together a C++ program to calculate the number of times any given ball was drawn.

// powerball.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <fstream>
#include <map>


int _tmain(int argc, _TCHAR* argv[])
{
   std::ifstream lStream( _T("c:\\temp\\powerball2.txt"), std::ios::in );
   // Check for successful open.
   if ( ! lStream.is_open () )
   {
      printf ("open failed\n");
      return 1;
   }
   std::map<int, int> lFreq;
   std::map<int, int> lPowerFreq;
   for (int i = 1; i < 70; i++)
   {
      lFreq[i] = 0;
   }
   for (int i = 1; i < 27; i++)
   {
      lPowerFreq[i] = 0;
   }
   for (;;)
   {
      if (lStream.eof())
      {
         break;
      }
      char lLineBuf[_MAX_PATH];
      lLineBuf[0] = 0;
      lStream.getline (lLineBuf, sizeof(lLineBuf));
      if (strlen(lLineBuf))
      {
         int lBall1, lBall2, lBall3, lBall4, lBall5, lBall6;
         char lDateBuff[_MAX_PATH];
         if (sscanf_s(lLineBuf, "%s %d %d %d %d %d %d", lDateBuff, _MAX_PATH, &lBall1, &lBall2, &lBall3, &lBall4, &lBall5, &lBall6) == 7)
         {
            lFreq[lBall1]++;
            lFreq[lBall2]++;
            lFreq[lBall3]++;
            lFreq[lBall4]++;
            lFreq[lBall5]++;
            lPowerFreq[lBall6]++;
         }
      }
   }
   for (int i = 1; i < 70; i++)
   {
      printf ("freq %d %d\n", i, lFreq[i]);
   }
   for (int i = 1; i < 27; i++)
   {
      printf ("powerfreq %d %d\n", i, lPowerFreq[i]);
   }
   return 0;
}

Input for the program in powerball2.txt was as follows:

Draw Date   WB1 WB2 WB3 WB4 WB5 PB  PP
01/09/2016  32  16  19  57  34  13  3
01/06/2016  47  02  63  62  11  17  3
01/02/2016  42  15  06  05  29  10  2
12/30/2015  12  61  54  38  36  22  3
12/26/2015  65  40  44  59  27  20  2
12/23/2015  67  16  63  38  55  25  4
12/19/2015  30  68  59  41  28  10  2
12/16/2015  09  42  10  55  32  06  2
12/12/2015  62  02  30  19  14  22  2
12/09/2015  16  46  10  56  07  01  2
12/05/2015  47  33  68  27  13  13  2
12/02/2015  14  18  19  64  32  09  2
11/28/2015  47  02  66  67  06  02  3
11/25/2015  53  16  69  58  29  21  2
11/21/2015  37  57  47  50  52  21  3
11/18/2015  40  17  46  69  41  06  2
11/14/2015  66  37  22  14  45  05  3
11/11/2015  26  04  32  55  64  18  3
11/07/2015  50  53  07  16  25  15  2
11/04/2015  12  02  17  20  65  17  4
10/31/2015  09  47  20  25  68  07  2
10/28/2015  56  62  54  63  04  10  2
10/24/2015  20  31  56  64  60  02  3
10/21/2015  57  32  30  42  56  11  4
10/17/2015  57  62  69  49  48  19  3
10/14/2015  20  15  31  40  29  01  2
10/10/2015  27  68  12  43  29  01  2
10/07/2015  52  40  48  18  30  09  3

I outputted this to a text file and loaded it into Excel. Here is the graph of balls and the number of times they have been picked.




Here is the graph of the powerball picks.



With the sample size, the 5 base balls on average should have been picked 2.02 times. With the powerball, each number should have been picked 1.07 times. This is based on my sample size of 28.

With the drawing yesterday, here are the results.

16 - picked 5 times. Well above 2.02
19 - picked 3 times. Above average.
32 - picked 5 times.
34 - picked 1 time. Below average finally.
57 - picked 4 times.

Powerball 13 has been picked 2 times. Above average.

The strategy of picking numbers that haven't been picked before clearly would not have worked yesterday. That said, it would be interesting to analyze the full data set and see if any real trends can be observed. This simple exercise opens the door for all sorts of numerical analysis. I am not sure if I want to go down that hole.


Sunday, February 9, 2014

std::seed_seq example doesn’t compile with VS2010



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!


Sunday, February 2, 2014

A call for mediocrity?

I started tracking consecutive wins and losses in the solitaire player. The results are easily predictable. After playing hundreds of millions of games, my game player wins one game in 5.36 games played. Conversely, it loses one game in about 1.234 games played. Thus the odds of winning two consecutive games is about 1 in 28.729 games played. 28.729 being calculated by taking 5.36 to the power of 2 (5.36^2).  The odds of winning three consecutive games is one in 153.99 games played (5.36^3). So on and so forth. If there is a problem with my random number generation, we should see some extreme variance in these odds. That is, my player will have some outrageous number of consecutive wins or losses given the total number of games played.

Let's examine a continuous run of game playing.
Win one in <5.42888> Ave cards remain <10.1497> One color deal one in <103.093> No play one in <52.356> No play/move one in <625> Total played <10000> Won <1842> Max consecutive wins <5> Max consecutive losses <51> seed <-1752695715>
After 10000 games played, the player had won 5 consecutive games and lost 51 in a row.
5.36^5 = 4424.09
1.234^51 =  45401.80
Thus the first 10000 games were quite "unlucky".

Win one in <5.54939> Ave cards remain <10.1738> One color deal one in <102.041> No play one in <51.4139> No play/move one in <526.316> Total played <20000> Won <3604> Max consecutive wins <6> Max consecutive losses <51> seed <-621770119>
After 20000 games played, it had won 6 consecutive games in a row.
5.36^6 = 23713.12

Win one in <5.43833> Ave cards remain <10.1819> One color deal one in <105.932> No play one in <52.1376> No play/move one in <413.223> Total played <50000> Won <9194> Max consecutive wins <7> Max consecutive losses <51> seed <-137475027>
After 50000 games played, it won 7 consecutive games.
5.36^7 = 127102.33
Now a "lucky" run.

Win one in <5.37109> Ave cards remain <10.1601> One color deal one in <105.263> No play one in <53.3204> No play/move one in <413.534> Total played <110000> Won <20480> Max consecutive wins <7> Max consecutive losses <53> seed <-1242274590>
After 110000 games played it had lost 53 consecutive games.
1.234^53 = 69135.87

Win one in <5.38089> Ave cards remain <10.1668> One color deal one in <105.105> No play one in <53.9291> No play/move one in <398.482> Total played <210000> Won <39027> Max consecutive wins <8> Max consecutive losses <53> seed <1626910630>
After 210000 games played, it had won 8 consecutive games.
5.36^8 = 681268.51

Win one in <5.38029> Ave cards remain <10.1704> One color deal one in <105.213> No play one in <53.9877> No play/move one in <402.194> Total played <220000> Won <40890> Max consecutive wins <8> Max consecutive losses <56> seed <-1955633737>
After playing 220000 games, it had lost 56 consecutive games.
1.234^56 = 129911.90

Win one in <5.36085> Ave cards remain <10.1561> One color deal one in <101.571> No play one in <54.1258> No play/move one in <391.144> Total played <530000> Won <98865> Max consecutive wins <9> Max consecutive losses <56> seed <711853774>
After playing 530000 games, it won 9 consecutive games. Lucky!
5.36^9 = 3651599.23

Win one in <5.36107> Ave cards remain <10.1572> One color deal one in <101.317> No play one in <54.1467> No play/move one in <387.597> Total played <600000> Won <111918> Max consecutive wins <9> Max consecutive losses <69> seed <1213694581>
My "luck" ran out after 600000 games played as it lost 69 consecutive games.
1.234^69 = 1998692.66

Win one in <5.36843> Ave cards remain <10.1576> One color deal one in <101.961> No play one in <54.2194> No play/move one in <384.399> Total played <2730000> Won <508529> Max consecutive wins <9> Max consecutive losses <75> seed <2049738009>
After 2.73 million games played, my bad luck continued with 75 consecutive losses.
1.234^75 = 7057273.96

When can we expect 76 consecutive losses and 10 consecutive wins?
1.234^76 = 8708676.07
5.36^10 = 19572571.89
Somewhere around 8 million games played, we should see 76 consecutive losses.
Somewhere around 19 million games played, we should see 10 consecutive wins.

Here's a run of 11 consecutive wins after 67 million games played. I wasn't logging consecutive losses with this version.
Win one in <5.35934> Ave cards remain <10.1514> One color deal one in <101.449> No play one in <54.2281> No play/move one in <381.972> Total played <67229791> Won <12544422> Max consecutive wins <11> seed <-1352972818>

Sometimes they come early, sometimes late, but we won't see extreme variance from these numbers. Casinos bank on this "reality" and this is why they are profitable. When we see extreme variance, we can be fairly certain it's cheating. For those of religious or spiritual persuasion, defying the odds in the extreme can be referred to as a miracle.

What about exceptional people? The world population stands at above 7 billion. The number of people born in the history of humanity is growing quite quickly. As more and more humans are produced, we should see extreme runs of "good" luck and "bad" luck. This would make that person exceptional. Was Adolf Hitler a run of 200 consecutive lost deals? Was Einstein a run of 20 consecutive wins?

I only offer this up as a rebuttal to the history channel alien theory. Einstein was an alien? I can only scoff. Furthermore, what constitutes good and bad luck as opposed to just runs of events that defy long odds? Einstein is viewed as a demigod in our culture but what real good has come from his knowledge? Piling up mounds of radioactive waste. Chernobyl? Fukushima? Hiroshima and Nagasaki? It's unclear what horrors await us. Stephen Hawking is a truly exceptional person but what good has he brought humanity? Visions of "whitey on Mars" does exactly what for the planetary condition?

So what does a "20 consecutive win" person look like?

“For me, I am driven by two main philosophies: know more today about the world than I knew yesterday and lessen the suffering of others. You'd be surprised how far that gets you.”
― Neil deGrasse Tyson

On a planet where one in two people live on $2 a day or less and one billion are starving, I don't see a lot of lessening the suffering of others. In terms of putting aside human exceptionalism, look at all the death and destruction wrought on the planet by humans. That is a lot of suffering life. Where are the "20 consecutive win" people? Instead, I see our most exceptional people on the planet engaged in the wholesale raping and pillaging of the planet. The Bill Gateses, Warren Buffets and Kock brothers held up as demigods. Gordon Gecko, invented as a parody, has become a role model.

Today is Ground Hog Bowl day. It's a ritualistic orgy of consumerist excess that this nation celebrates annually. Victim and predator alike rally to the cause of new commercials and QB success. Oh happy day! As for Mr. Tyson, how exactly do wage and debt slaves lessen the suffering of others?  Cura te ipsum (physician heal thyself)?

Tuesday, January 21, 2014

Odds of predicting the results of all 67 games in the NCAA tourney

With 67 games played, trying to predict the outcome of 67 coin tosses is 1 over 2^67 or 1 in 147,573,952,589,676,412,928. That's about one in 147 quintillion (less likely than winning 24 consecutive games of solitaire). Let's assume over half the games are indeed predictable with assorted nags taking on the better teams. 1 over 2^33 is only 1 in 8,589,934,592 (less likely than winning 13 consecutive games of solitaire). Hot diggity,  I think their money is safe.

Friday, January 3, 2014

Mistakes were made

I'm playing this solitaire game and solving games. Watching the mistakes that are made to solve a game makes me think of Hawking and his ideas about the imperfection of the universe. You can watch it here:

https://www.youtube.com/watch?v=DECAorZYErk

Watching mistakes result in favorable outcomes makes me wonder if a mistake-prone player could beat the winning rate of the "perfect" player. Could a formulation of mistake frequency do such a thing? It's worth investigating.

Another interesting aspect of this solver is watching how any given mistake really doesn't cause any changes until consequences present themselves. You can ignore moving a black queen any number of times but it really doesn't do anything until the other black queen shows up on the Talon and you play it. Life is a lot like this. We keep making the same mistakes over and over until real consequences present themselves. The river denial runs deep.

I find the game solving option extremely useful. I can play a hand and then solve it afterwards. If I lost and it yields a result of solutions or no solutions, I feel vindicated. I don't even look at the solutions, I'm just checking my play. If I won and it yields solutions, I can rest assured I made some fortunate mistakes.

There is something obscene about playing only winning hands. One game after another where the cards come up golden. I can't spot any trend on the deals and they all play like regular hands until good card keep coming up at opportune times. It's pure cheating the odds with technology and I can't help but think this might be a metaphor for our modern existence. It seems real but it truly is unreal. It's unsettling.

My son had me read some of David Lynch's book about fishing.

http://en.wikipedia.org/wiki/Catching_the_Big_Fish

It's a great book. He talks about how ideas can branch out into all sorts of directions. I'm not sure where this is leading. One thing is for certain, I'm clicked out and I still prefer to play a game of solitaire with a real deck of cards.