¿Cuál es el límite inferior más alto conocido para el mate en N desde la posición inicial?

14

Editar : Parece que mi pregunta no fue lo suficientemente clara. Permítanme reformular: ¿Cuál es la N más grande para la cual podemos decir a sabiendas "el ajedrez, desde la posición inicial, no es un compañero forzado en N movimientos"?

El ajedrez no está resuelto, es decir, no se sabe cuál es el resultado perfecto de la posición inicial.

Sin embargo, si la posición inicial es ganar para cualquiera de los jugadores, es un compañero en N para algunos N. Además, por ejemplo, si sabemos con certeza que la posición inicial no se puede ganar en 5 movimientos (para cualquier jugador), 5 es un límite inferior para N.

¿Aproximadamente qué tan profundo es factible buscar exhaustivamente desde la posición inicial en la práctica? ¿Qué tan alto se conoce un límite inferior para N?

Sami Liedes
fuente
1
Por curiosidad: el compañero forzado más largo conocido (suponiendo un juego perfecto) fue descubierto durante un esfuerzo en la mesa final de 7 hombres, y es el artículo 316 en el Open Chess Diary de Tim Krabbé . Son 517 movimientos largos. Ahora, esta posición no necesariamente se puede alcanzar usando el juego perfecto, pero muestra la escala del problema en general. Con una fuerza bruta desde una posición inicial, probablemente podríamos llegar a una docena de movimientos de profundidad como máximo, con el hardware actual.
Daniel B
@DanielB No, 549 es el más largo conocido, encontrado en 7man tablebases.
Santropedro

Respuestas:

6

Esta es esencialmente la cuestión de cuál es la complejidad del juego del ajedrez. Tenga en cuenta que, por finitud, sabemos que el ajedrez está determinado, pero no sabemos si la posición inicial es una victoria para las blancas, una victoria para las negras o un empate. La complejidad del juego del ajedrez es aproximadamente el número mínimo de posiciones que necesitamos verificar en el árbol del juego para determinar el estado de la posición inicial. Esto se conoce como el número de Shannon . En el influyente artículo Programming a Computer for Playing Chess , Shannon estimó que el número de Shannon es al menos 10 ^ {120). Tenga en cuenta que el número de partículas en el universo se estima en 10 ^ (80). Para responder la pregunta, en realidad queremos saber la alturadel árbol del juego cuando se determina la posición inicial. También deberíamos dividir esta altura entre 2, ya que un movimiento en el ajedrez generalmente se considera un movimiento blanco y negro. Se estima que el factor de ramificación del árbol es de aproximadamente 30. Por lo tanto, podemos tomar el N más grande de modo que 30 ^ (2N) <10 ^ (120).

Responder. Al dorso del sobre, N = 40 funciona. Casualmente, esta es la duración de un juego promedio entre grandes maestros (aunque a menudo renuncian y en realidad no juegan el juego hasta la conclusión).

Editar. La moraleja de la historia es que estaba tratando de estimar un límite superior para su límite inferior. La primera parte del razonamiento de Shannon no es circular; Él dice que hay alrededor de 30 movimientos legales de cada posición, y este número es razonablemente constante para la primera parte de un juego.

Por lo tanto, podemos estimar el valor actual conocido de N (que es realmente lo que está preguntando, llamemos a esto N ') como máximo log_30 (C) donde C es igual a la cantidad de potencia informática que ha existido en la historia de la humanidad. Incluso con estimaciones conservadoras para C, obtenemos algo así como N 'como máximo 20. En la práctica, no creo que nadie haya llevado a cabo este cálculo muy lejos en el árbol, ya que a priori sabemos que el cálculo se vuelve inviable después de un período muy prolongado. altura corta y no es necesario buscar exhaustivamente en el árbol para escribir buenos programas de ajedrez.

Sin embargo, tenga en cuenta que está haciendo una pregunta un poco más débil, ya que es posible que el estado inicial del juego sea un empate con un juego óptimo. Entonces, uno podría obtener límites para N escribiendo un programa cuyo objetivo era no perder el mayor tiempo posible. Entonces podríamos jugar este programa contra los mejores programas o jugadores humanos del mundo y ver cuál es la duración de un juego más corto. Nuevamente, esto no responde adecuadamente la pregunta, ya que no podemos suponer que nuestros oponentes están jugando de manera óptima . El verdadero juego óptimo requiere un conocimiento completo del árbol del juego, pero hemos visto que esto es computacionalmente inviable. Por lo tanto, lo mejor que podemos hacer actualmente es aproximarnos a un oponente que juega de manera óptima con un Kasparov o un muy buen programa de ajedrez.

Tony Huynh
fuente
1
No creo que esto responda exactamente la pregunta (da una estimación de N en lugar del límite inferior más conocido), pero, sin embargo, ¡buena respuesta!
Sami Liedes
3
En realidad, de acuerdo con el artículo numérico de Shannon de Wikipedia, Shannon estimó el número por el hecho de que un juego típico dura unos 40 movimientos, por lo que este es un razonamiento circular.
Sami Liedes
3

No es cierto que la posición inicial no se pueda ganar en 5 movimientos o menos utilizando la definición canónica de un movimiento completo en el ajedrez. Se puede hacer en 2 movimientos a través de Fool's Mate .

Para responder a su pregunta, la fuerza de un motor de ajedrez depende del software y el hardware. En 1997, Deep Blue fue una prueba del concepto de hardware, una supercomputadora masivamente paralela capaz de evaluar 200 millones de movimientos por segundo con una profundidad promedio de 7-8 movimientos. Sin embargo, en 2006, Deep Fritz ejecutándose en una computadora personal de doble núcleo tuvo resultados equivalentes mientras solo evaluaba 8 millones de movimientos por segundo.

Hoy, la supercomputadora más fuerte que se ha aplicado al ajedrez es Blue Gene . Usando 131,000 procesadores, Blue Gene puede calcular 280 trillones de operaciones por segundo . Aunque no hay datos para confirmar la profundidad a la que Blue Gene puede calcular, supongo que sería bastante profundo. Por supuesto, esto depende de cuánto tiempo funcione la computadora.

Sin embargo, en este caso no podemos usar el término 'exhaustivo' al 'resolver' y abrir. Un motor de ajedrez no tiene necesidad de ir al final de la línea cuando es seguro que el resultado final es decisivo. En tal caso, el programa se cerraría cuando quedara claro que la evaluación estaba claramente a favor de un lado. Esto se conoce en informática teórica como poda alfa-beta .

Si tuviera que hacer una estimación aproximada, diría que Blue Gene podría calcular entre 15 y 20 movimientos por segundo. Aunque su hardware y software es extremadamente impresionante, tenemos que recordar que la complejidad del ajedrez escala exponencialmente. Según estimaciones recientes , la complejidad del ajedrez en el árbol de juego es de al menos 10 ^ 123 y el número de posiciones potenciales en 10 ^ 46.7.

Andrew Ng
fuente
Ese busto de Kings Gambit fue la broma de los inocentes de
Bort
Guau. Estoy seguro de que me engañaron. Gracias por la info.
Andrew Ng
1
Por "ganable", me refería a compañero forzado, es decir, ganable dado el juego óptimo del oponente. Parece que necesito editar mi pregunta para aclarar :)
Sami Liedes
1

Suponiendo que hay una continuación ganadora desde una posición determinada y suponiendo que el juego sea perfecto, implica que Nes fijo y no limitado (de lo contrario, ¡no es un juego perfecto!).

En este caso, uno tiene que trabajar realmente hacia atrás, lo que se logra mediante Endgame Tablebase

Las bases de tablas de todos los finales con hasta seis piezas están disponibles para descarga gratuita, y también se pueden consultar mediante interfaces web (ver los enlaces externos a continuación). La base de tabla de Nalimov requiere más de un terabyte de espacio de almacenamiento

Nishanth
fuente
Eso es cierto, pero aún es posible conocer un límite inferior para N sin conocer N (por ejemplo, sabemos que ciertamente no hay un compañero forzado en 2 desde la posición inicial; por lo tanto, sabemos que N> = 3 sin saber N.
Sami Liedes
Pero su pregunta comenzó con el supuesto de que hay una continuación ganadora de la posición dada. En cuyo caso Nes fijo, con juego perfecto.
Nishanth
¡Vi tu edición ahora!
Nishanth
1

Puedes mirar aquí para una discusión. Por supuesto, no debe usar la regla de 50 movimientos, pero de acuerdo con este foro, el registro se mantiene hasta ahora en esta posición (negro para moverse):

NN - NN

517 se mueve a una posición ganadora y 525 para aparearse (mejor jugada por ambos lados). Ver aquí , entrada 316. Por lo tanto, esta es una posición ganadora sin ganar en menos de 525 movimientos.

Permítanme también reproducir los comentarios de Bourzutschky: "Incluso pueden existir finales de 7 hombres más profundos, pero lo dudo. Que una profundidad tan grande todavía sea posible con tanta potencia de fuego en el tablero sugiere que pueden surgir finales aún más profundos con 8 piezas, tal vez en krnnkbbn. Este final podría generarse con 64 GB de RAM en unos pocos meses en una sola máquina de CPU rápida y aproximadamente 5 terabytes de almacenamiento.

J.-E. Alfiler
fuente
1
¡Esto no responde la pregunta, pero los detalles me parecen muy interesantes!
Halvard
0

Editar: Lo siento, parece que leí mal la pregunta. Mi conjetura es que cualquier N razonable está fuera del horizonte de una computadora. Si configuramos una computadora muy poderosa para calcular la posición inicial que es probablemente la única X segura que podemos mostrar, digamos que podría 10 millones de nodos por segundo después de 10 días podríamos calcular 10 * 86400 * 10 ^ 8 nodos = 8.64 * 10 ^ 13 nodos. Si suponemos que la posición promedio en los primeros 20 movimientos tiene alrededor de 15 movimientos legales (más bajo porque el comienzo tiene mucho menos y probablemente incluso un poco más bajo debido a la poda alfa-beta), que es solo unos 12 movimientos después de 10 días (posición solo después del movimiento 6 ) para que veas por qué este problema es feo. Sin embargo, creo que el juego práctico probablemente sugiere un valor mucho, mucho, mucho mayor. YO'

Ignoremos que el ajedrez es probablemente un empate. Debemos considerar las reglas bajo las cuales se juega el ajedrez en la práctica. En casi todas las situaciones de torneo, existe una regla de 50 movimientos que establece que el juego es un empate si "los últimos 50 movimientos consecutivos han sido realizados por cada jugador sin el movimiento de ningún peón y sin la captura de ninguna pieza".

Esto significa que podemos tener 49.5 movimientos por captura o movimiento de peón. Cada peón puede moverse hasta 6 veces y hay 15 piezas que pueden capturarse para cada lado (aunque una pieza debe permanecer para entregar el jaque mate) para que podamos poner un límite superior en el número de movimientos.

Esto resulta en 49.5 * (8 * 2 * 6 (movimientos de peón) + 29) = 6187.5 Entonces esto significa que SI el ajedrez es una victoria forzada para las blancas al adherirse a la regla de 50 movimientos, entonces está en un máximo de 6188 movimientos para las blancas . Probablemente podría reducir esto un poco sin hacer demasiado al decir que todos los compañeros de pieza K + v K que son forzados (Rook at Queen solamente) son factibles en sustancialmente menos de 50 movimientos (creo que 16 juegan con Nalimov por algunos casos "difíciles". ¡Así que creo que probablemente podamos restar 34 movimientos de ese total con confianza para 6134!

Por lo tanto: si el ajedrez es una victoria forzada para las blancas al adherirse a la regla de 50 movimientos, entonces es como máximo 6134 movimientos.

WorruB
fuente
La pregunta pedía un límite inferior, no un límite superior.
dfan
Pensé que quería el mejor límite inferior en el límite superior. ¿O la pregunta es si el ajedrez definitivamente no es compañero en X donde X podría ser 30 o algo así?
WorruB