Este año se celebra la tercera edición de la Javacup, un torneo realizado por Javahispano. Este torneo es noticia en este blog, porque para poder participar en él debemos tener conocimientos de inteligencia artificial. Si deseamos competir deberemos realizar un equipo de fútbol utilizando su framework, y programar unas táctica en java que permitan al equipo conseguir el máximo número de goles en esta competición tan exigente. El torneo consistirá en una serie de fases eliminatorias; en cada una de ellas se enfrentaran dos equipos a un partido, hasta llegar a la gran final. Los jugadores que queden entre los cuatro primeros ganarán un año de suscripción gratuita la revista “Sólo Programadores”, y recibirán un premio de 125€, 250€, 500€ y 1000€ respectivamente. Los concursantes tienen como fecha límite el 30 de mayo del 2009.

La verdad que jugar con este tipo de framework es muy divertido, porque no te tienes que preocupar ni de desarrollar interfaces, ni de cuestiones gráficas, sólo te dedicas a desarrollar la inteligencia de tus jugadores. En ellos puedes aplicar todos los conocimientos que poseas.

Hay multitud de tácticas, combinaciones, formas de desplegarse… fíjate si no en estos vídeos del torneo de año pasado.

Un factor importante en el juego es que existe una gran componente azaroso, y como se puede ver hay muchas formas de contrarrestarlo.

Aunque, como se puede ver en la final, las diferencias eran bastante evidentes.

¿Has participado alguna vez en la Javacup? ¿Tienes pensado participar este año? ¿Tienes experiencia en este tipo de competiciones? Cuéntanoslo.

En mi anterior post intentamos definir lo que eran los problemas y cuál era el camino a seguir para solucionarlos. Hoy vamos a plantear un problema típico y muy sencillo, pero con una resolución compleja: el problema del viajante de comercio. El enunciado es el siguiente:

Suetorp es un vendedor de una remesa de droides astromecánicos de la serie R3. Quiere hacer una ruta por el planeta Tatooine recorriendo su principales ciudades, y parte de la capital, Bestine.

Rutas de comercio en Tatooine

Las líneas en rojo marcan las rutas seguras para viajar en este planeta. Nuestro intrépido comerciante debe pasar por todas las ciudades y debe plantearse cuál es el recorrido más barato, es decir, el que gaste menos combustible sin pasar dos veces por el mismo lugar. ¿Cuál es la ruta que debe elegir el comerciante para minimizar el coste?

El problema aparentemente es sencillo, pero el número de combinaciones que tenemos que sopesar es bastante amplio.

Evidentemente nos encontramos ante un grafo con pesos. Estos pesos tendrán el valor de la distancia que tenemos que recorrer para llegar a la ciudad de destino.

¿Qué es un grafo con pesos?

Un grafo es una representación de la información compuesta por nodos, los cuales guardan una información sobre el elemento, y arcos, que unen a los nodos y aportan información sobre la relación que existe entre ellos. Esta información puede ser numérica, y en ese caso es llamada peso.

Grafo con las ciudades que tiene que visitar el mercader

Gracias a este grafo podemos representar el mapa y analizaremos cuál es el camino óptimo.

Muy bien, ¿y cómo encontramos el camino más corto?

Es muy difícil alcanzar la solución óptima probando todas las opciones porque nos encontramos con una infinidad de casos, por lo que tendremos que utilizaremos una serie de algoritmos que nos permitan alcanzar la resolución del problema. Éstos son llamados algoritmos de búsqueda. Durante las siguientes semanas intentaremos resolver el problema aplicando diferentes métodos y analizaremos cómo son de eficientes.

Aunque la inteligencia artificial se ideó para emular los conocimientos humanos, la IA puede ser aplicada para la resolución de muchos problemas. En esta sección nos vamos a encargar de hablar sobre como se aplica la IA para resolver problemas complejos. En muchos casos, los seres humanos los realizan con una facilidad extrema, mientras que a las computadoras les resultará casi imposible llegar acercarse a esa capacidad. Sin embargo en otras ocasiones, conceptos muy sencillos y básicos resolverán problemas, que son casi imposibles de resolver por los humanos, en pocos segundos.

Buscar la salida de una habitación es fácil para una persona, pero es bastante más difícil para una máquina (esto mismo pasa con la visión artificial, con la comprensión del lenguaje natural…), mientras que hacer predicciones buscando relación con miles de datos es sencillo para las máquinas y muy difícil para los humanos (también ocurre esto con juegos de tablero como ajedrez o damas, en la resolución de rompecabezas, la reconstrucción de imágenes…).

Esta sección describirá todos estos problemas y planteará cuales son las soluciones que se aplican en cada uno de los casos. Tocaremos muchos temas y vamos a intentar desarrollarlos de manera que no se necesiten conceptos muy amplios de programación. Cada uno de los temas se dividirá en partes teóricas, donde se explicarán los conceptos básicos, y en ejemplos de código, estos principalmente en Java, donde se aplicarán esos conceptos, estos ejemplos serán explicados minuciosamente de manera que sea fácil trasladarlos a otros lenguajes. Cuando toquemos algunos temas donde necesitemos software adicional utilizaremos, siempre que sea posible, software libre, todos nuestros códigos también estarán sujetos a una licencia pública.

Tal vez ésta sea una de la secciones más prácticas y en la que más vais a poder trabajar, aunque también os digo que es, a mi parecer, la parte más simple de la IA ya que muchos problemas están resueltos sólo hay que saber las posibles soluciones y buscar la que nos parezca más útil para nuestro problema específico.