De Tic-Tac-Toe a Minimax: construyendo y midiendo un motor en Go

Nota editorial (2026): Este artículo fue publicado originalmente en Medium en 2023. Lo he revisado corrigiendo errores técnicos, mejorando la coherencia entre narrativa y código, y añadiendo contexto sobre las limitaciones del diseño. El código del repositorio también fue actualizado.

---

Go es un lenguaje excelente para introducirse en ciencias de la computación. Su pequeño número de palabras reservadas, la velocidad de compilación y la claridad del sistema de tipos lo convierten en una herramienta didáctica muy efectiva. Y si además buscamos un problema entretenido para practicar, los juegos clásicos son una opción difícil de superar.

En este artículo construiremos un motor para Tic-Tac-Toe (el gato, tres en raya) aplicando el algoritmo Minimax. El objetivo no es solo hacerlo funcionar, sino también entender por qué una implementación ingenua de Minimax escala peor que el resto del motor. Ahí está la parte más interesante del ejercicio.

Puede encontrar el código completo en el repositorio de GitHub.

---

Qué vamos a construir

1. Un módulo Go con un paquete que expone una struct para almacenar el estado del juego.
2. Métodos para registrar jugadas y consultar el estado.
3. El algoritmo Minimax para calcular la mejor jugada posible.
4. Tests unitarios y benchmarks para cada método.

Nos centraremos en el motor, no en la interfaz. Sin ventanas, sin gráficos: solo lógica y medición.

El repositorio incluye un ejemplo ejecutable en examples/human_vs_machine/main.go que permite jugar una partida completa contra el motor por consola.
Para correrlo:

$ go run examples/human_vs_machine/main.go

Las coordenadas se ingresan como x y (columna y fila, valores 0–2).

---

El algoritmo Minimax

Minimax es un método de decisión para juegos de dos jugadores de suma cero. La idea central es:

Elige el mejor movimiento para ti, sabiendo que tu adversario elegirá el movimiento que sea peor para ti.

Partiendo del estado actual, el algoritmo genera recursivamente todos los estados posibles del juego y les asigna una puntuación. Los nodos donde gana el jugador reciben puntuación positiva; los nodos donde gana la máquina, negativa. Los estados intermedios se evalúan propagando hacia arriba el valor del nodo hoja más favorable.

Para una introducción conceptual más detallada, recomiendo el artículo de Dorian Lazar sobre el tema.

---

El proyecto

$ mkdir catngine
$ cd catngine
$ go mod init github.com/profe-ajedrez/catngine

---

Constantes y errores

package catngine

import (
    "errors"
    "fmt"
)

const (
    // E representa una casilla vacía
    E = int8(0)

    // P representa una casilla ocupada por el jugador humano
    P = int8(1)

    // F representa una casilla ocupada por la máquina
    F = int8(2)
)

var (
    // ErrOutOfBoardBounds se devuelve al intentar acceder a una casilla fuera del tablero
    ErrOutOfBoardBounds = errors.New("out of board bounds")

    // ErrNoEmptyCell se devuelve al intentar ocupar una casilla ya tomada
    ErrNoEmptyCell = errors.New("that cell is not empty")
)

Definir errores con nombre propio es una forma de documentar el comportamiento esperado sin escribir un comentario adicional.

---

La estructura

// Minimax es una implementación usando el algoritmo homónimo
type Minimax struct {
    g    []int8
}

// NewMinimax inicializa y devuelve un motor listo para usar
func NewMinimax() *Minimax {
    return &Minimax{
        g:    make([]int8, 9),
    }
}

El tablero se representa con un slice unidimensional de 9 posiciones. Esto es más eficiente de recorrer que una matriz 3×3, pero requiere un paso de mapeo.

---

Mapeo de coordenadas 2D a índice 1D

El tablero es conceptualmente una grilla 3×3 donde x es la columna e y es la fila:

(x=0,y=0) | (x=1,y=0) | (x=2,y=0)   ← fila 0
----------+-----------+----------
(x=0,y=1) | (x=1,y=1) | (x=2,y=1)   ← fila 1
----------+-----------+----------
(x=0,y=2) | (x=1,y=2) | (x=2,y=2)   ← fila 2

La relación con el índice lineal es:

i = 3*y + x

La implementación valida las coordenadas antes de calcular el índice para evitar falsos positivos (por ejemplo, x=-1, y=1 daría i=2, que parece válido pero no lo es):

func (b *Minimax) m(x, y int8) (int8, error) {
    if x < 0 || x > 2 || y < 0 || y > 2 {
        return 0, ErrOutOfBoardBounds
    }
    i := 3*y + x
    return i, nil
}

Test

func TestMinimaxMap(t *testing.T) {
    testCases := []struct {
        x, y        int8
        expectedErr error
        expectedIdx int8
        msg         string
    }{
        {9, 9, ErrOutOfBoardBounds, 0, "esperaba ErrOutOfBoardBounds para (9,9)"},
        {-1, -2, ErrOutOfBoardBounds, 0, "esperaba ErrOutOfBoardBounds para (-1,-2)"},
        // Bug corregido: (-1,1) daba i=2 con la validación anterior
        {-1, 1, ErrOutOfBoardBounds, 0, "esperaba ErrOutOfBoardBounds para (-1,1)"},
        {1, 2, nil, 7, "esperaba índice 7 para (1,2)"},
    }

    b := NewMinimax()

    for _, cs := range testCases {
        got, err := b.m(cs.x, cs.y)
        if err != cs.expectedErr {
            t.Errorf("%s: error recibido: %v", cs.msg, err)
            t.FailNow()
        }
        if err == nil && got != cs.expectedIdx {
            t.Errorf("%s: índice recibido: %v", cs.msg, got)
            t.FailNow()
        }
    }
}

$ go test -timeout 30s -run ^TestMinimaxMap$

Benchmark

var mapResult int8

func BenchmarkMinimaxMap(b *testing.B) {
    bd := NewMinimax()
    for i := 0; i < b.N; i++ {
        mapResult, _ = bd.m(1, 2)
    }
}

La variable mapResult se declara fuera del loop para evitar que el compilador descarte la llamada como código muerto (dead-code elimination), lo que produciría tiempos artificialmente bajos.

$ go test -benchmem -count=4 -run=^$ -bench ^BenchmarkMinimaxMap$

Resultado orientativo en una máquina de escritorio (Intel i7):

BenchmarkMinimaxMap-16    1000000000    ~0.22 ns/op    0 B/op    0 allocs/op

Esta operación es barata y no realiza asignaciones en heap. Lo importante aquí no es el número exacto, sino que sirve como referencia para comparar con operaciones más costosas más adelante.

💡 Para los curiosos: lo que genera el compilador

¿Qué pasa si no se usa la variable de sink mapResult? El ensamblador
lo muestra.

En el repositorio provisto encontrará 2 benchmarks que miden lo
mismo; BenchmarkMinimaxMapNoSink y BenchmarkMinimaxMapSink, uno
usando la variable de sink y otro que no la usa.

Podemos saber como se comportan con la siguiente instrucción:

$ go test -gcflags="-S" -run=^$ -bench=^$ 2>&1 | grep -A 12 "BenchmarkMinimaxMapNoSink\|BenchmarkMinimaxMapSink"

El compilador aplicó dos optimizaciones en cadena. Primero evaluó
m(1, 2) en tiempo de compilación:
la función es pura, sus argumentos son constantes,
el resultado siempre es 7.
Luego, en la versión sin sink, descartó esa constante porque nadie la usa.

Sin sink — el loop no contiene ninguna llamada a m():

XORL  CX, CX
JMP   7
INCQ  CX
CMPQ  528(AX), CX
JGT   4
RET

Con sink — el compilador precalculó m(1,2) = 7 y solo emite
la escritura a memoria:

XORL  CX, CX
JMP   14
MOVB  $7, catngine.mapResult(SB)
INCQ  CX
CMPQ  528(AX), CX
JGT   4
RET

Sin mapResult, el benchmark mediría cuánto tarda un loop vacío.
Con ella, forzamos que el resultado se materialice en memoria en cada iteración.

---

Registrar una jugada

func (b *Minimax) Set(x, y int8, p int8) error {
    i, err := b.m(x, y)
    if err != nil {
        return err
    }
    if b.g[i] != E {
        return ErrNoEmptyCell
    }
    b.g[i] = p
    return nil
}

---

Mostrar el tablero

Para cerrar la brecha entre el estado interno (valores 0, 1, 2) y la representación visual del artículo (X, O), String() traduce con un array fijo de 3 símbolos:

func (b *Minimax) String() string {
    s := [3]string{" ", "X", "O"}
    return fmt.Sprintf(
        " %s | %s | %s \n---+---+---\n %s | %s | %s \n---+---+---\n %s | %s | %s \n",
        s[b.g[0]], s[b.g[1]], s[b.g[2]],
        s[b.g[3]], s[b.g[4]], s[b.g[5]],
        s[b.g[6]], s[b.g[7]], s[b.g[8]],
    )
}

Un array fijo [3]string es suficiente aquí: solo hay tres estados posibles y el índice coincide directamente con las constantes E, P, F.

---

Detectar al ganador

func (b *Minimax) Winner(p int8) bool {
    return checkWin(b, p)
}

func checkWin(b *Minimax, p int8) bool {
    return (b.g[0] == p && b.g[1] == p && b.g[2] == p) ||
        (b.g[3] == p && b.g[4] == p && b.g[5] == p) ||
        (b.g[6] == p && b.g[7] == p && b.g[8] == p) ||
        (b.g[0] == p && b.g[3] == p && b.g[6] == p) ||
        (b.g[1] == p && b.g[4] == p && b.g[7] == p) ||
        (b.g[2] == p && b.g[5] == p && b.g[8] == p) ||
        (b.g[0] == p && b.g[4] == p && b.g[8] == p) ||
        (b.g[2] == p && b.g[4] == p && b.g[6] == p)
}

Es fuerza bruta: enumera las 8 combinaciones ganadoras. Es deliberadamente simple para mantener el artículo enfocado en Minimax. Hay formas más elegantes —bitboards, por ejemplo— pero las dejamos para otro momento.

Test

func TestMinimaxWinner(t *testing.T) {
    b := NewMinimax()

    // Simulamos jugadas intercaladas
    _ = b.Set(0, 0, P) // P en columna 0, fila 0
    _ = b.Set(0, 1, F) // F en columna 0, fila 1
    _ = b.Set(1, 0, P) // P en columna 1, fila 0
    _ = b.Set(1, 1, F) // F en columna 1, fila 1
    _ = b.Set(2, 0, P) // P en columna 2, fila 0 -->  completa la primera fila

    if !b.Winner(P) {
        t.Errorf("Winner: esperaba true para P, recibió false")
    }
    if b.Winner(F) {
        t.Errorf("Winner: esperaba false para F, recibió true")
    }
}

Benchmark

var winnerResult bool

func BenchmarkMinimaxWinner(b *testing.B) {
    bd := NewMinimax()
    _ = bd.Set(0, 0, P)
    _ = bd.Set(0, 1, F)
    _ = bd.Set(1, 0, P)
    _ = bd.Set(1, 1, F)
    _ = bd.Set(2, 0, P)

    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        winnerResult = bd.Winner(P)
    }
}

Resultado orientativo:

BenchmarkMinimaxWinner-16    ~600M ops/s    ~1.9 ns/op    0 B/op    0 allocs/op

El costo es bajo y consistente. También realiza cero asignaciones.

---

El motor: Evaluate() y miniMax()

Evaluate() recorre las casillas vacías, simula cada jugada posible y llama a miniMax() para obtener su puntuación. Se queda con la jugada de mayor (o menor) puntuación según el jugador evaluado.

func (b *Minimax) Evaluate(p int8) int8 {
    j := int8(0)
    score := int8(20)
    if p == P {
        score = -20
    }

    for i := int8(0); i < 9; i++ {
        if b.g[i] == E {
            b.g[i] = p

            if p == P {
                s := miniMax(b, 0, F)
                b.g[i] = E
                if s > score {
                    score = s
                    j = i
                }
            }

            if p == F {
                s := miniMax(b, 0, P)
                b.g[i] = E
                if s < score {
                    score = s
                    j = i
                }
            }
        }
    }

    return j
}

miniMax() es la función recursiva que construye el árbol de juego. Contempla tres estados terminales: victoria del jugador, victoria de la máquina, y empate. Sin el caso de empate, el algoritmo devolvería un valor arbitrario al agotar las casillas, lo que introduciría un sesgo silencioso en la evaluación.

func isDraw(b *Minimax) bool {
    for i := 0; i < 9; i++ {
        if b.g[i] == E {
            return false
        }
    }
    return !checkWin(b, P) && !checkWin(b, F)
}

func miniMax(b *Minimax, depth int8, p int8) int8 {
    if checkWin(b, P) {
        return 11 - depth
    }
    if checkWin(b, F) {
        return depth - 11
    }
    if isDraw(b) {
        return 0
    }

    mark := int8(20)
    if p == P {
        mark = -20
    }

    for i := 0; i <= 8; i++ {
        if b.g[i] == E {
            if p == P {
                b.g[i] = P
                m2 := miniMax(b, depth+1, F)
                b.g[i] = E
                if m2 > mark {
                    mark = m2
                }
            }
            if p == F {
                b.g[i] = F
                m2 := miniMax(b, depth+1, P)
                b.g[i] = E
                if m2 < mark {
                    mark = m2
                }
            }
        }
    }

    return mark
}

Test

func TestMinimaxEvaluate(t *testing.T) {
    testCases := []struct {
        setup    func() *Minimax
        expected int8
        desc     string
    }{
        {
            desc: "F debe bloquear la columna 0 donde P tiene dos en raya",
            setup: func() *Minimax {
                b := NewMinimax()
                _ = b.Set(0, 0, P) // P en columna 0, fila 0  --> índice 0
                _ = b.Set(1, 0, F) // F en columna 1, fila 0  --> índice 1
                _ = b.Set(0, 1, P) // P en columna 0, fila 1  --> índice 3
                return b
            },
            // P ocupa (0,0) y (0,1): amenaza en columna 0.
            // El bloqueo es (0,2): i = 3*2 + 0 = 6
            expected: 6,
        },
    }

    for i, cs := range testCases {
        b := cs.setup()
        got := b.Evaluate(F)
        if got != cs.expected {
            t.Errorf("caso %d (%s): esperaba índice %d, recibió %d", i+1, cs.desc, cs.expected, got)
        }
    }
}

Benchmark — y la sorpresa

var evalResult int8

func BenchmarkMinimaxEvaluate(b *testing.B) {
    bd := NewMinimax()
    _ = bd.Set(0, 0, P) // columna 0, fila 0
    _ = bd.Set(1, 0, F) // columna 1, fila 0
    _ = bd.Set(0, 1, P) // columna 0, fila 1

    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        evalResult = bd.Evaluate(F)
    }
}

$ go test -benchmem -count=4 -run=^$ -bench ^BenchmarkMinimaxEvaluate$

Resultado orientativo:

BenchmarkMinimaxEvaluate-16    ~70K ops/s    ~16.5 µs/op    0 B/op    0 allocs/op

Comparemos con los benchmarks anteriores:

Operación	Costo aproximado
m()	~0.22 ns/op
Winner()	~1.9 ns/op
Evaluate()	~16,500 ns/op

La diferencia es de cuatro órdenes de magnitud. No es que Evaluate() sea lenta en términos absolutos, pero la escala de crecimiento sí es un problema: en cada llamada recursiva, miniMax() recorre el slice entero buscando casillas vacías. Para un tablero vacío de 9 casillas esto se traduce en miles de llamadas. A medida que el árbol crece, el costo también crece.
El motor funciona correctamente, pero su implementación ingenua tiene un techo claro.

En microbenchmarks tan pequeños, el compilador y el inlining pueden influir bastante en los resultados.
Aquí me interesan más las diferencias relativas que el valor absoluto.

---

Qué haría distinto hoy

Después de revisar este código tres años después, hay varias cosas que cambiaría:

Unificar Evaluate() y miniMax() en una sola función recursiva. La separación actual es un artefacto de cómo fui construyendo el código, no una decisión de diseño deliberada.

Añadir poda alfa-beta. Esta es la mejora natural más importante. La poda alfa-beta elimina ramas del árbol que no pueden afectar el resultado final, reduciendo la complejidad de O(b^d) a O(b^(d/2)) en el mejor caso. Para Tic-Tac-Toe el impacto es modesto, pero el principio escala a juegos más complejos.

Usar una tabla de transposición. Muchos estados del tablero son equivalentes por rotación o simetría. Almacenar resultados ya calculados (memoización) evitaría recalcularlos.

Explorar bitboards. Representar el estado del tablero con enteros y operaciones de bits haría tanto checkWin() como la búsqueda de casillas vacías considerablemente más rápidos.

Esas mejoras merecen su propio artículo. Por ahora, el objetivo era construir algo funcional, medirlo y entender por qué el diseño más simple tiene sus límites.

---

Bonus: cómo quedaría la recursión unificada

Como adelanto, unificaría Evaluate() y miniMax() haciendo que la función recursiva devuelva dos valores en lugar de uno: el índice de la mejor jugada y su puntuación.
Actualmente el diseño tiene esta separación de responsabilidades:

Evaluate() encuentra el índice de la mejor casilla (loop sobre casillas vacías, llama a miniMax por cada una)
miniMax() devuelve solo una puntuación (recursión pura, no le importa el índice)

El problema es que Evaluate() básicamente replica el loop de miniMax() en el primer nivel. Son la misma lógica duplicada para la raíz del árbol.
La unificación consiste en darle a la función recursiva la capacidad de rastrear también el índice cuando está en profundidad 0:

// minimax devuelve el índice de la mejor casilla y su puntuación para el jugador p.
// En llamadas recursivas (depth > 0), el índice devuelto es -1 y puede ignorarse.
func minimax(b *Minimax, depth int8, p int8) (int8, int8) {
    if checkWin(b, P) {
        return -1, 11 - depth
    }
    if checkWin(b, F) {
        return -1, depth - 11
    }
    if isDraw(b) {
        return -1, 0
    }

    bestIdx := int8(-1)
    var bestScore int8
    if p == P {
        bestScore = -127
    } else {
        bestScore = 127
    }

    var next int8
    if p == P {
        next = F
    } else {
        next = P
    }

    for i := int8(0); i < 9; i++ {
        if b.g[i] == E {
            b.g[i] = p
            _, score := minimax(b, depth+1, next)
            b.g[i] = E

            if p == P && score > bestScore {
                bestScore = score
                bestIdx = i
            }
            if p == F && score < bestScore {
                bestScore = score
                bestIdx = i
            }
        }
    }

    return bestIdx, bestScore
}

// Evaluate es ahora una envoltura delgada sobre minimax.
func (b *Minimax) Evaluate(p int8) int8 {
    idx, _ := minimax(b, 0, p)
    return idx
}

La diferencia clave es que ahora hay un solo loop, no dos. Evaluate() queda como una envoltura de una línea que descarta la puntuación y expone solo el índice.

---

Resumen

• Construimos un motor de Tic-Tac-Toe en Go en la implementación Minimax.
• Representamos el tablero como un slice unidimensional con mapeo explícito de coordenadas.
• Validamos con tests con tabla de casos para facilitar la extensión.
• Medimos con benchmarks corregidos (sin dead-code elimination, con b.ResetTimer()).
• Identificamos el cuello de botella principal: la exploración exhaustiva sin poda.

El código completo está en el repositorio de GitHub. Si encuentra algún error o tiene sugerencias, los comentarios están abiertos.

---

Escrito originalmente en 2023. Revisado en 2026.