Determinar ganador de Connect 4

19

Se le proporciona una red Connect 4 parcialmente llena (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

(La entrada se puede proporcionar como una matriz 1D o 2D y como letras o números, etc.)

Asumir que

  • X comenzó el juego.
  • Nadie ha ganado todavía.
  • Los jugadores pueden no haber jugado bien hasta ahora, pero ahora en adelante ambos emplearán estrategias óptimas.
  • La cuadrícula de entrada no es defectuosa.

Debe generar un único valor que indique qué jugador gana (o un empate)

Código de desafío de golf; entonces el código más corto gana. Su programa no tiene que calcular la salida real en un período de tiempo razonable, pero debe poder demostrar que la salida se obtendrá correctamente en un período de tiempo limitado.

fantasmas_en_el_código
fuente
Relacionado.
Martin Ender
@ MartinBüttner ¿Eso significa que recibiré un voto negativo, o está bien dejar mi pregunta aquí?
ghosts_in_the_code
44
Simplemente significa que las preguntas están relacionadas, nada más y nada menos. El propósito de publicar el enlace es que los desafíos aparezcan en la barra lateral "Vinculada" de cada uno, para que las personas puedan encontrar desafíos relacionados más fácilmente. Si considerara su pregunta como un duplicado, lo habría dicho (o simplemente lo habría cerrado), así que no se preocupe. :)
Martin Ender
2
¿Está bien definido el "juego óptimo"? Si es así, ¿puede proporcionar un enlace que describa el algoritmo para un juego óptimo?
Rainbolt
2
@Rainbolt Se ha resuelto y también existen algoritmos perfectos . Lea Wikipedia para más.
ghosts_in_the_code

Respuestas:

16

Perl, 119 118 117 bytes

Incluye +4 para -0p

Dé el tablero girado acolchado con espacios en STDIN (la gravedad tira piedras a la derecha)

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 3si el jugador que se mueve gana, 1si el jugador que se mueve pierde y 2para un empate.

En perls anteriores, puede usar un literal ^Spara obtener un byte. Si no le importa la ineficiencia extrema , puede omitir la $$_||=(tabla de transposición) y ganar 6 bytes más. Si deja de lado $_=, le mostrará dónde jugar en lugar del resultado (juegue 1y gane si hay uno, juegue 2y dibuje si hay uno o juegue en alguno 3y pierda)

Construye y evalúa un árbol minimax completo. Se le acabará la memoria y el tiempo a menos que el tablero ya esté razonablemente bien lleno.

Ton Hospel
fuente
2
¿Por qué demonios alguien votó en contra? El golf es realmente asombroso (yo juego golf con Perl y obtener esa solución es extremadamente difícil; no estoy seguro de que ningún otro golfista de Perl que conozca pueda haber ideado ese código). Y el código tiene el comportamiento requerido.
Dada
Esto hace que me duela el cerebro. +1!
levelonehuman
@Dada, ¿cómo sabes que esta respuesta ha sido rechazada? Veo 3 como voto ...
RosLuP
@RosLuP cuando vi por primera vez esta publicación, tenía 1 voto negativo. Además, cuando tiene suficiente representante, puede ver cuántos votos hacia arriba y hacia abajo tiene una publicación: en ese caso, ahora tiene 4 arriba y 1 abajo.
Dada