(Editar: 8/8/2013) - He escrito algunos ejemplos de código: Ultimate Tic-Tac-Toe, donde tengo una implementación genérica de búsqueda de juegos mínima/máxima. El código está escrito en una variante tonta de C++, llamada prepp.
Su mejor recurso sería un curso de nivel universitario sobre Inteligencia Artificial. El libro de texto clásico es "Artificial Intelligence: A Modern Approach" by Russel & Norvig
Trataré de darle un desglose de los conceptos clave.
estado del juego - se trata de un conjunto de variables que se pueden utilizar para determinar:
- El estimado "Valor" de la situación actual
- Es el juego más?
Valor - el "valor" de un estado en particular es una función de ese estado evaluadas por el jugador actual, vamos a llamarlo f (x). Otro nombre para esta función es la función "heurística".Determina el mejor valor posible que el jugador actual podría alcanzar, dado el estado del tablero, x. El modelo x depende de usted, pero x debe abarcar todo lo que se usa en el flujo natural del juego. Por lo tanto, en su caso, x puede ser una matriz de valores 8x8 mapeada en pedazos en el tablero. Y, f sería una función que da el "valor" de esa configuración de la tarjeta para el jugador rojo (o algo así).
Una posible simplificación de considerar en un juego basado en turnos de 2 jugadores es para codificar el "jugador actual" como parte del estado. Esto agrega estado a la entrada a la función heurística. Entonces, en lugar de f (x), tenemos f (x, player). Sin embargo, eso se puede simplificar rolando el jugador en x. De cualquier manera, f siempre devolverá el "Valor" para el mismo jugador, pero según quién sea el próximo turno.
Para aclarar por ejemplo (simplificado), f en el ajedrez casi siempre debe devolver una puntuación muy alta si las blancas pueden matar a la reina del negro. Pero si el negro tendrá la posibilidad de matar a la reina blanca en el próximo movimiento, entonces f debería devolver un número muy bajo.
Tenga en cuenta que hasta ahora no se menciona la parte de búsqueda de árboles de minmax. f siempre se define según el estado actual . Entonces, cuando dije "el negro tendrá la posibilidad ...", lo que quiero decir es que su función heurística puede determinar, por ejemplo, que dado x, hay una línea de visión (diagonal, horizontal o vertical) entre un alfil negro o torre, a la reina blanca. La heurística para el ajedrez debe ser lo suficientemente sofisticada como para saber que solo esto crea una amenaza y, por lo tanto, debe puntuarse en consecuencia al calcular el valor total de f.
Antes de llegar a minmax, tenga en cuenta que A * es una optimización para buscar en el espacio de posibles valores x. Sin embargo, no debe preocuparse por la optimización hasta que comprenda completamente y haya implementado minmax.
Por lo tanto, el algoritmo minmax es una forma de organizar el proceso de toma de decisiones de su IA. Las cosas que usted necesita para ser capaz de hacer con el fin de poner en práctica MinMax:
- Generar válidos estados de juego de un partido-estado existente x.
- Detenga el bucle o la repetición después de que se haya alcanzado una profundidad determinada.
- Recuerde el "valor" para cada recursión de nivel devolviéndola a la persona que llama.
El flujo básico comienza entendiendo, ¿a qué turno? Como mencioné anteriormente, f siempre devolverá valores altos para indicar éxito para el jugador 1, y valores bajos para indicar éxito para el jugador 2. En cada nivel más profundo de recursión, jugador le permitirá saber si elegir el mínimo o el máximo de los valores potenciales descubiertos a través de su recursión.
Déjenme decir que de otra manera. Hay dos razones para evaluar realmente f (x).
- ¿Quiere saber si el juego ha terminado en el estado x.
- Has alcanzado el nivel más profundo de recursión y quieres evaluar cuál será el puntaje si el juego avanza hasta este punto.
Por lo tanto, el código podría hacer algo como esto:
función MinMax (x, reproductor) vuelve valor
- Mi estado actual es x, y el siguiente jugador para moverse es conocido. Lo sé porque
- función choose-move me lo dijo. (ver a continuación)
- Me llamaron recursivamente por mi cuenta. (ver abajo)
- ¿Se acabó el juego? Preguntar f (x). Si devuelve infinito positivo, entonces el blanco ha ganado. Si devuelve infinito negativo, entonces el negro ha ganado. Si su juego tiene una opción de punto muerto, o tiene un puntaje final (quizás como parte de un juego más grande), entonces simplemente tendrá que inventar una manera de representar el puntaje ganador como un valor de retorno de f. O bien, si desea separarlo, simplemente realice una nueva función g (x) que hace esto. Si el juego termina, devuelve ese valor a tu interlocutor. Si el juego no ha terminado, continúa.
- De x Voy a enumerar todas las posibles x '. En un juego de 8x8, puede haber algunos, hasta decenas o cientos de posibles movimientos válidos desde cualquier estado de juego individual. Esto depende de las reglas de tu juego.
- Si se ha alcanzado el nivel más profundo de la recursión deseada,
- Para cada x ', llame f (x', reproductor). Para cada llamada, asociamos su valor de retorno con los particulares x ' que habíamos pasado en.
- Else
- para cada x', de forma recursiva llamar MinMax (x', otros jugadores). (Tenga en cuenta que otros jugadores es lo contrario de jugador en este punto.) Para cada llamada, asociamos su valor de retorno con los particulares x' que habíamos pasado en.
En este punto, todos los movimientos siguientes posibles deben tener un "valor" asociado a ellos.
- Si jugador es el jugador 1, elegir el valor máximo de todos los valores asociados con todas x', y devolver ese valor. Eso es lo mejor que el jugador 1 podrá hacer en este estado del juego.
- Si jugador es el jugador 2, elegir el valor mínimo de todos los valores asociados con todas x', y devolver ese valor. Eso es lo mejor que el jugador 2 podrá hacer en este estado del juego.
función final MinMax
función elegir-move (x, reproductor) retorno * * next_state
- Mi estado actual es x, y estamos tratando de averiguar qué jugador's siguiente movimiento debe ser.
- Comprueba si el juego ha terminado, como se describe arriba.
- De x Voy a enumerar todas las posibles x '. (Usted debe ser capaz de volver a usar cualquier código que tenía que hacer esto en MinMax.
- Para cada x ', llame MinMax (x', reproductor). Para cada llamada, asociamos su valor de retorno con los particulares x ' que habíamos pasado en.
- Si jugador es el jugador 1, elegir el valor máximo de todos los valores asociados con todas x' y r crear ese valor Eso es lo mejor que el jugador 1 podrá hacer en este estado del juego.
- Si jugador es el jugador 2, elegir el valor mínimo de todos los valores asociados con todas x', y devolver ese valor. Eso es lo mejor que el jugador 2 podrá hacer en este estado del juego.
función final elegir-movimiento
Su código conductor sólo tendrá que llamar elegir- movimiento, y debe devolver el próximo juego de mesa. Obviamente, también puede codificar el valor de retorno como un "movimiento" en lugar de un estado, para una representación diferente.
Espero que esto ayude. Perdón por la explicación larga, solo tomé un café.
¿Tiene una pregunta? – jakev
Lo siento, enviado sin mi consentimiento :) – Cyril
GameDev.StackExchange es mucho mejor para esta pregunta: http://gamedev.stackexchange.com/ –