Las mejores técnicas para una IA de un juego de cartas

27

Estoy tratando de desarrollar una IA para un juego de cartas y estoy un poco atascado sobre la técnica / algoritmo que debo usar. Aquí hay algunas suposiciones sobre el juego:

  • Después de que las cartas se distribuyen a los jugadores, no hay aleatoriedad. Quiero decir que cada jugador puede elegir qué cartas juega, pero no se produce un proceso aleatorio como al distribuir las cartas al comienzo del juego.
  • Hay restricciones sobre las cartas que se pueden jugar cuando ya se jugó una carta.
  • El jugador que gana el truco juega primero. Por ejemplo, el jugador 1 juega una carta, el jugador 2 juega una carta y gana. Entonces el jugador 2 juega una carta y luego el jugador 1 juega.

Conozco muchas pistas / reglas (por ejemplo, si sé que el jugador tiene las cartas A, B, C, entonces debería jugar D), lo que me ayuda a ganar el juego. Por lo tanto, primero quería usar una red bayesiana para describir esas reglas. El problema es que no conozco ninguna probabilidad de asignar, pero podría calcular una heurística usando la historia de los juegos jugados (contra un humano). Segundo problema, es muy probable que no conozca todas las reglas y que la IA necesite algunas reglas implícitas para encontrar el juego óptimo.

¿No estoy seguro de si esta sería una buena manera de desarrollar una IA para un juego de cartas?

También me pregunto si hay otras técnicas que se ajusten mejor al problema. Por ejemplo, eché un vistazo a minimax (tal vez con un algoritmo de poda), pero ¿sería una buena opción para este problema? No estoy muy seguro ya que las jugadas más importantes están al comienzo del juego cuando hay los parámetros desconocidos más altos (la mayoría de las cartas aún no se juegan).

LaurentG
fuente
1
Gran pregunta! No tengo una respuesta completa. Solo me gustaría agregar mi 2c: si conoces todos los estados posibles en los que puede estar tu juego, entonces Minimax teóricamente sería una buena forma de atravesar ese árbol de estados de juego. Podría entrar en problemas de rendimiento si ese juego indica que el árbol es demasiado grande ...
Shivan Dragon
1
¿Cuál es el objetivo del juego? ¿Quién gana? ¿Podría ser posible para un jugador aproximar sus posibilidades de ganar el juego en un momento dado?
VENIDO del
No puedo explicar en detalle el juego. Para ganar, uno tiene que obtener el mayor número de puntos (más que el otro jugador). Al principio, es difícil / imposible decir si vamos a ganar. Al final, podemos estar seguros de ganar si uno ya tiene suficientes puntos (el otro jugador ya no puede ganar suficientes puntos para ganar).
LaurentG
1
¿Es el juego HeartStone? :)
Lescai Ionel
1
Parece que estoy en una situación muy similar a la tuya, también juego de cartas, también local (aunque no Suiza) y también estoy tratando de entender por dónde empiezo. Una cosa que me pareció interesante es un evolucionista, donde asigna ADN a jugadores virtuales y luego los enfrenta uno contra el otro. Matas a los perdedores y crías a los ganadores. El resultado podría ser bots de IA bastante decentes. No he descubierto cómo adaptar este tropiceuro.com/puerto-rico-evolver para mi juego de cartas, pero creo que esto es posible.
Andrew Savinykh

Respuestas:

11

Su ejemplo suena similar a Bridge . Los principales sistemas de juego de Bridge usan métodos de Monte Carlo para seleccionar movimientos. A un nivel alto:

  • Determine las probabilidades de que cada carta esté en una mano determinada. Usted sabe con certeza qué cartas tiene en su mano y qué cartas se han jugado. Determine la probabilidad de todas las otras cartas en función de las cartas que se han jugado y posiblemente de la oferta de un jugador si hay una oferta involucrada. Para empezar, podrías usar una probabilidad ingenua e igual de que una carta esté en la mano de algún jugador.
  • Ahora, ejecuta tantos juegos "virtuales" como puedas. Simula jugar una carta de tu mano y luego determina las respuestas de tus oponentes usando las reglas del juego y tus probabilidades. Para cada juego virtual, usa tus probabilidades para asignar cartas a un jugador y luego simula rápidamente el juego. Suponga que cada jugador jugará lo mejor que pueda. Conoces todas las cartas de tu juego virtual para que puedas hacer que cada jugador juegue perfectamente.
  • Cuando tenga una muestra sólida (o se le acabe el tiempo), elija el movimiento legal que le dio el mejor resultado con mayor frecuencia.

Una vez que algo funciona, puede agregar todo tipo de estrategias enriquecidas. Por ejemplo, varíe sus probabilidades según las jugadas históricas de un jugador, varíe las probabilidades según el estilo de un jugador (pasivo, cauteloso, agresivo) o incluso considere los efectos de jugadores específicos que juegan juntos.


Editar según el comentario de LaurentG:

En última instancia, es posible que desee desechar la idea del juego perfecto para todos los jugadores y sustituirlo por algo más realista. Conceptualmente, separe las probabilidades de que una carta esté en la mano de alguien (distribución de cartas) de la probabilidad de que un jugador juegue una carta legal determinada durante una mano (selección de cartas).

La selección de cartas está lista para aprender. Si realiza un seguimiento de las jugadas en los juegos, puede aprender cómo un jugador determinado, o los jugadores en general, tienden a jugar según las cartas en su mano y las cartas que se han jugado. Incluso podrías ponerte elegante y modelar sus suposiciones sobre las cartas que se les ocultan.

También hay oportunidades de aprendizaje para la distribución de tarjetas. Las ofertas pasadas y la selección de cartas de un jugador durante una mano pueden revelar un "aviso" sobre lo que está oculto en su mano. Podrías usar datos históricos para ajustar las probabilidades al construir cada juego virtual.

Corbin March
fuente
Gracias por tu interesante respuesta. Tienes razón, el juego comparte algunas reglas con Bridge. Según tengo entendido, tu IA no será mejor que lo que codificaste. ¿Hay alguna manera de usar un método de Monte Carlo y hacer que la IA aprenda? ¿Sería posible asignar las probabilidades para cada tarjeta usando los eventos pasados ​​(de todos los juegos anteriores)?
LaurentG
Definitivamente puedes hacer que la IA aprenda. El truco sería separar las probabilidades de que una carta esté en una mano particular de la probabilidad de que un jugador juegue una carta legal dada una vez que está en su mano. Voy a elaborar más arriba.
Corbin Marzo
6

Un caso de experiencia personal reciente:

Yo mismo he estado trabajando en un juego de cartas (Bisca, un juego portugués de 2 jugadores), y he obtenido buenos resultados con los métodos de Monte Carlo, especialmente con el reciente algoritmo de búsqueda de árbol Monte Carlo del conjunto de información (ISMCTS, descrito con ejemplo de código fuente en Python en http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Se juega razonablemente bien, con el movimiento incorrecto ocasional, solo con el conocimiento de las reglas del juego. Actualmente estoy tratando de asimilarlo, para poder mejorarlo, ya que de acuerdo con la información que he leído sobre él (y su MCTS "padre") es posible mejorar su juego con heurística ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) e inferencia de la tarjeta del oponente.

Gato negro
fuente
1
esta publicación es bastante difícil de leer (muro de texto). ¿Te importaría editarlo en una mejor forma?
mosquito
Gracias por la respuesta de alguien con experiencia real sobre el problema. excelentes enlaces!
luben
3

Creo que depende de las reglas del juego.

Esto es lo que entiendo de tu pregunta:

  • El juego se juega en rondas, con cada jugador jugando una carta por ronda.
  • El jugador que va primero puede jugar cualquier carta que quiera
  • El jugador que va segundo solo puede jugar ciertas cartas, dependiendo de lo que se jugó primero
  • El jugador que gana la ronda va primero a la siguiente ronda.
  • Todas las cartas se distribuyen antes de la primera ronda.

Suposiciones

  • Con pleno conocimiento de las cartas del otro jugador, el jugador que va primero puede decidir, para cada una de las suyas, si una carta ganará la ronda o no (el primer jugador puede jugar una carta ganadora segura)
  • Si las cartas A y B ganarán cuando se juegue primero en esta ronda, jugar A en esta ronda (y ganar) y luego jugar B en la siguiente ronda significa que B también ganará (las cartas no pierden valor)
  • Con pleno conocimiento de las cartas del otro jugador, el jugador que va en segundo lugar puede decidir si una carta puede ganar esta ronda, pero perdería si se juega primero en la siguiente ronda (elija la peor carta ganadora)

Ejemplo de juego que sigue estas reglas:

El primer jugador juega una carta. El segundo jugador tiene que jugar una carta de la misma suite o perder. Si las suites coinciden, gana la carta más alta.

Ahora, este juego se decide por suerte en el sorteo y por poder memorizar qué cartas se han jugado para conocer la mano de tus oponentes.
En esta situación, haría que la IA solo recordara parcialmente qué cartas se jugaron, es decir, eliminar aleatoriamente de la lista recordada algún porcentaje de las cartas jugadas (menor número = IA de mayor dificultad), pero no importantes como Ases o Reyes. De esta manera, por ejemplo, la IA sabrá que es seguro jugar una Reina de Corazones porque recordará que el oponente no tiene el As o el Rey, pero tendrá que calcular una probabilidad si quiere jugar el 10, porque quizás no recuerde si el Jack todavía está en juego.
Esto imita la capacidad de atención humana.

TL; DR
Limite cuánto sabe la IA para que sus decisiones no sean perfectas, solo lo suficientemente buenas.

Cezar Moise
fuente
Gracias por tu respuesta. Pero como se dijo en la pregunta, no hay suerte / no aleatoriedad después de que se distribuyen las tarjetas. Y un jugador no conoce las cartas de otros jugadores. Debe hacer suposiciones usando las cartas ya jugadas y algunas "reglas".
LaurentG
2
Como la idea de eliminar al azar las tarjetas memorizadas. Esto da una pista sobre el desarrollo de niveles como fácil, medio y difícil.
SuperM