Base de datos de cada movimiento posible en ajedrez

14

Imagine que hay una base de datos de ajedrez de cada movimiento y posición posibles. Esta base de datos contiene todos los movimientos posibles desde la apertura hasta el final del juego.

Si jugué usando mi intuición contra un motor de ajedrez, puede predecir qué movimiento me hará perder y ganar.

Esto significa que no hay necesidad de un "motor de ajedrez" porque todos los movimientos posibles ya están grabados.

Si existe tal base de datos, tendría las siguientes ventajas:

  • En las partidas rápidas, el motor de ajedrez definitivamente perderá contra la base de datos de movimiento de posibilidad de ajedrez.
  • Podemos saber exactamente qué apertura tendrá más oportunidades de ganar contra los demás.

O si tal base de datos aún no existiera, podríamos tener un cálculo matemático de todos los movimientos posibles desde la apertura hasta el final del juego.

¿Sería posible que tal base de datos exista?

Ahmad Azwar Anas
fuente
55
No, no es posible con ninguna tecnología imaginable.
Tony Ennis
Estoy vagando un rato .. Y todavía no lo creó. Tienes razón. Jajaja
Ahmad Azwar Anas
2
Buena suerte construyendo una base de datos con más bytes que átomos en el Universo
David
Hola, soy nuevo en esta comunidad y soy de MathStack. Solo para compartir que hay menos átomos en el universo que la cantidad de juegos de ajedrez posibles en una partida de ajedrez. Pruebe el número de Shannon ( youtube.com/watch?v=Km024eldY1A ).
Sujit Bhattacharyya

Respuestas:

33

Creo que su pregunta se reduce esencialmente al tema de si es posible "resolver" completamente el ajedrez. Wikipedia tiene un excelente artículo sobre el tema que debería darle una buena visión general.

Para resumir, el número de posibles variaciones de juego en el ajedrez se estima en 10 ^ 120. Este es un número asombrosamente enorme, para comparar, considere que el número de átomos en el universo observable se estima en alrededor de 10 ^ 80 . En otras palabras, si usaras todo el universo observable como tu disco duro, aún necesitarías almacenar 10 ^ 40 combinaciones de juegos de ajedrez en cada átomo , para simplemente almacenarlo todo. No hace falta decir que esto está mucho más allá de nuestras tecnologías actuales y previsibles que la mayoría de las personas consideran que es completamente imposible.

Los finales de ajedrez son considerablemente menos complejos, y hemos llegado a un punto en el que es posible calcular todas las combinaciones posibles para finales de cinco y seis piezas . Estas son típicamente grandes empresas realizadas por investigadores con acceso a supercomputadoras, y las bases de datos finales resultantes son enormes (del orden de cientos de terabytes). Cada vez que se agrega una nueva pieza, el tamaño y la complejidad de los cálculos aumenta exponencialmente, lo que significa que en el futuro previsible, podemos esperar que estos resultados se expandan solo unas pocas piezas.

Daniel B
fuente
ahora me imagino que hay un algoritmo que representa la mesa final del juego .. ^^
Ahmad Azwar Anas
3
@AhmadAzwarAnas Bueno, creo que los simples ya se usan en los motores de ajedrez, y los más completos se agregarán a medida que la tecnología lo permita. En términos de un algoritmo, supongo que podría "comprimir" una tabla final del juego analizándola en busca de patrones y generalizándolos en un conjunto de reglas que claramente conducen a un resultado. Sin embargo, con toda probabilidad, este conjunto de reglas aún sería absolutamente masivo, ya que pequeñas variaciones (como tener oposición o no) pueden cambiar el resultado del juego.
Daniel B
@AhmadAzwarAnas en realidad, ¿por qué no solo un algoritmo para el ajedrez? debe haber un movimiento en cada juego perdido que sea el incorrecto, ¿verdad? es decir, el movimiento antes del cual existía un camino para no perder, independientemente del movimiento de los oponentes, pero después del cual esto ya no es cierto. entonces "todo" que debe hacer el algoritmo es identificar estos movimientos para que pueda evitarlos.
Michael
1
@Michael es más difícil que eso: ¿cómo puedes saber que existe un camino para ganar independientemente de lo que mueva el oponente? en el mejor de los casos, habría uno solo el 50% del tiempo, porque si una persona gana, la otra se ve obligada a perder. En realidad, volvamos a las posiciones iniciales: para que exista un camino más adelante en el juego, debería existir un "camino ganador absoluto" en ese momento. Si descubrimos eso, ¿por qué alguien jugaría más el color perdedor? , sabiendo que independientemente de lo que muevan, ¿perderán? ¿Por qué alguien jugaría más al ajedrez si pudiéramos hacer eso?
user2813274
2
+1 pero tu análisis está mal. Para almacenar una base de tabla, solo necesitas almacenar cada posición, no cada juego posible. Shannon estima que hay aproximadamente 10 ^ 43 posiciones , lo que se compara con aproximadamente 10 ^ 50 átomos en la tierra . Entonces podrías resolver el ajedrez convirtiendo toda la tierra en una computadora .
David Richerby
8

No, no sería posible que tal base de datos exista. Calcularlo requeriría una computadora demasiado grande y el cálculo tomaría tanto tiempo que su computadora no existiría el tiempo suficiente para completar la tarea.

Claude Shannon estimó que hay alrededor de 10 43 posibles posiciones en el ajedrez y su base de datos necesitaría almacenar el resultado de todo esto (esto sería, esencialmente, una base de tabla de 32 hombres ). Sin embargo, se estima que la Tierra contiene solo unos 10 50 átomos , por lo que, incluso si pudiera construir una celda de memoria con solo 10,000,000 de átomos, aún necesitaría una computadora del tamaño de la Tierra para almacenar todas las posiciones.

Pero una computadora tan grande trae grandes problemas. El diámetro de la tierra es de unos 12.800 kilómetros y la luz tarda unos 43 ms en cruzar esa distancia. Eso significa que, si un ciclo de reloj dura más de 43 ms, entonces no solo tiene un sesgo de reloj horrible, sino que diferentes partes de su computadora ni siquiera están en el mismo ciclo de reloj. Evitar esto limita la velocidad de su reloj a aproximadamente 23.5Hz (no GHz o MHz; solo Hz). Incluso si pudiera evaluar completamente una posición en un solo ciclo de reloj, eso significa que su computadora tardaría aproximadamente 4,3x10 41 segundos en completar su tarea. Eso es alrededor de 1.4x10 34 años. Eso es 14 millones de billones de billones de años.

Los astrofísicos creen que el universo se verá radicalmente diferente en 1.4x10 34 años de lo que es ahora. Para entonces, las estrellas habrán dejado de existir hace mucho tiempo e incluso los elementos que no tienen sentido radioactivo habrán sufrido grandes cantidades de desintegración radiactiva. Incluso los protones que forman núcleos atómicos habrán sufrido una importante desintegración radiactiva. Entonces su computadora del tamaño de la Tierra simplemente ya no existirá.

David Richerby
fuente
2
¿Quieres decir que hay una posibilidad?
bpromas
6

Creo que la respuesta de Daniel es excelente (+1) pero de todos modos quiero agregar algunas ideas.

¿Una mesa de 32 piezas realmente reemplazaría a los motores de ajedrez? ¡La respuesta es definitivamente no!

Para jugar un buen ajedrez, se necesita más información que si un movimiento es ganar, dibujar o perder. Por supuesto, una base de datos de este tipo sería inmejorable, pero tampoco superaría a nadie.

Para jugar al ajedrez con fuerza no es suficiente elegir un movimiento no perdedor en cada turno. De los muchos movimientos de dibujo en cada posición, solo unos pocos ejercen una presión real sobre el oponente.

Los motores de ajedrez existentes se fortalecen significativamente al acceder a las bases de tablas. Pero a medida que crecen las bases de datos, el tiempo de acceso se convertiría en un factor prohibitivo mucho antes de usar cada átomo en el universo para la memoria ;-).

Así que creo que su conclusión es incorrecta: una base de datos de este tipo nunca perdería y casi nunca ganaría. No nos diría nada sobre las aperturas, excepto que casi todas son empates. Probablemente podríamos idear nuevos algoritmos para extraer esta base de datos y llegar a conclusiones interesantes sobre todo tipo de posiciones, pero creo que esto no cambiaría el mundo del ajedrez de manera significativa.

BlindKungFuMaster
fuente
Has entendido mal lo que contendría la base de datos. Cada posible movimiento se marcaría como "Si juego esto, mi oponente puede forzar una victoria, haga lo que haga después", "Si juego esto, puedo forzar una victoria lo que haga mi oponente a continuación" o "empate". Por lo tanto, no estarías jugando "movimientos no perdedores en cada turno": estarías jugando victorias forzadas en cada turno, siempre y cuando existiera tal movimiento.
David Richerby
1
Bueno, en realidad entendí exactamente lo que contendría la base de datos ... El punto que estaba tratando de hacer es que en los juegos de ajedrez de alto nivel "¡No hay victorias forzadas!" en más del 90% de los puestos. Y necesita mucha más información que "este movimiento atrae y este movimiento pierde", para llegar realmente a una posición ganadora contra un jugador decente.
BlindKungFuMaster
2
Para dar un ejemplo: en la posición inicial, con toda probabilidad, la única información en la base de datos sería "Todos los movimientos dibujados". Entonces estarías completamente solo. Y si estás completamente solo, ¿cómo consigues una posición ganadora contra un jugador fuerte? La respuesta es: no. Su posición empeorará cada vez más si sigue la única línea de dibujo.
BlindKungFuMaster
No, eso no está bien. Es trivial obtener tu jugada ganadora. Simplemente calcule todos los movimientos posibles desde la posición actual, verifique las posiciones resultantes en el DB y elija una que gane o empate. Por definición, si su posición actual es "usted gana", habrá al menos una en las siguientes posiciones que es "usted gana"; y si su posición actual es "empate", al menos una de las siguientes posiciones será "empate" (y posiblemente algo de "usted gana" si su oponente no juega perfectamente).
Ignacio Calvo el
1
El punto es que la posición actual generalmente no es "tú ganas". Por ejemplo, es muy probable que no haya una victoria forzada en la posición inicial.
BlindKungFuMaster
3

Creo que algún día el ajedrez se resolverá. ¿Por qué? Porque, bueno, no hace mucho tiempo, jugar ajedrez contra una computadora era extraño e impensable. ¿Cómo podrías entrenar una computadora para jugar al ajedrez? Bueno, lo hicieron! (Además, la idea de una computadora era extraña ...) Mi punto es que puede parecer extraño porque nunca la hemos visto o escuchado. No es algo que podamos imaginar fácilmente. Pero la tecnología se está expandiendo a un ritmo exponencial. No me sorprendería si en un futuro próximo (más de 10 años) se resuelve de una forma u otra.

Ryan Orr
fuente
1
El obstáculo para resolver el ajedrez es la cantidad literalmente astronómica de datos que necesitaría clasificar. Shannon estimó que hay aproximadamente 10 ^ 43 posiciones en el ajedrez y que necesitarías almacenar el resultado para cada una de ellas. Para poner esto en perspectiva, la tierra contiene alrededor de 10 ^ 50 átomos , por lo que, incluso si pudieras construir una celda de memoria a partir de 10,000,000 átomos, ¡aún necesitarías convertir toda la tierra en un banco de memoria solo para almacenar el resultado!
David Richerby
1
@DavidRicherby Digamos que el ajedrez es un empate con la mejor jugada. Luego, por cada movimiento blanco, hay una respuesta adecuada para el negro. Para el siguiente movimiento blanco, el negro también tiene una respuesta adecuada, y así sucesivamente. Es concebible que construir tal "árbol de dibujo" requiera mucho menos de 10 ^ 43 posiciones.
Dag Oskar Madsen
44
@DagOskarMadsen Sí, es posible que almacenar el árbol realmente requiera mucha menos memoria (aunque todavía una cantidad astronómica). Sin embargo, la técnica actual para construir tales árboles es hacer un análisis retrógrado desde todas las posiciones finales, lo que requiere construir la base de datos completa de qué hacer en cada posición, como al menos una etapa intermedia.
David Richerby
1
¡Lamento anunciarte que estás equivocado! @DagOskarMadsen Pero si no sabes cómo refutar las respuestas "inadecuadas", ¿puedes realmente afirmar que has resuelto el juego?
David
2

De regreso a la universidad a principios de la década de 1980, leí en un juego jugando texto que si una computadora pudiera planificar, evaluar y ejecutar un movimiento, cualquier movimiento, desde el comienzo del juego hasta todas las conclusiones posibles cada 1/3 de nanosegundo, eso es aproximadamente 3 mil millones de movimientos / segundo, hacer esto por cada resultado concebible llevaría de 10 a los siglos 120 en completarse. ¿Y quién tiene tanto tiempo para esperar?

Otra estadística asombrosa? ¿Obviamente has oído hablar de un googol? ¿No es Google, sino el número? Es de 10 a la potencia número 100. Un 10 seguido de 100 ceros. Ahora imagina el googolplex. Eso es 10 para el googol'th power.

He leído que no hay suficiente de nada en el universo conocido, ni siquiera átomos, para requerir el uso de googleplex. De hecho, incluso el googol es demasiado grande para describir algo. Deberías ver algunas de las asombrosas curiosidades sobre estos números.

Jon
fuente
0

Aunque podría no ser posible realizar ajedrez en una base de datos en este universo, se puede decir que la estructura abstracta del juego existe como un objeto matemático finito. Uno puede razonar al respecto y concluir que tiene un resultado definitivo, aunque es posible que no sepamos qué es eso. Y luego, si lo ve como una matriz, puede hacer preguntas como cuál es el valor propio máximo del ajedrez aproximadamente. De hecho, Platón pensó que los números tienen una existencia real, por lo que creo que diría que el juego de ajedrez existe de la misma manera sublime e inútil.

Pero más prácticamente, me imagino que una computadora cuántica avanzada podría realmente representar esto y resolver el ajedrez. El jurado aún no está al tanto de las capacidades de esta tecnología, pero en principio no puedo ver que sea imposible

Laska
fuente
-1

Sí, creo que sería posible. Pero solo si la base de datos se parecía más a una red neuronal, tomar movimientos que causaron su pérdida y eliminarlos. Ese cálculo se basa en exponer (tener paciencia conmigo) todas las acciones posibles en un juego de ajedrez en el movimiento uno, mover 100 o algo así. Mientras tanto, si nos deshacemos de las repeticiones, ((Ke3 Ke4 Ke3 Ke4) bucle) 10 ^ 120 probablemente podría convertirse en algo así como 10 ^ 70. Eso sigue siendo ridículamente enorme, pero si de alguna manera pudiéramos codificarlo en un plano 4D (lo que creo que es posible) sería un juego de niños.

usuario19889
fuente
2
¡Bienvenido al ajedrez ! Por favor, haga el recorrido mientras lo hace. Su publicación podría ser rechazada porque es más una opinión y menos una respuesta como la esperamos aquí; consulte el artículo del Centro de ayuda Cómo responder .
Glorfindel
2
No soy un jugador de ajedrez, y para que conste, tampoco soy una de las personas que te votaron en contra, pero he leído que hay 10 ^ 43 posiciones diferentes. Solo porque tiene un método que permite filtrar algunos de los datos, ¿por qué supone automáticamente que eso lo hace posible? Creo que está subestimando exactamente cuán concebiblemente debería ser esta base de datos. Esto está mucho más allá del alcance de la tecnología informática moderna que no puedo imaginar que estemos en una trayectoria para que esto suceda incluso dentro de un siglo. Pero bienvenido a SE Chess. (Y bienvenido también, supongo: P)
Joe Majewski