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

109

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.

Desbordado
fuente
1
+1: excelente tema. Sin embargo, creo que esto debería ser wikiificado como lo demuestra la variedad y el volumen de respuestas.
IAbstract
1
"¿Crees que he señalado algo que aún no está probado satisfactoriamente"? ¿Qué ha señalado que no se haya probado formalmente?
S.Lott
2
¡ack! ¿Cómo puede haber 20 respuestas diferentes a una pregunta en blanco y negro? (sin juego de palabras).
Peter Recore
5
A mí también me sorprende la cantidad de personas que publican sus respuestas especulativas sin saber que la respuesta de hecho ha sido determinada matemáticamente - respuesta en el sentido de que se ha demostrado que el ajedrez tiene una solución - simplemente no es práctico calcularla.
DJClayworth
3
Me recuerda el chiste sobre el ordenador perfecto para jugar al ajedrez. Jugando con las blancas, piensa y piensa y piensa y luego ... ¡renuncia!

Respuestas:

104

"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.

S.Lott
fuente
22
Todos los finales con 6 piezas o menos han sido enumerados y resueltos. Consulte tablebase y bitbase aquí: en.wikipedia.org/wiki/Tablebase . Por ejemplo, ¡hay un final KQNKRBN donde se requieren 517 movimientos para forzar un mate! Pero el número total de partidas de ajedrez ronda los (10 ^ (10 ^ 50)).
HTTP 410
2
Tener un guión para ganar es una cosa. Enumerado exhaustivamente es una cosa diferente. De cualquier manera, la información es perfecta, todo se sabe, el juego es determinista por definición.
S.Lott
11
@RoadWarrior: en desacuerdo. El azar se aplica al clima. Dios lanza los dados. El azar no se aplica al ajedrez, por definición. El ajedrez tiene información completa. El clima tiene efectos cuánticos, no puede ser completo.
S.Lott
3
Lo que dificulta el pronóstico del tiempo son los factores caóticos no lineales, no los efectos cuánticos. Con suficiente poder de cómputo y conocimiento, en teoría podríamos crear un pronóstico del tiempo "correcto".
HTTP 410
3
@monojohnny: Las reglas prohíben tres repeticiones de la misma posición. El ajedrez es simplemente finito. Es grande pero finito.
S.Lott
72

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 : debe haber un algoritmo perfecto para el ajedrez, al menos para uno de los dos jugadores.

Artelius
fuente
2
+1, esa es una forma genial de explicarlo. ¡No puedo creer que nunca pensé en eso!
Zifre
2
¿Por qué las negras no tienen una estrategia perfecta implica que las blancas tienen una estrategia perfecta? ¿Qué hay de que ambos jugadores no tengan una estrategia perfecta? Si su implicación fuera cierta, ¿no sería cierto para cada juego de 2 jugadores, lo que significa que cada juego tiene una estrategia perfecta?
John M Naglick
8
@john: Debido a que el ajedrez tiene información perfecta y no elementos aleatorios (a diferencia de muchos, muchos otros juegos de 2 jugadores), la única forma en que es posible que no exista una estrategia perfecta para las negras sería si las blancas pueden forzar una victoria a pesar de cualquier intento de negro, en otras palabras, si existe una estrategia perfecta para el blanco.
Dave Sherohman
2
En realidad, esta lógica no siempre se cumple, pero es cierto en este caso.
BlueRaja - Danny Pflughoeft
4
@john "por qué tanta discusión aquí" - porque algunas personas no saben la respuesta, pero publican aquí de todos modos.
DJClayworth
30

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.

BCS
fuente
6
"No lo harás pronto" es un poco subestimado. Además del límite de la duración esperada del universo, tienes un problema de almacenamiento: el número de estados en el Ajedrez supera con creces los 500 mil millones de mil millones de damas; de hecho, excede el número de partículas del universo.
Michael Dorfman
30
"[...] de hecho, supera el número de partículas del universo". Mientras no exceda el número de estados de las partículas en el universo, todavía hay esperanza ;-)
Carsten
1
¿Qué pasa cuando el programa que siempre obliga al oponente a perder es jugar contra sí mismo ????
John Demetriou
1
@BCS hmm, ¿qué pasa si hay una predicción en la que si estoy jugando como segundo jugador y el otro está usando la misma heurística que yo, entonces siga esta heurística para ganar y si el primer jugador tiene una heurística similar? ?
John Demetriou
1
lo que estoy diciendo es que si hay un algoritmo perfecto y ambos jugadores lo tienen, habrá un número indefinido de probabilidades de que el algoritmo pueda cambiar para que sea perfecto
John Demetriou
15

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.

ypnos
fuente
Entonces, ¿quién tuvo el impulso de rechazar mi respuesta? ¿Tiene algo de malo? ¿Quieres ponerte al frente?
ypnos
@ypnos, no voté en contra de tu respuesta en absoluto. Solo comenté para decir que no debes dejar que los votantes en contra al azar te desanimen. Has ganado 30 repeticiones y solo has perdido 1. Además, +1;)
mmcdole
1
Varias razones para el voto negativo. 1) Se sabe que existe un algoritmo para resolver el juego, es solo que el algoritmo no es práctico de calcular usando cualquier tecnología concebible. 2) Resolver el juego NO implica que exista una estrategia a prueba de fallas. Tic-tac-toe está resuelto, pero no hay una estrategia para el segundo jugador que evite una pérdida.
DJClayworth
2
"Esta no es una pregunta sobre computadoras, sino solo sobre el juego de ajedrez". Bueno, la ciencia de la computación no se trata de computadoras. Son solo una herramienta. La informática funciona sin ordenadores.
Janus Troelsen
1
Es, en realidad, una pregunta sobre computadoras, ya que la pregunta es si podría existir una Máquina de Turing (= Computadora) que resuelva el ajedrez.
SDwarfs
14

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.

HTTP 410
fuente
3
Vamos. Tienes que pensar en el problema de otra manera. No pienses en la cantidad de juegos, porque las transposiciones y los algoritmos alfa-beta y todo eso reducen enormemente eso. Piense en posiciones del tablero (10 ^ 60) o combinaciones de piezas de ajedrez (100 millones). Con Quantum Computing, es trivial.
lkessler
2
Alpha-beta en este contexto (resolver ajedrez) requeriría una función de evaluación perfecta. Lo mismo ocurre con las posiciones del tablero y las combinaciones de piezas. No tenemos una función de evaluación perfecta, por lo que la computación cuántica no nos ayuda.
HTTP 410
1
Siempre que pienso que algo es "trivial", y estoy seguro de que nadie lo ha hecho, también estoy seguro de que me he equivocado al menos una vez.
Dean J
2
@lkessler: Las posiciones de la junta no cuentan toda la historia. Al menos se necesita algo de historia del juego para el enroque o las capturas al paso o el empate debido a la falta de captura o movimiento de peón, y toda la historia para empate por repetición. Además, dado que fue un resultado de investigación notable recientemente para una computadora cuántica al factor 15, yo diría que nada es trivial con la computación cuántica en este momento.
David Thornley
2
A modo de comparación aquí, si puede generar todas las posiciones de ajedrez posibles, puede forzar trivialmente cualquier cifrado con una clave de 128 bits, ya que 10 ^ 46 es aproximadamente 2 ^ 152 o 2 ^ 153. Hay excelentes razones para pensar que esto es imposible antes de la muerte por calor del Universo.
David Thornley
9

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.

Cybis
fuente
8

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.

Franco
fuente
9
"¿Sabías que las ventas de discos de discoteca aumentaron un 400% en el año que finalizó en 1976? Si estas tendencias continúan ... ¡AAY!" - Disco Stu
Jeremy Friesner
2
Es probable que la ley de Moore (la potencia informática se duplica cada 18 meses) falle alrededor de 2015. O el diseño del procesador de la computadora tendrá que ser radicalmente diferente. Así que 2080 no es un objetivo realista.
Philip Smith
3
@Philip: Las velocidades de reloj del procesador de las computadoras de escritorio han aumentado solo ligeramente desde 2003, y las mejoras desde entonces han sido principalmente un aumento de la memoria caché y múltiples núcleos. Dado que un procesador de 3 GHz tiene un ciclo de reloj en el tiempo que tarda la luz en moverse 4 pulgadas / 10 cm, no se puede esperar que la velocidad del reloj aumente indefinidamente. Además, el paralelismo suele ser difícil. Proyectar un aumento exponencial durante cincuenta años cuando comenzó a romperse hace siete años no parece una apuesta segura.
David Thornley
1
@David: todo eso es cierto. Pero pierde el punto. Si reduce la mitad del tamaño de los componentes del chip, los electrones se hacen el doble a la misma velocidad de reloj. Esto es lo que alimenta la ley de Moore.
Philip Smith
3
@Philip: La reducción a la mitad, por supuesto, no puede continuar para siempre. Un átomo de silicio tiene aproximadamente un cuarto de nanómetro de diámetro y la fabricación de chips ya se ha reducido a decenas de nanómetros. Además, a niveles cuánticos, las partículas obedecen a reglas estadísticas, no reglas absolutas, por lo que es necesario mover suficientes electrones a la vez para invocar la ley de los grandes números. Hasta ahora, la ley de Moore ha estado en algún lugar entre una ley y una profecía autocumplida, pero eso terminará bastante pronto.
David Thornley
7

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

BlueRaja - Danny Pflughoeft
fuente
4
Técnicamente, la regla de los cincuenta movimientos, como la repetición de tres movimientos (que también limita las cosas, hay un número finito de posiciones posibles, por lo que multiplicar ese número por tres nos da un límite superior) no causa un empate. Más bien, le da a cualquiera de los jugadores la oportunidad de reclamar un empate. Normalmente, el jugador perdedor lo hará, pero no es obligatorio. Por tanto, el siguiente es un juego totalmente legal: 1. Cc3 Cc6 2. Cb1 Cb8 3. Cc3 Cc6 4. Cb1 Cb8, repetido para siempre. Y si no me equivoco, no se ha refutado que ese no es el resultado de dos algoritmos perfectos que juegan como blanco y negro.
Lenoxus
6

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.

Bill el lagarto
fuente
5

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.

Kibbee
fuente
1
Se puede hacer, pero ¿se puede hacer en una computadora que probablemente veamos alguna vez?
BCS
1
Probablemente no en nuestra vida. Toda la investigación realmente interesante en el campo se está realizando en el juego Go. :)
Bill the Lizard
IIRC la mayoría de los niños de 6 años pueden estar en cualquier computadora en Go.
BCS
2
@BCS: Ya no. Los mejores programas de Go están superando a los jugadores de nivel dan (profesional) ahora.
Bill the Lizard
1
@BlueRaja: Eso fue en 2008. No sé cuál es el récord actual, pero MoGo ha vencido a los profesionales con 6 y 7 piedras en un 19x19. ireport.cnn.com/docs/DOC-214010
Bill the Lizard
5

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.

Jason Jackson
fuente
Así es como se gana a las computadoras de hoy en el ajedrez. Mañana será mejor. Sin embargo, estoy de acuerdo contigo en que Blondie24 es fascinante.
Bill the Lizard
Votado de nuevo. Esta publicación no merece una puntuación negativa.
Cybis
Desafortunadamente, el problema del juego de ajedrez es demasiado grande para que funcione el aprendizaje automático. Nunca pudieron conseguir un programa de aprendizaje de ajedrez para ni siquiera jugar de forma novicia sin cometer errores. Las heurísticas son mejores. Pero Brute Force fue incluso mejor. El campo del aprendizaje automático solo aprendió de su fracaso con el ajedrez.
lkessler
Los programas de ajedrez no cometen errores a corto plazo y los mejores programas juegan mejor que los campeones del mundo. Creo que la última versión de Rybka de 64 bits tiene una clasificación de 3200 ELO
Alex
5

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.

Robert Gould
fuente
Esto no es teoría de juegos
BlueRaja - Danny Pflughoeft
4
Técnicamente, es teoría de juegos combinatoria.
Anaphory
5

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

Jon Smock
fuente
5

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!

lkessler
fuente
3

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.

mikera
fuente
Tener oponentes imperfectos no es un problema real. Esto hace que el jugador perfecto gane / empate (sea cual sea el resultado perfecto) en menos movimientos. Un movimiento óptimo en cada posición es siempre mejor o igual a los otros movimientos posibles (por definición). Entonces, un movimiento subóptimo le permite a su oponente alcanzar un estado final óptimo (ganar / empatar) antes o incluso permite forzar un mejor resultado. Por ejemplo, si las negras siempre perderían si las blancas juegan a la perfección, es posible que las negras ganen, si las blancas juegan solo una jugada subóptima. Pero sí, esto debería aumentar un poco la complejidad del análisis.
SDwarfs
@Stefan: los oponentes imperfectos son un gran problema si te preocupas por un juego óptimo . En particular, puede concebir situaciones en las que sea preferible realizar una jugada perdedora (es decir, una jugada en la que un oponente perfecto definitivamente le ganaría) si sabe que la probabilidad de que su oponente cometa un error es suficientemente alta.
mikera
En mi opinión, el juego óptimo significa lograr el mejor resultado posible sin riesgo. Tu oponente es probablemente "débil", pero cuando juegas esa jugada perdedora , desafortunadamente puede jugar una buena jugada por accidente. Preocuparse por los oponentes que no son óptimos solo es relevante si solo se puede elegir entre movimientos perdedores en los que uno de ellos tiene mayores posibilidades de cometer un error por parte del oponente (de juego subóptimo) que lleva realmente a un empate o una victoria.
SDwarfs
1
Esa no es la definición habitual de óptimo en la teoría de juegos. Óptimo generalmente significa maximizar el resultado esperado . En cuyo caso, un jugador óptimo aceptará algún riesgo siempre que obtenga un mejor resultado en promedio .
mikera
En ese caso, ¡tienes toda la razón!
SDwarfs
2

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.

Joel Coehoorn
fuente
De hecho, la cita es correcta. Los programas analizan todos los movimientos posibles para ambos lados en la posición actual y utilizan la heurística para encontrar un buen movimiento para impulsar el juego en la dirección de una posición favorable para la computadora.
Bill the Lizard
1
No, no miran todos los movimientos posibles. Usan una heurística de movimiento nulo para podar el árbol.
Alex
2

"¿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

poligenelubricantes
fuente
1
Siendo un jugador de ajedrez bastante decente y habiendo estudiado el problema extensamente a lo largo de los años, estoy 99.9% seguro de que la estrategia perfecta en el ajedrez para ambos jugadores da como resultado un empate (lo mismo que se ha demostrado con las damas). También hay evidencia de que a medida que aumenta la fuerza del jugador, también lo hace el porcentaje de empates.
mikera
2

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.

Ben Gartner
fuente
2

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.

Salomón
fuente
1

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

Doug McClean
fuente
1
Tu m = 5898. Las reglas de ajedrez de la FIDE definen que tienes que mover un peón o tomar una pieza (algo que cambia irreversiblemente el juego) al menos cada 50 movimientos (llamada la regla de los 50 movimientos) o uno de los jugadores puede reclamar un empate. Se ha calculado que el juego más largo posible es de 5898 movimientos, si ambos jugadores cooperan y reclaman un empate lo antes posible. No tiene sentido seguir jugando, si ambos jugadores pueden reclamar un empate. Si un jugador nota que pierde, puede reclamar el empate, dando el mismo resultado. Ver: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs
1
Nota: m = 5898 es el número de "movimientos". El número máximo de medios movimientos es (118-3) * 100 + 3 * 99 = 11797. Puedes encontrar la prueba aquí (¡alemán!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs
1

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.

MrDeeJayy
fuente
1

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!

SDwarfs
fuente
0

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.

E Dominique
fuente
5
El movimiento perfecto se decide mediante la estrategia 'minmax': es el movimiento que maximiza la puntuación mínima posible (dados todos los movimientos posibles que podría hacer el oponente). O para decirlo de otra manera, se supone que el oponente también juega a la perfección.
Nick Johnson
Sin embargo, este es un punto interesante. ¿Podría surgir una situación en la que una respuesta a la mejor jugada posible lo ponga en desventaja si su oponente no realiza la mejor jugada posible? ¿Qué implicaciones tiene esto?
Nona Urbiz
No soy matemático ni muy buen jugador de ajedrez; También asumí que, en teoría (si se conociera todo el árbol del juego), la respuesta es "sí". Sin embargo, ahora que mencionas este problema [la elección del otro jugador], ¿significa esto que el sistema es potencialmente impredecible? ¿Hay un punto medio en el juego en el que el otro jugador podría forzar una desventaja? ¿Se parece un poco al hecho de que el perceptrón (red neuronal) puede aprender 'O' y 'Y' pero nunca puede comprender 'XOR'? ¿Es el ajedrez un ejemplo de sistema 'caótico'? FWIW, en mi humilde opinión, creo que la respuesta parece ser 'no sé' en este punto.
monojohnny
@Nona Por definición, ese movimiento sería el mejor movimiento. No hay ninguna suposición.
piccolbo
@piccolbo: Mejor, uno de los mejores movimientos. Hay posiciones en el ajedrez donde múltiples movimientos dan como resultado el mismo resultado (ganar, empatar o perder en el mismo número de movimientos).
SDwarfs
0

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.

Philipp Claßen
fuente
-1

, 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

Dhia Hassen
fuente
-2

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

Alex
fuente
-3

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.

Desarrollador de IA
fuente