Considere as informações completas sobre jogos combinatórios para dois jogadores que terminam após um número polinomial de jogadas e, de maneira alternada, os jogadores escolhem um número finito de jogadas permitidas. A pergunta usual é: quão difícil é distinguir de uma determinada posição o vencedor. Outra seria: quão difícil é escolher uma jogada vencedora de uma posição vencedora. (Aqui eu chamo uma jogada de ganhar, se a posição continuar ganhando depois de jogá-la.) Para diferenciar, chamarei a antiga POSITION-COMPLEXITY e a segunda MOVE-COMPLEXITY.
É fácil ver que, se a MOVE-COMPLEXITY está em ou P S P A C E , o mesmo ocorre com a POSITION-COMPLEXITY - podemos calcular os movimentos ideais e verificar quem vence no final. (Eu realmente não pensei no que acontece se a MOVE-COMPLEXITY estiver em N P , provavelmente a POSITION-COMPLEXITY está em algo como P N P. ) No entanto, existem exemplos fictícios em que a MOVE-COMPLEXITY é trivial e a POSITION- A COMPLEXIDADE é arbitrariamente difícil - como o jogo (não muito interessante) de verificar qual é a saída de um algoritmo, com os jogadores dando os próximos passos, sendo permitido apenas um movimento. Eu divaguei um pouco, minha pergunta principal é a seguinte.
Existe um jogo natural, onde a MOVE-COMPLEXITY dos dois jogadores é diferente?
Por exemplo, o jogo em que o primeiro jogador escolhe os valores das variáveis de uma CNF (que pode não ter uma solução), enquanto o segundo jogador está tentando resolver um quebra-cabeça da SOKO-BAN (que pode não ter uma solução), é tal exemplo.
fonte
Respostas:
Talvez um jogo bastante natural seja o seguinte:
O jogador 1 é colocado no meio de um labirinto e deve chegar à saída para vencer.
O jogador 2 está no mesmo labirinto e deve coletar um conjunto de "componentes" para criar um controlador de rádio que permita fechar a saída (e vencer).
Para tornar o jogo mais "interativo", também podemos adicionar algumas ações extras ao Jogador 2 que podem causar apenas uma desaceleração polinomial no cálculo da próxima jogada do Jogador 1; por exemplo, permitindo-lhe bloquear um número fixo de corredores do labirinto.
fonte
Depois, basta olhar para alguns jogos naturais em que a POSITION-COMPLEXITY é assimétrica. Sempre precisaremos de alguma assimetria entre os jogadores para criar essas situações, mas espero que seja o mais natural possível.
fonte
De fato, nos chamados jogos Picker-Chooser ou Chooser-Picker, é fácil criar exemplos para os quais a melhor estratégia de um jogador é uma estratégia de emparelhamento simples, enquanto o outro precisa resolver um 3-SAT em qualquer CNF especificada anteriormente, esse é um problema NP-completo.
Digamos, um jogo Picker-Chooser é um jogo assimétrico em um hipergrafo H = (V, E): Picker seleciona dois elementos não selecionados de V, então Chooser pega um desses e retorna o outro para Picker. O seletor ganha se ele obtiver todos os elementos de um A de E. Agora, dada a fórmula F da CNF de 3-SAT, V é o conjunto de literais e E realiza algum dispositivo. Em suma, Picker deve sempre oferecer x_i e x_i negar em todas as etapas (caso contrário, perde imediatamente), enquanto a seleção Chooser é uma entrada arbitrária de 0-1 para qualquer x_i, e ele vence satisfazendo F.
Veja os detalhes em: A. Csernenszky, R. Martin e A. Pluhár, Sobre a complexidade dos jogos posicionais do seletor-selecionador. Inteiros 11 (2011).
ou em: http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf
fonte