algoritmo Minimax

Question

Tengo una pregunta simple en el algoritmo Minimax: por ejemplo, para el juego de tic-tac-dedo del pie, como determino la función de utilidad es para cada jugador juega? No hace que automáticamente, lo hace? Debo difícil que el código de los valores en el juego, no pueden aprender de ellos por sí mismo, ¿verdad?

Answer 1

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

Answer 2

Por lo general se pondría en práctica la función de utilidad directa. En este caso, el algoritmo no sería aprender a jugar el juego, se utilizaría la información que habías explícitamente no modificable en la implementación.

Sin embargo, sería posible usar genética de programación (PG) o alguna técnica equivalente para derivar automáticamente una función de utilidad. En este caso, usted no tiene que codificar cualquier estrategia explícita. En cambio, la evolución descubriría su manera de jugar muy bien el juego.

Se puede combinar bien su código Minimax y el código de GP en un solo programa adaptativo (probablemente muy lento), o podría correr el GP en primer lugar, encontrar una función de utilidad bien y luego añadir esta función a su código de Minimax tal como lo haría con cualquier función codificada a mano.

Answer 3

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

Si no, debe proporcionar una función que determina el valor de una posición heurísticamente. En el ajedrez, por ejemplo, un factor importante es el valor del material, sino también que controla el centro o la facilidad con que las piezas se puede mover.

En cuanto al aprendizaje, se puede añadir factores de peso a diferentes aspectos de la posición y tratar de optimizar las de jugar repetidamente juegos.

Answer 4

? ¿Cómo determinar la función de utilidad para cada juego?

Con cuidado ;-) Esta href="http://aristotlethegeek.wordpress.com/2008/01/24/minimax-negamax-and-tic-tac-toe/" rel="nofollow noreferrer"> artículo muestra como una función de evaluación poco defectuoso (uno por ej. que o bien no ir "profunda" lo suficiente en mirar hacia el futuro en el árbol de posibles pliegues, o una que no logra captar el strengh relativa de algunas posiciones en el tablero) resultados en un algoritmo débil general (uno que PÉRDIDAS más a menudo).

no puede aprender de ellos por sí mismo, ¿verdad?

No, no lo hace. Hay formas, sin embargo, para que el equipo aprenda la fuerza relativa de las posiciones del tablero. Por ejemplo, examinando Donald Mitchie y su programa AMENAZA verá cómo un proceso estocástico se puede utilizar para aprender el tablero sin a priori conocimiento, sino las reglas del juego. La parte divertida es que, si bien esto puede ser implementado en los ordenadores, unos pocos cientos de cuentas de colores y cajas de cerillas son todo lo que se requiere, gracias al tamaño relativamente pequeño del espacio de juego, y también gracias a diversas simetrías.

Después de enterarse de tal manera fresca de enseñar a la computadora cómo jugar, que puede no estar tan interesado en volver a MinMax como se aplica a Tic-Tac-Toe. Después de todo MinMax es una forma relativamente sencilla de la poda de un árbol de decisión , que casi no se necesita con el espacio pequeño juego de tic-tac-dedo del pie. Pero, si hay que ;-) [volver a MinMax] ...

Podemos mirar en la "caja de cerillas" asociado con la siguiente jugada (es decir, no profundizar en absoluto), y utilizar el porcentaje de cuentas asociadas con cada cuadrado, como un factor adicional. Entonces podemos evaluar un árbol tradicional, pero sólo ir, por ejemplo 2 o 3 movimientos de profundidad (una profundidad de preanálisis poco profunda que normalmente suele terminar en pérdidas o dibuja) y calificar cada movimiento siguiente sobre la base de la sencilla -1 ( pérdida), 0 (dibujar / desconocido), 1 (valoración ganar). Para entonces, la combinación del porcentaje de granos y la calificación sencilla (por adición digamos, desde luego no por multiplicación), que son capaces de utilizar con eficacia MinMax de una manera que se asemeja más a la forma en que se utiliza en los casos en que no es posible evaluar el árbol de juego a su fin.

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