En este artículo, compartiré la experiencia de desarrollar inteligencia artificial simple (IA) utilizando un algoritmo genético, y también hablaré sobre el conjunto mínimo de comandos necesarios para formar cualquier comportamiento.
El resultado del trabajo fue que la IA, sin conocer las reglas, dominó de forma independiente el juego del tic-tac-toe y descubrió las debilidades de los bots que jugaban contra él. Pero comencé con una tarea aún más simple.
Conjunto de instrucciones
Todo comenzó con la preparación de un conjunto de comandos que AI podría tener. Los lenguajes de alto nivel contienen cientos de operadores diferentes. Para resaltar el mínimo necesario, decidí recurrir al lenguaje Assembler. Sin embargo, resultó que contiene muchos comandos.
Necesitaba la IA para leer y generar datos, trabajar con memoria, realizar cálculos y operaciones lógicas, hacer transiciones y bucles. Encontré el lenguaje Brainfuck, que contiene solo 8 comandos y puede realizar cualquier cálculo (es decir, si Turing está completo). En principio, es adecuado para la programación genética, pero fui más allá.
Me preguntaba: ¿cuál es el número mínimo de comandos necesarios para implementar cualquier algoritmo? Al final resultó que - uno!
El procesador URISC contiene solo un comando: restar y omitir la siguiente instrucción si el restado fue mayor que el decrementado. Esto es suficiente para construir cualquier algoritmo.
Oleg Mazonka fue aún más lejos, desarrolló el equipo
BitBitJump y demostró que está completo de acuerdo con Turing. El comando contiene tres direcciones, copia un bit de la primera a la segunda dirección de memoria y transfiere el control a la tercera dirección.
Habiendo tomado prestadas las ideas de Oleg, para simplificar el trabajo, desarrollé el equipo SumIfJump. El comando contiene cuatro operandos: A, B, C, D y realiza lo siguiente: agrega datos de la celda a la dirección A a la dirección B, si el valor es mayor que el especificado *, va a la dirección C, de lo contrario va a la dirección D.
Nota* En este caso, se utilizó 128, la mitad de la longitud del genoma.
Cuando el operando A accede a la celda de memoria N0, se ingresan datos, y cuando van a la celda N1, luego salen.
A continuación se muestra el código SumIfJump en FreePascal (un análogo gratuito de Delphi).
procedure RunProg(s: TData); var a, b, c, d: TData; begin Inc(NStep); if NStep > MaxStep then begin ProgResult := 'MaxStep'; Exit; end; a := s; b := s + 1; c := s + 2; d := s + 3; a := Prog[a]; b := Prog[b]; c := Prog[c]; d := Prog[d]; if a = 0 then begin ProgResult := 'Input'; Exit; end; if a = 1 then begin ProgResult := 'Output'; Exit; end; Prog[b] := Prog[b] + Prog[a]; if Prog[b] < ProgLength div 2 then RunProg(c) else RunProg(d); end;
SumIfJump implementa código auto modificable. Puede ejecutar cualquier algoritmo disponible en el lenguaje de programación habitual. El código es fácil de modificar y soporta cualquier manipulación.
Tarea simple
Entonces, nuestra IA solo tiene un equipo. Si bien el tic-tac-toe es un juego muy difícil para él, comencé con uno más simple.
El bot da un número aleatorio, y la IA debe leer los datos y dar una respuesta. Si el número es mayor que el promedio (del rango de números aleatorios), la IA debe dar un número menor que el promedio y viceversa.
El genoma de nuestra IA consta de 256 celdas con valores de 0 a 255. Cada valor es una memoria, un código y una dirección. El número de pasos de ejecución de código está limitado a 256. Los operandos se leen uno tras otro.
Inicialmente, el genoma está formado por un conjunto de números aleatorios, por lo que la IA no sabe lo que necesita para jugar. Además, no sabe que necesita ingresar y generar datos secuencialmente, respondiendo al bot.
Población y selección
La primera población consta de 256 IA que comienzan a jugar con el bot. Si la IA realiza las acciones correctas, por ejemplo, solicita datos de entrada y luego muestra algo, entonces la IA recibe puntos. Cuantas más acciones correctas, más puntos.
Las 16 IA que obtuvieron la mayor cantidad de puntos dan 15 descendientes y continúan participando en el juego. Un descendiente es un mutante. La mutación se produce al reemplazar una celda aleatoria en la copia principal con un valor aleatorio.
Si ninguna IA obtuvo puntos en la primera población, se forma la siguiente población. Y así sucesivamente hasta que parte de la IA comience a realizar las acciones correctas y dar la descendencia "correcta".
Evolución
| N | Hitos |
|---|
| 1 | La IA no hace nada. El programa toma 256 pasos y finaliza. |
| 2 | Comenzó a solicitar datos. |
| 3 | Comenzó a solicitar datos y generar algo. La secuencia de solicitudes y respuestas es caótica. |
| 4 4 | La entrada y salida de datos ocurre secuencialmente, a veces ocurren errores. En la mitad de los casos, AI da la respuesta correcta. |
| 5 5 | Da respuestas correctas regularmente, pero a veces ocurren errores. |
| 6 6 | Dio la respuesta correcta en 30 mil iteraciones. La selección está cargada. |
Entre eventos significativos, miles de generaciones pasaron. El programa se lanzó en varios hilos en Core i7. Los cálculos tomaron unos 15 minutos.
Puntos interesantes
- Cuando el "líder" de la IA cometió un error aleatorio y no obtuvo suficientes puntos, la población comenzó a degradarse, porque descendencia formada por padres "secundarios".
- Dio la casualidad de que en la corriente con extraños que estaban marcando el tiempo, se produjo una mutación exitosa, proporcionando un aumento explosivo en los puntos acumulados. Después de eso, este flujo se convirtió en el líder.
- A veces, durante mucho tiempo, no ocurrieron mutaciones exitosas, e incluso 500 mil generaciones no fueron suficientes para completar la selección.
Conclusión
En conclusión, hice lo mismo con el juego de tres en raya. El tamaño del genoma se utilizó como en el primer caso. El número de pasos se incrementó a 1024 y el tamaño de la población a 64 (para un cálculo más rápido). El cálculo tardó un poco más. Todo sucedió de acuerdo con el mismo escenario.
Al principio, la IA jugó contra el "aleatorizador". Llamé al bot que camina al azar. Bastante rápido, AI comenzó a vencerlo, completando una línea. Además, compliqué la tarea agregando una pequeña razón al aleatorizador: ocupar la línea, si es posible, o defender. Sin embargo, en este caso, AI descubrió las debilidades del bot y comenzó a vencerlo. Quizás la historia sobre esto es un tema para un artículo separado.
El hijo me pidió que escribiera un programa para que las IA jueguen entre ellos, y no con el bot. Hubo ideas para hacer lo mismo para jugar damas o ir, sin embargo, para esto ya no tenía suficiente tiempo.
El único método que usé para obtener nuevos individuos fue una mutación. También puede usar crossover e inversión. Quizás estos métodos aceleren la obtención del resultado deseado.
Al final, nació la idea: darle a AI la capacidad de administrar todos los procesos en una PC y luchar por los recursos de la computadora. Conecte una PC a Internet y use el conjunto de antiguas granjas de bitcoins como potencia informática ...
Como se dijo, realizando un experimento similar, el blogger
Mikhail Tsarkov :
Tal vez se harán cargo del mundo, pero ¿y si?
Referencias
- Algoritmos Genéticos
- Copy Bit - La máquina de computación más simple / Oleg Mazonka
- URISC - Wikipedia
- Integridad de Turing - Wikipedia