3.3 Aislamiento 5 X 5 [Inteligencia Artificial]

Resolviendo el aislamiento 5x5

Cuando se trabaja en el juego 5x5 aislamiento de la clase, creímos que se hizo para buscar el final del juego.

Pero cuando hablamos de factor de ramificación anterior, dijimos que lo haría imposible buscar el fin del juego en una cantidad razonable de tiempo.

En primer lugar se implementó el algoritmo MiniMax con Alfa Beta.

Como ya saben, esto reduce el tamaño del espacio de búsqueda, reduciendo así de aproximadamente 8 a la 25 al 8 a la 12.

Después se aprecia que algunos movimientos son equivalentes.

Por ejemplo vamos a ver un jugador del primer movimiento.

Si el jugador se mueve a 0,0 es el equivalente a mover en 4,0. Si se da cuenta solo se está rotando el tablero 90 grados y se tiene el mismo estado del tablero.



Por lo tanto si se conoce el árbol de juego para nuestro primer movimiento de 0,0, se conoce el árbol de juego para nuestro primer movimiento de 4,0, que es el mismo que 4,4 y lo mismo para 0,4.

Esto es útil sobre todo al principio del juego cuando la ramificación es mucho mayor.

Por ejemplo, mientras que el jugador uno tiene 25 movimientos posibles, en realidad solo hay seis movimientos únicos, ya que se puede usar la simetría alrededor del eje horizontal y vertical.



Y sobre el eje diagonal, y por supuesto está el centro de movimiento.


Solo se han mostrado seis movimientos únicos de jugador y sus equivalentes. Un análisis similar es posible en cualquier estado que se defina como una serie de orden de movimiento.
Vamos a movernos a través de un ejemplo.
O se colocó en 2,2
X está considerando posibles movimientos y evalúa primero un movimiento a 2,1
X ahora conoce el valor del estado, 2,2 , 2,1.
Ahora vamos a considerar un movimiento X de 2,3.
X comprueba si el resultado de este movimiento ya se conoce.

Para hacer esto X comprobaciones para ver si se conoce el valor de la tabla de estado 2,2 , 2,3, no es así, ahora X gira el tablero 90 grados y comprueba para ver si sabe el valor de 2,2 y 1,2 tampoco lo conoce, a continuación X gira 180 grados y comprueba si se conoce el valor del estado del tablero 2,2  ,  2,1. Ahora lo conoce...


X devuelve el valor del estado del tablero 2,2   ,   2,1 y no es necesario ampliar el árbol del juego aún más.

Si X no ha encontrado la solución, se habrían comprobado los estados de tabla creados por la rotación del tablero 270 grados y voltear la junta a lo largo de su eje diagonal. Solo entonces se habrían necesitado X para expandir el árbol de juego.

Así que se ha encontrado que la simetría realmente reduce el número de nodos que había que expandir solo hasta alrededor del nivel 3 de búsqueda.

Todo esto reduce el número de estados posibles del juego, pero aun no es suficiente.

Durante la búsqueda de una función de evaluación, se descubrió que no siempre se tiene la necesidad de buscar el final del árbol del juego.

Resulta que se puede saber el resultado tan pronto haya una partición.

Esto es porque un espacio separa dos jugadores completamente, por lo tanto el jugador con la trayectoria más larga gana.

Por ejemplo en este juego, el jugador mueve lo siguiente.


Pero el resultado de este juego ya se conoce por que el primer jugador tiene 8 movimientos posibles, mientras que el segundo jugador solo tiene 6.

Así que las particiones, alfa-Beta y la simetría permiten ver a través de todos los movimientos posibles.
Y el resultado es curioso, resulta que el jugador 2 siempre gana.

La reflexión es simplemente la rotación de 180 grados de movimiento del oponente. Al tratar de resolver el juego, sucede un fenómeno interesante.

Si la primera jugada del jugador uno es el centro y el primer movimiento del segundo jugador es de dos, entonces el jugador uno puede llegar a ganar.

Todo lo que tiene que hacer es reflejar cada movimiento del jugador 2.

Como puede el jugador evitar perder, la respuesta es cambiando a una ubicación que el jugador no se pueda reflejar.
Existen ocho posibles movimientos de los 24 disponibles para el jugador dos.


¿Qué ocurre si tres jugadores quieren entrar a la partida de aislamiento?

Para juegos multijugador no se utiliza MiniMax.
En su lugar se evalúa el tablero de juego desde la perspectiva de cada jugador y se propagan los valores a través del árbol.
Imagina un árbol de juego donde se busca hasta el nivel 3 del árbol.

En la rama más a la izquierda se evalúa el tablero de juego que resulta de cada una de las perspectivas del jugador. Para el jugador 1, la función de valoración devuelve un 1 para el jugador 2 que es un 2. Y para el jugador 3, la valoración es un 6.


Se evalúa cada uno de los nodos de mesa de este nivel y a continuación se vuelven trillizos para cada uno de ellos y luego propagar los valores del árbol.

En primer lugar, elegir el valor máximo en cada una de las ramas de nivel 2 desde la perspectiva del jugador 3.
El nodo más a la izquierda, el jugador 3 tiene una opción entre 6 y 3


Sí por su puesto elegimos 6, en la siguiente rama a la derecha en este nivel hay una elección entre un 2 y un 1, por lo que se eligió 2.

En la tercera rama de la izquierda escogemos entre un 2 y un 1 por lo que, se elige un 2.

Y finalmente en la última rama de la derecha se elige el 5.
Y para el siguiente nivel se elige el máximo valor desde el punto de vista del jugador 2.

Por lo tanto en la rama izquierda se elige la rama con el 2 y, en la rama de la desecha elegimos el 5.



Y en el nivel superior elegimos el valor máximo desde la perspectiva del jugador 1.
En este ejemplo las dos opciones son igual de buenas.

Así que se elige el uno a la izquierda por defecto.
Esta versión de un árbol de juego, lo llamamos MAX N, puede trabajar para juegos con cualquier número de jugadores.

Como ejercicio rellene le árbol de juego del siguiente ejemplo de tres jugadores, que alterna entre los tres niveles de jugadores. Los valores de cada nodo están en el orden, reproductor de una anotación, dos jugadores puntuación, y el jugador sesenta.

Cada quien intenta maximizar su propia puntuación, por lo que se propagara a los valores de la base.

---