Dificultad: Principiante

¿Has intentado programar una Inteligencia Artificial alguna vez pero no sabías por dónde empezar? Conseguiste programarlo, ¿pero era un churro de ifs y bucles interminables? ¿Estás estudiando los autómatas finitos en clase y no tienes ni idea de para qué sirven?

No te preocupes, ¡hoy soluciono todas tus dudas! En este artículo teórico aprenderás a plantear tus propias inteligencias artificiales en papel, para que seas capaz de programarlas en cualquier lenguaje que se te pueda ocurrir.

¡Empezamos!

Si prefieres seguir un vídeo, puedes verlo en mi canal:

Índice

¿Qué tienen que ver las MEFs con la Inteligencia Artificial?

Las Máquinas de Estado Finitas, o Autómatas Finitos, son la base sobre la que se asientan la inmensa mayoría de comportamientos «inteligentes» que encontramos por ahí. Los ejemplos más relevantes que me vienen a la cabeza son lavadoras, máquinas expendedoras, ascensores… ¡y no sólo electrónicos! Seguramente, muchos de los Personajes No Jugadores de tus videojuegos favoritos tengan por lo menos una, si no varias, MEFs integradas.

Y es que muchos editores de videojuegos las implementan. Por ejemplo, los Animators de Unity son en esencia una MEF:

Los blueprints de Unreal Engine también lo son:

E incluso algunos de los plugins más conocidos para hacer Inteligencias Artificiales están completamente basados en ellas, como NodeCanvas:

Así que comprender la teoría detrás de las MEFs te capacitará para entender y programar comportamientos aún más complejos y sofisticados, en cualquier lenguaje de programación que se te pueda ocurrir. La teoría es la base de la práctica, a fin de cuentas.

¿Qué son las Máquinas de Estado Finitas o Autómatas Finitos?

Es un modelo computacional que define una serie de estados por las que puede pasar el programa.

La característica principal de las Máquinas de Estado Finitas es que todas tienen un principio y un final. No importa por cuántos estados pueda pasar la máquina, o si ésta no acaba antes de que se cierre el programa. Lo que la define como un Autómata Finito es que siempre pueda acabar.

¿Pero cómo funcionan?

La máquina más básica

Imaginemos la máquina más simple del mundo:

Esta máquina tiene cuatro estados, representados por círculos: el punto de entrada, el punto de salida y dos estados intermedios que por ahora están vacíos. Las flechas nos indican las transiciones entre los estados; podemos ir de Start a los estados intermedios, y de estos a End.

Hay una flecha más, que no viene de ninguna parte. Esta flecha nos indica cuál es el nodo de entrada, que en este caso está convenientemente marcado como Start.

Para pasar de un estado a otro utilizamos un concepto llamado Alfabeto. El Alfabeto es el conjunto de inputs que puede recibir y procesar la máquina.

Contempla la siguiente imagen:

La máquina de estados ha evolucionado. Digamos que al entrar en un estado, imprimiremos el texto que contiene dentro.

¿Pero qué son las letras que aparecen junto a las flechas? Pues bien, son el Alfabeto, los inputs que marcarán la transición entre estados.

Cuando la máquina se encuentre en el estado Hello,…

• Recibir una a, b o c hará que la máquina pase al estado Marc.
• Recibir una d, e o f hará que la máquina pase al estado Aitor.
• Cualquier otra letra, número o input no tendrá efecto, o dará un error, según queramos programarla.

Es decir, el Alfabeto de esta máquina es «a, b, c, d, e, f».

Además, he utilizado el guión (-) para indicar una transición automática. Es decir, una vez en Marc o Aitor, la máquina pasará de estado a ! Nice to meet you sin esperar un input. Sin embargo, recuerda que el guión en sí podría ser un input, y que podrías indicar la transición automática no poniendo nada. O también podrías indicar «cualquier input» con un asterisco (*). Recuerda que el límite es el cielo.

Ejecutemos la máquina para ver qué ocurriría:

> a
"Hello, Marc! Nice to meet you!"

// La máquina empieza
// "Hello, "
// > a   
// (recibe el input "a", una transición puede aceptarla)
// "Marc"
// (no espera input, transición automática)
// "! Nice to meet you"

Ejercicio personal; ¿qué ocurriría si el input hubiera sido una d?

Una máquina más complicada

¿Son estos los únicos estados que puede tener una Máquina Finita?

¡No!

Una Máquina Finita puede tener infinitos estados, y existen muchas más transiciones posibles. Contempla la siguiente máquina:

Es mucho más compleja que la anterior. No sólo tenemos cuatro estados intermedios, ¡también tenemos algunas flechas nuevas! En la máquina anterior no podíamos retroceder, mientras que en esta sí (fíjate en la flecha que viene del estado superior izquierdo). Encima, en el estado abajo del todo, ¡tenemos una flecha que da la vuelta! Nada nos impide volver a realizar las acciones del estado en el que estamos.

Cuando la máquina se encuentra en un estado no puede ejecutar otro; sólo puede moverse desde el estado en el que esté. Y es que ésta es la clave de las máquinas de estado finitas; pueden ser todo lo complejas que queramos o necesitemos porque, cuando estemos analizando un estado, siempre estará limitada al manojo de transiciones que tenga disponible. Esto es lo que las hace ideales para las Inteligencias Artificiales; el conjunto entero puede ser muy complicado, pero cada paso es muy sencillo.

De una máquina a una Inteligencia Artificial

En el contexto de los videojuegos, un Personaje No Jugador (PNJ) o Non-Playable Character (NPC) es un personaje movido por la máquina. Es decir, se trata de una Inteligencia Artificial. Ésta puede ser tan simple o complicada como queramos.

Utilizando la máquina anterior, voy a definir el comportamiento de un PNJ:

Los estados

Esto es lo que ocurre en los diferentes estados de la máquina:

• IA – no es un estado como tal, pero es quien está ejecutando la máquina. Es de donde parte.
• Idle – el personaje está tranquilo, esperando sin hacer nada.
• Walk – el personaje anda de un punto a otro.
• Talk – el personaje habla con le jugadore.
• Run – el personaje echa a correr, asustade.
• Door – el personaje abre la puerta de su casa y se mete dentro.
• Sleep – el personaje se va a dormir. Es el punto final de la máquina de estados, después no volvemos a verlo.

Observando estas definiciones, hay algo que nos tiene que llamar la atención; son mucho más complejos que antes. Andar, esperar, correr… implican muchas instrucciones, muchas más que mostrar texto por pantalla. De hecho, ¡algunas de ellas necesitarán bucles!

Los estados de una Máquina de Estados Finita no tienen por qué ser instrucciones únicas, de hecho, rara vez lo serán. Lo más habitual es que se estén ejecutando hasta que una de las transiciones se cumpla, y sólo entonces cambiaremos de estado.

Eso sí, un buen estado será aquel que se dedique a una única cosa. Si ves que un estado se empieza a complicar demasiado, es probable que necesites separarlo en más estados.

Las transiciones

Centrémonos en el estado Walk por un momento. Tiene tres transiciones: → Idle, → Talk y → Door. Digamos que hay un 50% de posibilidades de que el PNJ pase de Walk a Idle o a Door. ¿Cómo sabe cuál comprobar primero?

La respuesta real es: depende. Depende de cómo programes cada estado o nodo) al final le darás más peso a unas transiciones u otras.

En el caso de esta máquina, he decidido que se comprueben en sentido horario. Es decir; primero comprobaremos Door, después Talk y por último Idle.

La Inteligencia Artificial completa

Tómate un momento para observarla e intentar comprenderla. A continuación, te la explicaré paso por paso:

• El PNJ empieza en Idle; no hace nada.
  • Pasados 30 segundos, empieza a Caminar.
  • Si antes de que pasen 30 segundos, le jugadore interactúa con el PNJ, éste iniciará una conversación (Talk).
  • Si antes de que pasen 30 segundos, le jugadore se pone agresive, el PNJ echará a correr.
• Cuando el PNJ está en Walk, se dedica a caminar.
  • Hay un 50% de posibilidades de que decida abrir la puerta de su casa (Door).
  • Si le jugadore interactúa con el PNJ, éste iniciará una conversación (Talk).
  • Hay un 50% de posibilidades de que vuelva a Idle.
• Cuando el PNJ está en Run, se dedica a huir de le jugadore.
  • Si le jugadore sigue estando agresive, el PNJ seguirá huyendo.
  • Si le jugadore interactúa con el PNJ, éste iniciará una conversación (Talk).
  • Si ninguno de estos dos inputs se cumple, el PNJ se irá a casa (Door).
• Cuando el PNJ está en Door, éste se irá a casa y abrirá la puerta.
  • No necesita ningún input. Una vez termine las instrucciones de este estado, se irá a dormir y terminará.

En conclusión

Las Máquinas de Estado Finitas o Autómatas Finitos…

• Son la base de las inteligencias artificiales y un montón de comportamientos electrónicos y digitales.
• Tienen siempre un principio y un final.
• Pueden tener infinitos estados.
• Tienen un «Alfabeto», una serie de inputs que pueden aceptar.
• Pueden transicionar de un estado a otro, o volver a uno anterior.
• Pueden transicionar hacia sí mismos.
• Pueden ser todo lo complicadas que queramos o necesitemos.

¿Y ahora?

¡Ahora es hora de crear tus propias máquinas de estados! La práctica te hará mejor, así que no dudes en darle caña y en compartir las tuyas en los comentarios para que podamos comentarlas y mejorar juntes.

En Busca la Excusa no dejamos de buscar cualquier pretexto para seguir aprendiendo. Si te interesan los tutoriales de inteligencia artificial, te sugiero los siguientes artículos de mi blog:

• Programa un NPC desde 0
• Bases de la Generación Procedural
• Introducción al Algoritmo A*
• Programando el Algoritmo A*

Nos vemos en la próxima excusa 😉