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.
Friday, January 3, 2014
Thursday, January 2, 2014
Let's play some solitaire!
I've made the solver an interactive Solitaire game where you can play 3 card draw solitaire with infinite go rounds. In addition to playing Solitaire, it allows you to have have the computer solve games that you have lost. It also allows you to play only winning and solvable hands. It has full undo/redo functionality in addition to an option to have the computer make the next play. This version of Solitaire is developed for Windows 7 and Windows XP. The x64 version is for 64 bit Windows. If you don't know if you have an x64 system, just download the non-x64 version. You can download it from here:
http://webpages.charter.net/jstefan/SolitaireSetup_1_0_0.zip
http://webpages.charter.net/jstefan/SolitaireSetup_x64_1_0_0.zip
Once you have dowloaded either zip, uncompress it and run the setup.exe found in the zip file. Feedback is welcome.
Below are the instructions included in the ReadMe.rtf file that is included as part of the install:
After installing the program, you will find a program item off your start menu. Running it the first time, it will try to size the window based on the resolution of your screen. It's set up for a minimum of 1280x1024. If your resolution is less, do not fret. The first thing to do is to go to the menu "Options/Window Layout" and reduce the zoom percentage. This will allow you to see the whole deal on lower screen resolutions. This is particularly useful for laptops which now have less resolution.
Menus:
File/New - Start a new game.
File/Open - Open a previously stored game.
File/Save/Save As - Save games.
File/Print - Print stuff.
Edit/Undo - Undo a previous move.
Edit/Redo - Redo a previous move.
Games/Computer Next Move - Have the computer make your next move.
Games/Replay Game - Replay a game.
Games/Solve Game - Attempt to solve a deal.
Start Continuous/Stop Continuous - Have the computer just play games and collect statistics.
Options/Play Only Winning Deals - Deals will only be ones that the computer can win. This excludes solvable and losing deals. This option is not sticky and will be off the next time you run the program. This is "as designed". Select "File/New" after turning on this option to get a new deal.
Options/Play Only Solvable Deals - Deals will only be ones that the computer can solve. This excludes winning and losing deals. This option is not sticky and will be off the next time you run the program. This is "as designed". Select "File/New" after turning on this option to get a new deal.
Options/Window Layout - Allows for the customization of the stack layout.
Options/Clear Won/Loss – Zeros out the won/loss counters.
After solving a deal or having dealt a game with the "Options/Play Only Solvable Deals" turned on, the "Games/Computer Next Move" command will play off a series of game snapshots which lead you to the solution. Unfortunately, they do not show all intermediate moves and it's left to your intellect as to how the game is actually solved. If you decide to make a move at any point in a solved game, the list of snapshots will be discarded and you will be on your own. This includes clicking on the stock stack. Not to worry though, choose "Games/Replay Game" to go back to the solution.
Moving cards:
Regular drag and drop to move cards around the deal. For ace cards, just move the ace into your ace stack area (by default, upper left of the window) and release the left mouse button. Unfortunately, I order the ace stacks for this version. Click on the stock to get the next three cards. When the stock is exhausted and you want to start back over, just left click in the stock area. To expose hidden cards on the Talon, middle click or double left click on the hidden card and it will show it (no cheating please). Useful when you win/lose a game and wish to see those cards. Right click will undo a move.
Output tabs:
Status tab displays informational message from the solver.
Statistics tab displays the win/loss counter.
http://webpages.charter.net/jstefan/SolitaireSetup_1_0_0.zip
http://webpages.charter.net/jstefan/SolitaireSetup_x64_1_0_0.zip
Once you have dowloaded either zip, uncompress it and run the setup.exe found in the zip file. Feedback is welcome.
Below are the instructions included in the ReadMe.rtf file that is included as part of the install:
After installing the program, you will find a program item off your start menu. Running it the first time, it will try to size the window based on the resolution of your screen. It's set up for a minimum of 1280x1024. If your resolution is less, do not fret. The first thing to do is to go to the menu "Options/Window Layout" and reduce the zoom percentage. This will allow you to see the whole deal on lower screen resolutions. This is particularly useful for laptops which now have less resolution.
Menus:
File/New - Start a new game.
File/Open - Open a previously stored game.
File/Save/Save As - Save games.
File/Print - Print stuff.
Edit/Undo - Undo a previous move.
Edit/Redo - Redo a previous move.
Games/Computer Next Move - Have the computer make your next move.
Games/Replay Game - Replay a game.
Games/Solve Game - Attempt to solve a deal.
Start Continuous/Stop Continuous - Have the computer just play games and collect statistics.
Options/Play Only Winning Deals - Deals will only be ones that the computer can win. This excludes solvable and losing deals. This option is not sticky and will be off the next time you run the program. This is "as designed". Select "File/New" after turning on this option to get a new deal.
Options/Play Only Solvable Deals - Deals will only be ones that the computer can solve. This excludes winning and losing deals. This option is not sticky and will be off the next time you run the program. This is "as designed". Select "File/New" after turning on this option to get a new deal.
Options/Window Layout - Allows for the customization of the stack layout.
Options/Clear Won/Loss – Zeros out the won/loss counters.
After solving a deal or having dealt a game with the "Options/Play Only Solvable Deals" turned on, the "Games/Computer Next Move" command will play off a series of game snapshots which lead you to the solution. Unfortunately, they do not show all intermediate moves and it's left to your intellect as to how the game is actually solved. If you decide to make a move at any point in a solved game, the list of snapshots will be discarded and you will be on your own. This includes clicking on the stock stack. Not to worry though, choose "Games/Replay Game" to go back to the solution.
Moving cards:
Regular drag and drop to move cards around the deal. For ace cards, just move the ace into your ace stack area (by default, upper left of the window) and release the left mouse button. Unfortunately, I order the ace stacks for this version. Click on the stock to get the next three cards. When the stock is exhausted and you want to start back over, just left click in the stock area. To expose hidden cards on the Talon, middle click or double left click on the hidden card and it will show it (no cheating please). Useful when you win/lose a game and wish to see those cards. Right click will undo a move.
Output tabs:
Status tab displays informational message from the solver.
Statistics tab displays the win/loss counter.
Saturday, December 21, 2013
A program solving at 83.6%
I haven't posted in a while but this project will never die until I'm dead. I can usually put a few hours a month on it and the payback is great. I got an email from another computer solver and his program is solving at 83.6% on a thousand deals. His results can be found here along with his source code:
https://github.com/ShootMe/Klondike-Solver/blob/master/Statistics.txt
His program gives up after 60 million states so his deal processing rate is much higher than mine. 8.2 seconds a deal versus my 19 seconds a deal (hardware considerations aside). Here are my results on a thousand games I ran today as a comparison:
80.2% solved. Roughly 19 seconds on average to process a deal. Some deals are ridiculously difficult to process. I've seen some take about 10 minutes before they become unsolvable.
Why the discrepancy? If we have bugs in either of our programs, that would certainly result in the discrepancy. Another potential problem is generating random numbers. I use stl:mersenne_twister and he used his home grown version to generate numbers. I'll try his random number generator. I asked him to try stl:mersenne_twister.
I'm working on making my solver interactive and hope to have it ready to post in a month or two. This will be a fully interactive installable program that you can play Klondike Solitaire on (draw 3, infinite retries). In addition, you will be able to ask the computer to attempt to solve any given deal that you lost and allow you to step through the solution. In addition, you'll be able to have the computer make a move at any given time in the game. Undo/Redo functionality to back up and go forward on moves. Version 2 or the end product will model after Dr. BlackJack. You can have it warn you when the computer thinks you are making a mistake. I don't have a lot of time to spend on this but surprisingly, I've made quite a bit of progress on it just looking at it a few hours a month.
https://github.com/ShootMe/Klondike-Solver/blob/master/Statistics.txt
His program gives up after 60 million states so his deal processing rate is much higher than mine. 8.2 seconds a deal versus my 19 seconds a deal (hardware considerations aside). Here are my results on a thousand games I ran today as a comparison:
80.2% solved. Roughly 19 seconds on average to process a deal. Some deals are ridiculously difficult to process. I've seen some take about 10 minutes before they become unsolvable.
Why the discrepancy? If we have bugs in either of our programs, that would certainly result in the discrepancy. Another potential problem is generating random numbers. I use stl:mersenne_twister and he used his home grown version to generate numbers. I'll try his random number generator. I asked him to try stl:mersenne_twister.
I'm working on making my solver interactive and hope to have it ready to post in a month or two. This will be a fully interactive installable program that you can play Klondike Solitaire on (draw 3, infinite retries). In addition, you will be able to ask the computer to attempt to solve any given deal that you lost and allow you to step through the solution. In addition, you'll be able to have the computer make a move at any given time in the game. Undo/Redo functionality to back up and go forward on moves. Version 2 or the end product will model after Dr. BlackJack. You can have it warn you when the computer thinks you are making a mistake. I don't have a lot of time to spend on this but surprisingly, I've made quite a bit of progress on it just looking at it a few hours a month.
Sunday, June 9, 2013
Random dot org
As much as I like STL mersenne_twister, I feel the need to verify my win percentages with a different random number generator. Of course, you can get random numbers online from http://www.random.org/. This is a pretty cool site and he uses atmospheric noise to generate random numbers. How good is that! It's a free service and he doles out "bit allowances" for generating numbers. His API is described here:
http://www.random.org/clients/http/
Of course he will sell additional allowances and I like his scheme. That said, I doubt I can pony up the dough for running a million deals. Like most Americans, I am nothing more than a wage/debt slave. The free bit allowance allows me to play about 600 hands so I played 500 and the game player won about 1 in 5.7 deals. This is within the ball park of my usual 1 in 5.37 deals so I am pretty happy with the results. I hope to email him with my hat in hand and see if he'll give me a million deals in the off hours or something.
So how hard was it to get random numbers off the internet? Not very. He has some samples posted and of course the link is stale. I googled the sample and found a good link. Here is a C++ program written by Doug Hague which will download the numbers:
https://github.com/doughague/random-dot-org
I pulled this down and tried to build it in VS2010. Of course it uses something called LibCurl. Édouard Tallent's blog has a nice write up on how to get it up and running under VS2010.
http://quantcorner.wordpress.com/2012/04/08/using-libcurl-with-visual-c-2010/
The thing also uses GNU option parsing but I know I don't need that. #ifdef NOTUSED. haha. I manually hack in the options I want. So I build the thing and of course there's a missing dll. The ole libsasl.dll is missing and I hunt this down and find it here:
libsasl.dll
Run and test this standalone. Works a treat! I add a function in place of main(), change the project to be a static library. I still need all the bonus dll's though. I add the static library project to my solitaire solution and I'm pretty close. I modify my deck object to deal using a sequence of numbers from random.org and there you have it. Solitaire dealt off of atmospheric noise.
http://www.random.org/clients/http/
Of course he will sell additional allowances and I like his scheme. That said, I doubt I can pony up the dough for running a million deals. Like most Americans, I am nothing more than a wage/debt slave. The free bit allowance allows me to play about 600 hands so I played 500 and the game player won about 1 in 5.7 deals. This is within the ball park of my usual 1 in 5.37 deals so I am pretty happy with the results. I hope to email him with my hat in hand and see if he'll give me a million deals in the off hours or something.
So how hard was it to get random numbers off the internet? Not very. He has some samples posted and of course the link is stale. I googled the sample and found a good link. Here is a C++ program written by Doug Hague which will download the numbers:
https://github.com/doughague/random-dot-org
I pulled this down and tried to build it in VS2010. Of course it uses something called LibCurl. Édouard Tallent's blog has a nice write up on how to get it up and running under VS2010.
http://quantcorner.wordpress.com/2012/04/08/using-libcurl-with-visual-c-2010/
The thing also uses GNU option parsing but I know I don't need that. #ifdef NOTUSED. haha. I manually hack in the options I want. So I build the thing and of course there's a missing dll. The ole libsasl.dll is missing and I hunt this down and find it here:
libsasl.dll
Run and test this standalone. Works a treat! I add a function in place of main(), change the project to be a static library. I still need all the bonus dll's though. I add the static library project to my solitaire solution and I'm pretty close. I modify my deck object to deal using a sequence of numbers from random.org and there you have it. Solitaire dealt off of atmospheric noise.
Saturday, June 8, 2013
Taking it to the next level
I have ported the program to x64. I have added multi-threading. I can keep eight cores going at 50% without increasing priority. Why do I do this? The holy grail is to prove that good deals are hard to lose. My preliminary runs support that hypothesis. You'll be hard pressed to lose a good deal regardless of the number of mistakes you make. I'll quantify this in upcoming posts.
From a computer geek point of view, reader/writer locks are your friends. I can't utilize processor unless I do a reader/writer lock on the list of unique card stacks. What's a reader/writer lock? I had a guy at work who went ballistic over this concept but it's pretty simple. If you are comparing card stacks, you can have as many threads as you want comparing card stacks. When you go to add a stack to the list, it is imperative that everyone be locked out of accessing the list of cards stacks. Thus a reader/writer lock lets all readers in, keeps writers out. When all pending readers are finished, the writer comes in and takes exclusive control of the list of card stacks. It works! She is your friend!
From a computer geek point of view, reader/writer locks are your friends. I can't utilize processor unless I do a reader/writer lock on the list of unique card stacks. What's a reader/writer lock? I had a guy at work who went ballistic over this concept but it's pretty simple. If you are comparing card stacks, you can have as many threads as you want comparing card stacks. When you go to add a stack to the list, it is imperative that everyone be locked out of accessing the list of cards stacks. Thus a reader/writer lock lets all readers in, keeps writers out. When all pending readers are finished, the writer comes in and takes exclusive control of the list of card stacks. It works! She is your friend!
Saturday, May 18, 2013
Solving rate down to 77%
I am down to 77% solving rate. My initial 80% is attributable to bugs that I have since fixed. It seems to be consistent but I really haven't built up a large sample set. We're talking hundreds of games.
My list of lists isn't doing exactly what I thought it was. I was incorrectly collecting statistics. The number of stacks in a given list is not limited at all and grows quite large. Computational power is an issue.
I took a shot at trying to calculate how many ways a game can be solved. This is a really small sample set and some deals couldn't finish as you run out of memory. Running 32 bit, my process is limited to 2 gig. This little foray led to me to following conclusions:
1. My card object is too large. For this reason, I encoded everything into a single byte. The card is encoded in the low order nibble, the suit is encoded into the next two bits and the up card state is encoded in the high order bit. Stacks are much smaller now and stack comparisons are much faster.
2. I need to port this to 64 bit. 2 gig has no chance of dealing with this problem.
3. Even then, I will probably have to implement a caching scheme for writing stacks to disk.
4. I need to go multi-threaded and run this thing on eight cores.
5. I need to implement a twelve key map which uses the number of cards on all the stacks as the keys.
6. Make an internet solver. This would be a service that could be installed on computers where the main solver could dole out stacks to be solved. Sort of like the SETI at home thing. I'm certain there's a large community of people who would want to donate computing time in pursuit of meaningless endeavors like calculating the number of ways a deal can be won in solitaire! Er, uh, maybe not.
7. Utilize a database for caching stacks, managing solving and collecting statistics.
This little hobby is taking on more dimensions than unique solitaire card stacks. The funny thing is, I can probably chip away at this in my spare time with obsolete computer equipment. When I first started programming, 64K RAM and an 8 bit processor wouldn't have gotten you very far with this problem.
My list of lists isn't doing exactly what I thought it was. I was incorrectly collecting statistics. The number of stacks in a given list is not limited at all and grows quite large. Computational power is an issue.
I took a shot at trying to calculate how many ways a game can be solved. This is a really small sample set and some deals couldn't finish as you run out of memory. Running 32 bit, my process is limited to 2 gig. This little foray led to me to following conclusions:
1. My card object is too large. For this reason, I encoded everything into a single byte. The card is encoded in the low order nibble, the suit is encoded into the next two bits and the up card state is encoded in the high order bit. Stacks are much smaller now and stack comparisons are much faster.
2. I need to port this to 64 bit. 2 gig has no chance of dealing with this problem.
3. Even then, I will probably have to implement a caching scheme for writing stacks to disk.
4. I need to go multi-threaded and run this thing on eight cores.
5. I need to implement a twelve key map which uses the number of cards on all the stacks as the keys.
6. Make an internet solver. This would be a service that could be installed on computers where the main solver could dole out stacks to be solved. Sort of like the SETI at home thing. I'm certain there's a large community of people who would want to donate computing time in pursuit of meaningless endeavors like calculating the number of ways a deal can be won in solitaire! Er, uh, maybe not.
7. Utilize a database for caching stacks, managing solving and collecting statistics.
This little hobby is taking on more dimensions than unique solitaire card stacks. The funny thing is, I can probably chip away at this in my spare time with obsolete computer equipment. When I first started programming, 64K RAM and an 8 bit processor wouldn't have gotten you very far with this problem.
Saturday, May 4, 2013
80% of solitaire deals are now solvable!
I was able to get the solver to solve at around 80% of deals. It is extremely consistent. My sample sizes are only hundreds of deals as it is solving at a rate of about 25 deals an hour. It makes me wonder how they were getting variation in the white paper solver listed in the previous post.
As I suspected, the first version of the solver was flawed. My move logic was flawed and I was skipping permutations. At a cost of making the solver slower (first version solved at a rate of about 40 deals per hour), I was able get my solution rate up to 80%. I discarded the concept of grouping stack moves and went for a far simpler implementation. Stack moves are pretty much treated just like card plays off the play stack. I also refined my strategy for check pointing stacks. My initial implementation would unconditionally check point a stack after a significant action after a skipped action. When I would go play another list, I would look for the stacks in the list of check pointed stacks and not play the stacks if they were found. I implemented a new strategy where I would mark the stacks for pending check point after a skipped action. I would then continue to play the hand and try to check point the stacks after each significant action. If the stacks were found in the previously tried list, I would leave the pending flag set and continue playing. In this manner, the program now seeks out new stacks to solve. Only when I am able to check point the stack (i.e. it doesn't exist in previously tried stacks) do I clear the pending flag. This means I have to spend more time comparing stacks but less time actually playing cards.
Lists of lists are good. My initial implementation of the lists of check pointed stacks was a std::map<int, std::vector<std::vector<Stack>>>. I used the number of cards remaining on the play stack as the key. I never analyzed this map but I figured that some lists were getting exceedingly long and required many comparisons of the stacks. I implemented a new list of check pointed stacks. It is:
static std::map<int, std::map<int, std::map<int, std::vector<std::vector<Stack>>>>> sStacksPlayed;
It has three keys and I tried to do eight but the compiler barfed on it. Something about names being too long. Three was the most I could get. I didn't bother to investigate further but I suspect I could get eight if I got into the business of typedeffing. Now I have a three key map and my keys are as follows:
std::vector<std::vector<Stack>> &lStackList(sStacksPlayed[mCardStacks[eStackPlay].size()][mCardStacks[eStack4].size()][mCardStacks[eStack7].size()]);
I arbitrarily chose the number of cards in the play stack, the fourth main stack and seventh main stack. I started analyzing my triple map after solving a deal and found that the maximum number of stacks in a list was consistently twelve. I had an "oh duh" moment when I realized that the most number of cards you can have on a main stack is twelve. This is good as the most number of stacks comparisons I will do on any attempted check point is twelve.
Most deals solve or don't solve fairly quickly. Periodically a deal comes up where hundreds of thousands of unique stack check points are generated. This really kills my throughput. I would like to collect stats on this.
The main recursion loop is as follows:
void PlayList::playList(const std::vector<Stack> &arCardStacks, int aCardsRemaining, int aLevel)
{
if (arCardStacks.size() == 0)
{
return;
}
// -1 means we won't skip any signifcant actions on this game
Game lGame(mSortStacks, -1, aLevel, false, true);
if (lGame.play(arCardStacks))
{
//std::wstringstream lStream;
//lStream << _T("Solved!");
//displayString(lStream.str());
mSolved++;
// game stops on first solve - I'll try to have it keep going some day
return;
}
// the number of significant actions in the previous attempt
int lEndSkip(lGame.skipPlayMoveCounter());
for (int i = 0; i < lEndSkip && !mSolved && !mStop; i++)
{
// i identifies the significant action to skip for this game
Game lGame(mSortStacks, i, aLevel, false, true);
mGamesPlayed++;
if (aLevel == 1)
{
std::wstringstream lStream;
lStream << _T("Level one step ") << i+1 << _T(" of ") << lEndSkip;
displayString(lStream.str());
}
if (lGame.play(arCardStacks))
{
//std::wstringstream lStream;
//lStream << _T("Solved!");
//displayString(lStream.str());
mSolved++;
}
else
{
if (!mSolved && !mStop && lGame.checkPointStacks().size() > 0)
{
playList(lGame.checkPointStacks(), lGame.cardsRemaining(), aLevel+1);
}
}
}
}
This recursive implementation leads to concerns about stack space and stack overruns. According to the doco, VS2008 default is 1 meg. My implementation consumes about 10K of stack for each level of recursion. I think I am OK but I need to track my maximum level of recursion. I'm printing out stats every thousand attempted solves and it never seems to solve above 30 levels of recursion. I am not sure why this is.
As I suspected, the first version of the solver was flawed. My move logic was flawed and I was skipping permutations. At a cost of making the solver slower (first version solved at a rate of about 40 deals per hour), I was able get my solution rate up to 80%. I discarded the concept of grouping stack moves and went for a far simpler implementation. Stack moves are pretty much treated just like card plays off the play stack. I also refined my strategy for check pointing stacks. My initial implementation would unconditionally check point a stack after a significant action after a skipped action. When I would go play another list, I would look for the stacks in the list of check pointed stacks and not play the stacks if they were found. I implemented a new strategy where I would mark the stacks for pending check point after a skipped action. I would then continue to play the hand and try to check point the stacks after each significant action. If the stacks were found in the previously tried list, I would leave the pending flag set and continue playing. In this manner, the program now seeks out new stacks to solve. Only when I am able to check point the stack (i.e. it doesn't exist in previously tried stacks) do I clear the pending flag. This means I have to spend more time comparing stacks but less time actually playing cards.
Lists of lists are good. My initial implementation of the lists of check pointed stacks was a std::map<int, std::vector<std::vector<Stack>>>. I used the number of cards remaining on the play stack as the key. I never analyzed this map but I figured that some lists were getting exceedingly long and required many comparisons of the stacks. I implemented a new list of check pointed stacks. It is:
static std::map<int, std::map<int, std::map<int, std::vector<std::vector<Stack>>>>> sStacksPlayed;
It has three keys and I tried to do eight but the compiler barfed on it. Something about names being too long. Three was the most I could get. I didn't bother to investigate further but I suspect I could get eight if I got into the business of typedeffing. Now I have a three key map and my keys are as follows:
std::vector<std::vector<Stack>> &lStackList(sStacksPlayed[mCardStacks[eStackPlay].size()][mCardStacks[eStack4].size()][mCardStacks[eStack7].size()]);
I arbitrarily chose the number of cards in the play stack, the fourth main stack and seventh main stack. I started analyzing my triple map after solving a deal and found that the maximum number of stacks in a list was consistently twelve. I had an "oh duh" moment when I realized that the most number of cards you can have on a main stack is twelve. This is good as the most number of stacks comparisons I will do on any attempted check point is twelve.
Most deals solve or don't solve fairly quickly. Periodically a deal comes up where hundreds of thousands of unique stack check points are generated. This really kills my throughput. I would like to collect stats on this.
The main recursion loop is as follows:
void PlayList::playList(const std::vector<Stack> &arCardStacks, int aCardsRemaining, int aLevel)
{
if (arCardStacks.size() == 0)
{
return;
}
// -1 means we won't skip any signifcant actions on this game
Game lGame(mSortStacks, -1, aLevel, false, true);
if (lGame.play(arCardStacks))
{
//std::wstringstream lStream;
//lStream << _T("Solved!");
//displayString(lStream.str());
mSolved++;
// game stops on first solve - I'll try to have it keep going some day
return;
}
// the number of significant actions in the previous attempt
int lEndSkip(lGame.skipPlayMoveCounter());
for (int i = 0; i < lEndSkip && !mSolved && !mStop; i++)
{
// i identifies the significant action to skip for this game
Game lGame(mSortStacks, i, aLevel, false, true);
mGamesPlayed++;
if (aLevel == 1)
{
std::wstringstream lStream;
lStream << _T("Level one step ") << i+1 << _T(" of ") << lEndSkip;
displayString(lStream.str());
}
if (lGame.play(arCardStacks))
{
//std::wstringstream lStream;
//lStream << _T("Solved!");
//displayString(lStream.str());
mSolved++;
}
else
{
if (!mSolved && !mStop && lGame.checkPointStacks().size() > 0)
{
playList(lGame.checkPointStacks(), lGame.cardsRemaining(), aLevel+1);
}
}
}
}
This recursive implementation leads to concerns about stack space and stack overruns. According to the doco, VS2008 default is 1 meg. My implementation consumes about 10K of stack for each level of recursion. I think I am OK but I need to track my maximum level of recursion. I'm printing out stats every thousand attempted solves and it never seems to solve above 30 levels of recursion. I am not sure why this is.
Subscribe to:
Posts (Atom)