Um jogo em vários gráficos

13

Considere o jogo a seguir em um gráfico ponderado direcionado G com um chip em algum nó.

Todos os nós de G são marcados por A ou B.

Existem dois jogadores Alice e Bob. O objetivo de Alice (Bob) é mudar o chip para um nó marcado por A (B).

Inicialmente, Alice e Bob têm mA e mB dólares, respectivamente.

Se um jogador estiver em uma posição perdida (ou seja, a posição atual do chip é marcada por uma letra oposta), ele pode mover o chip para um nó vizinho. Esse movimento custa alguns dólares (o peso da margem correspondente).

O jogador perde se estiver em uma posição perdida e não tiver dinheiro para consertá-lo.

Agora considere o idioma GAME que consiste em todos os gráficos ponderados direcionados G (todos os pesos são números inteiros positivos), posição inicial do chip e maiúsculas de Alice e Bob que são dadas na representação unária

de modo que Alice tenha uma estratégia vencedora neste jogo.

O jogo de linguagem pertence a P . De fato, a posição atual do jogo é definida pela posição do chip e pelas capitais atuais de Alice e Bob, de modo que a programação dinâmica funciona (aqui é importante que as capitais iniciais sejam dadas na representação unária).

Agora considere a seguinte generalização deste jogo. Considere vários gráficos ponderados direcionados G1,Gn com um chip em cada gráfico. Todos os nós de todos os gráficos são marcados por A e B. Agora, Bob ganha se todas as fichas são marcadas por B e Alice vence se pelo menos uma ficha marcada com A.

Considere o idioma MULTIGAME que consiste em todos os gráficos G1,,Gn , posições iniciais e maiúsculas mA e mB (na representação unária), de modo que Alice vença no jogo correspondente. Aqui é importante que as capitais sejam comuns para todos os gráficos, portanto, não são apenas vários GAMEs independentes.

Pergunta Qual é a complexidade do idioma MULTI-JOGOS? (Também pertence a P ou existem algumas razões para que esse problema seja difícil?)

UPD1 Neal Young sugeriu o uso da teoria de Conway. No entanto, não sei se é possível usar essa teoria para vários jogos com capital comum.

UPD2 Quero mostrar um exemplo que mostra que MULTI-JOGO não é muito simples. Vamos Alice dividir seu capital de mA para alguns n termos mA=a1+a2+an (Ela vai usar ai dólares para i gráfico -ésimo). Definir bi como o número mínimo de tal forma que em i jogo -ésimo Bob vitórias se Alice e Bob tem ai e bi dólares respectivamente. Se b1+bn>mB (para alguma divisãomA=a1+a2+an ), então Alice vence. No entanto, o oposto não é verdadeiro. Considere duas cópias do gráfico a seguir (inicialmente o chip fica à esquerda A): insira a descrição da imagem aqui

Para um gráfico, Bob vence se mA=0 e mB=2 ou se mA=1 e mB=3 . No entanto, para o jogo com duas cópias deste gráfico, Bob perde se mA=1 e mB=5 . Na verdade, Bob tem que gastar 4 ou 5 dólares para mudar ambos os chips a um nó marcado por B . Então Alice pode mudar pelo menos um chip para um nó marcado por A. Depois disso, Bob não tem dinheiro para salvar sua posição.

UPD3 Como a pergunta para gráficos arbitrários parece difícil, considere gráficos específicos. Denote os nós de algum gráfico Gi como 1,k . Minha restrição é a seguinte: para cada par i<j existe aresta de i até j e não há aresta reversa. Também existe uma restrição para os custos das arestas: para i<j<k a aresta j para k não é maior que de i para k .

Alexey Milovanov
fonte
4
no MULTI-JOGO, o que constitui uma jogada? O jogador faz um movimento em cada gráfico? Ou escolhe um gráfico para fazer a mudança? Você já examinou se a teoria dos jogos de Conway (aquecimento e resfriamento) se aplica aqui? (Algumas referências podem ser encontradas aqui: en.wikipedia.org/wiki/… )
Neal Young
@Neal Young O jogador escolhe um gráfico para fazer um movimento.
Alexey Milovanov
FWIW, se bem me lembro, a teoria dos jogos de Conway considera como jogar jogos que são compostos de outros jogos dessa maneira (em cada jogada, o jogador escolhe um dos sub-jogos para jogar). Não sei qual a relevância da teoria dele sobre a complexidade computacional.
Neal Young
11
@NealYoung Obrigado, mas pelo que entendi o problema é que os jogadores têm capitais comuns para todos os jogos. Eu não acho como isso pode ser consertado pela teoria de Conway ...
Alexey Milovanov
Alice (Bob) é forçada a mover o chip se estiver no nó A (B)? Quais são as condições vencedoras do multi-jogo? B ganha também quando todas as fichas estão nos nós B, mas A ainda tem algum dinheiro? Você diz que A vence se pelo menos um chip estiver em A; portanto, A pode simplesmente tentar manter dois chips em um nó marcado com A nos dois gráficos "menos caros"; logo movimento B um dos dois chips de distância do nó A, Alice traz de volta (e ignorar os outros gráficos)
Marzio De Biasi

Respostas:

2

Como a resposta de Steven Stadnicki não parece ter sido aceita pelo autor da pergunta, achei que ainda seria útil fornecer uma atualização: tenho uma redução de 3SAT para MULTI-JOGO. Eu não olhei atentamente a resposta de Steven ou segui o link que ele forneceu, mas com base na seguinte redução, não ficarei surpreso se o MULTI-JOGO for realmente PSPACE completo. No entanto, posso não me incomodar em estender esse resultado além da dureza NP.

Uma instância 3SAT consiste nas cláusulas C1,,Cm , sendo cada cláusula no formato Ci=Li1Li2Li3 onde cada Lik é uma das variáveis x1,,xn ou a negação de uma das variáveis.

Dada uma instância 3SAT, a redução cria uma instância MULTI-JOGO que consiste em n+1 jogos - um para cada variável e outro jogo usado como um excesso de capital. Primeiro, definiremos a estrutura dos gráficos para cada jogo, depois examinaremos um exemplo e discutiremos a ideia central e, em seguida, descobriremos quais custos exatos serão atribuídos às arestas para manter a redução firme.

Primeiro, o gráfico de jogo variável Gj para cada variável xj :

  1. Crie um vértice rotulado xj marcado com um A (ou seja, um vértice vencedor para Alice). O chip para Gj começa no vértice xj .
  2. Crie um vértice rotulado T e um vértice rotulado F , cada um marcado com um B (ou seja, ambos são posições vencedoras para Bob). Crie arestas direcionadas de xj para T e F , ambas com custos de 1 .
  3. Para cada literal Lik de cláusula Ci , se Lik=xj ou Lik=¬xj , criar vértices marcados CiTA e CiFA marcada com A e vértices marcados CiTB e CiFB marcado com B. Adicione arestas (T,CiTA) e(F,CiFA) com custos definidos emlik . (Vamos definirlik mais tarde.)

    Adicione arestas (CiTA,CiTB) e (CiTA,CiTB) . Se Lik=xj , defina o custo (CiTA,CiTB) como lik1 e (CiTA,CiTB) custo 's paralik . Caso contrário definido(CiTA,CiTB) 'custo s alik e(CiTA,CiTB) ' s custo paralik1 .

O jogo do sumidouro de capital:

  1. Crie um vértice rotulado C , marcado com B.
  2. Para cada cláusula Ci , crie um vértice marcado CiA marcado com A e um vértice marcado CEuB marcado com B. Crie uma aresta (C,CEuUMA) com custo de aresta cEu (novamente a ser determinado abaixo) e uma aresta (CEuUMA,CEuB) também com custo de aresta cEu .

Isso é muito para absorver, por isso, espero que um exemplo torne isso um pouco mais digerível. Nossa instância 3SAT é a seguinte:

C1 1=x1 1x2¬x3

C2=x2x3¬x4

C3=¬x1 1¬x3x4

A redução transforma essa instância em 4 gráficos de jogos variáveis ​​e 1 gráfico de capital capital. Nos diagramas abaixo, os vértices vermelhos são marcados com A (ou seja, são posições vencedoras para Alice) e os vértices cianos são marcados com B (são posições vencedoras para Bob).

Gráfico para x1 1 :

insira a descrição da imagem aqui

Gráfico para x2 :

insira a descrição da imagem aqui

Gráfico para x3 :

insira a descrição da imagem aqui

Gráfico para x4 :

insira a descrição da imagem aqui

Gráfico para capital capital:

insira a descrição da imagem aqui

A ideia é a seguinte:

Bob é forçado a fazer os primeiros n movimentos, a fim de perder posições perdidas nos n jogos variáveis. Cada movimento codifica uma atribuição de true ou false para a variável correspondente.

Alice terá capital suficiente para fazer exatamente 4 movimentos, cada um dos quais Bob precisará ter capital suficiente para corresponder para que Bob vença. As cEu valores e as euEuk valores devem ser escolhidos de modo que apenas estratégia vencedora possível de Alice é a seguinte, por alguma cláusula CEu :

Cláusula de Alice CEu estratégia: deixe CEu=euEu1 1euEu2euEu3 . Para cada k{1,2,3} , se Lik=xj ou ¬xj , vá para Ci?A no jogo variável para xj . Também vá para CiA no jogo capital sumidouro.

( Ci?A denota CiTA ou CiFA , apenas um dos quais é alcançável em um determinado jogo variável após os movimentos de abertura de Bob.)

Se corresponde abertura de Bob para uma atribuição verdade que deixa alguma cláusula Ci insatisfeito, então Alice escolher Ci e implementação da estratégia acima dos custos Alice li1+li2+li3+ci capital para implementar e Bob o mesmo derrotar; Se, por outro lado Ci está satisfeito, então contra-jogo de Bob recebe um desconto de pelo menos 1 . Nosso objetivo na definição de ci e lik valores e as capitais iniciais de Alice e Bob é garantir que esse desconto seja o fator decisivo para a conquista de Alice ou Bob.

Para esse fim, defina b=m+1 e defina

lik=2b10+ib2k para cadak{1,2,3} ,

ci=3b10+b8k=13ib2k ,

Capital inicial de Alice para 9b10+b8 ,

e o capital inicial de Bob para 9b10+b8+n1.

Observe que todos esses valores são polinomiais em m , portanto, a instância MULTI-GAME gerada pela redução possui polinômio de tamanho no tamanho da instância 3SAT, mesmo que esses custos sejam codificados em unários.

Observe também que para cada cláusula Ci , li1+li2+li3+ci=9b10+b8 é o capital inicial de Alice. (Que também é 1 maior que o capital de Bob depois de fazer os primeiros n movimentos.)

Antes de tudo, fica imediatamente claro que, se a abertura de Bob define uma atribuição de verdade que deixa uma cláusula Ci insatisfeita, então Alice vence usando sua cláusula Ci estratégia dada acima.

Se a abertura de Bob atender a todas as cláusulas, podemos argumentar sobre as opções de Alice que excluem qualquer outra possibilidade de vitória de Alice. Observe que a ordem na qual Alice faz suas jogadas é irrelevante, pois as respostas de Bob são forçadas e o capital total que Bob exigirá para responder às jogadas de Alice é inalterado pela ordem das jogadas de Alice.

  • Alice não pode fazer mais de 4 movimentos: se Alice fizer 5 ou mais movimentos, seus movimentos terão um custo total de 5b10 , que excede seu orçamento.
  • Alice deve fazer 4 jogadas: se Alice seleciona 3 jogadas no jogo do coletor de capital, seu custo total é 9b10+3b8-3b7>9b10+2b8 que está acima do orçamento. Se ela selecionar pelo menos uma jogada de 3 em um jogo variável, seu custo total será 8b10+2b8+b7 que é substancialmente menor que o capital pós-abertura de Bob, para que Bob possa facilmente pagar a contra-partida.
  • Alice deve selecionar uma jogada no jogo do sumidouro de capital: se não, então ela seleciona 4 jogadas de jogos variáveis, com custo total 8b10+4b7 , e novamente Bob pode facilmente pagar a contra-partida. (Observe que, se houvesse um jogo separado de capital por cláusula, poderíamos até mostrar que Alice deve jogar exatamente em um desses jogos.)

A partir desta fase, podemos desconsiderar a b10 e b8 termos nos custos de movimentação escolhido, como eles vão sempre somar 9b10+b8 . Desde Alice deve escolher exatamente um movimento no jogo dissipador de capital, suponha que o movimento é a CEuUMA . Em seguida, Alice (ignorando b10 e b8 Da) k=1 13Eub2k capital restante, e Bob tem 1 1 menos do que esta quantidade restante.

  • Alice deve selecionar pelo menos um movimento custando euj3 por alguma cláusula Cj : se ela não acontecer, então ela se move custo (mais uma vez termos de ordem inferior) 3b5 , e Bob tem mais de capital suficiente para contra-jogo.
  • O referido movimento que custa lj3 deve ser o movimento que custa li3 : não pode ser um movimento que custa lj3 para j>i ; caso contrário, esse movimento por si só custa (i+1)b6 que é maior que o restante de Alice despesas. Se for lj3 para j<i , então o movimento de custo l(ij)3 também deverá ser escolhido por Alice para esgotar o b6pedido no restante do orçamento de Bob. Mas, em seguida, Ou o b2 -order prazo no orçamento restante do Bob ou b2 -order termo não se esgota, então Bob ganha com folga.

Argumentos semelhantes devem estabelecer que Alice deve selecionar os movimentos que custam li2 e li1 . Se satisfaz atribuição verdade de Bob Ci , então, mesmo esta estratégia não funciona, como o desconto Bob fica em uma das lik custos baseados compensa a 1 1 menos capital que ele tem depois de sua abertura.


Uma observação sobre a minha resposta anterior: é óbvio, em retrospectiva, que, para a variante TABLE-GAME de MULTI-JOGO definida nos comentários dessa resposta, um DP no estilo de mochila é suficiente para determinar qual jogador tem uma estratégia vencedora. Você pode argumentar que a melhor estratégia de Bob é sempre responder a um estado perdedor em uma determinada mesa de jogo com o investimento mínimo possível (isso não pode interromper um movimento subsequente para Bob que ele teria de outra forma) e, a partir daí, a ordem dos movimentos de Alice não importa. Torna-se então uma questão de escolher uma divisão do capital de Alice entre os jogos, de forma que a soma das respostas mínimas de vitória de Bob sobre esses jogos exceda seu orçamento, que pode ser reformulado como um problema no estilo de mochila, que possui um DP em tempo polinomial devido à representação unária de custos. (Minha recorrência na verdade seria '

Acontece que mesmo uma estrutura de árvore simples para cada jogo, com profundidade constante e realmente apenas um garfo significativo por jogo (ou seja, aqueles no início que forçam Bob a escolher uma tarefa de verdade) é suficiente para obter a dureza NP. Eu tive algumas idéias para me livrar dessa bifurcação inicial, que parou de alguma forma forçando Bob a investir uma quantia fixa relativamente grande de capital em n jogos, sem que Alice precisasse se comprometer com esses jogos com antecedência, mas obviamente desde que o TABLE-GAME está em andamento. P isso não é possível sem o garfo.

Não pensei muito no seu caso especial da UPD3 . Suspeito que também seja difícil para o NP, pelo fato de meus gadgets variáveis ​​parecerem de relance como se eles fossem adaptáveis ​​a essas restrições, mas provavelmente não analisarei mais.

gdmclellan
fonte
0

Atualização: provavelmente incorreta, deixando por enquanto um registro de ter explorado uma avenida. Ver comentários.

Atualização 2: definitivamente incorreta.

Considere um gráfico da forma (B) -1-> (A) -1-> (B), ie G=(V,E)V={1 1,2,3}E={(1 1,2),(2,3)}

mUMA=mB=2G1 1=G2=G3=G

No entanto, a recorrência abaixo falha em M[3,2,2] : não há divisão dos fundos de Bob 2-você,você entre os dois primeiros jogos e o terceiro jogo, de modo que, para todas as parcelas dos fundos de Alice u = 1 ou u = 2v,2-vM[2,2-você,2-v]=BW[3,você,v]=Bvocê=1 1você=2M[2,2-você,2]=UMAvocê=0 0W[3,você,2]=UMA

vocêv


mUMA,mB,G1 1,,Gn,

Pré-cálculo

W[k,x,y]={UMAse Alice ganhar GAME em Gk com fundos iniciais x para Alice e y para Bob,Bde outra forma

xmUMAymB

M[k,x,y]kxmUMAymBM[k,x,y]=BA

M[1,x,y]=W[1,x,y]

e

M[k+1,x,y]=Bif and only ifvu,W[k+1,u,v]=BandM[k,xu,yv]=B.

M[n,mA,mB]=A

gdmclellan
fonte
Seu algoritmo está errado. Considere o gráfico da foto no meu post. Considere o MULTI-JOGO com dois desses gráficos. Aqui W [1,0,2] = W [2,0,2] = B e W [1,1,3] = W [2,1,3] = B. No entanto, para MULTI-JOGO com m_A = 1 e m_B = 5, Alice vence
Alexey Milovanov
u
@AlexeyMilovanov com alterações nos quantificadores pelos quais a recorrência deve passar, por exemplo. Mas você colocou em minha mente dúvidas sobre essa abordagem. Parece que pode exigir que Bob organize uma única distribuição de fundos que supere todas as distribuições que Alice poderia conceber. Dito isto, não tenho certeza de que fui convencido da idéia central aqui: que esse problema não é realmente sobre GAME. Existe algo conhecido sobre o problema relacionado em que cada instância GAME é substituída por uma tabela simples à la W acima?
gdmclellan 3/09/19
A tabela W não define o vencedor. Eu não sei o que é verdade para alguns outra mesa ...
Alexey Milovanov
@AlexeyMilovanov A Tabela W, por definição, determina o vencedor das instâncias GAME isoladas para qualquer um dos gráficos de entrada específicos. Não sei por que você diria o contrário. Atualizei minha resposta com um contraexemplo, no caso de haver alguma dúvida persistente de que ela estava incorreta.
Gdmclellan #
0

Pelos meus comentários acima, aqui está uma redução que eu acho que mostra que o problema é difícil para o PSPACE (e presumivelmente completo). Deixei[n]n+1 1n0 0Eu+1 1Eu0 0Eu<n0 00 0n[n]n0 00

Agora, considere o gráfico G com dois nós adicionais α e βα[i]ββ[j][k]j<kαββ[j][k][k][i]{i{jk}}

Steven Stadnicki
fonte
11
As provas da tese parecem usar grandes valores de i, j e k nos jogos. Observe que aqui todos os pesos podem ser considerados no máximo as capitais dos jogadores, que foram representadas em unárias.
Antti Röyskö 6/02
@ AnttiRöyskö Vou ter que dar uma olhada muito mais de perto na prova; Acredito que o resultado da finalização do PSPACE dos jogos finais do Go usa o resultado da tese e também assume a contagem unária (já que lá, i / j / k são do tamanho de regiões de tabuleiro).
Steven Stadnicki 06/02
αβ0 0
@AlexeyMilovanov Opa, isso é culpa minha - também deve vincular a β . Além disso, Alice ainda pode querer sair dessa posição; imagine o caso em que apenas temos um único nó, ααβα[i]>[j]j+1[i][j]
αβn