Tuesday, September 13, 2011

Deep Waste of Time

This post is about solitaire, but it's related to my work so a little background on what I do. I'm essentially a computational biologist, that is, I study biological problems using computational methods. Computational methods are used when either 1) the scientist doesn't know math well enough to solve a problem analytically, or 2) the problem is too difficult or too long to solve analytically. Both apply to me. The major computational method that I use is simulation and I typically use a simulation to solve optimization problems. So for example, I might be interested in the optimal motion of a fruit fly wing to balance weight and maximize thrust (forward flight force). There's lots of parameters that can go into a computer model such as the wing beat frequency, and the wing beat amplitude, and how much the wing rotates during the down or upstroke, and how rapidly it rotates, etc. etc. A simulation is used to explore combinations of the different values that a parameter may take. An exhaustive search (I don't know the technical term) would just try all combinations throughout the range of values for each parameter. This can be computationally intensive and most of the solutions will be pretty dumb but if the model itself is simple (computationally quick) then a large parameter space can be searched in a short time. If the model is computationally slow then it's better to use some kind of smart strategy to search only part of the parameter space (the range of parameter values).

Still with me? One smart way to search a subset of the parameter space is to use evolutionary or genetic algorithms. I don't do these and really know little about them but essentially a population/evolution approach is used where random variation is added to the parameters in a population of "strategies" and the strategy that has the highest performance (thrust in the case of my fly wing) is selected and then mutated (that is copied and the random values are added to the parameters) and etc. etc until the strategy stops evolving, which means an optimum has been found (not necessarily the optimum because the "performance surface" could have multiple peaks and an evolutionary algorithm will climb only the nearest peak from where the strategy starts. Like I said, I've always been interested in these but I haven't really done them but smart engineers are using these to design all sorts of cool toys.

Still with me? Here is where any of this has to do with solitaire. When I first got my smart phone last year, I started playing (for the first time in my life on a computer) klondike solitaire (three cards dealt and three rounds through the deck) and noticed that my winning percentage increased. That is, I was getting better or more skillful. Prior to this I had only played solitaire with a brick and morter deck of cards and I would have argued that there is no strategy, a win is all in the luck of the shuffle. Anyway, I developed a serious addiction and took the game off my smart phone.

Then I got my ipad, which I had for about a month before I downloaded a klondike solitaire game. I'm absolutely fascinated with the strategy. Enough that I thought, I could spend a day programming a solitaire solver and then explore a strategy space and try to determine the optimal strategy. And then I thought, I could learn something about evolutionary algorithms by implementing one. I did a little google and google scholar search and found that a few mathematicians have addressed solitaire but not many. Some of these address a very basic question, how many shuffles are winnable? This problem is way too hard for an analytical solution (first it is dependent on a specific strategy but its too hard even given that).  That's an interesting question but I'm more interested in strategies. For example, if I just dealt a 4 clubs and I have a six of spades as the top card in my building stacks and a five of hearts up top in my suit stacks, do I move the five of hearts down to the build stacks so I can play the 4 of clubs? I have one card less in my suit stack (so I'm further away from winning) but I have one more card in my build stack (so I'm closer to winning) but certainly there is more of a cost to pulling a card from a suit stack than gaining a card in the build stack so...what's a computational biologist to do?

Write some code. I don't mean writing code for ME to play solitaire I mean write code for the COMPUTER to play solitaire. Sort of like Deep Blue. What I thought would take a day has taken about a week and lots of intense hours. I'll say this, even the simplest "strategy" requires a lot of decisions that we don't even think of as decisions. But you are forced to recognize them when you're coding the game. My initial strategy is pretty dumb as it cannot see ahead more than 1 step and evaluate the consequences (so if I see an ace as card 2 in the three cards that I've just dealt it may be worth moving a card down from the suit stack to the build stack to be able to play the top card - and therefore the ace):

definitions
1.The build stacks are the 7 columns of face-up cards that you build in descending order with alternating color
2. The suit stacks are the 4 columns of single suit cards that are built in ascending order (if completed the game is one)
3. The talon is the single pile of face up cards that can be played to the build or to the suits
4. The pile the the single pile of face down cards that are turned over, three at a time, and added to the talon.
5. The down stacks are the face down cards beneath the build stacks

The strategy, in order of priority:
1. play the build cards to the suit stack
2. play the talon to the suit stack
3. play build kings to empty build columns with priority (the first king moved) given to the king on the build stack on top of the shortest down stack
4. play talon kings to empty build columns
5. play one build column to another with priority (the one being moved) given to the build stack on top of the shortest down stack
6. play the talon to the build stack

So there is 1) no moving parts of a build stack to another build stack (to free up a card that can move to the suit stack, say) and 2) no moving suit stack cards back to the build and 3) no choosing not to do one of the above (such as not playing a talon card). I would consider these three more advanced strategies but each has lots of flavors. At this point I may be satisfied with simply having coded the computer to win a game because implementing more advanced strategies would be even more of a time waster.

Which raises the question, can I make money out of this? Probably not. My dumb computer has a winning percentage of about 1%, which seems awefully low, even for this simple algorithm. By comparison, I've won 17% of the 1100 games that I've played on my ipad. Maybe I'll try to create an evolutionary algorithm and let it evolve a more optimal strategy.

postscript. At Twin Brook tonight Ian said he got through most of this post before he realized not only was I taking my time relating this to running but I probably wasn't going to ever get there. So here is the connection: This is the sort of crap I think about when I run solo!

Here is my computer's first win! (what is shown is the top card of the build stacks from start to finish)


  playmap(htops[, 1])  X1  X2  X3  X4  X5  X6  X7
1                start  H3 D11 C13  C7 C10  C2  D2
2       build to build  H3 C10 C13  C7  D6  C2  D2
3       build to build  H3 C10 C13  D6 H13  C2  D2
4       build to build  C2 C10 C13  D6 H13  S5  D2
5       build to build  C2 C10 C13  S5 H13  S2  D2
6       talon to build  C2 C10 H12  S5 H13  S2  D2
7        talon to suit  C2 C10 H12  S5 H13  S2  D2
8        build to suit  H3 C10 H12  S5 H13  S2  D2
9       build to build  S2 C10 H12  S5 H13 H10  D2
10      talon to build  S2 C10 H12  S5 C12 H10  D2
11      build to build  S2  S3 H12  S5 C10 H10  D2
12      build to build  S2  D2 H12  S5 C10 H10  C6
13       talon to suit  S2  D2 H12  S5 C10 H10  C6
14      talon to build  S2  D2 H12  H4 C10 H10  C6
15      build to build  S2   . H12  D2 C10 H10  C6
16           play king  S2 H12  D1  D2 C10 H10  C6
17       build to suit  S2 H12  D3  D2 C10 H10  C6
18       build to suit  S2 H12  D3  S3 C10 H10  C6
19       build to suit  S2 H12   .  S3 C10 H10  C6
20           play king  S2 H12 C10  S3  H6 H10  C6
21      talon to build  S2 H12 C10  S3  H6  S9  C6
22       talon to suit  S2 H12 C10  S3  H6  S9  C6
23       build to suit  H3 H12 C10  S3  H6  S9  C6
24       build to suit  H3 H12 C10  H4  H6  S9  C6
25      talon to build  H3 H12 C10  H4  H6  H8  C6
26      build to build  H3 H12 C10  S8  H6  H4  C6
27      talon to build  H3 H12  H9  S8  H6  H4  C6
28       talon to suit  H3 H12  H9  S8  H6  H4  C6
29       build to suit   . H12  H9  S8  H6  H4  C6
30       build to suit   . H12  H9  S8  H6  S5  C6
31      build to build   . H12  S8 C11  H6  S5  C6
32      build to build   . C11  S8  D5  H6  S5  C6
33      build to build   . C11  S8   .  H6  S5  D5
34      build to build   .  S5  S8   .  H6 D13  D5
35           play king D13  S5  S8   .  H6  C9  D5
36      talon to build D13  S5  D7   .  H6  C9  D5
37      build to build D13  S5  D5   .  H6  C9 S12
38      build to build S12  S5  D5   .  H6  C9  S4
39       build to suit S12  S5  D5   .  H6  C9  D9
40       build to suit S12  D6  D5   .  H6  C9  D9
41      talon to build S12  D6  C4   .  H6  C9  D9
42       talon to suit S12  D6  C4   .  H6  C9  D9
43       talon to suit S12  D6  C4   .  H6  C9  D9
44      talon to build S12  C5  C4   .  H6  C9  D9
45      talon to build H11  C5  C4   .  H6  C9  D9
46       talon to suit H11  C5  C4   .  H6  C9  D9
47       build to suit H11  C5  D5   .  H6  C9  D9
48       build to suit H11  D6  D5   .  H6  C9  D9
49      talon to build H11  D6  D5   .  H6  C9  C8
50      talon to build S10  D6  D5   .  H6  C9  C8
51       talon to suit S10  D6  D5   .  H6  C9  C8
52       build to suit S10  D6  C6   .  H6  C9  C8
53       build to suit S10  C7  C6   .  H6  C9  C8
54       build to suit S10  C7  D7   .  H6  C9  C8
55       build to suit S10  H8  D7   .  H6  C9  C8
56       build to suit S10  H8  S8   .  H6  C9  C8
57       build to suit S10  H8  H9   .  H6  C9  C8
58       build to suit S10  H8  H9   .  H6  C9  D9
59       build to suit S10  H8  H9   .  H6   .  D9
60      build to build  D9  H8  H9   .  H6   .  H5
61       build to suit  D9  H8  H9   .  H6   . S13
62       build to suit  D9  H8  H9   .  D8   . S13
63       build to suit  D9  H8  H9   .   .   . S13
64       build to suit S10  H8  H9   .   .   . S13
65       talon to suit S10  H8  H9   .   .   . S13
66      talon to build S10  H8  H9   .   .   . D12
67       talon to suit S10  H8  H9   .   .   . D12
68       build to suit S10  S9  H9   .   .   . D12
69       build to suit S10 H10  H9   .   .   . D12
70       build to suit H11 H10  H9   .   .   . D12
71       build to suit H11 H10 C10   .   .   . D12
72       build to suit H11 C11 C10   .   .   . D12
73       build to suit S12 C11 C10   .   .   . D12
74       build to suit S12 C11 D11   .   .   . D12
75       build to suit S12 H12 D11   .   .   . D12
76       build to suit S12 C13 D11   .   .   . D12
77       build to suit S12 C13 C12   .   .   . D12
78       build to suit S12 C13 H13   .   .   . D12
79       build to suit S12   . H13   .   .   . D12
80       build to suit S12   .   .   .   .   . D12
81       build to suit S12   .   .   .   .   . S13
82       talon to suit S12   .   .   .   .   . S13
83       build to suit D13   .   .   .   .   . S13
84       build to suit   .   .   .   .   .   . S13
85       build to suit   .   .   .   .   .   .   .

10 comments:

  1. My brain officially hurts after reading that.

    ReplyDelete
  2. Oh my...meanwhile on the homefront...we need an evolutionary algorithm for the ever-growing To Do list...

    ReplyDelete
  3. Wow, I got nothin'. We need to do a long run sometime so you can go in to more detail for me...

    ReplyDelete
  4. Yeeeeh that was Cacky's first comment on any blog post evah!

    ReplyDelete
  5. There's no way I'm reading that.

    ReplyDelete
  6. snom8n: what I wrote is far more intelligible than the pomo stuff you had to read in college.

    por ejemplo: “Society is unattainable,” says Derrida. Therefore, Foucault’s analysis of subtextual socialism suggests that narrativity may be used to entrench class divisions. The opening/closing distinction prevalent in Eco’s Foucault’s Pendulum is also evident in The Name of the Rose, although in a more subconceptualist sense.

    The characteristic theme of the works of Eco is the collapse of textual art. In a sense, Derrida uses the term ‘the neocapitalist paradigm of narrative’ to denote the bridge between class and society. If rationalism holds, the works of Eco are modernistic.

    Therefore, Hamburger[2] implies that we have to choose between cultural narrative and dialectic situationism. Debord promotes the use of posttextual material theory to analyse and modify class.

    In a sense, the premise of subtextual socialism suggests that reality is capable of significant form. Baudrillard suggests the use of cultural narrative to deconstruct capitalism.

    But Debord’s critique of the neocultural paradigm of narrative holds that consensus must come from communication. Bataille promotes the use of rationalism to read sexual identity.

    However, cultural narrative states that the goal of the observer is social comment, given that consciousness is interchangeable with language. The main theme of Hubbard’s[3] analysis of subtextual socialism is the role of the reader as poet.

    ReplyDelete
  7. Jeff - I will get back to you once I talk to Val and have her translate all this into squirrel-ese for me. p.s. are you doing meth? p.p.s. if you are doing meth, could you come over and do some yard cleanup for me?

    ReplyDelete
  8. I think the cheese has slid off Jeff's cracker a little...

    ReplyDelete
  9. How dare you?!?! I miss Derrida.

    ReplyDelete