Algoritmo Minimax

Question

Tengo una pregunta simple sobre el algoritmo Minimax: por ejemplo, para el juego de tres en raya, ¿cómo determino la función de utilidad para cada jugador? No hace eso automáticamente, ¿verdad? Debo codificar los valores en el juego, no puede aprenderlos por sí mismo, ¿o sí?

Answer 1

No, un MiniMax no aprende. Es una versión más inteligente de una búsqueda de árbol de fuerza bruta.

Answer 2

Tic-Tac-Toe es lo suficientemente pequeño para ejecutar el juego hasta el final y asignar 1 para ganar, 0 para sorteo y -1 para perder.

De lo contrario, debe proporcionar una función que determine el valor de una posición de forma heurística. En el ajedrez, por ejemplo, un factor importante es el valor del material, pero también quién controla el centro o qué tan fácil se pueden mover las piezas.

En cuanto al aprendizaje, puede agregar factores de peso a diferentes aspectos de la posición e intentar optimizarlos mediante juegos repetidos.

Answer 3

¿Cómo se determina la función de utilidad para cada jugada?

Cuidadosamente ;-) Este article muestra cómo una función de evaluación ligeramente defectuosa (una por ejemplo, que no es lo suficientemente "profunda" al mirar hacia adelante en el árbol de posibles capas, o una que no captura el fuerza relativa de algunas posiciones del tablero) da como resultado un algoritmo débil general (uno que pierde más a menudo).

no puede aprenderlos por sí mismo, ¿o sí?

No, no es así. Sin embargo, hay formas de que la computadora aprenda la fuerza relativa de las posiciones de la placa. Por ejemplo, al buscar en Donald Mitchie and his MENACE program, verá cómo se puede utilizar un proceso estocástico para aprender la placa sin ningún conocimiento a priori pero las reglas del juego. Lo gracioso es que, si bien esto se puede implementar en computadoras, basta con unos cientos de cuentas de colores y cajas de fósforos, gracias al tamaño relativamente pequeño del espacio del juego, y también gracias a varias simetrías.

Después de aprender una manera tan genial de enseñarle a la computadora cómo jugar, es posible que no estemos tan interesados ​​en volver a MinMax como se aplica a Tic-Tac-Toe. Después de todo, MinMax es una forma relativamente simple de podar un árbol de decisión, que apenas se necesita con el espacio para juegos pequeños de tres en raya. Pero, si debemos ;-) [volver a MinMax] ...

Podemos examinar la "caja de cerillas" asociada con la siguiente jugada (es decir, no profundizar en absoluto), y usar el porcentaje de cuentas asociadas con cada cuadrado, como un factor adicional. Entonces podemos evaluar un árbol tradicional, pero solo yendo, digamos 2 o 3 movimientos de profundidad (una profundidad de observación superficial que normalmente terminaría en pérdidas o sorteos) y calificamos cada movimiento siguiente sobre la base del simple -1 (pérdida), 0 (dibujar/desconocido), +1 (ganar) calificación. Para entonces, combinando el porcentaje de cuentas y la clasificación simple (por ejemplo, sin multiplicación), podemos usar MinMax de manera más parecida a la que se usa en los casos en que no es posible evaluar el árbol del juego hasta su final.

En pocas palabras: en el caso de Tic-Tac-Toe, MinMax solo se vuelve más interesante (por ejemplo, para ayudarnos a explorar la efectividad de una función de utilidad particular) cuando eliminamos la naturaleza determinista del juego, asociado con fácil evaluación del árbol completo. Otra forma de hacer el juego [matemáticamente] interesante es jugar con un oponente que comete errores ...

Answer 4

Normalmente implementaría la función de utilidad directamente. En este caso, el algoritmo no aprendería a jugar el juego, usaría la información que usted había codificado explícitamente en la implementación.

Sin embargo, sería posible usar genetic programming (GP) o alguna técnica equivalente para derivar automáticamente una función de utilidad. En este caso, no tendría que codificar ninguna estrategia explícita. En cambio, la evolución descubriría su propia forma de jugar bien el juego.

Puede combinar su código minimax y el código GP en un solo programa de adaptación (probablemente muy lento), o puede ejecutar primero la GP, encontrar una buena función de utilidad y luego agregar esta función a su código minimax igual que tendrías cualquier función codificada a mano.