La mejor respuesta
La «estrategia» real es bastante compleja e implica una búsqueda exhaustiva en los puntos para tratar con tácticas, por lo que no es práctico usarlo a mano.
Por otro lado, los conocimientos estratégicos y algunas reglas de propósito general son fáciles de usar para un humano y probablemente lo convertirán en un buen jugador.
Antecedentes
Empecemos por revisar rápidamente connect-4. El juego se juega en un tablero de 6 × 7; podemos etiquetar cada fila con un número y cada columna con una letra:
Cada jugador se turna para elegir una columna; su piedra se coloca en la celda más abierta de la parte inferior de la columna. Podemos escribir un juego usando solo las columnas; por ejemplo, si ambos jugadores tocan la columna central, podemos escribir dd. Esto conduciría al siguiente tablero:
(Por convención, el jugador 1 será azul y el jugador 2 rojo).
Se puede ganar un juego conectando cuatro piezas de tu color horizontal, vertical o diagonalmente:
Una última noción útil es una amenaza , que son solo tres piezas seguidas con el cuarto cuadrado abierto (pero no necesariamente accesible). Aquí, el azul tiene una amenaza en diagonal:
Estrategia
El juego está resuelto: el primer jugador (azul) siempre puede forzar una victoria. Las ideas centrales detrás de la estrategia ganadora son bastante simples: controlar zugzwang y controlar impar / par filas.
Zugzwang
«Zugzwang» como término significa perder porque tiene para hacer un movimiento. Un ejemplo simple sería tener dos amenazas una encima de la otra. Aquí hay un ejemplo de azul forzando una victoria en la columna c con rojo para moverse:
Sin embargo, amenazas dobles como esta son razonablemente fáciles de reconocer con anticipación y contraataque. En la práctica, una forma mucho más útil de Zugzwang implica esperar hasta que se llene todo el tablero y solo quede un movimiento posible. Considere el ejemplo simple donde el rojo gana a la izquierda con la fuerza real solo sucediendo después de un montón de movimientos:
Amenazas pares / impares
Quien tenga una amenaza que se cumplirá inexorablemente ganará al final. Como vimos en el ejemplo anterior, el rojo puede ganar con una amenaza en un par fila. Por el contrario, el azul necesita una amenaza impar para ganar: aquí es donde la asimetría en el juego emerge.
Una amenaza extraña «tapa» una columna y, esencialmente, cambia quién puede obtener qué fila cuando se llena toda la boa rd. En particular, esto significa que una amenaza impar válida es «más fuerte» que una amenaza par válida: si el azul tiene una amenaza impar en una columna y el rojo una amenaza par en otra, el azul seguirá ganando. Aquí hay un ejemplo (azul para jugar):
Desde esta posición, podemos llenar repetidamente hasta llegar a un posición donde el rojo tiene que jugar c porque g (que tiene un número impar de piezas) daría como resultado una victoria azul. Esto permite la columna c se llena hasta que el rojo se ve obligado a perder:
El la amenaza impar «funciona» porque limita una sola columna para tener un número impar de posiciones, lo que hace que el tablero deje de tener un número par de cuadrados (42) a un número impar, lo que cambia la dinámica del juego. Esto también significa que si ambos rojo y azul tienen amenazas impares independientes, se cancelan: tener dos columnas impares devuelven el total a ser par.
De manera más general, la distinción impar / par nos da una noción de control : el rojo normalmente controla el juego, pero el azul puede ganar el control estableciendo una amenaza extraña. En la práctica, el control significa poder jugar cualquier casilla par o, como opción, jugar una casilla impar pero dejar que tu oponente juegue una casilla par a cambio.
Tácticas
La distinción impar / par nos permite jugar «estratégicamente», un montón de movimientos por delante, en todo caso. Para ganar de manera consistente, tenemos que combinar nuestro conocimiento sobre la estrategia a largo plazo con movimientos tácticos sólidos a corto plazo. Tenemos que tener en cuenta pequeñas trampas como esta:
Reglas
La estrategia ganadora real para el juego se reduce a un conjunto de nueve reglas basadas en los principios estratégicos cubiertos anteriormente y las tácticas.Las reglas fueron desarrolladas por Victor Allis en 1988; creo que fue la primera persona en resolver el juego.
Las reglas pueden «t siempre encontrar la solución óptima: a veces, tendría que hacer una búsqueda real a través de las posibilidades, en gran parte para lidiar con preocupaciones tácticas.
Aquí están las que creo que son las reglas más importantes, con los nombres que les dio Allis . Hay algunas reglas más, pero son para casos especiales o simplemente para combinaciones de reglas anteriores; puedes leer sobre todas las reglas en la tesis real: Un enfoque basado en el conocimiento de Connect Four .
- baseinverse : siempre puedes reclamar uno de los dos cuadrados accesibles cuando tu oponente reclame el otro, por lo que siempre puedes bloquear un cuatro en una fila que necesite dos cuadrados como ese. Por ejemplo, el rojo siempre puede jugar uno de los cuadrados verdes después de que el azul toque la o hay:
- vertical : siempre puedes bloquear un cuatro en fila vertical jugando uno de los dos cuadrados directamente uno encima del otro. El rojo siempre puede bloquear los cuatro verticales en fila en
djugando uno de los cuadrados resaltados:
- claimeven : quien tenga el control del juego (es decir, rojo a menos que el azul tenga una amenaza extraña ) puede jugar un cuadrado en una fila par (siempre que ese cuadrado no se pueda reproducir inmediatamente). Esta regla incorpora la estrategia básica impar / par.
- aftereven : si tienes el control y tienes una amenaza en una fila par, podrás jugar esa fila a través de claimeven. Esto significa que cualquier amenaza en la misma columna por encima de esa está bloqueada. Por ejemplo, aquí el azul no podrá reproducir
b3ya que el rojo tiene una amenaza enb2:
- lowinverse : si hay dos columnas con un número impar de cuadrados, el resultado es par. Si hay dos cuadrados impares es en esas columnas que no son directamente jugables, quien controle el juego podrá jugar al menos uno de ellos. Esto también se puede aplicar a los cuadrados que están lejos de ser jugables y no están uno al lado del otro. En estos dos ejemplos simples, el rojo puede obtener al menos uno de los dos cuadrados resaltados:
Ganar
El juego en realidad se resolvió mediante una combinación de estas reglas y una búsqueda exhaustiva; las reglas por sí mismas no son suficientes por desgracia.
Muchas de las reglas dependen de tener el control del juego. Dado que el rojo tiene el control inicialmente, el azul no puede usar muchas de las reglas hasta que logren establecer una amenaza extraña. El azul puede establecer una amenaza extraña usando algunas de las reglas que no dependen de tener el control o simplemente del pensamiento táctico, como combinar grupos de dos piezas para garantizar una amenaza extraña en el futuro.
Resulta la primera El jugador puede hacer esto contra un juego óptimo siempre que el primer movimiento sea d1. Esto significa que el primer jugador siempre puede ganar. La búsqueda que realmente estableció esto también se detalla en la tesis.
Para los jugadores humanos, es difícil trabajar con este tipo de lógica. Afortunadamente, alguien más encontró un conjunto de buenas oportunidades que generalmente puedes usar: Juego de expertos en Connect-Four .
Además, como acotación al margen, hice todas las ilustraciones usando el maravilloso paquete de diagramas de Haskell. De hecho, toda esta respuesta fue en realidad un ejercicio para aprender a usar la biblioteca, ¡lo que he querido hacer durante un tiempo! Puedes echar un vistazo al código en esta esencia. El código es complicado, pero es una gran demostración de que, contrariamente a la creencia popular, Haskell es realmente genial para crear prototipos de forma interactiva y escribir código desechable.
Además, creo que es genial ver cómo Emacs puede obtener una vista previa de SVG y PNG en un búfer, esencialmente dándome un entorno personalizado para desarrollar imágenes como esta: