Tic-Tac-latino!

Esta é uma história verdadeira, então os nomes foram alterados.

Meu professor de latim, Sr. Latin, criou sua própria variante proprietária (sem brincadeira). Vamos chamar de tic-tac-latin. O jogo é simples, é essencialmente tic tac toe jogado em uma grade de quatro por quatro.

Declaração formal de regra

Uma linha é uma linha, coluna ou uma diagonal. Existem dois símbolos, 'X' e 'O', mas um ou ambos podem ser substituídos por um símbolo diferente.
Você marca um ponto quando possui três do seu símbolo e um do outro personagem.

Estes arranjos pontuam:

--- O
-O--
XXXO
XOOX

O -XX
- O -
- X -
--- O

Estes não pontuam:

----
XXXX
----
OOOO

----
XXX-
----
OOO-

O jogo é ganho sempre que um jogador tem mais pontos que outro. O jogo é empatado apenas se o tabuleiro estiver cheio.

Desafio

Resolva este jogo. Seu trabalho é fornecer uma maneira de garantir uma vitória ou empate, o que for o resultado ideal.

Sua solução pode optar por iniciar primeiro ou segundo (e, portanto, pode escolher seu símbolo). Não é obrigatório implementar um jogo interativo em que as entradas do usuário se movam e a exibição correspondente seja alterada. Também pode ser uma função ou programa que recebe a entrada como um estado do jogo e gera um novo tabuleiro ou uma descrição de sua jogada . Qualquer uma das opções deve ser executada em aproximadamente dez segundos por movimento realizado.

---

Jogar seu jogador contra qualquer sequência de movimentos deve dar o resultado ideal. Isso significa que você pode assumir que a posição de entrada é aquela que pode ser alcançada com o player. Os envios devem ser determinísticos e não precisam necessariamente fornecer uma prova de otimização, mas se forem quebrados (por serem derrotados), seus envios serão considerados inválidos (você pode deixar para lá, mas adicionar (quebrado) no título).

---

Essa é uma tarefa não trivial, portanto, qualquer envio válido é impressionante e merece um visto aceito, mas tornarei o código de golfe o principal critério de vitória.

O vencedor é escolhido descendo esta lista até que um vencedor seja escolhido.

• Implementação resolvida mais curta que sempre vence
  
• Implementação mais curta
  

Perl, 147 bytes (não concorrente, leva mais de 10 segundos por movimento)

Inclui +4 para -0p

O programa é reproduzido X. Jogará um jogo perfeito.

Insira a placa no STDIN, por exemplo:

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

A saída será a mesma placa, com todas Xsubstituídas por Oe vice-versa. As vagas vazias serão preenchidas com um número indicando o resultado se X for jogado lá, o que 1significa que o resultado será uma vitória, 2um empate e 3uma perda. Um jogo terminado retorna a mesma posição com as cores invertidas.

Neste exemplo, a saída seria:

1O1X
1O33
O3O3
X33X

Portanto, a posição é uma vitória, Xse ele jogar nos 3 lugares ao longo do topo e da esquerda. Todos os outros movimentos perdem.

Essa saída confusa é realmente conveniente se você quiser saber como o jogo continua após uma jogada. Como o programa sempre é reproduzido, Xvocê deve trocar Xe Over os movimentos O. Aqui, por exemplo, é bem claro que Xganha ao jogar no canto superior esquerdo, mas e se Xjogar na terceira posição ao longo do topo? Basta copiar a saída, colocar um Olugar no movimento que você selecionar e substituir todos os outros números -novamente, então aqui:

-OOX
-O--
O-O-
X--X

Resultando em:

3XXO
3X33
X3X3
O33O

Obviamente, todo movimento Odeve perder, então como ele perde se jogar no canto superior esquerdo? Novamente, faça isso colocando Ono canto superior esquerdo e substituindo os dígitos por -:

OXXO
-X--
X-X-
O--O

Dando:

XOOX
1O33
O3O3
X33X

Então X tem apenas um caminho a percorrer para sua vitória:

XOOX
OO--
O-O-
X--X

Dando

OXXO
XX33
X3X3
O33O

A situação para Opermanece sem esperança. É fácil ver agora que cada movimento permite Xganhar imediatamente. Vamos pelo menos tentar fazer 3 O's seguidos:

OXXO
XX--
X-X-
O-OO

Dando:

XOOX
OO13
O3O3
X3XX

Xjoga a única jogada vencedora (observe que isso ocorre XXXOna terceira coluna:

XOOX
OOO-
O-O-
X-XX

Aqui a saída é:

OXXO
XXX-
X-X-
O-OO

porque o jogo já estava terminado. Você pode ver a vitória na terceira coluna.

O programa atual tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Aplicado ao tabuleiro vazio, ele avalia 9506699 posições, o que leva 30 GB e 41 minutos no meu computador. O resultado é:

2222
2222
2222
2222

Assim, cada movimento inicial é empatado. Então o jogo é um empate.

O uso extremo da memória é causado principalmente pela recursão em uso do$0. O uso desta versão de 154 bytes usando uma função comum precisa de 3Gb e 11 minutos:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

o que é mais suportável (mas ainda é demais, algo ainda deve estar vazando de memória).

A combinação de várias acelerações leva a esta versão de 160 bytes (5028168 posições, 4 minutos e 800M para o tabuleiro vazio):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

Esse último usa 0para uma vitória (não confunda O), 1para um empate e 2para uma derrota. A saída deste também é mais confusa. Ele preenche a jogada vencedora para X no caso de uma vitória sem troca de cores, mas se o jogo de entrada já foi ganho, ainda assim a troca de cores e não preenche nenhuma jogada.

É claro que todas as versões ficam mais rápidas e usam menos memória à medida que a placa se enche. As versões mais rápidas devem gerar um movimento em menos de 10 segundos assim que 2 ou 3 movimentos forem feitos.

Em princípio, esta versão de 146 bytes também deve funcionar:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

mas na minha máquina ele aciona um bug perl e despeja o núcleo.

Todas as versões, em princípio, ainda funcionarão se o cache da posição de 6 bytes feito por $$_||=for removido, mas isso usa tanto tempo e memória que funciona apenas para placas quase cheias. Mas, em teoria, pelo menos eu tenho uma solução de 140 bytes.

Se você colocar $\=(custo: 3 bytes) imediatamente antes do $@<=>0painel, cada placa de saída será seguida pelo status de todo o painel: 1para Xvitórias, 0empates e -1perdas.

Aqui está um driver interativo baseado na versão mais rápida mencionada acima. O motorista não tem lógica para quando o jogo terminar, então você deve se parar. O código golfado sabe embora. Se a jogada sugerida retornar sem -substituir por nada, o jogo acabou.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 bytes

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

Uso

O "bot" tocará em segundo.

Desenhe uma grade 4x4 numerada assim:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Vamos executar isso no console do navegador: basta colocar f=antes do código

Então, se eu quiser começar 1, eu correria f([1])([])e isso me dará 14.

Boa jogada ... E se eu jogar 2depois? f([2,1])([14]). Voltará 13.

Deixe-me tentar se render. Tocar 3. f([3,2,1])([14,13]). Oh 0! Você me pegou!

Tocar 0? f([0,2,1])([14,13]). 15Ok, vamos continuar jogando ...

Nota

1. Jogue interativamente. Comece com f([your-step])([]).

2. Anexe seu próximo passo. (Veja a demonstração acima)

3. Ajude o "bot" a inserir suas etapas. Não fornecerá bons resultados se você definir aleatoriamente. (Como f([1,2,4])([14,12])vai dar 14- Ei, o bot queria jogar na 13segunda jogada!

Sumário breve

Enquanto você não se render, o bot fará um movimento de espelho.

Obrigado @EHTproductions por me dizer que eu li mal as regras do jogo e as dicas de golfe: P

Agora também detectará se conseguiu um xeque-mate. Se sim, bloqueie-o!

Suas prioridades: Bloco> Espelho> (fallback) procuram maneiras de reproduzir um espelho