Jon Ureña's Blog, page 76

Experimento sobre búsqueda de ruta en 3D y para personajes con diferentes reglas de movimiento

Pretendo programar un juego de construcción de colonias similar a Dwarf Fortress. Desde el principio supe que debía arreglármelas primero para que el sistema calculara las rutas de los agentes de manera fiable, aprovechando los diferentes hilos del procesador, y que generara rutas adecuadas para agentes que pudieran andar, volar, nadar en aguas poco profundas, en aguas profundas, o una combinación de cualquiera de esas posibilidades.

Hace un par de semanas programé una versión sólida de un generador de mapas locales basado en el ruido Perlin. El vídeo recoge el resultado. Ninguna inteligencia artificial involucrada: el personaje lo muevo yo con el teclado numérico.

Sin embargo, tras varios experimentos en los que yo no tenía claro desde un principio cómo proceder, la arquitectura se había vuelto engorrosa. Dediqué varios días a refactorizar la mayoría del código e implementar nuevas clases que representaban abstracciones que antes ni siquiera existían. El bucle actual consiste en lo siguiente:

Una clase llamada Inputs gestiona si el usuario ha presionado alguna tecla, ha movido el ratón o pulsado alguno de sus botones. El sistema ejecuta las funciones dependiendo de las relaciones escritas en un archivo json.[image error]
Una clase llamada Display encapsula todo lo relacionado con dibujar los elementos en la pantalla. Aparte de que aislar esas responsabilidades mejora la arquitectura, ya empezaba a ver que pygame se quedaba corto incluso para dibujar el mapa a una velocidad consistente. Pronto deberé averiguar si puedo sustituir todas las referencias a pygame con llamadas a OpenGL.[image error]
Si el usuario pulsa la tecla punto, se simula un turno. Sabía desde un principio que para programar una simulación compleja tendría que aislarla y limitar la cantidad de veces que se ejecutaría en un segundo, aunque la simulación acabara aprovechando los diferentes núcleos del procesador.
Durante la simulación de un turno, una clase Messenger, encargada de publicar mensajes a su subscriptores, envía el mensaje de update para que todas las clases que deban hacerlo ejecuten su lógica de actualización. Para encapsular este comportamiento tuve que reestructurar por completo cómo representaba una entidad en el programa. Aunque ya conocía la tendencia moderna de representar entidades mediante componentes en vez de como jerarquías de herencias, consideré que para los experimentos simples del principio bastaba con heredar de clases simples como Actor y Personaje. Había programado las casillas del mapa como entidades aparte, pero la necesidad de todos esos objetos de actualizarse y mostrarse en la pantalla evidenciaba que necesitaba reducir la idea de cada entidad a un identificador (en este caso, un UUID), y que una multitud de componentes independientes se encargaran de su funcionalidad. Programé el sistema para que bastara con definir los componentes de cada entidad en un archivo de texto json. Una serie de constructores y factorías compondrían una entidad cuando fuera necesario.

[image error]

Una clase llamada ComponentManager se encarga de archivar la relación de identificador y componente en un diccionario. Permite recuperar cualquier componente existente de un identificador concreto sin involucrar al resto de componentes.

[image error]

Una clase de componentes que reciben el mensaje para actualizarse son los Behavior trees, o árboles de comportamiento. La inteligencia artificial para los agentes modernos se ha reducido a estos árboles o a planning systems (sistemas de planificado), sobre los que no he leído todavía. Pero los árboles de comportamiento encajan de maravilla con la neuroevolución. Algunos de los nodos de un árbol de comportamiento se limitan a decidir qué comportamiento se ejecutará, así que bastaría con crear nodos específicos que cumplieran esa función mediante redes neurales evolucionadas. Los árboles de comportamiento son enrevesados, y a pesar de su aparente simplicidad, decidir su estructura para que reflejen el comportamiento exacto que quieres puede complicarse bastante. Para empezar, decidí que bastara con definir un comportamiento aislado en un archivo json. Una serie de constructores y factorías crearía la red final de objetos. La siguiente es la definición de la inteligencia artificial completa que permite a cada uno de los agentes del siguiente vídeo moverse:

[image error]

Refleja el siguiente esquema:

[image error]

La mayoría de los libros y artículos sobre árboles de comportamiento recomiendan reducir su composición a los selectores básicos: sequencias y fallbacks (o selectores clásicos), aparte de decoradores. La sequencia funciona de la siguiente manera: si el primer hijo falla, la sequencia entera falla y envía el fallo al nivel superior. Si todos sus hijos devuelven que han satisfecho su tarea, la sequencia se considera satisfecha. Los fallback funcionan al revés: si un hijo falla, se prueba el siguiente. Si todos fallan, el fallback falla, pero si alguno de los hijos ha satisfecho su tarea, el fallback se considera satisfecho. Aunque me devané los sesos para componer el árbol de manera que no necesitara repetir ningún nodo, no lo conseguí. Como el diagrama refleja, la lógica considera dos veces si el agente ha terminado de calcular su ruta, y otras dos veces si puede moverse al siguiente punto de la ruta. Pero funciona como está.
Este comportamiento tiene poco de inteligente, claro. Sólo refleja una secuencia lógica de acciones para pedir un cálculo de ruta, asegurarse de que haya terminado de calcularse, consumirla y determinar si el agente ha alcanzado su destino. Pero la estructura está dispuesta para implementar comportamientos mucho más complicados.
En un principio pretendí ejecutar los árboles de comportamiento en diferentes hilos o procesos, para aliviar el núcleo principal del procesador. Sin embargo, Python es muy peculiar a la hora de tratar los hilos, y para ejecutar cada árbol de comportamiento en un núcleo diferente, el sistema copiaría todo el árbol y las clases involucradas. Si la estructura se limitara a la lógica, no habría mucho problema, pero muchos de esos nodos deben preguntar cosas a diferentes componentes de la entidad, lo que implica tener que copiar el diccionario entero de comportamientos. Podría arreglármelas para aislarlo, pero en el futuro es de esperar que alguno de los nodos debiera mirar dentro del mapa, lo que implicaría copiar el mapa entero a otro proceso. Demasiado pronto para decidirme.
Lo que sí implementé fue separar la idea de razonar de la de ejecutar el razonamiento. Los árboles de comportamiento sólo devuelven tareas a ejecutar, y no se encargan de modificar el mundo ni los actores. Cada turno, otra clase dedicada a almacenar tareas y procesarlas las ejecuta como considere oportuno, ya sea en el mismo núcleo o en los hilos disponibles. En el futuro también debería ejecutar tareas en otros procesadores.

[image error]

Mencionaré que aunque había implementado el algoritmo A* de búsqueda de ruta hace unas semanas, no encontré la manera de incorporar las reglas de movimiento en él, así que tuve que programarlo otra vez desde cero siguiendo otro ejemplo. Pero la versión actual es mucho mejor, y refleja las reglas de movimiento perfectamente.
De momento sólo ejecuta fuera del hilo principal los cálculos de ruta, y únicamente en los hilos disponibles. Mis primeros intentos por implementar mediante el multiproceso la búsqueda de ruta fueron descorazonadores: tardaba al menos tres o cuatro segundos en devolver incluso las rutas vacías. No acababa de verle el sentido, pero se debía a que no entendía la diferencia entre hilos y procesos. Los hilos existen en un proceso y usan el mismo espacio de memoria. Pueden acceder a los datos. Si uno de ellos escribe un dato mientras otro hilo intenta leerlo, se producirán inconsistencias, pero para evitar ese problema basta con dividir la ejecución interna de los efectos externos. Sin embargo, yo mandaba calcular la ruta mediante un pool de procesos, para lo que el ordenador debía iniciar el Python en otro núcleo del procesador y copiar todos los datos involucrados. Ahora resulta evidente que sólo las tareas que puedan permitirse tardar varios segundos en devolver un resultado se benefician del multiproceso, pero de todas formas son muchas: por ejemplo, si se quiere procesar la temperatura, la presión del aire, etc., de cada casilla del mapa, o calcular un mapa de amenazas o de visibilidad, o procesar qué pasa en el mundo en general mientras el juego transcurre en el mapa local. En el futuro imagino que podría aprovechar el octree del mapa, que distribuye a los agentes según su cercanía, para ejecutar la inteligencia de los agentes cercanos en hilos, pero procesar la de los demás en otros procesadores.
Algunas tareas producen comandos: acciones que modifican a algunos agentes y/o el mapa. En este caso producen la acción de moverse al siguiente punto de su ruta. Como se verá en el vídeo, también gestiona si el siguiente punto de la ruta está bloqueado por otro agente, y en ese caso permitirá volver a buscar una ruta otro par de veces antes de renunciar a ese destino. Una clase se encarga de procesar la cola de comandos ejecutándolos uno tras otro.

El experimento tenía una complejidad añadida: yo quería que convivieran agentes que andaran por el suelo con otros que volaran, nadaran en aguas poco profundas, en profundas, etc. En vistas al futuro, el sistema debería permitir añadir comportamientos como por ejemplo los de un agente que se moviera abriendo túneles en los bloques sólidos de roca, o que nadara en lava. Además, esas capacidades de movimiento deberían poder combinarse: algunos agentes deberían poder volar, nadar y además abrir túneles en roca, por ejemplo. Para ello tuve que abstraer las reglas de movimiento a archivos json.

[image error]

La búsqueda de ruta necesitaba conocer las posibles casillas vecinas de cada casilla que consideraba. La accesibilidad de cada casilla dependía del agente que pedía la ruta, así que en un primer momento no se me ocurría otra cosa que calcular los vecinos cada vez que se pedía calcular una ruta. Eso ralentizaba mucho la búsqueda, obviamente. Al final opté por generar cada posible vecino en un diccionario interno del mapa, poco después de generarse al comienzo del experimento. Eso tarda unos ocho segundos, pero no necesitará volver a hacerlo durante el transcurso del experimento o del juego salvo que alguna casilla cambie, y aun así sólo deberán recalcularse los vecinos inmediatos de la casilla que haya cambiado. Esa tarea se puede delegar a un hilo aparte.

Sin embargo, la lógica que genera los vecinos de cada casilla es de lo más complicado que he programado recientemente:

[image error]

El resultado se ve en el siguiente vídeo. Hay cuatro tipos diferentes de agentes. Unos andan, y sólo pueden moverse por la tierra (aunque podría incluir sin problemas que nadaran en aguas poco profundas). Otros vuelan, lo que implica que pueden moverse por el aire y por la tierra. Otro agente sólo nada por aguas poco profundas. El último agente nada por aguas poco profundas y por las profundas.

Cuando todo funcionaba ya, he cambiado un par de detalles de la implementación. La búsqueda de ruta se ejecuta en hilos; aunque los hilos funcionan de manera semiindependiente, si a una búsqueda le costaba encontrar el camino, bloqueaba el sistema durante un segundo o algo más. Las búsquedas normales consideran unas veinte, treinta o cincuenta casillas. Algunas raras superan las cien. Pero esas búsquedas que bloqueaban el sistema consideraban hasta mil quinientas o más. Acabé limitando artificialmente la consideración de casillas a unas trescientas. Como resultado, algunos agentes no se moverán a ese destino, pero en el transcurso de un juego podría considerarse razonable: el destino es demasiado complicado como para alcanzarlo desde su punto de origen. La inteligencia artificial lo tendría en cuenta y lo derivaría a otras acciones.

Después de esto me toca refactorizar un poco más el sistema para integrar a la arquitectura los bloques más sólidos del experimento, y luego investigaré cómo trabaja Python con OpenGL y si es factible reemplazar pygame por completo.

Implementation of pathfinding with Z levels

The following video shows an actor moving through the different levels of depth of a simple map, and then going for a while to random coordinates on the first level:

Although the actor reaches the objective, for now I haven’t managed to prevent that in two particular moments the actor decides to go through the roof as part of his route, although I had modified the code so it wouldn’t allow him to do so, at least in theory. But it’s a minor problem for what I intended implementing the pathfinding: that when I programmed new experiments in which the user moved his character, around him other actors would find their way and act according to their AI.

Movement in three dimensions tends to divide these kinds of games. Dwarf Fortress is famous in part for how it handles the different layers, allowing the user to strike the earth for a couple dozen levels to build his fortress, or raise it several levels above sea level if he wants to. On the other hand, Rimworld, programmed with Unity, sacrifices that verticality to offer better graphics and effects and a complexity limited in comparison. I was convinced that simple sprites were enough in exchange of a complex simulation and an artificial intelligence that would, hopefully, surprise often. And behave reasonably to begin with.

I programmed this experiment a few days ago, but I recall spending a couple hours trying to solve a problem. When the actor had to find his route to the inside of the house, which should force him to pass through the doorway, the actor went straight to the western wall of the house, his image passed through and stopped in the final coordinates. I was making sure that the pathfinding algorithm identified the wall as impassable, but the actor was still going through it. In the end, after a lot of testing, I revised my assumptions. Were the actor sprites being displayed according to the level they were in? Turns out I had let that for later, and the pathfinding was doing its job: instead of going through the wall, the actor jumped it and “crashed” through the roof to reach his objective. The function that had to draw the actor showed him indistinctly going through a wall that in reality existed a level below.

After that, to make sure the pathfinding algorithm worked better in three dimensions, I had to add more booleans to the tiles. Apart from whether or not they blocked the straight path, they should mark whether they blocked going upwards or downwards (days later I wrote a couple of booleans more: whether the tile blocked the path straight up and down). Otherwise the actor would go through several layers of underground tiles to reach a basement. The changes worked for the most part, shown in the video where the actor goes down the stairs to reach the basement.

To draw the different layers of depth I paid attention to how Dwarf Fortress did it. When the user went up a z level, if any tile was defined as “empty”, the program should draw the closest “real” tile below, but tinted blue to show the user that he was seeing tiles belonging to another z level. On my first try, the code copied each of those sprites and modified its RGB component according to how close they were to the current z level. That’s shown in the video. However, copying all those sprites every frame hurt the framerate too much. A couple of days later I opted for something simpler and that even works better: I draw the first “real” tile normally, but over it I draw translucent tiles for each z level in between. The translucent tiles stack up, darkening the tile below.

This experiment worked for what I intended, so I moved on to new ones.

Implementación de búsqueda de ruta con niveles de profundidad

El siguiente vídeo muestra a un actor moviéndose por los diferentes niveles de profundidad de un mapa simple, y luego dirigiéndose por un rato a puntos aleatorios del primer nivel:

Aunque el actor alcanza su objetivo, no conseguí de momento evitar que en dos puntos concretos decidiera atravesar el techo como parte de su ruta, a pesar de que yo había modificado el código para que en teoría lo evitara. Pero se trata de un problema menor para lo que pretendía implementando la búsqueda de ruta: que en otros experimentos en el que el usuario moviera a su personaje, a su alrededor hubiera actores moviéndose y actuando en base a su inteligencia artificial.

El movimiento en tres dimensiones suele dividir este tipo de juegos. Dwarf Fortress es famoso en parte por cómo gestiona las diferentes capas, permitiendo profundizar en la tierra durante un par de decenas de niveles para construir tu fortaleza, o elevándola varios niveles sobre el nivel del mar si se quiere. En contra, Rimworld, programado con Unity, sacrifica esa verticalidad para ofrecer mejores gráficos y una complejidad muy limitada en comparación con Dwarf Fortress. Yo tenía claro que los sprites en dos dimensiones bastaban a cambio de ofrecer un juego con una simulación compleja y una inteligencia artificial que, con suerte, sorprenda a menudo. Y que actúe de una manera razonable en un primer lugar.

Programé este experimento hace unos pocos días, pero recuerdo que dediqué un par de horas intentando solucionar un problema. Cuando el actor debía encontrar su ruta hasta el interior de la casa, lo que debería obligarlo a pasar por la puerta, dado que se trata de una única entrada despejada, el actor se dirigía al muro occidental de la casa, su imagen pasaba a través del muro y acababa la ruta en su objetivo. Yo me aseguraba de que el algoritmo de búsqueda de ruta identificaba el muro como impasable, pero a pesar de ello lo pasaba. Al final, después de mucho probar, revisé lo que yo había asumido sobre la escena: ¿de verdad los gráficos dibujaban al actor en el nivel de altitud en el que está de verdad? Resultó que había dejado eso para otro momento, y la búsqueda de ruta hacía su trabajo: en vez de atravesar el muro, lo subía y luego atravesaba el techo para llegar a su objetivo. La función que dibuja la escena reflejaba al actor de manera indistinta atravesando el muro que en realidad se encontraba en un nivel por debajo.

A raíz de eso, y de manera previsible, para que el algoritmo de búsqueda de ruta funcionara mejor en tres dimensiones tuve que añadir otros booleanos a cada terreno. Aparte de si bloqueaban el paso a través, debían marcar si bloqueaban subir a un nivel superior, para que a un actor no le diera por elevarse por el cielo, y también debían marcar si bloqueaban lo contrario, bajar a un nivel inferior, para que no atravesaran varias capas de tierra subterránea para llegar a un sótano. La modificación acabó funcionando en su mayor parte, lo que se ve en el vídeo cuando el actor baja por la escalera para alcanzar el sótano.

Para dibujar las diferentes capas de altitud me fijé en cómo lo hacía Dwarf Fortress. Cuando el usuario sube la vista a un nivel superior, si alguna casilla está vacía, el programa debería dibujar lo que está por debajo, pero tintado de otra manera para que no le parezca al usuario que está viendo elementos en la misma dimensión. En un primer lugar el código copiaba cada una de esas casillas inferiores y las tintaba con más o menos azul en función de lo lejos del nivel actual que se encontraban. Eso se ve en el vídeo. Sin embargo, reducía los fotogramas por segundo de una manera bestial. Un par de días después opté por algo más simple y que además funciona mejor: dibujo la casilla original de manera normal, pero luego voy dibujando casillas traslúcidas por cada nivel de altitud que lo separe de la vista. Las transparencias se acumulan y oscurecen la casilla inferior.

El algoritmo me sirve de momento como ha quedado, así que paso a otros experimentos.

(Iteration #2) Simple experiment about neuroevolution

After changing some elements of the experiment, I got the actors behaving in a way closer to what I wanted:

I reestructured the inputs, the sensorial information, that each of the neural networks received. I thought that including so many values that only held the information about where some fruit was located, even if they included the notion of the cardinal direction where it was, destroyed the balance with the rest of the inputs. So I reduced them to the following:

A normalized value, from 0.0 to 1.0, that represents each turtle’s health
A normalized value, from 0.0 to 1.0, that represents how close is the closest fruit
A value of 1.0 if a turtle has another one right next, and 0.0 otherwise

Although I couldn’t think of an obvious way the final input would affect the behavior, it was information present in the simulation, and part of a neural network’s job consists in not using the information that doesn’t help it achieve its objective.

I also added an output: if it received the maximum value, the actor would walk a tile in a random direction. As the video shows, in a few generations those turtles that received the highest values for that single output ended up reproducing more, because moving through the map got them closer to the fruit. They dominated so much that I reduced the amount of fruit present at any given moment, to make sure they weren’t just walking over it randomly. Many of the members of many generations gravitate towards the fruit; after all, the inputs include a measure of how close the closest piece is. I don’t know if the information of whether each turtle had another one right next to them affected anything.

The experiment went well enough for me, and I moved on to more interesting ones.

(Iteración 2) Experimento simple sobre la neuroevolución (NEAT-Python)

Tras cambiar varios elementos del experimento he conseguido un comportamiento de los actores cercano a lo que quería:

Reestructuré los inputs, la información sensorial, que cada una de las redes neurales recibía. Me pareció que incluir tantos valores que sólo recogían información sobre la localización de alguna fruta, aunque incluyera el sentido de en qué dirección cardinal se encontraba, destrozaba el balance con el resto de los inputs. Ahora recibe los siguientes:

Un valor normalizado, de 0.0 a 1.0, que representa la salud de cada tortuga
Un valor normalizado, de 0.0 a 1.0, de lo cerca que se encuentra la fruta más próxima
Un valor de 1.0 si alguna tortuga se encuentra a su lado, 0.0 en caso contrario

Aunque el último input en principio no afectaría de una manera obvia al resultado, se trataba de información presente en la simulación, y el trabajo de una red neural también consiste en no usar información que no la ayude de verdad a conseguir su objetivo.

También añadí un output: si esa salida recibía el valor máximo, el actor daría un paso en una dirección aleatoria. Como se ve en el vídeo, en pocas generaciones esas tortugas que procesaban valores altos para ese único output acabaron reproduciéndose más, ya que moverse por el mapa los acercaba a la fruta presente. Triunfaron tanto, de hecho, que limité la cantidad de fruta para asegurarme de que no topaban con ella por error. En muchas generaciones se ve cómo la mayoría de los agentes gravitan hacia la fruta; a fin de cuentas, los inputs incluyen una medida de lo cerca que se encuentran a la más próxima. No sé si la presencia de otra tortuga junto a otra ha afectado algo.

Considero que el experimento ha salido bien, y he pasado a otros experimentos más interesantes.

Simple experiment about neuroevolution (NEAT-Python)

The next video, that shows about 166 generations of the evolving neural networks, clarifies the situation enough so I can explain myself later:

I’m interested in programming above all because of artificial intelligence and videogames. Although I consider myself a writer first, another one of my dreams, shared with many programmers of modern videogames, consists on making a game with the best of Dwarf Fortress, but with the more immediate and exploratory aspects of games like Cataclysm: Dark Days Ahead. Rimworld’s ambience comes somewhat close to what I would want, but I’d prefer a complexity closer to that of Dwarf Fortress, with most of its elements depending on procedural generation, and supported with an artificial intelligence based on neural networks that would offer constants surprises.

To prove to myself that I could program the visual aspect of a similar game and set the basis for developing the intelligence of its actors, I intended to develop the prototype shown in the video. For now I’ve failed in generating the behaviors that I wanted for the involved neural networks, but having reached this point allows me to progress quickly.

For those who don’t know it, and according to the story as I remember it, neural networks were considered the Holy Grail of artificial intelligence in the eighties and early nineties, but they crashed against an unsolvable problem: no mathematical model could determine which was the best architecture to use for a network to solve a particular problem. They depended on trial and error, and eventually neural networks ended up relegated to obscurity for the most theory-minded and a minority of dedicated programmers.

But in 2002, Kenneth Stanley, from Texas university in Austin, wrote the following paper:

Evolving Neural Networks through Augmenting Topologies

The paper, and those that followed it, revealed the way to solve the main issue with neural networks: instead of designing its architecture, it should evolve through a genetic algorithm. A significant part of the revolution in artificial intelligence we are living in has its origin in papers like this one and others from that era.

The prototype I intended to build had to implement the the following elements:

The visual aspect of games like Dwarf Fortress (with tilesets) and Cataclysm: Dark Days Ahead.
A reusable architecture that would allow adding new features and programming other experiments easily
It would implement the neuroevolution using some library based on NEAT
The neural networks should evolve a behavior close to what I intended

Visual representation of a neural network:

[image error]

A neuroevolution tends to begin with only the input and output layers set. The inputs represent the sensorial information that a neural network would process, and the outputs the answers that the internal architecture generates through the interaction of all the nodes.

The success of this method depends mainly on the following factors: the inputs must feed the network with the relevant information that could end up producing the intended behavior, and the inputs should be normalized (should be scaled to a range of 0.0 to 1.0). For my experiment I settled on the following inputs:

The normalized value of each turtle’s health
A value of 1.0 if the animal detects a fruit close enough in the northwest, but 0.0 otherwise.
Same but in the north
Same but in the northeast
Same but in the east
Same but in the southeast
Same but in the south
Same but in the southwest
Same but in the west

I decided that each actor would act depending on which output had produced the highest value, and according to its index, the actor would walk a tile over to one of the cardinal directions or it would stay in place.

I chose those inputs because I considered that an actor should learn to link his health deteriorating quickly to the need to search for food, and the actor should detect the fruits instead of stumbling in the dark.

Apart from the architecture of the network, the other key is the function that determines each neural network’s fitness. The fitness is a mathematical measure of how close the network has gotten to the goal. Usually it consists in reaching a high number. In my case I settled for the following function:

((Health ^ 2) + (AmountOfFruitsEaten * 50) + (TurnsSpentNearFood * 2)

I wanted to reward the actors that kept their health as high as possible, and as secundary measures I wanted to suggest that they should look for food and keep close. I’m terrible at math and I’m doing this alone, so suggestions are welcome.

For now the experiment hasn’t produced the behaviors I intended. I’ll leave it some night so it can reach a thousand or thousands of generations, but at least I’m happy that it’s built upon a platform that could allow me to move towards programming something close to an interesting videogame or simulation.

UPDATE: I’ve changed some aspects of the experiments and gotten results close enough to what I intended. I’ll write another post showing them.

Experimento simple sobre la neuroevolución (NEAT-Python)

El siguiente vídeo, que recoge unas 166 generaciones de las redes neurales que evolucionaban, ilustra la situación lo suficiente como para que me explique después:

Me interesa la programación sobre todo por la inteligencia artificial y los videojuegos. Aunque me considero primero un escritor, otro de mis sueños, compartido con muchísimos programadores de videojuegos modernos, era crear un juego que recogiera lo mejor de Dwarf Fortress, pero con los aspectos más inmediatos y exploratorios de juegos como Cataclysm: Dark Days Ahead. La ambientación de Rimworld recoge parte de la idea, pero yo querría una complejidad mucho más cercana a Dwarf Fortress, con la mayor cantidad de elementos basados en la generación procedural, y una inteligencia artificial fundada en las redes neurales que ofreciera sorpresas constantes.

Para probar a mí mismo que podría programar el aspecto visual de un juego semejante y establecer la base para desarrollar las inteligencias de sus actores, pretendí desarrollar el prototipo que se muestra en el vídeo. De momento he fracasado en generar los comportamientos que pretendía para las redes neurales involucradas, pero haber llegado hasta este punto me permite progresar deprisa.

Para quienes lo desconozcan, y de acuerdo con la historia tal como la recuerdo, las redes neurales se consideraban el Santo Grial de la inteligencia artificial en los años ochenta y principios de los noventa, pero se toparon con un problema insalvable entonces: no existía ningún modelo matemático que determinara cuál era la mejor arquitectura de cada red neural para resolver los problemas concretos. Que dependieran del ensayo y error acabó relegando las redes neurales a los ámbitos más teóricos o a una minoría de programadores dedicados.

Pero en 2002, Kenneth Stanley, de la universidad de Texas en Austin, sacó este artículo académico:

Evolving Neural Networks through Augmenting Topologies

El artículo, y los que se sucedieron, revelaron la manera de solventar el problema principal de las redes neurales: en vez de diseñar su arquitectura, debería evolucionar mediante un algoritmo genético. Una parte significativa de la revolución en inteligencia artificial que vivimos durante estos días tiene su origen en este artículo y en otros de esa época.

El prototipo que yo pretendía construir debía implementar los siguientes elementos:

El aspecto visual de juegos como Dwarf Fortress (con tilesets) y Cataclysm: Dark Days Ahead
Una arquitectura reusable para que tanto añadir nuevos elementos como programar experimentos adicionales fuera razonablemente fácil
Implementar la neuroevolución con alguna librería de NEAT
Que las redes neurales evolucionaran un comportamiento cercano a lo que quería

Representación visual de una red neural:

[image error]

La neuroevolución suele empezar sólo con la capa de inputs y la de outputs. Los inputs representan la información sensorial que una red neural recogería, y el output la respuesta que la arquitectura interna genera mediante la interacción de todos los nodos.

Con respecto a la arquitectura, que una neuroevolución funcione bien depende en gran medida de los siguientes factores: que los inputs recojan la información relevante para generar los comportamientos queridos y que estén bien normalizados (reducirlos proporcionalmente a rangos como de 0.0 a 1.0). Para mi experimento decidí los siguientes inputs:

El valor normalizado de la salud de esa tortuga.
Valor de 1.0 si ve una fruta en el noroeste (en las cuatro casillas más cercanas), 0.0 en caso contrario
Lo mismo pero en el norte
Lo mismo pero en el noreste
Lo mismo pero en el este
Lo mismo pero en el sureste
Lo mismo pero en el sur
Lo mismo pero en el suroeste
Lo mismo pero en el oeste

Decidí que cada actor actuaría en función de qué output había recibido el valor más alto, y dependiendo de cuál se tratara, avanzaría una casilla en una dirección cardinal o se quedaría quieto.

Opté por esos inputs porque consideré que un actor debería aprender a relacionar que su salud se deterioraba rápidamente con la necesidad de buscar comida, y necesitaba poder detectar las frutas para que topar con ellas no fuera una coincidencia.

Aparte de la arquitectura de la red neural, la otra pieza fundamental es la función que determina el fitness de cada red neural. El fitness consiste en un valor que calcula matemáticamente cuánto se ha acercado a cumplir la meta. Por lo general suele consistir en intentar alcanzar un valor alto. En mi caso me decidí por la siguiente función:

((Salud) ^ 2) + (CantidadDeFrutasComidas * 50) + (TurnosPasadosCercaDeFruta * 2)

Quería premiar a los actores que mantuvieran la salud lo más llena posible, pero también pretendía sugerir que debían buscar comida activamente y no alejarse demasiado de ella. Soy pésimo con las matemáticas y programo solo, así que se admiten sugerencias.

De momento el experimento no ha sacado los comportamientos que quería. Lo dejaré alguna noche para que cumpla mil o miles de generaciones, pero al menos me alegra que se sostenga sobre una plataforma que me permitirá avanzar hacia programar algo cercano a un videojuego interesante.

Reseña: Welcome to the N.H.K., Volumen 4, de Tatsuhiko Takimoto

Este volumen diverge del anime de una manera fundamental. Para aquellos de nosotros que vimos esa versión primero, preparó un giro argumental que no he visto venir.

Misaki, la “terapeuta” del protagonista, se ha enfadado con Satou por ignorarla después de que ella lo hubiera atado a una silla y se hubiese olvidado de él durante una semana. Peor: cuando ella reúne el coraje para acercarse a él, Satou está ocupado hablando con su senpai del instituto, Hitomi, que había venido a disculparse por haberle ofrecido pasar la noche juntos en un love hotel aunque ella se casaría pronto. Misaki, celosa, huye. Ahora llega el momento en el que las diferencias entre ambas versiones de la historia afectan más a la trama.

En el manga, Misaki nunca fue a la isla para evitar que Satou se suicidara. Para él la chica es alguien con algún tornillo suelto, que insiste en entrometerse en su vida y decirle qué hacer, y que ha llegado al extremo de olvidarlo atado a una silla durante una semana. En el anime, Misaki es en esencia una chica dulce, aunque jodida, pero aquí destroza su propio cuarto, y cuando se reencuentra con Satou lo insulta recordándole lo despreciable que es, que sin la ayuda de la chica será un hikikomori durante el resto de su vida. En mitad del enfrentamiento, Satou se percata de las cicatrices de quemaduras de cigarrillo en un brazo de la chica. Eso es, pensé. En esta versión colocaron la revelación sobre el backstory de Misaki en la mitad de la narración, como deberían haberlo hecho en el anime. La chica cuenta que su madre murió poco después de dar a luz, que su padre se convirtió en un borracho violento y pegaba a Misaki a menudo, mostrado de manera gráfica en el manga. A pesar de ello la chica seguía queriendo a su padre. Justificaba los golpes creyéndose que los había merecido por ser despreciable. Después de que se llevaran a su padre a algún sitio, Misaki fue a vivir con su tía. Sin embargo, la chica se había vuelto incapaz de rendir en el colegio. Tras abandonarlo trabajó en una tienda y ayudó a su tía durante sus salidas a hacer proselitismo.

Satou está conmovido. Se percata de que la rareza de esta chica está justificada, y ahora quiere ayudarla cuanto pueda. Misaki, celosa y resentida, lo fuerza a hacer lo que a ella se le antoje, desde gastar dinero del que él carece hasta seguirla a todas partes. En una de esas salidas se montan en una noria enorme. Desde ahí Satou coincide en atalayar a su senpai, que disfruta de una cita con su prometido. Lo golpea el hecho de que en su vida sólo había conectado con esa chica, y ahora la perderá y se quedará con esta otra chica que lo manipula porque él es despreciable. Misaki intenta convencerlo de firmar un contrato que dice que él será su esclavo para siempre, pero la chica se percata de que se ha pasado cuando Satou abre la puerta de la cabina de la noria y casi se mata. Después de bajar de la atracción, a pesar de la preocupación de Misaki, él entiende como en una epifanía que sencillamente no quiere seguir viviendo. Se las arregla para zafarse de la chica.

Satou ha salido de viaje, y Misaki se mete en el ordenador del hombre para averiguar adónde. El protagonista ha viajado a una zona montañosa popular para aquellos que pretenden suicidarse. Misaki, junto con Yamazaki, viaja allá y encuentra al protagonista cuando se preparaba para tirarse de un risco. Satou argumenta que sería mejor incluso para Misaki si él desapareciera; la chica no debería lastrarse, dado su trauma, con alguien tan patético como él, pero la naturaleza dulce de ella la forzará a sacrificarse para salvarlo una y otra vez. Sólo si él desaparece y ella no puede hacer nada para solucionarlo será la chica capaz de seguir adelante. Pero Misaki admite que mintió sobre su pasado. Resulta que el backstory usado en el anime se lo ha inventado, que en realidad sus padres son amables y ricos, nadie la fuerza a acudir al instituto, y la chica tiene algún tornillo suelto por ningún motivo en particular. ¿Qué cojones?

Satou pelea por encontrar algún sentido para su inminente suicidio. Incluso trata de abrirse el cráneo contra una roca para donar su cerebro a alguien que le pueda dar un uso mejor, pero su colega Yamazaki le dice que nadie querría esa cosa podrida. Se trata de Yamazaki, entre todas las personas, quien lo convence para volver a casa.

No recuerdo ninguna experiencia reciente con la ficción en la que una versión posterior de una historia haya preparado un giro argumental para la versión original. No tengo ni idea de adónde se dirige el manga ahora.

Reseña: Welcome to the N.H.K., Volumen 3, de Tatsuhiko Takimoto

Un volumen disperso. Contiene los “arcos” en los que el protagonista, Satou, desperdicia semanas en un juego online mientras que su “terapeuta”, Misaki, intenta sacarlo de él, y también la parte en la que el protagonista cae presa de una estafa piramidal. Me pareció que el anime trató ambos arcos mejor. En el primero la relación entre Satou y esa chica-gata curandera está desarrollada más, permitiendo que te importe su relación hasta un extremo razonable para cuando el martillo acaba cayendo. Este arco también sufrió por el hecho de que yo había visto la serie Net-juu no Susume, que también incluye a un personaje principal aislado que conoce a alguien especial a través de un MMO, pero en ese caso con menos consecuencias de comedia negra.

El segundo arco, sobre la estafa piramidal, se resuelve en el anime, pero aquí no. Satou no puede devolver lo que ha comprado, y lo persiguen cobradores.

Además, la versión manga de Misaki intenta desmantelar a Satou mediante bondage, una sección que quizá desapareció del anime por esa razón.

Como punto más interesante, Satou se reúne con su senpai del instituto para una cita a pesar de que ella se casará pronto. Hitomi siempre resulta interesante, enzarzada a diario en un tira y afloja entre asegurarse una vida que no se colapsará y sentirse a gusto consigo misma, lo que suele consistir en caer tan bajo como abusar las drogas o involucrarse con agujeros negros como el protagonista. Más allá de las alucinaciones de Satou que interrumpen la trama, Hitomi le ofrece pasar la noche juntos, pero Satou no quiere contribuir al instinto autodestructivo de la mujer, así que se va a casa, de vuelta a su vida miserable.

Reseña: Welcome to the N.H.K., Volumen 2, de Tatsuhiko Takimoto

Este volumen contiene el arco más memorable del anime: aquel en el que el protagonista, Satou, viaja con su senpai del instituto, Hitomi, a una isla privada para lo que él cree que se trata de unas vacaciones cortas, y la narración se convierte en una comedia negra brillante. Pero el anime divergió de manera significativa del material de origen de una manera que cambió el tono de la historia.

Los personajes se muestran como auténticos cabrones. El colega de Satou, Yamazaki, lo presiona para escribir una escena para el videojuego erótico que están desarrollando, y que incluye, de todas las cosas, la violación de una menor. Me fascina que hayan publicado esta historia. La mente de Satou se resiste de manera heroica; su “terapeuta”, Misaki, se ha convertido en su musa, y no aguanta imaginar esa escena. Pero el cabrón de Yamazaki le recuerda que las mujeres son despreciables. De niño, la chica de la que se enamoró lo engañó para salir con otro, y se agarrará a esa amargura para siempre. Guía a Satou hasta que consigue escribir la mayor parte del borrador de la escena de la violación, pero antes de acabarla, Yamazaki recibe una llamada: la chica que le gusta ahora quiere salir con él esa noche, así que Yamazaki se olvida por un rato de la falta de valor de las mujeres. Es el nice guy arquetípico: sonreirá todo el rato a la chica que se quiera tirar, pero si ella lo rechaza, él considerará que la chica le debía una relación, y hará que se arrepienta regodeándose en fantasías en las que la violará.

Mientras, la senpai de Satou pasa una mala época. Su novio mayor, el ejecutivo de una compañía, apenas tiene tiempo para ella. La naturaleza esquizotípica de la chica la impide encajar en algún sitio, y tomarse sobredosis de ansiolíticos y narcóticos ha dejado de solucionarlo. Hitomi visita a Satou en mitad de la noche y la ocupan bebiendo. A la mañana siguiente, Satou quiere poner una sonrisa en la cara de Hitomi, y le ofrece viajar a algún sitio. La chica se alegra; cree que Satou ha leído la hoja impresa que había traído sobre la reunión de los usuarios de un foro, a la que había decidido atender, y ahora irá con su viejo amigo.

Desde aquí vienen los mayores cambios con respecto al anime. Allá, el ejecutivo de la compañía aparece como un personaje desarrollado. Cuando descubre que su novia ha viajado a una isla privada para suicidarse, se reúne con Misaki y Yamazaki para viajar juntos a la isla y salvarlos. Tras algunos momentos de comedia negra en los que quienes pretendían suicidarse cambian de opinión, y el que había venido confundido se percata de que le convendría morirse, los rescatadores ganan y todos salen de la isla vivos. Ésta es la secuencia en el anime. Aparte del final de la serie, quizá mi momento favorito.

El manga lo trata de manera muy diferente. El ejecutivo de la compañía falta por completo. Misaki encuentra la hoja impresa sobre la reunión del foro, y junto a Yamazaki corren hacia el lugar de reunión. O eso cree Misaki. Yamazaki le sonsaca que se ha apegado tanto a Satou porque en él ha encontrado por fin a alguien más despreciable que ella, así que a través de salvarlo quizá podría salvarse a sí misma. Yamazaki ha grabado la confesión y pretende usarla de inspiración para una escena de su videojuego erótico. Resulta que no se dirigían al punto de reunión. Después de todo, argumenta, Satou no conseguiría suicidarse. La gente como él no podían ganar de esas maneras dramáticas. Se achantaría, y al final moriría de algún modo ridículo.

En la isla, Hitomi abusa las drogas de manera descontrolada. Está colocada todo el rato, apenas consciente. Cuando los miembros de la reunión deciden cancelar el suicidio grupal, Satou argumenta de manera convincente que su vida carece de valor y que le convendría matarse ahí mismo. Intenta morir por inhalación de monóxido de carbono, pero cuando desfallece, los demás lo arrastran fuera de la isla. Ahora que el novio de Hitomi le ha propuesto casarse, ella se olvida deprisa de Satou.

Este anticlímax encaja mejor que la versión del anime, pero no sé si la prefiero. Aun así, el manga honra mejor ese tono de “tocar fondo siendo un japonés de unos veintitantos que carece de futuro”.