No jogo 15, dois jogadores se revezam na seleção de números de 1 a 9 (sem escolher nenhum número que um dos jogadores já tenha selecionado). Um jogador vence se tiver três números que somam 15. Se todos os números foram selecionados e nenhuma combinação dos dois somar 15, então o jogo está empatado.
Sua tarefa é criar uma função que leva o estado de um jogo de 15 (representado na forma que você desejar) e retorna o número a ser movido a seguir, que atuará como uma IA para jogar com outro jogador. Você pode assumir que a posição é legal (nenhum jogador tem mais de um número a mais que o outro jogador e nenhum jogador já tem três números que somam 15).
A IA deve ser perfeita - isto é, se receber uma posição vencedora, deve forçar uma vitória e se receber uma posição não perdida (uma posição em que seu oponente não tem uma estratégia vencedora), não deve permitir sua vitória. oponente para lhe dar uma posição perdida (o que é possível, pois 15 é um jogo resolvido).
O código mais curto vence.
(observação: aceitarei a resposta mais curta atualmente e a alterarei se aparecer uma resposta mais curta.)
Respostas:
GolfScript (
129 86 81 8575 caracteres)Formato de entrada esperado:
[[int int ...][int int ...]]
onde a primeira lista é meus números e a segunda lista são os números do meu oponente. Para teste interativo, adicione~N
no final do script e forneça uma string nesse formato: por exemploHeurísticas:
5
é o único número que pode contribuir para ganhar de quatro maneiras, então pegue-o, se disponível.Estrutura de teste:
fonte
[5][3]
(deve retornar 4 ou 8).9
- mas parece que você mudou as regras.4
ou8
?7
deve funcionar, por isso9
é aceitável.Ruby,
330 315341 caracteresPor enquanto, reteremos os detalhes, mas digamos que ele se baseia no algoritmo ideal para um problema semelhante que também foi resolvido e cujo algoritmo ideal funcionou tão bem aqui.
Foram feitas suposições - isso escolherá jogadas ruins em situações que não podem ser produzidas por esse algoritmo jogando contra outro jogador, apenas por dois jogadores um contra o outro.Entrada: uma matriz de duas matrizes de cadeias de caracteres de um dígito. Cada matriz representa os valores obtidos por um jogador - o primeiro é o AI, o segundo é o oponente.
Saída: um número ou uma sequência de um dígito. Eles são semanticamente equivalentes. A normalização para strings custaria 8 caracteres.
Mais três caracteres podem ser salvos se assumirmos a ordem dos números dados pelo chamador - altere a expressão regular em L5 para
/^285$/
ou/^258$/
dependendo da ordem produzida no jogo(opponent)5-(ai)2-(opponent)8
.fonte
5
para o início do seu pedido de preferência.GolfScript (
90 8584 caracteres)Isso adota uma abordagem completamente diferente, mas é potencialmente suscetível a otimizações para superar a heurística. Aqui fazemos uma análise completa da árvore do jogo, incrivelmente devagar. (Não, quero dizer. Demora várias horas para executar o teste completo, principalmente por causa do
`{...}+
que adiciona o estado atual ao loop do próximo movimento). Observe que a parte difícil é identificar um estado vencedor (um terço do código, atualmente).Existem alguns hacks feios nas seções não recursivas. Em particular, quando a posição é identificada como perdida, tomamos nossas posições como
[value move]
matriz, confiando no movimento como sendo irrelevante e o valor sendo diferente de zero.fonte