HUB

[DESAFÍO] ¿Cómo podríamos que hacer que una computadora juegue mejor que un humano al truco? ¿Podríamos crear una IA para el truco?

Resumen: El Truco es un juego de cartas Argentino popularmente jugado en el todo el país y el cono sur. Es un juego de estrategia competitivo basado en turnos, de suma cero, estados finitos e información incompleta, lo cúal quiere decir que los jugadores basaran sus estrategias en base a especulaciones en cuanto a las cartas de los demas. En los últimos tiempos, han existido numerosos artículos científicos implementando modelos de aprendizaje reforzado en juegos de dichas características. No obstante, aún no hay ningún trabajo que haya analizado este particular juego Argentino. El próposito de este proyecto es analizar este juego desde un aspecto computacional para poder, luego, modelar un agente de aprendizaje reforzado. Para dicho fin, primero vamos a hacer una revisión de los trabajos científicos en juegos similares (como el poker), luego conceptualizar algunos términos clave para abordar dicho problema, proponemos en este trabajo un modelado del oponente en función del comportamiento y estilo cognitivo de jugadores de truco y finalmente, invitamos a la comunidad al involucramiento en el desarrollo de un agente de aprendizaje reforzado para resolver este problema. ¿Cuál creen qué es el mejor enfoque para abordar el problema? ¿Qué algoritmo usarías?

Nota: Estamos analizando el truco Argentino sin flor y de a dos jugadores.

• Si te interesa participar simplemente clona este repositorio y unite al slack haciendo clic a este link: http://iaar-slack.herokuapp.com/
• Si ya estas en slack podes ingresar con este link: http://iaar.slack.com

Patricio J. Gerpe

En tanto no se han encontrado artículos científicos en respecto al juego de cartas 'Truco' sí existe artículos cientificos que abordan juegos de cartas de información imperfecta tal como el Poker. Ejemplos incluyen:

• Heinrich, J., & Silver, D. (2016). Deep reinforcement learning from self-play in imperfect-information games. arXiv preprint arXiv:1603.01121. https://arxiv.org/pdf/1603.01121.pdf
• Mealing, R., & Shapiro, J. L. (2017). Opponent Modeling by Expectation-Maximization and Sequence Prediction in Simplified Poker. IEEE Trans. Comput. Intellig. and AI in Games, 9(1), 11-24.
• Kitchen, A., & Benedetti, M. (2018). ExpIt-OOS: Towards Learning from Planning in Imperfect Information Games. arXiv preprint arXiv:1808.10120. https://arxiv.org/pdf/1808.10120.pdf
• Yakovenko, N., Cao, L., Raffel, C., & Fan, J. (2016, February). Poker-CNN: A Pattern Learning Strategy for Making Draws and Bets in Poker Games Using Convolutional Networks. In AAAI (pp. 360-368).
• Ganzfried, S., & Yusuf, F. (2017). Computing human-understandable strategies: Deducing fundamental rules of poker strategy. Games, 8(4), 49.
• Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2017). Heads-up limit hold'em poker is solved. Communications of the ACM, 60(11), 81-88.
• Li, X., & Miikkulainen, R. (2018, July). Opponent modeling and exploitation in poker using evolved recurrent neural networks. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 189-196). ACM.
• Dahl, F. A. (2001, September). A reinforcement learning algorithm applied to simplified two-player Texas Hold’em poker. In European Conference on Machine Learning (pp. 85-96). Springer, Berlin, Heidelberg.
• Teófilo, L. F., Passos, N., Reis, L. P., & Cardoso, H. L. (2012). Adapting strategies to opponent models in incomplete information games: a reinforcement learning approach for poker. In Autonomous and Intelligent Systems (pp. 220-227). Springer, Berlin, Heidelberg.
• Erev, I., & Barron, G. (2005). On adaptation, maximization, and reinforcement learning among cognitive strategies. Psychological review, 112(4), 912. https://www.researchgate.net/profile/Ido_Erev/publication/7505648_On_Adaptation_Maximization_and_Reinforcement_Learning_Among_Cognitive_Strategies/links/00b49524696d50e515000000.pdf
• Szita, I. (2012). Reinforcement learning in games. In Reinforcement Learning (pp. 539-577). Springer, Berlin, Heidelberg.
• Kovacic, M. (2015). Opponent Modelling in Games with Imperfect Information.
• Hernandez-Leal, P., Taylor, M. E., Rosman, B., Sucar, L. E., & Munoz de Cote, E. (2016). Identifying and tracking switching, non-stationary opponents: A Bayesian approach.
• Albrecht, S. V., & Stone, P. (2018). Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258, 66-95.
• Kawamura, K., Mizukami, N., & Tsuruoka, Y. (2017, August). Neural Fictitious Self-Play in Imperfect Information Games with Many Players. In Workshop on Computer Games (pp. 61-74). Springer, Cham.
• Ponsen, M. J., Gerritsen, G., & Chaslot, G. (2010). Integrating Opponent Models with Monte-Carlo Tree Search in Poker. Interactive Decision Theory and Game Theory, 82.
• Bard, N., & Bowling, M. (2007, July). Particle filtering for dynamic agent modelling in simplified poker. In Proceedings of the National Conference on Artificial Intelligence (Vol. 22, No. 1, p. 515). Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999.
• Hernandez-Leal, P., Zhan, Y., Taylor, M. E., Sucar, L. E., & de Cote, E. M. (2017). An exploration strategy for non-stationary opponents. Autonomous Agents and Multi-Agent Systems, 31(5), 971-1002.

• Modelado del oponente: Dado que no podemos saber qué cartas tiene nuestro oponente es necesario poder modelar el estilo del juego del mismo. El modelado del oponente busca clasificar a nuestro oponente en base a su estilo estilo cognitivo (Toma deciciones de manera racional VS toma decisiones de manera intuitiva) así como su comportamiento. ¿Con qué frecuencia el oponente cambia su estilo de juego? ¿Cuál es la frecuencia en la qué miente? ¿Tiene predominancia el comportamiento agresivo (Ejem.: Aumentar apuestas) o el comportamiento defensivo (Ejem.: Rechazar apuestas en contextos de malas cartas).

• Equilibrio de Nash: Se llama equilibrio de Nash a situaciones en las que las decisiones que ambos jugadores tomaron no pudiesen haber maximizado la utilidad para ambos de otra mejor alternativa.

• Valor esperado: El valor esperado (EV) es el puntaje que podemos ganar al tomar una acción (Ejemplo: Ganar envido vs Perder envido) multiplicado por la probabilidad de ocurrencia de dicho desenlance.

• Expectativa positiva: EV+ , o expectativa positiva, es aquella acción que maxima la utilidad en función de su probabilidad de ocurrencia dados ciertas jugadas en contextos de información incompleta.

• Teorema fundamental del Poker. (Aplica para el Truco) El teorema fundamental del poker, propuesto por David Sklansky, afirma que 'Siempre que un jugador juegue de manera distinta a la que lo habría hecho si conociera las cartas del rival, su rival saca ventaja; siempre que un jugador haga el mismo movimiento que haría si conociera las cartas del rival, él saca ventaja.'

• Pozo del juego (Game's Equity): El pozo del juego es la cantidad de puntos en juego durante la partida. (Ejemplo: Si se canta truco y re truco serán 3).

• Pozo del jugador (Player's equity): El pozo del jugador es el pozo del juego multiplicado por la probabilidad del jugador de ganar sobre el pozo del juego multiplicado por la probabilidad del jugador de perder.

• Valor de la mano (Hand's value): Es un puntaje obtenido en base a la posición de las cartas en función del truco y los tantos multiplicado por la probabilidad de obtenerlos.

• Combinatoria: Es el estudio de la probabilidad de obtener diferentes manos en particular.

• Set de información (Information set): Es la información que el agente conoce en cierto estado del juego.

• Árbol de juego (Game Tree): Es el esquema en el cuál se dan los posibles cursos de acción en el juego.

• Persona: Modelado de distintos perfiles de estrategia y/o personalidad de oponentes.

• Rango de manos: Modelado deductivo del posible rango de manos que tiene nuestro oponente en función de la información disponible en el juego.

P = Probabilidad

Vamos a usar lógica difusa para clasificar nuestras cartas:

Vamos a rankear las cartas:

Carta	Ranking	P d/ derrotar a otra carta	P d/ obtener carta
	1	1.0	0.075
	2	0.97	0.075
	3	0.95	0.075
	4	0.92	0.075
	5	0.82	0.277
	6	0.72	0.277
	7	0.66	0.146
	8	0.56	0.277
	9	0.46	0.277
	10	0.36	0.277
	11	0.31	0.146
	12	0.21	0.277
	13	0.10	0.277
	14	0	0.277

Formula de p/d ganar:

casos en los que gana la carta / total de casos.

Fórmula de p d/ obtener carta en una mano: Manos con la carta : C(casos,2) = n

Tener un 7 de basto o un 7 de copa: p(A or B) =

Tener algun 4: p(A or B or C or D) =

Cantidad de manos : 9,880

Fórmula:

P = 40! / (40 - 3)! = 40! / 37! = (40 * 39 * 38) / 6 = 9,880

9,880 son la cantidad de combinaciones posibles que tenemos. Es un número muy grande así que vamos a clasificar esas manos con el uso de lógica difusa.

Sí consideramos la diferentes combinación en función de si sos mano o pie las posibilidades son:

9880 * 2 = 19,760

El primer jugador puede tener 9,880 manos distintas. El segundo jugador puede tener entonces: P = 37! / (37 - 3)! = 37! / 34! = (37 * 36 * 35) / 6 = 7,770

7,770 son la cantidad de combinaciones posibles de la mano del segundo jugador. Esto da un total de 9,880 * 7,770 = 76.767.600 manos diferentes al jugar 1v1.

Vamos a clasificar la mano por:

• (A) Su valor en el juego del envido.
• (B) Su valor en el juego del truco.

Vamos por su valor en el envido:

E = Envido m = 'Soy mano' p = 'Soy pie'

Probabilidad de ganar se calcula en base al total de casos que mi mano puede ganar el envido sobre el total de casos posibles de envido que tenga el oponente

Casos posibles = [33,32,31,30,29,28,27,26,25,24,23,22,21,20,7,6,5,4,3,2,1]

Sí tengo 32 y soy mano entonces mis probabilidades de ganar son que el rival NO tenga 33. (9,880-152)/9,880 = 0.9846 (*) *Nota: en realidad son más, dado que para tener 32 debo tener un 7, lo cual disminuye los 152 casos del rival.

Para los que sean intervalos, calculamos para cada caso y luego computamos promedio.

Ejemplo:

Em = (28, 32) Ep = (28, 32)

P(g)Em = recalcular P(g)Ep = recalcular

Vamos por su valor en el truco:

Para el truco vamos darle un puntaje a cada carta de nuestra mano en base a su ranking.

Ejemplo: Sí tengo un ancho de espada, es decir ranking 1 son 14 puntos (inversamente proporcional a la cantidad de casos)

Carta	Ranking	Puntaje	Expresión linguística
	1	14	Muy Alto
	2	13
	3	12
	4	11
	5	10	Alto
	6	9
	7	8	Medio
	8	7
	9	6
	10	5
	11	4	Bajo
	12	3
	13	2
	14	1

Entonces por ejemplo...

P = Puntaje Pr = Probabilidad

Mano	Ranking	Pr de mano	P d/ envido	P d/ truco	Pr d/ ganar envido	Pr d/ ganar truco	Valor mín de tanto	Valor mín de truco	Valor máx de tanto	Valor máx de truco	Valor de la mano
de mano	1	0.0015581	21/21	29/39	1	0.95	2	1.90	7	3.8	10.8
de mano	2	0.0015581	21/21	28/39	1	0.92	2	1.84	7	3.7	10.7
de mano	2	0.0015581	21/21	28/39	1	0.92	2	1.84	7	3.7	10.7
de mano	3	0.0015581	21/21	27/39	1	0.89	2	1.78	7	3.56	10.56
OR de mano	4	0.0008212	21/21	26/39	1	0.87	2	1.74	7	3.48	10.48
de mano	?	0.0004220	18/21	36/39	0.86	0.95	1.72	1.90	6	3.8	9.80
de mano	?	0.0004220	16/21	39/39	0.76	1	1.52	2	5.32	4	9.32

ESTAS PROBABILIDADDES NECESITAN REVISION

Cálculo de probabilidad de obtener mano: p(A and B and C) =

La probabilidad de ganar truco se basa en la probabilidad conjunta de que ganes dos manos con tus mejores cartas. El valor mínimo de tanto es lo mínimo que podes ganar (Envido) multiplicado por la probabilidad de ganar esos puntos. Mismo con el truco. El valor máximo es en el envido el (envido,envido, real envido = 7 puntos) y en el truco (quiero vale 4 = 4), en ambos casos se multiplica por la probabilidad de obtener dichos puntos.

Basado en este sistema de puntaje sería bueno averiguar si realmente esta mano es la más valiosa. Sí uno tiene en cuenta el valor (equity) de la mano, parecería que tener buen envido es más valioso que tener puntos para el truco. ¿A vos qué te parece?

Fórmula del índice de mentira:

Mi = ((bets,raises, calls when mano = 'malas' || 'muy malas') / (bets + raises + calls) ) * 100

Mi = (0,1)

Fórmula índice de agresión:

Ai = (bets + raises) / (bets + raises + calls + checks + passes) * 100 Mi = (0,1)

Fórmula velocidad de respuesta: Tiempo promedio acumulado en responder ante la última acción del oponente

Vr = ms Vr = (300,9000)

Fórmula índice de variabilidad:

Coeficiente de varianza = Cv

Vi = v3/( Cv(Ai) * Cv(Mi) * Cv(Vr) )

Vi = (0,1)

Tiene en cuenta: (A) Índice de mentira (Oportunidades que mintió sobre oportunidades que no lo hizo) , (B) Índice de agresión (Oportunidades que aumentó apuesta sobre oportunidades que no lo hizó) y (C) índice de variabilidad (Frecuencia en la cambia el patrón de estrátegia en función del resto)

Podriamos decir que tenemos 3 espectros de comportamiento:

1. Protectivo <-> Agresivo
2. Conservador <-> Ariesgado
3. Estático <-> Dinámico

Un cuarto tipo se podría definir si tenemos en cuenta las pausas de juego: 4. Crítico <-> Ágil

¿Se les ocurren otras clasificaciones?

• porcentaje de 2Bet: (2bet raises / total raises) * 100 Esta es la cantidad de veces que el jugador aumenta la apuesta ante una apuesta inicial del oponente. Ejem.: 'Truco, Quiero re truco'

• porcentaje de 3Bet: (3bet raises / total raises) * 100 Esta es la cantidad de veces que el jugador aumenta la apuesta ante una apuesta 2bet del oponente. Ejem: 'Quiero re truco, Quiero vale 4.'

• porcentaje de 4Bet: (4bet raises / total raises) * 100 Esta es la cantidad de veces que el jugador aumenta la apuesta ante una apuesta 3bet del oponente. Ejem: 'Envido, Envido, Real Envido, Falta envido'

• ratio de aperturas: ruedas.isMano ='true' + call(Envido) / ruedas Este indicador nos dice cuanto es la probabilidad que nuestro oponente cante envido en primera mano. Es un indicador que nos puede ayudar a detectar ciertas tácticas como la pesca de tantos. O la importancia que le asigna el oponente a los tantos.

• suerte: manos altas, muy altas / total manos Este indicador nos dice cuantas manos bravas tuvo nuestro oponente en base todas sus manos. Nos ayuda a identificar y estimar si la performance del oponente se debe a una buena estrategia o simplemente a su suerte.

• Ratio de Partidas ganadas / Partidas jugadas.
• Promedio de puntos por rueda: score / rounds
• Promedio de puntos por rueda con cartas altas: (score / rounds ) when manos altas, muy altas
• Promedio de puntos por rueda con cartas medias: (score / rounds ) when manos medias
• Promedio de puntos por rueda con cartas bajas: (score / rounds ) when manos bajas, muy bajas

• Partidas = Juego a 15 o 30 puntos obtenidos por uno de los jugadores.

Las partidas se subdividen en dos momentos:

1. Malas (de 0 a 15 puntos).
2. Buenas (de 15 a 30 puntos).'

• Ruedas = Juego parte de la partida que necesita al menos 2 rounds ganados por un jugador.

La rueda se subdivide en 3 rounds. Y tiene dos momentos:

1. Momento Pre-Envido (1er Round)
2. Momento Post-Envido (2do y 3er Round)

• Encontrar mejores formas de clasificar valor de las manos.
• Hacer una simulación para detectar el top de manos con más valor.
• Calcular probabilidad de ganar en función de la clasificación de la mano.
• Calcular probabilidad de las manos.¨
• Modelar estados del juego
• Clasificar jugadas (plays)
• Calcular valor esperado de jugadas y acciones segun diferentes estados.

¡No dudes en participar de este proyecto con tus ideas!

• AI for Imperfect-Information Games: Beating Top Humans in No-Limit Poker (2018). Microsoft Research. De https://www.youtube.com/watch?v=McV4a6umbAY
• Tough Poker Player: Brains Vs. AI Update. Carnegie Mellon University (2017). De https://www.youtube.com/watch?v=CRiH8yCskAE
• DeepStackAI Youtube Channel. De https://www.youtube.com/channel/UC4vSx3bbs8dbaHl2tkzU8Nw
• The State of Techniques for Solving Large Imperfect-Information Games, Including Poker. Microsoft Research (2016). De https://www.youtube.com/watch?v=QgCxCeoW5JI

• David Sklansky (1987). The Theory of Poker. Two Plus Two Publications. ISBN 1-880685-00-0.
• Zadeh, L. A. (1965). Fuzzy sets. Information and control, 8(3), 338-353

• Billings, D., Schaeffer, J., & Szafron, D. (1999). Using probabilistic knowledge and simulation to play poker. In In AAAI National Conference. http://www.aaai.org/Papers/AAAI/1999/AAAI99-099.pdf
• Barone, L., & While, L. (2000, July). Adaptive learning for poker. In Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation (pp. 566-573). Morgan Kaufmann Publishers Inc.. http://www.cs.bham.ac.uk/~wbl/biblio/gecco2000/RW179.pdf
• Johansson, U., Sonstrod, C., & Niklasson, L. (2006, December). Explaining Winning Poker--A Data Mining Approach. In Machine Learning and Applications, 2006. ICMLA'06. 5th International Conference on (pp. 129-134). IEEE. https://ieeexplore.ieee.org/abstract/document/4041481/