Ayuda con un juego de cartas

Question

Intro

Un amigo mío está tratando de crear un tiempo real de juego de cartas donde los jugadores tratan de combinar imágenes en las cartas de su mano a la otra tarjeta que está en juego.

Ejemplo: el Jugador 1 juega una tarjeta con imágenes {a, b, c}. Otro jugador puede jugar una carta con cualquiera de a, b o c en él. Que es {a, d, e}, {b, d, e}, {c, d, e} todos coinciden exactamente en una de las imágenes de la tarjeta en el juego ({a, b, c}).

Estamos tratando de entender cómo el programa de instalación de este juego tal que:

1) Cada tarjeta con el N de imágenes está garantizado para que coincida con al menos N otras tarjetas (no huérfanos de imágenes).

Ejemplo: la tarjeta de {a, b, c} coincidiría con al menos 3 cartas. Uno para cada uno de a, b, y c de.

2) No hay dos tarjetas de coincidir en más de una forma. Ejemplo {a, b, c} y {a, b, d} no puede existir en la cubierta mientras tanto {a, b} coincidir estas dos tarjetas. En la mayoría de una imagen debe coincidir (sólo {a}, sólo {b}, o simplemente {c}).

3) En realidad nos gustaría contar con 8 imágenes por tarjeta y tienen una cubierta de al menos el 50 tarjetas. Así que en lugar de tarjetas que se ven como {a, b, c}, realmente tendríamos tarjetas con 8 imágenes y se vería algo como {a, b, c, d, e, f, g, h}.

Pregunta

1) la cantidad de imágenes que vamos a necesitar para crear para apoyar este plan?

He mirado en la construcción de la cubierta como una colección de completamente conectado gráficos que garantice que cada una de las imágenes en cada tarjeta está "conectado" a otro de la tarjeta única, pero el número de imágenes necesarias crece muy rápidamente.

Ejemplo: Para obtener un conjunto de tarjetas con 8 imágenes en ella, veo a 9 vértices (tarjetas) en un gráfico completamente conectado, que requiere no menos de 36 imágenes (sólo para 9 tarjetas!). Este es K9 en el gráfico completamente conectado enlace.

2) ¿existe algún tipo de pseudocódigo o algoritmo para ayudarnos a construir esto a través de programación? Idealmente, nos gustaría ajustar lo que nos puede afectar a la probabilidad de partidos.

Ejemplo: En el gráfico completamente conectado esquema, cada tarjeta coincide con todos los demás de la tarjeta (lo que significa que usted siempre puede jugar todo lo que esté en tu mano). Nos gustaría idealmente como un esquema donde cada tarjeta coincide con algo así como 1/3 o 1/4 de la cubierta de la tarjeta de la población, de modo que hay un cierto grado de habilidad. Sería bueno si el algoritmo/pseudocódigo nos permitió afectar a la probabilidad de tarjetas a juego.

Alguien me puede ayudar a entender este problema de matemáticas perspectiva?

Gracias de antemano!

Answer 1

Como se señala anteriormente, la respuesta sobre LO que es similar. En tanto su ejemplo y el de ellos, quieres 8 imágenes por tarjeta, como ellos lo hacen. Sin embargo, está situación es realmente diferente. Porque no requieren que todos los pares de cartas que se cruzan. Esto es en realidad muy diferente de la situación; incluso la generalización de los planos proyectivos, los diseños de bloque, siempre requieren que cada par de tarjetas de compartir algunos de imagen.

Sin embargo, tenemos una simple modificación. Creo que en lugar de una sola imagen, creo que de las variaciones en las imágenes.

Por lo tanto, vamos a volver a la simple ejemplo de las tarjetas con las tres letras, y luego, como en el ejemplo relacionado, usted tiene 7 cartas, total de 7 imágenes. Pero cada carta que coincida con todos los otros de la tarjeta. Y del mismo modo, si usted quería tarjetas con 8 imágenes, tendría $(8-1)^2+(8-1)+1=57$ tarjetas a tu disposición. Nota, el número de cartas posibles es el número de imágenes necesarias.

Ahora vamos a trabajar en su modificación. Para cada imagen, $p \in P$, considerar tres variantes $p_1, p_2, p_3$, entonces cada tarjeta se divide en $3^8=6561$ tarjetas, por lo que, en total, el número de cartas posibles es $6561*57=373977$ que es un montón de cartas. Sin embargo, este juego tiene 8 imágenes por tarjeta, y un $1/3$ de probabilidad de dos tarjetas de "intersección". Nota, el número de imágenes necesarias ya no es más el número de tarjetas, las imágenes en este caso son, simplemente,$3*57=171$.

Del mismo modo, si su probabilidad de "intersección" es $1/n$, a continuación, asumir que cada imagen $p$ $n$ variaciones.

Pero tal vez podamos encontrar un camino mejor.

En primer lugar, que sólo podría tratar de una simple fuerza bruta enfoque de decir, dado $n$-imágenes por tarjeta, y el deseo de ellos para conectarse a $n$-otras tarjetas, de tal manera que no se $m*n$-total de tarjetas(es decir, la probabilidad de coincidencia de $1/m$), pero nos damos cuenta de que para $n=3$ $m=3$ no hay solución(prueba de dibujo de la gráfica).

Lo que estamos buscando es el llamado "triángulo de los gráficos gratuitos". Su condición de que dos cartas puede no coincidir en dos maneras puede ser pensado en términos de gráficos, donde cada tarjeta es un nodo, y una arista conecta dos nodos a la hora de compartir una imagen. Algunas otras condiciones es que cada nodo tiene $\geq N$ grado(voy a suponer exactamente N). Además, si la probabilidad de coincidencia es$1/m$, entonces hay un total $N*m$ nodos(tarjetas). Por lo tanto, estamos a la izquierda para comprobar si existe un triángulo de libre gráfico en $N*m$ nodos, cada uno con grado de $N$.

Por el momento, tengo que correr, pero tal vez voy a volver y seguir pensando.

Answer 2

Resulta que hay un "lo suficientemente cerca" respuesta de stackoverflow que claramente responde a esta.

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

Voy a cavar allí. Sólo tienes que aprender MUCHO más acerca de la proyectada planos :-).