Minimax Algoritmo: la función de costo / evaluación?

Question

Un proyecto de la escuela me ha escrito un juego Fecha en C ++ (ejemplo en http://www.cut-the-knot.org/Curriculum/Games/Date.shtml ) donde el jugador ordenador debe implementar un algoritmo Minimax con la poda alfa-beta. Hasta el momento, entiendo cuál es la meta detrás del algoritmo en términos de maximizar las ganancias potenciales al tiempo que asume el adversario minify ellos.

Sin embargo, ninguno de los recursos que leí me ayudó a entender cómo diseñar la función de evaluación de las bases de todo es minimax decisiones sobre. Todos los ejemplos han tenido números arbitrarios asignados a los nodos hoja, sin embargo, necesito valores significativos en realidad asignar a esos nodos.

La intuición me dice que sería algo así como 1 para un nodo hoja victoria, y -1 para una pérdida, pero ¿cómo se evalúan los nodos intermedios?

Cualquier ayuda sería muy apreciada.

Answer 1

Los mayoría Evalúa básicos minimax sólo nodos hoja, marcando victorias, pérdidas y dibuja, y las partes posteriores esos valores de hasta el árbol para determinar los valores de los nodos intermedios. En el caso de que el árbol de juego es intratable, es necesario utilizar una profundidad de corte como un parámetro adicional a sus funciones minimax. Una vez que se alcanza la profundidad, es necesario ejecutar algún tipo de función de evaluación para los estados incompletos.

La mayoría de las funciones de evaluación en una búsqueda minimax son específicos de dominio, por lo que encontrar ayuda para su juego en particular puede ser difícil. Sólo recuerda que la evaluación tiene que devolver algún tipo de porcentaje expectativa de la posición de ser un triunfo para un jugador específico (típicamente máximo, aunque no cuando se utiliza una aplicación negamax). Casi cualquier juego menos investigado va a parecerse mucho a otro juego más investigado. Éste enlaza muy estrechamente con el juego palos de recogida . El uso de minimax y alfa-beta solamente, yo supongo que el juego es tratable.

Si usted es debe crear una función de evaluación de posiciones no terminales, aquí es un poco de ayuda con el análisis del juego de palos, que puede decidir si es útil para el juego fecha o no.

empezar a buscar una manera de forzar un resultado examinado en una posición terminal y todos los movimientos que pueden conducir a esa posición. En el juego de palos, una posición terminal es de 3 o menos palos restante en el último movimiento. Por lo tanto, la posición que procede de inmediato que posición terminal está dejando 4 palos a su oponente. Ahora el objetivo es dejar a su oponente con 4 palos no importa qué, y que se puede hacer ya sea de 5, 6 o 7 palos que se deja a usted, y que le gustaría forzar a su oponente a dejar en una de esas posiciones. El lugar necesita a su oponente a estar en orden para que usted pueda estar en cualquiera de 5, 6 o 7 es 8. Continuar esta lógica y seguir y un patrón que se disponga de muy rápidamente. Siempre deje que su oponente con un número divisible por 4 y se gana, todo lo demás, se pierde.

Este es un juego bastante trivial, pero el método para determinar la heurística es lo que es importante, ya que se puede aplicar directamente a su asignación. Desde el último en movimiento va primero, y sólo se puede cambiar la fecha 1 de atributos a la vez, ya sabes para ganar es necesario que haya exactamente 2 mueve a la izquierda ... y así sucesivamente.

Lo mejor de la suerte, vamos a saber lo que terminan haciendo.

Answer 2

El caso más sencillo de una función de evaluación es 1 para una victoria, -1 para una pérdida y 0 para cualquier posición de no acabado. Dada su árbol es lo suficientemente profunda, incluso esta simple función le dará un buen jugador. Por ningún juego no triviales, con alto factor de ramificación, por lo general se necesita una función mejor, con algunas heurísticas (por ejemplo, para el ajedrez podría asignar pesos a las piezas y encontrar un resumen, etc.). En el caso del juego de la fecha, yo sólo tiene que utilizar la función de evaluación más simple, con 0 para todos los nodos intermedios.

Como nota al margen, Minimax no es el mejor algoritmo para este juego en particular; pero supongo que ya lo sabes.

Answer 3

Por lo que entiendo del juego Fecha se ha vinculado a, parece que los únicos resultados posibles para un jugador se gana o pierde, no hay en el medio (por favor, corríjanme si me equivoco).

En este caso, es sólo una cuestión de la asignación de un valor de 1 a una posición ganadora (actual jugador obtiene al 31 de diciembre) y un valor de -1 a las posiciones perdedoras (otro jugador se pone al 31 de diciembre).

Su algoritmo Minimax (sin poda alfa-beta) sería algo como esto:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome