Jogue um jogo perfeito de 4x4 Hex

10

fundo

Hex é um jogo de estratégia abstrata para dois jogadores, jogado em um K×Klosango 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 = 4e representamos o quadro como a seguinte grade. As linhas grossas denotam blocos adjacentes.

Uma grade 4x4.

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:

  1. Entrada de STDIN, saída para STDOUT.
  2. Entrada como um argumento de linha de comando, saída para STDOUT.
  3. Entrada como 16 argumentos de linha de comando de caractere único, saída para STDOUT.
  4. 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:

  1. Um índice baseado em zero (conforme usado na figura acima).
  2. Um índice baseado em um.
  3. A cadeia de entrada com uma Esubstituído por qualquer dos Wou Bque 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.

Zgarb
fonte
Esse desafio me lembra de tentar compactar uma IA do tic tac toe quando eu estava escrevendo programas de calculadora. ticalc.org/archives/files/fileinfo/354/35408.html
Sparr
2
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.Eu deveria ter vencido há muito tempo, ou estou errado?
Sebastian Höffner
@ SebastianHöffner Isso parece um bug no controlador. Vou tentar consertar quando tiver tempo.
Zgarb
@ SebastianHöffner O bug agora deve ser corrigido.
Zgarb

Respostas:

6

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 Ee produzirá a posição indexada em zero do próximo movimento da branca.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

Acho que provavelmente posso jogar cerca de 200 caracteres com uma melhor ramificação e eliminação da reutilização do código.

Sparr
fonte
Eu adicionei a opção para 16 argumentos de linha de comando e atualizei o script do verificador, para que esta solução possa ser testada.
Zgarb 27/06/2015
Marbelous +1 (PPCG pensa adicionando esses personagens melhorou comentário)
Rohan Jhunjhunwala
1

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])
  • Jogador: BLACK
  • Método: STDIN / STDOUT, MODIFIED_BOARD

A estratégia é primeiro procurar um Bno quadro. Se não houver, isso retornará -1, que em python é o mesmo que last 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 Elugar nenhum ), não me mexo.

O printparece 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 e b[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:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Teste

Ao executar o conjunto de testes do controlador hexadecimal, encontrei um comportamento estranho:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

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:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Isso levará ao seguinte:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

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.

Sebastian Höffner
fonte