Solitaire Variant - Optimization

Need help with the following optimization.

The game is a type of solitaire. You play with a deck of 30 cards, ranked A to 10, where A is always 1. You may choose how many cards of each rank go into your deck before you start, with no limits. The optimization is to construct your deck to perform as well as possible in the following game.

The game is played in 10 rounds; the goal is to score as many total points as possible. By 'as many points as possible', I'm referring to maximizing the long-run average of your score if you were to play it an infinite number of times, as opposed to a high-volatility strategy designed to try to get as high a score as possible if you only have a single attempt.

Round 1:
-Draw three of your 30 cards at random.
-You may score up to 1 point this round. The point is scored if you have an A in your hand, and you choose to discard it (leaving you with two cards). Otherwise, score zero points, and keep your 3 cards. You may not discard any cards greater than rank 1, but you are not forced to discard any cards if you don't want to.

Round 2:
-Draw an additional card at random.
-You may score up to 2 points this round, scored by discarding some combination of As and 2s (one A would score 1 point; two As or one 2 would score 2). The sum of your discards cannot exceed a combined value of two.

Round 3:
-Draw an additional card at random.
-You may score up to 3 points this round, scored by discarding some combination of As, 2s and 3s, as long as the sum of your discards do not exceed a combined value of three.

Rounds 4-10:
-Same idea; draw a card, try to maximize discards each round. After Round 10, tally up your score from each round to get your total points.

-If you run out of cards in a particular round, you do NOT get to draw any new cards; you must wait until you start the new round.

Thanks,
Mike

Cool idea. So a perfect score in a given instance is 55? And cards may only have natural value? (no 3.4s or PIs?)

I think I'm going to try putting together a genetic algorithm to optimize.

A useful starting lower bound: value of decks of single denomination

Deck composed of	EV (var = 0)	cards in hand at end
1	13	0
2	26	0
3	39	0
4	40	3
5	35	6
6	30	8
7	28	9
8	24	10
9	18	11
10	10	12

So a deck of 4s has EV 40, that's what need to be beaten

Thanks for helping out; both your prior assumptions are correct, the max score is 55 and you must use whole-number ranks.

I think you'd want a deck heavy in 4s and 3s, with some 2s, 1s and 5s sprinkled in there.

And calculating the EV of a deck with different ranks may require some decision-making in some rounds. It might be optimal to always discard to score, but it might not. That would be a bear to program

Here is the notation I have used, deck=[a, b, c, d, e, f, g, h, i, j] where a is the number of 1s, b is the number of 2s, .. j is the number of 10s.

I finished building an evaluator for a given deck. I have not yet done any real optimization, but a new lower bound choice is [0,0,5,10,10,5,0,0,0,0]. This deck has an EV of 48.0352. It has on average .1541 cards left in the hand at the end.

My play assumption is play the biggest card in your hand. If there is still value in a round, then play the next highest available card. Continue until there are no valid plays that round.

Whoops, found a bug in my code. trying again

Bug seems to be fixed.

Current best deck: [2, 4, 6, 6, 6, 4, 2, 0, 0, 0], EV = 48.98, avg cards left in hand at end = 0.9250

I'm now letting the GA do it's thing. Currently my best deck: [0,4,6,5,6,5,1,2,0,1], EV = 50.04, avg cards left in hand at end = 2.7107

Quote: endermike

My play assumption is play the biggest card in your hand. If there is still value in a round, then play the next highest available card. Continue until there are no valid plays that round.

I'm not sure there. If you have 3,3,4 and you're on 6, is it better to play 4 or 3,3?

Quote: MathExtremist

I'm not sure there. If you have 3,3,4 and you're on 6, is it better to play 4 or 3,3?

Neither am I. I just made a simple assumption and looked where it went. Speaking of which I think that there will be very little improvement over decks similar to:

Deck	EV	E[cards left in hand]
[0 5 6 6 5 4 2 1 1 0]	50.32	2.04
[0 5 6 5 5 4 2 2 1 0]	50.35	2.42
[0 5 7 5 5 3 1 2 1 1]	50.30	2.42

for the simple rule I used. I will rewrite the rule to maximize the value of cards played in a round. The big hanging question is which is better to play in round R, R-3&3 or R-2&2. It may be deck dependent. I'm going to go with "save the smallest card" (and play the R-3&3) for now. Which would mean in round 8, on a hand of {1, 2, 3, 5, 6} we would play 6&2 to save the 1. I have no idea if this is optimal.

Never got around to thanking you...thanks!

Quote: endermike

I will rewrite the rule to maximize the value of cards played in a round. The big hanging question is which is better to play in round R, R-3&3 or R-2&2. It may be deck dependent. I'm going to go with "save the smallest card" (and play the R-3&3) for now. Which would mean in round 8, on a hand of {1, 2, 3, 5, 6} we would play 6&2 to save the 1. I have no idea if this is optimal.

That's a good testcase: see if you play 6+2 or 5+3, based on what other cards you could draw in rounds 9 and 10, which choice maximizes your total. E.g. is one choice in round 8 uniformly better than the other, or does it depend -- and if so, which direction does the needle point?

So, I just finished a long run. The strategy used was find the largest total play possible for the given hand in a round. To break ties between plays, choose the one which preserves the smallest card. In the event that multiple candidate plays treat the smallest card the same, move on to comparing how they treat the the second smallest card and so on.

[Side note: in my {1,2,3,5,6} example, we would play the 5&3, not 6&2 as I suggested]

The best deck I found was: [0,7,8,6,3,2,2,1,1,0], with an EV of 50.74 and an expected cards left in hand of 2.28.

True optimal strategy for a given deck is a difficult stochastic optimization problem in itself. I would guess that for near optimal decks that optimal play provides not a lot of value over a good heuristic rule like the one ME suggested and is now being used.