Cuántos legal de los estados de ajedrez existe?

Question

Tengo una bastante simple pregunta. Cuántos legal de los estados de ajedrez existe? "Legal", como en la permitida por las reglas y el "estado" como una configuración única de las piezas.

Estoy no solicitar el número de posibles juegos de ajedrez. Estoy preguntando por el número de posibles jurídica de los estados, o de tablero de ajedrez de las configuraciones, las reglas del ajedrez permite.

Por ejemplo, un peón blanco no puede ser en [A-H]1 y un rey no puede estar en jaque por dos piezas diferentes al mismo tiempo. Tales estados son, obviamente, no permitida por las reglas e ilegal.

Answer 1

Se debe aclarar si se desea diferenciar entre posiciones basadas en "en passant", el enroque, y cuyo lado es moverse. Francisco Labelle y otros han utilizado el término de ajedrez "posición" para indicar que la junta de estado, incluyendo la información anterior, y de ajedrez "diagrama" para indicar un consejo de estado, no como la anterior información, es decir, justo lo que las piezas en el tablero y donde. En ninguno de los casos es información para la elaboración de normas tales como la 50-mover la regla o la triple repetición de la regla incluido.

La mejor cota superior de la encontrada para el número de posiciones de ajedrez es 7728772977965919677164873487685453137329736522, o acerca de la $7.7 * 10^{45}$, basado en un programa complicado por Juan Tromp, según él, la mejor documentación es necesaria para que el programa sea considerado verificable. Él también tiene una mucho más sencillo programa que le da una cota superior de a $4.5 * 10^{46}$.

Para los diagramas de ajedrez, Tromps más sencillo programa proporciona un límite superior de aproximadamente $2.2 * 10^{46}$; no dice lo obligado es obtenida por el programa complicado, pero es probablemente un poco menos de la mitad (desde el lado de dobles de la envolvente, mientras que el enroque y en passant agregar relativamente poco), así que es probable acerca de $3.8 * 10^{45}$. Más información en el sitio web de la Tromp

La mejor obligado publicado en una revista fue obtenida por Shirish Chinchalkar en "Un límite Superior para el Número de Accesible Posiciones". No tengo acceso a este papel, pero de acuerdo a Tromp es acerca de $10^{46.25}$. Aunque se refiere a "posiciones", podría muy fácilmente ser un límite para el número de diagramas.

Como para los límites inferiores, que son mucho más difíciles, desde una posición dada puede ser ilegal, por muy sutiles razones. Wikipedia ha afirmado que el número de puestos es "entre el$10^{43}$$10^{47}$", pero creo que es poco probable que el límite inferior ha sido probado.

Me imagino que el número real de diagramas es entre el$10^{44}$$10^{45}$, pero esto es pura especulación.

Answer 2

Puesto que usted desea a todos los estados "que las reglas lo permiten," es muy poco probable que usted pueda obtener una respuesta exacta con los ordenadores actuales, pero tal vez usted puede obtener los límites superior e inferior. Una mano ondulado prueba de por qué esto debería ser, es que en el fin de contar con los estados, que seguramente tendrá que enumerar a ellos (o a enumerar las clases de equivalencia de ellos, donde usted tiene una cuenta de fórmula para cada clase de equivalencia). Pero en el equipo de ajedrez de la estrategia, la enumeración de los posibles estados futuros (y la comprensión de que el estado puede llevar a que el estado) es la forma en que prácticamente todos los jugadores de ajedrez jugar, y sin embargo no puede enumerar todo hasta el punto de encontrar una primera estrategia ganadora (o de demostrar que ninguna estrategia ganadora existe). De hecho, incluso super-computadoras no pueden ni siquiera acercarse.