¿Qué sucede cuando aplicamos tecnologías modernas de vanguardia al antiguo juego de ajedrez? ¿Y qué sucede cuando un geek aburrido con un exceso de potencia informática realiza sus propios experimentos caseros extraños en el juego?
Este año, un ingeniero de software de Pensilvania que se hace llamar Tom Murphy VII decidió crear algunos algoritmos de ajedrez ridículamente malos utilizando todo, desde aprendizaje automático y redes neuronales hasta una cantidad gratuita de ciclos de CPU, y luego enfrentó los algoritmos malos entre sí para crear un «torneo de tontos».»
» Es mi idea de diversión Murphy», dice Murphy en un video humorístico que describe los experimentos.
Primeros movimientos
Murphy tiene la capacidad intelectual para llevarlo a cabo. Nos cuenta que en 2007 defendió su doctorado en ciencias de la computación. en Carnegie Mellon, que fue el mismo año en que los estudiantes comenzaron a celebrar la conferencia anual SIGBOVIK el Día de los Inocentes. Patrocinado por la» Asociación para la Herejía Computacional», era una especie de grupo satírico de interés especial dedicado a un investigador ficticio llamado» Harry Quizmaster Bovik», e incluía una convocatoria para artículos tontos sobre temas como «estupidez artificial».»
Durante los últimos 11 años, Murphy ha sido ingeniero de software de personal senior en Google (en sus oficinas de Pittsburgh). Pero este año decidió regresar de nuevo para la conferencia del Día de los Inocentes — y de nuevo, contribuyó con su propia investigación humorística.
Murphy se enorgullece de que algunas de sus presentaciones pasadas allí involucraron investigaciones ridículas que eran «indistinguibles de la investigación’ real ‘(por ejemplo, el primer nivel de Super Mario Bros.es fácil con ordenamientos lexicográficos y el viaje en el tiempo tiene unas 20 citas en la investigación académica’ real’).
Pero este fue el año en que Murphy volvió su atención al ajedrez.
Que comiencen los juegos
En el juego inicial de Murphy, los jugadores humanos tienen los ojos vendados, obligándolos a recordar dónde están las piezas. Pero, ¿cuál es el equivalente para una computadora? Decirle dónde se encuentran las piezas, pero no qué piezas son (o incluso de qué color)…
Por supuesto, la computadora tampoco tendría los movimientos que conducen a una posición. Ni siquiera sabría de quién era el turno. Sí, existe la posibilidad de que el rey de la computadora esté en jaque, momento en el que casi todos los movimientos son ilegales, excepto los que llevan a tu rey a un lugar seguro. Pero para evitar eso, Tom creó un programa que genera una lista de posibles movimientos, clasificados en orden de preferencia, de los cuales se elegirá el primer movimiento legal.
» Me gusta jugar contra él, porque no es muy bueno», dice Murphy en el video. «Pero la pregunta natural es ¿no-muy-buena es?»Probarlo contra programas de juego de ajedrez demuestra que sí, pierde con gran regularidad — como en, «cada vez.»
Luego se dispuso a construir otros algoritmos de ajedrez malos, para poder comparar su rendimiento relativo
Uno tenía preferencia por colocar sus piezas en los cuadrados blancos cuando jugaba en blanco, y en cuadrados negros cuando jugaba en negro. (Su oponente? Un algoritmo que prefería colocar sus piezas en cuadrados de colores opuestos. Al final, ambos jugaron bastante mal. «Tienen una preferencia, pero en realidad no tiene que ver con ganar.»De hecho, ambos son un poco peores que el algoritmo que elige sus movimientos al azar.
Si encuentras que mi intrincado video de 42 minutos sobre 30 algoritmos de ajedrez extraños que compiten en un torneo de tontos para evaluar mi programa que juega al ajedrez sin saber qué piezas están en el tablero es aburrido, entonces es porque no entiendes el arte:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) Julio 15, 2019
También había dos algoritmos que llamó » Huddle «y» Swarm», en los que un jugador automático busca movimientos manteniendo sus piezas cerca de su propio rey, mientras que el otro busca movimientos colocando sus piezas cerca del rey de su oponente. Esto a veces lleva al rey de Huddle a ser forzado a seguir a sus propios peones en todos los ámbitos, en los que al menos unos pocos casos su peón promovió accidentalmente en piezas más poderosas e inadvertidamente jaquemateó al rey contrario.
Pero más a menudo, funciona al revés. «Si tienes una preferencia por atacar al oponente, a veces vas a darle jaque mate accidentalmente.»En el video, Murphy revela que entre los algoritmos de ajedrez malos, este sorprendentemente no es tan malo. «‘Enjambre’ es de hecho mucho mejor que ‘ Movimiento aleatorio.'»
Y una estrategia más exitosa es un algoritmo que prioriza cuatro tipos específicos de movimiento( en este orden): jaque mate, jaque, capturar una pieza o empujar al territorio de su oponente.
Pero hay otras ideas terribles, como un algoritmo que busca reflejar las piezas de su oponente, o mover todas sus piezas al otro lado del tablero. Un algoritmo simplemente elige el movimiento que viene primero en orden alfabético.
Y hay otro algoritmo donde cada movimiento se elige de una lista de movimientos posibles, con las elecciones dictadas arbitrariamente por los dígitos de pi
Survival in Chessland
Pero finalmente su algoritmo más elaborado comenzó con una pregunta: ¿qué pieza de ajedrez es más probable que «sobreviva», que permanezca en el tablero hasta el final de la partida y salga victoriosa con todas sus piezas de ajedrez? Investigando diligentemente la respuesta, Murphy hizo una visita al sitio de ajedrez libre LiChess.org (que ahora ve más de un millón de juegos al día). También ofrece juegos para descargar, por lo que Murphy descargó los 506.000.416 de ellos.
Resumió los resultados en un artículo llamado «Supervivencia en Ajedrez», que explica su metodología. Murphy descargó todos los juegos completos que tenían hasta noviembre de 2018, aunque aparentemente otros 200 millones han estado disponibles en los ocho meses posteriores. Incluso su botín de noviembre representó la friolera de 875 GB de partidas de ajedrez, «por lo que procesarlas tuvo un poco de cuidado por la eficiencia y el paralelismo», dice Murphy en el video.
» Afortunadamente, tengo una computadora con un número obsceno de núcleos y una RAM realmente excesiva, por lo que debes usarla para algo.»
Er, how obscene? En un correo electrónico, describe su sistema doméstico «gratuito», un AMD ThreadRipper 2990WX de 32 núcleos. Ejecutar los programas multihilo de C++ durante unas horas fue suficiente para procesar todo el conjunto de datos. «Creo que la gente subestima lo que se puede hacer de manera eficiente con una sola máquina.»
«El trabajo involucrado es bastante simple: Analizo el PGN (que describe el juego), luego ejecutolos movimientos en el juego, haciendo un seguimiento del destino de cada pieza, y luego sumo los recuentos de cada destino
«Básicamente escribí todo el código desde cero, porque esto es más divertido que hacer funcionar el código de otras personas. :)»
El análisis de «supervivencia» de Murphy creó algunas visualizaciones realmente hermosas de los datos, mostrando la probabilidad de supervivencia de cada pieza de ajedrez en cada una de las 64 casillas (con colores que indican su probabilidad de estar en esa casilla al final del juego.)
Y luego esto llevó a más algoritmos de ajedrez malos. Primero, está el que mueve las piezas a esos cuadrados donde es estadísticamente más probable que sobrevivan. O simplemente a las casillas donde es más probable que estén al final de una partida. Y otros algoritmos hacen exactamente lo contrario: mover piezas a cuadrados donde es menos probable que sobrevivan (o terminen). Dos algoritmos calculan qué cuadrado tiene la tasa de supervivencia más alta (versus la tasa de captura) para una pieza en cada cuadrado, con un algoritmo que busca la relación más alta que favorece la supervivencia, y el algoritmo «fatalista» que busca la relación más baja.
» Extrañamente, tiene las mejores oportunidades de ganar de estas estrategias.»
Y finalmente, decidió compararlos todos con el motor de ajedrez Stockfish en varios niveles (incluido un algoritmo especial donde se ve obligado a jugar su movimiento menos prometedor). «Mirando los resultados, como era de esperar, esta es la peor estrategia en general, y se las arregla para perder ante casi todo el mundo.»
¿Pero recuerdas el algoritmo original «con los ojos vendados» de Tom, que no sabía qué pieza ocupaba un cuadrado (o incluso su color)? Decidió aumentarlo con una red neuronal, que realizaba aprendizaje automático, utilizando los miles de millones de posiciones disponibles en los juegos de LiChess.org. Ahora era capaz de predecir correctamente las piezas reales en cada posición con un 100% de precisión, aproximadamente una quinta parte de las veces. E incluso cuando está mal, solo se adivina incorrectamente un promedio de 3.22 piezas para cada posición.
Y esto se convierte en un punto de partida para cálculos aún más salvajes. En algún momento, deduce que todos los juegos en su base de datos finalmente pasan por 21,553,382,902 posiciones únicas. Con 204 GB, podría almacenarlos todos, junto con el siguiente movimiento, pero hay otra estadística interesante. Un enorme 76% de las posiciones ocurrieron exactamente una vez. «Así que ocupan mucho espacio, y no son muy útiles para jugar, porque es muy poco probable que los vuelva a ver.»Desechando estas posiciones únicas, cualquier otra posición de juego posible se puede almacenar con aproximadamente 500 MB de memoria. Esto se puede convertir fácilmente en un algoritmo que reproduce el movimiento más popular para cualquier posición que encuentre (mientras se intercambia en un movimiento aleatorio si se encuentra atrapado en una posición única).
Pero hay un truco fácil para vencerla. «Tan pronto como hago un movimiento un poco raro, comienza a jugar al azar. Y luego es muy fácil de superar.»
Un experimento final implica varias «diluciones» del motor de Stockfish, en el que su movimiento preferido es reemplazado por un movimiento elegido al azar x por ciento del tiempo.»
«En realidad podemos evaluar lo bueno que es un jugador ahora comparándolo directamente con una dilución específica de Stockfish
Después de que todos los elaborados algoritmos de juego de ajedrez de Murphy hubieran sido probados diligentemente, resumió los resultados en una mesa masiva, y concluyó triunfalmente su video anunciando que finalmente estaba listo para perseguir otros intereses.
» Ahora vamos al siguiente proyecto, que está enseñando a este perro a jugar ajedrez.»
- ¿Qué sucede cuando el aprendizaje automático lleva a la humanidad a respuestas que no entendemos?
- Conoce a Sophie, la robot que hace fideos.
- Después de 15 años, los investigadores descubren un brazo artificial que puede sentir.