Independencia 01: ¿En que consiste el juego?
En la revista Muy Interesante Año 17 Número 195, el tema de portada es la Inteligencia Artificial. Leí un párrafo que me llamó la atención el cual dice: "Incluso la poderosísima Deep Blue, tan inteligente que es capaz de ganarle una partida de ajedrez a Kasparov, perdería con un niño un juego de triqui ". Es cierto, Deep Blue fue programada para jugar exclusivamente ajedrez, todos sus algoritmos y bancos de memoria están diseñados para producir la próxima jugada analizando con fuerza bruta (potencia de computo) millones de movimientos. Deep Blue no conoce el triqui, para esto, un programador tendría que sentarse y programarla para ser invencible en este juego y así sucesivamente por cada juego nuevo.
¿Por qué no construir un software capaz como el humano de entender un juego de mesa y poder jugarlo?
Un juego es un ambiente con unas reglas lógicas, estas reglas hacen que un jugador gane, pierda o empate durante la partida. Un jugador es un ser vivo que debe adaptarse a ese ambiente: una buena adaptación significa que es ganador, una mala adaptación es un perdedor.
Igual que sucede con los grandes torneos, los que ganan, aseguran un cupo para las siguientes partidas, los perdedores son eliminados. Selección natural simple.
El objetivo de esta simulación es tomar un juego simple de mesa: Hacer líneas horizontales y verticales con N piezas. Estas son las reglas:
Dos jugadores.
El jugador 1 comienza colocando su símbolo en alguna celda vacía de la cuadricula.
Sigue el jugador 2 colocando su símbolo en otra celda vacía de la cuadricula.
El objetivo es hacer líneas horizontales o verticales con N mismos símbolos contínuos.
Ambos jugadores continúan jugando hasta que la cuadricula este llena.
Gana el jugador que complete mas líneas horizontales y verticales.
| x | 0 | x | 0 | 0 |
| 0 | 0 | x | 0 | 0 |
| x | x | x | 0 | 0 |
| 0 | x | x | x | x |
Dado N=4 (gana los de 4 horizontal o vertical) el jugador con símbolo "x" es el vencedor con 1 horizontal y una vertical, es decir 2 puntos, el jugador con símbolo "0" no tiene puntos.
¿Podremos decirle a un programa evolutivo que entienda un juego como este? Yo pienso que es posible. Se generan algoritmos en forma aleatoria y luego por selección sobreviven aquellos que puedan ser buenos jugadores en este tipo de juego. Los sobrevivientes son reproducidos con ligeras mutaciones hasta que después de millones de ciclos salga un algoritmo lo suficientemente bueno como para jugar contra un humano.
Se observa que la idea no es tan descabellada, es posible, se requiere eso si gran capacidad de computo y algoritmos optimizados.
Durante el desarrollo de este algoritmo logré separar los algoritmos que evolucionan de los componentes del ambiente. Se nota claramente que en esta hay:
Un ambiente
Sensores (Retornan estados del ambiente)
Acciones (Hacen algo sobre el ambiente)
Un proceso de selección natural.
Algoritmo Evolutivo en si.
El algoritmo evolutivo puede estar completamente independiente en una DLL o un ActiveX, el programador aparte, solo debe programar el ambiente (en este caso el tablero del juego), los sensores (retornan las dimensiones del tablero y si una casilla esta ocupada o no), las acciones (colocar un símbolo en determinada casilla) y el proceso de selección natural (cuantas líneas creó).
La primera aproximación es que simplemente el algoritmo evolutivo logre colocar sus símbolos sobre el tablero (todavía no compite). Era de esperarse que generando al azar algoritmos usando dos sensores y una acción, se tardara muchísimo en lograr un algoritmo que llenara el tablero.
Probando un tablero de 10 * 10, los primeros algoritmos no lograban siquiera llenar una sola casilla, luego llenaban solo una y de vez en cuando dos, lo ideal sería que llenara las 100 casillas. Es tan bajo el nivel de éxito que personalmente llegué a pensar que la investigación no debe llevarse por este camino, pero a medida que probaba simulaciones con miles de algoritmos, la efectividad creció alrededor del 7%, luego no es prudente desechar esto, hay que hacer mas pruebas.
Esta simulación solo es de algoritmos al azar, todavía no hay mutación fuerte o simple.
Ambiente: Tablero de 11*11
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Sensor 1: Informa dimensión del tablero 0 a 10.
Sensor 2: Informa si una casilla esta vacía u ocupada con algún símbolo.
Acción 1: Coloca un símbolo en determinada casilla.
Proceso de Selección Natural: "Sólo aquellos algoritmos que logren colocar mas símbolos en el tablero estarán en la lista de los 40 mejores".
Las pruebas desde 100.000 organismos hasta 900.000 organismos se pueden ver en el siguiente gráfico:
Cómo se observa no es mucho el éxito para colocar símbolos en un tablero de 11*11 (121 casillas), el promedio oscilaba entre 7 y 12 casillas (5.7% a 9.9%). Son algoritmos al puro azar sin capacidad de reproducción (no son genéticos).