Una de inteligencia artificial: buscador de caminos A*

Desde mi punto de vista una de las ramas más fascinantes de la programación es la Inteligencia Artificial. Existen 2 definiciones de IA que me gustan especialmente, la primera es muy técnica y la segunda muy práctica, y son las siguientes:

1) Disciplina de la programación dedicada a resolver problemas de complejidad exponencial.
2) Dícese de aquellos actos efectuados por una máquina que de hacerse por humanos se atribuiría a la inteligencia.

Existe una eterna discusión acerca de si las máquinas pueden llegar a ser realmente inteligentes, y en ese sentido recomiendo un libro bastante bueno, «El quinteto de Cambridge» de John L.Casti.

Yo desde luego soy de los que piensa que una máquina sí puede ser inteligente, y llegará un momento en que nos superen. Una de las aplicaciones prácticas que me resulta más interesante (por mi aficción a los juegos) es el buscador de caminos. Son algoritmos por los cuales nuestro objetivo es capaz de sortear los obstáculos y llegar de un punto A a otro B.

El más popular de todos ellos por su eficacia y eficiencia es el buscador A* (o A-estrella, A-Star para los anglosajones). Existe mucha literatura en internet al respecto y recomiendo su lectura si estás interesado en el tema. Groso modo se trata de un mecanismo de selección de trayectoria que utiliza una heurística por la que descarta los nodos de búsqueda de mayor coste y más alejados del destino (en verdad tiene más chicha pero vaya, no tiene sentido extenderse).

Y como no voy a contar algo que ya está en internet os pongo una aplicación práctica de como funciona el A*. Aquí os pongo un pequeño ejecutable hecho en Blitz Basic (para un juego de rol) en el que podeís juguetear con un punto y ponerle obstáculos. Vereís si el condenado es listo o no.

Buscador A*

Funciona tanto en Windows como en Linux usando el wine. Agradecimiento especial a Patrick Lester, cuya ayuda resultó imprescindible.

P.D.: Thank you Patrick, you are on the credits of Caotic Party.

Comentarios

  1. Mezclando un poco los temas:
    ¿Donde podríamos estar si la evolución hubiera estado guiada por una búsqueda A o mejor aún por una búsqueda basada en el aprendizaje?
    Comparado estos con la evolución Darwiniana podría parecer este un mecanismo muy ineficaz, ya que genera ciegamente aproximadamente 10^45 organismos sin mejorar su búsqueda heurística un ápice.
    Os dejo un pequeño applet para hacer pruebas:http://www.cs.rmit.edu.au/AI-Search/Product/

  2. El problema del 8-puzzle, otro gran clásico de la IA :). Al respecto de la evolución ya que lo mencionas tengo una duda. Si nuestros primeros ancestros caminaron sobre la tierra hace 5 millones de años y en solo 200 años hemos pasado de carros tirados por caballos a surcar las estrellas, ¿qué demonios hemos hecho en los otros 5 millones? Mucho tiempo perdido veo yo…

  3. bueno me parece interesante el tema yo tbn tengo este problema pero cuando estaba paseando por la web encontre una aplicacion hecha en blitzbasic que parece prometedor con respecto a la busqueda de caminos lo que hace el programa es cargar tu escenario o construirlo dentro de el y en base a nodos generar todos los caminos posibles para luego lo exporta en 2 archivos uno con las coordenadas de cada nodo y el otro con la enumeracion de cada nodo y el mapa para poder llegar lo mas rapido posible de un punto a cualquier otro.

Comments are closed.