o que acontece quando aplicamos tecnologias modernas de ponta para o velho jogo de xadrez? E o que acontece quando um cromo entediado com um excesso de poder computacional realiza as suas próprias experiências caseiras estranhas no jogo?
este ano um engenheiro de software da Pensilvânia que se chama Tom Murphy VII decidiu criar alguns algoritmos de jogo de xadrez ruidosamente ruim usando tudo, desde a aprendizagem de máquinas e redes neurais a uma quantidade gratuita de ciclos de CPU — e, em seguida, colocou os algoritmos maus uns contra os outros para criar um “torneio de tolos”.”
” it’s my idea of fun… ” Murphy diz em um vídeo humorístico descrevendo as experiências.
os primeiros movimentos
Murphy tem a capacidade cerebral para fazê-lo. Ele nos diz que em 2007 ele defendeu seu doutorado em Ciência da computação. no Carnegie Mellon – que foi o mesmo ano em que os estudantes começaram a realizar a conferência anual SIGBOVIK no Dia Das mentiras. Patrocinado pela” Association for Computational Heresy”, era uma espécie de grupo de interesse especial satírico dedicado a um pesquisador fictício chamado” Harry Quizmaster Bovik”, e incluindo uma chamada para papéis Patetas sobre temas como “estupidez artificial”.”
nos últimos 11 anos, Murphy tem sido um engenheiro de software sênior da Google (em seus escritórios em Pittsburgh). Mas este ano ele decidiu voltar novamente para a Conferência do Dia Das mentiras — e novamente, contribuiu com alguma pesquisa humorística de sua autoria.Murphy gaba-se orgulhosamente de que algumas de suas apresentações anteriores envolveram investigações ridículas que eram “indistinguíveis da pesquisa ‘real’ (por exemplo, o primeiro nível de Super Mario Bros.é fácil com ordenamentos lexicográficos e viagens no tempo tem cerca de 20 citações na pesquisa acadêmica ‘real’).
mas este foi o ano em que Murphy virou sua atenção para o xadrez.
que os jogos comecem
no jogo inicial de Murphy, os jogadores humanos são vendados, forçando-os a lembrar onde as peças estão. Mas qual é o equivalente a um computador? Dizendo-lhe onde as peças estão localizadas, mas não quais as peças que são (ou até mesmo de que cor)…
é claro, o computador também não seria fornecido com os movimentos que levam a uma posição. Nem saberia de quem era a vez. Sim, há a possibilidade de o rei do computador estar sob controlo.nessa altura, praticamente todos os movimentos são ilegais, excepto um movimento que leva o seu rei à segurança. Mas para contornar isso, Tom criou um programa que gera uma lista de possíveis movimentos, classificados por ordem de preferência — dos quais o primeiro movimento legal será escolhido.
“eu gosto de jogar contra ele, porque não é muito bom”, diz Murphy no vídeo. “Mas a questão natural é como não é muito bom?”Testá-lo contra programas de xadrez prova que sim, ele perde com grande regularidade — como em, “todas as vezes.”
em seguida, ele partiu para construir outros algoritmos de jogo de xadrez ruim, para que ele pudesse comparar sua performance relativa…
um tinha uma preferência para colocar suas peças nos quadrados brancos quando está jogando branco, e nos quadrados negros quando está jogando Preto. (O seu adversário? Um algoritmo que preferiu colocar as suas peças em quadrados de cores opostas.) No final, ambos jogaram muito mal. “Eles têm preferência, mas não tem a ver com ganhar.”Na verdade, ambos são um pouco piores do que o algoritmo que escolhe os seus movimentos aleatoriamente.
se acham o meu intrincado vídeo de 42min sobre 30 algoritmos de xadrez estranhos a competir num torneio de tolos para avaliar o meu programa que joga xadrez sem saber que peças estão no tabuleiro são aborrecidas, então é porque não compreendem a arte.:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) de julho de 15, 2019
houve também dois algoritmos deu o nome de “Huddle” e “Enxame” — em que um automatizado jogador procura se move mantendo suas peças, perto de seu próprio rei, enquanto o outro procura move a colocação de suas peças, perto de seu rei adversário. Isso às vezes leva ao rei Huddle ser forçado a seguir seus próprios peões em toda a linha, onde pelo menos alguns casos seu peão, em seguida, acidentalmente promovido em peças mais poderosas e inadvertidamente xeque-mate o rei adversário.
mas mais frequentemente, funciona da outra maneira. “Se você tem uma preferência para atacar o adversário, você vai acidentalmente xeque-mate às vezes.”No vídeo, Murphy revela que entre os algoritmos de xadrez ruim, este é surpreendentemente não-tão-ruim. “‘Enxame’ é de fato muito melhor do que ‘ movimento aleatório.'”
e mais uma estratégia bem sucedida é um algoritmo que prioriza quatro tipos específicos de movimento (nesta ordem): xeque-mate, xeque, captura uma peça, ou empurrar para o território do adversário.
mas existem outras ideias terríveis-como um algoritmo que procura espelhar as peças do adversário, ou mover todas as suas peças para o outro lado do tabuleiro. Um algoritmo simplesmente escolhe o movimento que vem primeiro em ordem alfabética.
E não há outro algoritmo, onde cada passo é escolhido a partir de uma lista de movimentos possíveis — com as escolhas arbitrariamente pelos dígitos de pi…
Sobrevivência em Chessland
Mas, em última análise, a sua mais elaborada algoritmo começou com uma pergunta: que peça de xadrez é mais provável de “sobreviver” – permanecer no tabuleiro até o final do jogo, e sair vitorioso com todas as suas outras peças de xadrez? Investigando a resposta, Murphy fez uma visita ao site de xadrez livre/libre. LiChess.org (que agora vê mais de um milhão de jogos por dia). Ele também oferece jogos para download — assim Murphy baixou todos 506,000,416 deles.
he resumed the results in a paper called “Survival in Chessland,” which explains his methodology. Murphy baixou todos os jogos completos que tinham até novembro de 2018 — embora outros 200 milhões aparentemente se tornaram disponíveis nos oito meses desde então. Mesmo seu lanço de novembro representou um enorme 875GB de jogos de xadrez, “então o processamento destes teve algum cuidado com a eficiência e o paralelismo”, diz Murphy no vídeo.
“felizmente, eu tenho um computador com apenas um número obsceno de núcleos e RAM realmente excessivo, então você tem que usar isso para alguma coisa.”
Er, how obscene? In an email, he describes his “gratuitous” home system, a 32-core AMD ThreadRipper 2990WX. Executar os programas C++ multi-threaded por algumas horas foi suficiente para crunch através de todo o conjunto de dados. “Eu acho que as pessoas subestimam o que você pode fazer eficientemente com uma única máquina!”
“O trabalho envolvido é muito simples: Eu analisar o PGN (que descreve o jogo) e, em seguida, executar os movimentos no jogo, manter o controle do destino de cada peça e, em seguida, soma a conta para cada destino…”
“basicamente, eu escrevi todo o código a partir do zero, porque isso é mais divertido do que ficar o código de outras pessoas para o trabalho. :)”
de Murphy “sobrevivência” de análise criado alguns realmente belos efeitos visuais dos dados, mostrando a probabilidade de sobrevivência para cada peça de xadrez em cada uma das 64 casas (com as cores indicando a sua probabilidade de estar no quadrado no final do jogo.)
e então isso levou a mais algoritmos de jogo de xadrez. Primeiro, há aquele que apenas move pedaços para aqueles quadrados onde eles são estatisticamente mais propensos a sobreviver. Ou simplesmente para os quadrados onde eles são mais propensos a estar no final de um jogo. E outros algoritmos fazem as peças em movimento oposto exato para quadrados onde eles são menos propensos a sobreviver (ou acabar). Dois algoritmos calculam qual quadrado tem a maior taxa de sobrevivência (versus taxa de captura) para uma peça em cada quadrado, com um algoritmo buscando a maior razão favorecendo a sobrevivência — e o algoritmo “fatalista” buscando a menor proporção.
“estranhamente, ele tem as melhores chances de ganhar destas estratégias.”
e finalmente, ele decidiu compará-los todos ao motor de xadrez Stockfish em vários níveis (incluindo um algoritmo especial onde é forçado a jogar seu movimento menos promissor). “Olhando para os resultados, sem surpresa, esta é a pior estratégia geral, e consegue perder para quase todos.”
But remember Tom’s original “blinded” algorithm, which didn’t know which piece occupied a square (or even its color)? Ele decidiu aumentá — lo com uma rede neural, que realizou o aprendizado de máquina-usando os bilhões de posições disponíveis nos jogos de LiChess.organizacao. Foi agora capaz de prever correctamente as peças em cada posição com 100% de precisão…cerca de um quinto do tempo. E mesmo quando está errado, é apenas incorretamente adivinhado uma média de 3,22 peças para cada posição.
And this becomes a jumping-off point for even more wild calculations. Em algum momento, ele deduziu que todos os jogos em seu banco de dados eventualmente passam por 21.553.382.902 posições únicas. Com 204GB você poderia armazená — los todos — junto com o próximo movimento-mas há outra estatística interessante. 76% das vagas ocorreram exatamente uma vez. “Então estes ocupam um monte de espaço, e não são muito úteis para jogar, porque eu sou muito improvável de vê-los novamente.”Jogando fora essas posições pontuais, qualquer outra posição de jogo possível pode ser armazenada com cerca de 500MB de memória. Isto pode ser facilmente convertido em um algoritmo que joga o movimento mais popular para qualquer posição que ele encontra (enquanto troca em um movimento aleatório se ele acontece encontrar-se preso em uma posição única).
mas então há um truque fácil para vencê-lo. “Assim que faço um movimento estranho, começa a tocar aleatoriamente. E depois é muito fácil de vencer.”
A final experiment involves various “dilutions” of the Stockfish engine — in which its preferred move is replaced by a randomly-chosen move x percent of the time.”
“Nós, na verdade, pode avaliar o quão bom um jogador é agora comparando-lo diretamente a uma determinada diluição de Bacalhau…”
afinal de Murphy elaborar xadrez algoritmos tinha sido devidamente testado, ele resumiu os resultados de uma enorme mesa, e triunfante concluiu seu vídeo anunciando que ele estava finalmente pronto para perseguir outros interesses.
” Now it’s on to the next project, which is teaching this dog how to play chess.”
- o que acontece quando o aprendizado de máquina leva a humanidade a respostas que não entendemos?Apresento-te a Sophie, a robô que faz macarrão.Após 15 anos, pesquisadores desvendam um braço artificial que pode sentir.