Qual foi a fonte de aleatoriedade no jogo Alpha Zero vs Stockfish?

7

Meu entendimento é que o algoritmo do Alpha Zero foi corrigido após a fase de "aprendizado"; portanto, ele apresentaria o mesmo movimento para todas as posições? A variabilidade na partida foi inteiramente devida a uma configuração do Stockfish ou o Alpha Zero também exibiu um elemento aleatório em sua seleção de movimentos?

engines computer-chess alphazero firtydank
fonte
2
A pesquisa de árvores de Monte Carlo usada pelo alfa zero parece bastante aleatória.
hoacin
11
Monte Carlo não é um algoritmo determinístico.
SmallChess
Meu entendimento é que o mcst foi usado na fase de "aprendizado" para treinar a rede neural, enquanto o algoritmo foi adiado para a correspondência real. Parece que estou perdendo um truque.
firtydank
3
Eu acho que mcts era usado o tempo todo.
hoacin
Outra possível, se de alguma forma a fonte improvável de variação for o tempo. Embora o mesmo tempo possa ser usado no mesmo movimento, sempre há alguma capacidade de levar um tempo diferente para fazer algum cálculo, portanto, talvez ele tenha sido executado um pouco mais rápido uma vez e depois o tempo mais rápido responder porque ficou mais longe do que o tempo mais lento.
Benji Altman

Respostas:

6

Notei que o AlphaZero jogou 1.d4 e 1.Nf3 em http://www.chessgames.com/perl/chess.pl?tid=91944&crosstable=1 . Possibilidades:

  • Mutlithreading (qualquer engenheiro de software pode dizer que não é determinístico)
  • Pesquisa em árvore Monte Carlo (o algoritmo desenha caminhos aleatórios, portanto, não pode ser determinístico)

Observe que enquanto os parâmetros do modelo são "fixos" (suas próprias palavras), a movimentação real pode ser diferente. Não temos o código fonte do AlphaZero, mas o multithreading e o MCTS provavelmente são dois casos principais.

SmallChess
fonte
11
O que você quer dizer com multiencadeamento não é determinístico? Isso não depende de como é usado. Podemos não saber qual thread termina primeiro, mas, na maioria das vezes, as pessoas tendem a (ou pelo menos tentam) ter cuidado para garantir que quaisquer inconsistências na ordem de execução das coisas não afetem o resultado final do programa.
precisa
@BenjiAltman eu escrevi que não temos código fonte. Você pode contribuir para sua própria resposta.
SmallChess
3
O multithreading nos motores de xadrez quase nunca é determinístico.
SmallChess
11
Os Threads do @BenjiAltman podem concluir o processamento e tempos diferentes. A menos que o programa aguarde, de alguma forma, que cada thread termine e os retorne deterministicamente , o resultado real pode depender de qual thread recebe prioridade mais alta pelo planejador.
11
@rec Correct. Aplicativos de alto desempenho, como o xadrez, não esperam o término dos encadeamentos (eles não são aplicativos de negócios!) E, portanto, determinísticos. Por exemplo, o Stockfish em execução em múltiplos núcleos é 100% não determinístico.
SmallChess
5

Os autores da LC0 estudaram o artigo AlphaZero com muito cuidado, fizeram seus próprios experimentos e chegaram à seguinte conclusão. O AlphaZero, apesar de chamar seu algoritmo de busca em árvore Monte Carlo (todos os métodos de Monte Carlo são por definição explicitamente aleatórios), não emprega nenhum não determinismo explícito após um certo número de jogadas (acredito que sejam 15 jogadas).

Existem duas partes diferentes no MCTS que podem introduzir aleatoriedade na seleção de movimentos.

  1. Durante a fase de pesquisa, o AlphaZero atribui pesos nos quais se move a explorar com base em 2 fatores: a probabilidade de vitória, conforme avaliada pela rede neural, e também algumas estatísticas de tamanho de subárvore do pai e do filho movem subárvores. O primeiro fator garante que as linhas mais promissoras sejam avaliadas primeiro, e o segundo fator garante que as linhas menos promissoras sejam eventualmente pesquisadas. Em uma implementação natural do MCTS, ele usaria escolhas aleatórias ponderadas entre essas possibilidades ponderadas. Na realidade, o AlphaZero escolhe entre estes completamente deterministicamente, apenas escolhendo o peso máximo de cada vez. Isso ocorre porque a aleatoriedade nesta etapa não se mostra útil e apenas distrai o mecanismo das variações mais importantes, em média.

  2. Durante a fase de mudança, ele pode fazer uma escolha ponderada entre os candidatos à mudança que já possuem avaliações profundas e precisas calculadas pela fase de pesquisa. A idéia é fazer movimentos levemente abaixo do ideal para tentar introduzir diversidade em seu jogo, para que ele não jogue o mesmo jogo todas as vezes. Isso é especialmente importante durante o treinamento, mas também leva a resultados mais interessantes da partida. Acontece que o AlphaZero só faz isso nos primeiros 15 movimentos, depois disso, sempre escolhe o melhor. Esse determinismo acaba sendo essencial para o seu jogo extremamente preciso no final do jogo, onde pequenas diferenças na avaliação acabam sendo a diferença entre empates e vitórias.

Isso é verdade durante o treinamento e a avaliação.

Em outras palavras, uma vez fora da abertura, seu jogo é tão determinístico quanto um mecanismo tradicional.

No entanto, observe que ele terá o mesmo tipo de multithreading e não determinismo de controle de tempo que os mecanismos tradicionais.

Benjamin
fonte