Por que não existem mecanismos de aprendizado de reforço profundo para xadrez, semelhantes ao AlphaGo?

Há muito tempo os computadores conseguem jogar xadrez usando uma técnica de "força bruta", procurando até uma certa profundidade e depois avaliando a posição. O computador AlphaGo, no entanto, usa apenas uma RNA para avaliar as posições (ele não faz nenhuma pesquisa em profundidade até onde eu sei). É possível criar um mecanismo de xadrez que jogue xadrez da mesma maneira que AlphaGo joga Go? Por que ninguém fez isso? Esse programa teria um desempenho melhor do que os principais mecanismos de xadrez (e jogadores de xadrez) de hoje?

EDIT (após a leitura do artigo):

Eu li o jornal pensativamente. Vamos começar com o que o Google afirmou no jornal:

• Eles derrotaram o Stockfish com redes Monte-Carlo-Tree-Search + Deep neural
• A partida foi absolutamente unilateral, muitas vitórias para o AlphaZero, mas nenhuma para o Stockfish
• Eles conseguiram fazer isso em apenas quatro horas
• AlphaZero jogou como um humano

Infelizmente, não acho que seja um bom jornal. Vou explicar com links (para você saber que não estou sonhando):

• https://chess.stackexchange.com/questions/19360/how-is-alpha-zero-more-human tem minha resposta sobre como o AlphaZero se comportou como humano

• A partida foi injusta , fortemente tendenciosa. Cito Tord Romstad, o programador original do Stockfish.

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

Os resultados da partida, por si só, não são particularmente significativos devido à estranha seleção de controles de tempo e aos parâmetros do Stockfish: os jogos foram disputados em um tempo fixo de 1 minuto / movimento, o que significa que o Stockfish não usa suas heurísticas de gerenciamento de tempo ( Foi feito um grande esforço para fazer o Stockfish identificar pontos críticos do jogo e decidir quando gastar algum tempo extra em um movimento; em um tempo fixo por movimento, a força sofrerá significativamente).

O Stockfish não poderia ter jogado o melhor xadrez com apenas um minuto por jogada. O programa não foi projetado para isso.

• O Stockfish estava sendo executado em uma máquina comercial comum, enquanto o AlphaZero estava em uma máquina de 4 milhões + TPU ajustada para o AlphaZero. É como comparar sua área de trabalho de ponta com um telefone Android barato. Tord escreveu:

Um é um programa de xadrez convencional rodando em computadores comuns, o outro usa técnicas fundamentalmente diferentes e é executado em hardware projetado personalizado que não está disponível para compra (e estaria fora do orçamento dos usuários comuns).

• O Google inadvertidamente deu 64 threads a uma máquina de 32 núcleos para o Stockfish. Cito GM Larry Kaufman (especialista em xadrez de computador de classe mundial):

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

Concordo que o teste estava longe de ser justo; outro problema que afetou o SF foi o fato de ele aparentemente ter sido executado em 64 threads em uma máquina com 32 núcleos, mas seria muito melhor executando apenas 32 threads nessa máquina, já que quase não há benefício do SMP para compensar a desaceleração de aproximadamente 5 a 3. Além disso, a relação de custo foi maior do que eu disse; Eu estava pensando que era uma máquina de 64 núcleos, mas uma máquina de 32 núcleos custa cerca da metade do que eu imaginei. Portanto, talvez todos os 30 para 1 não sejam uma estimativa tão ruim. Por outro lado, acho que você subestima o quanto isso poderia ser melhorado.

• O Stockfish forneceu apenas uma tabela de hash de 1 GB. Isso é uma piada ... Tenho uma tabela de hash maior para o meu aplicativo Stockfish iOS (Isenção de responsabilidade: sou o autor) no meu iPhone! Tord escreveu:

  ... tabelas de hash muito pequenas para o número de threads ...

A tabela de hash de 1 GB é absolutamente inaceitável para uma correspondência como esta. O Stockfish frequentemente encontrava colisão de hash. São necessários ciclos de CPU para substituir entradas antigas de hash.

• O Stockfish não foi projetado para ser executado com tantos números de threads. No meu aplicativo de xadrez para iOS, apenas alguns threads são usados. Tord escreveu:

... estava jogando com muito mais tópicos de pesquisa do que nunca recebeu uma quantidade significativa de testes ...

• O Stockfish estava funcionando sem um livro de abertura ou uma base de mesa Syzygy de seis peças no final de jogo. O tamanho da amostra foi insuficiente. A versão do Stockfish não era a mais recente. Discussão aqui .

CONCLUSÃO

O Google não provou sem dúvida que seus métodos são superiores ao Stockfish. Seus números são superficiais e fortemente influenciados pelo AlphaZero. Seus métodos não são reproduzíveis por terceiros independentes. Ainda é um pouco cedo para dizer que o Deep Learning é um método superior à programação tradicional de xadrez.

Há um novo artigo do Google Deepmind ( https://arxiv.org/pdf/1712.01815.pdf ) sobre aprendizado de reforço profundo no xadrez. Do resumo, o mecanismo de xadrez Stockfish número um do mundo foi "convincentemente" derrotado. Acho que esta é a conquista mais significativa no xadrez para computadores desde a partida Deep Blue de 1997. Atualizarei minha resposta assim que ler o artigo em detalhes.

Original (antes de dez de 2017)

Vamos esclarecer sua pergunta:

• Não, os motores de xadrez não usam força bruta.
• AlphaGo faz buscas uso árvore, ele usa Monte Carlo árvore de busca . Google " Monte Carlo Tree Search alphaGo " se você quiser se convencer.

A RNA pode ser usada para motores de xadrez:

• Girafa (o link postado por @Tim)
• NeuroChess

Esse programa teria um desempenho melhor do que os principais mecanismos de xadrez (e jogadores de xadrez) de hoje?

Giraffe é reproduzido no nível Master Internation, que é sobre a classificação FIDE 2400. No entanto, Stockfish, Houdini e Komodo estão no FIDE 3000. Essa é uma grande lacuna. Por quê? Por que não a Pesquisa em Árvores Monte-Carlo?

• A heurística material no xadrez é simples. Na maioria das vezes, uma posição no xadrez está ganhando / perdendo apenas contando os materiais no tabuleiro. Lembre-se de que a contagem de materiais não funciona no Go. A contagem de materiais é uma ordem de magnitude mais rápida que a execução de redes neurais - isso pode ser feito por painéis de bits representados por um número inteiro de 64 bits. No sistema de 64 bits, isso pode ser feito apenas com várias instruções da máquina. Pesquisando com o algoritmo tradicional é muito mais rápido que o aprendizado de máquina. Nós mais altos por segundo são traduzidos para uma pesquisa mais profunda.
• Da mesma forma, existem técnicas muito úteis e baratas, como poda de movimentos nulos, redução de movimentos tardios e movimentos matadores etc. Eles são baratos de executar e muito eficientes para a abordagem usada no AlphaGo.
• A avaliação estática no xadrez é rápida e útil
• O aprendizado de máquina é útil para otimizar parâmetros, mas também temos o SPSA e o CLOP para o xadrez.
• Existem muitas métricas úteis para a redução de árvores no xadrez. Muito menos para Go.

Houve pesquisas de que o Monte Carlo Tree Search não se adapta bem ao xadrez. Go é um jogo diferente para o xadrez. Os algoritmos de xadrez não funcionam para o Go porque o xadrez depende de táticas brutais. A tática é sem dúvida mais importante no xadrez.

Agora, estabelecemos que o MCTS funciona bem para o AlphaGo, mas menos para o xadrez. O aprendizado profundo seria mais útil se:

• A avaliação NN ajustada é melhor que os algoritmos tradicionais. No entanto ... o aprendizado profundo não é mágico, você como programador ainda precisaria fazer a programação. Como mencionado, temos algo como SPSA para jogar automaticamente para ajustar os parâmetros no xadrez.
• Investimento, dinheiro! Não há muito dinheiro para o aprendizado de máquina no xadrez. O Stockfish é gratuito e de código aberto, mas forte o suficiente para derrotar todos os jogadores humanos. Por que o Google gastaria milhões se alguém pode baixar o Stockfish gratuitamente? Por que vai pagar pelos clusters de CPU? Quem vai pagar por talentos? Ninguém quer fazer isso, porque o xadrez é considerado um jogo "resolvido".

Se o aprendizado profundo conseguir o seguinte, ele vencerá o algoritmo tradicional:

• Dada uma posição no xadrez, "sinta-a" como um grande mestre humano. Por exemplo, um grande mestre humano não entraria em linhas ruins - por experiência. Nem o algoritmo tradicional nem o aprendizado profundo conseguem isso. Seu modelo NN pode fornecer uma probabilidade [0..1] para sua posição, mas isso não é bom o suficiente.

Deixe-me salientar:

Não. O Giraffe (o link publicado por @Tim) não usa o Monte Carlo Tree Search. Ele usa o algoritmo regular nega-max. Tudo o que faz é substituir a função de avaliação regular por NN, e é muito lento.

mais um:

Embora Kasparov tenha sido derrotado pelo Deep Blue na partida de 1997. "Humanity" foi realmente perdido entre 2003 e 2005, quando Kramnik perdeu uma partida para Deep Fritz sem vitória e Michael Adams perdeu para uma máquina de cluster em uma partida unilateral. Naquela época, Rybka se mostrou forte demais até para os melhores jogadores do mundo.

Referência:

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

Eu cito:

No xadrez, temos o conceito de materialidade, que já fornece uma estimativa razoável do desempenho de um motor e pode ser calculado rapidamente. Além disso, existem muitos outros aspectos do jogo que podem ser codificados em uma função de avaliação estática que não poderia ser feita no Go. Devido às muitas heurísticas e boa avaliação, o EBF (fator de ramificação efetivo) é bastante pequeno. Usar uma rede neural como um substituto para a função de avaliação estática definitivamente atrasaria bastante o mecanismo.

O DeepBlue já venceu Kasparov, então esse problema é resolvido com uma abordagem muito mais simples. Isso foi possível porque o número de movimentos possíveis no xadrez é muito menor do que o esperado , por isso é um problema muito mais simples. Além disso, observe que tanto a NN quanto a força bruta precisam de enormes recursos de computação ( aqui você pode encontrar uma foto do computador atrás do AlphaGo, observe que ele usa nem mesmo as GPUs, mas as TPU para computação). O problema foi que, quando Deep Blue venceu Kasparov, a comunidade go argumentou que isso não seria possível com go (por muitas razões diferentes, mas para resumir os argumentos que eu precisaria dar uma introdução detalhada ao jogo de ir). Sim, você pode ensinar NN a jogar xadrez, Mario , ou tentar ensiná-lo a jogarStarcraft ...

Eu acho que a razão disso é que você simplesmente não ouve com frequência na grande mídia sobre casos em que as pessoas resolvem problemas que já foram resolvidos.

Além disso, sua premissa está errada, o Deep Learning é usado para jogar xadrez, por exemplo, conforme descrito em Deep Learning Machine Learns Xess in 72 Hours, Play at International Master Level . Veja também o artigo correspondente, Girafa: Usando o reforço profundo Aprendendo a jogar xadrez .