¿Existe un algoritmo perfecto para el ajedrez? [cerrado]

Recientemente estuve en una discusión con una persona no codificadora sobre las posibilidades de las computadoras de ajedrez. No estoy muy versado en teoría, pero creo que sé lo suficiente.

Argumenté que no podría existir una máquina de Turing determinista que siempre ganara o se quedara estancada en el ajedrez. Creo que, incluso si busca en todo el espacio de todas las combinaciones de movimientos del jugador 1/2, el movimiento único que decide la computadora en cada paso se basa en una heurística. Al estar basado en una heurística, no necesariamente supera TODOS los movimientos que el oponente podría hacer.

Mi amigo pensó, por el contrario, que una computadora siempre ganaría o empataría si nunca cometía un movimiento "erróneo" (¿cómo lo define usted?). Sin embargo, siendo un programador que ha tomado CS, sé que incluso sus buenas decisiones, dado un oponente sabio, pueden obligarlo a cometer movimientos "erróneos" al final. Incluso si lo sabe todo, su próximo movimiento es codicioso al hacer coincidir una heurística.

La mayoría de las computadoras de ajedrez intentan hacer coincidir un posible final de juego con el juego en curso, que es esencialmente un seguimiento de programación dinámica. Una vez más, el final en cuestión es evitable.

Editar: Hmm ... parece que me revolví algunas plumas aquí. Eso es bueno.

Pensando en ello de nuevo, parece que no hay ningún problema teórico en resolver un juego finito como el ajedrez. Yo diría que el ajedrez es un poco más complicado que las damas en el sentido de que una victoria no es necesariamente por agotamiento numérico de piezas, sino por un mate. Mi afirmación original probablemente sea incorrecta, pero nuevamente creo que he señalado algo que aún no se ha probado satisfactoriamente (formalmente).

Supongo que mi experimento mental fue que cada vez que se toma una rama en el árbol, entonces el algoritmo (o caminos memorizados) debe encontrar un camino hacia un compañero (sin ser emparejado) para cualquier posible rama en los movimientos del oponente. Después de la discusión, compraré que si tenemos más memoria de la que podemos soñar, todos estos caminos podrían encontrarse.

"Argumenté que no podría existir una máquina de Turing determinista que siempre ganara o se quedara estancada en el ajedrez".

No tienes toda la razón. Puede haber una máquina así. El problema es la inmensidad del espacio estatal que tendría que buscar. Es finito, es REALMENTE grande.

Es por eso que el ajedrez recurre a la heurística: el espacio de estados es demasiado grande (pero finito). Incluso enumerar, y mucho menos buscar cada movimiento perfecto a lo largo de cada curso de cada juego posible, sería un problema de búsqueda muy, muy grande.

Las aperturas están programadas para llevarte a una mitad del juego que te da una posición "fuerte". No es un resultado conocido. Incluso los juegos finales, cuando hay menos piezas, son difíciles de enumerar para determinar el mejor próximo movimiento. Técnicamente son finitos. Pero la cantidad de alternativas es enorme. Incluso un 2 torres + rey tiene alrededor de 22 posibles próximos movimientos. Y si se necesitan 6 movimientos para mate, estás viendo 12,855,002,631,049,216 movimientos.

Haz los cálculos de los movimientos de apertura. Si bien solo hay unos 20 movimientos de apertura, hay alrededor de 30 segundos movimientos, por lo que para el tercer movimiento estamos viendo 360,000 estados de juego alternativos.

Pero los juegos de ajedrez son (técnicamente) finitos. Enorme, pero finito. Hay información perfecta. Hay estados de inicio y final definidos. No hay lanzamientos de monedas ni de dados.

No sé casi nada sobre lo que se ha descubierto sobre el ajedrez. Pero como matemático, este es mi razonamiento:

Primero debemos recordar que las blancas van primero y tal vez esto le dé una ventaja; tal vez le dé a las negras una ventaja.

Ahora suponga que no existe una estrategia perfecta para las negras que le permita siempre ganar / estancarse. Esto implica que no importa lo que hagan las negras, hay una estrategia que las blancas pueden seguir para ganar. Espere un minuto - esto significa que no es una estrategia perfecta para el blanco!

Esto nos dice que al menos uno de los dos jugadores qué tienen una estrategia perfecta que permite que el jugador siempre gana o empata.

Entonces solo hay tres posibilidades:

• El blanco siempre puede ganar si juega perfectamente
• El negro siempre puede ganar si juega perfectamente
• Un jugador puede ganar o empatar si juega a la perfección (y si ambos jugadores juegan perfectamente, siempre quedan estancados)

Pero cuál de estos es realmente correcto, es posible que nunca lo sepamos.

La respuesta a la pregunta es sí : debe haber un algoritmo perfecto para el ajedrez, al menos para uno de los dos jugadores.

Se ha demostrado para el juego de damas que un programa siempre puede ganar o empatar el juego. Es decir, no hay elección de movimientos que un jugador pueda hacer que obligue al otro jugador a perder.

Los investigadores pasaron casi dos décadas revisando los 500 billones de billones de posiciones posibles de las damas, que por cierto sigue siendo una fracción infinitesimalmente pequeña del número de posiciones de ajedrez. El esfuerzo de las damas incluyó a los mejores jugadores, que ayudaron al equipo de investigación a programar las reglas generales de las damas en un software que clasificaba los movimientos como exitosos o no exitosos. Luego, los investigadores dejaron que el programa se ejecutara, en un promedio de 50 computadoras al día. Algunos días, el programa se ejecutó en 200 máquinas. Mientras que los investigadores monitorearon el progreso y ajustaron el programa en consecuencia. De hecho, Chinook venció a los humanos para ganar el campeonato mundial de damas en 1994.

Sí, puedes resolver ajedrez, no, no lo harás pronto.

Esta no es una pregunta sobre computadoras, sino solo sobre el juego de ajedrez.

La pregunta es, ¿existe una estrategia a prueba de fallas para no perder nunca el juego? Si existe tal estrategia, entonces una computadora que lo sabe todo siempre puede usarla y ya no es una heurística.

Por ejemplo, el juego tic-tac-toe normalmente se juega basándose en heurísticas. Pero existe una estrategia a prueba de fallas. Independientemente de lo que mueva el oponente, siempre encontrará la manera de evitar perder el juego, si lo hace bien desde el principio.

Por lo tanto, necesitaría probar que tal estrategia existe o no también para el ajedrez. Básicamente es lo mismo, solo que el espacio de posibles movimientos es mucho mayor.

Llego a este hilo muy tarde y que ya se ha dado cuenta de algunos de los problemas. Pero como ex maestro y ex programador de ajedrez profesional, pensé que podría agregar algunos datos y cifras útiles. Hay varias formas de medir la complejidad del ajedrez :

• El número total de partidas de ajedrez es aproximadamente 10 ^ (10 ^ 50). Ese número es inimaginablemente grande.
• El número de partidas de ajedrez de 40 movimientos o menos es de alrededor de 10 ^ 40. Sigue siendo un número increíblemente grande.
• El número de posiciones de ajedrez posibles es de alrededor de 10 ^ 46.
• El árbol de búsqueda de ajedrez completo (número de Shannon) es de alrededor de 10 ^ 123, basado en un factor de ramificación promedio de 35 y una duración promedio de juego de 80.
• A modo de comparación, la cantidad de átomos en el universo observable se estima comúnmente en alrededor de 10 ^ 80.
• Se han recopilado y resuelto todos los finales de 6 piezas o menos .

Mi conclusión: mientras que el ajedrez es teóricamente solucionable, nunca tendremos el dinero, la motivación, el poder de cómputo o el almacenamiento para hacerlo.

De hecho, algunos juegos se han resuelto. Tic-Tac-Toe es muy fácil para construir una IA que siempre ganará o empatará. Recientemente, Connect 4 también se ha resuelto (y se ha demostrado que es injusto para el segundo jugador, ya que una jugada perfecta le hará perder).

El ajedrez, sin embargo, no se ha resuelto y no creo que haya ninguna prueba de que sea un juego justo (es decir, si el juego perfecto da como resultado un empate). Sin embargo, hablando estrictamente desde una perspectiva teórica, el ajedrez tiene un número finito de posibles configuraciones de piezas. Por lo tanto, el espacio de búsqueda es finito (aunque increíblemente grande). Por lo tanto, existe una máquina de Turing determinista que podría jugar perfectamente. Sin embargo, si alguna vez se podría construir uno, es un asunto diferente.

La computadora de escritorio promedio de $ 1000 podrá resolver las fichas en solo 5 segundos para el año 2040 (cálculos de 5x10 ^ 20).

Incluso a esta velocidad, 100 de estos ordenadores tardarían aproximadamente 6,34 x 10 ^ 19 años en resolver el ajedrez. Todavía no es factible. Ni siquiera cerca.

Alrededor de 2080, nuestras computadoras de escritorio promedio tendrán aproximadamente 10 ^ 45 cálculos por segundo. Una sola computadora tendrá la potencia computacional para resolver ajedrez en aproximadamente 27,7 horas. Definitivamente se hará para el 2080 siempre que la potencia informática siga creciendo como lo ha hecho en los últimos 30 años.

Para el 2090, existirá suficiente poder computacional en un escritorio de $ 1000 para resolver el ajedrez en aproximadamente 1 segundo ... por lo que para esa fecha será completamente trivial.

Dado que las damas se resolvieron en 2007, y el poder computacional para resolverlo en 1 segundo se retrasará entre 33 y 35 años, probablemente podamos estimar aproximadamente que el ajedrez se resolverá en algún lugar entre 2055-2057. Probablemente antes, ya que cuando se disponga de más potencia computacional (que será el caso en 45 años), se podrá dedicar más a proyectos como este. Sin embargo, diría que 2050 como muy pronto y 2060 como muy tarde.

En 2060, se necesitarían 100 computadoras de escritorio promedio de 3,17 x 10 ^ 10 años para resolver el ajedrez. Me doy cuenta de que estoy usando una computadora de $ 1000 como mi punto de referencia, mientras que probablemente habrá disponibles sistemas más grandes y supercomputadoras, ya que su relación precio / rendimiento también está mejorando. Además, su orden de magnitud de potencia computacional aumenta a un ritmo más rápido. Considere una supercomputadora que ahora puede realizar 2,33 x 10 ^ 15 cálculos por segundo, y una computadora de $ 1000 aproximadamente 2 x 10 ^ 9. En comparación, hace 10 años la diferencia era de 10 ^ 5 en lugar de 10 ^ 6. Para el año 2060, el orden de la diferencia de magnitud probablemente será de 10 ^ 12, e incluso esto puede aumentar más rápido de lo previsto.

Mucho de esto depende de si nosotros, como seres humanos, tenemos el impulso para resolver el ajedrez, pero el poder computacional lo hará factible en este momento (siempre que nuestro ritmo continúe).

Por otro lado, el juego Tic-Tac-Toe, que es mucho, mucho más sencillo, tiene 2.653.002 cálculos posibles (con tablero abierto). El poder computacional para resolver Tic-Tac-Toe en aproximadamente 2.5 (1 millón de cálculos por segundo) segundos se logró en 1990.

Retrocediendo, en 1955, una computadora tenía el poder de resolver Tic-Tac-Toe en aproximadamente 1 mes (1 cálculo por segundo). Nuevamente, esto se basa en lo que obtendría $ 1000 si pudiera empaquetarlo en una computadora (una computadora de escritorio de $ 1000 obviamente no existía en 1955), y esta computadora se habría dedicado a resolver Tic-Tac-Toe ... que no era el caso en 1955. La computación era costosa y no se habría utilizado para este propósito, aunque no creo que haya ninguna fecha en la que Tic-Tac-Toe se haya considerado "resuelto" por una computadora, pero estoy seguro que va por detrás de la potencia computacional real.

Además, tenga en cuenta que $ 1000 en 45 años valdrán aproximadamente 4 veces menos de lo que es ahora, por lo que se puede destinar mucho más dinero a proyectos como este, mientras que la potencia computacional seguirá siendo más barata.

De hecho, es posible que ambos jugadores tengan estrategias ganadoras en juegos infinitos sin un buen orden; sin embargo, el ajedrez está bien ordenado. De hecho, debido a la regla de los 50 movimientos , existe un límite superior para el número de movimientos que puede tener un juego y, por lo tanto, solo hay un número finito de juegos de ajedrez posibles (que se pueden enumerar para resolver exactamente ... teóricamente, al menos :)

Su final del argumento está respaldado por la forma en que funcionan ahora los programas de ajedrez modernos . Funcionan de esa manera porque es demasiado intensivo en recursos codificar un programa de ajedrez para que funcione de manera determinista. No siempre funcionarán necesariamente de esa manera. Es posible que algún día el ajedrez se resuelva , y si eso sucede, es probable que lo resuelva una computadora.

Para que conste, hay computadoras que pueden ganar o empatar a las damas . No estoy seguro de si se podría hacer lo mismo con el ajedrez. El número de movimientos es mucho mayor. Además, las cosas cambian porque las piezas pueden moverse en cualquier dirección, no solo hacia adelante y hacia atrás. Creo que, aunque no estoy seguro, el ajedrez es determinista, pero que hay demasiados movimientos posibles para que una computadora actualmente determine todos los movimientos en una cantidad de tiempo razonable.

Creo que estás acertado. Máquinas como Deep Blue y Deep Thought están programadas con una serie de juegos predefinidos y algoritmos inteligentes para analizar los árboles en los extremos de esos juegos. Esto, por supuesto, es una simplificación excesiva dramática. Siempre existe la posibilidad de "vencer" a la computadora en el transcurso de un juego. Con esto me refiero a hacer un movimiento que obliga a la computadora a realizar un movimiento que no es óptimo (sea lo que sea). Si la computadora no puede encontrar el mejor camino antes del límite de tiempo para la mudanza, es muy posible que cometa un error al elegir uno de los caminos menos deseables.

Hay otra clase de programas de ajedrez que utiliza aprendizaje automático real o programación genética / algoritmos evolutivos. Algunos programas han evolucionado y utilizan redes neuronales, et al, para tomar decisiones. En este tipo de casos, me imagino que la computadora podría cometer "errores", pero aún así terminar con una victoria.

Hay un libro fascinante sobre este tipo de médico de cabecera llamado Blondie24 que puede que leas. Se trata de damas, pero podría aplicarse al ajedrez.

Desde la teoría de juegos, que es de lo que trata esta pregunta, la respuesta es sí. El ajedrez se puede jugar perfectamente. El espacio del juego es conocido / predecible y sí, si tuviera las computadoras cuánticas de su nieto, probablemente podría eliminar todas las heurísticas.

Podría escribir una máquina de tic-tac-toe perfecta hoy en día en cualquier lenguaje de programación y funcionaría perfectamente en tiempo real.

Othello es otro juego que las computadoras actuales pueden jugar perfectamente, pero la memoria y la CPU de la máquina necesitarán un poco de ayuda.

El ajedrez es teóricamente posible pero no prácticamente posible (en 2008)

i-Go es complicado, su espacio de posibilidades cae más allá de la cantidad de átomos en el universo, por lo que podría llevarnos algo de tiempo hacer una máquina i-Go perfecta.

El ajedrez es un ejemplo de un juego matricial, que por definición tiene un resultado óptimo (piense en el equilibrio de Nash). Si los jugadores 1 y 2 toman cada uno movimientos óptimos, SIEMPRE se alcanzará un resultado determinado (aún se desconoce si se trata de una victoria-empate-pérdida).

Como programador de ajedrez de la década de 1970, definitivamente tengo una opinión al respecto. Lo que escribí hace unos 10 años, todavía es básicamente cierto hoy:

"Trabajo inconcluso y desafíos para los programadores de ajedrez"

En ese entonces, pensé que podríamos resolver el Ajedrez de manera convencional, si se hacía correctamente.

Las damas se resolvieron recientemente (¡¡¡Yay, Universidad de Alberta, Canadá !!!), pero eso se hizo con fuerza bruta. Para jugar al ajedrez de forma convencional, tendrás que ser más inteligente.

A menos que, por supuesto, la Computación Cuántica se convierta en una realidad. Si es así, el ajedrez se resolverá tan fácilmente como Tic-Tac-Toe.

A principios de la década de 1970 en Scientific American, hubo una breve parodia que me llamó la atención. Fue un anuncio de que el juego de ajedrez fue resuelto por una computadora de ajedrez rusa. Había determinado que hay un movimiento perfecto para las blancas que aseguraría una victoria con un juego perfecto de ambos lados, y ese movimiento es: 1. ¡a4!

Muchas de las respuestas aquí señalan los puntos importantes de la teoría de juegos:

1. El ajedrez es un juego finito y determinista con información completa sobre el estado del juego.
2. Puedes resolver un juego finito e identificar una estrategia perfecta
3. Sin embargo, el ajedrez es lo suficientemente grande como para que no puedas resolverlo por completo con un método de fuerza bruta.

Sin embargo, estas observaciones pasan por alto un punto práctico importante: no es necesario resolver el juego completo a la perfección para crear una máquina imbatible .

De hecho, es muy probable que pueda crear una máquina de ajedrez inmejorable (es decir, que nunca perderá y siempre forzará una victoria o un empate) sin buscar ni siquiera una pequeña fracción del espacio de estado posible.

Las siguientes técnicas, por ejemplo, reducen enormemente el espacio de búsqueda requerido:

• Las técnicas de poda de árboles como Alpha / Beta o MTD-f ya reducen enormemente el espacio de búsqueda
• Posición ganadora demostrable. Muchos finales caen en esta categoría: no necesitas buscar KR vs K, por ejemplo, es una victoria probada. Con algo de trabajo es posible demostrar muchas más victorias garantizadas.
• Casi ciertas victorias - por un juego "suficientemente bueno" sin errores tontos (digamos sobre ELO 2200+?) Muchas posiciones de ajedrez son victorias casi seguras, por ejemplo, una ventaja material decente (por ejemplo, un Caballo extra) sin ninguna ventaja posicional compensatoria. Si su programa puede forzar tal posición y tiene una heurística suficientemente buena para detectar la ventaja posicional, puede asumir con seguridad que ganará o al menos empatará con un 100% de probabilidad.
• Heurística de búsqueda de árbol: con un reconocimiento de patrones suficientemente bueno, puede concentrarse rápidamente en el subconjunto relevante de movimientos "interesantes". Así es como juegan los grandes maestros humanos, por lo que claramente no es una mala estrategia ... y nuestros algoritmos de reconocimiento de patrones mejoran constantemente
• Evaluación de riesgos: una mejor concepción del "riesgo" de un puesto permitirá una búsqueda mucho más eficaz al centrar la potencia de cálculo en situaciones en las que el resultado es más incierto (esta es una extensión natural de la búsqueda en reposo )

Con la combinación correcta de las técnicas anteriores, me sentiría cómodo afirmando que es posible crear una máquina de juego de ajedrez "inmejorable". Probablemente no estemos demasiado lejos con la tecnología actual.

Tenga en cuenta que es casi seguro que es más difícil demostrar que esta máquina no puede ser vencida. Probablemente sería algo así como la hipótesis de Reimann: estaríamos bastante seguros de que juega perfectamente y tendríamos resultados empíricos que muestran que nunca perdió (incluidos algunos miles de millones de proyectos consecutivos contra sí mismo), pero en realidad no tendríamos la capacidad de Pruébalo.

Nota adicional sobre la "perfección":

Tengo cuidado de no describir la máquina como "perfecta" en el sentido de la teoría del juego porque eso implica condiciones adicionales inusualmente fuertes, como:

• Siempre ganando en todas las situaciones en las que es posible forzar una victoria, sin importar cuán compleja sea la combinación ganadora. Habrá situaciones en el límite entre ganar / empatar donde esto sea extremadamente difícil de calcular perfectamente.
• Explotar toda la información disponible sobre posibles imperfecciones en el juego de tu oponente, por ejemplo, inferir que tu oponente podría ser demasiado codicioso y jugar deliberadamente una línea un poco más débil de lo habitual con el argumento de que tiene un mayor potencial para tentar a tu oponente a cometer un error. Contra oponentes imperfectos, de hecho, puede ser óptimo perder si estima que su oponente probablemente no detectará la victoria forzada y le da una mayor probabilidad de ganar usted mismo.

La perfección (sobre todo ante oponentes imperfectos y desconocidos) es un problema mucho más difícil que simplemente ser invencible.

Si busca en todo el espacio de todas las combinaciones de movimientos de jugador1 / 2, el único movimiento que decide la computadora en cada paso se basa en una heurística.

Allí hay dos ideas en competencia. Una es que busque todos los movimientos posibles y la otra es que decida basándose en una heurística. Una heurística es un sistema para hacer una buena suposición. Si está buscando en todos los movimientos posibles, entonces ya no está adivinando.

"¿Existe un algoritmo perfecto para el ajedrez?"

Sí hay. Tal vez sea para que las blancas ganen siempre. Tal vez sea para que las negras ganen siempre. Quizás sea que ambos siempre se empaten al menos. No sabemos cuál, y nunca lo sabremos, pero ciertamente existe.

Ver también

• El algoritmo de dios

Encontré este artículo de John MacQuarrie que hace referencia al trabajo del "padre de la teoría de juegos" Ernst Friedrich Ferdinand Zermelo . Llega a la siguiente conclusión:

En el ajedrez, las blancas pueden forzar una victoria o las negras pueden forzar una victoria, o ambos lados pueden forzar al menos un empate.

La lógica me parece sólida.

Es perfectamente solucionable.

Hay 10 ^ 50 posiciones impares. Cada posición, según mis cálculos, requiere un mínimo de 64 bytes redondos para almacenar (cada cuadrado tiene: 2 bits de afiliación, 3 bits de pieza). Una vez que se cotejan, las posiciones que son jaque mate se pueden identificar y las posiciones se pueden comparar para formar una relación, mostrando qué posiciones conducen a otras posiciones en un gran árbol de resultados.

Entonces, el programa solo necesita encontrar las raíces de jaque mate de un solo lado más bajas, si tal cosa existe. En cualquier caso, el ajedrez se resolvió de manera bastante simple al final del primer párrafo.

Solo estoy convencido en un 99,9% por la afirmación de que el tamaño del espacio estatal hace que sea imposible esperar una solución.

Seguro, 10 ^ 50 es un número increíblemente grande. Llamemos n al tamaño del espacio de estados.

¿Cuál es el límite del número de movimientos en el juego más largo posible? Dado que todos los juegos terminan en un número finito de movimientos, existe tal límite, llámelo m.

Comenzando desde el estado inicial, ¿no puede enumerar todos los n movimientos en el espacio O (m)? Claro, lleva O (n) tiempo, pero los argumentos del tamaño del universo no abordan directamente eso. O (m) el espacio puede que ni siquiera sea mucho. Para O (m) space, ¿no podría también rastrear, durante este recorrido, si la continuación de cualquier estado a lo largo del camino que está atravesando conduce a EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin o BlackMayWinOrForceDraw? (Hay una celosía dependiendo de quién sea el turno, anote cada estado en el historial de su recorrido con la reunión de celosía).

A menos que me falte algo, ese es un algoritmo de espacio O (n) tiempo / O (m) para determinar en cuál de las categorías posibles cae el ajedrez. Wikipedia cita una estimación de la edad del universo en aproximadamente 10 ^ 60 tiempos de Planck. Sin entrar en un argumento de cosmología, supongamos que queda mucho tiempo antes del calor / frío / lo que sea que muera el universo. Eso nos deja en la necesidad de evaluar un movimiento cada 10 ^ 10 veces Planck, o cada 10 ^ -34 segundos. Es un tiempo increíblemente corto (aproximadamente 16 órdenes de magnitud más corto que los tiempos más cortos jamás observados). Digamos con optimismo que con una implementación super-duper-buena que se ejecuta en la parte superior de la línea presente-o-previsto-no-cuántico-P-es-un-subconjunto-apropiado-de-NP, podríamos esperar evaluar (tome un solo paso adelante, categorizar el estado resultante como un estado intermedio o uno de los tres estados finales) a una velocidad de 100 MHz (una vez cada 10 ^ -8 segundos). Dado que este algoritmo es muy paralelizable, esto nos deja necesitando 10 ^ 26 de esas computadoras o aproximadamente una por cada átomo de mi cuerpo, junto con la capacidad de recopilar sus resultados.

Supongo que siempre hay un poco de esperanza para una solución de fuerza bruta. Podríamos tener suerte y, al explorar solo uno de los posibles movimientos de apertura de las blancas, ambos elegimos uno con un fanout mucho más bajo que el promedio y otro en el que las blancas siempre ganan o ganan o empatan.

También podríamos esperar reducir un poco la definición de ajedrez y persuadir a todos de que sigue siendo moralmente el mismo juego. ¿Realmente necesitamos que las posiciones se repitan 3 veces antes de un empate? ¿Realmente necesitamos hacer que el grupo que huye demuestre la capacidad de escapar durante 50 movimientos? ¿Alguien siquiera entiende qué diablos pasa con la passant en regla? ;) Más en serio, es lo que realmente necesitamos para obligar a un jugador para moverse (en comparación con cualquiera de dibujo o perder) cuando su sólo se mueven para escapar cheque o un punto muerto es una passant en la captura? ¿Podríamos limitar la elección de piezas a las que se puede promover un peón si la promoción deseada que no es de reina no conduce a un jaque o jaque mate inmediato?

Tampoco estoy seguro de cuánto permitir el acceso basado en hash de cada computadora a una gran base de datos de estados tardíos del juego y sus posibles resultados (que podrían ser relativamente factibles en el hardware existente y con las bases de datos del juego final existentes) podría ayudar a podar la búsqueda antes. Obviamente, no puede memorizar toda la función sin el almacenamiento O (n), pero puede elegir un entero grande y memorizar tantos finales enumerando al revés de cada estado final posible (o incluso no fácilmente demostrable imposible, supongo).

Sé que esto es un poco complicado, pero tengo que poner mis 5 centavos aquí. Es posible que una computadora, o una persona, termine cada partida de ajedrez en la que participa, ya sea en una victoria o en un punto muerto.

Sin embargo, para lograr esto, debe conocer con precisión cada movimiento y reacción posible, etc., hasta el final de todos y cada uno de los resultados posibles del juego, y para visualizar esto, o para hacer una manera fácil de analizar esta información, piense en como un mapa mental que se ramifica constantemente.

El nodo central sería el comienzo del juego. Cada rama de cada nodo simbolizaría un movimiento, cada uno diferente a sus movimientos hermanos. Presentarlo en esta mansión requeriría muchos recursos, especialmente si lo estuviera haciendo en papel. En una computadora, esto tomaría posiblemente cientos de Terrabytes de datos, ya que tendría muchos movimientos repetitivos, a menos que hiciera que las ramas regresaran.

Sin embargo, memorizar tales datos sería inverosímil, si no imposible. Para hacer que una computadora reconozca el movimiento más óptimo para sacar de los (como máximo) 8 movimientos instantáneamente posibles, sería posible, pero no plausible ... ya que esa computadora necesitaría poder procesar todas las ramas más allá de ese movimiento, hasta llegar a una conclusión, cuente todas las conclusiones que resulten en una victoria o un estancamiento, luego actúe sobre esa cantidad de conclusiones ganadoras contra las conclusiones perdidas, y eso requeriría una RAM capaz de procesar datos en los Terrabytes, ¡o más! ¡Y con la tecnología actual, una computadora como esa requeriría más que el saldo bancario de los 5 hombres y / o mujeres más ricos del mundo!

Entonces, después de toda esa consideración, se pudo hacer, sin embargo, ninguna persona podría hacerlo. Tal tarea requeriría 30 de las mentes más brillantes vivas en la actualidad, no solo en el ajedrez, sino en la ciencia y la tecnología informática, y tal tarea solo podría completarse en un (pongámoslo completamente en perspectiva básica) ... extremadamente en última instancia hiper super-duper computadora ... que posiblemente no podría existir durante al menos un siglo. ¡Sera hecho! Simplemente no en esta vida.

Hay dos errores en su experimento mental:

1. Si tu máquina de Turing no está "limitada" (en memoria, velocidad, ...) no necesitas usar heurísticas pero puedes calcular evaluar los estados finales (ganar, perder, empatar). Para encontrar el juego perfecto, solo necesitaría usar el algoritmo Minimax (consulte http://en.wikipedia.org/wiki/Minimax ) para calcular los movimientos óptimos para cada jugador, lo que conduciría a uno o más juegos óptimos.

2. Tampoco hay límite en la complejidad de la heurística utilizada. Si puede calcular un juego perfecto, también hay una forma de calcular una heurística perfecta a partir de él. Si es necesario, es solo una función que mapea posiciones de ajedrez de la manera "Si estoy en esta situación S, mi mejor movimiento es M".

Como ya han señalado otros, esto terminará en 3 posibles resultados: las blancas pueden forzar una victoria, las negras pueden forzar una victoria, uno de ellos puede forzar un empate.

El resultado de un juego de damas perfecto ya ha sido "calculado". Si la humanidad no se destruye a sí misma antes, también habrá un cálculo para el ajedrez algún día, cuando las computadoras hayan evolucionado lo suficiente como para tener suficiente memoria y velocidad. O tenemos algunas computadoras cuánticas ... O hasta que alguien (investigador, expertos en ajedrez, genio) encuentra algunos algoritmos que reducen significativamente la complejidad del juego. Para dar un ejemplo: ¿Cuál es la suma de todos los números entre 1 y 1000? Puede calcular 1 + 2 + 3 + 4 + 5 ... + 999 + 1000, o simplemente puede calcular: N * (N + 1) / 2 con N = 1000; resultado = 500500. Ahora imagina que no sabes sobre esa fórmula, no sabes sobre inducción matemática, ni siquiera sabes cómo multiplicar o sumar números, ... Entonces, Es posible que exista un algoritmo actualmente desconocido que, en última instancia, reduzca la complejidad de este juego y solo tomaría 5 minutos calcular el mejor movimiento con una computadora actual. Tal vez incluso sería posible estimarlo como un ser humano con lápiz y papel, o incluso en tu mente, con un poco más de tiempo.

Entonces, la respuesta rápida es: si la humanidad sobrevive lo suficiente, ¡es solo cuestión de tiempo!

Puede que tenga solución, pero algo me molesta: incluso si se pudiera atravesar todo el árbol, todavía no hay forma de predecir el próximo movimiento del oponente. Siempre debemos basar nuestro próximo movimiento en el estado del oponente y hacer el "mejor" movimiento disponible. Luego, según el siguiente estado, lo volvemos a hacer. Entonces, nuestro movimiento óptimo podría ser óptimo si el oponente se mueve de cierta manera. Para algunos movimientos del oponente, nuestro último movimiento podría haber sido subóptimo.

Simplemente no veo cómo podría haber un movimiento "perfecto" en cada paso.

Para que ese sea el caso, debe haber para cada estado [en el juego actual] un camino en el árbol que conduzca a la victoria, independientemente del próximo movimiento del oponente (como en tic-tac-toe), y tengo una dificultad tiempo pensando en eso.

Matemáticamente, el ajedrez ha sido resuelto por el algoritmo Minimax , que se remonta a la década de 1920 (ya sea encontrado por Borel o von Neumann). Por lo tanto, una máquina de turing puede jugar al ajedrez perfecto.

Sin embargo, la complejidad computacional del ajedrez lo hace prácticamente inviable. Los motores actuales utilizan varias mejoras y heurísticas. Los mejores motores de hoy han superado a los mejores humanos en términos de fuerza de juego, pero debido a la heurística que están usando, es posible que no funcionen perfectamente cuando se les da un tiempo infinito (por ejemplo, las colisiones de hash pueden conducir a resultados incorrectos).

Lo más cercano que tenemos actualmente en términos de juego perfecto son las tablas de finales . La técnica típica para generarlos se llama análisis retrógrado . Actualmente se han resuelto todas las posiciones con hasta seis piezas.

Sí , en matemáticas, el ajedrez se clasifica como un juego determinado, eso significa que tiene un algoritmo perfecto para cada primer jugador, esto está demostrado que es cierto incluso para un tablero de ajedrez infinito, por lo que un día probablemente una IA cuántica encontrará la estrategia perfecta. y el juego se ha ido

Más sobre esto en este video: https://www.youtube.com/watch?v=PN-I6u-AxMg

También está el ajedrez cuántico, donde no hay pruebas matemáticas de que sea un juego determinado http://store.steampowered.com/app/453870/Quantum_Chess/

y ahí tienes un video detallado sobre el ajedrez cuántico https://chess24.com/en/read/news/quantum-chess

Por supuesto, solo hay 10 elevado a la potencia de cincuenta combinaciones posibles de piezas en el tablero. Teniendo esto en cuenta, para jugar a cada compilación, necesitarías hacer menos de 10 elevado a la potencia de cincuenta movimientos (incluidas las repeticiones, multiplica ese número por 3). Entonces, hay menos de diez a la potencia de cien movimientos en el ajedrez. Solo elige los que te lleven al jaque mate y listo

Matemáticas de 64 bits (= tablero de ajedrez) y operadores bit a bit (= próximos movimientos posibles) es todo lo que necesita. Tan simplemente. Brute Force encontrará la mejor manera de hacerlo. Por supuesto, no existe un algoritmo universal para todas las posiciones. En la vida real, el cálculo también está limitado en el tiempo, el tiempo de espera lo detendrá. Un buen programa de ajedrez significa código pesado (peones pasados, doblados, etc.). El código pequeño no puede ser muy fuerte. Las bases de datos de apertura y finales solo ahorran tiempo de procesamiento, algún tipo de datos preprocesados. El dispositivo, quiero decir: el sistema operativo, la posibilidad de subprocesamiento, el entorno, el hardware define los requisitos. El lenguaje de programación es importante. De todos modos, el proceso de desarrollo es interesante.