1.1 Aislamiento [Inteligencia Artificial]

Inteligencia Artificial

El objetivo de esta lección es diseñar una IA más inteligente que usted, al menos en jugar un "juego" real. Un juego es un contexto muy limitado, sin embargo, hacer un programa que pueda jugar mejor que usted es muy emocionante.

Introducción a la IA es una muy buena forma de adentrarse a este mundo de la IA.

Usted aprenderá como utilizar una búsqueda de confrontación para encontrar óptimos movimientos, en particular vamos a hablar sobre el algoritmo Minimax y Alfa Beta, también hablaremos sobre cómo crear funciones de evaluación para los juegos. Estas ideas son suficientes para crear un sorprendente y potente juego. Vamos a utilizar nuestros conocimientos para el juego de Aislamiento, un juego complejo con reglas sencillas y sorprendentes. A continuación, vamos a examinar varios jugadores y juegos probabilísticos. A medida que avance en la lección, usted tendrá que crear un juego para algun jugador solitario.

Minimax es el algoritmo primario para averiguar cuál es el mejor movimiento a cada paso, Alfa beta ayuda a optimizar este algoritmo, haciendo a la gente jugar más rápido.

Para juegos no deterministas (que sus movimientos son conocidos, no son al azar) se utiliza una modificación de Minimax llamado Expectimax, el cual considera todos los posibles resultados y elige uno como el retorno máximo esperado, esto suponiendo que el adversario no está haciendo las mejores jugadas disponibles. Una vez que tengamos este algoritmo Expectimax lo podemos utilizar para muchos juegos diferentes.

Vamos a enseñar las reglas de Aislamiento, el juego de ejemplo que se va a utilizar.


El primer jugador colocar la pieza en cualquier parte del tablero

El jugador oponente también, solo la primera pieza es colocada asi.

A partir de ahora, las piezas se mueven como las reinas del ajedrez, horizontal, vertical o diagonal, excepto a través de las piezas enemigas.

El objetivo es ser el último jugador en moverse, sin salirse de los límites del tablero de juego.
Tampoco a través de una posición que se encuentre actualmente o previamente ocupada por alguna otra pieza.

El primer jugador que consigue aislar a su oponente gana, aislar es volver al jugador contrario incapaz de mover en su turno, y así perder.

Construyendo un árbol de juego

Nota: Comenzaremos con un espacio lleno en un tablero mas pequeño para reducir la complejidad del problema, a medida que tratamos de desarrollar un método para resolverlo. Definitivamente es más agradable (y desafiante) jugar aislamiento en tablas más grandes, con más puntos para llenar.

Ahora vamos a utilizar un tablero sencillo de dos por tres para ilustrar como hacer un árbol de juego que muestra todos los movimientos posibles durante un juego.

Vamos a utilizar este árbol de juego para seleccionar movimientos que dan la mejor garantía de ganar.

Considere cualquier lugar del campo sobre el tablero de juego como no disponible, vamos a empezar con un punto de campo.
Llamaremos al nivel de juego de principio a cero en nuestro árbol de juego.

Supongamos que "O" es el jugador de la computadora.

"O" es el primero en mover, por lo que el equipo tiene 5 opciones en principio.

Sacamos a cabo todas las posibles tablas para el nivel uno del árbol de juego.

La tabla original es de 5x5 pero por cuestiones de explicación y para no hacer exageradamente grande el árbol de juego se van a utilizar solo 5 casillas de esta tabla de 2 x 3.


X va al lado y puede poner su pieza en cualquier parte del tablero de juego que no ha sido tomada por "O".

Así que no importa qué posición "O" ocupe para su primer movimiento, "X" tiene cuatro opciones


Podemos extraer rápidamente los nodos de nivel dos de nuestro árbol.

A partir de entonces, el número de opciones para cada jugador se vuelve más pequeña ya que las piezas se limitan a los movimientos como una reina en el ajedrez.


"O" va al lado, para la mayor parte de la hoja izquierda, O puede moverse hacia abajo


A forma de ejercicio identifique los movimientos posibles para "O" en su siguiente turno, respecto al movimiento ya realizado.

---