S3, S4, S5, S6, S7, S8. y que están numeradas en sentido horario. Además tiene 4 movimientos posibles:
• Norte: Se mueve una celda arriba.
• Sur: Se mueve una celda abajo.
• Este: Se mueve una celda a la derecha.
• Oeste: Se mueve una celda a la izquierda.
• Características:
− Percepción: Según el ejemplo anterior hay 8 variables para ubicarnos, por tanto existen 28=256
combinaciones de valores posibles. Algunos pueden ser descartados, ya que no existen pasillos estrechos.
Podemos elegir 4 carcterísticas llamadas X1, X2, X3, X4.
− Acción: De las características definidas, lo siguiente que debemos hacer es darles alguna definición para que
puedan cumplir su cometido.

Capítulo III − Búsqueda Heurística
3.1 Introducción: Se llama Búsqueda Heurística debido a que usa conocimientos específicos del problema.
Con esta búsqueda podemos encontrar soluciones más eficientemente en el tiempo mas rápido posible sin
repetir ninguna ciudad. No obstante existe un tope de 30 ciudades, ya que aún a 1 µseg por solución, se
tardaría 1020 años en resolver el problema. (El universo solo tiene 1,6 x 1010 años). Una solución común es
de 9 ciudades, que nos da una combinación de 9!=362 880 viajes posibles. Como se ve, la Búsqueda
Heurística nos da la ventaja de rapidez en estos casos.
A la aproximación de la Búsqueda Heurística, la llamaremos: Búsqueda Primero el Mejor. Existen algunas
variantes:
3.2 Algoritmo *A: Es la forma de búsqueda Primero el Mejor más conocida, sirve para el pathfinding
(Búsqueda de Caminos) y es muy usada en juegos. Un ejemplo es el famoso juego Pacman: Los fantasmas
que persiguen a Pacman buscan el camino mas corto, en lugar de aparecer en forma aleatoria en el Mapa del
Juego, otro ejemplo es el Age of Empires, un juego de conquista de civilizaciones, los enemigos salvan
obstáculos para llegar a la ciudad del adversario. El Algoritmo *A, no desarrolla un camino por interacción,
sino que desarrolla varios caminos y elige los más prometedores. (Para ver un ejemplo del Algoritmo *A
véase el Anexo A).
4.3 Algoritmo MINIMAX: Se poseen 2 jugadores: MAX y MIN, primero jugará MAX y así seguirá el flujo
hasta acabar el juego. Existe un árbol de juegos que los programas utilizan para calcular los Movimientos
Legales (Permitidos). El valor MINIMAX será un valor que determine el estado final del juego (En le ajedrez:
−1, 0, 1; que son triunfo, derrota o empate). En algunos juegos este valor MINIMAX puede ser muy alto
(Como en el Backgamon, se estima algo de −192 a 192 valores).
Incluso el TicTacToe (3 en Raya), es complejo para armar el árbol de juegos. A los niveles del árbol se les
llama capas.
Para determinar la estrategia óptima a seguir se usan valores MINIMAX. MAX adoptará el valor máximo y
MIN el mínimo. La decisión MINIMAX supone que los 2 jugadores son óptimos, si uno es un novato será
fácilmente derrotado por esta decisión.
El Algoritmo MINIMAX es la forma computacional en la que se calcula el valor MINIMAX de cada estado
4