¿El número de juegos de ajedrez posibles es infinito?

16

Esta pregunta está algo relacionada con ¿Se puede calcular el número total de posibles victorias / empates / pérdidas? , pero un poco diferente.

Hay un episodio reciente de un programa de televisión que afirma que hay "más juegos de ajedrez posibles que átomos en el universo". Continúan diciendo que "cada posible movimiento representa un juego diferente, un universo diferente [..]"; "por el segundo movimiento hay 72084 juegos posibles, por el tercero - 9 millones, por el cuarto --- 318 millones".

Entonces, ¿el número total de juegos de ajedrez es infinito, a todos los efectos prácticos, dadas las limitaciones humanas y tecnológicas? ¿Y los números anteriores realmente resisten el escrutinio? (es decir, ¿cuáles son los posibles juegos estimados por, digamos, el décimo movimiento?)

Curiosamente, Wikipedia parece estar implicando que se puede estimar la cantidad de juegos:

la cantidad de juegos posibles [en Go] es enorme (10 761 en comparación, por ejemplo, con los 10 120 posibles en ajedrez)

theory statistics game-complexity Landroni
fuente
3
Si define un "juego" como el historial de movimientos, cualquier juego que permita la repetición tiene infinitos juegos posibles. Snakes and Ladders tiene infinitos "juegos" posibles. Si está interesado en la complejidad de la solución de un juego, ignorar la historia de movimientos y mirar el número de estados posibles del tablero puede estar en.
Schwern
3
Nota: la gente de informática se opondría inmediatamente a "infinito, a todos los efectos prácticos". Es notablemente peligroso "redondear" hasta el infinito. En términos generales, cuando cometen el error de hacerlo, alguien rompe rápidamente su algoritmo al mostrar que en realidad no se trataba de un infinito. En el cifrado, no es insólito que tienen algoritmos que parecían "irrompible hasta la muerte térmica del universo", que se rompieron debido a un par de trucos que se redujo el tamaño del problema por 10 ^ 80 o más
Cort Amón - Restablecer Mónica
2
Si no me equivoco, te estás refiriendo al programa de televisión Persona de interés, ¿verdad? Lo que quieren decir es que al prever los próximos movimientos posibles, debe crear un árbol de decisión para calcular todas las posibilidades. Cuando Harold se refiere al 'segundo movimiento', quiere decir mirar dos movimientos hacia adelante (el tuyo y el del oponente; en ciencias de la computación este es el segundo nivel de profundidad del árbol). Entonces, sin hacer los cálculos, creo que podría ser correcto. Sin embargo, al menos debe ser un gran número.
CMPSoares
Puede encontrar este video interesante. youtu.be/Km024eldY1A
Jivan Scarano

Respuestas:

17

El número máximo de movimientos en un juego de ajedrez no es infinito, son 11797 capas = 5898 movimientos y medio. Esto se debe a la regla de los cincuenta movimientos.

Entonces no, el número de juegos de ajedrez posibles no es infinito.

El número máximo de movimientos legales en una posición es 218. Entonces, un límite superior bruto para el número de juegos de ajedrez posibles es 218 ^ 11797 = 10 ^ 27586

Espera, en realidad después de cincuenta movimientos sin captura ni movimiento de peón, los jugadores también pueden continuar jugando sin reclamar el empate ...

El Artículo 9.3 de las Leyes de Ajedrez de la FIDE establece que:

9.3

El juego se basa en un reclamo correcto de un jugador que tiene el movimiento, si:

  • escribe su movimiento, que no se puede cambiar, en su hoja de puntaje y declara al árbitro su intención de hacer este movimiento que dará como resultado que los últimos 50 movimientos de cada jugador se hayan realizado sin el movimiento de ningún peón y sin ninguna captura, o
  • Los últimos 50 movimientos de cada jugador se han completado sin el movimiento de ningún peón y sin ninguna captura.

Entonces supongo que el número de juegos de ajedrez posibles podría considerarse infinito entonces ...

Pero si no está interesado en los números teóricos anteriores:
el número promedio de movimientos legales en una posición es de alrededor de 35, y la duración promedio de un juego de ajedrez es de alrededor de 40 movimientos = 80 capas, por lo que una estimación del número de " "juegos de ajedrez racionales son 35 ^ 80 = 10 ^ 123
En cuanto al número total de posiciones legales, está en algún lugar entre 10 ^ 40 y 10 ^ 50.

Destino
fuente
El problema de la repetición puede resolverse ajustando la pregunta para que no se trate de movimientos sino de estados. ¿Cuántas configuraciones posibles diferentes de un tablero de ajedrez son posibles? Esa es la pregunta interesante desde el punto de vista de la complejidad. La repetición no importa, es repetir el mismo estado. No se puede llegar a muchos estados porque tomarían más de 50 movimientos, o son imposibles debido a restricciones en el movimiento de piezas (particularmente peones).
Schwern
3
@ Tony Ennis: edité. Pero en realidad no, la regla de 50 movimientos no garantiza que el juego termine, porque los jugadores también pueden elegir no reclamar el sorteo.
Fate
2
¿Podrías editar tu respuesta para que se lea como una respuesta, en lugar de una discusión contigo mismo? Comienza haciendo una afirmación incorrecta de que el número de juegos es finito, luego corrígete. Simplemente haga el reclamo correcto primero; si luego quieres decir "Pero si los jugadores siempre toman un empate tan pronto como tienen derecho a eso ..." está bien.
David Richerby
11
En realidad, a partir de julio del año pasado, hay una regla de 75 movimientos que es obligatoria. Por lo tanto, la regla de 50 movimientos no garantiza un final del juego, pero la regla de 75 movimientos sí, aunque el juego más largo aumenta a 17,697 capas. Dado un factor de ramificación promedio de 35, uno podría estimar el número posible de juegos en 35 ^ 17697, o alrededor de 10 ^ 27000.
Publicado el
1
Incluso si ignoramos las reglas de 50 y 75 movimientos, si los jugadores juegan sin reclamar un empate, en algún momento tiene que ocurrir una triple repetición. No sé si es necesario hacer un sorteo aquí, pero consideraría un número finito de juegos distintos con posibilidades infinitas de repetir un número finito de juegos posibles, a los efectos de esta pregunta.
11684
6

Q1: sí. El número total de juegos de ajedrez puede considerarse infinito para todos los fines prácticos. No tenemos la tecnología para la fuerza bruta durante los primeros 13 movimientos desde la posición inicial.

P2: Se conocen los números reales hasta la profundidad 13. El número exacto de posibles posiciones para los movimientos 10 es 69,352,859,712,417. Lea este artículo de Wikipedia para más detalles.

Hay un intento de profundidad 14 pero hasta ahora el cálculo después de meses y meses todavía se está ejecutando.

Hola Mundo
fuente
Sí, números impresionantes. Es curioso que no podamos calcular más de 14 movimientos ... Me pregunto cuántos movimientos se pueden calcular para Go ... Three? :)
landroni
No necesita ser "considerado infinito para todos los propósitos prácticos" ya que en realidad es infinito. Aunque las reglas de repetición triple y 50 movimientos permiten a cualquiera de los jugadores reclamar un empate, no terminan automáticamente el juego.
David Richerby
1
@landroni Go es probablemente más fácil de calcular que el ajedrez. Hay 361 juegos de un movimiento, 361 * 360 juegos de dos movimientos y 361 * 360 * 359 juegos de tres movimientos. El número de cuatro juegos de movimientos depende de si se permite el suicidio. Si es así, habrá 358 cuartos movimientos posibles, a menos que las primeras dos piedras negras tomen la primera piedra blanca en la esquina, en cuyo caso hay 359. Entonces 361 * 360 * 359 * 358 + 8 juegos de cuatro movimientos. Si el suicidio no está permitido, entonces hay 361 * 360 * 359 * 358 - 8 * 358 juegos de cuatro movimientos. Puede continuar de esta manera, separándose en casos: 14 movimientos probablemente se puedan hacer con el esfuerzo de la computadora.
Deedlit
44
Tenga en cuenta que esto es 13 medios movimientos, o siete capas : siete movimientos en blanco y seis en negro.
RemcoGerlich
2
@DavidRicherby: sin embargo, la regla de 75 movimientos (nueva desde julio de 2014) es obligatoria.
RemcoGerlich
2

En algún momento te quedarás sin combinaciones. Entonces la respuesta es básicamente no.

Nuach
fuente
1

Un argumento simple de que el número de juegos de ajedrez es finito podría ser el siguiente.

Debido a la regla de 50 movimientos, cualquier subsecuencia de 50 movimientos de un juego de ajedrez dado contendrá al menos una captura o un movimiento de peón. Como hay muchas piezas en el tablero, y dado que los peones pueden moverse solo muchas veces durante un juego, el número de movimientos en un juego de ajedrez tiene un límite finito. Dado que en cada movimiento, solo hay muchas posibilidades, los números de todos los juegos son finitos.

Tenga en cuenta que este argumento es casi inútil si se quiere obtener una estimación del número de juegos posibles. Si por nada más, lo único que uso arriba es la regla de 50 movimientos y cómo se mueven las piezas, por lo que las repeticiones están permitidas (máx. 50 repeticiones, por supuesto). Por lo tanto, el argumento es simplemente teórico, no práctico.

Zvonimir
fuente
0

La regla de 50 movimientos incluye 'sobre un reclamo correcto': sin reclamo, sin implementación de la regla. Lo mismo se aplica a la repetición. Ergo, infinito.

Sin un número máximo obligatorio de movimientos, por supuesto.

x1797n7917
fuente
44
Ya no. Las nuevas Leyes de Ajedrez de la FIDE tienen una regla de 75 movimientos con un sorteo automático. Consulte fide.com/fide/handbook.html?id=171&view=article $ 9.6.
Dag Oskar Madsen
0

Sobre la comprensión de las leyes de la FIDE: en primer lugar, se usan con torneos, así que, dada esa información, ¿comprende cómo las leyes de la FIDE no se relacionan con dos amigos que deciden jugar? Para dos amigos, que se reducen a solo dos reyes, pueden perseguirse alrededor del tablero una cantidad infinita si lo desean. (Plausible, no realmente, posible, sí)

De acuerdo con la ley 9.2 de la FIDE, se deben realizar 50 movimientos consecutivos donde no hay peones movidos y no se realiza ninguna captura. Obviamente, esto no sería un "juego de 50 movimientos" (por ejemplo, 1.e4 significaría otros 50 movimientos consecutivos sin un peón movido o captura realizada)

En la ley FIDE 9.6 - 75 movimientos consecutivos ... El mismo razonamiento de que este no es un juego de 75 movimientos.

Una de las primeras pruebas de un juego grabado fue 14 movimientos consecutivos (1. e4 b6 2. d4 Bb7 3. Ad3 f5 4. ef5 Ag2 5. Qh5 g6 6. fg6 Nf6 7. gh7 Nh5) Aunque el 15 fue jaque mate- si el ganador decidiera no hacer jaque mate, aún necesitaría 75 movimientos más para declarar el empate en la ley FIDE 9.6 (con 12 peones restantes en el tablero, dudo que hubiera sucedido en 75 movimientos)

Respetuosamente, CFC

Clayton Currier
fuente
2
Bueno, si dos amigos a quienes no les importan las reglas oficiales les gusta jugar un juego sin sentido y llamarlo ajedrez, ¡pueden hacerlo! ¿Pero deberíamos llamarlo ajedrez para los propósitos de este sitio? Una posición con solo dos reyes es un empate inmediato.
RemcoGerlich
0

Dado que otras respuestas aquí apuntan a la repetición o similar, deseo modificar su pregunta a "¿Son infinitas las POSICIONES posibles de ajedrez? La respuesta es" No ". Sin embargo, el total es muy grande y se estima que es de aproximadamente 10 a la potencia 120 Se cree que el número total de átomos en el universo es de solo 10 a la potencia 80. ¡Guau!

El número 10 a la potencia 134 dada por un respondedor anterior puede ser correcto.

El juego chino "Go" es aún más variado que el ajedrez (pero aburrido en comparación ya que el ajedrez tiene piezas con diferentes habilidades, mientras que en Go todas las piezas son iguales).

markbolles44
fuente
0

Puede que esté viendo esto de manera demasiado simplista, pero me parece que el número tiene que ser finito. Si miramos el tablero y las piezas en lugar del juego de ajedrez y calculamos el número de variaciones posibles, podemos obtener una respuesta que es finita. Mente alucinantemente enorme pero finita. Dado que no todas las combinaciones son posibles en un juego de ajedrez, el número de combinaciones en un juego de ajedrez debe ser menor que este número finito y, por lo tanto, un número finito en sí mismo.

Justin
fuente