Tampilkan postingan dengan label curiosidades. Tampilkan semua postingan
Tampilkan postingan dengan label curiosidades. Tampilkan semua postingan

Jumat, 18 November 2011

Caballerosidad deportiva mal entendida


En ajedrez a veces existe algo que se malinterpreta como caballerosidad deportiva, como jugar limpio, aunque en realidad es solamente una exageración a conductas deportivas que se interpretan de forma equivocada. Hace unas pocas semanas, Navara, el GM checoslovaco, jugaba con el GM Moiseenko, en la Copa Mundial 2011, cuando se presentó una situación anómala. Jugaba Navara y aparentemente tocó el rey y su alfil, prácticamente de forma simultánea. Su rival advirtió al juez y después de unos minutos de discusión parece que quedó claro para Moiseenko que Navara no había querido realmente tocar a su monarca y se le permitió hacer la jugada del alfil. En caso de que el juez hubiese decidido en contra de Navara, éste hubiese perdido la partida inmediatamente pues habría perdido una pieza. La partida continuó y Navara llegó a una posición ganadora. Mate en un par de jugadas... Pero no lo ejecutó. ¿Qué hizo? Ofreció el empate, porque se sentía mal por la situación y discusión anterior. ¿Hizo bien? ¿Hizo mal? Los árbitros le concedieron a Navara y a Moiseenko, unos días después, un premio especial por "fair play".

De acuerdo a las propias palabras de Navara: "no sé quién tenía la razón". Navara sintió que el match no debía decidirse por esta situación anómala o por una protesta sin suficiente evidencia. No quería además ser acusado de pasar a la siguiente ronda de forma ilegal y por ello ofreció el empate. A la postre el GM checoslovaco pasó a la siguiente ronda, eliminando a Moiseenko.


Pero este caso no es único. Malakhov, en el Campeonato Individual Europeo de hace unos pocos años, contra Azmazparashvilli, éste último cambió su jugada y esto le permitió coronarse campeón de Europa. Cabe decir que Azmazparashvilli se sintió mal con su proceder y en algún momento le ofreció tablas a su rival, el cual no acepto (de acuerdo a Geurt Gissen, el prestigiado árbitro internacional, en su columna de Chesscafe.com).

Pero Tim Krabbé, que lleva un registro de todo género de situaciones curiosas en ajedrez, lo cual daría a muchos libros del tema, y que tiene un sitio web, es de la opinión de que: "Apiadarse del rival es contra el espíritu deportivo", y para ello pone el siguiente ejemplo del torneo de Wijk aan Zee, de 1970:


Platonov- Cortlever
Wijk aan Zee, 1970
Juegan las blancas

En esta posición las blancas tienen la partida ganada después de 54 jugadas. Simplemente jugando 55.Td7 las negras podrían rendirse. Por ejemplo: 55. ... Db6 56. Td8+ Rh7 57.Dd3+ Tf5 58. g4 y se acabó. En lugar de eso, Platonov cometió un espantoso error y jugó: 55.Td8+?? con lo cual las negras podrían responder con 55. ... Te8+ a la descubierta, con lo cual se pierde la torre ya que a 56. Td6 Te6 gana. Cortlever jugó la torre para cubrir el jaque, pero inmediatamente ofreció el empate, el cual fue aceptado por Platonov.

Dice Krabbé entonces:
"Pensamos que la reacción deportiva de Cortlever merece respeto y admiración", escribió Barry Withius en el boletín del torneo. Pero, dice Krabbé "yo personalmente desprecio este tipo de caballerosidad", y agrega: "Está en el espíritu de todos los deportes sacar ventajas de las debilidades de su oponente si está dentro de las reglas. El deporte es duro, es cruel. El deporte es realmente sobre sacar ventajas de los errores, haciendo que el rival se vea patético -y no sobre excelencia moral. No veo porqué tiene que ser diferente en ajedrez." Y concluye: "Cortlever debió haber sido expulsado del torneo".

Así las cosas en este fascinante mundo del ajedrez. Pero usted, lector, lectora, ¿qué piensa?

Minggu, 11 September 2011

Sobre resolver con Prolog el problema de los sudokus

En mi último artículo sobre programación y sudokus, hablé de un programa que podría resolver, en esencia, cualquier sudoku que se le pusiese, utilizando para ello fuerza bruta, es decir, considerando todas las posibilidades de números a poner en cada casilla. Alguna combinación debe ser la adecuada y con ello el asunto estaría resuelto.

Cuando corrí mi programa, pensé que se tardaría algunas horas quizás, de hecho no lo sabía, pero sospechaba que así sería. Un par de horas después de haber empezado el proceso lo aborté porque me hartó. No se veía para cuando terminaría. Así que decidí primero ver cuántos cálculos tiene que hacer el programa para poder resolver el sudoku planteado, que en ese caso hablamos de 46 números por hallar. Si usamos Prolog, tenemos que calcular la cantidad de combinaciones con repetición de 9 números tomados de 46 en 46.

La fórmula para ello es:
                               (n+r-1)!
Combinaciones =  ----------
                                r!(n-1)!

 donde n es la cantidad de números diferentes y r es la cantidad de espacios a llenar. Además, se pueden repetir los números, es decir, no todos tienen que ser siempre distintos. El resultado de esto es 1,040,465,790, es decir, mil cuatrocientos millones de posibles combinaciones. Para entender la magnitud de este número, si cada combinación se genera en un segundo (muy lento), entonces tardará unos 32 años en probar todas las posibles combinaciones. Si hace 1000 combinaciones por segundo (una aproximación más razonable), el sistema tardará unos 120 días en resolver todas las posibles combinaciones de números. Algo sin duda, demasiado lento. Vaya, si hiciese 10000 combinaciones por segundo, tardaría 12 días en resolverlo. Aún así es muy lento.

La razón de esto es que el programa, como originalmente está escrito, está obligado a prtimero poner a todos los números que buscamos, un "1". Se prueban entonces la combinación (como si fuese una caja fuerte). Si no "se abre", entonces probamos con otra combinación, haciendo backtrack. El resultado es un gigantesco proceso de ir cambiando números.

¿Cómo se podría mejorar? Desde luego que la técnica de prolog de examinar hasta agotar todas las posibilidades (simple fuerza bruta), no es práctica en este caso. Se necesita más inteligencia. Aún así, si no se quiere pensar mucho, bien podría intercalarse la búsqueda de unos pocos números, y entonces checar algunas de las ecuaciones, si eso está correcto, entonces buscar las restantes. Esto es lo que en principio sugirió el buen amigo Eduardo Ramos, aunque aún así los resultados pueden tardar si bien nos va, muchos días. De hecho, el programa se vería esta intercalación así:

predicates

   sudoku
   suma(integer, integer, integer, integer, integer, integer, integer, integer, integer, integer)
   num(integer)
  
clauses
  
   num(1).
   num(2).
   num(3).
   num(4).
   num(5).
   num(6).
   num(7).
   num(8).
   num(9).
  
   suma(A,B,C,D,E,F,G,H,I,R) :-
                          A+B+C+D+E+F+G+H+I = R.  

   sudoku :-
            / horizontales */
          
             num(A1), num(B1), num(C1), num(D1),
             suma(5,A1,4,3,B1,6,C1,7,D1,45),
           
             num(A2), num(B2), num(C2), num(D2), num(E2),   

             num(F2), num(G2), num(H2),
             suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
           
             num(A3), num(B3), num(C3), num(D3), num(E3),
             suma(A3,7,6,B3,C3,2,9,D3,E3,45),
           
             num(A4), num(B4), num(C4), num(D4),
             suma(A4,8,B4,7,C4,5,6,D4,1,45),
                       
             num(A5), num(B5), num(C5), num(D5),
             suma(7,6,A5,B5,3,C5,D5,8,9,45),
           
             num(A6), num(B6), num(C6), num(D6),
             suma(9,A6,3,8,B6,4,C6,2,D6,45),
           
             num(A7), num(B7), num(C7), num(D7), num(E7),
             suma(A7,B7,8,1,C7,D7,2,9,E7,45),

             num(A8), num(B8), num(C8), num(D8), num(E8), 

             num(F8), num(G8), num(H8),
             suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),

             num(A9), num(B9), num(C9), num(D9),
             suma(A9,3,B9,4,C9,7,1,D9,6,45),

            
             /* verticales */
            
             suma(5,A2,A3,A4,7,9,A7,A8,A9,45),
             suma(A1,B2,7,8,6,A6,B7,B8,3,45),
             suma(4,1,6,B4,A5,3,8,C8,B9,45),
             suma(3,C2,B3,7,B5,8,1,D8,4,45),
             suma(B1,D2,C3,C4,3,B6,C7,E8,C9,45),
             suma(6,E2,2,5,C5,4,D7,F8,7,45),
             suma(C1,F2,9,6,D5,C6,2,3,1,45),
             suma(7,G2,D3,D4,8,2,9,G8,D9,45),
             suma(D1,H2,E3,1,9,D6,E7,H8,6,45),
            
             /* cajas */
            
             suma(5,A1,4,A2,B2,1,A3,7,6,45),
             suma(3,B1,6,C2,D2,E2,B3,C3,2,45),
             suma(C1,7,D1,F2,G2,H2,9,D3,E3,45),
             suma(A4,8,B4,7,6,A5,9,A6,3,45),
             suma(7,C4,5,B5,3,C5,8,B6,4,45),
             suma(6,D4,1,D5,8,9,C6,2,D6, 45),
             suma(A7,B7,8,A8,B8,C8,A9,3,B9,45),
             suma(1,C7,D7,D8,E8,F8,4,C9,7,45),
             suma(2,9,E7,3,G8,H8,1,D9,6,45).
            

por cierto, este programa está en el antiguo turbo Prolog 2.0 de Borland.

La conclusión inicial es que si tuviésemos memoria infinita y poder de procesamiento infinito, las soluciones tipo prolog, resolviendo todo el árbol de búsquedas (árbol solución), podría llegar a la conclusión del resultado correcto. Pero en la vida real, al tener limitaciones en memoria y velocidad de proceso, esto desde luego vuelve impráctico este enfoque.

Cabe decir que no por ello prolog no es útil para resolver problemas. Simplemente el sudoku -utilizando el esquema de fuerza bruta- no es el más adecuado.