Explicación de Minimax "para dummies"

Question

Soy bastante nuevo en algoritmos y estaba tratando de entender el minimax, leí muchos artículos, pero todavía no puedo entender cómo implementarlo en un tic-tac-toe juego en python. ¿Puedes tratar de explicarme lo más fácil posible con un pseudocódigo o algún código python?

Solo necesito entender cómo funciona. Leí un montón de cosas sobre eso y entendí lo básico, pero todavía no puedo entender cómo puede devolver un movimiento.

Si puede, por favor, no me vincule tutoriales y ejemplos como (http://en.literateprograms.org/Tic_Tac_Toe_(Python)), sé que son buenos, pero simplemente necesito una explicación idiota.

gracias por su tiempo :)

Answer 1

idea de "minimax" es que hay un jugador en un juego de dos jugadores, un jugador está tratando de maximizar algún tipo de puntaje y otro jugador está tratando de minimizarlo. Por ejemplo, en Tic-Tac-Toe, la victoria de X podría puntuarse como +1 y la victoria de O como -1. X sería el máximo jugador, tratando de maximizar el puntaje final y O sería el jugador mínimo, tratando de minimizar el puntaje final.

X se llama jugador máximo porque cuando se trata del movimiento de X, X necesita elegir un movimiento que maximice el resultado después de ese movimiento. Cuando O jugadores, O necesita elegir un movimiento que minimice el resultado después de ese movimiento. Estas reglas se aplican recursivamente, de modo que, p. si solo hay tres posiciones de tablero abiertas para jugar, la mejor jugada de X es la que fuerza a O a elegir un movimiento de valor mínimo cuyo valor sea lo más alto posible.

En otras palabras, el valor minimax V de teoría de juegos para una posición en el tablero B se define como

V(B) = 1 if X has won in this position 
V(B) = -1 if O has won in this position 
V(B) = 0 if neither player has won and no more moves are possible (draw) 

lo contrario

V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for X, and it is X's move 
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for O, and it is O's move 

La estrategia óptima para X es siempre para pasar de B a Bi tal que V (Bi) es máximo, es decir, corresponde al valor teórico del juego V (B), y para O, de forma análoga, para elegir una posición sucesora mínima.

Sin embargo, esto no suele ser posible en juegos como el ajedrez, porque para calcular el valor teórico del juego se necesita enumerar el árbol de juego completo hasta las posiciones finales y ese árbol suele ser extremadamente grande. Por lo tanto, un enfoque estándar es acuñar una "función de evaluación" que mapee las posiciones de la junta con las puntuaciones que se correlacionan con los valores teóricos del juego. P.ej. en los programas de ajedrez, las funciones de evaluación tienden a dar una puntuación positiva para la ventaja material, columnas abiertas, etc. Un algoritmo minimax minimiza la puntuación de la función de evaluación en lugar del valor teórico real (no computable) de una posición de la mesa.

Una optimización estándar significativa para minimax es "poda alfa-beta". Da los mismos resultados que la búsqueda minimax, pero más rápido. Minimax también se puede convertir en términos de "negamax" donde el signo del puntaje se invierte en cada nivel de búsqueda. Es solo una forma alternativa de implementar minimax, pero maneja a los jugadores de manera uniforme. Otros métodos de búsqueda de árbol de juego incluyen profundización iterativa, búsqueda de número de prueba y más.

Answer 2

Minimax es una forma de explorar el espacio de posibles movimientos en un juego de dos jugadores con la alternancia de turnos. Estás tratando de ganar, y tu oponente está tratando de evitar que ganes.

Una intuición clave es que si actualmente es su turno, una secuencia de dos movimientos que le garantice una victoria no es útil, porque su oponente no cooperará con usted. Intentas hacer movimientos que maximicen tus posibilidades de ganar y tu oponente realiza movimientos que minimizan tus posibilidades de ganar.

Por esa razón, no es muy útil explorar ramas de movimientos que haces que son malos para ti, o movimientos que hace tu oponente que son buenos para ti.