Dominion Strategy Forum

Dominion => Dominion Articles => Topic started by: david707 on June 13, 2011, 06:01:53 pm

Title: Treasure Map Probabilty (Can also be applied to other cards)
Post by: david707 on June 13, 2011, 06:01:53 pm
In this article: http://dominionstrategy.com/2011/03/09/basic-opening-probabilities/
theory asked "...probability each deck cycle of activating Treasure Maps, assuming n Treasure Maps and p cards in the deck".
In my workings, I've assumed that you have t Treasure maps and n cards in total. It is also assumed n is divisible by 5 for simplicities sake. The probability below is that in at least one hand you have at least 2 treasure maps, it is also one minus the probability of every treasure map being in a different hand. It also assumes you don't have draw cards like lab or Village/Smithy, but you can represent great halls and other +1 Action +1 Card Kingdoms by not counting them when counting the number of cards in your deck.

The answer:
(http://i226.photobucket.com/albums/dd82/david707/treasuremapprobformula.png)

This can be applied to other cards as well, for example, you could make t the number of terminal actions you have and see what the chances are of drawing two together.

Workings:
Involves some pretty advanced mathematics and I expect only a few people will understand the derivation. Basically, I'm too lazy to post them, but if someone requests I will.

If you have any probability questions you would like answered (relating to Dominion), then please say.

Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: theory on June 13, 2011, 07:48:53 pm
Well, I would like to see the derivation, just to see how over my head it is :)

Say t = 2 and n = 10, 15.  What is p?

Could you graph that as well?  Graph n vs p, and have different curves for each t.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: timchen on June 13, 2011, 07:52:28 pm
Sorry, but I lol'ed when I saw you said that the math is pretty advanced. :p No offense intended, but I think stuff like Truerank is quite a bit more advanced than that.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: theory on June 13, 2011, 07:56:03 pm
There are different kinds of advanced ... what MIT mathematicians find simple might not be so simple for lowly lawyers :P
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: timchen on June 13, 2011, 08:04:51 pm
The problem is to count how many ways there are without more than 1 treasure map in a hand. When t<=n/5, you choose t "bins" out from the n/5 bins to put in the treasure map, and for each bin there are 5 ways to put it. This gives 5^t C(n/5,t). Divide this with the total number of ways to arrange the draw, which is C(n,t), you get the answer.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: Teproc on June 13, 2011, 08:06:14 pm
For example, as a political sciences student, I don't understand this result, and much less so the math involved to find it.

What does this result actually amounts to, basically ?
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: Kirian on June 13, 2011, 08:53:17 pm
Of course, this only works for n mod 5 = 0, which leaves out a heck of a lot of possibilities.

Teproc:  the exclamation points in the formula represent the factorial function.  That's the product of all whole numbers from the number down; so, for 5, it's 5 4 3 2 1 = 120.  Because the way the OP has this set up results in huge factorials (15! has 13 digits), it helps to break it down and cancel things out a bit.  For theory's question, t = 2, n = 15, we have:

n/5 = 3
5t = 25

The first factorial on top is 3!, and the first on the bottom is 1!.  Divide those and you get 3 2 = 6
The second factorial on top is 13!, and the second on the bottom, n!, is 15!.  Divide them, and you get 15 14 = 210 (on the bottom).

Simplified, then, the fraction is (6 25)/(210) = 0.714

Therefore, p (the chance of getting 2 Maps this cycle) is 0.286, or about 29%.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: Teproc on June 13, 2011, 09:47:35 pm
Very interesting, thanks for the clarification.

29% is a bit more than I expected, but it sounds about right in that it confirms that you should probably never buy it without heavy trashing or some other kind of enabler (e.g Warehouse, Haven).
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: david707 on June 14, 2011, 05:56:07 pm
The problem is to count how many ways there are without more than 1 treasure map in a hand. When t<=n/5, you choose t "bins" out from the n/5 bins to put in the treasure map, and for each bin there are 5 ways to put it. This gives 5^t C(n/5,t). Divide this with the total number of ways to arrange the draw, which is C(n,t), you get the answer.

Well explained, when I said the maths was pretty advance, I learnt how to do that sort of thing at degree level and assumed most people on the forum aren't degree level mathematicians.

Of course, this only works for n mod 5 = 0, which leaves out a heck of a lot of possibilities.
I did do a more complex formula assuming that you draw you last few cards and nothing else, but that doesn't happen in dominion. The question was per deck cycle, so when you draw those last few cards you shuffle anyway.

A nice table:
(http://i226.photobucket.com/albums/dd82/david707/tmapprob.png)

And a graph:
(http://i226.photobucket.com/albums/dd82/david707/tmapgraph.png)

Edit: t=9 and t=10 were not included in the graph, both appear as straight lines at 1.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: rrenaud on June 14, 2011, 06:13:10 pm
Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: david707 on June 14, 2011, 06:27:49 pm
Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

I probably should have said "University Level", which I think is the same in America and UK (Although I can imagine learning that kind of thing before Uni).
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: Axe Knight on June 15, 2011, 11:13:38 pm
I was a Mathematical Statistics major, and have tried to derive what you did, but got stuck.  Would love to see the workings of your proof.   :)
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: david707 on June 16, 2011, 06:21:24 pm
Okay, here are the workings:
The formula is 1 minus the probability of not matching any tmaps, so how do we work that out?
We need the number of ways to not match divided by the total number of ways to draw the deck.
The total number of ways (b) is easiest, b=n!/((n-t)!t!) (see http://en.wikipedia.org/wiki/Combination).
Now for the number of ways to not match, we need to draw something like this, where K represents a non tmap card:
{KKKKT,KKKKT,KKKKT,...,KKKKK,KKKKK,...}
Overall there will be t hands of KKKKT and (n/5)-t hands of KKKKK. Now it doesn't matter where the T is in the KKKKT hands, it can be in 5 different places in each hand, giving us 5^t. Also the hands don't have have to be in that order, their are (n/5)!/(t!((n/5)-t)!) orders to draw these hands, using combinations again. So the number of ways to not match (a) is a=((5^t)(n/5)!)/(t!((n/5)-t)!).
Finally we find a/b and the (t!)'s cancel, do 1 minus to get the required formula.
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: PetterTB on June 20, 2011, 07:06:04 am
Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

Does that match a bachelor at the university? A master?
Title: Re: Treasure Map Probabilty (Can also be applied to other cards)
Post by: david707 on June 20, 2011, 05:36:42 pm
Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

Does that match a bachelor at the university? A master?

Okay, I'll try and clear this up. I'm currently studying Mathematics at University and I'm reasonably confident university is the same in the UK and USA. I'm effectively doing a Bachelor's degree which also seems to be the same in the UK and USA.