Help With a Card Game

Question

Intro

A friend of mine is trying to create a real time card game where players try to match images on cards in their hand to another card that is in play.

Example: Player 1 plays a card with images {a, b, c}. Another player could play a card with any of a, b, or c on it. That is {a, d, e}, {b, d, e}, {c, d, e} all match at exactly one of the images on the card in play ({a, b, c}).

We're trying to understand how to setup this game such that:

1) Each card with N images is guaranteed to match at least N other cards (no orphaned images).

Example: the card {a, b, c} would match at least 3 other cards. One for each of a, b, and c.

2) No two cards match in more than one way. Example {a, b, c} and {a, b, d} cannot exist in the deck as both {a, b} match these two cards. At most one image should match (just {a}, just {b}, or just {c}).

3) In reality we'd like to have 8 images per card and have a deck of at least 50 cards. So instead of cards that look like {a, b, c}, we'd really have cards with 8 images and they'd look something like {a, b, c, d, e, f, g, h}.

Question

1) How many images will we need to create to support this scheme?

I've looked into building the deck as a collection of fully connected graphs which would ensure that each images on every card is "connected" to another unique card, but the number images needed grows quite quickly.

Example: To get a set of cards with 8 images on it, I see 9 vertices (cards) in a fully connected graph which requires no less than 36 images (just for 9 cards!). This is K9 in the fully connected graph link.

2) Is there some type of pseudocode or algorithm to help us build this out programatically? Ideally we'd like to adjust it so that we can affect the probability of matches.

Example: In the fully connected graph scheme, each card matches every other card (which means you can always just play whatever is in your hand). We'd ideally like a scheme where every card matches something like 1/3 or 1/4 of the deck's card population so that there's some degree of skill involved. It would be nice if the algorithm/pseudocode allowed us to affect the probability of cards matching.

Can someone help me understand this problem from at math perspective?

Thanks in advance!

Answer 1

As you point out above, the answer on SO is similar. In both your example and theirs, you want 8 images per card, as they do. However, you're situation is actually different. Because you don't require that every pair of cards intersect. This is actually a quite different situation; even the generalization of projective planes, block designs, always require that every pair of cards share some image.

However, we have a simple modification. Think instead of single images, think of variations on images.

So, let's come back to the simple example of cards with three letters, then, as in the example linked, you have 7 cards, total of 7 images. But every card would match every other card. And similarly, if you wanted cards with 8 images, you would have $(8-1)^2+(8-1)+1=57$ cards at your disposal. Note, the number of possible cards is the number of necessary images.

Now let's work in your modification. For each picture, $p \in P$, consider three variants $p_1, p_2, p_3$, then every card splits into $3^8=6561$ cards, and thus in total the number of possible cards is $6561*57=373977$ which is a lot of cards. However, this game would have 8 pictures per card, and a $1/3$ probability of two cards "intersecting". Note, the number of necessary pictures is no longer the number of cards, the images in this case are simply $3*57=171$.

Similarly, if your probability of "intersection" is $1/n$, then assume each picture $p$ has $n$ variations.

But maybe we can find a better way.

First, we could just try a simple brute force approach of saying, given $n$-pictures per card, and wanting them to connect to $n$-other cards, such that there are $m*n$-total cards(i.e. match probability of $1/m$), but we notice that for $n=3$ and $m=3$ there is no solution(try drawing the graph).

What you're looking for is called "triangle free graphs". Your condition that two cards can't match up in two ways can be thought of in terms of graphs where each card is a node, and an edge connects two nodes when they share a picture. Some other conditions is that every node has $\geq N$ degree(I'm going to assume exactly N). Further, if the match probability is $1/m$ then there are in total $N*m$ nodes(cards). So we're left to check if there exists a triangle free graph on $N*m$ nodes each with degree $N$.

At the moment, I have to run, but perhaps I'll return and keep thinking.

Answer 2

Turns out there's a "close enough" answer on stackoverflow that neatly answers this.

https://stackoverflow.com/questions/6240113/what-are-the-mathematical-computational-principles-behind-this-game

I'll dig in there. Just need to learn a LOT more about projected planes :-).