Qual é o seu próximo passo?

18

Esse desafio é escrever uma função minimax no idioma de sua escolha, para produzir a próxima melhor jogada em um jogo NxN de jogo da velha, considerando o estado atual do tabuleiro . A entrada da placa pode ser aceita como uma matriz, uma coleção 2D ou qualquer outra coisa que faça sentido para você, mas siga as regras . A saída é a próxima melhor jogada para quem quer que seja , atualmente , onde X é considerado como tendo iniciado .

Antecedentes Rápidos do Algoritmo Minimax

A idéia básica do algoritmo minimax é enumerar todos os resultados possíveis como um DAG e ponderá-los pelo benefício que a sequência de movimentos tem para o jogador, codificada pelo primeiro movimento realizado. Todos os resultados possíveis são 'agrupados' pela primeira jogada e são pontuados com base na soma de todos os resultados (-1 para uma perda, 0 para um empate e 1 para uma vitória). Nas implementações que exigem que vários jogadores joguem, você enumera todos os movimentos possíveis pelo jogador e todas as respostas possíveis dos adversários. Por exemplo, em um jogo do jogo da velha (após o primeiro movimento), existem 8 possíveis primeiros movimentos que você pode fazer, e todos podem parecer iguais ao analisar apenas o próximo turno. Mas iterando todos os resultados possíveis para cada conjunto de movimentos possível que resulta em um resultado final e resumindo todos eles,

Para um resumo melhor, mais aprofundado e contextual do algoritmo mini-max em termos de jogo da velha, leia mais aqui: http://neverstopbuilding.com/minimax

XKCD (somente solução 3x3)

Todos os movimentos possíveis para um jogo 3x3 de jogo da velha.

As regras

  • Qualquer idioma pode ser usado, mas nenhuma biblioteca minimax externa é permitida.
  • A saída pode ser uma coordenada (0-n, 0-n) ou um número (1-n * n) indicativo da melhor jogada seguinte.
    • Além disso, você deve ser capaz de identificar quando o melhor cenário é uma perda ou um empate, em vez de uma vitória.
    • A maneira como você denota uma perda ou um empate depende, mais uma vez, de você.
  • A entrada deve usar o X e O tradicional e você deve assumir que X se move primeiro; espaços em branco podem ser representados por qualquer coisa.
  • Você pode assumir que todas as entradas que entram no seu programa têm n O e n + 1 X, ou seja, você pode assumir que está obtendo um quadro bem formado.
  • O estado atual da placa deve ser a única entrada para o seu programa; se você estiver usando recursão, métodos auxiliares deverão ser feitos para facilitar os requisitos de entrada. Consulte /codegolf//a/92851/59376 para obter esclarecimentos.
  • Qualquer valor de 10> = n> = 1 deve ser suportado; se o seu programa "exceder o tempo limite" para n> 10, também acho isso aceitável, pois alguns idiomas têm um poder de processamento significativamente menor (especialmente usando consoles da Web).

A julgar

  • Isso é código-golfe, portanto a contagem de bytes mais baixa do programa vence e as brechas padrão são universalmente proibidas.
  • Em caso de empate, o programa que suportar o maior 'n' vencerá.

Exemplo de entradas

2x2

[[X,O]
 [-,-]]

Saída: 2 ou [0,1] (3 ou [1,1] também seria discutivelmente correto) (Alguma forma de indicação da localização, arbitrária, desde que você possa explicar facilmente o formato usado)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Saída: -1 (perda)


Mais uma vez, qualquer formato de entrada desejado é permitido, mas X e O devem ser usados, os exemplos fornecidos não foram feitos para restringir esse formato, apenas para inspirar.

Urna de polvo mágico
fonte
Desculpe DJMCMayhem, eu realmente tentei marcar essas coisas, mas não consegui, pois sou novo aqui.
Magic Octopus Urn
Bônus também removido, acrescentou nada além de tédio.
Magic Octopus Urn
É permitido o seguinte formato de saída: um diagrama da posição do tabuleiro com, em cada espaço originalmente vazio, um caractere único, indicando se o jogo leva a uma vitória / perda / empate (por exemplo, W, L e D)
Ton Hospel,
1
No exemplo 3x3, O deve perder, não importa o que ele toque, mas você diz que a saída deve ser [2,1], por que isso?
Dada
Editado, boa captura. Não sei o que eu estava pensando, esse foi o exemplo negativo.
Magic Octopus Urn

Respostas:

8

Perl, 101 98 bytes

Inclui +4para-0p

Execute com a entrada em STDIN

tictactoe.pl
OXO
---
--X
^D

A saída é o mesmo diagrama, mas com cada movimento atualizado com seu status, 1representa uma vitória, 2representa um empate e 3representa uma perda. Para este caso, isso seria

OXO
223
21X

então 3 jogadas empatam, 1 vence e 1 perde (atualizarei a solução se este formato de saída for inaceitável, mas o código básico permanecerá o mesmo)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Isso já é muito lento e usa muita memória para a placa 3 * 3 vazia (por que, na verdade, a recursão não é tão profunda. Deve haver algum vazamento de memória). Adicionar memoizing custa 6 bytes, mas é muito mais saudável:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Ton Hospel
fonte
Uau, com vista para o fato de que é pl e provavelmente não funcionaria absolutamente para n = 10 com muitos vazios ... Você fez as duas coisas que esperava ver alguém fazer. Uma entrada de string e mapeando o resultado para todos os movimentos, não apenas os melhores. Bravo.
Magic Octopus Urn
Se uma função recursiva 'vazar', como pode estar ok ??? Muito alto linguagem make não ver o registo de 32 bits na CPU (ou algo como que a instrução simples)
RosLuP
@RosLup Vazamento neste contexto não significa necessariamente memória perdida inacessível. O Perl é bastante peculiar quando libera memória, frequentemente fazendo isso mais tarde do que o esperado e, portanto, usando muito mais memória do que o esperado. Também tende a alocar mais do que o necessário diretamente, na expectativa de que você amplie suas estruturas de dados. Nesse caso, o uso de recursão "normal" com uma função, em vez do abuso de do$0, usaria 10 vezes menos memória. Lembre-se, este caso é tão extremo que pode realmente ser um vazamento de memória real.
Ton Hospel 27/09/16
Não só não ver os registos ou as instruções de base (das instruções Hlls), mas perder o controle do uso de memória ... Para mim eles não escala ...
RosLuP
Já faz bastante tempo, você venceu meu homem, mas infelizmente não tivemos mais tentativas.
Magic Octopus Urn
2

Javascript (ES6), 320 294 bytes

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Entrada

1) Uma matriz de matriz de caracteres que descreve a placa atual, como:

[['X', '-'], ['-', 'O']]

2) Um número inteiro descrevendo o turno atual: 1 = X, -1 =O

Resultado

Uma matriz composta por:

  • uma matriz que descreve a melhor jogada no [x, y]formato
  • o resultado do jogo como um número inteiro: 1 = vitória, -1 = perda, 0 = empate

Exemplo

No exemplo a seguir, Xé garantido que você ganha jogando [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

UM JOGO ESTRANHO. O único movimento vencedor não é jogar.
QUE TAL UM BOM JOGO DE XADREZ?

Arnauld
fonte
Bem feito, boa primeira entrada. Somente as observações que tenho têm o potencial de salvar bytes com as informações fornecidas 'X sempre se moverá primeiro'. E você já tentou com uma placa não 3x3;)?
Magic Octopus Urn
@carusocomputing - Não se esqueça de entender o que você tem em mente com 'X sempre se moverá primeiro'. Poderia ser usado para deduzir qual lado está em movimento, considerando apenas o quadro, mas computando que realmente custaria mais bytes; então eu acho que você está falando de outra coisa. E sim, eu fiz alguns testes com placas um pouco maiores. Isso deve funcionar como esperado, contanto que ... err ... não haja muitas posições vazias. :-)
Arnauld 10/09
O desafio diz The current state of the board must be the only input to your program. Seu código precisa de duas entradas, o que quebra essa regra.
Dada
1
@ Dadá - Eu estava pensando sobre isso, mas eu assumi que a cor ativa faz parte do estado do tabuleiro (assim como uma posição no xadrez sempre vem com cores ativas + em quadrado passivo + disponibilidade de castelos). Acho que o OP deve esclarecer esse ponto. (E se você está certo, isso soa como uma dificuldade adicional desnecessária, IMHO.)
Arnauld
1
Mmm .. eu realmente gosto da explicação do estado da placa em sua resposta. Pensando nisso, algumas linguagens podem usar apenas cadeias de caracteres como entrada, pois seria difícil decifrar uma placa como XXOOXO-OO em contagens baixas de bytes, sem informações adicionais, como as dimensões da placa. Permitirei quaisquer entradas adicionais que contribuam para o estado da placa, embora eu ainda ache que a informação 'suponha que o X se mova primeiro' seja diferente de 'dada a quem for'. Alguns idiomas aproveitarão isso como uma suposição;).
Magic Octopus Urn