Jogue Wythoff's Nim perfeitamente

16

Seu objetivo é escrever um jogador perfeito para o jogo de Nim de Wythoff .

Regras do Nim de Wythoff

O Nim de Wythoff é um jogo determinístico para dois jogadores, jogado com duas pilhas de marcadores idênticos. Os jogadores alternam turnos, nos quais realizam um destes procedimentos:

  1. Remova um ou mais contadores da primeira pilha
  2. Remova um ou mais contadores da segunda pilha
  3. Remova um número igual de contadores (um ou mais), da primeira pilha e da segunda pilha.

Obviamente, as pilhas não podem ser negativas, mas podem chegar a 0. Qualquer jogador que remover o último contador geral vence o jogo.

Para os mais geométricos, aqui está uma formulação equivalente do jogo que você pode jogar neste applet . Uma única rainha começa em algum quadrado de um tabuleiro de xadrez infinito, cujo canto fica no canto inferior esquerdo. Os jogadores alternam a mudança da rainha, que se move como uma rainha do xadrez, mas restrita a três direções:

  1. Baixa
  2. Esquerda
  3. Na diagonal para baixo e para a esquerda

Quem leva a rainha para o canto ganha.

Associando as coordenadas da rainha (com canto (0,0)) ao tamanho das respectivas pilhas, é fácil ver os dois jogos iguais.

Jogo perfeito

(Você pode pular isso se estiver familiarizado com as noções de jogo perfeito e movimentos vencedores.)

Como o Nim de Wythoff é um jogo finito e determinístico, ele tem uma noção de jogo perfeito . Um jogador perfeito é uma estratégia que sempre vencerá de uma posição conquistada teoricamente, ou seja, uma posição em que exista uma estratégia que garanta uma vitória.

Para ser uma estratégia vencedora, basta mudar para sempre passar para uma posição teórica de vitória para o jogador que acabou de se mudar e, portanto, o jogador não vai para a próxima. A primeira dessas posições vencedoras (também chamadas de posições frias ) é (0,0), (1,2), (2,1), (3,5), (5,3). Consulte o artigo da Wikipedia para obter uma explicação de um algoritmo para encontrar uma estratégia vencedora para o Nim da Wythoff, bem como uma fórmula para gerar posições de vitória.

Requisitos do programa

Escrever um programa ou função toma uma posição como entrada e produz um movimento vencedor na forma da posição após esse movimento. Menos bytes ganha.

Se não houver movimento vencedor, ou seja, a posição é uma perda teórica, seu programa deve indicar isso e perder.

Seu programa deve ser executado dentro de um período de tempo razoável. Portanto, uma pesquisa de árvore de jogo recursiva exponencial não será suficiente. Se você quiser pré-calcular e codificar uma estratégia, tudo bem.

Entrada

Um par (i,j)de números não negativos representando tamanhos de pilha, cada um no máximo 99. Podem ser dois números, uma tupla, uma lista ou qualquer contêiner que você preferir.

Resultado

Imprima ou produza a posição após a sua mudança, novamente como dois números ou um contêiner. Isso deve ser uma mudança legal para uma posição vencedora. Se houver vários desses movimentos, qualquer um está bem, mas apenas um.

Se não houver movimento vencedor, você deve indicar isso na saída. Qualquer saída como False, None0 ou (-1,-1)funcionará, desde que não seja uma posição legal e seja a mesma para todas as entradas perdidas.

Execuções de exemplo

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)    
xnor
fonte
2
+1, em parte porque gosto da ideia de um quarto do infinito.
Level River St
definir "quantidade razoável de tempo". Vários segundos para (100,50) são uma quantidade razoável de tempo?
John Dvorak
Oh. Esperar. a entrada é delimitada por ... 30 ??? Isso é um pouco baixo, não é?
John Dvorak
@JanDvorak Você está certo, pode permitir atalhos baratos. Mudou para 99 - acho que basta? Desculpas por editar especificações após a publicação.
Xnor
@ Petereteray Obrigado, corrigido.
Xnor

Respostas:

6

Haskell, 167 165 caracteres

c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

O algoritmo é ineficiente, mas ainda é executado dentro de um segundo (embora não no console interativo) para entradas <100.

Explicação:

c p=o p:c(o p:p)

A lista de posições frias para um conjunto de posições frias anteriores é uma posição fria seguida pela lista de posições frias para esta posição e as anteriores (Ineficiência: esta posição é gerada duas vezes)

o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

Uma posição fria é o primeiro par, de modo que não há posições frias acessíveis a partir desse par (Ineficiência: devemos procurar pelo par anterior)

(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

As posições alcançáveis ​​a partir de um par são aquelas que correspondem aos seus primeiros elementos, seus segundos elementos, suas diferenças ou o heap menor antes da remoção é o heap maior após a remoção.

f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

(método principal) Se os montões estiverem na ordem errada, troque-os. Caso contrário, se a primeira posição fria alcançável de uma posição for a própria posição, indique falha (idealmente, a pessoa retornariaMaybe (Int,Int) contrário vez disso ). Caso contrário, retorne à posição fria (Ineficiência: o referido par é consultado duas vezes. Pior ainda, a lista de posições frias é gerada duas vezes)

John Dvorak
fonte
Parece que " Portanto, uma pesquisa exponencial de árvore de jogo recursiva não será suficiente " foi otimista, porque o que você descreve soa exatamente assim.
Peter Taylor
@ PeterTaylor é O (n ^ 4). Cada par frio leva O (n ^ 3) tempo para encontrar e há O (n) deles. A otimização da geração o traria para O (n ^ 2) (se eu ler a sequência corretamente). Um algoritmo de tempo exponencial seria muito mais lento. Devo executar alguns testes?
John Dvorak
Tudo bem, eu acredito em você.
Peter Taylor
você pode remover x@dex@(a,b)?p=...
proud haskeller 29/04
Não sei como chegou lá. Fixação, obrigado.
John Dvorak
5

GolfScript ( 63 57 bytes)

{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

Espera a entrada de stdin no formulário [a b]e deixa a saída em stdout nesse formulário ou 0se é uma posição perdida. Demonstração online

Visão geral

,4*{..,,^[(.@,2/+.2$]+}38*2/

calcula uma lista de posições frias (incluindo a versão invertida [b a]para cada posição fria [a b]) usando a propriedade de sequência Beatty .

Então ? procura a primeira posição fria que satisfaz o bloco criado por

{\]zip{~-}%0|$(!*,1=}+

que basicamente verificações de que a posição é acessível a partir da posição de entrada calculando a diferença de vectores e, em seguida, verificar se é ou [0 x], [x 0], ou [x x]por algum x > 0. O IMO desse teste é o bit mais inteligente: 0|$força qualquer matriz em um desses formatos para o formulário [0 x]durante o mapeamento [0 0]para [0], [a b]onde nem anem bé 0para uma matriz de três elementos e [-x 0]ou [-x -x]para [-x 0]. Em seguida, (!*,1=verifica se temos [0 x].

Finalmente 0]0=`faz o caso de fallback e formatação para saída.

Peter Taylor
fonte
4

Pitão 57 58 61 62

K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

Experimente online.

Bem parecido com outras respostas, mas essa página da Wikipedia não deu muito mais para continuar;) O número mágico 39é o número de posições frias com valores < 99.

Define uma função gque você pode chamar como g 30 25. Retorna []por falha, [(13,8)]em caso de sucesso.

Explicação

K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below 
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98
FryAmTheEggman
fonte
sé convertido para int - salva alguns caracteres /____1. rZ39pode ser substituído por U39, usando um intervalo unário. Da mesma forma, você pode substituir r99)por U99.
Isaacg #
@isaacg Thanks! Eu esqueci completamente U. Eu realmente deveria atualizar a explicação: P
FryAmTheEggman
@isaacg Apenas um pensamento sobre Pyth, acho que você poderia fazer @uma interseção de conjuntos se seu segundo argumento for uma lista agora. É um pouco sem jeito deixado de fora desde que afoi mudado: P
FryAmTheEggman
Essa é uma boa ideia - eu a implementei. Também alterei o código de interseção para permitir alguns truques que não eram possíveis antes, incluindo a interseção de duas listas de listas.
Isaacg
2

Javascript ES6 - 280 bytes

Minificado

r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

Expandido

r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

Algoritmo rápido e agradável. É executado em O (n), mas seria executado em tempo constante, se não fosse por um loop de economia de bytes. O loop é implementado como um incrementador recursivo; portanto, o script eventualmente falhará com um erro de recursão para n na casa das centenas ou milhares. Usa a mesma propriedade de sequência Beatty mencionada pelo Sr. Taylor, mas, em vez de computar a sequência, ela simplesmente adota o (s) termo (s) correto (s).

É executado corretamente em todas as entradas de teste e em muitas dezenas além do que eu testei.

A função a chamar é f. Ele retorna uma matriz de sucesso e uma 0desistência.

COTO
fonte
Espere, a saída de uma matriz está ok?
John Dvorak
@ JanDvorak: O xnor tem uma tupla listada na lista de saídas válidas, portanto achei que sim. Talvez ele possa esclarecer o assunto. É uma correção trivial, pelo menos.
COTO
Uma matriz ou uma matriz singleton do par é boa; vários movimentos vencedores não são.
Xnor
1

Perl 5 - 109 (com 2 bandeiras)

#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

Uso:

$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

Simplesmente calcula a solução para cada entrada possível e apenas faz uma única pesquisa.

nutki
fonte