Jogos ideais de Tic Tac Torus

31

Este desafio é sobre o jogo Tic Tac Toe, mas é jogado em um toro.

Como jogar

Para criar o tabuleiro necessário, comece com um tabuleiro regular de jogo da velha. Primeiro dobre-o em um cilindro juntando as bordas esquerda e direita. Em seguida, dobre-o em toro juntando a borda superior e inferior. Aqui está uma visualização simples desse tabuleiro de jogo com alguns movimentos jogados (habilidades do Sick Paint!).

Tic Tac Torus

As regras do Tic Tac Toe em um toro são as mesmas do Tic Tac Toe comum. Cada jogador coloca Xs e Os alternados. O primeiro com 3 mesmos símbolos seguidos, uma coluna ou um na diagonal vence.

Como um toro é bastante difícil de visualizar, simplesmente projetamos o cartão de volta em um papel. Agora podemos jogar o jogo como Tic Tac Toe regular. A única diferença é que você também pode ganhar com 3 mesmos símbolos em uma diagonal quebrada. Por exemplo, o Jogador 1 (X) vence o seguinte quadro. Você pode ver isso facilmente, alterando um pouco a visão no toro.

O jogador 1 (X) vence por causa de 3 Xs em uma diagonal quebrada

Se você estiver interessado, você pode jogar Tic Tac Toe em um Torus nos Torus Games . Existe uma versão para Windows, Mac e Android.

Optimal Games

Neste desafio estavam interessados ​​em jogos ótimos. Um jogo ideal é um jogo em que ambos os jogadores jogam uma estratégia ideal. Em um tabuleiro regular de Tic Tac Toe, os jogos ideais sempre terminam em empate. Fascinantemente em um toro sempre o primeiro jogador vence. De fato, um jogo em um tabuleiro de toro nunca pode terminar em empate (também se os jogadores não jogarem o ideal).

A estratégia ideal é realmente fácil:

  • Se você pode ganhar colocando seu símbolo, faça-o.
  • Caso contrário, se o seu oponente tiver dois símbolos em uma linha / coluna / diagonal, tente bloqueá-lo. Caso contrário, faça o que quiser.
  • Caso contrário, faça o que quiser.

Todo jogo ideal consiste em exatamente 7 jogadas e essas jogadas podem ser descritas da seguinte maneira:

  1. O jogador 1 coloca um X em qualquer lugar do tabuleiro (9 opções)
  2. O jogador 2 coloca um O em qualquer lugar do tabuleiro (8 opções)
  3. O jogador 1 coloca um X em qualquer lugar do tabuleiro (7 opções)
  4. O movimento do jogador 2 pode ser forçado (1 opção); caso contrário, ele coloca o O em qualquer lugar (6 opções)
  5. A jogada do jogador 1 é forçada (1 escolha)
  6. O jogador 2 está preso em um garfo (o jogador 1 pode vencer de duas maneiras diferentes); portanto, o jogador 2 precisa bloquear o jogador 1 de uma maneira (2 opções)
  7. O jogador 1 coloca seu último lance e ganha (1 escolha)

Existem 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 jogos ótimos diferentes em nosso quadro projetado. Aqui você pode ver um jogo ideal típico:

Exemplo de um jogo ideal

Se rotularmos cada célula do tabuleiro com os dígitos 0-8, podemos descrever esse jogo pelos dígitos 3518207. Primeiro, um X é um local na célula 3 (linha do meio, coluna da esquerda), que um O na célula 5 (linha do meio, coluna da direita), que um X na célula 1 (linha superior, coluna do meio), ...

Usando essa notação de dígito, geramos automaticamente um pedido. Agora podemos classificar todos os 1728 jogos ideais e temos a lista:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Desafio

Esta lista faz parte do seu trabalho. Você receberá um número kentre 0 e 1727 e precisará retornar o kjogo em notação de dígitos dessa lista classificada.

Escreva uma função ou um programa que receba o número k( número inteiro) calcule o jogo correspondente. Você pode ler a entrada via STDIN, argumento de linha de comando, argumento de prompt ou função e imprimir o resultado (7 dígitos) em um formato legível (por exemplo, 0123845ou [0, 1, 2, 3, 8, 4, 5]) ou retorná-lo usando uma sequência (formato legível por humanos) ou um número inteiro (contendo todos os dígitos na base 10) ou em qualquer formato de matriz / lista.

O tipo de desafio é o código-golfe. Portanto, o código mais curto vence.

Jakube
fonte
Por que o primeiro movimento do jogador 2 precisa estar na mesma linha ou coluna que o primeiro movimento do jogador 1? Joguei alguns jogos na minha cabeça em que o primeiro movimento do jogador 2 está em uma das mesmas diagonais e eles seguem o mesmo padrão de jogo ideal. Parece-me que um dos aspectos do tabuleiro toroidal é que linhas, colunas e diagonais têm efeitos simétricos no jogo.
precisa saber é o seguinte
@ Runer112 Simplificou muito a estratégia ideal. A única regra agora é bloquear seu oponente, se puder, caso contrário, faça o que quiser.
Jakube
7
Apenas um comentário secundário: na verdade, há muito menos jogos únicos possíveis aqui. A simetria translacional torna a posição do primeiro movimento irrelevante (porque você sempre pode centralizar sua visualização), então divida por 9 ... e a rotação do tabuleiro faz apenas dois segundos segundos diferentes (diagonal ou quadrado adjacente) ... mais 48 jogos distintos. Se você considerar a simetria da reflexão, ela diminui ainda mais. Esta versão do toro é muito mais chata do que a versão normal. Golfe de distância.
Orion
@orion Na verdade, o fato de o toro envolver, não nos impede de pensar em '0' como o 'primeiro' reto no quadro de toro e distinguir todos os nove campos em geral ... No entanto, concordamos que o "meridiano 0" esteja em Greenwich , enquanto no lado oposto da Terra podemos estar com uma perna no local onde é quinta-feira, uma perna no local é quarta-feira (diferença de 24 horas no horário local!) - e apesar de a Terra ser redonda e não ter um "ponto de partida" ...
pawel.boczarski 15/04
@ Rodney Nope, é um, não um sete. Tente calcular.
Jakube

Respostas:

6

JavaScript (ES6), 266308317333434

Uma função retornando uma string. Edit Encontrou uma solução aritmética para a função M (finalmente!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Muito ingênuo , pode ser reduzido de várias maneiras . Simplesmente enumera todos os possíveis valores legais e retorna o que é encontrado no local n. A função M retorna a posição entre duas células, que é o movimento obrigatório para bloquear um jogador oposto.

Mais legível

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position
edc65
fonte
3

Oitava, 467369363309297 caracteres

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

A única mudança relevante é que nunca verificamos se o jogador atual pode vencer, apenas verificamos a possibilidade do adversário de vencer no próximo turno . Como o único turno que o jogador pode vencer é o turno 7 , este é o único local em que o algoritmo produziria um jogo que não é ideal, mas é muito fácil filtrar essa situação. Simplesmente verificamos cada jogo gerado se ele foi vencido pelo jogador 1 - se não foi, a jogada por sua vez 7 foi incorreta, por isso não adicionamos esse jogo à tabela de jogos ideal.

(Exatamente metade dos jogos gerados por esta regra é falsa, ou seja, no 7º turno, o jogador 1 sempre tem duas possibilidades de bloquear o jogador dois, mas apenas um o fará vencer instantaneamente).

Usar:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

O código ungolfed se parece com:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));
pawel.boczarski
fonte
1
pequena dica: você pode cortar versões antigas se eles usam a mesma lógica uma vez que estas são armazenadas no histórico de edições para que eles ainda estão disponíveis
masterX244