Jogo de permutação redux

20

Esta é uma reafirmação de uma pergunta anterior .

Considere o seguinte jogo imparcial de informações perfeitas entre dois jogadores, Alice e Bob. Os jogadores recebem uma permutação dos números inteiros 1 a n. A cada turno, se a permutação atual estiver aumentando, o jogador atual perde e o outro jogador vence; caso contrário, o jogador atual remove um dos números e o jogo passa para o outro jogador. Alice toca primeiro. Por exemplo:

  • (1,2,3,4) - Bob vence imediatamente, por definição.

  • (4,3,2,1) - Alice vence após três turnos, não importa como alguém jogue.

  • (2,4,1,3) - Bob pode vencer em seu primeiro turno, não importa como Alice jogue.

  • (1,3,2,4) - Alice vence imediatamente removendo o 2 ou o 3; caso contrário, Bob pode vencer no primeiro turno removendo o 2 ou o 3.

  • (1,4,3,2) - Alice acaba vencendo se fizer o 1 no primeiro turno; caso contrário, Bob pode vencer no seu primeiro turno não removendo o 1.

Existe um algoritmo de tempo polinomial para determinar qual jogador vence este jogo a partir de uma dada permutação inicial, assumindo o jogo perfeito ? De maneira mais geral, por se tratar de um jogo imparcial padrão, toda permutação tem um valor Sprague – Grundy ; por exemplo, (1,2,4,3) tem o valor * 1 e (1,3,2) tem o valor * 2. Quão difícil é calcular esse valor?

O algoritmo de retrocesso óbvio é executado em tempo O (n!), Embora isso possa ser reduzido para tempo por meio de programação dinâmica.O(2npoly(n))

Jeffε
fonte
4
Parece-me que o algoritmo ingênuo é executado no tempo O (2 ^ n⋅poly (n)).
Tsuyoshi Ito
A partir dos seus exemplos, é óbvio que Alice sempre vence se a sequência estiver descendente e Bob sempre vence se a sequência estiver ascendente. Esse problema me lembra a análise de algoritmos de classificação, que foram extensivamente estudados e permitem que você use um amplo arsenal de ferramentas.
chazisop
1
@chazisop: “Alice sempre vence se a sequência estiver descendente”: esse é o caso se e somente se n for par.
Tsuyoshi Ito
@ Jɛ ff E no caso 3, como Bob vence no seu primeiro turno?
Suresh Venkat
2
@Suresh: No caso de (2,4,1,3), a representação gráfica é o gráfico linear em 4 vértices (2-1-4-3). Se Alice remover um nó final, isso deixará o gráfico linear em 3 vértices; Bob vence removendo o vértice central (então 3 é respondido por 1 e 2 é respondido por 4). Se Alice remover um nó interno, isso deixará dois vértices conectados e um nó isolado; Bob vence removendo um dos dois vértices conectados (então 1 é respondido por 3 ou 4 e 4 é respondido por 1 ou 2).
Mjqxxxx

Respostas:

7

O "jogo de permutação" é isomórfico para o seguinte jogo:

Desconectar. Os jogadores alternadamente remover os vértices de um grafo . O jogador que produz um gráfico totalmente desconectado (ou seja, um gráfico sem arestas) é o vencedor.G

O gráfico correspondente a uma permutação inicial específica contém apenas as arestas para as quais e têm sinais opostos. Ou seja, cada par de números na ordem errada na permutação está associado a uma aresta. Claramente, os movimentos permitidos são isomórficos aos do jogo de permutação (remover um número = remover um nó) e as condições de vitória também são isomórficas (sem pares em ordem decrescente = sem arestas restantes). π S n ( i , j ) i - j π ( i ) - π ( j )GππSn(i,j)ijπ(i)π(j)

Uma vista complementar é obtida considerando que joga um jogo de "dupla" do gráfico complemento , que contém essas bordas para o qual e são na ordem correta na permutação. O jogo duplo para desconectar é: ( i , j ) i jGπc=GR(π)(i,j)ij

Reconecte. Os jogadores alternadamente remover os vértices de um grafo . O jogador que produz um gráfico completo é o vencedor.G

Dependendo da permutação específica, um desses jogos pode parecer mais simples que o outro para analisar. A vantagem da representação gráfica é que é claro que os componentes desconectados do gráfico são jogos separados e, portanto, espera-se uma redução na complexidade. Também torna as simetrias da posição mais aparentes. Infelizmente, as condições vencedoras não são padrão ... o jogo de permutação sempre termina antes que todos os movimentos sejam esgotados, dando a ele um personagem misère . Em particular, o valor nim não pode ser calculado como a soma nim (XOR binário) dos valores nim dos componentes desconectados.


Para Desligar, não é difícil de ver que, para qualquer gráfico e qualquer mesmo , o jogo é equivalente a (onde é o gráfico sem gume em vértices) . Para provar isso, precisamos mostrar que a soma disjuntiva é uma vitória do segundo jogador. A prova é por indução em . Se tiver bordas, o primeiro jogador perde imediatamente (os dois jogos terminam). Caso contrário, o primeiro jogador pode mover-se em e o segundo jogador pode copiar sua jogada no outro (reduzindo para comn G ˉ K n G ˉ K n n G + G ˉ K n | G | + N G G G ' + G '¯ K n | G ' | = | G | - 1 n 2 L + L ˉ K n - 2GnGK¯nGK¯nnG+GK¯n|G|+nGGG+GKn¯|G|=|G|1 ); ou, se , o primeiro jogador pode mover-se na peça desconectada e o segundo jogador pode fazer o mesmo (reduzindo para ).n2G+GK¯n2

Isto mostra que todo o gráfico é equivalente a , onde é a parte do sem vértices desconectadas, e ou , é a paridade do número de vértices desconectados em . Todos os jogos em uma classe de equivalência têm o mesmo valor nim e, além disso, a relação de equivalência respeita a operação de união: se e então . Além disso, pode-se ver que os jogos em eH K P H L p = 0 1 L L ~ H K P L ' ~ H 'K p ' L L ' ~ ( H H ' ) K p p ' [ H K 0 ] [ H K 1 ] H H + H GHKpHGp=01GGHKpGHKpGG(HH)Kpp[HK0][HK1]tem valores nim diferentes, a menos que seja o gráfico nulo: ao jogar , o primeiro jogador pode pegar o vértice isolado, saindo de , e depois copiar os movimentos do segundo jogador.H H + HH+HK1H+H

Não conheço nenhum resultado de decomposição relacionado ao Reconectar.


Dois tipos especiais de permutações correspondem a jogos de pilha particularmente simples.

  1. A primeira é uma descida ascendente , por exemplo, . Quando assume esta forma, o gráfico é uma união de cliques disjuntos, e o jogo Disconnect se reduz a um jogo em montões: os jogadores removem alternadamente um único feijão de um montão até que todos os montes tenham o tamanho .π G π 132165487πGπ1
  2. O segundo é uma descida ascendente , por exemplo, . Quando assume esta forma, o gráfico é uma união de panelinhas disjuntas, e o jogo de Reconectar se reduz a um jogo em montões: os jogadores removem alternadamente um único feijão de um montão até que haja resta apenas um monte .π G c π78456123πGπc

Um pouco de reflexão mostra que esses dois jogos diferentes em montões (podemos chamá-los de 1 montões e um montão , com algum risco de confusão) são, de fato, isomórficos. Ambos podem ser representados por um jogo em um diagrama de Young (como proposto inicialmente por @domotorp), no qual os jogadores alternam a remoção de um quadrado inferior direito até que apenas uma única linha seja deixada. Obviamente, este é o mesmo jogo que o 1-Heaps quando as colunas correspondem aos heaps e o mesmo jogo que o One-Heap quando as linhas correspondem aos heaps.

Um elemento-chave deste jogo, que se estende a Desconectar e Reconectar, é que a duração está relacionada ao estado final do jogo de uma maneira simples. Quando for a sua vez, você vencerá se o jogo tiver um número ímpar de movimentos restantes, incluindo o que você está prestes a fazer. Como um único quadrado é removido a cada jogada, isso significa que você deseja que o número de quadrados restantes no final do jogo tenha a paridade oposta à existente. Além disso, o número de quadrados terá a mesma paridade em todos os seus turnos; para que você saiba desde o início que paridade deseja que a contagem final tenha. Podemos chamar os dois jogadores de Eve e Otto, dependendo se a contagem final deve ser par ou ímpar para que eles ganhem. Eva sempre se move em estados com paridade ímpar e produz estados com paridade par, e Otto é o oposto.

Em sua resposta, @PeterShor faz uma análise completa do One-Heap. Sem repetir a prova, o resultado é o seguinte:

  • Otto gosta de e pilhas e pode tolerar uma única pilha maior. Ele vence se conseguir fazer todos os tamanhos de pilha, exceto um , pelo menos sem dar a Eve uma vitória imediata da forma . Uma estratégia ideal para Otto é sempre tirar da segunda maior pilha, exceto quando o estado é , quando ele deve tirar da . Otto perderá se houver muitos feijões em grandes montes para começar.2 2 ( 1 , n ) ( 1 , 1 , n > 1 ) n122(1,n)(1,1,n>1)n
  • Eve não gosta de pilhas. Ela vence se conseguir fazer todos os tamanhos de heap . Uma estratégia ideal para Eve é sempre pegar uma pilha , se houver alguma, e nunca tirar uma pilha . Eve perderá se houver muitas pilhas de para começar.2 1 2 112121

Como observado, isso também oferece estratégias ótimas para o 1-Heaps, embora elas sejam um pouco mais difíceis de se expressar (e eu posso estar cometendo um erro na "tradução" do primário para o duplo). No jogo de 1 pilhas:

  • Otto gosta de um ou dois montões grandes e pode tolerar qualquer número de montões. Ele vence se conseguir fazer com que todos, exceto os dois maiores, sejam montes, pelo menos sem dar a Eve uma vitória imediata da forma . Uma estratégia ideal para Otto é sempre usar a terceira maior pilha ou a menor quando houver apenas dois.1 ( 1 , 1 , , 1 , 2 )11(1,1,,1,2)
  • Eve não gosta de uma lacuna entre a maior e a segunda maior pilha. Ela vence se conseguir fazer com que as duas maiores pilhas tenham o mesmo tamanho. Uma estratégia ideal para Eve é sempre usar o maior monte, se for único, e nunca se houver exatamente dois do maior tamanho.

Como o @PeterShor observa, não está claro como (ou se) essas análises podem ser estendidas aos jogos mais gerais de Disconnect and Reconnect.

mjqxxxx
fonte
2
Eu acho que esse tipo de jogo é coletivamente chamado de "jogos de exclusão de vértices". Mas eu concordo com você que a condição vencedora é bastante fora do padrão, pois se refere à propriedade global do gráfico, em vez de propriedades locais, como o grau de um vértice.
Tsuyoshi Ito
4
O gráfico construído é chamado de gráfico de permutação ( en.wikipedia.org/wiki/Permutation_graph ) na literatura. Algumas propriedades estruturais podem ajudar.
Yoshio Okamoto
1
@ Yoshio: Esse é um bom ponto. O jogo de permutação é isomórfico para o jogo gráfico, mas os gráficos iniciais não são arbitrários. Portanto, mesmo que o jogo gráfico geral seja difícil de analisar, é possível que, quando restrito a essa subclasse de gráficos, ele se torne mais simples.
mjqxxxx
2
Por outro lado, a formulação mais geral pode ser mais fácil de provar. Sabe-se que variantes de jogos de exclusão de vértices são difíceis para o PSPACE, por exemplo: emis.ams.org/journals/INTEGERS/papers/a31int2005/a31int2005.pdf
Jeffε
2
Eu adicionei uma pergunta sobre esse tipo de jogo especificamente em math.SE ( math.stackexchange.com/questions/95895/… ). Aliás, como os gráficos de permutação são gráficos de círculo, uma formulação alternativa é a seguinte: Os jogadores se revezam na remoção de acordes de um conjunto inicial; o jogador que deixa um conjunto de acordes sem interseção é o vencedor.
Mjqxxxx
7

Em sua resposta, domotorp sugere analisar um caso especial do jogo. Este caso especial surge quando a permutação é uma série de seqüências crescentes, cada uma das quais é maior que a seguinte, como (8,9,5,6,7,4,1,2,3). Neste jogo, você começa com uma coleção de montes de pedras e os jogadores removem uma pedra alternadamente de uma pilha. O jogador que deixa uma única pilha ganha. que o th heap tem stones nele, e assumimos que o é dado em ordem decrescente. Por exemplo, para a permutação acima, os são 3,3,2,1. Tentei dar a análise deste jogo nos comentários à resposta da domotorp, mas (a) eu entendi errado e (b) não há espaço suficiente nos comentários para fornecer uma prova real.h i h i h iihihihi

Para analisar esse jogo, precisamos comparar duas quantidades: , o número de pilhas contendo pedras únicas ; observe que ignoramos a maior pilha na soma. Esse é o número de pedras que você precisaria remover para garantir que todos os montões, exceto um, não contenham mais do que duas pedras. Afirmamos que as posições perdedoras são as seguintes:t = i 2 , h i > 2st=i2,hi>2hi2

  1. Posições onde contendo um número ímpar de pedras.ts2

  2. Posições onde contém um número par de pedras.ts

É fácil mostrar que, de uma posição perdida, você deve ir para uma posição vencedora, pois os só podem mudar em no máximo 1 por turno, e o número de pedras diminui em 1 a cada movimento.ts

Para terminar de mostrar que isso está correto, precisamos mostrar que, de qualquer posição que não esteja na categoria (1) ou (2), o primeiro jogador pode, em um movimento, alcançar uma posição na categoria (1) ou (2), ou ganhar diretamente.

Existem dois casos:

  1. Posições onde contendo um número ímpar de pedras. Aqui, se , remova uma pedra de uma pilha com uma única pedra. Se houver apenas um monte, vencemos. Caso contrário, agora temos . Se não houver pilhas com uma única pedra, remova-a de uma pilha com pelo menos três pedras. (Como havia um número ímpar de pedras, isso é possível). Como , temos .s > 0 t s s = 0 t sts1s>0tss=0ts

  2. Posições onde contendo um número par de pedras. Aqui, se houver pilhas com pelo menos duas pedras além da pilha maior, remova-a de uma delas. Se essa pilha tiver três ou mais pedras, diminui em uma. Se tiver exatamente duas pedras, aumenta em uma. Agora temos . O último caso é quando todos os montões, exceto um, consistem em pedras únicas; Nesse caso, é fácil verificar se o primeiro jogador vence se houver um número par de pedras.t s t s - 2ts1tsts2

Eu tentei generalizar essa estratégia para o jogo original e ainda não descobri como fazê-lo.

Peter Shor
fonte
1
Na minha resposta, observei que ter uma solução para esse caso especial também resolve o caso especial com uma série crescente de execuções decrescentes, jogando na posição "dupla" obtida pela transposição do diagrama de Young. Em particular, a estratégia ideal de Eve passa a ser "retirada da maior pilha, a menos que haja exatamente dois desse tamanho", e a estratégia ideal de Otto passa a ser "retirada da menor pilha".
Mjqxxxx
Estou certo de que essa abordagem levará a uma solução perfeita, mas no momento ainda há um pequeno erro, por exemplo, (3,1) não está perdendo e (3,1,1) está. O problema é que a definição de 2. deve excluir esse caso, pois podemos alcançar uma posição de pilha em uma etapa. Mas acho que esse é o único problema do 2. e espero que não seja difícil corrigi-lo.
domotorp
1
-
Claro, eu esqueci essa parte no final ... Então este jogo está resolvido!
domotorp
1
Não é uma resposta completa, mas ainda vale a pena.
Jeffε
3

Eu implementei uma solução para verificação rápida de hipóteses. Sinta-se livre para jogar com ele . Se você não possui o compilador C ++ localmente, pode executá-lo em diferentes entradas remotamente usando o link "carregar com nova entrada".O(2nn)

@ Jɛ ff E Aconteceu que (1,4,3,2) tem o valor * 1, não * 2 como você sugeriu.

Dmytro Korduban
fonte
Opa, meu erro. Corrigida a questão: g (1,3,2) = mex {g (1,3), g (1,2), g (3,2)} = mex {0, 0, * 1} = * 2.
Jeffε
@ Jɛ ff E É interessante que, para , o valor SG de qualquer posição não seja maior que 2. Estou tentando provar isso agora para arbitrário , embora não sei como isso vai ajudar. nn10n
Dmytro Korduban
@maldini: dá esperança de que o jogo tenha algumas boas propriedades, o que pode torná-lo tratável. Eu me pergunto o que acontece com o jogo generalizado em gráficos, ou o jogo apenas generalizado em gráficos perfeitos.
quer
3

Editar 5 de janeiro: De fato, o One Heap Game descrito abaixo é um caso especial do problema, ou seja, quando os números se seguem de uma maneira específica, de modo que o primeiro grupo seja maior que o segundo grupo que seja maior que o terceiro etc. e os números em cada grupo estão aumentando. Por exemplo, 8, 9, 4, 5, 6, 7, 2, 3, 1 é essa permutação. Então, proponho resolver esse caso especial primeiro.

Exoneração de responsabilidade: não reivindico mais que a prova abaixo esteja correta, veja, por exemplo, o comentário de Tsuyoshi, que mostra que a exclusão de um número de uma permutação fornecerá um diagrama impossível de ser obtido pela exclusão de um quadrado do diagrama da permutação. Deixei a resposta aqui para mostrar que essa abordagem não funciona, além de conter outro jogo simples.

O jogo tem uma outra formulação muito simples, graças ao Young Tableaux. Estou certo de que pode ser analisado a partir daí como outros jogos e produzirá um algoritmo de tempo linear.

Primeiro, defina o seguinte jogo nos diagramas jovens: A cada turno, se o diagrama atual for horizontal (todos os quadrados em uma linha), o jogador atual perde e o outro jogador vence; caso contrário, o jogador atual remove um dos quadrados inferior direito e o jogo passa para o outro jogador.

Agora ordene a sequência de números em um Young Tableaux. A principal reivindicação é que o vencedor do jogo original é o mesmo que o vencedor do jogo de diagrama começando com essa forma. Para ver isso, observe que sempre que os jogadores excluem um número, o diagrama da nova sequência pode ser alcançado excluindo um quadrado inferior direito do diagrama. Além disso, qualquer diagrama pode ser obtido excluindo o número do respectivo quadrado inferior direito. Essas declarações seguem a teoria padrão de Young Tableaux.

Embora este jogo de diagrama seja bastante simples, é trivialmente equivalente ao jogo a seguir, que parece mais padrão:

Um jogo de pilha: Os jogadores recebem algumas pilhas com algumas pedras em cada uma. A cada turno, se restar apenas uma pilha, o jogador atual perde e o outro jogador vence; caso contrário, o jogador atual remove uma pedrinha de uma pilha e a jogada passa para o outro jogador.

Se houver uma solução simples para o jogo de heap (e eu acredito fortemente que exista), também obteremos uma solução para o jogo original: basta colocar a sequência em um Young Tableaux e transformar seu diagrama em montões.

Infelizmente, não vejo quais posições de pilha estão ganhando / como determinar os valores de Sprague – Grundy. Eu verifiquei alguns casos manualmente, e a seguir estão as posições perdedoras com no máximo 6 pedras:

uma pilha; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2)

Alguém pode resolver este jogo?

Edit: Peter Shor pode, veja sua resposta!

domotorp
fonte
1
Você pode dar pelo menos um exemplo que mostre como uma permutação específica é transformada em um Young Tableau e como o mesmo jogo (remoção de número até que uma sequência ascendente seja atingida) é reproduzido no Tableau? Em particular, não entendo o que significa remover "um dos quadrados inferior direito".
mjqxxxx
5
Aqui está um contra-exemplo de uma alegação mais fraca de que remover um número de uma permutação corresponde a remover uma das células inferior direita do diagrama Young correspondente (em vez do quadro Young ). Seja n = 5 e considere uma posição especificada pela permutação [4,1,3,5,2] (ou seja, σ (1) = 4, σ (2) = 1 e assim por diante) e remova 3 a partir dele. O diagrama Young correspondente antes da movimentação é 5 = 3 + 1 + 1, mas o diagrama Young correspondente após a movimentação é 4 = 2 + 2, que não é obtido pela remoção de uma célula de 3 + 1 + 1.
Tsuyoshi Ito
5
E a permutação [5,4,1,2,3] tem o mesmo diagrama de Young que [4,1,3,5,2], mas você não pode alcançar o diagrama de Young 4 = 2 + 2 a partir dele. Portanto, o jogo depende de mais do que a forma do quadro Young.
quer
2
Viva um mal-entendido construtivo!
Jeffε
3
@ Jɛ ff E: Sim, isso é muito mais útil do que uma prova da mera existência de mal-entendidos.
Tsuyoshi Ito