Determinar o vencedor do Connect 4

19

Você recebe uma grade do Connect 4 parcialmente preenchida (7x6).

O X             
O X          
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(A entrada pode ser fornecida como uma matriz 1D ou 2D e como letras ou números, etc.)

Assuma isso

  • X começou o jogo.
  • Ninguém ganhou ainda.
  • Os jogadores podem não ter jogado bem até agora, mas agora eles vão empregar estratégias ótimas.
  • A grade de entrada não está com defeito.

Você deve gerar um valor único que indique qual jogador vence (ou empata)

Código de desafio de golfe; o código mais curto vence. Seu programa não precisa calcular efetivamente a saída em uma quantidade razoável de tempo, mas você deve poder provar que a saída será obtida corretamente em uma quantidade finita de tempo.

code-golf game grid board-game ghosts_in_the_code
fonte
Relacionado.
Martin Ender
@ MartinBüttner Isso significa que vou receber votos negativos ou está tudo bem deixar minha pergunta aqui?
ghosts_in_the_code
4
Significa apenas que as perguntas estão relacionadas, nada mais, nada menos. O objetivo de postar o link é que os desafios apareçam na barra lateral "Linked" um do outro, para que as pessoas possam encontrar desafios relacionados mais facilmente. Se eu considerasse sua pergunta uma duplicata, eu o teria dito (ou a encerrei), então não se preocupe. :)
Martin Ender
2
O "jogo ideal" está bem definido? Em caso afirmativo, você pode fornecer um link descrevendo o algoritmo para uma reprodução ideal?
Rainbolt
2
@Rainbolt Foi resolvido e também existem algoritmos perfeitos . Leia a Wikipedia para mais.
ghosts_in_the_code

Respostas:

16

Perl, 119 118 117 bytes

Inclui +4 para -0p

Dê placa giratória preenchida com espaços em STDIN (a gravidade puxa pedras para a direita)

connect4.pl
  OXXX
   XOO
    OX
  OOXX
  XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

#!/usr/bin/perl -p0
y/XO/OX/if$^S|y/X//>y/O//;$_=$$_||=/Z@{[map"|O".".{$_}O"x3,0,5..7]}/sx||s% (?! )%$_="$`X$'";do$0%eg?/1/?3:1+/2/:2

Imprime 3se o jogador se mover ganha, 1se o jogador se move perde e 2empata.

Em perls mais antigos, você pode usar um literal ^Spara obter um byte. Se você não se importa com extrema ineficiência, pode deixar de fora a $$_||=(tabela de transposição) e obter mais 6 bytes. Se você deixar de fora, $_=ele mostrará onde jogar, em vez do resultado (jogue 1e ganhe, se houver), jogue 2e empate, se houver, ou jogue em qualquer 3e perca.

Cria e avalia uma árvore minimax completa. Você ficará sem memória e tempo, a menos que o quadro já esteja razoavelmente bem preenchido.

Ton Hospel
fonte
2
Por que diabos alguém votou negativamente? O golfe é realmente incrível (eu jogo com perl e obter uma solução desse tipo é extremamente difícil - não tenho certeza de que outro jogador de perl que conheço possa ter inventado esse código). E o código tem o comportamento necessário.
Dada
Isso faz meu cérebro doer. +1!
levelonehuman
@ Dadá, como você sabe que esta resposta está com o voto negativo? Vejo 3 como voto ...
RosLuP
@RosLuP quando vi este post pela primeira vez, ele tinha 1 voto negativo. Além disso, quando você tem representante suficiente, pode ver quantos votos para cima e para baixo uma postagem tem: nesse caso, agora ela tem 4 para cima e 1 para baixo.
Dada