Domineering
Domineering (también llamado Stop-Gate o Crosscram) es un juego matemático que se puede jugar en cualquier colección de cuadrados en una hoja de papel cuadriculado. Por ejemplo, se puede jugar en un cuadrado de 6 × 6, un rectángulo, un polyomino completamente irregular o una combinación de cualquier número de tales componentes. Dos jugadores tienen una colección de fichas de dominó que colocan sucesivamente en la cuadrícula, cubriendo los cuadrados. Un jugador coloca las fichas verticalmente, mientras que el otro las coloca horizontalmente. (Tradicionalmente, estos jugadores se denominan "Izquierda" y "Derecha", respectivamente, o "V" y "H". En este artículo se utilizan ambas convenciones). Como en la mayoría de los juegos de teoría de juegos combinatorios, el primer jugador que no puede moverse pierde.
Domineering es un juego partisano, en el que los jugadores usan diferentes piezas: la versión imparcial del juego es Cram.
Aparte del juego vacío, donde no hay cuadrícula, el juego más simple es una sola caja.
En este juego, claramente, ningún jugador puede moverse. Dado que es una victoria del segundo jugador, es un juego cero.
Este juego es una cuadrícula de 2 por 1. Existe una convención de asignar al juego un número positivo cuando la Izquierda está ganando y uno negativo cuando la Derecha está ganando. En este caso, Izquierda no tiene movimientos, mientras que Derecha puede jugar un dominó para cubrir todo el tablero, sin dejar nada, lo que claramente es un juego de cero. Por tanto, en notación numérica surreal, este juego es {| 0} = −1. Esto tiene sentido, ya que esta cuadrícula es una ventaja de 1 movimiento para Derecha.
Este juego también es {| 0} = −1, porque una sola casilla no se puede jugar.
Esta cuadrícula es el primer caso de elección. La derecha podría jugar las dos casillas de la izquierda, dejando -1. Las casillas de la derecha también dejan -1. También podría jugar las dos casillas del medio, dejando dos casillas individuales. Esta opción deja 0 + 0 = 0. Por lo tanto, este juego se puede expresar como {| 0, −1}. Este es -2. Si este juego se juega junto con otros juegos, estos son dos movimientos libres para Derecha.
Las columnas verticales se evalúan de la misma manera. Si hay una fila de 2 n o 2 n +1 casillas, cuenta como - n . Una columna de tal tamaño cuenta como + n .
Este es un juego más complejo. Si la izquierda va primero, cualquier movimiento deja una cuadrícula de 1 × 2, que es +1. La derecha, por otro lado, puede moverse a -1. Por tanto, la notación numérica surreal es {1 | −1}. Sin embargo, este no es un número surrealista porque 1> −1. Este es un juego pero no un número. La notación para esto es ± 1, y es un juego caliente, porque cada jugador quiere moverse aquí.
Esta es una cuadrícula de 2 × 3, que es aún más compleja, pero, al igual que cualquier juego de Domineering, se puede desglosar observando cuáles son los distintos movimientos para Izquierda y Derecha. La izquierda puede tomar la columna de la izquierda (o, de manera equivalente, la columna de la derecha) y moverse a ± 1, pero es claramente una mejor idea dividir el medio, dejando dos juegos separados, cada uno con un valor de +1. Por tanto, el mejor movimiento de Left es +2. La derecha tiene cuatro movimientos "diferentes", pero todos dejan la siguiente forma en alguna rotación:
Este juego no es un juego caliente (también llamado juego frío), porque cada movimiento lastima al jugador que lo hace, como podemos ver al examinar los movimientos. La izquierda puede moverse a -1, la derecha puede moverse a 0 o +1. Por lo tanto, este juego es {−1 | 0,1} = {−1 | 0} = −½.
Nuestra cuadrícula de 2 × 3, entonces, es {2 | −½}, que también se puede representar por el valor medio, ¾, junto con la bonificación por moverse (la "temperatura"), 1¼, así:
El Mathematical Sciences Research Institute celebró un torneo de Domineering, con un premio de $ 500 para el ganador. Este juego se jugó en un tablero de 8 × 8. El ganador fue el matemático Dan Calistrate, que derrotó a David Wolfe en la final. El torneo se detalla en Games of No Chance de Richard J. Nowakowski (p. 85).
Un problema de Domineering es calcular la estrategia ganadora para tableros grandes, y particularmente tableros cuadrados. En 2000, Dennis Breuker, Jos Uiterwijk y Jaap van den Herik calcularon y publicaron la solución para el tablero de 8x8. El tablero 9x9 siguió poco después de algunas mejoras de su programa. Luego, en 2002, Nathan Bullock resolvió el tablero 10x10, como parte de su tesis sobre Domineering. TEl tablero 11x11 fue resuelto por Jos Uiterwijk en 2016.
Domineering es una victoria del primer jugador para los tableros cuadrados 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 y 11x11, y una victoria del segundo jugador para los tableros 1x1 y 5x5. Los otros valores conocidos para tablas rectangulares se pueden encontrar en el sitio de Nathan Bullock.
Cram es la versión imparcial de Domineering. La única diferencia en las reglas es que cada jugador puede colocar sus fichas de dominó en cualquier orientación. Parece solo una pequeña variación en las reglas, pero da como resultado un juego completamente diferente, que se puede analizar con el teorema de Sprague-Grundy.
En inglés: