Re: RUBIK Infinito

Posted by RUBIK Transfinito on Dic 31, 2012; 2:20am
URL: http://foro-crashoil.109.s1.nabble.com/RUBIK-Infinito-tp14p72.html

@ KUZNACTI


Vas a tener que traducirme eso porque mi inglés es muy malo. No sea flojo, escribe.


¿¿¿ Te refieres al título del enlace de antes ... ???

¿Cómo puedes vivir en Sudamérica [en realidad, en cualquier parte del planeta que sea] e ignorar la lengua del Imperio ...? Creo que dijiste una vez que no comprendo bien el ideal de los EE UU ... Pero sé el idioma (hay que conocer al enemigo). Tú también deberías dominarlo, ya sea para conocer también a tu enemigo (¿eres chavista?) o a tu supuesto amigo:


WHAT IS IT LIKE TO BE A BAT? = ¿CÓMO SERÍA SER UN MURCIÉLAGO?

Se trata de un ensayo escrito por el filósofo inglés Thomas Nagel y en el que habla del tema de la Consciencia en general y también -especulativamente- sobre QUÉ ASPECTO PODRÍA TENER EL HECHO DE SER NOSOTROS (REENCARNARNOS EN, se se quiere ver así) UN MURCIÉLAGO.

Supe de este ensayo hace muchos años, leyendo la famosa obra de Richard Dawkins titulada EL RELOJERO CIEGO (The Blind Watchmaker). En cierta forma, ese maravilloso libro es mi Biblia. A veces, cuando han llamado testigos de Jehová o mormones a la puerta para dar la vara e intentar convertirme a sus religiones, yo he contraatacado con el libro de Dawkins. Puedo enorgullecerme de haber conseguido como mínimo UNA conversión. Un chico joven que delante de mí se decepcionó del rollo jehovanista que contaba la abuelita que lo acompañaba, y claramente se hizo el propósito de estudiar Dawkins (y por ello también Darwin) a fondo.

Así de insondables son los Caminos del Señor: incluso en el terreno aparentemente más baldío, puede florecer un día la simiente.


En cuanto al tema del AJEDREZ, Kuznacti, está claro que te falta conocimiento del juego y -más grave- también de Matemáticas. Pensaba que un filósofo como tú estaría ducho como mínimo en el segundo tema. Paso a ese apartado ...




Aun soy escéptico en cuanto a que no exista un algoritmo para hacer jaque mate, no solo jaque, con  R+T+A  vs. R+C+C. Además creo que no debe ser muy difícil hacer ese algoritmo para que haga el jaque mate por fuerza bruta con esas condiciones, es decir que aun incluso dudo de la necesidad de una supercomputadora. Hasta me suena a uno de los problemas de programación de los maratones de programación. Lo cual por cierto, ahora que recuerdo, me sorprende que no hayas dicho ni pío, además de tu ultima respuesta al respecto. Desde luego que el número de combinaciones a simple vista es enorme, pero también lo seria que te pusieras a buscar el camino más corto en un grafo completo aleatorio de  64 puntos por poner un numero igual al de las casillas del ajedrez sin aplicar un algoritmo como del Dijsktrak, quiero decir por fuerza bruta.

Espero que no me contestes diciéndome lo complejo que en general es el Juego de ajedrez, con esas pocas piezas la complejidad se reduce muchísimo. Solo soy escéptico no digo que estés equivocado.


-> Entre en la página rusa de problemas de programación. Empecé por la parte de "para principiantes", y resolví un par de problemas que eran *gilipolleces*. No he vuelto a entrar desde entonces, pero está claro que hay que hurgar ahí. Considero la programación una de las Bellas Artes, y yo aspiro a ser artista.

Lo que dices del grafo y demás lo comento a continuación del próximo párrafo tuyo.




Un buen ejemplo seria digamos un grafo mucho más representativo del tablero de ajedrez con cada vértice representando una casilla y cada arista representando que la casilla es vecina de otra. El peso de cada arista es aleatorio. El problema seria como dije anteriormente hallar la distancia más corta entre dos casillas cualesquiera con un algoritmo de fuerza bruta. Creo que la complejidad de ese problema si se podría comparar entonces, guardando las distancias, con la complejidad que tiene tu problema de hacer jaque mate para las piezas del tablero dadas....


-> Discrepo. Un planteamiento estándar bueno para programar el juego del Ajedrez sería como sigue:

Planteamos el juego en abstracto como un inmenso GRAFO -en efecto-, un diagrama arbóreo pero puesto cabeza abajo, y en el que cada *nodo* (¿que es eso de "arista" ...?) representa una posición alcanzable mediante un movimiento legal desde los nodos a los que está conectado. Por simplicidad (para evitar lazos), dibujaremos el grafo desde el nodo inicial (posición de partida) hacia abajo. De cada nodo surgen tantas ramas como movimientos posibles tiene el bando que es mano.

Por ejemplo, del nodo origen (posición inicial) surgen 20 ramitas, correspondientes a los 20 movimientos legales que tiene el Blanco (16 posibles movimientos de peón y 4 posibles de caballo).

Luego, de cada uno de esos nodos, surgen 20 ramitas más correspondientes a los 20 movimientos posibles para el Negro: los mismos que tenía el blanco, i.e. 16 posibles movimientos de peón y 4 saltos de caballo.

etc.

Hay que aclarar que con la convención que tomamos para la notación, habría posiciones "iguales" que aparecerían como nodos distintos en el árbol. Si por ejemplo hacemos

1- P4R, P4R
2- C3AR, C3AR

Llegaríamos a un nodo del árbol. Pero haciendo


1- C3AR, C4AR
2- P4R, P4R

Llegaríamos a la misma posición PERO a un nodo distinto viéndolo así, a fin de mantener el grafo lo más simple posible a nivel conectivo.


Cada turno del Negro o del Blanco se llama MOVIMIENTO. El conjunto de dos movimientos es una JUGADA (por ejemplo un movimiento blanco y la respuesta negra).


El algoritmo a usar no consistiría en "hallar la distancia más corta entre dos casillas cualesquiera con un algoritmo de fuerza bruta", que dice KUZNACTI ...

Lo que KUZNACTI olvida es que nosotros (supongamos que somos las blancas) jugamos, pero luego el Negro responde, y elige hacia qué parte del grafo quiere llevar el juego. Es como si navegáramos por un río que se va bifurcando (o tri-furcando, o múltiple-furcando, ...), y a cada encrucijada, uno de los adversarios elige qué camino tomar ... Cada uno puede tomar la mitad de las decisiones, con lo que la ruta final qe se sigue (partida) es un destino forjado por ambos.

La forma clásica de tratar esto es la siguiente:

Necesitamos una FUNCIÓN DE EVALUACIÓN, que asigne a cada posicón (nodo) un VALOR o EVALUACIÓN (por eso se llama "función" de ídem). Ese valor o "nota" se asigna teniendo en cuenta el material y los aspectos de la posición. Si sale un valor 0.0, entenderemos que las fuerzas están igualadas. Si sale un valor positivo, entenderemos que las blancas están mejor. Si es negativo, entenderemos que las negras están mejor ...

Evidentemente, el Ajedrez es un JUEGO DE SUMA CERO (como puede acabar siéndolo el Peak Oil), porque lo que gana uno, es inevitablemente a expensas del otro. Todo lo que gane el Blanco, lo pierde el Negro, y viceversa. Es una *complementariedad* perfecta, y no hay forma de que ambos ganen la partida. Además, las unidades de evaluación se intenta que correspondan con la unidad material mínima: el PEÓN. Así por ejemplo, si para una posición determinada la Función de Evaluación arroja un 1.0 como resultado, significa que teoría que las blancas están mejor que las negras, y esto en tal grado como si, siendo todo los demás (posición, etc.) igual, tuvieran las blancas UN PEÓN DE VENTAJA. Naturalmente, puede ser que ese peón no sea "material", sino sencillamente una combinación de ventajas posicionales: estar más desarrollado,  tener más espacio, tener el rey bien protegido, etc. Pueden salir evaluaciones con decimales, como 3.25, que equivaldría a "tres peones y cuarto".

En general, se entiende que la salida inicial da a las blancas algo así como 0.5 peones de ventaja.

Si tuviéramos una Función de Evaluación perfecta, no haría falta explorar el Árbol de Posibilidades (Grafo). Bastaría con evaluar cada una de las posiciones alcanzables desde la inicial (a lo sumo unas pocas docenas) y hacer la jugada. Ese simple método nos llevaría inevitablemente a la Victoria o bien a un empate (si el adversario se defiende perfectamente y supuesto que el Ajedrez sea un tablas teóricas, como es plausible). Pero repito: necesitaríamos una Función de Evaluación *perfecta* ...

En la realidad, lo que tenemos es muy imperfecto: podemos construir una funcion de evaluación simple sencillamente sumando el material de que dispone cada bando. Aplicaríamos en principio una Tabla Bruta, bastante simple: Un PEÓN vale 1; un CABALLO 3 unidades o peones; un ALFIL 3.5 peones; una TORRE 5.25 peones; una REINA 9 peones; un REY ... Infinito, salvo que sea el borbón, que valdría menos 100 elefantes.

Esa tabla u otra parecida sirve, ya que no se puede hablar de Valores absolutos de las piezas: son contextuales, dependen de la posición; en ciertas posiciones un caballo puede "trabajar" más que una dama y valer por ello mucho más que ella. A fin de cuentas, el objetivo es matar al Rey enemigo, no ganar material. Aun así, los valores giran más o menos entorno a lo de antes, y las evaluaciones intuitivas de los distintos campeones van por ahí. Es posible estimar esos valores en base a la movilidad bruta media de una pieza en un Tablero vacío: así por ejemplo, una Torre siempre podrá alcanzar 14 cuadros en tal situación, mientras que un caballo dominará 8 si está centralizado; 4 si está en un borde; y tan poco como 2 si está en una esquina. Este tipo de enfoque permite calibrar más o menos el valor "teórico" de cada pieza.

En todo caso, una función de evaluación digna de tal nombre habría de tener en cuenta el material y algunos factores *posicionales*. Cosas como ...

CONTROL DEL CENTRO
PROTECCIÓN DEL REY PROPIO
CALIDAD DE LA ESTRUCTURA DE PEONES
DEBILIDAD O FUERZA DE CASILLAS BLANCAS O NEGRAS
ACTIVIDAD DE LAS DISTINTAS PIEZAS
DESARROLLO GENERAL
ESPACIO
"ENERGÍA" DE LA POSICIÓN Y POSIBILIDADES DINÁMICAS LATENTES EN ELLA (por que en el tablero ... hay energía, ja ja ja)

etc.

Con todo esto y otras cosas que se nos ocurran (potencialmente una infinidad de conceptos estratégicos) podemos pergeñar una FUNCIÓN DE EVALUACIÓN.

Como no será perfecta, nos veremos obligados a explorar el Grafo hasta la profundidad que permita la potencia de nuestra máquina y el tiempo disponible por jugada.

Idea es ir asignando puntuaciones (PESOS) a los nodos del grafo. Si el número es grande (positivo), es que para las blancas es bueno. Si el número es pequeño (negativo), es que es bueno para las negras.

Ahora bien, en cada posición a la que lleguen las negras, las blancas tratarán de hacer la mejor jugada disponible para ellas mismas a largo plazo ... y viceversa. Y de esta apreciación es de donde sale el llamado ALGORITMO MINIMAX:

Supongamos que hemos explorado el árbol hasta una profundidad de 10 estratos (movimientos), alcanzando a ser posible una posición estática, en la que no hay cambios a medio hacer, no estamos en jaque ni nada por el estilo ... a partir de los nodos que hay ahí (seguramente muchos), hay que retroceder o retrogradar ... En principio consideraremos el que tenga valor más alto (si somos las blancas), un MÁXimo ya que queremos llegar a *ese*, y suponemos que es uno en el que hemos acabado de jugar y por ende le toca a las negras). Eso lo hacemos para cada uno de los nodos "madre", es decir, del estrato anterior, correspondientes a la posición *desde* la que jugaron las blancas. Ello nos deja con una posición destino por nodo desde el que se jugo. Si partíamos de N nodos, tenemos N nodos hijos máximos (los "hermanos menores" son elimnados). Pero ahora, de esos N nodos origen hay que tomar el MÍNimo *porque* las negras precisamente habrían elegido, bajo juego óptimo, llegar ahí para perjudicarnos ... Y es iterando esto que se va hacia atrás: máximo-mínimo, máximo-mínimo-máximo-minimo ... De ahí el nombre de MIN-i-MAX o MINIMAX abreviadamente.

Una FUNCION DE EVALUACIÓN, el algoritmo MINIMAX y la exploración lo más exhaustiva posible del GRAFO es el corazón de un algoritmo convencional básico.

Esto se puede combinar con una PODA (prunning) para hacerlo más eficiente/rápido. Por ejemplo, no tiene mucho sentido explorar ramificaciones del árbol a partir de un nodo en el que supuestamente un bando regala alegremente su reina a cambio de nada ... En realidad hay que escarbar un poco ahí por  si se tratara de un *sacrificio* útil para algo, como a veces sucede en Ajedrez.

En todo caso, es posible *podar* muchísimo el árbol de posibilidades. En lugar de tener los típicos 37 movimientos legales típicos (promedio) en el Medio Juego, podemos quedarnos con tan poco como 6, lo cual es vastamente más manejable (es preferible que el trabajo crezca como una potencia de 6 que como una potencia de 37, evidentemente), por motivos relacionados con la FUNCIÓN EXPONENCIAL, de esos que los economistas no comprenden y que les impiden captar que es imposible el crecimiento infinito en un planeta finito.

Téngase en cuenta también que hay una especie de COMPROMISO entre la complejidad de la FUNCIÓN DE EVALUACIÓN y la rapidez de nuestro programa:

Si la función de evaluación es compleja (y por ende más perfecta), necesitaremos profundizar menos en el árbol o Grafo. No necesitaremos una exploración tan exhaustiva (con una función de evaluacion *perfecta* sólo necesitaríamos profundizar UN estrato: y nos diría directamente qué movimiento es el mejor). Ahora bien, la funcion de evaluación en realidad nunca será perfecta, y cuanto más compleja sea, MÁS LENTO será el proceso de evaluarla en cada nodo a medida que exploramos el árbol ... Una función "más precisa", que permita hallar líneas de juego igual de buenas evaluando la mitad de nodos, pero que gaste 4 veces más tiempo en evaluar cada nodo, es una elección peor que la función de evaluación más imperfecta que exige mirar doble nodos pero gastando 4 veces menos tiempo en cada uno (y por lo tanto la mitad de tiempo globalmente). ESTO HAY QUE TENERLO MUY EN CUENTA.

A efectos prácticos, se estima que hay unas 10^120 partidas de Ajedrez posibles, y unas 10^50 posiciones posibles.

En la práctica se ha comprobado que los programas que funcionan por fuerza bruta (lo cual incluye el caso en que hacen "prunning", que sólo es una heurística) tienen una fuerza que es proporcional al número de estratos o capas que son capaces de profundizar; es decir, CUÁNTOS MOVIMIENTOS o semiJUGADAS PUEDEN VER. Además, esa relación es casi totalmente lineal, y con coeficientes conocidos:

Grosso modo, un programa capaz de profundizar 10 movimientos (i.e. 5 jugadas, siendo cada una un movimiento blanco y una respuesta negra) tendría 200x10 = 2000 puntos ELO de fuerza. Esto se cumple con muy gran exactitud.

Cuando Deep Blue le ganó a Kasparov en Abril del '97, era capaz de evaluar 200,000,000 de posiciones por segundo, con un factor de ramificacion promedio en cada nodo (tras la necesaria poda) de aproximadamente 6. Eso le permitía profundizar en los 3 minutos disponibles por turno una cantidad de estratos igual a:


180 segundos x 200,000,000 de posiciones = 3.6*10^10 posiciones evaluadas


y ahora

log(3.6*10^10) / log(6) = 13.56587 estratos


Lo cual corresponde a una fuerza de juego aproximada de

200 puntos ELO/estrato * 13.56587 estratos = 2713 puntos ELO


Lo cual es nivel de Campeón del mundo ...

Cierto que Kasparov se aproximó (y acabó superando, algunos dicen que debido a la "inflación" de las puntuaciones) la barrera de los 2800 puntos ELO, pero aun así:

*** La máquina no se pone nerviosa.

*** No se cansa, desmoraliza o deja impresionar.

*** Le da igual ir ganando o perdiendo.

*** Analiza incluso las posiciones más enrevesadas SIN ERRORES.

etc.


Y se acabó imponiendo, de forma bastante previsible. Es más, con la Ley de Moore en la mano, se podía haber estimado que eso que no ocurrió en 1996 (Kasparov batió a la versión primigenia de Deep Blue, que corría sobre una plataforma menos potente) sí que iba a suceder en 1997 debido a la velocidad del nuevo computador de IBM.




Creo que la complejidad de ese problema si se podría comparar entonces, guardando las distancias, con la complejidad que tiene tu problema de hacer jaque mate para las piezas del tablero dadas....


-> Kuznacti, es en cosas como ésta donde se te ven limitaciones de comprensión ... Evidentemente, la posición inicial del Ajedrez es un CASO PARTICULAR de problema de DAR MATE como se pueda.


Quizá un ordenador *rapidísimo* (digamos que quizá 10^100 veces más rápido que los actuales) podría informarnos tras unos segundos que en realidad el Ajedrez es ...

VICTORIA TEÓRICA para las Blancas: Mate en -como mucho- 497 movimientos.

EMPATE TEÓRICO (lo más probable), bajo juego perfecto por ambos bandos.

VICTORIA TEÓRICA para las Negras, porque ya en la posicion inicial las Blancas están en zugzwang (término alemán que denota la obligacion de jugar en una posicion tan desfavorable que lo mejor sería quedarse quieto para no perjudicarse: pero en Ajedrez el movimiento es un derecho Y una obligación que no se puede pasar). Esto es POSIBLE pero totalmente inverosímil, a mi modo de ver.

En todo caso, cualquier posición simplificada, de finales o lo que esa, no es más que un subgrafo del inmenso grafo inicial del Ajedrez, y se presta a ser tratado con los mismos métodos.

Ahora bien, hay posiciones que admiten un tratamiento técnico, y hay una inmensa mayoría que son intratables de manera "mecánica". Nos vemos obligados a explorar el árbol y coger lo que podamos, sin tener garantías (ni mucho menos) de jugar óptimamente. De hecho, computacionalmente el Ajedrez o las Damas son peores aún que los problemas NP-completos ... Pertenecen a una categoría denominada p-espacio difícil.

La TEORÍA DE FINALES abarca libros y libros ... Los finales simples los puede dominar hasta un niño. Algunos intermedios requieren una técnica difícil; y los hay diabólicamente complejos (con varias reinas y peones, por ejemplo). Kasparov dijo que los finales en general son la pequeña capilla de fugas musicales y minuetos del ajedrez ... Un difícil Arte cuyo dominio viene lentamente para algunos y nunca en absoluto para muchos otros. Que un ordenador *entienda* la IDEA de un final es todavía imposible, y la dificultad de programar esa parte del juego (que se presta poco al enfoque por fuerza bruta) es una de las causas principales de que el ajedrez computarizado sufriera un relativo atasco durante décadas.

Fue el advenimiento de las hash tables para los finales, y sobre todo la llegada de ordenadores muchísimo más rápidos lo que cambió todo eso.

Hasta hace todavía relativamente poco  tiempo era posible burlarse incluso de los programas más potentes montando una POSICIÓN INICIAL en la que uno se quedaba con el rey blanco *desnudo* y los 8 peones, aunque eso sí: se disponían los peones blancos y negros respectivamente en:

a4, b3, c4, d3, e4, f3, g4, h3 [blancos]

y

a5, b4, c5, d4, e5, f4, g5, h4 [negros]


para ganar, las Negras sólo necesitan sacrificar un caballo o alfil para abrir un boquete en esa muralla y luego irrumpir con sus piezas ... pero hasta hace no muchos años, los ordenadores no veían eso, porque el mate del rey blanco caía más allá de su HORIZONTE de visión. Ahora sí que lo hacen, aunque para ello tienen que estar acercándose al límite de tablas de las 50 jugadas.

En cambio, un niño, CONSCIENTE, pensaría que puede abrir un agujero en la pared y luego entrar con su reina, despejar de peones, entrar con otras piezas, y matar al blanco.

Es decir, los ordenadores siguen siendo -en temas generales- tan estúpidos como siempre, sólo que su velocidad tremenda les permite producir performance artificial más que satisfactoria en ciertos ámbitos. Para ellos el Ajedrez es una contabilidad. No hacen más que "contar bolitas" ... MUY RÁPIDO.