fundo
AMEAÇA ( M achine E ducable N deveres A nd C rosses E ngine) é um algoritmo de aprendizado de máquina rasa rudimentar para os Noughts jogo e cruzes, criados pela British computador cientista Donald Michie na década de 1960. Foi originalmente implementado com 304 caixas de fósforos, cada uma rotulada com uma posição no tabuleiro e contendo miçangas coloridas (com uma das nove cores, representando possíveis movimentos). Michie calculou que essas 304 caixas de fósforos eram suficientes para todas as combinações de jogadas no tabuleiro.
Os mais matemáticos entre vocês podem perceber que, na verdade, existem 19.683 combinações possíveis de nada, cruzes e espaços em branco em um quadro da N&C; no entanto, ele calculou maneiras de reduzir esse número (para acelerar o algoritmo e provavelmente reduzir as caixas de fósforos!). Primeiro, ele removeu todos os movimentos não possíveis, como:
-------
|X|0|X|
| |0| |
|X|X| |
-------
(dois zeros e quatro cruzamentos)
Em seguida, ele compensou as rotações. Por exemplo, se na caixa de fósforos, vemos:
-------
| |0|0|
|X| |X|
| |0| |
-------
podemos usar a mesma caixa para
-------
| |X| |
|0| |0|
| |X|0|
-------
Portanto, as contas coloridas acima mencionadas representam posições relativas, não absolutas. Por exemplo, se disséssemos que um cordão vermelho significava o canto superior esquerdo, veríamos a imagem na parte superior da caixa e veríamos:
-------
| |0|0|
|X| |X|
| |0| |
-------
então saberíamos que, no caso de ser esse o quadro, a conta vermelha significaria:
-------
|R|0|0|
|X| |X|
| |0| |
-------
Mas se este for o quadro:
-------
| |X| |
|0| |0|
| |X|0|
-------
a conta vermelha significaria
-------
| |X|R|
|0| |0|
| |X|0|
-------
Essas transformações se aplicavam a rotações e inversões (em todas as direções, inclusive na diagonal). Mais uma vez, você só precisa salvar cada caixa de fósforos desta maneira: não faça caixas virtuais separadas para cada transformação!
Outra simplificação que Michie fez foi garantir que o computador funcione primeiro. Dessa forma, ele poderia remover todos os movimentos de primeiro nível, removendo cerca de um quinto das caixas restantes. Por fim, ele removeu todas as caixas de final de jogo (pois não foram necessários mais 'conteúdos' ou movimentos nessas etapas).
Certo, agora no próprio algoritmo (é muito simples):
- Primeiro, decida o que as cores das contas representam. Você precisará de 9 cores para representar cada um dos espaços no quadro.
- No início do jogo, cada uma das 304 caixas de fósforos contém miçangas. Embora as contas tenham cores aleatórias (portanto, duplicatas são ótimas), elas devem ser possíveis movimentos (por isso, se a imagem do estado da placa exibir um 'O' no meio direito, não será possível usar a conta que representa o centro. certo).
- Toda vez que for a vez do MENACE (X), encontre a caixa de fósforos com a posição atual do tabuleiro (ou alguma transformação dela) impressa nela.
- Abra a caixa de fósforos e escolha qualquer conta ali aleatoriamente.
- Descubra como o status do quadro foi transformado para chegar à imagem na caixa de fósforos (por exemplo, girado 90 graus no sentido anti-horário). Em seguida, aplique essa transformação ao cordão (por exemplo, a parte superior esquerda se torna a esquerda).
- Coloque um X nesse quadrado. Remova o cordão selecionado da caixa de fósforos. Se a caixa for deixada vazia como resultado, coloque três contas aleatórias (possíveis) na caixa e escolha uma delas para a mudança.
- Repita 3-6 até o jogo terminar.
- Se o MENACE ganhou o jogo, volte a todas as caixas de fósforos do MENACE. Em seguida, rastreie de que cor o cordão usou nesse movimento. Coloque duas dessa cor de conta na caixa (para que haja a conta original + mais uma, aumentando assim a probabilidade de MENACE fazer esse movimento na próxima vez que chegar a essa posição)
- Se MENACE perder o jogo, não faça nada ( não substitua as contas que ele tirou).
- Se MENACE desenhou o jogo, substitua o cordão usado em cada um dos seus movimentos, mas não adicione um extra, para que você fique com o que começou.
Isso nos deixa com um algoritmo muito simples, mas difícil de implementar. Isso forma a base do seu desafio.
Se você ainda está confuso, consulte http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ - é o que li quando soube pela primeira vez sobre esse algoritmo
Desafio
Jogue um jogo de Tic-Tac-Toe com o computador. Em cada etapa, imprima o conteúdo de todas as caixas de fósforos.
Entradas
- No início do programa, um número dizendo quantos jogos você deseja jogar contra o MENACE
- Depois, após o primeiro turno do MENACE, você insere seu movimento como uma sequência de dois caracteres, sendo a primeira letra "L", "R" ou "M" (esquerda, direita ou meio) referente ao eixo Y. Em seguida, insira outra letra (novamente, "L", "R" ou "M"), desta vez referindo-se ao eixo X. Repita para todos os movimentos e jogos.
Saídas
- No início de cada novo jogo, produza "novo jogo".
- Após cada jogada do jogador, produza o tabuleiro em qualquer formato razoável. Não precisa parecer bonito (por exemplo, uma matriz de matrizes representando as posições da placa é boa).
- Após cada jogada do jogador, MENACE deve fazer uma jogada. Saída do quadro após a mudança da MENACE
- Após cada jogo, produza o conteúdo de todas as 304 caixas de fósforos. As contas podem ser representadas por uma letra, nome de uma cor, caractere ou qualquer sequência ou número inteiro que você desejar (sem ponteiros, funções anônimas, etc.).
Regras
- Isso é código-golfe , então a resposta mais curta em bytes vence.
- Devo ser capaz de inserir movimentos depois de ver a resposta da MENACE. Não 'passe todos os seus movimentos para essa função e observe como o jogo se desenrola'.
- O tabuleiro deve ser limpo entre os jogos.
- As caixas de fósforos não devem ser limpas entre os jogos (isso redefiniria o aprendizado de máquina)
- Você deve ter 304 caixas de fósforos. Qualquer um pode implementar esse algoritmo com todas as 19.683 caixas de fósforos, mas o aprendizado é lento (pois exige muitos jogos para obter todos eles com conteúdo útil).
- A saída pode estar em qualquer formato razoável e a entrada pode ser obtida conforme os padrões PPCG (desde que esteja em conformidade com a regra 2). Se você precisar ajustar o formato de entrada (conforme descrito na seção ' Entrada '), tudo bem, desde que faça sentido.
- Um jogo termina quando um jogador vence (fazendo três em sequência na diagonal, horizontal ou vertical) ou se houver um empate (o tabuleiro está cheio e não há vencedor)
- Embora o MENACE precise fazer possíveis movimentos (e só tenha contas possíveis dentro de cada caixa de fósforos), para o desafio, você não precisa validar a entrada do usuário. Se eles digitarem algo errado, seu programa poderá fazer o que for (enlouquecer, lançar erro etc.) - você pode assumir que a entrada está correta.
fonte
[[0, 2, 6], [4, 8, 4, 3, 3], [7, 7, 7, 7, 7, 7, 7, 8], [1], ... [3, 3, 5, 4]]
.Respostas:
R , 839 bytes
Experimente online!
Uma resposta bastante longa, mas este não foi um desafio direto. O link do TIO aqui falhará porque espera uma entrada interativa. Aqui está uma versão que joga contra um segundo jogador aleatório que escolhe um lugar aleatoriamente. A saída para esta segunda versão é apenas a vencedora (1, 2 ou 0 para um empate.) As caixas de fósforos são inicializadas para todas as posições do tabuleiro, mas usadas apenas para o 304 conforme a especificação. Eles são implementados como cópias do quadro com números negativos para indicar o número de contas em cada posição. Eu experimentei uma lista de vetores de acordo com a especificação original, mas era menos intuitiva.
Esta é uma versão menos golfe com comentários (mas nomes curtos de variáveis). Observe que ele não imprime as caixas de fósforos porque são muito longas. Ele pode implementar um jogador interativo 2, um jogador aleatório 2 ou a mesma estratégia de caixa de fósforos do jogador 2.
fonte