Então eu apenas sentei e admirei AlphaZero contra Stockfish . E agora voltei ao assunto relacionado com a tarefa de otimizar redes neurais, que às vezes tem de ser feita no trabalho (infelizmente, menos do que gostaríamos). Como me parece, essas tarefas podem estar intimamente relacionadas, então eu queria de alguma forma sistematizar minhas idéias.
O xadrez é um jogo com informações completas, baseado em uma enumeração de opções (bem como damas, go, etc.).
O problema, entretanto, é que a árvore de variação no xadrez cresce muito rápido (embora significativamente mais lenta do que no Go). Por exemplo, com um tabuleiro cheio de peças em uma posição tranquila, cada lado tem cerca de 10 continuações razoáveis. Assim, em apenas 3 movimentos de preto e branco (6 meios movimentos) podemos obter um milhão de posições com este. Além disso, vamos levar em conta que o jogo médio entre pessoas dura 40-50 movimentos (entre computadores - 80-100). Assim, chegaremos à conclusão de que um cálculo completo da árvore de variantes é impossível para a maioria das posições, o que significa que devemos nos concentrar no corte parcial da árvore de busca, tanto em largura quanto em profundidade. Agora vamos ver como os humanos e as máquinas lidaram com esse problema. Vou começar com uma pequena visão geral histórica.
"Protein Chess".
O xadrez é conhecido há cerca de 1400 anos, mas os primeiros grandes torneios começaram a ser realizados em meados do século XIX. Foi uma época de batalhas abertas e românticas. Os adversários tentaram introduzir rapidamente as peças na batalha, abrir a posição e iniciar um ataque ao rei. Ninguém considerou particularmente as concessões materiais e posicionais. Mas, surpreendentemente, o antagonista do xadrez romântico, Wilhelm Steinitz, tornou-se o primeiro campeão mundial oficial .
Ele lançou as bases para o jogo posicional . Em grande parte graças a Steinitz, passamos a operar com conceitos como “estrutura de peões”, “casas fortes e fracas”, “peças boas e ruins”. Foi isso que introduziu no xadrez o elemento da estratégia baseada em vantagens de longo prazo. Steinitz desenvolveu uma abordagem posicional e puniu implacavelmente seus oponentes por sacrifícios materiais e falhas posicionais. Emmanuel Lasker , que o sucedeu no trono do xadrez, falou muito bem do primeiro campeão : " O talento de Steinitz como jogador prático era menor do que o talento de Blackburn ou Zukertort, que ele mesmo assim derrotou, porque era um grande pensador, mas eles não eram ."Steinitz formulou os princípios básicos de avaliação de posição e os planos de jogo resultantes em uma linguagem de alto nível (neste caso, alemão).
Conseqüentemente, ele os disponibilizou para estudo por outras pessoas . Isso moldou o que chamamos de abordagem humana do xadrez. Levamos muito a sério a poda da árvore de variação do xadrez com base nos princípios posicionais. Alguns movimentos são descartados porque levam a uma posição ruim no horizonte calculado. Alguns porque levam a concessões de longo prazo, outros porque não têm objetivo. Como resultado, calculamos uma parte muito pequena das opções possíveis.
Uma maior compreensão do xadrez foi essencialmente um desenvolvimento das idéias estabelecidas pelo primeiro campeão. Surgiram conceitos como bloqueio, prevenção, dominação. Os jogadores de xadrez começaram a estudar os princípios de jogar posições típicas decorrentes de várias aberturas (correntes fechadas, um peão isolado, etc.). De uma forma ou de outra, foram estudadas posições próximas ao equilíbrio dos materiais. Mas também houve exceções - por exemplo, o jovem Mikhail Tal jogou em um estilo diferente. Ele criou posições desequilibradas agudas com uma violação da proporção de material (mais tarde Garry Kasparov também demonstrou um jogo semelhante) Não acostumados a esse tipo de jogo, os oponentes passaram um após o outro. Tal se tornou campeão mundial em 1960, mas perdeu a revanche um ano depois. Na segunda metade do século 20, o foco da pesquisa mudou para o início do jogo - a abertura. Com a mão leve de Mikhail Botvinnik (6º campeão mundial) e Garry Kasparov (13º), os jogadores de xadrez começaram a dedicar a maior parte do seu tempo para trabalhar em variações específicas de abertura. Cada vez mais usando computadores neste processo. Como resultado, muitas variações em aberturas populares são desenvolvidas até posições em que o resultado do jogo é predeterminado. Isso leva a uma certa emasculação do xadrez, bem como à necessidade de memorizar um grande número de variações para não ser derrotado já na abertura. Não é de surpreender que o pêndulo tenha oscilado na direção oposta recentemente. O atual campeão mundialMagnus Carlsen se esforça para obter não uma vantagem no final da abertura, mas uma posição de jogo que não seja “desgastada” pelos motores de computador. A gravidade da luta é transportada para as fases posteriores do jogo (meio-jogo, fim-de-jogo).
"Xadrez de Silicone".
Como Aleksandr Kronrod disse , o xadrez é a “mosca da fruta” da inteligência artificial. Seu estudo começou com o advento dos primeiros computadores e atraiu pioneiros como Alan Turing e Claude Shannon.... Foi Shannon quem apresentou a primeira estimativa do valor das peças de xadrez "Rei = 200, Rainha = 9, Torre = 5, Bispo = 3, Cavalo = 3, Peão = 1". Estranhamente, foi essa avaliação simples que determinou o desenvolvimento da programação do xadrez nos próximos 70 anos. Shannon também previu a divisão dos programas de xadrez em "rápido" (força bruta) e "inteligente" (inteligente). Programas "rápidos" percorrem completamente todas as opções possíveis até uma certa profundidade, avaliam a posição usando uma função de avaliação simples (como proporção de material) e selecionam o melhor movimento usando o princípio minimax... Os programas “inteligentes” usam algoritmos mais complexos e variam a profundidade de pesquisa da mesma forma que um ser humano. O 6º campeão mundial Mikhail Botvinnik esteve envolvido na criação de tal algoritmo nos últimos anos de sua vida. No entanto, sem muito sucesso, como muitos outros criadores de programas "inteligentes". Pois em sua terceira previsão, Shannon estava errado - os programas "inteligentes" falhavam constantemente na luta contra os "rápidos". A razão é que a força bruta é muito bem paralelizada e otimizada. E a estimativa simples de Shannon revelou-se bastante estável e robusta. Pois, como os jogadores de xadrez sabem, qualquer vantagem posicional mais cedo ou mais tarde se transformará em vantagem material. Enquanto os princípios de avaliação de posições se prestam a uma formalização muito pior.
Eles exigem cálculos sequenciais complicados e são mal otimizados. Como resultado, com o aumento do desempenho do computador, os programas "rápidos" começaram a dominar. É assim que a corrente principal do xadrez de computador foi formada, que é notavelmente diferente dos humanos - estourando a uma certa profundidade usando corte alfa-beta (e algumas outras heurísticas) e estimativa de posição de acordo com Shannon. Além disso, os programas começaram a desenvolver ativamente e usar bases de abertura (quando o jogo ainda não se distanciou da posição inicial) e final (quando o número de peças é pequeno e a árvore de variações pode ser calculada completamente). E o desempenho dos computadores crescia o tempo todo, e os programadores também não ficavam parados, otimizando os motores constantemente. Em 11 de maio de 1997, um evento que marcou época ocorreuO computador Deep Blue derrotou o campeão mundial Garry Kasparov em uma partida de 6 jogos.
Imediatamente depois disso, a IBM encerrou esse projeto nunca barato. Chips que aceleram os cálculos do xadrez foram criados especialmente para o Deep Blue ! Porém, mesmo sem eles, a superioridade de um computador sobre uma pessoa já era óbvia. Deep Fritz , Deep Junior , Rybka , Komodo , Stockfish começaram a esmagar impiedosamente os grandes mestres, até lhes dando material à frente ... Entre eles, no entanto, eles jogaram com sucesso variável - os resultados dos campeonatos mundiais entre os programas podem ser encontrados aqui .
Tudo mudou quando os criadores do AlphaZero, depois de derrotar o campeão mundial no jogo de Li Sedol , finalmente começaram a jogar xadrez. O resultado foi fenomenal - depois de 4 horas brincando comigo mesmoAlphaZero derrotou StockFish vencendo 28 jogos e empatando 72. Depois de um ano, DeepMind fez um experimento mais limpo , permitindo que Stockfish usasse os livros de abertura e final de jogo. E ainda assim o resultado +155 -6 = 839 não deixa dúvidas sobre quem é o jogador mais forte do mundo no momento.
Vamos entender como arranjou esse novo milagre. (Para aqueles que desejam se aprofundar em scripts python, já existe um livro inteiro ). O algoritmo principal é a pesquisa em árvore de Monte Carlo... É claro que isso é um exagero, o que torna o AlphaZero semelhante a outros programas de xadrez. Mas a palavra Monte Carlo não deve ser enganosa - a pesquisa é controlada por uma rede neural (para Go era de 80 camadas, não sei qual aqui) e tem um foco restrito. AlphaZero apara a árvore de força bruta para considerações posicionais, assim como um humano faz! Comparado com Stockfish, Alphazero passa por quase 1000 vezes menos opções... Ela pega muito menos "lixo", mas calcula as opções mais fortes mais provavelmente com mais profundidade e precisão. Portanto, ele ganha mesmo com menos tempo ou em hardware mais fraco. E o mais importante é que AlphaZero "estudou" xadrez exclusivamente com "sua própria experiência". Ela não tinha informações a priori. Sua "compreensão" não foi manchada pela "avaliação de Shannon". Ela tem sua própria compreensão única da visão do xadrez e do estilo de jogo, que muitas vezes ignora o equilíbrio material (como o jovem Tal!).
Que conclusões podemos tirar dessa experiência maravilhosa?
- Ele refuta decisivamente todas as considerações sobre a emasculação do xadrez. A própria aparência de um jogador que joga em um estilo nunca antes visto e demonstra total superioridade sobre os concorrentes indica que as possibilidades do jogo estão longe de se esgotarem.
- . 4 (« ») ! – ( -) . . . AlphaZero () .
- – ? – , , .. , . AlphaZero – – –. ? , , . , . . . . SkyNet ficará um pouco menos distante e um pouco mais sinistro ... Nesse ínterim, agradeceria os links, artigos e ideias de como abordar este problema.
PS. Mas você vai assistir aos jogos . Tive um prazer incomparável.