Extendí mi ejercicio de A* para que además busque la solución utilizando Avara y las compare gráficamente.

Avara es otro algoritmo de búsqueda, pero a diferencia de A* no es ni óptimo ni completo. Ambos utilizan una heurística para estimar el costo de un estado n al estado objetivo y por esto se dice que son métodos informados.

La diferencia radica en cómo seleccionan nodos para su expansión: mientras que A* siempre elije el nodo que minimice la función camino recorrido + estimación al objetivo, Avara simplemente elije el nodo con menor estimación al objetivo (no tiene en cuenta el camino previo).

Hay escenarios en los que ambas estrategias encontrarán el mismo camino:

Pero hay otros en los que no:

Instalación y uso

Similar al ejemplo anterior. Teniendo Python y PyGame instalados, obtener el código fuente:

svn co http://svn.juanjoconti.com.ar/astar/tags/astar-vs-avara/ astar-vs-avara

y dentro de la carpeta astar-vs-avara ejecutar gui.py:

cd astar-vs-avara

python gui.py

El ejemplo consiste en un plano de 800x600 puntos con el punto (0,0) en la esquina superior izquierda. En el plano hay puntos y figuras (formadas por puntos). Uno de los puntos es el origen y otro el destino. El problema a resolver es encontrar el camino más corto desde el origen al destino moviéndose de punto a punto y sin pasar sobre una figura.

La heurística utilizada es la distancia en línea recta desde la posición actual a la posición del objetivo.

Instalación y uso

Teniendo Python y PyGame instalados, obtener el código fuente:

svn co http://svn.juanjoconti.com.ar/astar/tags/astar-only/ astar

y dentro de la carpeta astar ejecutar gui.py:

cd astar

python gui.py

El primer click que se haga marcará el punto origen (verde) y el segundo el punto destino (rojo).

Luego se pueden agregar tantos puntos sueltos o figuras como se quieran. Si se hace uno o dos clicks y luego se aprieta la barra espaciado, uno o dos puntos son añadidos al planto. Si se hacen más de dos clicks antes de apretar la barra espaciadora, entonces una figura formada por los puntos marcados es añadida.

Se siguen cargando tantos puntos y figuras como se quiera. Finalmente, al aprender Enter se ejecuta el algoritmo de búsqueda y si se encuentra un camino-solución, este es graficado.

Otros casos de prueba:

Teoría relacionada

• Estrategia de búsqueda A*
• Inteligencia artificial, un enfoque moderno

La semana pasada se desarrolló PyWeek 7. Este año participé con una entrada solo (se puede participar solo o en equipo) e hice un pequeño juego en las 10 horas que tuve para dedicarle a la competencia: Cecilia Music Game. Un juego en el que escuchamos una canción y luego tenemos que intentar reproducir eligiendo cuerdas de distinto largo (el tema de la competencia era "The length of a piece of string").

Download: cecilia_music_game-1.0

Video: http://www.youtube.com/watch?v=Z5P0GB00RpY (gracias, Ema)

Acaba de terminar la sexta edición de PyWeek.

Algo que me gusta mucho de esta competencia es que además de ser votado por tus pares, podés recibir comentarios de ellos. De los 48 comentarios que nos dejaron (el juego más votado tuvo 49 votos) resumo:

<li><strong>Hard to play:</strong> casi todos se quejaban o al menos comentaban que les resultó difícil de jugar el juego, al menos al principio. Nos recomendaban que el primer nivel nivel sea más fácil, esto ayuda al jugador a no frustrarse.</li>

<li><strong>Volver a empezar:</strong> muchos también se quejaron de que una vez que perdías tenías que volver a empezar. Otro punto para evitar la frustración de nuestros queridos jugadores.</li>

<li><strong>Consistencia:</strong> si todo el juego es basado en mouse, el menú también podría haberlo sido :)</li>

<li><strong>Otras críticas menores:</strong> pocos niveles, más robots.</li>

<li><strong>Excelente artwork:</strong> tanto los gráficos como la música fueron muy aclamados. Gracias César, David y Pablo por hacernos ver como estrellas de rock ;-)</li>

Espero que en la próxima tengamos estas cosas presentas para nuestro plan de acción :D ...y que tengamos plan de acción ;-)

PS: en otro orden de noticias, salimos 6tos.

El sábado pasado entregamos nuestro juego para la sexta competencia de programación de juegos en Python PyWeek. El nombre se debe a que el juego debe ser desarrollado integramente en una semana :)

Ya participamos el año pasado con un juego llamado Twisted Zombie. Una particularidad del certamen es que los juegos deben respetar un tema. El tema de cada concurso es votado por los participantes de entre una lista de 5 temas posibles y es rebelado la misma noche que comienza la competencia (9 pm en Argentina).

El tema de este año fue robot y, como el año pasado, no habíamos pensado ninguna buena idea para este :( Pero a no desesperar, siempre tenemos un as bajo la manga!

Pedro's Robot Factory

La Historia

Pedro es un hombre modesto. Un día, leyó un libro escrito por Isaac Asimov y empezó a soñar con robots (Robot Dreams). Tiempo más tarde, Pedro invirtió su dinero en una fábrica de robots llamada Pedro's Robot Factory (por su puesto) y vos sos su robotcista (Sorry). Pedro desarrrolló el modelo "Cabeza de embudo" (Funnelhead)... y vos debés construirlo. Pedro es un jefe demandante y nivel tras nivel, mientras la empresa progresa, deberás ser más rápido.

Qué lo disfrutes!

Cómo jugar

Ayudá a Pedro a construir sus robots!

1. click izquierdo para agarrar o soltar piezas.
2. Scrol para arriba y para abajo o las teclas A/D para rotar la pieza agarrada.
3. Tecla P para pausar el juego.
4. Tecla F para pasar a modo fullscreen.
5. Las piezas especiales te dan puntos extra!

Trivia:

1. También podés usar las teclas A y Z para rotar la pieza agarrada, o la barra espaciadora.
2. Hay un huevo de pascua en el nivel 2.
3. Si completás los tres niveles podrás ver el Happy Dance :)

Paquetes

En GNU/Linux simplemente bajá http://media.pyweek.org/dl/6/pysfe/robotfactory-1.zip y con Python y PyGame instalado ejecutá run_game.py

En Windows podés hacer lo mismo que en GNU/Linux o bajar un paquete autocontenido con el juego, Python y las librerías necesarias: http://pyweek6.googlecode.com/files/robotfactory-sc-win.zip

Screenshots

Nivel 2 del juego en Windows Vista. Ejecutado desde el paquete autocontenido.

Mi rostro adornando el menú del juego.

En el nivel 1 vemos a un pedro engrasado y desaliñeado. Ubuntu.

En el segundo nivel Pedro empieza a vestirse mejor. Para ver el tercer nivel vas a tener que jugar un rato :)

Ayer recibí por email:

Nos alegra comunicarle que Twisted Zombie ha sido incluido en el listado de programas de uptodown.com.

Nuestros editores prueban y redactan un detallado análisis de cada aplicación, publicando aquellas que consideramos relevantes y a las que procuramos una adecuada visibilidad con un tráfico segmentado de más de 300.000 usuarios únicos día.

Si entran a este sitio web se puede leer:

Eras un muerto feliz, pero un mago oscuro te sacó de tu letargo y te convirtió en zombie para pasar a engrosar su ejército de muertos vivientes. Sin embargo, uno de sus aprendices decidió devolverte a tu tumba para no ser utilizado con fines malignos. Ésto ha generado un conflicto entre ellos, y ahora tú intentarás sacar partido de todo esto para volver a la vida. Ésta es la historia de Twisted Zombie, un juego arcade donde tendremos una curiosa manera de avanzar entre niveles. Nuestra misión es acoplarnos a los moldes que nos encontremos a lo largo del nivel. Nos encontraremos también varias pociones según avancemos. Las rojas nos quitarán vida. El resto... tendrás que descubrirlo tú mismo. Si quieres pasar un buen rato con un juego como los de antes, te gustará probar Twisted Zombie.

Un aplauso para el Zombie!

 

Una tarde estábamos jugando a este juego en su tablero y me dieron ganas de jugarlo en la compu también. Una búsqueda rápida no nos arrojó resultados y decidí programarlo para practicar mi PyGame. La idea fue no terminar con algo muy complejo, sino más bien simple que pueda programarlo rápido y que sirva también como ejemplo de uso de esta librería.

El juego es un juego lógico: hay que pensar para poder ganar ;-).

Para jugarlo pueden obtener la última versión desde el svn:

svn co http://svn.juanjoconti.com.ar/code/ SecretCode

A pedido de Lucio de PyAr dejo unas capturas de pantalla, espero que alcancen para entender el juego. Si no se entiende, podemos usar los comentarios de este post para aclarar dudas :).

Menú

Las reglas

Jugando

Una jugada ganadora

Créditos

Twisted Zombie, el juego que desarrollamos en una semana para la quinta edición del concurso PyWeek ya funciona en Windows. Está escrito en Python, un lenguaje multiplataforma, y hemos tenido en cuenta algunas consideraciones para que funcione sin problemas en distintos sistemas operativos. Incluso lo hemos probado en un par.

Pero para usarlo en Windows necesitás tener instalado Python y Pygame.

El siguiente es un paquete con todo lo necesario para correr el juego si necesidad de instalar nada más: Twisted-Zombie-1-Win.zip

Este es el código fuente del archivo setup.py que utilicé para crear el paquete:

# setup.py es usado para generar un paquete autocontenido

# para Windows. Incluye el interprete de Python, PyGame

# y otros modulos utilizados en el juego.

# Uso: C:Python25python.exe stup.py py2exe

# Version de py2exe: 0.66

# Nota: en run_game.pyw cambiar os.path.dirname(__file__)

# por la ruta al directorio donde esten los fuentes del

# juego. Ej: 'C:tz'



from distutils.core import setup

import py2exe

import os



options = {

    "py2exe": {

        #"compressed": 1,

        #"optimize": 2,

        #"excludes": excludes,

        "includes": ["pygame", "pygame.locals", "random", "pickle"],

    }

}



data_files = [ (x, [os.path.join(x, e) for e in z]) for d in ("lib", "data")

               for x,y,z in os.walk(d) if not ".svn" in x ] + [ "README.txt"]



setup( console=["run_game.pyw"], data_files=data_files, options=options)

N-Puzzle sigue sin tener una real inteligencia, pero hice una modificación que lo hace verse un poco más inteligente:

Si un jugador o el desordenador aleatorio hace movimientos que se cancelan entre sí

<li>Izquierda - Derecha</li>

<li>Izquierda - Izquierda - Derecha - Derecha</li>

<li>Izquierda - Izquierda - Arriba - Arriba - Derecha - Izquierda - Abajo - Abajo - Derecha - Derecha</li>

el siguiente algoritmo es capás de eliminarlos de la lista de acciones y así lograr una resolución en menos movimientos y que parezca menos tonta.

El método que encapsula al algoritmo en cuestión es llamado cada vez que se entra al modo Auto Solve:

    def _reduce_actions(self):

        '''This method try to reduce the actions' log

        removing repeted moves.'''



        log = self.actions_log

        stack = []



        while log:



            a = log.pop()

            ia = self._inverse_action(a)



            if stack:

                s = stack.pop()

                if ia != s:

                    stack += [s, a]

            else:

                stack += [a]



            print "Stack: ", len(stack)

            print "Log: ", len(log)



        stack.reverse()

        self.actions_log = stack

Download last version: n-puzzle-0.1-2

Hace unos días mandé a la lista de correos de PyAr una implementación inicial del juego N-Puzzle. n-puzzle-0.1.tgz.

Es muy sencilla. Toma una imagen, la parte en cuadraditos, quita uno de los cuadraditos y los mezcla. Luego uno puedo deslizar los cuadraditos adyasentes al espacio en blanco con las flechas de teclado. El objetivo del juego es recomponer la imagen original.

Hoy estuve mejorando el código y agregándole una funcionalidad que permite que la computadora resuelva el problema (o nos ayude a hacerlo).La idea original para este programa es luego utilizarlo para probar los métodos de búsqueda que estamos estudiando en Inteligencia Artificial.

Ojo! Si bien en esta nueva versión apretando la tecla 'S' entramos y salimos del modo Auto Solve, no estoy usando IA para implementarlo. Siempre pueden mirar el código y ver como lo estoy haciendo :)

Actualmente el juego está planteado como una prueba de concepto más que como un programa totalmente usable. Esto implica que pueden ocurrir errores durante su ejecución y que algunas opciones que podrían ser configurables están clavadas en el código:

• N es el número de fichas que participan del juego: 8 (en un tablero de 3 x 3), 15 (en uno de 4 x 4), 24 (en uno de 5 x 5). Por defecto es 8 pero puede cambiarse en el archivo run.py.
• La imagen que se usará para generar las fichas se llama ejemplo.jpg y debe estar en el mismo directorio que los scripts (yo proveo una). Pueden pisarla con otra imagen o pueden cambiar la ruta a la misma en el archivo run.py. La imagen debe ser de 600 x 600 pixeles.
• El desordenamiento original del tablero se efectua mediante un número X de movimientos. En el código fuente el valor usado es 20 pero puede cambiarse en el método __init__ de la clase Puzzle en el archivo puzzle.py (van a encontrarlo en la llamada al método _shuffle).

El puzzle resuelto se ve así:

La última versión puede encontrarse en: files/python/n-puzzle-0.1-1.tgz.Y este es el CHANGELOG de mi primer intento a este segundo mejorado:

0.1-1: mix(x,y) se realiza ahroa como x,y = y,x en lugar de usar una variable temporal. Cada Card tiene un cid (Card ID), un par i,j correspondiente a su posición original en el tablero. El desordenado del tablero se realiza mediante el movimiento aleatorio de las piezas (usando los métodos up, down, right y left) para evitar que el juego comience con una configuración que no tiene solución (Para un ejemplo, Google: 14-15 Puzzle). Apretando la tecla 'S' se entra y sale del modo 'Auto Solve' en el cual la computadora nos ayuda a resolver el juego. Atención: NO IA was used in this feature.

Requiere Python y PyGame. Si tienen problemas para instalarlos mandenme un mail y los ayudo.