Dominion > Puzzles and Challenges

Minimizing Complexity

(1/2) > >>

Razzishi:
Apologies if this topic has been approached before.

I hereby define the Complexity of a puzzle solution:

Complexity = unique named Kingdom cards gained * Total cards gained * re-Shuffles needed.  (Or C = K * T * S.)

Feel free to comment on my choice of variables and the method in which they are composed; it was sorta thrown together with the constraint that it use variables related to length of game, size of deck, and number of piles needed to be specified.

What is the absolute minimum complexity value for a finished (piles or 8 Province) solitaire game?  Don't think too hard about it. 
How many turns does it take?  I get 16, which I have very good reason to believe is the minimum but still need to determine if my method is sufficiently rigorous. 

What about the minimum non-zero complexity?  I haven't started real work on yet, but it's my intention to do so as I get time to.

I offer this definition mainly as a way of suggesting a way of judging whether a certain answer for the various puzzles in this forum is in some way simpler than another.  If you can state what the complexity of your given solution is at the outset, you can give people something to shoot for (assuming you don't continually move the goal posts so that your solution is the only one that works).  The puzzles/questions are merely there as interesting things to discuss.

chwhite:
Absolute minimum should be zero, since pure Big Money doesn't buy any unique Kindgom Cards.

As for your second challenge, my first thought gets it down to 90.

Turn 1: n Coppers =  Chancellor
Turn 2: -, reshuffle
Turn 3: Chancellor + 4 Coppers = Gold, reshuffle
Turns 4-10: Gold + Chancellor + 3 Coppers = 7 Provinces, 7 reshuffles
Turn 11:  Gold + Chancellor + 3 Coppers = Province, game end

1 unique named Kingdom card (Chancellor)
10 total cards gained (Chancellor, Gold, 8 Provinces)
9 reshuffles

Compexity = 1 * 9 * 10 = 90

I haven't tested any others, but I wouldn't be surprised if this is the best solution.

timchen:
Frankly speaking, I feel this question depend too much on the definition of complexity, which is quite arbitrary.

And maybe let me digress: I am actually somewhat tired of seeing questions/puzzles containing words such as "minimum", in the sense that this can be a lousy way to make puzzles that definitely have an answer. Without specific interesting tricks involved, it just cannot get me interested.

Razzishi:

--- Quote from: timchen on August 08, 2011, 02:20:01 am ---Frankly speaking, I feel this question depend too much on the definition of complexity, which is quite arbitrary.

And maybe let me digress: I am actually somewhat tired of seeing questions/puzzles containing words such as "minimum", in the sense that this can be a lousy way to make puzzles that definitely have an answer. Without specific interesting tricks involved, it just cannot get me interested.

--- End quote ---

I wholeheartedly agree that it's completely arbitrary.  I don't really intend my questions to be interesting in their own right, but I'm more interested in developing a metric where one can compare various solutions to other problems, and I sorta needed to place to start that discussion.  A very small amount of thought was put into my definition; it's only a first suggestions and contains factors that I feel are important.  You increase complexity of a puzzle solution the more you specify exactly what needs to happen in terms of which cards to make available, which cards to purchase, and what the order of a shuffle it.  You could just add them all up instead of multiplying them, but there's a specific reason I went with multiplication for my initial presentation.

And if it's not interesting, that's fine.

Razzishi:
The answer to the second part that got my initially interested in this idea.  After noticing what a certain combo was capable of, I was interested just how fast it could be in theory.  Upon working it out I was quite struck by how quickly and easily it could win the game given perfect shuffles, and just how tight the solution was in some respects.

X = Copper or Estate

Open Silver/Bridge - shuffle 1 (B, S, 7*C, 3*E)
t3/4: BSCCC -> King's Court / CCCCE -> Bridge / next hand has EE - shuffle 2 (B*2, K, S, 7*C, 3*E)
t5: EEKBC -> King's Court
t6: BSXXX -> Bridge / next hand has XXXX - shuffle 3 (B*3, K*2, S, 7*C, 3*E)
t7: XXXXX -> nothing
t8: KKBBB -> buy 8 provinces

Kingdom cards needed: 2 (King's Court, Bridge)
Gained cards: 14 (1 Silver, 2 King's Court, 3 Bridge, 8 Provinces)
Shuffles: 3

Complexity: 84

I never actually calculated the exact complexity of my solution before, so I was somewhat surprised when it came in as better than chwhite's, whose solution I feel in some ways is "better", but the definition of the metric is somewhat arbitrary and by other measures a different one might have come out as "simpler".  I personally am now of the opinion that the number of gained cards needs to be weighted less and the shuffles weighted more, each of which favors one of our solutions, but again, it would be somewhat arbitrary to decide just how to weight them and thus I just went with what was simple and had the required properties.

Navigation

[0] Message Index

[#] Next page