Ingenious Game

Ingenious Game

1. Introducción

Debido a la gran demanda de tecnología, la IA es una ciencia aplicada que consiste en incluir inteligencia a máquinas creadas por el hombre, estas tecnologías de IA también son aplicadas en juegos para darle una mejor interacción humano-computador. El algoritmo de minimax en simples palabras consiste en la elección del mejor movimiento para el computador, suponiendo que el contrincante escogerá uno que lo pueda perjudicar, para escoger la mejor opción este algoritmo realiza un árbol de búsqueda con todos los posibles movimientos, luego recorre todo el árbol de soluciones del juego a partir de un estado dado. Por tanto, minimax se ejecutará cada vez que le toque mover a la IA. En este informe se abarcara la teoria del algoritmo minimax aplicada en este juego, descripcion del juego, descripcion de la implementacion de la aplicación Ingenious Game, resultados y conclusiones.

1. Descripcion del Juego

Contenido        

- 1 tablero (con seis casillas impresas, una con cada símbolo de un color)

- 120 piezas de juego (cada una con dos símbolos de colores)

- 1 bolsa (para guardar las piezas de juego)                

- 4 barras (para poner 6 piezas en cada una)

- 4 tableros marcadores

- 24 fichas de puntuación (4 de cada uno de los 6 colores de los símbolos)

El Tablero

•        Con 1 o 2 personas: solo se usa la parte blanca del tablero.

•        Con 3 personas: se usa la parte blanca y la gris claro.

•        Con 4 personas: se usa el tablero completo (parte blanca, gris claro y gris oscuro).

Preparación

Antes de empezar, cada persona debe disponer de un tablero marcador de puntuación. Todas las piezas deben guardarse y mezclarse desordenadas en la bolsa. Cada persona coloca delante suya una barra y roba al azar 6 piezas de la bolsa, colocándolas verticalmente en la barra para poder ver los símbolos de cada una (pero que el resto de personas no los puedan ver). Cada persona coloca 6 fichas de puntuación, una de cada color, en la posición 0 de su tablero marcador, cada una sobre el símbolo de color adecuado.

Cada persona debe colocar delante suya su barra con las piezas y su tablero marcador, las dos cosas al lado una de otra, de forma que el resto de personas puedan ver claramente sus puntuaciones en todo momento. ¡Y cuidado con derribar las piezas encima del marcador y mover las ficha de puntuación!.

Objetivo del juego

La partida se juega colocando piezas con unos símbolos en el tablero, junto a otras piezas con otros símbolos. Si los símbolos de la pieza colocada coinciden con los de las piezas adyacentes, se obtienen puntos. Cuantos más símbolos coincidentes haya en línea, más puntos se obtienen. Cada punto conseguido se refleja en el marcador de cada persona. La puntuación total de una persona es igual al número de puntos en el color en el que menos puntos tenga. Gana la persona cuyo mínimo de puntos entre los 6 colores sea el mayor entre todas las personas al final de la partida. Por lo tanto se debe de ir aumentando los puntos de todos los colores sin dejar ninguno atrás.

1. Algoritmo Minimax

En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Este cálculo se hace de forma recursiva.

El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

En el algoritmo Minimax el espacio de búsqueda queda definido por:

Estado inicial: Es una configuración inicial del juego, es decir, un estado en el que se encuentre el juego. Para ingenious game, un ejemplo seria asi:

[pic 2]

Operadores: Corresponden a las jugadas legales que se pueden hacer en el juego, en este caso por ejemplo no se puede colcar un ficha en un hexagono ya marcado, ademas al iniciar el juego una ficha debe colcarse en los hexagonos adyacentes a las esquinas:

[pic 3]

[pic 4][pic 5][pic 6]

[pic 7][pic 8][pic 9]

Condición Terminal: Determina cuando el juego se acabó, en nuestro ejemplo el juego termina cuando se marcan todas los hexagonos y se evalua que jugador tiene mayor puntaje o si hay un empate.

[pic 10]

                                [pic 11][pic 12]                                                                 [pic 13][pic 14]

Función de Utilidad: Da un valor numérico a una configuración final de un juego. En un juego en donde se puede ganar, perder o empatar, los valores pueden ser 1, 0, o -1.

[pic 15]                                   [pic 16]                                                        [pic 17]

                   0                                             -1(Jugador oponente)                                     1(Jugador humano)

Implementación Minimax: Los pasos que sigue minimax pueden variar, pero lo importante es tener una idea clara de cómo es su funcionamiento, los pasos a seguir son:

Para cada nodo final, buscamos la función de utilidad de estos.

Y lo que hará el algoritmo Minimax cuando vaya regresando hacia atrás, será comunicarle a la llamada recursiva superior cuál es el mejor nodo hoja alcanzado hasta el momento. Cada llamada recursiva tiene que saber a quién le toca jugar, para analizar si el movimiento realizado pertenece a la IA o al otro jugador, ya que cuando sea el turno de la IA nos interesa MAXIMIZAR el resultado, y cuando sea el turno del rival MINIMIZAR su resultado.

...