Rob Renaud
United States
New York
New York
-
You have a Race deck in front of you. You are going to draw cards from the deck until you have all abilities.
What is the expected number of cards to draw to get all abilities? Can you compute this efficiently and exactly if you are sampling without replacement? How does this number change as you start your hand with various home worlds? What would you estimate this number at before running the code?
I think this number will give a pretty good ranking of the likelihood of drawing the all abilities goal. I'd expect Old Earth and Separatist Colony to be favorites.
This Race stats spreadsheet might be useful. I converted to an easily parsable text file, with frequency counts and abilities listed, and an encoding of the ability subset for your maximal laziness.
This is from a board gaming blog a friend of mine and I are starting. http://www.bgholic.com/story/race-galaxy-all-abilities-coder...
-
Chris Ferejohn
United States
San Francisco
California
Pitying fools as hard as I can...
-
By "abilities" here do you mean "1 power usable in every phase"? Do trading and "normal" consuming count separately?
-
Rob Renaud
United States
New York
New York
-
It's the same as the goal from the expansion, trade and consume count separately.
-
BT Carpenter
United States
Reston
Virginia
-
More importantly, is this 'get in hand' or 'play to the board'?
Because play to the board needs not only the cards, but the ability to play them, and some of the abilities might make it easier to get others to the table.
-
Rob Renaud
United States
New York
New York
-
I simplified the game extremely. The question is merely about drawing cards from a race deck in a random fashion, not actually playing the game. Because of this, the model underestimates the difficulty in getting a settle power, since lots of military worlds that provide settle powers already require one.
-
Chris Tyler
United States
Minnetonka
Minnesota
-
To clarify the problem, all you can really express here is the probability as a function of the cards seen. For instance, if the seven cards with development powers (investment bank, public works, investment credits, and galactic federation) are the last seven cards in the deck, you need to draw all but six of the cards to have a 100% certainty of drawing all the powers.
There are, as far as I can recall, fewer development powers than anything else. I can think of several approaches to solve this problem. The simplest is simply to write a monte carlo code and run it 10,000 times. Sounds like fun. I'll see what I can do.
Regards,
Chris
-
Rob Renaud
United States
New York
New York
-
Well, I want to compute the expected value of the number of cards drawn until you have collected all abilities, given that you are drawing cards at random from the deck. If you sample with replacement, I can give you a reasonably efficient method to calculate the exact answer. If you draw without replacement, I cannot calculate the exact answer.
But yeah, monte carlo is extremely simple to code.
Perhaps I am a bit foolish in the insistence of drawing with replacement for mathematical purity of the exactness of the answer, given that the problem is already full of hacks and approximations. That is, I am getting an exact answer to a question which is only an approximation of something that I really care about, so why the instance on exactness? Having said that, there were academic articles published on this very problem in 2001, which I discovered only after I solved it.
-
ackmondual
United States
Virginia
-
And then one should take into account cards such as Mining Conglomerate. That card alone gets you $ through V right there, 3 out of 6 powers.
-
David desJardins
United States
Burlingame
California
-
rrenaud wrote: Well, I want to compute the expected value of the number of cards drawn until you have collected all abilities, given that you are drawing cards at random from the deck.
If I understand correctly, this is a coupon collector problem. It's complicated because some cards have more than one ability, right? If each card had at most one ability, then you can solve it exactly as follows:
suppose there are n(1) cards with ability type 1, n(2) cards with ability type 2, ..., n(k) cards with ability type k, and n(0) cards with no ability. Assume n(1),n(2),...,n(k) are all positive.
Let n = n(1)+n(2)+...+n(k)+n(0).
If you draw m cards, what's the probability that you get every type of ability at least once? The formula is based on "inclusion-exclusion":
Let K = \{1,2,...,k\}, the set of different ability types.
Then p(m) = \sum_{S \subseteq K} (-1)^{#S} ((n - \sum_{j in S} n(j)) choose m)/(n choose m). Note that p(0)=0 and p(n)=1.
Then, the expected number of cards until you collect every type is
E = \sum_{m=1}^n m*(p(m)-p(m-1)) = n - \sum_{m=1}^{n-1} p(m)
-
David desJardins
United States
Burlingame
California
-
You can compute an exact answer to the general problem, where some cards have more than one ability type, using dynamic programming.
Let K=\{1,2,...,k\} be the set of ability types.
Let S \subseteq K be a subset of ability types. Suppose that, after looking at m cards, S(m) is the set of ability types that you've seen so far.
When you draw the next card, it will have some new set of ability types T(m+1), and so, after looking at m+1 cards, you'll have seen the set S(m+1) = S(m) \union T(m+1).
The key point is that the conditional probability distribution P(S(m+1)|S(m)) doesn't depend on exactly which m cards you've seen so far, only on which types you've seen so far. Specifically,
P(S(m+1)=S|S(m)=R) = #{cards that have all of the ability types in S\R and none of the ability types in K\S} / (n-m)
except when S=R we have
P(S(m+1)=S|S(m)=S} = (#{cards that have no ability types in K\S} - m) / (n-m).
So, we start with the rule:
P(S(0)=S) = 1 if S is the empty set, 0 otherwise
And then we can apply the recursive formula:
P(S(m+1)=S) = \sum_{R \subseteq S} P(S(m)=R)*P(S(m+1)=S|S(m)=R)
to compute P(S(1)=S) for every S.
Then we can compute P(S(2)=S) for every S. And so on.
Then, the desired expectation is
E = n - \sum_{m=1}^{n-1} P(S(m)=K).
-
Daniel Cristofani
United States
Portland
Oregon
-
rrenaud wrote: I think this number will give a pretty good ranking of the likelihood of drawing the all abilities goal. I'd expect Old Earth and Separatist Colony to be favorites.
Doomed World is identical to Separatist Colony for these purposes, and all start worlds have expectation between 19 and 22. Whether you get a development power in your starting hand is much more important than what start world you get. Also, since the distributions are right-skewed, the point at which you have a 50% chance of having the full set is somewhat earlier than the number of cards you "expect" to have to draw; I've noted both here. And I've given the numbers in full since you were interested in mathematical exactness. Of course these rely on the correctness of that text file, which calls Separatist Colony "Separatist_Homeworld", and they're for Race+Gathering Storm.
None: 4400387455748537558303863597/198825366204616124073391200, or about 22.1319. 51.7183% at 19.
Old Earth: 1845390726511/87934210650, or about 20.986. 52.4634% at 18.
Epsilon Eridani: 13364897379527/610850611800, or about 21.8792. 52.217% at 19.
Alpha Centauri: 1819664037378577708403/83029804658750149200, or about 21.9158. 52.2032% at 19.
New Sparta: 1819664037378577708403/83029804658750149200, or about 21.9158. 52.2032% at 19.
Earth's Lost Colony: 39101134535221/1785457402560, or about 21.8998. 52.2075% at 19.
Ancient Race: 602853081437549645487629312789/27437900536237025122127985600, or about 21.9715. 52.1875% at 19.
Separatist Colony: 1211499754090253/62954258281200, or about 19.2441. 50.0751% at 15.
Damaged Alien Factory: 499901353189401114517/22787275641379005120, or about 21.9377. 52.1937% at 19.
Doomed World: 1211499754090253/62954258281200, or about 19.2441. 50.0751% at 15.
I followed David desJardins's delightful algorithm fairly closely, and I'm not aware of any bugs' remaining in the code, but who knows?  Here it is, anyway.
http://pastebin.ca/raw/1285053
-
Rob Renaud
United States
New York
New York
-
I posted a followup with my own implementation of David's algorithm, which confirms Daniel's numbers.
http://www.bgholic.com/story/racematics-all-abilities-follow...
-
|
|
Posted Wed Dec 10, 2008 11:01 pm
