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

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?

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.

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.

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

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):

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.

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.