algorithm - pensamiento - ¿Hay un algoritmo perfecto para el ajedrez?
algoritmos de ajedrez analisis (27)
"¿Hay un algoritmo perfecto para el ajedrez?"
Sí hay. Tal vez sea para que las blancas siempre ganen. Tal vez sea para Black que siempre gane. Tal vez sea para ambos siempre empate al menos. No sabemos cuál, y nunca lo sabremos, pero ciertamente existe.
Ver también
Recientemente estuve hablando 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 ganó o se estancó en el ajedrez. Creo que, incluso si busca el espacio completo de todas las combinaciones de jugadores 1/2 movimientos, el único movimiento que la computadora decida en cada paso se basa en una heurística. Al estar basado en una heurística, no necesariamente vence a 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 hiciera un movimiento de "error" (¿cómo defines eso?). Sin embargo, como soy un programador que ha tomado CS, sé que incluso sus buenas elecciones, dado un oponente sabio, pueden forzarlo a realizar movimientos de "error" al final. Incluso si sabes todo, tu próximo movimiento es codicioso al combinar una heurística.
La mayoría de las computadoras de ajedrez intentan hacer coincidir un posible juego final con el juego en progreso, que es esencialmente un seguimiento de programación dinámico. Nuevamente, el final del juego en cuestión es evitable.
Edit: Hmm ... parece que he revuelto algunas plumas aquí. Eso es bueno.
Al pensarlo nuevamente, parece que no hay ningún problema teórico para resolver un juego finito como el ajedrez. Yo diría que el ajedrez es un poco más complicado que las damas en que una victoria no es necesariamente por agotamiento numérico de piezas, sino por un compañero. Mi afirmación original probablemente sea errónea, pero creo que he señalado algo que aún no está probado satisfactoriamente (formalmente).
Supongo que mi experimento mental fue que cada vez que se toma una rama en el árbol, el algoritmo (o las rutas memorizadas) debe encontrar una ruta a un compañero (sin aparearse) para cualquier posible rama en los movimientos del oponente. Después de la discusión, compraré que con más memoria de la que podamos soñar, todos estos caminos podrían encontrarse.
Si busca el espacio completo de todas las combinaciones de jugadores1 / 2 movimientos, el único movimiento que la computadora decida en cada paso se basa en una heurística.
Hay dos ideas que compiten allí. Una es que busca todos los movimientos posibles, y la otra es que usted decide en función de una heurística. Una heurística es un sistema para hacer una buena suposición. Si buscas en cada movimiento posible, entonces ya no estás adivinando.
"Argumenté que no podría existir una máquina determinante de Turing que siempre ganó o se estancó en el ajedrez".
No estás del todo bien. Puede haber tal máquina. El problema es la enormidad del espacio de estado que debería buscar. Es finito, es REALMENTE grande.
Es por eso que el ajedrez recurre a la heurística: el espacio de estado es demasiado grande (pero finito). Incluso enumerar, y mucho menos buscar cada movimiento perfecto en cada curso de cada juego posible, sería un problema de búsqueda muy, muy grande.
Las aperturas tienen un guión para llegar a un juego intermedio que le 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 cuál es el mejor movimiento siguiente. Técnicamente son finitos. Pero la cantidad de alternativas es enorme. Incluso un 2 rooks + king tiene algo así como 22 posibles próximos movimientos. Y si se necesitan 6 movimientos para aparearse, estás viendo 12,855,002,631,049,216 movimientos.
Haz los cálculos sobre los movimientos de apertura. Aunque solo hay unas 20 jugadas de apertura, hay algo así como 30 movimientos de segundo o así, por lo que en 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 fin definidos. No hay tiradas de monedas o dados.
Algunos juegos, de hecho, han sido resueltos. 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 hará que pierda).
El ajedrez, sin embargo, no se ha resuelto, y no creo que haya ninguna prueba de que sea un juego justo (es decir, si la jugada perfecta resulta en un empate). 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. Si alguna vez se podría construir, sin embargo, es un asunto diferente.
Como programador de ajedrez de la década de 1970, definitivamente tengo una opinión sobre esto. Lo que escribí hace 10 años, sigue siendo cierto hoy en día:
"Trabajo inacabado y desafíos para los programadores de ajedrez"
En aquel entonces, pensé que podríamos resolver el Ajedrez convencionalmente, si se hacía correctamente.
Las damas se resolvieron recientemente (¡Sí, Universidad de Alberta, Canadá!) Pero eso se hizo de manera efectiva Fuerza Bruta. Para hacer ajedrez convencionalmente, deberás ser más inteligente.
A menos que, por supuesto, la computación cuántica se convierta en 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. Se determinó que hay un movimiento perfecto para el blanco que garantizaría una victoria con el juego perfecto de ambos lados, y ese movimiento es: 1. a4!
Creo que estás muerto. 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 es, por supuesto, una sobresimplificación dramática. Siempre hay una posibilidad de "vencer" a la computadora a lo largo del juego. Con esto me refiero a hacer un movimiento que obliga a la computadora a realizar un movimiento que es menos que óptimo (lo que sea que sea). Si la computadora no puede encontrar la mejor ruta antes del límite de tiempo para la mudanza, podría cometer un error al elegir una de las rutas menos deseables.
Hay otra clase de programas de ajedrez que utiliza el aprendizaje automático real, o la programación genética / algoritmos evolutivos. Algunos programas han evolucionado y usan redes neuronales, etc., para tomar decisiones. En este tipo de caso, me imagino que la computadora podría cometer "errores", pero aún así terminar en una victoria.
Hay un libro fascinante sobre este tipo de GP llamado Blondie24 que podrías leer. Se trata de damas, pero podría aplicarse al ajedrez.
De hecho, es posible que ambos jugadores tengan estrategias ganadoras en juegos infinitos sin ordenar bien; sin embargo, el ajedrez está bien ordenado. De hecho, debido a la regla de 50 movimientos , hay un límite superior al número de movimientos que un juego puede tener, y por lo tanto, solo hay finitos muchos juegos de ajedrez posibles (que se pueden enumerar para resolver exactamente ... teóricamente, al menos :)
De la teoría de juegos, de lo que se trata esta pregunta, la respuesta es sí. El ajedrez se puede jugar perfectamente. El espacio del juego es conocido / predecible y sí, si tuvieras las computadoras cuánticas de tu nieto probablemente puedas eliminar todas las heurísticas.
Podrías escribir una máquina de tres en raya perfecta hoy en día en cualquier lenguaje de scripting y jugaría perfectamente en tiempo real.
Othello es otro juego que las computadoras actuales pueden jugar perfectamente, pero la memoria de la máquina y la CPU necesitarán un poco de ayuda
El ajedrez es teóricamente posible pero no es posible en la práctica (en 2008)
i-Go es complicado, su espacio de posibilidades está por encima de la cantidad de átomos en el universo, por lo que podría tomarnos un tiempo crear una máquina i-Go perfecta.
El ajedrez es un ejemplo de un juego de matriz, que por definición tiene un resultado óptimo (piense en el equilibrio de Nash). Si el jugador 1 y 2 toman movimientos óptimos, SIEMPRE se alcanzará un determinado resultado (aún se desconoce si se trata de una derrota por empate).
El escritorio promedio de $ 1000 podrá resolver damas en solo 5 segundos para el año 2040 (5x10 ^ 20 cálculos).
Incluso a esta velocidad, todavía tomaría 100 de estas computadoras aproximadamente 6.34 x 10 ^ 19 años para resolver el ajedrez. Aún no es factible. Ni siquiera cerca.
Alrededor de 2080, nuestros escritorios promedio tendrán aproximadamente 10 ^ 45 cálculos por segundo. Una sola computadora tendrá el poder computacional para resolver el ajedrez en aproximadamente 27.7 horas. Definitivamente se realizará en 2080, siempre y cuando el poder de la computación continúe creciendo como lo ha hecho en los últimos 30 años.
Para el año 2090, habrá suficiente poder computacional en un escritorio de $ 1000 para resolver el ajedrez en aproximadamente 1 segundo ... así 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á unos 33-35 años, probablemente podamos estimar que el ajedrez se resolverá en algún lugar entre 2055-2057. Probablemente, antes, cuando haya más potencia computacional disponible (que será el caso en 45 años), se puede dedicar más a proyectos como este. Sin embargo, diría 2050 como muy pronto, y 2060 a más tardar.
En 2060, tomaría 100 escritorios promedio 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 sistemas y supercomputadoras más grandes probablemente estarán disponibles 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 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 10 ^ 5 en lugar de 10 ^ 6. Para 2060, la diferencia de orden de magnitud será probablemente 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).
En otra nota, el juego de Tic-Tac-Toe, que es mucho, mucho más simple, tiene 2,653,002 cálculos posibles (con un 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 $ 1000 obtendría 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 .... simplemente no era el caso en 1955. La computación era cara y no se habría utilizado para este propósito, aunque no creo que haya ninguna fecha en la que Tic-Tac-Toe haya sido "resuelto" por una computadora, pero estoy seguro que se queda atrás del poder computacional real.
Además, tener en cuenta $ 1000 en 45 años valdrá 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 el poder de cómputo seguirá siendo más barato.
El modo en que funcionan los programas de ajedrez modernos ahora respalda su argumento. Funcionan de esa manera porque es demasiado intenso en recursos para codificar un programa de ajedrez para operar de manera determinista. No necesariamente siempre funcionarán de esa manera. Es posible que el ajedrez se solved algún día, y si eso sucede, es probable que sea resuelto por una computadora.
Encontré este artículo de John MacQuarrie que hace referencia al trabajo del "padre de la teoría de juegos" Ernst Friedrich Ferdinand Zermelo . Se llega a la siguiente conclusión:
En ajedrez, ya sea blanco puede forzar una victoria, o negro puede 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 jaquemate se pueden identificar y las posiciones se pueden comparar para formar una relación, mostrando qué posiciones conducen a otras posiciones en un árbol de resultados grande.
Entonces, el programa solo necesita encontrar las raíces de jaque mate más bajas, si es que existe. En cualquier caso, Chess fue resuelto bastante simplemente al final del primer párrafo.
Estoy llegando a este hilo muy tarde, y que ya te has dado cuenta de algunos de los problemas. Pero como ex-maestro y ex programador de ajedrez profesional, pensé que podría agregar algunos hechos y cifras útiles. Hay varias formas de medir la complejidad del ajedrez :
- El número total de juegos de ajedrez es de aproximadamente 10 ^ (10 ^ 50). Ese número es inimaginablemente grande.
- La cantidad de juegos de ajedrez de 40 movimientos o menos es de alrededor de 10 ^ 40. Eso sigue siendo un número increíblemente grande.
- La cantidad de posibles posiciones de ajedrez es de alrededor de 10 ^ 46.
- El árbol completo de búsqueda de ajedrez (número de Shannon) es alrededor de 10 ^ 123, basado en un factor de ramificación promedio de 35 y una longitud promedio de juego de 80.
- Para comparación, el número de átomos en el universo observable se estima comúnmente en alrededor de 10 ^ 80.
- Todos los finales de 6 piezas o menos han sido en.wikipedia.org/wiki/Tablebase .
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.
Hay dos errores en tu experimento mental:
Si su máquina Turing no está "limitada" (en memoria, velocidad, ...) no necesita usar heurísticas, pero puede calcular los estados finales (ganar, perder, dibujar). Para encontrar el juego perfecto, solo necesitas usar el algoritmo Minimax (ver http://en.wikipedia.org/wiki/Minimax ) para calcular los movimientos óptimos para cada jugador, lo que llevaría a uno o más juegos óptimos.
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 las posiciones de ajedrez de la manera "Si estoy en esta situación, mi mejor jugada es M".
Como ya lo señalaron otros, esto terminará en 3 resultados posibles: el blanco puede forzar una victoria, el negro puede 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 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) encuentre algunos algoritmos que reduzcan 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 imagine que no sabe acerca de esa fórmula, no sabe acerca de la inducción matemática, ni siquiera sabe cómo multiplicar o agregar números, ... Entonces, es posible que haya una algoritmo desconocido que en última instancia reduce la complejidad de este juego y solo tomaría 5 minutos calcular el mejor movimiento con una computadora actual. Tal vez sería incluso posible estimarlo como un ser humano con lápiz y papel, o incluso en su mente, dado un poco más de tiempo.
Entonces, la respuesta rápida es: ¡si la humanidad sobrevive lo suficiente, es solo cuestión de tiempo!
La matemática de 64 bits (= tablero de ajedrez) y los operadores bit a bit (= los siguientes movimientos posibles) es todo lo que necesita. Tan simplemente. Brute Force encontrará la mejor manera por lo general. 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, duplicados, etc.). El código pequeño no puede ser muy fuerte. Las bases de datos de apertura y final solo ahorran tiempo de procesamiento, algún tipo de datos preprocesados. Me refiero al dispositivo: el sistema operativo, la posibilidad de roscado, el entorno y los requisitos de definición del hardware. El lenguaje de programación es importante. De todos modos, el proceso de desarrollo es interesante.
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 ajedrez perfecto.
Sin embargo, la complejidad computacional del ajedrez lo hace prácticamente inviable. Los motores actuales usan varias mejoras y heurísticas. Los mejores motores de hoy en día han superado a los mejores humanos en términos de fuerza de juego, pero debido a la heurística que están utilizando, es posible que no sean perfectos cuando se les da un tiempo infinito (por ejemplo, las colisiones hash pueden dar resultados incorrectos).
Lo más parecido que tenemos actualmente en términos de juego perfecto son las bases de juego 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.
Muchas respuestas aquí hacen que los puntos teóricos del juego sean importantes:
- El ajedrez es un juego finito y determinista con información completa sobre el estado del juego
- Puedes resolver un juego finito e identificar una estrategia perfecta
- El ajedrez es lo suficientemente grande como para que no puedas resolverlo completamente con un método de fuerza bruta
Sin embargo, estas observaciones omiten un punto práctico importante: no es necesario resolver el juego completo a la perfección para crear una máquina inmejorable .
De hecho, es bastante probable que pueda crear una máquina de ajedrez imbatible (es decir, 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, todas reducen enormemente el espacio de búsqueda requerido:
- Técnicas de poda de árboles como Alpha / Beta o MTD-f ya reducen masivamente el espacio de búsqueda
- Posible posición ganadora. Muchos finales entran en esta categoría: no es necesario buscar KR vs K, por ejemplo, es una victoria comprobada. Con algo de trabajo es posible probar muchas victorias más garantizadas.
- Casi ciertas victorias - para un juego "suficientemente bueno" sin ningún error tonto (por ejemplo, sobre ELO 2200+) muchas posiciones de ajedrez son victorias casi seguras, por ejemplo, una ventaja material decente (por ejemplo, un Caballero extra) sin una 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 que ganará o al menos dibujará con un 100% de probabilidad.
- Heurística de búsqueda de árboles: con suficiente reconocimiento de patrones, puede enfocarse 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 una posición permitirá una búsqueda mucho más efectiva al enfocar el poder de cómputo en situaciones donde el resultado es más incierto (esta es una extensión natural de la búsqueda de inactividad )
Con la combinación correcta de las técnicas anteriores, me sentiría cómodo al afirmar que es posible crear una máquina de juego de ajedrez "invencible". Probablemente no estemos muy lejos con la tecnología actual.
Tenga en cuenta que es casi seguro que es más difícil probar 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 funciona perfectamente y tendría resultados empíricos que demuestren que nunca perdió (incluidos unos mil millones de sorteos en contra de sí mismo), pero en realidad no tendríamos la capacidad de Pruébalo.
Nota adicional con respecto a 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, tales como:
- Siempre gana en todas las situaciones donde es posible forzar una victoria, sin importar cuán compleja sea la combinación ganadora. Habrá situaciones en el límite entre ganar / dibujar donde esto es extremadamente difícil de calcular perfectamente.
- Explotando toda la información disponible sobre la imperfección potencial en el juego de tu oponente, por ejemplo, infiriendo que tu oponente puede ser demasiado codicioso y jugar deliberadamente una línea un poco más débil de lo normal con el argumento de que tiene un mayor potencial para tentar a tu oponente a cometer un error. Contra los oponentes imperfectos, de hecho puede ser óptimo perder si se estima que tu oponente probablemente no detectará el triunfo forzado y te dará una mayor probabilidad de ganarte.
La perfección (especialmente dado a los oponentes imperfectos y desconocidos) es un problema mucho más difícil que simplemente ser inmejorable.
No sé casi nada de lo que se descubrió realmente sobre el ajedrez. Pero como matemático, aquí está mi razonamiento:
Primero debemos recordar que White tiene que ir primero y tal vez esto le dé una ventaja; tal vez le da a Black una ventaja.
Ahora supongamos que no hay una estrategia perfecta para Black que le permita ganar / empatar siempre. Esto implica que no importa lo que haga Black, hay una estrategia que White puede seguir para ganar. Espera un momento: ¡esto significa que hay una estrategia perfecta para White!
Esto nos dice que al menos uno de los dos jugadores tiene una estrategia perfecta que permite que ese jugador siempre gane o dibuje.
Solo hay tres posibilidades, entonces:
- Las blancas siempre pueden ganar si él juega perfectamente
- Las negras siempre pueden ganar si él juega perfectamente
- Un jugador puede ganar o empatar si juega perfectamente (y si ambos jugadores juegan perfectamente, entonces siempre se estancan)
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.
No se trata de computadoras, sino del juego de ajedrez.
La pregunta es, ¿existe una estrategia a prueba de fallas para nunca perder el juego? Si existe tal estrategia, entonces una computadora que sabe todo, siempre puede usarla y ya no es una heurística.
Por ejemplo, el juego tic-tac-toe normalmente se juega según la heurística. Pero, existe una estrategia a prueba de fallas. Independientemente de lo que mueva el oponente, siempre encontrarás una manera de evitar perder el juego, si lo haces desde el principio.
Entonces necesitaría probar que tal estrategia existe o no para el ajedrez también. Es básicamente lo mismo, solo el espacio de posibles movimientos es mucho más grande.
Para el registro, hay computadoras que pueden ganar o empatar en las checkers . No estoy seguro si lo mismo podría hacerse para el ajedrez. La cantidad de movimientos es mucho mayor. Además, las cosas cambian porque las piezas se pueden mover en cualquier dirección, no solo hacia adelante y hacia atrás. Creo que aunque no estoy seguro, ese ajedrez es determinista, pero hay demasiados movimientos posibles para que una computadora determine actualmente todos los movimientos en un tiempo razonable.
Por supuesto, solo hay 10 en el poder de cincuenta posibles combinaciones de piezas en el tablero. Teniendo eso en mente, para jugar a cada compilación, necesitaría hacer menos de 10 para la potencia de cincuenta movimientos (incluidas las repeticiones, multiplicar ese número por 3). Entonces, hay menos de diez en el poder de cien movimientos en el ajedrez. Solo elige aquellos que conducen al jaque mate y estás listo para ir
Sé que esto es un poco abultado, pero tengo que poner mi valor de 5 centavos aquí. Es posible que una computadora, o una persona para el caso, finalicen cada juego de ajedrez en el que participe, ya sea en una victoria o en un punto muerto.
Para lograr esto, sin embargo, debe conocer con precisión cada posible movimiento y reacción, y todo lo demás, hasta llegar a todos y cada uno de los posibles resultados del juego, y para visualizar esto, o para hacer una manera fácil de analizar esta información, piense en es como un mapa mental que se bifurca 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 bretheren. Presentarlo en este señorío requeriría muchos recursos, especialmente si lo hicieras en papel. En una computadora, esto tomaría posiblemente cientos de datos de Terrabytes, ya que tendría muchos movimientos repetitivos, a menos que hiciera que las ramas regresaran.
Sin embargo, memorizar tales datos sería poco plausible, si no imposible. Hacer que una computadora reconozca el movimiento más óptimo para llevar a cabo (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 ese número de conclusiones ganadoras contra la pérdida de conclusiones, y eso requeriría 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, podría hacerse, sin embargo, ninguna persona podría hacerlo. Tal tarea requeriría 30 de las mentes más brillantes hoy en día, no solo en ajedrez, sino en ciencia y tecnología informática, y tal tarea solo podría completarse en una (póngalo completamente en perspectiva básica) ... extremadamente extremadamente hiper computadora súper-duper ... que posiblemente no podría existir durante al menos un siglo. ¡Sera hecho! Solo que no en esta vida.
Se ha demostrado para el juego de damas que un programa siempre puede ganar o empatar el juego. Es decir, no hay opción de movimientos que un jugador puede hacer que obliguen al otro jugador a perder.
Los investigadores pasaron casi dos décadas atravesando los 500 mil millones de posibles puestos de damas, por cierto, que todavía es una fracción infinitesimalmente pequeña del número de puestos de ajedrez. El esfuerzo de los inspectores incluyó a los mejores jugadores, quienes ayudaron al equipo de investigación a establecer las reglas del juego en el software que clasificaba los movimientos como exitosos o fallidos. Luego, los investigadores permitieron que el programa se ejecutara, en un promedio de 50 computadoras por 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 humanos para ganar el campeonato mundial de damas en 1994.
Sí, puedes resolver el ajedrez, no, no lo harás pronto.
Simplemente podría resolverse, 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 que el "mejor" movimiento esté disponible. Luego, según el próximo estado, lo hacemos nuevamente. Por lo tanto, 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 un duro tiempo calculando eso.
Solo estoy 99.9% convencido de que el tamaño del espacio de estado hace que sea imposible esperar una solución.
Claro, 10 ^ 50 es un número imposiblemente grande. Llamemos al tamaño del espacio de estado n.
¿Cuál es el límite en la cantidad de movimientos en el juego más largo posible? Como todos los juegos terminan en un número finito de movimientos, existe tal límite, llámalo m.
Comenzando desde el estado inicial, ¿no puedes enumerar todos los n movimientos en O (m) espacio? Claro, toma O (n) tiempo, pero los argumentos del tamaño del universo no abordan directamente eso. O (m) el espacio podría no ser mucho. Para O (m) space, ¿no podría también rastrear, durante este recorrido, si la continuación de cualquier estado a lo largo de la ruta que está atravesando conduce a EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin o BlackMayWinOrForceDraw? (Hay un enrejado dependiendo de a quién le toca el turno, anota cada estado en la historia de tu recorrido cruzado con el enrejado).
A menos que me esté perdiendo algo, ese es un algoritmo O (n) time / O (m) space para determinar en cuál de las posibles categorías se puede encontrar el ajedrez. Wikipedia cita una estimación de la edad del universo en aproximadamente 10 ^ 60 ° tiempos de Planck. Sin entrar en un argumento cosmológico, supongamos que queda mucho tiempo antes del calor / frío / la muerte del universo. Eso nos deja con la necesidad de evaluar un movimiento cada 10 ^ 10a. Veces de 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 de manera optimista que con una implementación súper buena que se ejecute en la parte superior de la línea presente -o-prevenido-no-cuántica-P-es-un-subconjunto-de-la tecnología de NP que podríamos esperar evaluar (tomar una un solo paso adelante, categorizar el estado resultante como un estado intermedio o uno de los tres estados finales) estados 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 tales computadoras o aproximadamente una por cada átomo en mi cuerpo, junto con la capacidad de recopilar sus resultados.
Supongo que siempre hay algo de esperanza en una solución de fuerza bruta. Podríamos tener suerte y, al explorar solo una de las posibles jugadas de apertura de los blancos, ambos eligen uno con un fanout mucho más bajo que el promedio y otro en el que el blanco siempre gana o gana o tira.
También podríamos esperar reducir la definición de ajedrez y persuadir a todos de que todavía es moralmente el mismo juego. ¿De verdad necesitamos pedir posiciones para repetir 3 veces antes de un sorteo? ¿De verdad necesitamos hacer que la fiesta de despedida demuestre la capacidad de escapar de 50 movimientos? ¿Alguien siquiera entiende lo que pasa con la regla de pase pasivo ? ;) Más en serio, ¿realmente tenemos que obligar a un jugador a moverse (en lugar de robar o perder) cuando su único movimiento para escapar de un cheque o un punto muerto es una captura de pase ? ¿Podríamos limitar la elección de las piezas a las que se puede promover un peón si la promoción deseada que no es reina no conduce a un control inmediato o jaque mate?
Tampoco estoy seguro de cuánto permita cada acceso basado en hash de computadora a una gran base de datos de los últimos estados del juego y sus posibles resultados (que podrían ser relativamente factibles en el hardware existente y en las bases de datos finales existentes) podría ayudar a reducir la búsqueda antes. Obviamente, no puede memorizar toda la función sin O (n) almacenamiento, pero podría elegir un número entero grande y memorizar que muchos finales enumerando al revés de cada posible (o incluso no fácilmente demostrable imposible, supongo) estado final.
Sí , en matemáticas, el ajedrez se clasifica como un juego determinado, lo que significa que tiene un algoritmo perfecto para cada primer jugador, esto se ha comprobado que es cierto incluso para el tablero de ajedrez infinate, así que un día probablemente un AI de quantum encuentre 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 hay ajedrez cuántico, donde no hay pruebas de matemáticas de que esté determinado el juego http://store.steampowered.com/app/453870/Quantum_Chess/
y ahí está el video detallado sobre el ajedrez cuántico https://chess24.com/en/read/news/quantum-chess