Algoritmos evolutivos (EA) son un subconjunto de IA que resuelven problemas utilizando métodos inspirados en la evolución biológica. Desde la optimización de redes neuronales hasta la programación de recursos, tienen una impresionante variedad de aplicaciones en el mundo real. Su belleza surge a través de un cambio de enfoque en lo que se requiere para resolver un problema. En lugar de describir los pasos necesarios para alcanzar un objetivo, los EA describen cómo es el objetivo.
En este artículo exploraré cómo podemos utilizar esta fantástica IA para generar acertijos de ajedrez, los beneficios que brinda y los inconvenientes que debemos considerar.
Un rompecabezas de ajedrez es una posición de ajedrez legal, donde una combinación única de movimientos resulta en una victoria, que a menudo termina en un jaque mate. Por lo general, se encuentran analizando bases de datos de juegos competitivos entre jugadores humanos.
Al generar mis propios acertijos usando nada más que código, aleatoriedad y una pizca de biología, se puede crear una base de datos interesante y diversa de acertijos. Exploremos cómo.
Los algoritmos evolutivos normalmente funcionan generando aleatoriamente una gran población de resultados, luego seleccionando los resultados “más aptos” utilizando una heurística y finalmente tomando esos resultados “más aptos” y generando poblaciones aleatorias posteriores. Están inspirados en la teoría de la selección natural de Darwin, según la cual los animales de una población que tienen más probabilidades de sobrevivir también tienen más probabilidades de transmitir sus rasgos a la siguiente generación. Después de muchas generaciones, a veces cientos de miles, la población converge hacia un resultado óptimo. Entonces, ¿cómo podemos aplicar esto al ajedrez?
Con el ajedrez, podemos crear una población de posiciones legales aleatorias simulando juegos en los que el programa se turna para realizar movimientos aleatorios para blancos y negros un número aleatorio de veces. Repitiendo este proceso decenas de miles de veces, se pueden analizar muestras grandes de posiciones aleatorias para determinar su idoneidad.
A continuación, puedes ver una función de mi Junta clase, que devuelve una lista de movimientos.
public List<(int[] from, int[] to)> GetAllPotentialMoves(Colour currentColour)
{
var activePieces = ActivePieces.Find(p => p.colour == currentColour);
var allLegalMoves = new List<(int[] from, int[] to)>();foreach (var piece in activePieces.pieces)
{
var moves = piece.GetLegalMoves(this);
allLegalMoves.AddRange(moves);
}
return allLegalMoves;
}
Una vez que se ha generado una población de posiciones, comienza lo realmente complicado. La clave de cualquier algoritmo evolutivo es cómo evalúa su heurística. En mi caso, solo se consideraron para un rompecabezas las posiciones en las que una única solución conducía a un jaque mate. Después de reducir esos resultados, la heurística es una medida de lo difícil que es elegir los movimientos correctos para ganar el juego. Pero, ¿cómo puede un programa de computadora estimar qué tan difícil es para un humano interpretar una posición de ajedrez?
Una opción es observar la estructura del rompecabezas. ¿Está el rey a salvo? ¿Hay movimientos que no resuelven el rompecabezas, pero lucen bien? ¿Sacrificamos algún material? ¿Qué piezas estamos moviendo? Al evaluar muchos factores, podemos crear una medida de dificultad. El problema con este enfoque es que es muy difícil decidir cómo crear una puntuación final a partir de tantos factores. Las reglas rígidas también ignoran por completo los sesgos en la percepción humana. Podría ser que incluso cambios sutiles en una posición de ajedrez hagan que a algunos individuos les resulte mucho más difícil elegir el movimiento correcto.
Entonces, ¿cómo podemos tener una mejor idea del desempeño humano? Al utilizar grandes bases de datos llenas de juegos reales, se han entrenado modelos de aprendizaje automático para jugar al ajedrez como jugadores de ciertos niveles. A través de estos modelos podemos tener una mejor idea de cómo jugadores de diferentes habilidades podrían intentar resolver un rompecabezas. ¿Puede una IA entrenada con 1200 jugadores clasificados resolver el rompecabezas? ¿Qué pasa con 1600, 1900? El beneficio de este enfoque es que profundiza en las mentes de los jugadores reales. Sin embargo, los modelos de aprendizaje automático no están exentos de inconvenientes. Estas IA no juegan como un jugador real, juegan como una aproximación de un jugador. También están entrenados en juegos reales y regulares, lo que significa que pueden no ser confiables al evaluar posiciones de ajedrez aleatorias.
Al combinar los modelos de aprendizaje automático con una evaluación compleja y detallada basada en reglas, creé un escenario con lo mejor de ambos mundos. Una heurística que comprende la composición del rompecabezas y al mismo tiempo considera cómo los humanos podrían abordarlo.
Una vez encontrados los mejores rompecabezas de una población, el siguiente paso es crear nuevas generaciones. Esto se puede hacer mediante muchas técnicas inspiradas en la evolución. Elegí utilizar cruce y mutación.
Crossover implica fusionar aleatoriamente las características de dos resultados con la esperanza de obtener las mejores características de ambos. Podemos cruzar posiciones de ajedrez similares retrocediendo una serie de movimientos hasta un punto de partida compartido y luego eligiendo movimientos legales utilizados para alcanzar cada resultado. Quizás mover la dama le dio a un rompecabezas una propiedad realmente buena, y mover el caballo hizo que otro rompecabezas fuera interesante. Al combinar ambas características creamos un problema aún más convincente.
Del mismo modo, podemos mutar acertijos retrocediendo y luego avanzando una serie de movimientos. Dependiendo de la cantidad de movimientos que hagas hacia adelante y hacia atrás, puedes cambiar el rompecabezas de manera sutil o masiva. Demasiada mutación y el algoritmo nunca mejorará; muy poca, el mejor resultado podría converger en un solo valor demasiado rápido.
El problema más común con los algoritmos evolutivos es la convergencia demasiado rápida. Inicialmente, los acertijos que estaba generando dejaron de mejorar después de solo unas pocas generaciones. En el mundo real, fronteras físicas como montañas, desiertos y mares han impedido que las poblaciones crucen su ADN, permitiendo preservar la diversidad genética. Sin suficiente diversidad genética, una población no evolucionará mucho. Al ejecutar poblaciones más pequeñas de acertijos de ajedrez en paralelo durante un tiempo, les di suficiente espacio para mantener cierta diversidad y evitar la convergencia demasiado pronto.
Los algoritmos evolutivos también pueden ser muy lentos. El ajedrez ciertamente no es una excepción. Ejecutar una evaluación heurística en millones de posiciones de ajedrez requiere una cantidad considerable de procesamiento. Generalmente, cuanto más tiempo se ejecuta un motor de ajedrez en una posición, más preciso puede predecir el siguiente mejor movimiento. Al encontrar el punto óptimo en el tiempo dedicado a analizar cada posición, seleccionar las más prometedoras y observarlas con mucho más detalle, pude optimizar el tiempo en una cantidad razonable. Decidir cuándo dejar de generar también es crucial. Si una muestra ha dejado de mejorar durante varias generaciones, quizás sea mejor empezar de nuevo con una nueva población aleatoria, ya que es posible que no pueda mejorar mucho más. Después de innumerables optimizaciones, la PC de mi hogar es capaz de generar más de 1000 acertijos desafiantes por día usando la evolución.
Finalmente, diagnosticar errores puede resultar increíblemente difícil. Con muchos programas se pueden esperar ciertos resultados dadas ciertas entradas. Con la evolución la situación es diferente. Pasé mucho tiempo rascándome la cabeza preguntándome por qué mi población estaba convergiendo demasiado rápido. ¿Fue generación de posición? ¿Fueron los métodos evolutivos, quizás los heurísticos? Puede ser fácil ni siquiera notar si algunas cosas no funcionan según lo previsto cuando el resultado esperado de un programa no se puede definir claramente.
Sin embargo, dejando las cuestiones a un lado, el poder y el potencial de esta técnica de IA brilla a la vista de todos. Usando solo mi vieja PC, he podido generar casi 50.000 acertijos de ajedrez en 3 meses, que contienen una gran cantidad de posiciones extrañas y maravillosas.
La naturaleza aleatoria del algoritmo significa que crea un conjunto de acertijos increíblemente colorido y diverso. Problemas tácticos interesantes que rara vez vemos en el ajedrez, como sacrificios de dama, ascensos de caballo y al paso, son fáciles de encontrar usando la evolución, pero difíciles usando bases de datos de juegos reales. Sin embargo, la naturaleza sin sentido de los acertijos los hace menos aplicables a escenarios del mundo real. Aunque son muy divertidos, se podría argumentar que los acertijos basados en juegos reales son mejores para aprender patrones comunes en los juegos de ajedrez.
Además de ser increíblemente productivo, el algoritmo también es excepcionalmente flexible. Shatranj, tableros de ajedrez torcidos, es fácil extender el EA para que funcione con cualquier derivado del ajedrez. Esta naturaleza extensible es donde realmente sobresale la técnica evolutiva. ¡No puedes hacer esto con bases de datos de juegos, ya que simplemente no existen!
Aunque para muchos es un rincón olvidado de la IA, he demostrado cómo se puede utilizar la evolución para crear una solución novedosa a un problema del mundo real. Hay mucho potencial inexplorado con esta tecnología. Con la IA generativa en aumento, me pregunto qué otras aplicaciones originales encontrará la gente para los EA en el futuro…
Puedes experimentar los rompecabezas por ti mismo en mi sitio web, ajedrezpuzzler.com.
A menos que se indique lo contrario, todas las imágenes son del autor.