¿Por qué no hay motores de aprendizaje de refuerzo profundo para el ajedrez, similares a AlphaGo?

Las computadoras han podido jugar al ajedrez durante mucho tiempo utilizando una técnica de "fuerza bruta", buscando a cierta profundidad y luego evaluando la posición. Sin embargo, la computadora AlphaGo solo usa un ANN para evaluar las posiciones (hasta donde yo sé, no realiza ninguna búsqueda profunda). ¿Es posible crear un motor de ajedrez que juegue ajedrez de la misma manera que AlphaGo juega Go? ¿Por qué nadie ha hecho esto? ¿Este programa funcionaría mejor que los mejores motores de ajedrez (y jugadores de ajedrez) de hoy?

EDITAR (después de leer el periódico):

He leído el periódico cuidadosamente. Comencemos con lo que Google afirmó en el documento:

• Derrotaron a Stockfish con Monte-Carlo-Tree-Search + Redes neuronales profundas
• El partido fue absolutamente unilateral, muchas victorias para AlphaZero pero ninguna para Stockfish
• Pudieron hacerlo en solo cuatro horas
• AlphaZero jugó como un humano

Desafortunadamente, no creo que sea un buen periódico. Voy a explicar con enlaces (para que sepas que no estoy soñando):

• https://chess.stackexchange.com/questions/19360/how-is-alpha-zero-more-human tiene mi respuesta sobre cómo AlphaZero jugó como un humano

• El partido fue injusto , muy sesgado. Cito a Tord Romstad, el programador original de Stockfish.

https://www.chess.com/news/view/alphazero-reactions-from-top-gms-stockfish-author

Los resultados del partido en sí mismos no son particularmente significativos debido a la elección bastante extraña de los controles de tiempo y la configuración de los parámetros de Stockfish: los juegos se jugaron en un tiempo fijo de 1 minuto / movimiento, lo que significa que Stockfish no tiene uso de su heurística de gestión del tiempo ( Se ha hecho un gran esfuerzo para que Stockfish identifique puntos críticos en el juego y decida cuándo pasar un tiempo extra en un movimiento; en un tiempo fijo por movimiento, la fuerza se verá afectada significativamente).

Stockfish no podría haber jugado el mejor ajedrez con solo un minuto por jugada. El programa no fue diseñado para eso.

• Stockfish se estaba ejecutando en una máquina comercial normal, mientras que AlphaZero estaba en una máquina de 4 millones de TPU sintonizada para AlphaZero. Esto es como hacer coincidir su computadora de escritorio de alta gama con un teléfono Android barato. Tord escribió:

Uno es un programa de ajedrez convencional que se ejecuta en computadoras comunes, el otro utiliza técnicas fundamentalmente diferentes y se ejecuta en hardware de diseño personalizado que no está disponible para la compra (y estaría fuera del presupuesto de los usuarios comunes si lo fuera).

• Google sin darse cuenta dio 64 hilos a una máquina de 32 núcleos para Stockfish. Cito al GM Larry Kaufman (experto en ajedrez informático de clase mundial):

http://talkchess.com/forum/viewtopic.php?p=741987&highlight=#741987

Estoy de acuerdo en que la prueba estuvo lejos de ser justa; Otro problema que perjudicó a SF fue que aparentemente se ejecutó en 64 subprocesos en una máquina de 32 núcleos, pero sería mucho mejor ejecutar solo 32 subprocesos en esa máquina, ya que casi no hay beneficio de SMP para compensar la desaceleración de aproximadamente 5 a 3. Además, la relación de costos fue más de lo que dije; Estaba pensando que era una máquina de 64 núcleos, pero una máquina de 32 núcleos cuesta aproximadamente la mitad de lo que supuse. Entonces, en general, 30 a 1 no es una mala estimación. Por otro lado, creo que subestimas cuánto podría mejorarse aún más.

• Stockfish dio solo 1 GB de tabla hash. Esto es una broma ... ¡Tengo una tabla hash más grande para mi aplicación Stockfish iOS (Descargo de responsabilidad: soy el autor) en mi iPhone! Tord escribió:

  ... tablas hash demasiado pequeñas para la cantidad de hilos ...

La tabla hash de 1 GB es absolutamente inaceptable para un partido como este. Stockfish frecuentemente encontraría colisión de hash. Se necesitan ciclos de CPU para reemplazar las entradas hash antiguas.

• Stockfish no está diseñado para ejecutarse con tantos hilos. En mi aplicación de ajedrez iOS, solo se usan unos pocos hilos. Tord escribió:

... estaba jugando con muchos más hilos de búsqueda de los que jamás haya recibido una cantidad significativa de pruebas ...

• Stockfish se estaba ejecutando sin un libro de apertura o una base de tabla final Syzygy de 6 piezas. El tamaño de la muestra fue insuficiente. La versión de Stockfish no era la última. Discusión aquí .

CONCLUSIÓN

Google no ha demostrado sin dudas que sus métodos son superiores a Stockfish. Sus números son superficiales y fuertemente sesgados a AlphaZero. Sus métodos no son reproducibles por un tercero independiente. Todavía es demasiado pronto para decir que el aprendizaje profundo es un método superior a la programación tradicional de ajedrez.

Hay un nuevo artículo de Google Deepmind ( https://arxiv.org/pdf/1712.01815.pdf ) para el aprendizaje de refuerzo profundo en ajedrez. Desde el resumen, el motor de ajedrez Stockfish número uno del mundo fue derrotado "convincentemente". Creo que este es el logro más significativo en el ajedrez informático desde el partido Deep Blue de 1997. Actualizaré mi respuesta una vez que lea el documento en detalle.

Original (antes de diciembre de 2017)

Aclaremos su pregunta:

• No, los motores de ajedrez no usan la fuerza bruta.
• AlphaGo hace la búsqueda uso de los árboles, que utiliza Monte Carlo árbol de búsqueda . Google " Monte Carlo Tree Search alphaGo " si quieres convencerte.

ANN puede usarse para motores de ajedrez:

• Jirafa (el enlace publicado por @Tim)
• NeuroChess

¿Este programa funcionaría mejor que los mejores motores de ajedrez (y jugadores de ajedrez) de hoy?

La jirafa juega aproximadamente al nivel de maestro internacional, que es aproximadamente la calificación FIDE 2400. Sin embargo, Stockfish, Houdini y Komodo juegan a aproximadamente FIDE 3000. Esta es una gran brecha. ¿Por qué? ¿Por qué no Monte-Carlo Tree Search?

• El material heurístico en el ajedrez es simple. La mayoría de las veces, una posición de ajedrez está ganando / perdiendo simplemente contando los materiales en el tablero. Recuerde que contar materiales no funciona para Go. El conteo de materiales es de órdenes de magnitud más rápido que la ejecución de redes neuronales; esto se puede hacer mediante paneles de bits representados por un número entero de 64 bits. En el sistema de 64 bits, solo se puede hacer con varias instrucciones de la máquina. Buscar con el algoritmo tradicional es mucho más rápido que el aprendizaje automático. Los nodos más altos por segundo se traducen en una búsqueda más profunda.
• Del mismo modo, existen técnicas muy útiles y baratas, como la poda de movimientos nulos, la reducción de movimientos tardíos y los movimientos asesinos, etc. Son baratos de ejecutar y muy eficientes para el enfoque utilizado en AlphaGo.
• La evaluación estática en el ajedrez es rápida y útil.
• El aprendizaje automático es útil para optimizar parámetros, pero también tenemos SPSA y CLOP para ajedrez.
• Hay muchas métricas útiles para la reducción de árboles en el ajedrez. Mucho menos para Go.

Se investigó que Monte Carlo Tree Search no escala bien para el ajedrez. Go es un juego diferente al ajedrez. Los algoritmos de ajedrez no funcionan para Go porque el ajedrez se basa en tácticas brutales. La táctica es posiblemente más importante en el ajedrez.

Ahora, hemos establecido que MCTS funciona bien para AlphaGo pero menos para el ajedrez. El aprendizaje profundo sería más útil si:

• La evaluación NN sintonizada es mejor que los algoritmos tradicionales. Sin embargo ... el aprendizaje profundo no es mágico, usted como programador aún necesitaría hacer la programación. Como se mencionó, tenemos algo como SPSA para el auto-juego para el ajuste de parámetros en ajedrez.
• Inversión, dinero! No hay mucho dinero para el aprendizaje automático en el ajedrez. Stockfish es gratuito y de código abierto, pero lo suficientemente fuerte como para derrotar a todos los jugadores humanos. ¿Por qué Google gastaría millones si alguien puede descargar Stockfish gratis? ¿Por qué va a pagar los grupos de CPU? ¿Quién va a pagar por los talentos? Nadie quiere hacerlo, porque el ajedrez se considera un juego "resuelto".

Si el aprendizaje profundo puede lograr lo siguiente, superará el algoritmo tradicional:

• Dada una posición de ajedrez, "siéntala" como un gran maestro humano. Por ejemplo, un gran maestro humano no entraría en líneas que son malas, por experiencia. Ni el algoritmo tradicional ni el aprendizaje profundo pueden lograrlo. Su modelo NN podría darle una probabilidad [0..1] para su posición, pero eso no es lo suficientemente bueno.

Déjame señalar:

No. Giraffe (el enlace publicado por @Tim) no usa Monte Carlo Tree Search. Utiliza el algoritmo regular nega-max. Todo lo que hace es reemplazar la función de evaluación regular con NN, y es muy lenta.

uno mas:

Aunque Kasparov fue derrotado por Deep Blue en el partido de 1997. La "humanidad" se perdió realmente alrededor de 2003-2005, cuando Kramnik perdió un partido contra Deep Fritz sin una victoria y Michael Adams perdió contra una máquina de racimo en un partido unilateral. Alrededor de ese tiempo, Rybka demostró ser demasiado fuerte incluso para los mejores jugadores del mundo.

Referencia:

http://www.talkchess.com/forum/viewtopic.php?t=64096&postdays=0&postorder=asc&highlight=alphago+chess&topic_view=flat&start=0

Yo cito:

En el ajedrez tenemos el concepto de materialidad que ya da una estimación razonable de qué tan bien está funcionando un motor y se puede calcular rápidamente. Además, hay muchos otros aspectos del juego que se pueden codificar en una función de evaluación estática que no se podría hacer en Go. Debido a las muchas heurísticas y la buena evaluación, el EBF (Effective-Branching-Factor) es bastante pequeño. El uso de una red neuronal como reemplazo de la función de evaluación estática definitivamente ralentizaría bastante el motor.

DeepBlue ya ha vencido a Kasparov, por lo que este problema se resuelve con un enfoque mucho más simple. Esto fue posible porque la cantidad de movimientos posibles en el ajedrez es mucho menor que en el juego , por lo que es un problema mucho más simple. Además, tenga en cuenta que tanto NN como la fuerza bruta necesitan enormes recursos informáticos ( aquí puede encontrar una foto de la computadora detrás de AlphaGo, observe que no utiliza ni GPU, sino TPU para el cálculo). Todo el alboroto con go fue que cuando Deep Blue venció a Kasparov, la comunidad go ha argumentado que esto no sería posible con go (por muchas razones diferentes, pero para resumir los argumentos necesitaría dar una introducción detallada al juego de ir). Sí, puedes enseñarle a NN a jugar ajedrez, Mario , o intentar enseñarlo a jugarStarcraft ...

Supongo que la razón es que simplemente no se escucha a menudo en los medios convencionales sobre casos en que las personas resuelven problemas que ya se resolvieron.

Además, su premisa es incorrecta, el aprendizaje profundo se utiliza para jugar al ajedrez, por ejemplo, como se describe en Deep Learning Machine Teaches Self Chess en 72 horas, juega a nivel internacional de maestría . Vea también el documento correspondiente, Jirafa: Uso del aprendizaje de refuerzo profundo para jugar al ajedrez .