fundo
Hex é um jogo de estratégia abstrata para dois jogadores, jogado em um K×K
losango de peças hexagonais. Dois lados opostos do losango são de cor branca, e os outros dois pretos, e os dois jogadores, preto e branco, revezam-se colocando um símbolo de sua cor em um ladrilho desocupado. O jogador que primeiro conseguir construir um caminho entre os lados opostos de sua cor é o vencedor. Sabe-se que o jogo não pode terminar em empate e que o primeiro jogador tem uma estratégia vencedora, independentemente do tamanho do tabuleiro (consulte a página da Wikipedia para obter detalhes).
A tarefa
Nesse desafio, fixamos o tamanho do quadro em K = 4
e representamos o quadro como a seguinte grade. As linhas grossas denotam blocos adjacentes.
Sua tarefa é produzir uma estratégia vencedora para o primeiro jogador, que você pode escolher ser preto ou branco. Isso significa que, qualquer que seja o lance legal que o jogador adversário faça, seu jogo deve resultar em vitória. Sua entrada é uma posição de jogo (o arranjo de fichas no tabuleiro) e sua saída é uma jogada legal, no formato especificado abaixo. Se você quiser encontrar uma estratégia vencedora, não leia este spoiler:
Esboço de uma possível estratégia vencedora, supondo que o branco seja o primeiro. Primeiro, selecione 5. Depois disso, se você tiver um caminho de 5 até a linha inferior OU o preto selecionar 0 ou 1 a qualquer momento, responda selecionando o que estiver 0 ou 1 vazio. Se o preto selecionar 9 ou 13, selecione 10 e, em seguida, o que estiver entre 14 ou 15 está vazio. Se o preto não selecionar 9, 13 ou 14, selecione 9 e o próximo, conforme o que estiver 13 ou 14, estiver vazio. Se o preto selecionar 14, responda selecionando 15. Em seguida, selecione 10 se estiver vazio; se o preto selecionar 10, responda com 11. Se o preto selecionar 6, responda com 7 e, em seguida, o que estiver 2 ou 3 vazio. Se o preto não selecionar 6, selecione-o para ter um caminho de 5 até a linha inferior.
Entrada e saída
Sua entrada é uma sequência de 16 caracteres WBE
, que significa branco, preto e vazio. Eles representam os blocos do tabuleiro, conforme enumerados acima. Você pode escolher o método de entrada (que também determina seu método de saída) entre as seguintes opções:
- Entrada de STDIN, saída para STDOUT.
- Entrada como um argumento de linha de comando, saída para STDOUT.
- Entrada como 16 argumentos de linha de comando de caractere único, saída para STDOUT.
- Entrada como argumento da função nomeada, saída como valor de retorno.
Sua saída representa o bloco no qual você coloca seu próximo token, pois é a sua vez de se mover. Você pode escolher entre os seguintes formatos de saída:
- Um índice baseado em zero (conforme usado na figura acima).
- Um índice baseado em um.
- A cadeia de entrada com uma
E
substituído por qualquer dosW
ouB
que você escolheu para o seu leitor.
Regras
Sua estratégia deve ser determinística. Não é necessário que você lide corretamente com as posições de jogo inacessíveis do tabuleiro vazio usando sua estratégia ou com as posições que já estão ganhando para um dos jogadores, e você poderá colidir com elas. Por outro lado, em quadros acessíveis através de sua estratégia, você deve retornar uma ação legal.
Isso é código-golfe, então a menor contagem de bytes vence. As brechas padrão não são permitidas.
Teste
Eu escrevi um controlador Python 3 para validar entradas, pois seria extremamente tedioso fazer isso manualmente. Você pode encontrá-lo aqui . Ele suporta os três primeiros formatos de entrada e as funções do Python 3 (funções em outras linguagens precisam ser agrupadas em programas), todos os três formatos de saída e os dois players. Se uma estratégia não estiver ganhando, ela produzirá um jogo perdedor encontrado, para que você possa ajustar seu programa.
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.
Eu deveria ter vencido há muito tempo, ou estou errado?Respostas:
Marbelous, 973b
Esta é uma implementação ingênua da estratégia sugerida na pergunta. Ele espera que a placa seja fornecida com 16 parâmetros de linha de comando / placa principal
hex.mbl B W E E E W E E E B E E E E E E
e produzirá a posição indexada em zero do próximo movimento da branca.Acho que provavelmente posso jogar cerca de 200 caracteres com uma melhor ramificação e eliminação da reutilização do código.
fonte
Python 3, 100b
A estratégia é primeiro procurar um
B
no quadro. Se não houver, isso retornará-1
, que em python é o mesmo quelast index
. Assim, em um tabuleiro vazio, meu primeiro índice seráindex=-1
, e é aí que começo a me mover.Se o campo à minha esquerda (
index-1
) estiver livre, minha próxima jogada será lá. Se for tirada, subo à esquerda. Nunca preciso subir: se o fizer, perco o ritmo e perderei o jogo.Em uma pensão completa (sem
E
lugar nenhum ), não me mexo.O
print
parece um pouco estranho no começo: Eu tenho que construir a nova diretoria (que eu via corte), mas então eu preciso cortar 16 caracteres. Isso é uma relíquia, pois trabalho com índices negativos eb[i+1:]
, assim, retornarei a placa do furo e o restante que espero, tornando importante cortar o restante. Outra maneira seria trabalhar com índices positivos, por exemplo, tomando(b.find('B')+16)%16
, mas(+16)%16
é um byte a mais que()[:16]
.Ungolfed:
Teste
Ao executar o conjunto de testes do controlador hexadecimal, encontrei um comportamento estranho:
Acho que eu deveria ter vencido após o quarto turno ou responder com a mesma placa a uma placa completa deve ser uma resposta correta. Não tenho certeza do que está errado lá, não mergulhei muito fundo - eu só queria verificar se tenho todos os casos "especiais" cobertos. Mas como não preciso encobrir situações em que alguém começa no espaço 4, mais ou menos, isso não importa.
85b
No entanto, se eu me permitir não verificar se há uma pensão completa (ou seja, deixar de fora
'E' in b
, posso simplificar ainda mais o código para usar apenas 85 bytes:Isso levará ao seguinte:
Isso pode ou não ser contado, e como eu achei que não era uma jogada válida, decidi buscar a resposta mais longa, mas mais correta.
fonte