Implementação de números surreais para jogos

11

Há uma construção muito agradável por Conway de números surreais. São "números" que contêm números reais e ordinais, são totalmente ordenados e têm todas as propriedades de um campo (exceto que eles não formam um conjunto, mas uma classe).

Veja, por exemplo, este pdf ou Wikipedia para uma introdução.

Eles podem ser ainda mais generalizados para os chamados "jogos", que foram originalmente introduzidos para estudar jogos combinatórios. A motivação original de Conway era analisar o jogo de Go , em particular o final de jogo é especialmente adequado para ser modelado com "jogos surreais".

Minha pergunta é: você sabe se alguém implementou essa abordagem em uma IA (ou seja, jogador de computador) para melhorar seu nível em um jogo? Estou especialmente interessado no caso do Go, mas também em outros. Caso contrário, existe um obstáculo ou uma razão pela qual não seria uma boa ideia?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Denis
fonte
1
De acordo com o livro "Mathematical Go", parece que existia um programa complementar de Raymond Chen para resolver os problemas de final de jogo do livro, mas não sei onde ele pode ser encontrado. Também tenho uma vaga lembrança da referência de Berlekamp ao "Go explorer", que pode ser mencionada no artigo "Smart game board and go explorer: um estudo em software e engenharia do conhecimento". No entanto, não acho que a teoria combinatória dos jogos seja realmente usada nos principais programas de execução do Go.
Mark S.
3
Se bem me lembro (talvez não como era há muito tempo), de acordo com David Wolfe (co-autor do Mathematical Go), pode-se inventar posições de final de jogo em que os melhores jogadores profissionais tendem a jogar de maneira não ideal tanto como ponto, enquanto a abordagem da teoria dos jogos de Conway / Berlekamp / Wolfe permite calcular o ideal com relativa facilidade. No entanto, essas posições são inventadas. Esse fenômeno é raro em jogos que surgem no jogo real.
Neal Young

Respostas:

8

Não tenho uma resposta para sua pergunta sobre se a teoria dos jogos de Conway foi usada na criação de programas de jogos, mas ainda assim você pode estar interessado no Combinatorial Game Suite ", um programa de código aberto para ajudar na pesquisa em combinações teoria dos jogos "(que eu aprendi aqui pela primeira vez ). Inclui uma implementação de várias operações padrão nos jogos Conway de forma canônica, além de uma linguagem de script para descrever novos jogos.

Noam Zeilberger
fonte
3

em algumas pesquisas, parece não haver muitas implementações gerais publicadas de números surreais. aqui está uma implementação de números surreais no coq .

  • Números surreais em coq / Mamane, TYPES'04 Anais da conferência internacional de 2004 sobre tipos de provas e programas

    Os números surreais formam um campo totalmente ordenado (comutativo), contendo cópias dos reais e (todos) os ordinais. Codifiquei a maior parte da estrutura em anel dos números surreais em Coq. Essa codificação depende da codificação da teoria dos conjuntos de Aczel na teoria dos tipos.

    Este artigo discute, em particular, os pontos de definição ou de prova em que eu tive que divergir da maneira de Conway ou da maneira mais natural, como a separação da recursão indutiva-recursiva simultânea em duas induções, transformando a definição da ordem em uma definição mutuamente indutiva de "no máximo" e “pelo menos” e ajustando os complicados esquemas de indução / recursão à teoria de tipos de Coq.

existem algumas implementações parciais da aritmética surreal para um jogo chamado hackenbush (Davis) popularizado por Conway, Berlekamp e Guy, das quais existem algumas referências.

O Go é de fato uma das áreas de ponta da pesquisa em IA de jogos (considerada significativamente mais difícil que o xadrez que ocupou a IA por décadas), mas parece que há pouca pesquisa especificamente sobre o uso de números surreais para modelá-lo / jogá-lo. O Go é considerado uma fronteira para os algoritmos de aprendizado de máquina / IA porque também possui um status / distinção relativamente exclusivo, pois os melhores algoritmos baseados em software ("ainda / atualmente") não superam os jogadores humanos campeões.

veja este artigo The Mystery of Go, o jogo antigo que os computadores ainda não podem vencer (Wired mag) para uma pesquisa aproximada decente das técnicas / pesquisadores / leads atuais da Go AI.

vzn
fonte