Reglas del Go para matemáticos

Mucha gente en Occidente tiene su primer contacto con el Go a través del reglamento japonés. Sin embargo, es un poco caótico, con varios parches, y peor aún, algunos libros parecen intentar ocultar la complejidad. El Go ya es un juego complejo de por sí, pero las reglas no necesitan serlo; la complejidad es una propiedad emergente, y por eso precisamente es un juego tan interesante. Si estás cómodo con las mates de primero de carrera y quieres conocer un conjunto de reglas bien definido, sigue leyendo. Vamos a hablar del reglamento Tromp-Taylor, que quizá sea el más elegante y breve de todos. Pero no te preocupes: Go con Tromp-Taylor es Go, y en la práctica casi cualquier reglamento da el mismo resultado en casi todos los casos. No es un reglamento exótico, es el simplemente el más sencillo y el que se presta a este tipo de análisis.

Aviso: estrictamente hablando, las reglas expuestas en este post son una generalización de las reglas Tromp-Taylor a $N$ jugadores y grafos finitos, arbitrarios y no dirigidos. Por lo demás, me estoy desviando de esas reglas lo mínimo posible. Creo que parte de lo bonito del juego solo se aprecia si lo ves generalizado.

Go en la vida real

Es un juego de tablero para dos jugadores que se juega por turnos con piedras negras y blancas. El tamaño de tablero más común e importante es 19x19. El objetivo es (aprox) rodear más territorio que el otro jugador, y en cada turno el jugador puede colocar una piedra en cualquier lugar del tablero, siempre y cuando el punto no esté ya ocupado por otra piedra (con algunas otras restricciones en las que ya entraremos luego). Las piedras se quedan donde están toda la partida (no se pueden mover) salvo que haya que retirarlas porque han muerto.

En este post voy a usar mucho un tablero de 9x9 para los ejemplos, pero al final veremos otros grafos más interesantes.

Definiciones matemáticas

Tablero, partida, puntos

El Go se juega sobre un grafo finito y no dirigido

$$G = (V, E)$$

donde $V$ es el conjunto de vértices/nodos y $E$ es el conjunto de aristas/conexiones entre ellos ($E$ de “Edges”, el post original lo escribí en inglés y quiero preservar la notación).

Los nodos del grafo pueden estar coloreados/etiquetados. Para $N$ jugadores, sea el conjunto de colores:

$$\mathcal C = \{\mathsf 0, c_1, \ldots, c_N\}$$

Para el caso especial de dos jugadores uso:

$$\mathcal C = \{\mathsf 0, \mathsf{B}, \mathsf{W}\}$$

$$(\text { Por "Black", "White", pero normalmente escribiré Negro, Blanco, Vacío. Uso } c \text{ minúscula para colores concretos).}$$

Una coloración del tablero es una función:¹

$$\lambda: V \to \mathcal C$$

Un punto es simplemente un vértice $v \in V$, y su color es $\lambda(v)$.

Una piedra es un punto no-vacío.

Como el grafo no cambia durante la partida, podemos decir que una partida jugada durante $n$ turnos es una sucesión de coloraciones:

$$(\lambda_i)=\lambda_0, ..., \lambda_n$$

(donde $\lambda_0$ es la coloración antes de que ningún jugador haya hecho nada)

Una consecuencia inmediata de lo anterior en los tableros típicos de Go es que las piedras colocadas diagonalmente entre sí no son adyacentes:

Ejemplo 1

Alcanzar

Se dice que un punto $P_0$ con color $c_0$ alcanza el color $c_1 \neq c_0$ si y solo si existe un camino de puntos de color $c_0$ que termina adyacente a un punto de color $c_1$. Es decir, $P_0$ alcanza $c_1$ si y solo si:

$$\exists \text{ un camino } (P_0, \ldots, P_m), \exists Q \in V$$

tal que:

$$\lambda(P_i)=c_0 : (i=0,\ldots,m),\quad \lambda(Q)= c_1, \quad \left\{P_m,Q\right\} \in E$$

(La última parte significa que $P_m$ y $Q$ son adyacentes porque existe una arista entre ellos. Fíjate también en que $m=0$ está permitido; simplemente significa que $P_0$ es directamente adyacente).

Cuando $Q$ es Vacío y $P_m$ no es vacío, $Q$ se llama una libertad de la componente conexa que contiene a $P_m$.

En el ejemplo de abajo consideramos varios casos a la vez.

Ejemplo 2

Limpieza

Ahora nos interesan las piedras/puntos que no alcanzan Vacío. Cuando describamos el bucle real de la partida veremos que esas piedras están muertas.²

Ejemplo 3

Ejemplo 4

Supongo que intuitivamente ves que los puntos blancos como los de arriba forman un grupo tal que, si uno de los puntos alcanza Vacío, todos lo hacen.

Proof

Sea $G_c \subseteq G$ el subgrafo de puntos coloreados $c$, y sea $S \subseteq G_c$ una componente conexa de $G_c$ (es decir, un subgrafo de $G_c$ donde para cada par de puntos existe un camino de uno al otro y el subgrafo no puede agrandarse sin romper la conexidad).

Proposición: Si $B \in S$ alcanza Vacío, $A$ alcanza Vacío $\forall A \in S$.

---

Demostración: Como $B$ alcanza Vacío, existe un camino $BC = (B, \ldots, C) \subseteq G_c$ desde $B$ hasta algún punto $C$ adyacente a un punto vacío $D$ del grafo completo $G$. Como $S$ es una componente conexa de $G_c$, también tenemos que $C \in S$. Eso significa que, para cada $A \in S$, existe un camino $AC \subseteq G_c$ que termina en $C$, que es adyacente a $D$. Por tanto, $A$ alcanza Vacío.$\square$

Ejemplo 5

Limpiar un color $c$ significa encontrar todos los puntos de ese color que no alcanzan Vacío y cambiar su color a Vacío. En el ejemplo 4, esto se correspondería con retirar las piedras blancas muertas.

Fíjate en que limpiar Vacío está permitido por esta definición, pero hacerlo no cambia nada.

Jugadas

Una jugada la realiza un jugador, y consta de 3 pasos:

1. Cambiar el color de un punto vacío al color de ese jugador. (En la vida real, esto corresponde a colocar una piedra del color de ese jugador).
2. Limpiar el color de cada rival (simultáneamente).
3. Limpiar el color propio.

Esto se ve mejor con un ejemplo.

Ejemplo 6

El ejemplo anterior muestra que el orden de limpieza es importante: puedes colocar la piedra negra en un punto donde no alcanzaría Vacío y aun así no muere, porque primero limpia las piedras blancas. Después de la limpieza, la piedra negra sí alcanza Vacío, así que no se limpia en el paso 3.

En realidad, es imposible limpiar a la vez algunas piedras enemigas y piedras propias en la misma jugada. Lo de abajo es más bien una pseudo-demostración de palabra.

Proof

Suponemos sin pérdida de generalidad que es el turno de Negro.

Notación. Sea:

• $\lambda$ la coloración al comienzo de un turno de Negro.
• $\mu$ la coloración después de colocar la piedra negra en $P$.
• $\nu$ la coloración después de limpiar todos los colores rivales, pero antes de limpiar Negro.
• $\lambda_{\mathrm{final}}$ la coloración al final del turno.
• Por “cluster” entenderemos una componente conexa $A$ donde todos los puntos son del mismo color no vacío.
• El conjunto de libertades de un cluster $A$ bajo la coloración $\varphi$ es $L_{\varphi}(A)$. Como todo punto no vacío $X$ pertenece a un único cluster bajo una coloración $\varphi$, y las libertades se definen solo para clusters, también podemos escribir $L_{\varphi}(X)$ como abreviatura de $L_{\varphi}(A)$.
• Interpretamos $\lambda(A)$ como $\lambda(X)$ para algún $X \in A$. Como $A$ es un cluster, todos sus puntos tienen el mismo color.

Proposición:

Supongamos que todo cluster alcanza Vacío antes de que Negro juegue.

Sea $P\in V$ el punto vacío donde Negro juega, es decir:

$$\lambda(P)=\mathsf 0, \quad \mu(P) = \mathsf B, \quad \mu(X)=\lambda(X)\quad \forall X\neq P$$

(es decir, $P$ empieza vacío, se vuelve negro, y ningún otro punto se vuelve negro).

Vamos a probar que, si existe algún conjunto de puntos $S \subset V$ que forma un cluster rival bajo $\lambda$ y que se limpia después de la jugada, es decir:

$$\exists S \mid \lambda(S) = c : \text{ and } : \lambda_{\mathrm{final}}(Y) = \mathsf 0 \quad \forall Y \in S$$

entonces la piedra recién colocada no se limpia:

$$\lambda_{\mathrm{final}}(P)=\mathsf B \tag {1}$$

y tampoco se limpia ningún cluster negro preexistente, es decir:

$$\lambda(X)=\mathsf B \implies \lambda_{\mathrm{final}}(X)=\mathsf B \tag {2}$$

---

Demostración:

Paso 1 ($\lambda \to \mu$): Colocar una piedra en $P$.

Como ya se ha dicho, $\mu(P)=\mathsf B$ y ningún otro punto cambia de color.

Paso 2 ($\mu \to \nu$): Limpiar rivales.

Los puntos negros no cambian, así que en particular $\nu(P)=\mathsf B$.

Sea $S$ un cluster rival limpiado después de que Negro juegue en $P$. Entonces

$$L_\lambda(S)\neq\varnothing, \quad L_\mu(S)=\varnothing$$

y el único punto que cambió de color entre $\lambda$ y $\mu$ fue $P$; por tanto, $P$ era la única libertad restante, es decir:

$$L_\lambda(S)={P}$$

Así que existe algún $Q\in S$ adyacente a $P$, es decir, ${Q,P}\in E$.

Como $S$ se limpia al pasar de $\mu$ a $\nu$, en particular, $Q$ se limpia: $\nu(Q)=\mathsf 0$.

Paso 3 ($\nu \to \lambda_{\mathrm{final}}$): Limpiar Negro.

Como $\nu(Q)=\mathsf 0$ y $P$ y $Q$ son adyacentes, $P$ tiene una libertad bajo $\nu$, es decir, $Q \in L_\nu(P)$.

Por tanto, la componente negra que contiene a $P$ alcanza Vacío y no se limpia:

$$\lambda_{\mathrm{final}}(P)=\mathsf B$$

Esto prueba $(1)$.

Ahora sea $H$ cualquier componente conexa negra bajo $\nu$.

• Si $P\in H$, entonces $L_\nu(P)=L_\nu(H)\neq\varnothing$. Alcanza Vacío y por tanto no se limpia.
• Si $P\notin H$, entonces $H$ consiste solo en piedras negras que ya estaban presentes antes de la jugada. Eso significa que alcanzaba Vacío bajo $\lambda$ a través de un punto vacío $R$ distinto de $P$ (si $P$ fuera una libertad de $H$ bajo $\lambda$, $P$ estaría en $H$ después del Paso 1). Como $R \neq P$, $\lambda(R)=\mu(R)=\nu(R)=\mathsf 0$. $H$ alcanza Vacío bajo todas esas coloraciones y por tanto no se limpia.

Esto prueba (2).$\square$

Fíjate en que añadimos el tercer paso porque colocar una piedra donde moriría está permitido bajo las reglas Tromp-Taylor (no así en otros reglamentos, donde ese “suicidio” está prohibido).

Territorio y puntuación

El territorio del color $c \neq \mathsf 0$ es el conjunto de puntos vacíos que solo alcanzan $c$:

$$T_c(\lambda) = \left\{P \in V \mid \lambda(P)=\mathsf 0, : P \text{ reaches only } c \right\}$$

La puntuación de un color de jugador $c$ es el número de puntos de su color más el territorio de ese color. En mates:

$$V_c(\lambda) = \left\{P \in V \mid \lambda(P)=c \right\}$$

$$\operatorname{score}(\lambda; c) = |V_c(\lambda)| + |T_c(\lambda)| + K(c)$$

El término $K(c)$ es el komi, un ajuste por el hecho de que Negro juega primero y se espera que termine con una puntuación mayor. En general, para $N$ jugadores cada uno recibirá un $K(c)$ diferente.

Ejemplo 7: puntuación

Como puedes ver, la puntuación de un jugador depende únicamente de la coloración actual. Estos son algunos ejemplos de cosas que no importan de cara a la puntuación:

• De quién es el turno.
• Estados anteriores.
• Estados futuros, incluyendo, por ejemplo, qué puntos es probable que dejen de alcanzar Vacío.

Eso último necesita algún comentario adicional. Consideremos el tablero del ejemplo anterior. Las piedras negras de la esquina superior izquierda están a punto de morir; están a una jugada de no alcanzar vacío. Pero eso no importa para la puntuación tal como la hemos definido. Por supuesto, esto también sugiere que la puntuación actual puede ser engañosa en partidas sin terminar. Volveremos sobre este tema más adelante.

Reglas del juego

Voy a suponer que no hay hándicap por ahora.

Reglas:

1. Asigna jugadores a colores. Los colores tienen un orden de turno fijo $c_1,\ldots,c_N$. Para dos jugadores, primero va Negro y luego Blanco.
2. La partida empieza con todos los puntos vacíos.³
3. Durante su turno, el jugador puede jugar (colocar una piedra) o pasar.
4. Un jugador puede jugar en cualquier punto vacío, siempre que la coloración resultante después de la jugada no se haya visto ya en la partida (es decir, si un jugador jugó en el turno $i$, $\lambda_i = \lambda_j, : j < i$ es ilegal).
5. La partida termina después de $N$ pases consecutivos, donde $N$ es el número de jugadores.
6. El ganador de la partida es quien tenga la puntuación más alta (se permiten empates).

Como puedes ver, no podemos describir por completo el estado de la partida solo con la coloración actual y sabiendo de quién es el turno. También necesitamos conocer las coloraciones anteriores para comprobar la legalidad de las jugadas. Esa regla se llama Super-Ko Posicional (PSK, por siglas en inglés), y es necesaria para evitar bucles infinitos.⁴ Por supuesto, las coloraciones repetidas no dan problemas si vienen de que un jugador haya pasado.

Más sobre el komi

La cantidad concreta de komi siempre es objeto de debate. En principio, debería fijarse en la cantidad que haga que negro y blanco tengan la misma probabilidad de ganar cuando el color de cada jugador se decide al azar. Eso significa que el komi de 6.5 es contextual, y grafos distintos deberían tener komis distintos. Con 3+ jugadores, el komi $K(c)$ debería ser mayor cuanto más tarde empiece a jugar el color $c$, empezando en 0 para el primer jugador.

En un servidor que encontré que permite 3+ jugadores, parece que no hay komi (por el motivo que sea). De todos modos, estos servidores no parecen tener demasiados jugadores, así que las cosas podrían cambiar con más experiencia en este tipo de juegos.

Hándicap

El sistema tradicional japonés de hándicap deja que el jugador más débil juegue con negras y tenga algunas piedras precolocadas. Luego, blanco hace la primera jugada real. La idea detrás de esto parece ser enseñar Go al jugador más débil dándole una buena colocación inicial independientemente de lo que le apetezca hacer.

Ese sistema, bastante opinado, generaliza mal, y otros sistemas dan al jugador más débil colocación libre de las piedras, como en China. También es la propuesta de Tromp-Taylor, y me parece razonable. Aun así, habría que ajustarlo para que cada jugador tenga la misma probabilidad de ganar, aunque tengo la sensación de que, incluso si lo haces correctamente, este método va a tener más varianza que la versión japonesa. Lo cual quizá sea una virtud y no un defecto; no lo tengo claro.

Otra opción obvia es simplemente dar komi a los jugadores más débiles. Por qué tener dos sistemas de compensación (komi y hándicap) pudiendo usar solo uno? Es interesante que el enfoque Tromp-Taylor sea tan minimalista en general y, sin embargo, no reutilice el komi para esto.

¿Puede definirse un sistema de piedras precolocadas para grafos y jugadores arbitrarios? Lo dudo, pero sería interesante intentar definirlo, aunque acabe siendo razonable solo para algunas familias de grafos.

Comentarios y algunas preguntas posibles

Puedo rendirme?

En implementaciones prácticas, por supuesto que está permitido y es muy común. En teoría, sin embargo, bajo Tromp-Taylor solo puedes pasar, y estás obligado a ver la partida hasta el fin de los tiempos o hasta que decidas no pasar, por algún motivo.

Puede haber en el tablero grupos de piedras que no alcanzan Vacío, a pesar de estar muertas?

Antes de la primera jugada, no, porque todos los puntos están vacíos, así que no hay piedras.

Después de que una jugada termina, tampoco, por dos razones:

1. Una jugada acaba limpiando los colores de todos los jugadores.
2. Limpiar colores expande el número de puntos vacíos, así que el número de puntos que alcanzan Vacío solo puede aumentar o quedarse igual. No puede ocurrir que, después de limpiar, algunas piedras estén de pronto muertas cuando antes no lo estaban.

Quizá edite esto para añadir una demostración por inducción en algún momento.

Está garantizado que la partida termina?

Sí. Recuerda que exigimos grafos finitos. Un grafo con $|V|$ vértices y $|\mathcal C|$ colores tiene $|\mathcal C|^{|V|}$ coloraciones posibles. Ese número finito es en realidad muchísimo mayor que el número de configuraciones posibles en Go, ya que muchas de esas coloraciones son ilegales o imposibles de producir en una partida. Además, PSK hace que el conjunto de coloraciones no vistas se reduzca con cada jugada que no sea pasar. En algún momento no quedan más jugadas legales (en el peor caso, porque todas las coloraciones se han visto ya) y los jugadores están obligados a pasar. Cuando todos los jugadores pasan, la partida termina.

Por supuesto, todos los jugadores pasarán muchísimo antes de quedarse sin jugadas legales (recuerda que el suicidio es legal, así que, si tuvieran que jugar todas las jugadas legales posibles, tendrían que empezar a suicidarse en algún momento. Lo cual no suena muy sano, por cierto).

Eso nos lleva al punto importante de la parada anticipada de las partidas, pero primero tenemos que hablar de otro asunto de vida o muerte.

Vida y muerte

Una consecuencia de las reglas del Go que no es obvia para nadie en una primera lectura de las reglas es que algunos grupos de piedras son imposibles de capturar. A veces el “grupo” inmortal ni siquiera es un solo grupo, sino dos o más! Considera esta situación:

Ejemplo 8

Parada anticipada de partidas

Como hemos explicado, jugar las partidas hasta que no queden más jugadas posibles no solo es cansino e inútil, sino indeseable, porque obligaría a los jugadores a hacer jugadas suicidas. Igual que en el ajedrez, la gente suele rendirse antes. En Go, en realidad, muchísimo antes.

Esto significa que, para jugar en el mundo real y pasarlo bien, necesitamos alguna forma de parar pronto y ponernos de acuerdo en quién ha ganado. El problema es que es computacionalmente inviable buscar todas las posibles continuaciones.⁵ Peor aún: si paras pronto, bajo estas reglas la puntuación podría parecer casi cualquier cosa. Considera el siguiente ejemplo:

Ejemplo 9

Entonces, cómo podemos conseguir parar anticipadamente?

Tradicionalmente, cuando ambos jugadores pasan, la partida no termina realmente. Los jugadores tienen que ponerse de acuerdo sobre qué grupos de piedras son inmortales y cuáles están muertos a todos los efectos. La piedra blanca solitaria del ejemplo anterior sería considerada muerta con casi con total seguridad por cualquier jugador razonable. Creo que, de hecho, es imposible que blanco “haga vida” dentro de ese territorio si negro juega de forma siquiera medianamente competente (no digamos ya óptimamente). Pero ¿qué pasa si Blanco no está de acuerdo? Aquí la respuesta varía según el reglamento. Los más liosos, como los reglamentos japonés y coreano, necesitan una especie de sandbox durante la llamada “fase de confirmación”: los jugadores juegan la situación local sobre la que no están de acuerdo y, una vez ha quedado demostrada la vida o muerte, la partida se reinicia a la posición anterior a la subpartida “sandboxeada”. La necesidad de esta subpartida es una consecuencia de cómo definen la puntuación, cosa en la que no voy a entrar. Baste decir que los otros sistemas, los llamados reglamentos de “puntuación por área”, como el chino, el americano y otros, también hacen que los jugadores jueguen sus desacuerdos, pero no requieren una subpartida sandboxeada.⁶

Los sistemas automáticos usan heurísticas para determinar qué está vivo y qué no, y eligen pasar cuando no hay nada bueno que hacer. GNU Go, por ejemplo, hace esto.

Otra posibilidad sería usar programas de inteligencia artificial sobrehumanos como KataGo como árbitro/oráculo que te diga quién ganó. Sin embargo, en el momento de escribir esto, tiene algunos fallos sistemáticos que pueden explotarse, así que no puede funcionar como oráculo de la verdad en torneos (los profesionales optimizarían específicamente contra KataGo, en vez de intentar ganar según la opinión de otros humanos experimentados). Podrías pensar en usarlo de manera informal, entre jugadores débiles, y puede que funcione. El único problema es que a veces no se entiende por qué dice que un jugador ha perdido. Para el ojo inexperto, cosas que están muertas pueden parecer vivas y viceversa. E incluso si estás de acuerdo, un jugador débil metería la pata al jugar las situaciones de vida o muerte, así que KataGo no representa “lo que habría pasado si ambos hubiéramos jugado esto hasta el final”, que probablemente es lo que querías.

Para mí, todo esto significa que el mecanismo tradicional de acuerdo es práctico, y funciona. Pero idealmente, a los novatos les supervisaría el final de partida algún jugador fuerte para orientarles sobre qué grupos están vivos y muertos. Luego, después de decidir quién ganó de este modo, también pueden jugarlo hasta el final y verlo por sí mismos si quieren.

¿Dónde puedo jugar al Go?

Si vives en una ciudad grande, es probable que haya algún club de Go. Pero eso depende del contexto. Mi recomendación general es OGS, que es un servidor occidental y, por supuesto, gratuito. Empieza una partida personalizada con los siguientes ajustes (deberían guardarse automáticamente como tus ajustes por defecto para otras partidas después):

• Tamaño del tablero: 9x9
• Reglas: chinas
• Velocidad de partida: en vivo
• Control de tiempo: byo-yomi
• Tiempo principal: 5 minutos
• Tiempo por periodo: 15 segundos
• Periodos: 5

Puedes dejar el resto con los ajustes por defecto.

Necesito más ayuda para entender este juego

Salvo que seas un lector muy cuidadoso y reflexivo, probablemente necesitarás ver algunos tutoriales para principiantes completos para captar del todo las reglas y sus implicaciones inmediatas. Recomiendo los 5 primeros vídeos de esta playlist. Después, simplemente juega algunas partidas, intenta mejorar por tu cuenta y, si ves que te atascas, echas un vistazo a los vídeos del Clossi Approach. Son muy buenos. Mira solo el primero e intenta aplicar esas ideas en más partidas. Solo entonces mira el segundo.

También me vino bien leer Go For Beginners. El problema es que usa reglas japonesas sin explicar el mecanismo de sandbox, lo cual en mi opinión es una omisión importante y hace que algunos ejemplos resulten confusos.

Más allá de la cuadrícula estándar

Hay una web con variantes de Go. Algunas son simplemente Go sobre grafos poco habituales, como:

Sunflower

Incluso puedes jugarlo en un cubo:

Go en un cubo

Un servidor que permite 3+ jugadores es este. Sin embargo, solo admite cuadrículas cuadradas (ni siquiera rectangulares). Otro problema de este Go multijugador es que matar piedras es demasiado fácil:

Muerte fácil

Creo que una solución a eso último, al menos para partidas de 3 o 4 jugadores, es crear una cuadrícula distinta, una en la que cada vértice tenga más aristas:

Teselación triangular con forma hexagonal

Conclusión

El Go es uno de esos juegos en los que las reglas son sencillas (o pueden serlo), pero volverse bueno es muy difícil. El juego lleva milenios existiendo y se nota. También tiene jugadores muy dedicados, y profesionales. Creo que merece mucho la pena darle una oportunidad y, si no, espero que al menos este post te haya parecido interesante.

Evita los bucles infinitos.