2.4 Profundización Iterativa [Inteligencia Artificial]

La profundización iterativa es casi libre debido a la naturaleza exponencial del problema. Esta realmente ayuda cuando se tiene un juego como aislamiento como el factor de ramificación violentamente variable. Cuando se calculó que solo debemos ir nueve niveles de profundidad en un árbol de aislamiento de cinco por cinco y dar una respuesta de dos segundos. Hemos asumido un factor de ramificación ocho. Sin embargo, hacia el final del juego, los jugadores de aislamiento solo tienen un par de movimientos disponibles. Podríamos ser capaces de buscar mucho más profundamente en el final del juego.

El final del juego es precisamente el momento que desea buscar más profundamente, para que pueda ver lo que sucederá.
Por otro lado el comienzo del juego, el factor de ramificación es bastante grande. Nuestro jugador de la computadora podría no responder en dos segundos.

Significa profundización iterativa que nuestro jugador de la computadora siempre tiene preparada una respuesta en caso de que se agote el tiempo y se pueda buscar en la medida de lo posible dentro de sus limitaciones de tiempo. Hemos limitado nuestro tiempo a dos segundos por jugada. Sin embargo en algunos juegos, como el ajedrez de velocidad, limitamos el tiempo total que un jugador puede tomar durante todo el partido. En estas situaciones, nuestro jugador de la computadora va a querer buscar más profundo en algunas partes del juego.

A menudo, podemos crear estrategia para la profundidad que queremos buscar.  Algo así como tener un libro de jugadas iniciales estándar para el principio del juego a continuación buscar más profundo en el medio y utilizar menos tiempo en el final. Basándose en la reducción y factor de ramificación y profundizar permitir todavía que nuestro jugador de la computadora iterar para poner fin al juego o tan profundo como pueda, dado el tiempo restante.

O es posible que desee tener una cantidad conservadora de tiempo que dedicamos por jugada y el uso de profundización iterativa y búsqueda de reposo para determinar los pocos movimientos que queríamos pasar más tiempo buscando.

Todas esas son grandes estrategias, pero todavía podemos tener problemas debido a algo que se llama el efecto horizonte.


Un desafío que queda en hacer que nuestro jugador de la computadora situaciones en las que es obvio para un jugador humano que el juego se decidirá en el siguiente movimiento, pero que el jugador de la computadora no puede buscar lo suficiente lejos a futuro para averiguar el problema.

Esta situación se conoce como el efecto horizonte.

De un vistazo a este tablero de aislamiento.

Es el turno de "O", Que movimiento debe tomar?



Tan pronto como "O" se mueve en diagonal hacia abajo y dejado uno, "X" solo tendrá seis movimientos en comparación con "O" de siete. A continuación "O" va a ganar.

Pero ese es el movimiento 13 y se mueve en el futuro. ¿Cómo darse cuenta de eso?

"X" será boqueado en el lado equivocado de una partición y no será capaz de alcanzarlo, ambos jugadores tendrán que rellenar el resto del tablero de juego de manera eficiente con el fin de tener una oportunidad de ganar.

Esa es una observación que nuestro jugador de la computadora no puede ver. Recuerde cuando empezamos a hablar de tener dos segundos para hacer un movimiento, dijimos que nuestro jugador de la computadora solo debe mirar hacia adelante nueve movimientos. No va a ver el final del juego que viene, pero con la profundidad iterativa podría ser capaz de ir más profundo. El factor de ramificación hacia el final del juego es mucho más pequeño. Sin embargo, imaginemos que tenemos todo listo para alcanzar la penúltima profundidad de nuestro árbol de búsqueda en el tiempo que tenemos. Tenemos que evaluar la bondad de las ramificaciones de este nodo.

Ciertamente no es el movimiento ganador. La función de evaluación volverá tres para el movimiento ganador, pero puedo ver un par de movimientos que sería preferido.
Ir todo el camino hacia la derecha da un cinco.


Y adelantándose en diagonal a la izquierda y abajo dos espacios da un seis, sin embargo, ambos de estos movimientos se traducirán en una pérdida.


Ir a la derecha o del lado equivocado de la partición, hacia la izquierda "O" para crear una partición con aun menos movimientos.

Tal vez deberíamos incluir una verificación en la función de evaluación para ver si una partición está formada por el siguiente movimiento. Y si es así, comenzar a contar la cantidad de movimientos que restan al jugador.

Es una gran idea pero va a costar que nuestra función de evaluación va desde una función muy sencilla de calcular a algo que puede implicar una gran cantidad de conteo. Simplemente contando el número de cuadros contiguos que un jugador puede utilizar se asemeja a la búsqueda niveles más abajo en el árbol de búsqueda.

Sabemos que es mucho tiempo.

El punto es que solo se duplicó la cantidad de tiempo que toma la función de evaluación. Ese tiempo se multiplica exponencialmente debido al factor de ramificación como la búsqueda más profunda.

Las funciones de evaluación no siempre valen la pena, depende el juego. Cambiar las reglas del aislamiento poco puede cambiar drásticamente si se trata de utilizar una función de evaluación simple y buscar más profundo. O utilizar una función de evaluación complicada que capture estas situaciones peligrosas.

---