Tres en Raya

TRES EN RAYA

El tres en línea, también conocido como tres en raya, juego del gato, tatetí, triqui, tres en gallo, michi o la vieja, es un juego de lápiz y papel entre dos jugadores: O y X, que marcan los espacios de un tablero de 3×3 alternadamente. Un jugador gana si consigue tener una línea de tres de sus símbolos: la línea puede ser horizontal, vertical o diagonal. Además en este juego podemos competir con la computadora.

Para la realización de la interfaz utilizamos lo siguiente:

• Utilizar eventos para los componentes.
• Menús, botones, gráficos, etc.

En lo que respecta a la parte programática:

• Implementar el algoritmo Min-Max para simular la inteligencia artificial de la máquina.
• Lograrlo mediante el uso de árboles y recursión
• Lenguaje de programación: Java.
• Uso del algoritmo Min-Mac de teoría de juegos.
• Árboles y recursión.

Algoritmo Min – Max

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. Minimax es un algoritmo recursivo.

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

Pasos del algoritmo Minimax:

1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.

2. Cálculo de los valores de la función de utilidad para cada nodo terminal.

3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.

4. Elegir la jugada valorando los valores que han llegado al nivel superior.

El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante una función de evaluación, empezando por los nodos terminales y subiendo hacia la raíz. La función de utilidad definirá lo buena que es la posición para un jugador cuando la alcanza. En el caso del ajedrez los posibles valores son (+1,0,-1) que se corresponden con ganar, empatar y perder respectivamente. En el caso del backgammon los posibles valores tendrán un rango de [+192,-192], correspondiéndose con el valor de las fichas. Para cada juego pueden ser diferentes.

Si Minimax se enfrenta con el dilema del prisionero escogerá siempre la opción con la cual maximiza su resultado suponiendo que el contrincante intenta minimizarlo y hacernos perder.

El algoritmo MINIMAX sirve para determinar la estrategia óptima para MAX, y decidir, de este modo, la mejor jugada. El algoritmo se compone de cinco pasos:

1. Generación de todo el árbol de juego, completamente hasta llegar a los estados terminales. En la mayoría de los casos, esto resulta prohibitivo.

2. Aplicación de la función de utilidad a cada estado terminal y obtención de su valor respectivo.

3. Uso de la utilidad de los estados terminales para calcular la utilidad de los nodos de nivel superior en el árbol de búsqueda.

4. Continuación del respaldo a los valores de los nodos hojas, en dirección a la raíz, una capa a la vez.

5. Finalmente, los valores respaldados llegan a la parte superior del árbol; aquí, MAX selecciona la jugada que le permite obtener el valor más alto.

INTERFAZ DEL JUEGO

Esta es la pantalla que aparece cuando el programa se carga.

Para iniciar el juego

Para escoger la forma de jugar

Ingresar los nombres de los jugadores

Persona Computadora

Escoger tipo de fichas

Video en YouTube:

http://www.youtube.com/watch?v=Q6ECoQuTzyQ

Programa en Megaupload:

http://www.megaupload.com/?d=M3ROR8AI