## Random generation of subsets using conditional probabilities

Edit: Rewritten with motivation, and hopefully more clarity.

I'm building a site for a card game called dominion. In it, people build 'decks' of 10 distinct cards from a set of (currently) approximately 80. People (will) upload their decks to the site I'm working on, where other users will rate them for quality.

What I would like to do is create a random deck generator that generates decks that are 'similar' to use-created decks. For example, if cards A and B occur frequently in isolation, but infrequently together, the decks generated should share this same property. The state required has to be relatively limited in order for me to be able to do this online.

My tentative idea is to do the following:

1. Compute the sum of all ratings for all decks (call it S)
2. Compute the sum of all ratings for decks that contain a given card (call it S(A))
3. Compute the sum of all ratings for decks that contain any pair of cards (call it S(A∩B))
4. Compute the 'weighted' conditional probability P(A|B) = S(A∩B) / S(B)

Then, to generate a random deck, follow a procedure like the following:

1. Initialize a probability distribution P0(x) such that P0(x) = S(x) / S.
2. Select the first card, c, using the probability distribution P0
3. Compute the updated probability distribution P1(x), such that P1(x) = n P0(x) P(x|c), where n is a normalizing factor such that the integral of the distribution is 1.
4. Repeat from step 2 for the next card.

The problem is, I have no idea if this is valid, or if not, what should be modified to make it so. Based on what I've read, this seems like an application of bayes' theorem, but again I have no idea if I'm getting it wrong.

-
 You did not tell what are the desired features of the generator. What is "valid" and what is "not valid" in this game? – Sergei Ivanov Apr 6 2010 at 21:40 The desired outcome is to generate 'random' decks that resemble those generated by users. For example, if cards 'A' and 'B' both occur frequently in decks, but rarely occur together, then this generator should do the same. – Nick Johnson Apr 6 2010 at 22:35 I read your comment as follows: you want every card and every pair of cards to occur with the same probability in your generator and in users' input. No it does do this. For example, you may have 3 special cards such that each of them is in 2/3 of users' decks and each pair of them is there in 1/3 of decks. (This occurs e.g. if each user wants to have exactly 2 of these 3 cards.) Your algorithm will include all 3 in the deck with probability close to 1. Another bad sign: if there is a "must have" card for users, your generator can omit it with a small but nonzero probability. – Sergei Ivanov Apr 6 2010 at 23:14 @Sergei: I realize an algorithm such as I describe has limitations - it can only consider first-order frequencies (those involving two cards, that is). I'm looking for a way to get the best fit with the least state required. In the latter case, omitting a card that's 'must have' in rare cases is actually desired - otherwise it'd never generate a novel deck, just rehashes of existing ones. – Nick Johnson Apr 7 2010 at 7:21

You may do better with an approach that mimics the likely characteristics, and then selects cards that meet the characteristics, and then resolves conflicts. Here is a possible approach:

Consider the gross characteristics of such a deck: number and distribution of costs, number of +n Buys +n Cards +n Actions, number of duration cards, number of attack cards. Now start the build by choosing a cost distribution, say 2 2's, 3 3's, 2 4's, and 3 5's. Choose 20 cards at random with cost distribution mirroring the target distribution. Now try a subset of 10 appropriate cards. Check their stats against the others, e.g. number of +1 Buys. If all the stats match up, then check to see how many pairs of cards are disallowed. By whatever means, determine which cards out of the ten chosen do not represent a good fit to a random desired deck, and replace those cards with appropriate choices from the remainder of the 20 cards. If possible, let the stats dictate the replacement subset. Now evaluate the modified deck, and see how many of the stats are out of whack. Chances are good that you will converge to an acceptable deck within a few trials.

If you implement this and find contrarily that chances are bad on converging to a good deck, then try resolving conflicts using a subset of 30 cards instead of a subset of 20 cards. I believe that finding a good set of characteristics will give you a way of generating many good random decks, rather than just considering how often individual cards and card pairs occur or do not occur in favored decks.

Gerhard "Ask Me About System Design" Paseman, 2010.04.06

-
 A reasonable strategy, but I was hoping to avoid having to rely on knowledge about the cards in particular. There are a lot of potential variables in selecting a deck, and there's not just a single ideal distribution for things like cost - for example, some cards alter the amount of money players can acquire, thus changing the desired cost distribution. There's also not a single ideal deck composition - many possible 'characters' of deck are possible. I was hoping to emulate some of these things with a purely statistical selection method. – Nick Johnson Apr 7 2010 at 7:23 Yes, but how many decks start with cards that all cost 5? Also, I played a deck that had no +Buys, which affected the playing strategy. So even if there is no ideal distribution, you could e.g. say that half the time, people prefer 2 cards with cost 2 and 3 with cost 3, and the rest of the time they like 3 cards with cost 2 and 2 with cost 3. In any case I don't know how you will generate a deck card-by-card and get the desired result. It may be better to data-mine the user decks and find common attribute groupings to mimic. Gerhard "Ask Me About System Design" Paseman, 2010.04.07 – Gerhard Paseman Apr 7 2010 at 19:44