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 ) 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 .B i i = 0 i , A , B w ( i , A , B )
Formalmente, eu gostaria de um algoritmo para calcular a função definida da seguinte maneira:
Deixe , .B o o l = { F a l s e , T r u e }
Função
onde
Estratégias erradas
Aqui estão algumas estratégias erradas:
- 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 ) 3
- 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.
fonte
Respostas:
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.n 2 n 1 1 ... 2 n
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.
fonte