Hola, soy uno de los autores de varios de los artículos de CFR, incluido el artículo original de 2007 y el reciente artículo de Science donde usamos CFR + para resolver el hold’em limit hold’em.
CFR es un algoritmo de auto-juego: aprende a jugar un juego jugando repetidamente contra sí mismo. El programa comienza con una estrategia que es uniformemente aleatoria, donde jugará cada acción en cada punto de decisión con la misma probabilidad. Luego simula jugar juegos contra sí mismo. Después de cada juego, revisa sus decisiones y encuentra formas de mejorar su estrategia. Repite este proceso para miles de millones de juegos, mejorando su estrategia cada vez. A medida que juega, se acerca cada vez más hacia una estrategia óptima para el juego: una estrategia que no puede ser peor que empatar contra cualquier oponente.
La forma en que mejora con el tiempo es sumando la cantidad total de arrepentimiento que tiene por cada acción en cada punto de decisión, donde el arrepentimiento significa: ¿cuánto mejor hubiera hecho en todos los juegos hasta ahora si siempre hubiera jugado esta acción? en esta decisión, en lugar de elegir cualquier combinación de acciones que mi estrategia dijo que debería usar? El arrepentimiento positivo significa que lo habríamos hecho mejor si hubiéramos tomado esa acción con más frecuencia. El arrepentimiento negativo significa que lo habríamos hecho mejor al no tomar esa acción en absoluto. Después de cada juego que el programa juega contra sí mismo, calcula y agrega los nuevos valores de arrepentimiento para todas sus decisiones que acaba de tomar. Luego recalcula su estrategia para que tome acciones con probabilidades proporcionales a su arrepentimiento positivo. Si una acción hubiera sido buena en el pasado, la elegirá con más frecuencia en el futuro.
- En los términos más simples, ¿qué es un algoritmo? ¿Cual es su propósito?
- Es un método de retroceso para imprimir permutaciones de cadena. No entiendo de qué manera se produce el flujo de control, como después de encontrar el intercambio, el intercambio se llama luego permutar y luego nuevamente. ¿Esto no se me viene a la cabeza?
- ¿Qué es un algoritmo explicado para que las personas normales puedan entender y también cómo se hacen?
- ¿Qué es el diseño paramétrico y cuáles son algunos ejemplos de él?
- ¿Cómo puedo encontrar la ruta más larga de un gráfico bidireccional utilizando el algoritmo BFS?
Repite este proceso para miles de millones de juegos. Entonces tienes esta larga secuencia de estrategias que estaba usando en cada juego. Contra-intuitivamente, esa secuencia de estrategias no necesariamente converge a algo útil (aunque a veces lo hace en la práctica, ahora, con el nuevo algoritmo CFR + que describimos en el artículo de Science). Sin embargo, en un juego de suma cero de dos jugadores, si calcula la estrategia promedio sobre esos miles de millones de estrategias en la secuencia, entonces esa estrategia promedio convergerá hacia un equilibrio de Nash para el juego. Una vez que ha terminado de aprender a jugar jugando contra sí mismo, no tiene que cambiar más: solo usa esa estrategia promedio contra cualquier oponente humano o informático que enfrenta.
Un equilibrio de Nash es un conjunto de estrategias, una para cada jugador en el juego. Si el juego es de dos jugadores y suma cero, y si los jugadores alternan posiciones para igualar la ventaja de jugar en cada posición (como en los juegos de póker), entonces el equilibrio de Nash tiene una propiedad teórica útil: no puede empeorar que empate, en expectativa, contra cualquier otra estrategia de oponente. En un juego como el póker, eso “a la expectativa” es importante: debido a la suerte en el juego de las cartas que se reparten al azar, no hay garantía de que un equilibrio de Nash (¡o cualquier estrategia!) Gane cada mano. Sin embargo, si promedia sobre un gran conjunto de manos, o calcula exactamente las expectativas, entonces no puede ser peor que empatar contra alguien.
Si el oponente también juega una estrategia de equilibrio de Nash, entonces empatará; Si el oponente considera cuidadosamente la estrategia de equilibrio de Nash y calcula una contraestrategia perfecta, entonces también empatará. Sin embargo, si el oponente comete errores, puede perder valor, permitiendo que gane la estrategia de equilibrio de Nash. En otras palabras, un equilibrio de Nash solo juega una defensa perfecta: no trata de aprender o explotar los defectos del oponente, sino que solo gana cuando el oponente comete errores. Esto es a propósito, ya que intentar encontrar y explotar los errores de un oponente generalmente hace posible que un oponente aún más inteligente explote su nueva estrategia. Hay una compensación entre jugar defensa y ofensiva.
Dado que un equilibrio de Nash es una estrategia inmejorable para este tipo de juego, se considera una estrategia óptima, y ”resolver” un juego es equivalente a calcular un equilibrio de Nash. En este sentido, “resolver” es un término técnico, que significa exactamente en el mismo sentido que uno podría “resolver para X” en una ecuación matemática.
Como mencioné anteriormente, con CFR, la estrategia promedio que está computando converge hacia un equilibrio de Nash. La “explotabilidad” de una estrategia es la cantidad máxima que una contraestrategia perfecta podría ganar a la espera de una estrategia. Un equilibrio de Nash tiene una explotabilidad de cero, ya que nadie puede vencerlo con expectativa, y tener una explotabilidad más baja es bueno. Cuando ejecuta CFR, la explotabilidad de la estrategia promedio converge hacia cero, lo que hace que su pérdida en el peor de los casos disminuya cada vez más. Tenga en cuenta que esta es una forma pesimista de medir cuán buena es su estrategia: nuestros mejores programas de póker comenzaron a vencer a los mejores jugadores humanos del mundo en el heads-up limit hold’em en 2008, a pesar de que nuestros programas en ese momento todavía eran masivamente explotables por esto. peor de los casos
En nuestro artículo de Ciencia de enero de 2015, anunciamos que produjimos una estrategia que esencialmente resolvió el juego de manera débil . Eso significa que hemos calculado una estrategia con una explotabilidad tan baja (0.000986 ciegas grandes por juego) que tomaría más de una vida humana de juego, usando la contra-estrategia perfecta, para que cualquiera tenga un 95% de confianza estadística de que estaban en realidad ganando contra eso. Por lo tanto, no es una estrategia exactamente perfecta, pero está tan cerca de ser perfecto que el juego está esencialmente resuelto, ya que ahora está fuera de la capacidad de cualquier humano para vencerlo por una cantidad estadísticamente significativa jugando juegos contra él.
