Así que estaba leyendo "Los gráficos y sus usos" de Oystein Ore y me encontré con una sección sobre el juego llamada Nim. Ahora el autor da por hecho las sumas digitales binarias como forma de resolver el juego. El caso es que no soy capaz de entender su intuición al respecto.
Respuestas
¿Demasiados anuncios?
Joffan
Puntos
7855
La respuesta sencilla es "porque funciona".
Aunque la paridad de dígitos binarios es ahora un enfoque bien conocido para establecer la estrategia ganadora para Nim, el juego en sí es mucho más antiguo que el conocimiento de esa estrategia, por lo que el uso de este enfoque no es automáticamente intuitivo.
Es una extensión bastante natural de un enfoque de tipo paritario que funciona en algunos juegos y rompecabezas sencillos.
runeh
Puntos
1304
En parte es porque hay dos jugadores. Los juegos imparciales de dos jugadores con información perfecta siempre se relacionan con Nim, que tiene una aritmética especial relacionada con los campos de la característica 2.
Una entretenida exposición de la teoría más amplia puede ser explorada a través de la Números de Grundy y los trabajos de JH Conway y colaboradores.
Como comenta Ross Millikan, Winning Ways de Conway, Berlekamp y Guy es una gran fuente - el primer volumen de cualquier edición.
Los juegos imparciales entre dos jugadores son juegos como el Nim, en los que cada jugador realiza los mismos movimientos desde la misma posición (el ajedrez sería diferente, por ejemplo, porque los jugadores controlan diferentes conjuntos de piezas).
Cada posición del juego recibe un número que representa el valor de la posición. El número de una posición es, en cierto sentido, el valor más sencillo posible teniendo en cuenta las jugadas disponibles para cada jugador, cuyos valores ya se han calculado. En las partidas imparciales resulta ser el valor mínimo excluido, por ejemplo $m$ y la posición puede ser tratada como una pila de $m$ cerillas (u otros objetos) en el juego de Nim. Así que los valores se llaman "Nimbers".
El punto de paridad se produce porque hay dos jugadores. Si el jugador $1$ juega una jugada ganadora, entonces el jugador $2$ tiene que jugar una jugada perdedora, y el jugador $1$ estará en una posición equivalente más sencilla en la que es posible otra jugada ganadora. Una jugada ganadora en una partida de este tipo es siempre a una posición de valor $0$ de la que no hay una buena opción. Desde una posición con valor superior a $0$ siempre es posible pasar a una posición con valor $0$ debido a la regla del valor mínimo excluido ( $0$ se ha excluido, por lo que se pasa a una posición de valor $0$ ). Así que en un juego imparcial bien jugado cualquier otra posición tendrá valor $0$ .
Así que en un juego bien jugado, los pares de movimientos consecutivos se anulan de alguna manera.
