Estrategia de emparejamiento

En un juego de posición , una estrategia de emparejamiento es aquella que un jugador puede usar para garantizar la victoria o, al menos, forzar un empate. Se basa en dividir las posiciones del tablero en pares disjuntos. Cuando el oponente elige una posición de un par, el jugador elige la otra posición del mismo par.

Consideremos la variante de 5x5 del Tres en Raya . Podemos crear 12 pares de posiciones del tablero disjuntas, denotadas por 1,...,12 a continuación: ^{[ 1 ] : 3}

Tenga en cuenta que el elemento central (indicado con *) no pertenece a ningún par; no es necesario en esta estrategia.

Cada línea horizontal, vertical o diagonal contiene al menos un par. Por lo tanto, se puede usar la siguiente estrategia de emparejamiento para forzar un empate: "siempre que tu oponente elija un elemento del par i , elige el otro elemento del par i ". Al final de la partida, tendrás un elemento de cada línea ganadora. Por lo tanto, garantizas que el otro jugador no pueda ganar.

Dado que ambos jugadores pueden utilizar esta estrategia, el juego termina en empate.

Este ejemplo se generaliza a continuación para un juego arbitrario de Creador-Destructor . En dicho juego, el objetivo del Creador es ocupar un conjunto ganador completo, mientras que el objetivo del Destructor es impedirlo poseyendo un elemento en cada conjunto ganador.

Una estrategia de emparejamiento para Maker requiere un conjunto de pares de elementos tal que: ^{[ 1 ] : 119}

• Todos los pares son disjuntos por pares;
• Todo conjunto que contenga al menos un elemento de cada par, contiene algún conjunto ganador.

Siempre que Breaker elige un elemento de un par, Maker elige el otro elemento del mismo par. Al final, el conjunto de Maker contiene al menos un elemento de cada par; según la condición 2, ocupa un conjunto ganador completo (esto se cumple incluso cuando Maker juega en segundo lugar).

Por ejemplo, consideremos un tablero de juego con todos los vértices de un árbol binario perfecto, excepto la raíz. Los conjuntos ganadores son todos los caminos desde la hoja hasta uno de los dos hijos de la raíz. Podemos particionar los elementos en pares emparejando cada elemento con su hermano. Esta estrategia de emparejamiento garantiza que el jugador gane incluso jugando en segundo lugar. Si el jugador juega primero, puede ganar incluso si el tablero también contiene la raíz: en el primer paso, simplemente elige la raíz y, a partir de ahí, aplica la estrategia de emparejamiento descrita anteriormente.

Una estrategia de emparejamiento para Breaker requiere un conjunto de pares de elementos tal que:

• Todos los pares son disjuntos por pares;
• Cada conjunto ganador contiene al menos un par.

Siempre que Maker elige un elemento de un par, Breaker elige el otro elemento del mismo par. Al final, Breaker tiene un elemento en cada par; por la condición 2, tiene un elemento en cada conjunto ganador.

Un ejemplo de dicha estrategia de emparejamiento para el tres en raya de 5x5 se muestra arriba. ^{[ 1 ] : 2–3} muestran otros ejemplos para el tres en raya de 4x4 y 6x6.

Otro caso sencillo en el que Breaker tiene una estrategia de emparejamiento es cuando todos los conjuntos ganadores son disjuntos por pares y su tamaño es de al menos 2.