Domingo 26 de abril de 2009 a las 07:38
Voy a decir cosas que tal vez ya sabes, pero por si acaso las digo.
El nivel del árbol puede verse como la cantidad de movimientos futuros que se toman en cuenta.
Digamos que vamos a hacer un árbol con todas las posibilidades que tengo de ir desde el punto A de una ciudad hasta el punto B de la misma ciudad. Imaginemos que todo el mapa está compuesto por manzanas cuadradas alineadas, y representemos ese mapa como una matriz de 10x10. Digamos además que el punto A está en 0;0 y el punto B en 5;5. Supongamos que nos moveremos de esquina a esquina, no podemos quedarnos a mitad de cuadra.
Ok, con lo definido en el párrafo anterior, si el árbol tiene N niveles, puede simular N-1 movidas hacia adelante (ya que la raiz es el estado actual).
Con N=2 yo tengo 2 hijos, ya que estando en una esquina tengo 4 posibles movimientos, de los cuales sólo 2 hacen que se acorte la distancia entre A y B.
Si el árbol tiene 3 niveles, entonces ya puedo prever avanzar 2 cuadras, pero para el 1er movimiento todavía tengo sólo 2 opciones ya que alejarme en el primer movimiento no parece una buena opción.
Si el árbol tiene N=1000 (exagerando) entonces se encontrará el conjunto de caminos óptimos para llegar de A a B, y tal vez el camino óptimo empiece alejándose del punto para sortear algún obstáculo que se encuentra en la mitad (calles cortadas, etc.) aunque al final llega antes o en menos pasos que los otros caminos.
Dicho lo anterior, como la inteligencia que estás utilizando (nivel del árbol) en cada uno de los fantasmas es mayor que la cantidad de movimientos que deberán hacer para llegar a pacman, entonces estás encontrando el mejor camino para todos ellos, y por lo tanto se moverán juntos.
Te sugiero otra estrategia.
En vez de hacer a los fantasmas más inteligentes podés crear un conjunto de celdas tabú. Que cada fantasma lleve un registro de cuáles fueron las últimas 5 celdas por las que pasó. Si en ese conjunto de 5 celdas hay una que se repita 2 o más veces, entonces metela en un conjunto tabú.
Cuando se va creando el árbol para el siguiente movimiento de un fantasma, no podrá pasar por ninguna celda que se encuentre en el grupo tabú. Por lo que no se le permitirá pasar por un lugar donde ya estuvo 2 o más veces en los últimos 5 movimientos.
De esta forma el fantasma se destrancará. Un fantasma poco inteligente ve que para esquivar una pared y llegar a pacman es igual de bueno rodearla por la derecha o por la izquierda. Al agregar la estrategia del conjunto tabú haremos que encuentre menos soluciones, y que se destranque aunque la decisión tomada no haya sido la mejor.
Es importante que una celda ingresada al grupo tabú tenga un tiempo de vida, y luego de pasados, digamos, 7 movimientos, sea quitada del grupo.
Espero que se haya entendido:
- Por qué de que al ser muy inteligentes todos los fantasmas optan por el mismo camino
- Qué es un grupo tabu
- Cómo un grupo tabu lograría que un fantasma se destranque
Fuerza++
=D
