'Othello' foi resolvido?
(arxiv.org)- Foi comprovado computacionalmente que, no Othello/Reversi 8×8, o resultado final é empate quando ambos os lados jogam perfeitamente, o que, segundo os pesquisadores, coloca o jogo em um estado de solução fraca
- O espaço de busca permaneceu muito mais difícil do que em casos já resolvidos, como checkers, já que se estima cerca de 10^58 registros de partidas possíveis e cerca de 10^28 posições de tabuleiro
- Este resultado obteve o valor teórico do jogo da posição inicial e uma estratégia para alcançar esse valor, mas não é uma solução forte que calcula todas as posições intermediárias
- Os pesquisadores explicam que usaram busca heurística baseada em software de Othello e alpha-beta search, e que a escala de busca necessária para uma solução precisa foi menor do que previsões anteriores
- Os dados brutos e programas para reproduzir o resultado foram publicados no GitHub, Zenodo e figshare, podendo servir como um caso verificável para pesquisas sobre resolução de jogos puramente estratégicos
Solução computacional de Othello
- O Othello no tabuleiro 8×8 foi fracamente resolvido, e o valor teórico do jogo da posição inicial foi calculado como empate
- Se ambos os lados jogarem da melhor forma possível, sem erros, o jogo termina empatado, e este estudo comprovou isso computacionalmente
- A Figure 1 apresenta um exemplo de registro de partida ótimo e o resultado final
- Se houver qualquer desvio dessa sequência em qualquer momento, o software dos pesquisadores garante empate ou vitória para o lado adversário
- Esse resultado coincide com a previsão feita por especialistas humanos em Othello, então os pesquisadores consideram que o resultado em si não é surpreendente
Escopo da solução e valor teórico do jogo
- Resolver um jogo de informação completa significa determinar o resultado final quando ambos os lados fazem jogo perfeito, ou seja, o valor teórico do jogo
- Jogos resolvidos normalmente são divididos em três níveis
- Solução ultra-fraca (ultra-weakly solved): quando se conhece apenas o valor teórico da posição inicial do tabuleiro
- Solução fraca (weakly solved): quando se conhece o valor teórico da posição inicial e também uma estratégia para que ambos os lados alcancem esse valor com recursos computacionais razoáveis
- Solução forte (strongly solved): quando se calcula o resultado de todas as posições possíveis que podem surgir durante a partida
- Este estudo é um caso de solução fraca para Othello, e não uma solução forte que calcula todas as posições possíveis
- Checkers também é apresentado como um jogo fracamente resolvido nesse mesmo sentido
Por que Othello demorou tanto
- Othello é um jogo popular com grande profundidade estratégica; foi inventado na Inglaterra no século 19, depois se difundiu amplamente em sua forma atual no Japão no século 20, e é jogado no mundo todo
- O campeonato mundial é realizado anualmente desde 1977, mostrando sua popularidade global
- O espaço de busca é extremamente grande
- em média, cerca de 10 jogadas por posição
- em média, cerca de 58 jogadas por partida inteira
- cerca de 10^58 registros de partidas possíveis
- cerca de 10^28 posições de tabuleiro possíveis
- Essa escala é apresentada como muito maior do que a dos jogos difíceis já resolvidos até agora, especialmente checkers
- Por causa desse grande espaço de busca, Othello permaneceu por muito tempo como um desafio de longo prazo na ciência da computação
Método de busca e eficiência computacional
- Os pesquisadores usaram alpha-beta search com o objetivo de obter uma solução fraca
- Os algoritmos de resolução de jogos variam conforme o objetivo e a natureza do jogo
- para solução fraca, alpha-beta search é frequentemente usada
- para solução forte, retrograde analysis é frequentemente utilizada
- para quebra-cabeças com sequências de solução muito longas, foram desenvolvidos métodos como df-pn search
- Alpha-beta search é um algoritmo que percorre o grafo do jogo sequencialmente em profundidade, então apenas paralelizar de forma simples não aumenta muito a eficiência da busca
- Vários métodos foram estudados para busca paralela
- em ambientes de memória compartilhada, YBWC e Lazy SMP são métodos populares
- em ambientes de memória distribuída, APHID e ABDADA são apresentados como algoritmos relacionados
- Em ambientes de memória distribuída, condições como largura de banda e latência entre nós variam bastante, então os desenvolvedores podem precisar escolher um algoritmo adequado ao ambiente ou criar um novo
- Mesmo com clusters de computadores modernos, resolver Othello continuava sendo uma grande barreira, e o avanço veio do aumento de eficiência na busca ao modificar software moderno de Othello
Outros jogos resolvidos e possibilidades de uso
- Antes de Othello, o caso recente apresentado como grande desafio resolvido era checkers
- Jogos não triviais como Connect Four, Qubic, Go-Moku, Nine Men’s Morris e Awari também são listados como casos resolvidos
- A dificuldade de resolver um jogo costuma depender fortemente do número de posições ou situações possíveis dentro dele
- Resolver um jogo não serve apenas para revelar o resultado final, mas também pode ser usado para geração de puzzles com base nesse jogo
- Os pesquisadores fornecem os dados brutos e os programas para reprodução no GitHub, Zenodo e figshare
1 comentários
Opiniões no Hacker News
Diz que “entre 2.958.551 posições, foram escolhidas 2.587 posições para formular uma hipótese sobre o resultado; se todas essas hipóteses estiverem corretas, isso prova que a posição inicial é empate”, mas não há uma explicação mais detalhada
Soa menos como se o jogo tivesse sido completamente resolvido e mais como se o autor tivesse procurado com bastante afinco uma sequência vencedora, mas não a tivesse encontrado
O texto diz que “há muitas formas de escolher um subconjunto capaz de provar que a posição inicial é empate, mas obtivemos um subconjunto pequeno com o Algorithm 1”
O Algorithm 1 é descrito como algo que recebe as pontuações previstas de todas as posições com 50 casas vazias e retorna um subconjunto tal que, se todas as posições desse subconjunto forem resolvidas e as soluções coincidirem com as previsões, então a posição inicial também acaba resolvida
No geral, a redação do artigo não é intuitiva. O autor pode estar certo, mas acho que seria preciso sentar com calma e seguir a lógica; minha primeira impressão é de ceticismo
Esse tipo de prova existe em outros lugares. Por exemplo, o teorema das quatro cores também foi reduzido a um número finito de configurações e depois verificado manualmente por coloração
O script em https://github.com/eukaryo/reversi-scripts/blob/main/reversi... joga perfeitamente assumindo que tudo está correto. Outros scripts do repositório usam os dados calculados a partir das soluções de posições com 36 casas vazias, e isso parece viável até em uma máquina comum
Essencialmente, a estrutura parece consultar uma tabela de até 300 GB contendo todas as posições com 37 a 64 casas vazias alcançáveis a partir da solução fraca, e resolver posições com 36 casas vazias ou menos usando o
-solvedo edaxOthello é um bom jogo para mostrar o quanto é possível ficar forte usando apenas heurísticas básicas
À medida que a partida avança, há casas em que você jamais deve jogar, e outras em que, se possível, você deve jogar
Só implementar regras desse tipo já cria um adversário bem razoável, e é interessante ver como as pessoas atribuem “inteligência” tão rapidamente até a coisas muito simples
Ele dizia que colocaram para jogar um app com heurísticas simples parecidas contra outro app igualmente simples, mas desastrosamente ruim, com a estratégia de “virar o maior número de peças”
O algoritmo heurístico venceu de lavada; lembro de algo como 60 a 4, ou até pior
Quando restavam 19 casas vazias, ele resolvia completamente o restante da partida, e isso era bem impressionante
Othello era um jogo que existia até em aparelhos LCD de US$ 10 com duas pilhas AA
Se você se interessa pelo jogo, o Campeonato Mundial de Othello, popular também entre pesquisadores de ciência da computação e inteligência artificial, está acontecendo agora em Roma, na Itália
As partidas são transmitidas ao vivo em liveothello.com e no YouTube @WorldOthello
Pergunto-me se Othello é um jogo em que a maioria das partidas de alto nível termina em empate, como em damas
Legal
Há uns 15 anos, resolvi um jogo mais simples que eu jogava com meu irmão. Era um jogo africano com cerca de 10 buracos de cada lado do tabuleiro, contendo pedras
Escrevi um motor alfa-beta e ele descobriu uma estratégia absurda que sempre vencia, adaptada às regras que usávamos. Depois disso, de repente passei a ganhar todas as partidas, e meu irmão nunca mais quis jogar comigo. Foi o típico duelo entre um cientista da computação e um optometrista
Há muito a aprender vendo africanos mais velhos jogarem Mancala. Eles jogam muito rápido, e fica uma sensação meio de pôquer, em que a trapaça faz parte do jogo
Se você espalhar as pedras rápido o bastante, pode pular uma tigela ou deixar cair uma pedra a mais para obter vantagem
Eu não sou tão habilidoso assim e jogo com a família, então não trapaceio. Ainda assim, vira um jogo muito diferente. É como a diferença entre senhoras inglesas jogando Mahjong lentamente enquanto tomam chá e pessoas apostando dinheiro em um cassino chinês
Se ganham demais ou perdem demais, deixam de aproveitar o jogo
Mas não sei que relevância a profissão de optometrista tem aqui
Isso é real? Parece um pouco estranho que o autor seja uma única pessoa e afiliado a uma startup de deep learning da qual nunca ouvi falar
Imagino que esteja passando por revisão por pares?
E Othello não está exatamente no mesmo nível da hipótese de Riemann. Ele era menos pesquisado, e pode ter havido algum fruto baixo ainda disponível
Othello é um dos melhores jogos para jogar com crianças pequenas
As regras são simples, há padrões que dá para aprender, e também é divertido virar um monte de peças de uma vez. Acima de tudo, é igualmente divertido não só para crianças, mas também para adultos
Eu conseguia me divertir bastante sem esmagar uma criança de 6 anos, e sem parecer um jogo simples baseado só na sorte
https://mancala.fandom.com/wiki/Hus
Em teoria não há sorte, mas na prática não dá para calcular tão longe por causa das reações em cadeia
O tabuleiro é fácil de fazer por conta própria
Se quiser experimentar o jogo, deixei no ar algo que fiz com meus filhos: https://jawj.github.io/fliptiles
O jogador de “IA” é bem fraco
Aprendi um jogo novo
O computador fez 33 pontos, eu fiz 31
Se você acha Othello trivial, experimente Zebra
Site do autor original: http://radagast.se/othello/
Código-fonte no GitHub: https://github.com/hoshir/zebra
O que eu gosto em Othello é a contradição entre ação e território
Durante a partida, o ato de fazer uma jogada no meu turno é, em certo sentido, prejudicial para mim, mas ainda assim sou obrigado a jogar
Por isso, até chegar o momento em que o espaço fica pequeno demais e é preciso recuperar influência clara, é preciso ocupar posições mantendo-se pequeno e no interior
Relacionado a isso, também há uma versão para jogar Reversi 6x6 perfeitamente
https://mame.github.io/6x6-reversi-oracle/
Fonte: https://twitter.com/mametter/status/1476379841004183556
Eu não sabia até agora que o 8x8 ainda não tinha sido resolvido