Teoría de juegos combinatorios
El estudio se ha limitado en gran medida a los juegos de dos jugadores que tienen una posición en la que los jugadores se turnan para cambiar de formas o movimientos definidos para lograr una condición ganadora definida.
Los juegos combinatorios incluyen juegos bien conocidos como ajedrez, damas y go, que se consideran no triviales, y tic-tac-toe, que se considera trivial en el sentido de ser "fácil de resolver".
[4] Otros juegos del mundo real son en su mayoría demasiado complicados para permitir un análisis completo en la actualidad, aunque la teoría ha tenido algunos éxitos recientes en el análisis de finales de go.
Aplicar la CGT a una posición significa intentar determinar la secuencia óptima de movimientos para ambos jugadores hasta que finaliza el juego y, al hacerlo, descubre el movimiento óptimo en cualquier posición.
En la práctica, este proceso es tortuosamente difícil a menos que el juego sea muy simple.
On Numbers and Games también fue fruto de la colaboración entre Berlekamp, Conway y Guy.
Los juegos combinatorios generalmente, por convención, se ponen en una forma en la que un jugador gana cuando al otro no le quedan movimientos.
Es fácil convertir cualquier juego finito con solo dos resultados posibles en uno equivalente cuando se aplique esta convención.
Esta forma de combinar juegos conduce a una estructura matemática rica y poderosa.
En 1953, Alan Turing escribió sobre el juego: "Si uno puede explicar sin ambigüedades en inglés, con la ayuda de símbolos matemáticos si es necesario, cómo se debe hacer un cálculo, entonces siempre es posible programar cualquier computadora digital para hacer ese cálculo, siempre que la capacidad de almacenamiento sea adecuada".
El ajedrez infinito tiene una complejidad combinatoria aún mayor que el ajedrez (a menos que solo se estudien partidas finales limitadas o posiciones compuestas con una pequeña cantidad de piezas).
Un juego, en sus términos más simples, es una lista de posibles "movimientos" que pueden hacer dos jugadores, llamados izquierda y derecha.
Usando Dominante como ejemplo, etiquete cada una de las dieciséis casillas del tablero de cuatro por cuatro con A1 para el cuadrado superior izquierdo, C2 para el tercer casillero desde la izquierda en la segunda fila desde arriba, y así sucesivamente.
Usamos, por ejemplo, (D3, D4) para representar la posición del juego en la que se ha colocado un dominó vertical en la esquina inferior derecha.
El {|} en la lista de movimientos de cada jugador (correspondiente al único cuadrado sobrante después del movimiento) se llama juego cero, y en realidad se puede abreviar como 0.
Las damas, por ejemplo, se vuelven locas cuando una de las piezas es promocionada, ya que entonces puede alternar interminablemente entre dos o más casillas.
Estrella, escrita como ∗ o {0 | 0}, es una victoria para el primer jugador, ya que cualquiera de los jugadores debe (si es el primero en moverse en el juego) pasar a un juego cero y, por lo tanto, ganar.
Puede sumarse a números o multiplicarse por positivos, de la manera esperada; por ejemplo, 4 ± 1 = {5 | 3}.
Asimismo, las damas no es imparcial, ya que los jugadores poseen piezas de diferentes colores.
El teorema de Sprague-Grundy afirma que todo juego imparcial equivale a un nimber.
