Uma versão simplificada do jogo de cartas Winner

9

Eu pedi esse problema no MathOverflow , sem nenhuma resposta satisfatória.

Considere o seguinte jogo para dois jogadores, que é uma simplificação do jogo de cartas chamado Winner . (A formulação a seguir foi retirada de um comentário de Guillaume Brunerie no MathOverflow.)

Existem dois jogadores A e B. Cada jogador tem um conjunto de cartas (um subconjunto de {1 1,...,n} ) visível dos dois jogadores. O objetivo do jogo é se livrar de seus próprios cartões. O primeiro jogador joga qualquer carta na mesa, então o outro jogador deve jogar uma carta (estritamente) maior, e assim sucessivamente até que um dos jogadores não possa jogar ou decida passar. Em seguida, as cartas na mesa são descartadas e o outro jogador começa novamente jogando qualquer carta (que será seguida por uma carta maior). E assim por diante até que um dos dois jogadores fique sem cartas e vença o jogo.

Quero saber a melhor estratégia para os jogadores (se ele pode ganhar).

Definição formal

Denote por a configuração do jogo em que o conjunto das cartas do primeiro jogador é , o conjunto das cartas do segundo jogador é e a maior carta da mesa é , onde significa que não há cartão na mesa. Eu gostaria que um algoritmo calculasse, dado , se o primeiro jogador tem uma estratégia vencedora na configuração .W(Eu,UMA,B)B i i = 0 i , A , B w ( i , A , B )UMABEuEu=0 0Eu,UMA,BW(Eu,UMA,B)

Formalmente, eu gostaria de um algoritmo para calcular a função definida da seguinte maneira:f

Deixe , .B o o l = { F a l s e , T r u e }Zn={1 1,2,,n}Booeu={Fumaeuse,Trvocêe}

Funçãof:{0,1,,n}×2Zn×2ZnBooeu

onde

f(i,A,B)={FalseB=TrueBjA:j>i,f(j,B,A{j})=FalseTrueBf(0,B,A)=FalseFalseotherwise

Estratégias erradas

Aqui estão algumas estratégias erradas:

  1. Sempre jogue a menor carta. Seja , a estratégia vencedora para o jogador A na configuração é jogar o cartão . Se o jogador A jogar o cartão 1, ele perderá.w ( 0 , A , B ) 3n=3,A={1,3},B={2}w(0,A,B)3
  2. Jogue a menor carta, a menos que o outro jogador tenha apenas uma carta. É uma estratégia mais forte que a estratégia 1, mas também está errada. Pense apenas na configuração . Se o jogador A usar a estratégia 2, ele perderá: , portanto o jogador A perde.w(0,{1,4,6,7},{2,3,5,8})124568pass3
Yai0Phah
fonte
6
Esta questão é interessante, mas tente torná-la o mais legível possível. Por exemplo, você não precisa copiar o comentário de Guillaume Brunerie literalmente, incluindo a parte “Eu acho que é A que deve ser conhecida pelo jogador…”, que é diferente da suposição em sua pergunta e só pode confundir os leitores. Além disso, considere remover a primeira formulação das três: a segunda formulação fornece uma compreensão intuitiva, a terceira uma definição formal e eu não acho que a primeira sirva a algum propósito.
Tsuyoshi Ito
5
Possivelmente, a melhor maneira de analisar isso é escrever um programa que calcule os movimentos ideais para qualquer posição e procure padrões. Não existe uma razão a priori para que este jogo tenha uma boa estratégia.
Peter Shor
2
Eu começaria uma estratégia com um pequeno número de cartões e trabalharia a partir daí. Por exemplo, se cada jogador tiver 2 cartas, o jogador que tiver a carta mais alta ganha, independentemente de qual jogador tenha o próximo turno. Ele joga a carta mais alta, o outro jogador deve passar e, em seguida, ele joga sua última carta.
21412 Joe
Alguém pode me ajudar a redescrever a descrição do GB para seguir o postscript 1? Sinto muito por não ser um falante nativo e descrever um jogo tão complexo está fora da minha capacidade.
precisa saber é o seguinte
11
@ Tsuyoshi: Se o jogador A sempre joga a menor carta, o jogador B vence. Se o jogador A jogar a carta 1 e nem sempre jogar a menor carta, o jogador A poderá ganhar. Isso significa que há um contra-exemplo menor para a estratégia 2 sempre vencendo.
Peter Shor

Respostas:

4

Provavelmente isso deve ser um comentário, mas é muito longo.

Um jogo relacionado foi estudado por Jeff Kahn, Jeff Lagarias e Hans Witsenhausen, na série de artigos Jogo de Cartas para Duas Pessoas de Naipe Simples I, II, III e No Jogo de Cartas de Laskar. No jogo que estudaram, cada jogador tem cartas, distribuídas a partir de cartas numeradas . Cada truque consiste em duas cartas, a carta mais alta vence o truque e o vencedor lidera. O objetivo é fazer o máximo de truques.n2n1 1 ... 2n

Eles provaram uma série de fatos interessantes sobre a estratégia ideal, mas não conseguiram encontrar um algoritmo eficiente para o jogo ideal e também não conseguiram provar que era difícil para o NP.

Para o jogo misère , onde cada pessoa tenta fazer o menor número possível de truques, foi capaz de dar a melhor estratégia.

Na maioria dos casos, esses resultados foram obtidos analisando primeiro os resultados de um programa de computador que encontrou a estratégia ideal para pequenas instâncias, depois procurando padrões para obter conjecturas e, finalmente, provando essas conjecturas. Eu suspeito que essa também seria uma abordagem proveitosa a ser adotada no jogo do OP.

Peter Shor
fonte