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)

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.

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

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?}