• Author / Uploaded
• Charming Pilares Leon

• Categories
• Áreas de la informática
• Programación de computadoras
• Ciencias de la computación teórica
• Matemática aplicada
• Informática

Citation preview

El problema del Tres en raya Aliaga Cornejo María Eugenia [email protected]

Pilares León Charming Catherine [email protected]

Universidad Nacional de San Agustin, Arequipa Escuela Profesional de Ingeniería de Sistemas

Resumen Los orígenes del Tres en Raya se remontan a hace mucho tiempo en un país del lejano Oriente. Muchos autores piensan que el Tres en Raya (el llamado Tic Tac Toe en inglés) se originó en China, como muchos otros juegos de mesa. El tres en raya 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.

1.

INTRODUCCIÓN El juego Tres en raya ha sido propuesto desde sus inicios como un juego entre adversarios (dos jugadores) y con manejo de fichas o simplemente a lápiz y papel. Con el tiempo esta idea ha ido evolucionando y ha tenido un gran impacto con la computación, debido a que se trata de un problema de razonamiento y estrategia, y que puede ser utilizado como base introductoria a lo que es Inteligencia Artificial. El proceso de razonamiento va enfocado principalmente a que el jugador escoja la mejor jugada, debido a que el objeto de búsqueda es encontrar el camino desde un estado de punto de partida a un estado objetivo, lo que lo hace un problema algo complicado. Ante este problema es que se han planteado diferentes algoritmos para su resolución, siendo la mejor opción la utilización del algoritmo Minimax, el que será detallado y desarrollado en el transcurso de este documento.

2.

DEFINICIÓN DEL PROBLEMA El objetivo del tres en raya, es que dado dos jugadores: O y X, marquen los espacios de un tablero de 3×3 alternadamente hasta conseguir que un ganador gane, esto sucede cuando se consigue tener una línea de tres símbolos (el símbolo varía dependiendo del jugador) que puede ser horizontal, vertical o diagonal. Este problema tiene diferentes propuestas de solución, las que detallaremos a continuación:

Solución #1 Una primera solución directa a este juego podría ser la de almacenar en un vector las 19.693 (39) posibilidades de un tablero de 3 x 3 con tres valores posibles en cada casilla (vacío-X-O), así como las correspondientes jugadas sucesoras. Para realizar una jugada, bastaría con acceder a la posición del tablero actual y la jugada sucesora correspondiente.

1

Las desventajas de este eficiente programa son bastante obvias: - necesita gran cantidad de memoria - alguien debe realizar el pesado trabajo de introducir todas las jugadas y sus sucesoras - el juego no se puede ampliar, por ejemplo a tres dimensiones. Solución #2 Considerando una estrategia para cada turno de jugador, se analiza el posible triunfo a partir de un estado del tablero dado. Aunque es menos eficiente que la solución anterior en términos de tiempo, tiene la ventaja que es más eficiente en términos de espacio. Su estrategia es más fácil de comprender y realizar cambios, aunque el programador debe comprender la totalidad de la estrategia de antemano. Solución #3 Implementar una estructura que contenga el tablero actual, así como una lista de posiciones del tablero que podrían ser el próximo movimiento, y una estimación de la probabilidad de que esa jugada lleve a la victoria. Para decidir la siguiente jugada se tienen en cuenta las posiciones de tablero que resultan de cada movimiento posible. Se decide la posición que corresponde a la mejor jugada, considerando si la jugada produce la victoria, y en caso contrario considerando todos los movimientos que el oponente puede realizar asumiendo que éste elegirá el peor para nosotros. Esta última solución cuenta con un algoritmo, el cual inspecciona secuencias de movimientos intentando maximizar la probabilidad de victoria. Necesita mucho más tiempo que los demás, ya que debe realizar una búsqueda en una estructura de posibilidades antes de realizar cada movimiento. Sin embargo, es superior a las demás soluciones pues podría ser ampliado para manipular juegos más complicados.

3.

MODELADO DEL PROBLEMA El problema del Tres en raya se enuncia inicialmente así: Empieza inicialmente con un tablero de 3x3 que es representado por un vector de nueve componentes, donde las componentes del vector se corresponden con las posiciones del tablero de la siguiente forma:

Figura 1: Representación del tablero

También consideramos una variable que determine la posición dentro del vector para calcular si ese campo está vacío, o no lo está, para así calcular si la partida ha finalizado o está aún en proceso. Para ello se define variables constantes que determinen el estado del juego, es decir, estado: GANADOR_JUEGO_O, GANADOR_JUEGO_X, EMPATE, además también se han considerado otros estados propios del desarrollo del juego propiamente dicho: COMENZAR, JUGANDO, PARAR. El tablero es representado como una lista de posiciones del tablero, en este caso fue construida una estructura vector, donde se puede relacionar con el siguiente movimiento, y un

2

número que representa una estimación de la probabilidad de que la jugada lleve a la victoria al jugador que mueve. Para determinar cómo es evaluado cada nodo o estado de la jugada, se realiza una evaluación por cada jugada, de la siguiente manera:

Figura 2: Evaluación jugada Y así determinamos que posibilidades existe para realizar la siguiente jugada, dependiendo de la posición de esta jugada inicial.

Aplicación del Algoritmo Para poder decidir la siguiente jugada, se debe tener en cuenta las posiciones del tablero que resultarán de cada posible movimiento. Decidir qué posición es la mejor, realizar la jugada que corresponda a esa posición, y asignar la clasificación de mejor movimiento a la posición actual. Para decidir cuál de todas las posibles posiciones es mejor, se realiza para cada una de ellas la siguiente: -

-

Ver si se produce la victoria. Si ocurre catalogarla como la mejor dándole el mejor puesto en la clasificación. En caso contrario, considerar todos los posibles movimientos que el oponente puede realizar en la siguiente jugada. Asumir que el oponente realizará este movimiento. Cualquier puesto que tenga la jugada, asignarla al nodo que se está considerando. El mejor nodo es el que resulte con un puesto más alto.

Para determinar cómo son dadas las jugadas simulamos el compartimiento de cada una:

Figura 3: Distribución de las jugadas

3

El algoritmo utilizado, como ya se había mencionado previamente es Minimax, este algoritmo inspecciona varias secuencias de movimientos para encontrar aquella que lleva a la victoria. Intenta maximizar la probabilidad de victoria, mediante la suposición de que el oponente intentará minimizar dicha probabilidad.

Heurística Para este problema, las heurísticas utilizadas en este estudio fueron diseñados para ser simples. Se parte de la idea inicial de tener el tablero con sus respectivas posiciones, para luego determinar los resultados en base a las posiciones del tablero ocupadas. Como el juego es del tipo «Humano vs computadora», se ha determinado considerar las variables: +ORDENADOR y –ORDENADOR, que calculara si el computador está ganando o está perdiendo, o simplemente el valor 0 si se trata de un empate La variación entre el optimista, pesimista y heurística Indeciso desarrollado a partir del juego de tener que resolver el valor de una junta sin terminar / indecidible que resulta de un control de mayor profundidad para reducir el tiempo de búsqueda.

4.

RESOLUCIÓN En base al modelo presentado, se ha implementado en un lenguaje determinado para que pueda ser resuelto. El lenguaje de programación utilizado es C++ bajo Visual Studio, debido a su facilidad en manipulación de objetos y estructuras. Para la resolución de este problema se ha aplicado el algoritmo Minimax, este recibe como parámetros un tablero definido con las 9 posiciones de posible juego descritas anteriormente y un jugador que realizara el movimiento respectivo. Con el fin de aplicar este algoritmo es necesario que se genere una lista de movimientos. Una vez implementado el algoritmo queda de la siguiente manera: int MiniMax(char _tablero[9], jugador _jugador) { int mejor_valor = -ORDENADOR; int indice = 0; /* Utilización de la estructura */ std::list lista_movimientos; char mejores_movimientos[9] = {0}; generar_movimientos(_tablero, lista_movimientos); while(!lista_movimientos.empty()) { _tablero[lista_movimientos.front()]= _jugador.simbolo; Simbolo_actual = _jugador.simbolo; int val = movimiento_Min(_tablero, _jugador); if(val > mejor_valor) { mejor_valor = val; indice = 0; mejores_movimientos[indice]=lista_movimientos.front()+1; } else if(val == mejor_valor) { mejores_movimientos[++indice]=lista_movimientos.front()+ 1; } _tablero[lista_movimientos.front()]= 0; lista_movimientos.pop_front(); } return mejores_movimientos[indice]; }

En esta implementación del algoritmo Minimax, se ha utilizado dos estructuras de datos para la representación del árbol formado por este algoritmo, la estructura principal usada es un array de listas, donde se almacenan las movidas realizadas por el jugador. std::list lista_movimientos; char mejores_movimientos[9] = {0};

4

En esta función se llama a la función: generar_movimientos(_tablero, lista_movimientos); Dicha función esta implementada como: void generar_movimientos(char _tablero[9], std::list &lista_movimientos) { for(int i = 0; i < 9; ++i) { if(_tablero[i] == 0) { lista_movimientos.push_back(i); } } }

Donde se muestra claramente que cada movimiento realizado es almacenado en la lista creada, mediante la función propia del tipo lista: lista_movimientos.push_back(i); Esta función que representa el comportamiento del algoritmo Minimax, esta implementada basándose en dos conceptos de este algoritmo, lo que corresponde a calcular el mínimo y máximo valor. Por ello que se han implementado como otras funciones: // Encontrar el mejor movimiento para minimizar int movimiento_Min(char _tablero[9], jugador _jugador) { int estado_tablero = evaluar_estado_tablero(_tablero, _jugador); if(estado_tablero != -1) { return estado_tablero; } int mejor_valor = +ORDENADOR; std::list lista_movimientos; generar_movimientos(_tablero, lista_movimientos); while(!lista_movimientos.empty()) { if (_jugador.simbolo == 'X') Simbolo_actual = 'O' else Simbolo_actual = 'X'; _tablero[lista_movimientos.front()] = Simbolo_actual; int val = movimiento_Max(_tablero, _jugador); if(val < mejor_valor) { mejor_valor = val; } _tablero[lista_movimientos.front()] = 0; lista_movimientos.pop_front(); } return mejor_valor; } // Encontrar el mejor movimiento para maximizar int movimiento_Max(char _tablero[9], jugador _jugador) { int estado_tablero = evaluar_estado_tablero(_tablero, _jugador); if(estado_tablero != -1) { return estado_tablero; } int mejor_valor = -ORDENADOR; std::list lista_movimientos; generar_movimientos(_tablero, lista_movimientos); while(!lista_movimientos.empty()) { if(_jugador.simbolo == 'X') Simbolo_actual = 'X' else Simbolo_actual = 'O'; _tablero[lista_movimientos.front()] = Simbolo_actual; int val = movimiento_Min(_tablero, _jugador); if(val > mejor_valor) { mejor_valor = val; } _tablero[lista_movimientos.front()] = 0; lista_movimientos.pop_front(); } return mejor_valor; }

5

Para el cálculo de la profundidad del árbol generado por el algoritmo, es que se ha definido la función: int obtener_nivel_juego() Esta función determina el nivel de dificultad del juego, este término especifica que tanto de entrenamiento se le ha asignado al computador para tal juego. Este código nos ejecutará el resultado para el juego de modo consola:

Figura 4: Resultado de ejecución

5.

REFERENCIAS [1]

Martha Mercaldi, Katarzyna Wilamowska General Heuristic for Tic-Tac-Toe, 2004

[2]

Desconocido, MTU Department of Computer Science, Heuristic Search, Chapter 4

[3]

Heather Desurvire, Martin Caplan, Jozsef Toth, Using Heuristics to Evaluate the Playability of Games.

[4]

Hauk, Buro, Schaeffer, Minimax Search in Computers and Games, 2006

6