Complexidade do hexadecimal com ordem de rotação aleatória.

Eu estive pensando em uma variante do hex , onde, em vez de os dois jogadores fazerem movimentos alternadamente, cada turno que um jogador escolhido aleatoriamente faz um movimento. Quão difícil é determinar as chances de cada jogador vencer? Obviamente, esse problema está no PSPACE, mas não pode ser difícil para o NP, muito menos completo para o PSPACE. As dificuldades vêm de como a aleatoriedade torna impossível para um jogador ser forçado a fazer uma escolha entre opções; se esse jogador tiver sorte, ele tiver movimentos suficientes duas tomarão as duas opções e, se o jogador tiver azar, o oponente terá movimentos suficientes para bloquear as duas opções. Por outro lado, não consigo pensar em nenhum algoritmo de tempo polinomial para isso.

cc.complexity-theory board-games Itai Bar-Natan
fonte

Seja S uma sequência binária de n bits que representa qual jogador está no turno. Na pior das hipóteses, você recupera o jogo hexadecimal padrão se a sequência aleatória for 010101 ... ou 101010 .... Portanto, seu problema é pelo menos tão difícil quanto o hexadecimal padrão.

Mohammad Al-Turkistany

Existem duas interpretações possíveis deste jogo. (1) Pouco antes de cada turno, os jogadores jogam uma moeda para determinar quem será o próximo. (2) No início do jogo, os jogadores jogam uma moeda

vezes (em um tabuleiro de tamanho

) e usam essa sequência nos seus turnos. O Turquistanês parece estar assumindo o modelo (2); a pergunta original é ambígua, mas, de acordo com algumas de suas palavras, eu acho que Itai está perguntando sobre (1), o que pode ser mais fácil do que o hexadecimal padrão.

n^{2}

$n^2$

n

$n$

quer

Na verdade, quero dizer a primeira interpretação, que a moeda é lançada logo antes da jogada. Além disso, notei outra ambiguidade na minha pergunta: a precisão na qual quero saber a probabilidade. Embora tenha deixado a impressão ao perguntar o problema, quero saber a probabilidade com precisão total, mas quero saber apenas a probabilidade com precisão logarítmica. Como a diferença entre PP e BPP, a última parece mais útil e natural.

Itai Bar-Natan

@ Itai: Outra pergunta. Por que você afirma que isso está obviamente no PSPACE? Parece-me que é um jogo arbitrado, o que significaria que o limite superior da teoria da complexidade natural é EXPTIME. Veja Feige e Kilian, "Tornando os jogos curtos".

quer

@tukistany Useless NÃO implica trivial!

Jeffε 22/10/10

Respostas:

Você pode querer ler o artigo "Jogos com giros aleatórios e outros jogos de seleção", de Yuval Peres, Oded Schramm, Scott Sheffield e David Wilson. Desde a introdução:

"O Hex de Turno Aleatório é o mesmo que o Hex comum, exceto que, em vez de turnos alternados, os jogadores jogam uma moeda antes de cada turno para decidir quem deve colocar a próxima pedra. Embora o Hex comum seja famoso por ser difícil de analisar, a estratégia ideal para o Random -Vire Hex acaba sendo muito simples. "

Então, de fato, sua intuição estava certa: isso será no BPP (ou talvez P).

Peter Shor
fonte

Estou surpreso que as pessoas tenham realmente trabalhado nisso :) Boa referência!

precisa

É uma prova muito boa também. Acho que ouvi Scott Sheffield mencioná-lo em uma de suas palestras (mas depois esqueci completamente até aparecer no Google).

Peter Shor

Além disso, o site do David Wilson na verdade tem um aplicativo que permite que você jogue aleatório-turn Hex (contra a sua estratégia publicado, eu acredito): dbwilson.com/#software

Andy Drucker

Em sua última visita a Israel, inspirado no jornal da PSSW, Oded Schramm e eu jogamos algumas rodadas de xadrez aleatório para perceber que não é um jogo particularmente interessante.

Gil Kalai

Acontece que há uma conexão notável (devido a David Richman) entre jogos de turno aleatório e jogos de lances , em que os jogadores fazem lances para a próxima jogada; consulte arxiv.org/pdf/0812.3677.pdf e users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf Essa conexão permite um jogo essencialmente ideal da licitação Hex, usando o trabalho de Peres et al. Gosto disso porque os jogos de lances são, pelo menos ostensivamente, sem sorte, e acho que dar lances em Hex seria mais satisfatório do que jogar em turnos aleatórios. (Lance de cada turno pode ser uma tarefa maddeningly exigindo, no entanto.)

Andy Drucker