Monday, September 26, 2011
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 . . . . . . .
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 . . . . . . .
Monday, September 5, 2011
managing calf pain
The evidence for what works in managing sports injuries is one of the more frustrating areas of health-related research that I've come across. During my MP run 16 days ago, I got a sudden calf pain that felt something like a cramp. At the time I didn't think it was a cramp because my gastrocnemius muscle (at least) wasn't obviously balled up. But maybe it was the deeper soleus. I assumed it was some sort of muscle strain (tearing). My management included no stretching, no strength training, no massaging, no nsaids, no icing, and no heating but only initial rest then running with short walk recoveries (note on my pain scale: 3 is noticeably sore, 5 is painful to run, and 7 is painful enough to not run, and 9 is painful enough to want to amputate). The initial pain was a 7.
S - off, sore
M - off, sore
T - 2.2 miles alternating walk/jog every 1/3 to 1/2 mile, pain = 2-3
W - attempted to run back cove 5k at 8 min/mi but at mile 1.1 pain went from 2-3 to 4-5. Continued walking/jogging rest of 5K with pain at 4, no soreness in evening
Th - 3.7 miles at back cove. Ran (7:35-8 m/m) 3.1 miles at pain=1-2 then sudden jump to 4-5. Walked remaining 1/2 mile, no soreness in evening
F - 4.8 miles on Brook rd (mostly flat). Ran (8 m/m) 3 miles at pain = 1-2 then sudden jump to 4. Walked most of rest with some light jogging. Sore (pain=1) that evening.
S - 4.8 on Brook Rd. 4 x 1 mile with 1/4 mile walk recoveries. Pain = 2. worked well.
S - off
M - 3 x 2 miles (7:12-7:59 m/m) @ back cove with 1/4 mile walk recoveries. Pain = 1. noticed pain on stairs before though (much more than running). Speed didn't seem to aggravate soreness.
T - off
W - 7.7 at RIT perimeter rd. 3 x 2.5 miles with 1/8 mile walk recoveries. Progression: 7:40 7:13 7:10 6:42 6:32 6:21. Last 1/3 at 6:08. Pain = 0.
Th - 4 + 2.5 + 1.5 mile with 1/8 mile walk recoveries. Brook Rd. Pain=0 first 6 mi then =1 last two.
F - 3 x 2 miles with 1/8 mile walk recoveries. 1st 3 miles community park trail last 3 on road. Progression: 6:42 6:48 (long hill) 6:22. Pain = 0
S - 10.5 very easy miles at Bradbury with several very short walk breaks. Pain = 0
S - 13.1 road (Woodville/Woods/Winn) at 7:30 min/mi with 4 1/8 walk recoveries every 3 miles. Pain = 0
So while I cannot say that the run-walk strategy was necessary for effective management (since I didn't try continuous running, at least after day 4), the run-walk strategy at least allowed me to run decent mileage and even some fast miles. To be continued...
S - off, sore
M - off, sore
T - 2.2 miles alternating walk/jog every 1/3 to 1/2 mile, pain = 2-3
W - attempted to run back cove 5k at 8 min/mi but at mile 1.1 pain went from 2-3 to 4-5. Continued walking/jogging rest of 5K with pain at 4, no soreness in evening
Th - 3.7 miles at back cove. Ran (7:35-8 m/m) 3.1 miles at pain=1-2 then sudden jump to 4-5. Walked remaining 1/2 mile, no soreness in evening
F - 4.8 miles on Brook rd (mostly flat). Ran (8 m/m) 3 miles at pain = 1-2 then sudden jump to 4. Walked most of rest with some light jogging. Sore (pain=1) that evening.
S - 4.8 on Brook Rd. 4 x 1 mile with 1/4 mile walk recoveries. Pain = 2. worked well.
S - off
M - 3 x 2 miles (7:12-7:59 m/m) @ back cove with 1/4 mile walk recoveries. Pain = 1. noticed pain on stairs before though (much more than running). Speed didn't seem to aggravate soreness.
T - off
W - 7.7 at RIT perimeter rd. 3 x 2.5 miles with 1/8 mile walk recoveries. Progression: 7:40 7:13 7:10 6:42 6:32 6:21. Last 1/3 at 6:08. Pain = 0.
Th - 4 + 2.5 + 1.5 mile with 1/8 mile walk recoveries. Brook Rd. Pain=0 first 6 mi then =1 last two.
F - 3 x 2 miles with 1/8 mile walk recoveries. 1st 3 miles community park trail last 3 on road. Progression: 6:42 6:48 (long hill) 6:22. Pain = 0
S - 10.5 very easy miles at Bradbury with several very short walk breaks. Pain = 0
S - 13.1 road (Woodville/Woods/Winn) at 7:30 min/mi with 4 1/8 walk recoveries every 3 miles. Pain = 0
So while I cannot say that the run-walk strategy was necessary for effective management (since I didn't try continuous running, at least after day 4), the run-walk strategy at least allowed me to run decent mileage and even some fast miles. To be continued...
Subscribe to:
Posts (Atom)