La solución óptima se convierte en una estrategia contingente cuando especifica el movimiento de MAX (el jugador de nuestro lado) en el estado inicial, luego Max se mueve a los estados resultantes para cada respuesta posible de MIN. Luego, los movimientos de MAX en los estados resultantes de cada respuesta posible de MIN a esos movimientos, y así sucesivamente.
Desde el estado actual, el método minimax en la figura anteriorcalcula la elección minimax. Implementa las ecuaciones definitorias directamente usando un cálculo recursivo simple de los valores minimax de cada estado sucesor. A medida que la recursión se desarrolla, avanza hasta las hojas del árbol, donde los valores minimax se respaldan a través del árbol. En la siguiente figura, por ejemplo, el algoritmo recurre hasta los tres Nodes inferiores izquierdos y usa la función UTILIDAD para determinar que sus valores son 3, 12 y 8, respectivamente. Luego toma el menor de estos valores, 3 en este caso, y lo devuelve como el valor respaldado del Node B. Los valores respaldados de 2 para C y 2 para D se obtienen utilizando un enfoque similar. Finalmente, sumamos el máximo de 3, 2 y 2 para obtener el valor respaldado del Node raíz de 3.
El algoritmo minimax explora el árbol del juego de arriba a abajo en profundidad primero. La complejidad temporal del método minimax es O si la profundidad máxima del árbol es my hay b movimientos legales en cada punto (bm). Para un algoritmo que crea todas las acciones a la vez, la complejidad del espacio es O(bm), mientras que para un algoritmo que genera acciones de una en una, la complejidad del espacio es O(m) El costo del tiempo es obviamente impráctico para los juegos reales, pero esta técnica sirve como base para el análisis matemático del juego y algoritmos más prácticos.
Muchos juegos populares admiten varios jugadores. Veamos cómo aplicar el concepto minimax a los juegos multijugador. Desde un punto de vista tecnológico, esto es básico, pero presenta algunos nuevos e intrigantes desafíos filosóficos. Para comenzar, debemos reemplazar el valor único de cada Node con un vector de valores. Cada Node en un juego de tres jugadores con los jugadores A, B y C, por ejemplo, está asociado con un vector <vA, vB, vC>. Este vector representa la utilidad de una condición terminal desde la perspectiva de cada actor. El vector de dos elementos se puede reducir a un solo valor en juegos de suma cero de dos jugadores porque los valores siempre son opuestos. La función UTILIDAD devuelve un vector de utilidades, que es el método más sencillo para lograr esto.
Ahora deben considerarse los estados no terminales. En el árbol del juego que se muestra en la figura a continuación, considere el Node etiquetado como X. El jugador C decide qué hacer en esa situación. Ambas opciones resultan en estados terminales con vectores de utilidad de vA = 1, vB = 2, vC = 6 y vA = 4, vB = 2, vC = 3 respectivamente. C debería hacer el primer movimiento ya que 6 es más que 3. Si se alcanza el estado X, el juego adicional dará como resultado un estado terminal con utilidades vA = 1, vB = 2 y vC = 6. Como resultado, este vector es el valor respaldado de X.
El vector de utilidad del estado sucesor con el valor más alto para el jugador que elige en n es siempre el valor respaldado de un Node n. Cualquiera que juegue juegos multijugador como Diplomacy se da cuenta rápidamente de que hay mucho más en juego que en los juegos de dos jugadores. Los juegos multijugador a veces incluyen individuos que forman alianzas formales o informales. A medida que avanza el juego, se forman y destruyen alianzas. La pregunta que nos viene a la mente es cómo se puede hacer entender este tipo de comportamiento. ¿Son las alianzas un resultado natural de la estrategia óptima de cada jugador en un juego multijugador? Pueden ser, como resulta. Considere el siguiente escenario: A y B están en situaciones débiles, mientras que C está en una posición más fuerte. Entonces, en lugar de atacarse entre sí, generalmente es preferible que tanto A como B ataquen a C. De lo contrario, C destruirá cada uno de ellos individualmente. La colaboración evoluciona de un comportamiento únicamente egoísta de esta manera. Por supuesto, la asociación pierde su significado tan pronto como C se debilita por el ataque conjunto, y A o B pueden romper el acuerdo. Las asociaciones explícitas, en ciertas circunstancias, solo concretan lo que habría ocurrido de todos modos. En otras circunstancias, romper una alianza conlleva un estigma social, por lo que los jugadores deben sopesar el beneficio inmediato de romper una alianza contra el costo a largo plazo de ser vistos como no confiables. sólo concretar lo que habría ocurrido de todos modos. En otras circunstancias, romper una alianza conlleva un estigma social, por lo que los jugadores deben sopesar el beneficio inmediato de romper una alianza contra el costo a largo plazo de ser vistos como no confiables. sólo concretar lo que habría ocurrido de todos modos. En otras circunstancias, romper una alianza conlleva un estigma social, por lo que los jugadores deben sopesar el beneficio inmediato de romper una alianza contra el costo a largo plazo de ser vistos como no confiables.
La colaboración puede ocurrir con solo dos participantes si el juego no es de suma cero. Suponga que hay un estado terminal con utilidades vA = 1000 y vB = 1000, siendo 1000 la utilidad más alta alcanzable para cada participante. El mejor enfoque es que ambos jugadores hagan todo lo posible para llegar a este punto, es decir, los jugadores cooperarán naturalmente para lograr un objetivo de beneficio mutuo.
Publicación traducida automáticamente
Artículo escrito por Mohit Gupta_OMG 🙂 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA