¿Puede haber un algoritmo de ajedrez perfecto?

15

Los algoritmos de ajedrez actuales van alrededor de 1 o tal vez 2 niveles por un árbol de posibles caminos dependiendo de los movimientos del jugador y del oponente. Digamos que tenemos el poder informático para desarrollar un algoritmo que predice todos los movimientos posibles del oponente en un juego de ajedrez. Un algoritmo que tiene todos los caminos posibles que el oponente puede tomar en un momento dado dependiendo de los movimientos de los jugadores. ¿Puede haber un algoritmo de ajedrez perfecto que nunca pierda? ¿O tal vez un algoritmo que siempre ganará? Quiero decir, en teoría, alguien que puede predecir todos los movimientos posibles debe ser capaz de encontrar una manera de derrotar a todos y cada uno de ellos o simplemente elegir un camino diferente si cierto lo llevará a la derrota ...

editar-- Cuál es mi pregunta realmente. Digamos que tenemos la potencia informática para un algoritmo perfecto que puede jugar de manera óptima. ¿Qué sucede cuando el oponente juega con el mismo algoritmo óptimo? Eso también se aplicará en todos los juegos de 2 jugadores con un número finito (muy grande o no) de movimientos. ¿Puede haber un algoritmo óptimo que siempre gane?

Definición personal: un algoritmo óptimo es un algoritmo perfecto que siempre gana ... (no uno que nunca pierde, sino uno que siempre gana)

algorithms turing-machines John Demetriou
fuente
1
vea también cuál es la complejidad computacional de la resolución de ajedrez, tcs.se
vzn
Esta pregunta se basa en varios conceptos erróneos. Primero, las computadoras de ajedrez miran más allá de una o dos capas por delante: incluso hace cinco años en una computadora portátil normal, los programas de ajedrez bastante comunes miraban 15-16 capas por delante y 25+ en líneas críticas. En segundo lugar, la definición de "perfecto" como "siempre gana" no se puede lograr, como se muestra en las respuestas. Tercero, los motores de ajedrez no "predicen" movimientos: calculan y juegan movimientos que son buenos contra cualquier respuesta posible.
David Richerby

Respuestas:

13

Su pregunta es similar a la vieja castaña: "¿Qué sucede cuando una fuerza irresistible se encuentra con un objeto inamovible?" El problema está en la pregunta misma: las dos entidades descritas no pueden existir en el mismo universo lógicamente consistente. Su algoritmo óptimo, un algoritmo que siempre gana, no puede ser jugado por ambos lados en un juego donde un lado debe ganar y el otro debe, por definición, perder. Por lo tanto, su algoritmo óptimo como se define no puede existir.

Kyle Jones
fuente
3
Bueno, puede, por ejemplo, un algoritmo que permite que gane el primer jugador. Esto significaría que jugar primero tiene una ventaja. O tal vez el algoritmo óptimo solo permite que gane el segundo jugador. Esto le daría una ventaja al segundo jugador. La tercera posibilidad es un algoritmo que permite a uno de los jugadores forzar siempre un empate, aunque no garantiza una victoria (porque, como quiere saber el OP, esto es lo que sucede, por ejemplo, si ambos jugadores juegan la misma estrategia ganadora , si no hay ventaja en jugar primero o segundo).
Realz Slaw
3
@Realz Bueno, sí, si cambias la definición de un "algoritmo óptimo", entonces puedes probar lo que quieras. Usé la definición que el interrogador nos pidió que usáramos.
Kyle Jones
Esta es la respuesta que estaba tratando de sacar de la gente. No puede haber un algoritmo que siempre gane porque es un juego de 2 jugadores, por lo que no hay forma de que el algoritmo pueda funcionar porque ambos jugadores pueden tener el mismo algoritmo, por lo que al menos uno de los dos se ve obligado a no ganar (perder o empatar) . Le hice la misma pregunta a mi maestro y nos llevó mucho tiempo hablar con él para llegar a esta conclusión
John Demetriou
3
@JohnDemetriou El problema es que esa conclusión es incorrecta . El ajedrez no es un juego simétrico debido a la ventaja del primer jugador: es completamente posible que exista un algoritmo óptimo que permita que las blancas jueguen y ganen, ¡pero las negras no pueden usar ese algoritmo por la simple razón de que ella no es blanca!
Steven Stadnicki
También es posible, debo señalar, que ir primero no es realmente una ventaja y que en realidad hay un algoritmo que siempre permite que las negras ganen contra la mejor jugada de las blancas, pero debería ser inmediatamente obvio que no hay un algoritmo que siempre pueda permitir que uno gane, ya sea negro o blanco. Es por eso que la gente habla del "mejor resultado posible", porque "ganar de ambos lados" es trivialmente imposible.
Steven Stadnicki
23

En primer lugar, creo que los algoritmos de ajedrez se ven más de 2 capas, aunque no consideran todas las posibilidades diferentes; podar el árbol de búsqueda es muy importante para evitar la explosión combinatoria en el número de movimientos posibles.

Para un juego como el ajedrez, hay tres posibilidades en cuanto a la identidad del ganador: el jugador 1 tiene una estrategia ganadora, o el jugador 2 tiene una estrategia ganadora, o ambos jugadores sortean en condiciones óptimas. No se sabe cuál es el caso del juego de ajedrez. Sin embargo, dado que el ajedrez es un juego finito, existe un algoritmo informático, que consiste en una mesa muy grande, que juega al ajedrez de manera óptima.

Por supuesto, tal algoritmo no sería práctico. Pero para algunos juegos más simples, se ha determinado el "valor" del juego (qué jugador gana, si lo hay), y se ha ideado un algoritmo óptimo. Tal juego se conoce como un juego resuelto .

El tema matemático que trata (lo que se conoce como) juegos combinatorios es la teoría de juegos combinatorios . Los matemáticos han desarrollado un método recursivo para determinar el valor de un juego dada la gráfica del juego, que incluye todas las posiciones y movimientos permitidos. Debería poder encontrar una descripción de este algoritmo en la entrada de Wikipedia o en las notas de clase sobre el tema.

Yuval Filmus
fuente
sí, de hecho, pero estaba tratando de responder a cualquier respuesta con otra pregunta, ¿qué sucede cuando ambos jugadores juegan con un algoritmo óptimo? ¿Qué sucede si un jugador encuentra una manera de vencer el algoritmo óptimo?
John Demetriou
11
@JohnDemetriou Cuando ambos jugadores juegan de manera óptima, obtendrás algún resultado. Ese resultado se llama el valor del juego. Si el ajedrez es blanco, eso significa que nada de lo que el negro podría hacer podría vencer a un jugador blanco jugando de manera óptima. Las blancas efectivamente tienen un libro enorme (o es capaz de producir el movimiento de dicho libro de manera computacional) que contiene un contador perfecto para cualquier movimiento que las negras puedan hacer en cualquier situación posible que se desarrolle desde el comienzo del juego. Por cierto, chillax en los signos de interrogación. Uno por oración es suficiente.
rrenaud
Pido disculpas por los signos de interrogación. Es la forma en que escribo en general. ¿Qué pasa si el ajedrez es la victoria más óptima? ¿Si el blanco y el negro tienen el mismo libro y los mismos contadores? ¿Qué pasará entonces?
John Demetriou
1
@JohnDemetriou "Óptimo" significa "el mejor posible". Si las consecuencias matemáticas de las reglas del ajedrez son que lo mejor que un negro puede hacer contra un blanco óptimo es el empate (o incluso solo puede retrasar la victoria del blanco el mayor tiempo posible), entonces el algoritmo óptimo para el negro es aquel que logra eso, y es capaz de ganar contra la mayoría de los oponentes no óptimos.
Ben
1
@JohnDemetriou Es posible que haya un algoritmo que siempre gane como blanco ; obviamente, ese algoritmo no siempre podría ganar como negro por las razones que ya se han descrito (porque estaría jugando contra sí mismo). Incluso es posible que resulte que el ajedrez negro 'gana' jugó perfectamente, y que hay un algoritmo que garantiza una victoria para las negras contra cualquier oposición. Si te refieres a 'un algoritmo que siempre gana desde cualquier lado', entonces sugiero usar esa terminología; 'óptimo' ya tiene un significado bien definido.
Steven Stadnicki
8

En primer lugar, los buenos algoritmos de ajedrez miran más allá de 1 o 2 niveles. En lugar de utilizar la búsqueda de árbol ingenua, realizan una poda alfa-beta para reducir el número de opciones a considerar. Tenga en cuenta que para aperturas y juegos finales, se utiliza una gran base de datos de movimientos, ya que tiene un mejor rendimiento que la búsqueda de árbol, que se utiliza en el medio del juego.

A la pregunta: lo que preguntas, creo, es "¿El ajedrez tiene solución ?". Hipotéticamente, lo es, aunque las opiniones varían sobre si este resultado será alcanzable en el corto plazo. Las damas se resolvieron en 2007, por ejemplo, pero tienen muchas menos posiciones (alrededor de la raíz cuadrada del número en el ajedrez). Vea el artículo de Wikipedia para más información.

Por cierto, las mejores IA actuales de ajedrez casi siempre derrotan o empatan con campeones mundiales; así que, aunque actualmente no es perfecto, ¡los algoritmos son bastante buenos al menos!

sjmeverett
fuente
6

En principio, el ajedrez se puede resolver como cualquier otro juego. Como las otras respuestas han señalado, sin embargo, no se espera que esto suceda pronto.

Editar: se ha señalado en los comentarios que [1] es un engaño, así que omita el resto de esta respuesta.

Dicho esto, ha habido algunos desarrollos recientes en esta dirección. [1] afirma haber demostrado que la apertura de ajedrez llamada King's Gambit está resuelta : solo hay un movimiento que atrae a las blancas, mientras que todos los demás movimientos de apertura conducen a una victoria para las negras. Tenga en cuenta que [1] no exploró el árbol del juego en profundidad, pero solo afirma que estos resultados se mantienen con alta probabilidad.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

Peter
fuente
1
Muy interesante artículo de hecho!
Paresh
Entonces ese no es un algoritmo óptimo. Me pregunto si alguna vez puede existir un algoritmo óptimo (si tenemos el poder de cómputo)
John Demetriou
1
Correcto, y considerando su definición de "algoritmo óptimo" como un algoritmo que siempre gana, dicho algoritmo no puede existir para ambos jugadores, Blanco y Negro. Además del árbol de juego más grande (pero finito), no hay nada especial sobre el ajedrez en este sentido en comparación con otros juegos como, por ejemplo, Hex, para el que ya se conoce la solución: si el primer jugador usa la estrategia óptima (conocida) para jugar Hex , entonces el primer jugador siempre gana, sin importar qué algoritmo use el segundo jugador.
Peter
El artículo del Rey Gambito resuelto resultó ser un engaño. Tenga en cuenta que el artículo comienza "El 31 de marzo, el autor del programa Rybka, Vasik Rajlich, y su familia se mudaron de Varsovia, Polonia, a un nuevo departamento en Budapest, Hungría. Al día siguiente, a pesar del bullicio de las cajas y el entorno. hasta el teléfono y las conexiones a Internet Vas, accedió amablemente a la siguiente entrevista "- en otras palabras, esto fue el 1 de abril ...
Joe K
-1

Si es posible ganar siempre una partida de ajedrez o no, depende de las reglas del juego. Sin embargo, hay una técnica / algoritmo llamado Minimax (para más detalles, consulte https://en.wikipedia.org/wiki/Minimax ). El algoritmo consiste en tratar de predecir qué jugador tiene la ventaja en diferentes escenarios con una función recursiva. Aquí hay una explicación clara de cómo funciona esto con un juego más simple: Tic-tac-toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13 .

Luke el geek
fuente
Aunque otra respuesta no se refiere explícitamente a minimax, algunos sí se refieren a enlaces que eventualmente conducen a ellos o la poda alfa-beta, un algoritmo para implementar minimax de manera más eficiente. ¿Qué agrega esta respuesta que aún no se ha dicho?
Lagarto discreto
-3

agregará otra respuesta que enfatice el espacio de estado masivo, no realmente conceptualizado en la pregunta o señalado en otras respuestas. debe estar en desacuerdo con su premisa:

Digamos que tenemos el poder informático para desarrollar un algoritmo que predice todos los movimientos posibles del oponente en un juego de ajedrez.

vea la información sobre el artículo de 1950 de Shannons, "Programación de una computadora para jugar ajedrez", que introdujo el campo de los juegos / algoritmos de ajedrez basados ​​en computadora y que su análisis básicamente no ha cambiado y sigue siendo sólido (incluso por la posterior revolución de la computadora y ley de Moores ). estima el número de movimientos. Es absolutamente astronómico. en el rango de "nunca dentro de hardware concebible incluso con avances revolucionarios imprevistos".

Es un hecho psicológico documentado [3], probablemente uno de los muchos prejuicios psicológicos [2], que los humanos tienen problemas para entender números de esta magnitud. vea también el pensamiento contrafactual . [4] mientras que las supercomputadoras calculan problemas masivos, no está indiscutiblemente dentro del rango de cualquier supercomputadora que se construya actualmente o que se pueda construir alguna vez. (y muchos aficionados al ajedrez dirían que esta "explosión combinatoria" en las posibilidades de movimiento / posición es un aspecto intrínseco del "sabor" de los juegos que parece haber sido diseñado intencionalmente en el juego milenario).

por lo tanto, el ajedrez es fundamentalmente diferente a algunos juegos que tienen espacios de estado "solucionables" más pequeños [de los cuales hay algún estudio en ciencias de la computación y teoría de juegos, etc.] y en algunos aspectos clave no pueden evaluarse dentro de ese marco.

101234×10791081

ahora, dicho esto, es concebible (pero poco probable) que pueda haber ideas teóricas sobre el juego que podrían usarse para podar sustancialmente el espacio de búsqueda. eso ha sucedido desde 1950, pero no de una manera fundamentalmente innovadora.

ver también

[1] ¿Cuál es la complejidad computacional de resolver ajedrez? Tcs.se

[2] sesgos humanos en el juicio y la toma de decisiones

[3] Estudiantes de psicología publican investigaciones sobre conceptualización de números

[4] pensamiento contrafactual

vzn
fuente
Bueno, en teoría, mi pregunta comenzó cuando digamos que tenemos el poder de la computación, combinamos la mitad de las computadoras del mundo para trabajar como un clúster para el blanco y la otra mitad para el negro ...
John Demetriou
1
amigo, se mantiene incluso si conecta cada supercomputadora que ahora existe o existe. su pregunta entonces equivale a "en teoría, si la teoría era falsa ..." la teoría (incluida la física) básicamente dice que obviamente no puede calcular (mucho) más caminos de los que hay átomos en el universo, ahora o nunca en el futuro. .
vzn
3
Es cierto, pero la pregunta comienza con: DIGAMOS QUE TENEMOS EL PODER DE COMPUTACIÓN, ¿puede hacerse esto? Esta es la pregunta real, si tenemos el poder, ¿puede haber un algoritmo?
John Demetriou
+1 por afirmar el hecho de que es físicamente imposible lograr el poder computacional necesario para resolver el ajedrez exactamente. Además, no sé por qué todos los -1 con esta respuesta, creo que es justo y agrega una buena visión a las otras respuestas.
Alejandro Piad