Algoritmo genético para un juego de cartas (Dominion)

Question

Tengo un programa F # activo que ejecuta Dominion, un juego de cartas. Me gustaría utilizar un algoritmo genético para determinar las estrategias óptimas para jugar. Sin embargo, no sé mucho sobre IA o algoritmos genéticos. ¿Me puede indicar alguna buena literatura para comenzar?

Una estrategia para jugar consiste en una reacción a una mano determinada. En cada turno, un bot recibe una mano de cartas. Puede elegir jugar cartas de acción o comprar nuevas cartas, según lo que se le haya repartido. El objetivo es terminar el juego con tantas cartas de puntos de victoria como sea posible.

Un enfoque codificado podría ser algo como:

def play(hand, totalDeck): 
    if hand contains Smithy then use Smithy 
    if hand contains enough coins for Province then buy Province 
    if more than 30% of the totalDeck is Smithy, then buy coins 

Estaba pensando en que describe una estrategia en términos de un vector de porciones deseadas del total de la cubierta para cada tarjeta:

[Smithy, Province, Copper, ...] 
[.3, .2, .1, ...] 

Entonces para mutar un bot, podría cambiar ese vector y ver si la versión mutada mejora. La función de acondicionamiento físico sería la puntuación promedio jugando Dominio contra una variedad de otros bots. (El puntaje de un bot depende de contra quién esté jugando, pero con suerte al jugar muchos juegos contra muchos bots esto puede igualar).

¿Tiene sentido esto? ¿Me dirijo por el camino correcto?

Answer 1

¿De dónde sacas los otros bots? ¿Los mantienes estáticos? Si es así, el robot entrenado no se convertirá en "bueno" en el juego per se, solo bueno en la explotación del bot ficticio. De lo contrario, los otros bots evolucionan también, y el porcentaje de victorias no será un buen indicador de calidad a menos que se apliquen otras restricciones. ¡Siempre se da cuenta de que con una población llena de bots con habilidades perfectas, su desempeño contra el otro parecerá mediocre!

usted podría tomar un enfoque de co-evolutiva:

• mutar todos los robots en unos suficientemente grandes poblaciones.
• Que compiten entre sí en varias ocasiones en un torneo round robin, por ejemplo 100 veces
• eliminar algunos de los robots de peor rendimiento,
• mantener algunas de las mejores robots de sin cambios (elitismo)
• Refill el resto de la población con mutaciones y cruces de buenos bots.

O usted podría entrenar contra un punto de referencia fijo:

• Hacer un robot con una política hecha a mano que aparece bueno, con su conocimiento del juego
• Alternativamente, tienen jugadores humanos (a sí mismo?) proporcionar los movimientos. Esta podría ser una buena fuente de experiencia en capacitación para tu bot, pero a menos que tengas acceso a una gran base de datos de movimientos humanos (expertos), es muy lenta.
• tren en contra de su índice de referencia
• Seleccionar los mejores, mutar, etc

Answer 2

creo que el vector no conducen realmente a buenos resultados a menos que el juego es muy lineal.Sugeriría el siguiente enfoque basado en reglas:

En cada turno tienes un juego de cartas y quieres determinar la carta que juegas o, en caso de que no juegues una carta, deseas dibujar un nuevo uno. Lo que necesitas es algún tipo de función prioritaria que te indique qué carta es la mejor para jugar. Tal función de prioridad se puede describir mediante programación genética. Siempre jugaría la carta con la prioridad más alta a menos que ninguna carta tenga una prioridad superior a un nivel establecido (por ejemplo, 0) en cuyo caso se dibujará una nueva. La programación genética se puede usar para desarrollar esa función de prioridad.

Dado que está utilizando F #, podría ser una buena idea intentar este enfoque con HeuristicLab que está escrito en C#. Puede implementar su programa como un problema y permitir que la función de evaluación realice una simulación de ese juego. Escribe una gramática y un intérprete para tu regla. Defina una serie de parámetros que le permitirán a su regla de prioridad tomar decisiones significativas, p. cierta información general del juego, como el número de cartas jugadas, provincias, etc. y alguna información relacionada con las cartas, como el impacto de jugar esa carta (en términos de puntos de victoria), etc. Estas son las variables de entrada para su intérprete que calcule un valor de prioridad. La tarjeta con el mejor valor de prioridad es la que usted elija. Luego, para evaluar su estrategia, defina, por ejemplo, 10 soluciones aleatorias cuando creas tal problema y en la evaluación, permite que cada solución compita contra esos bots aleatorios. Mida la cantidad a la que le gana a cada uno de los bots aleatorios, cuanto más alto gane y cuantos más bots venza, mejor será la condición física, cuanto más ganen, peor será el puntaje. También puede agregar un analizador a su problema, que actualizará las soluciones aleatorias del problema con las de mejor rendimiento para que también evolucione con el tiempo.

También puede usar la idea de la porción de destino si lo desea. En ese caso, su codificación sería un RealVector. También puede optimizar eso con HeuristicLab (use Evolution Strategy, Particle Swarm Optimization o Genetic Algorithm).

Answer 3

Dominion es un gran juego, pero será difícil de optimizar usando un algoritmo genético, ya que las entradas de un juego determinado difieren entre juegos (juegos de cartas), la estrategia óptima cambia en el transcurso del juego, y el juego óptimo para cualquier situación dada va a aparecer lentamente en una búsqueda genética (intuitivamente, basado en mi bastante buena comprensión tanto de los GA como del juego).

Una mejor aproximación a Dominion, creo, sería un enfoque heurístico directo (basado en reglas) o, muy interesante, la búsqueda de Monte Carlo (ver, por ejemplo, http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext). Monto Carlo Search es atractivo precisamente porque:

• Es fácil generar una secuencia aleatoria pero legal de movimientos en Dominion.
• Es al menos recta hacia adelante para juzgar el "valor" de tal secuencia (aumento de VP) edificio
• A-priori de reglas "mejor juego" es duro (que es lo que hace que el juego tan bueno)

Es un desafío muy bueno, debe bloguear sus experiencias.