Suele decirse del ajedrez que es tan complejo que el número de posibles partidas es mayor que el número de átomos en el universo. En este vídeo de Numberphile se examinan esas cifras y cómo se ha llegado a ellas. El valor más utilizado suele ser el llamado Número de Shannon, calculado por el propio padre de la teoría de la información: 10^120. El número de átomos en el universo es más o menos 10^80, de modo que la diferencia de 50 órdenes de magnitud es sencillamente abismal.
Comentarios
Mira que hay probabilidades, y a mi me tocan siempre en las que pierdo. Qué mala suerte tengo.
PD: El Go tiene aún más posibilidades.
#2 El Go tiene bastantes mas, concretamente en algun punto entre 2 x 10^170 (Tromp, 2007) y 10^360 (Allis, 1994), depende del tipo de analisis y de que normas uses (superko, ko japones,...).
De hecho la estimacion de 10^360 es usando el mismo metodo que Shannon para el ajedrez.
#2 #12 Por cierto, si usas el metodo de Hardy te sale un minimo que cercano a (10^10)^171 (Tromp and Farnebäck).
#12 gnugo es una burrada, traga CPU más que los simuladores de vuelo con las físicas entre los movimientos.
En cambio es más "fácil" jugar al ajedrez contra un motor.
#24 GNUgo tampoco traga tanto.
El problema en realidad no esta tanto en la diferencia de tamaños entre el ajedrez y el Go (que es inmensa), sino en que el Go carece de una "funcion de evaluacion". Es decir, que dado un punto de la partida el ordenador no es capaz de evaluar de manera rapida y precisa si va ganando blanco o negro y por cuanto.
Por lo que no podemos usar las tecnicas tradicionales de busqueda en arboles (como min-max o alpha-beta), si no que tenemos que recurrir a tecnicas de simulacion como Monte Carlo Tree Search, que simulan millones de partidas aleatorias para cada movimiento (para intentar estimar como de bueno es).
#30 Oye, me interesa lo de Monte Carlo Tree Search. Me gusta simular cosas con Monte Carlo y nunca he intentado nada en análisis de ramas. (a ver como programo eso en Excel, que soy lento y malo de cojones)
#36 No, las posiciones de Go siguen sin poderse evaluar, y es precisamente por eso por lo que se utiliza MCTS (que es para el problema que se diseño).
Lo que se hace en Go es simular millones (incluso decenas de millones) de veces lo que resta de la partida y ver quien gana, cosa curiosamente que funciona bastante bien para elegir el siguiente mejor movimiento, pero que funciona como el culo para saber quien va ganando y por cuanto (de forma precisa).
Lo que se llama una 'funcion de evaluacion' no puede depender nunca de los siguientes movimientos, ya que es algo que tienes que aplicar en el limite de tu arbol para hacer frente al llamado 'efecto horizonte' de los algoritmos de busqueda, y ademas tiene que ser muy preciso para permitirte hacer podas eficientes. En Go las heuristicas que mencionas, no se hacen para evaluar si no para ajustar las probabilidades de los movimientos candidatos. Se hace lo que se llama "pattern matching", es decir tienes una base de datos de patrones locales basados en conocimento experto que te sugiere movimientos candidatos (a los que aumentas la probabilidad de simulacion) y movimientos que debes evitar (a los que se la bajas) para tu algoritmo MCTS... pero aun asi tienes que simular cada movimiento candidado millones de veces (fase de 'playout'). Esto es un enfoque radicalmente diferente al de un algoritmo de ajedrez tradicional.
En ajedrez, donde si que hay una funcion de evaluacion, dada una posicion se puede calcular una puntiacion muy precisa solamente basadandose en las piezas que quedan y sus posiciones (lo que se llama 'desarrollo').
Y lamenteblemente tampoco (no para mi, que si no me quedaba sin tema de tesis doctoral :P), los programas de Go actuales no tienen ninguna posibilidad de ganar a un jugador profesional en 19x19, ni siquiera a un jugador amateur de muy alto nivel. Los ultimos resultados de la UEC cup (http://entcog.c.ooco.jp/entcog/densei/eng/index.html) son partidas con 3-4 piedras de handicap (y la diferencia entre profesionales es muy pequeña). Lo que si que se ha ganado es en 9x9, donde los profesionales no se han dedicado a estudiarlo tanto, cosa que esta cambiando precisamente porque los ordenadores empezaron a ganarles.
Mientras que en ajdrez a dia de hoy el tema mas candente es precisamente cuanta ventaja tienen que darle los ordenadores a los grandes maestros humanos para tener una partida interesante.
Por cierto, el enlace que pones precisamente dice lo que estoy diciendo yo... que no hay una funcion de evaluacion para el Go y que por eso no se puede utilizar tecnicas tradicionales de busquda que fue lo que se intento primero (aunque todo en un bonito ingles de investigacion, "have seen less success" -> "van como el mismisimo culo"). Solo se han podido utilizar en problemas de vida y muerte (en entornos cerrados) que tienen arboles pequeñisimos en comparacion, donde se usa una tecnica llamada df-PN, "depth first proof number search".
#32 No es tan dificil en http://mcts.ai/ tienes varias implementaciones y toda la teoria.
#55 Es que no soy programador ni se programar, apenas he programado alguna chorrada en VBA en Excel, nada del otro mundo, mejor dicho nada (creo que 40 lineas o 50 por aplicación)
Solo he aplicado mis muy básicos conocimientos de lógica y he armado "oraciones espartanas" que tienen sentido, solo eso. Alguna que otra simulación de Montecarlo o aplicación para Inversiones o Finanzas.
#40 Voy a documentarme, desde hace un año le estoy dando caña a la estadística, pero el camino muy largo. Por ahora llevo estadística básica (vamos, uso de distribuciones para modelar) y con ello desarrollar mis propios modelos de evaluación en finanzas, cosa que realmente con la Normal sacas casi todo, pero quiero profundizar más, voy poco a poco.
#57 MCTS es un algoritmo algo avanzado, pero si ya has hecho simulaciones de Monte Carlo no te deberia resultar mucho mas difícil.
Básicamente vas creando un árbol a la vez que guardas los resultados de las simulaciones, y el nodo que te toca expandir y simular lo eliges con una formula (normalmente UCB - Upper Conficende Bound). Con lo que aparte de la simulación de Monte Carlo (especifica del dominio al que quieras aplicar el algoritmo) solo tienes que implementar una estructura de datos en forma de árbol, recorrerla aplicando una formula matemática y propagar hacia atrás los resultados de la simulación. Suena bastante mas confuso de lo que es, pero en realidad la parte difícil es la simulación.
Eso si, la parte teórica que justifica que puedes hacer eso para resolver el "multi-arm bandit problem" eficientemente y porque UCB elige los nodos miniando el ¿arrepentimiento? (regret) de forma optima (asintoticamente y en ausencia de conocimiento sobre el dominio) si que son difíciles... pero si confiás en que la teoría es correcta, no tienes que preocuparte.
Dicho sea de paso MCTS usando UCB (mucho mas eficiente que escoger todos los nodos uniformemente) se llama UCT... que es la implementación del algoritmo que mas se utiliza. Pero si quieres profundizar mas en las distintas formas de elegir el nodo a simular te recomiendo este articulo http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf
#58 vale, gracias. En cierto modo es lo que me imaginé, ir simulando por parte y que vaya avanzando en el árbol. (Bueno, que te entendí sólo la mitad de todo lo que escribiste)
A ver, autoexplicado a modo tonto, montas el modelo en un árbol y la aplicación ira simulando y guardando resultados según avance por el árbol. Imagino que en cierto modo sería fácil montar un árbol pequeño en Excel (programa que domino), pero creo que necesitaría más poder de cálculo para el ordenador. Ahora, no me veo andando por simulaciones con árboles grandes o complejos, creo que será cuestión de probar. Leeré lo que enviaste, lástima mi nivel de inglés. Gracias.
#32 Los lenguajes similares a LISP son idóneos para esas cosas.
#30 Lo que dices sobre la evaluación de una posición de una partido de Go era cierto hace unos años, pero actualmente está bastante más avanzado, y más que no poder evaluar una posición, el problema es que una posición puede requerir evaluar varias decenas siguientes o incluso centenares. De hecho, se tiende a usar una combinación de varias heurísticas (en realidad, como con el ajedrez) (https://en.wikipedia.org/wiki/Computer_Go#Design_philosophies). Todavía no llega (y posiblemente no llegue) al nivel de "maestría" en ajedrez, pero se ha avanzado mucho en la ultima década y ahora un ordenador puede enfrentarse a un jugador profesional de categorías medias-inferiores con cierta posibilidad de éxito.
#2 Menos mal que alguien a mentado al Go y así baja los humos a los ajedrecistas.
#50 Siempre pierdes ¿verdad?
#62 En los dos 😰
Y yo sigo rompiéndome el coco pensando cómo cuernos colorados lo hizo Iznogud para dar mate en dos jugadas en la post-conclusión de La isla de los gigantes, usándose sólo a sí mismo (era el alfil) y a Dilá (era el caballo). Sí, como le dijo Dilá, tenía un genio "alfiladísimo", pero yo sigo dándole vueltas a si pudo hacerlo limpiamente o hizo trampas. Conociendo a mi amo, es más que probable que las hiciera, pero quiero averiguar si pudo NO hacerlas.
Y otra cosa: La reina blanca (de Alicia en el País del Espejo), ¿por qué es tan rematadamente idiota? No sólo se mueve por el tablero como un pollo sin cabeza, huyendo cuando nadie la amenaza, sino que, después del banquete, desaparece ¡en un movimiento ilegal! (os recuerdo que en la novela, se está dando jaque al rey. Cuando el rey está en jaque, los únicos movimientos permitidos son para sacar al rey del jaque, pero la reina blanca huye sin que su movimiento proteja al rey en absoluto). Un autor como Carroll, que no ponía por casualidad ni las comas, ¿de quién se estaba acordando con una reina tan lela?
Y por último: no pienso volver a jugar al ajedrez con el juego del Ipad. En el Battle Chess, los movimientos de la máquina también eran instantáneos, pero con la animación, ganabas un tiempo de respiro. Aquí, no. Tú te tiras un cuarto de hora pensando, y él contesta al instante. Acabé intentando jugar a su misma velocidad. Gané (no os penséis que soy Kasparov; estaba en un nivel bajo de dificultad), pero no os cuento qué manera de sudar y qué dolor de cabeza.
#10 ¿Qué tiene que ver todo eso con la noticia?
#16 También son partidas posibles del ajedrez: las partidas en cómics, en novelas y en mi vida personal.
#17 Se te va la pelota
#10 La partida más corta posible es de solo dos movimientos y el mate lo dan las negras. Se llama mate del loco y es porque solo alguien que juegue como un loco haría las jugadas necesarias para que puedan hacérselo... En la versión del mismo mate para blancas, el número de jugadas es de tres, mientras que el mate del pastor se da en cuatro jugadas.
Para más información...:
https://es.wikipedia.org/wiki/Mate_del_loco
Pero bueno, sé que todo esto te importará poco, solo lo comento como curiosidad...
Pon 10^120 y 10^80 en la entradilla.
#3 Y si no contamos las que, con una jugada perfectamente visible se hace jaque mate, pero haciendo otra jugada se pueden alargar hasta "el infinito" permitiendo por el camino "infinitas" partidas posibles ¿habrá mucha diferencia?
#4 No se pueden alargar hasta el infinito. Si repites tres movimientos son tablas.
#5 El infinito iba entre comillas, porque me refería a un número muy grande.
#5, son tablas si uno de los jugadores lo solicita (me he enterado de hecho a raíz del meneo). Si no, pueden seguir jugando. En el meneo se supone que en tales casos se piden las tablas.
#21 No, eso es en el caso de no capturar ninguna pieza pero haciendo movimientos diferentes. Si los dos jugadores hacen los mismos movimientos tres veces son tablas y punto. Es típico de cuando se queda un rey sólo con un peón y cosas así.
#39, he buscado en Google y lo de la repetición de 3 posiciones también son a petición.
De acuerdo al reglamento de la FIDE, la partida es tablas si el jugador que está en juego reclama correctamente, cuando por lo menos por tercera vez la misma posición va a repetirse o acaba de producirse.
https://es.m.wikipedia.org/wiki/Tablas_(ajedrez)
#5 En mi opinión #21 #45 tiene razón, pero matizando más:
Repetir una posición quiere decir que, visualmente, la posición que se presenta es idéntica, pero además que las condiciones son las mismas (turno de juego, posibilidad o no de enroque, y posibilidad o no de captura al paso); también hay que considerar que la posición repetida puede o no presentarse de manera secuencial.
https://es.wikipedia.org/wiki/Tablas_%28ajedrez%29#Triple_repetici.C3.B3n_de_posici.C3.B3n
cc #39
#63 Bueno, a mi me enseñaron eso. Seguramente sea porque cuando se consigue esa jugada normalmente un contendiente está en clara inferioridad con lo que pide tablas enseguida.
#5 ko
#4 Precisamente de eso habla el video, 10^120 es la estimaion de posibles partidas en las que de verdad intentas ganar lo antes posible... (10^10)^50 es la estimacion para cualquier partida legal posible (incluso para las que no intentas ganar).
#14 Pues no entiendo, porque una partida legal se me ocurre que, si se hacen movimientos no ofensivos ni repetitivos, podría durar indefinidamente... ¿no?
#25 No, en ajedrez existen ciertas normas por las cuales una partida acaba en tablas, principalmente la regla de repeticion (https://en.wikipedia.org/wiki/Threefold_repetition) y la regla de los 50 movimientos (https://en.wikipedia.org/wiki/Fifty-move_rule) que evitan que una partida dure infinintamente.
No se usan mucho, pero tampoco son especialmente raras (yo las he usado ambas en campeonatos). De hecho las nombran ambas en el video.
#0 goto #3
He sentido una leve sensación de vérgigo con esos números.
... una pena que no se pueda expresar en campos de futbol.
Me acabó de enterar de que las tablas por 50 movimientos o por repetición son a petición, pensaba que eran automáticas. Así que los videojuegos de ordenador ¡están todos mal! Al menos los que conozco.
#20 #2º Depende de la version del reglamento, en algunas versiones son obligatorias.... ademas son a peticion por cualquiera de los dos jugadores, asi que estan bien, ya que consideran que el ordenador siempre las pide.
Nunca he visto a alguien no pedirlas.
#41, en el ordenador puedes jugar contra humano, y ahí también son tablas automáticas. A veces la repetición de 3 movimientos es con varios de por medio y que los jugadores ni se hayan dado cuenta ni tuvieran pensado pedir tablas. Pero el ordenador mete tablas.
#43 Ciertamente, pero lo dicho la voluntariedad es con las reglas de torneo FIDE (donde existe la "deportividad"), existen variaciones de las reglas para torneos donde puede ser obligatorias.
Tengo la teoría que el ajedrez es como el tres en raya venido a más. Al final cuando se consigan calcular todas las probabilidades se demostrará que ganan siempre las blancas o siempre es tablas.
#27 ¡Me encantan los comentarios de este hilo! Os juntaba a todos en una mesa, proponía tema de conversación y ¡hala! a disfrutar.
Lo digo en serio
#27 #38 En realidad el planteamiento es correcto, es un juego de informacion perfecta con lo cual si conseguimos calcularlo todo (podando inteligentemente) podriamos saber quien gana siempre. Pero como en el ajedrez no se puede pasar, no se puede descartar de que quien empieza puede tener desventaja (como en el juego de Nim)
Resumiendo un poco:
10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000
#31 · 10⁷.
(Te cortaron el comentario).
#23 error. Eso sería para x*10^y.
#33 En este caso la base es 10 por lo tanto tiene razón y es solo colocar ceros.
#33 x = 1.
Cuantas películas posibles existen a 640p??
#19 Depende de la profundidad de color, de la duración de la película y de si incluyes el sonido. ¿Podemos consideramos película todo encadenamiento de imágenes aunque no tengan ningún significado? En caso de ser así cada fotograma tendría 307.200 px (640x480), y si la profundidad de color fuera de 16 bits el número de fotogramas únicos sería 16^307200. Suponiendo que la película va a 24fps y queremos saber cuántas películas hay de 90 minutos exactamente habría 90*60*24*16^307200 posibles películas, es decir aproximadamente 5,9E369910 (al igual que en Excel, aquí la E denota potencia de 10). Si en vez de calcular todas las películas posibles de 90 minutos calculamos todas las películas posibles de cualquier duración entre 0 y 120 minutos (eso sí, suponiendo que todas tienen un número entero de minutos) obtenemos algo más de 4,76*10^369912 películas posibles. Un número un poco más grande que el de partidas de ajedrez
#60, es una paranioa interesante, invita a reflexionar sobre si el número de cosas que pueden pasar es finito.
¿Entre 10^120 y 10^80 no hay una diferencia de 40 órdenes de magnitud (120-80) y no de 50 como dice el artículo?
En perspectiva:
(10^10 )^5 = 10^50
10^10^5 = 10^100.000
El número de átomos aproxidos el universo ~ 10^80
Así, hay 10^100.000 / (10^80) 10 = 99.920 múmero de juegos de ajedrez legales que los átomos en el universo.
#26 No, se te ha ido unos cuantos ordenes de magnitud.
Las partidas de ajedrez son (10^10)^50 = 10^500 y el numero de atomos aproxidos el universo es 10^80, con lo que hay 10^500 / 10^80 = 10^420 partidas legales de ajedrez por cada atomo del universo, una burrada vamos.
#52 Tienes razón en eso. Por ejemplo. no tendría sentido mover un peón hasta que te lo coman.
#52 #53 Hay movimientos que pueden parecer absurdos y no lo son, y jugadas que parecen brillantes y luego, analizando la partida, tenían una respuesta ganadora. Se podrían descontar...
Vaya chasco, yo pensaba que habían corregido esas cifras calculando cuantas de esas partidas podrían tener algún sentido.
#8 ¿Cómo determinas cuáles tienen sentido y cuáles no? Los grandes maestros pueden ganar partidas con movimientos aparentemente sin sentido. El "sentido" en ajedrez es simplemente hacer tablas, o ganar (y en tal caso no tendría "sentido" perder ninguna partida jugando con las blancas, porque no tendría sentido perder la pequeña ventaja que eso supone).
#48 Vas al detalle, tampoco le estaba pidiendo tanta precisión. Imagina que usas dados roleros para generar partidas: tiras un dado de 16 para decidir que mueves, si no se puede mover, se repite. Luego cuentas el número de posibles movimientos que puede hacer, eliges el dado adecuado, lo lanzas y repites con el otro bando. Piensa que en todas las posibles partidas calculadas del modo que nos proponen caben partidas en la que uno, o los dos jugadores, están empeñados en suicidarse o partidas en las que sólo se mueven los caballos para ir a ejecutar una especie de bailecillo en el centro del tablero: partidas que a pesar de ser posibles no aportan nada al juego.
El universo es infinito.
#54 No se sabe. O bien es finito y tiene un tamaño "medible" o bien es infinito. También puede ser que sea "plano" y tenga un tamaño finito pero continue expandiendose.
¿Quieres elaborar tu opinión?
De todas formas, lo del número de átomos en el universo es irrelevante. ¿Cuantas partículas subatómicas hay en el universo? Podemos hacer una aproximación basandonos en las partículas que conocemos y el universo observable. Pero aun así, también sería irrelevante si el universo fuera infinito o continuara expandiendose.
Me cuesta creer que por ejemplo el Sol no tenga 10^120 atomos. Si deben caber como 10^20 Tierras en el!!!
#9 la función exponencial es muy poco intuitiva. Tu comentario es un ejemplo.
#11 Si solo tienes que poner la cantidad de ceros del exponente.
#9, para que en el sol cupieran todos esos átomos que dices, la Tierra debería de tener 10^80 átomos, y esos son los que se supone que tiene el universo.
Por si acaso,10^80 no es el doble de 10^40 sino muchísimo más. 1000000 es mil veces mil. Etc.
#9 #22 Es lo curioso de la exponencial 10^81 es 10 veces mas 10^80 (acuerdate de la regla de multiplicacion de potencias (con la misma base), se suman los exponentes), por lo que 10^80 no es el doble de 10^40 sino 10^40 veces mas 10^40.
#9 no caben 10^20 tierras en el sol.
De la wikipedia:
Es del orden de 10^5 ~10^6