Logo Lainformacion.com

Categoría: Ordenadores

Hackstory, la historia de los hackers españoles, en libro electrónico

Portada Hack StoryUna buenísima noticia para cualquiera que esté interesado en la historia de los hackers españoles: Hackstory, el impresionante trabajo de Mercé Molist que recopilando su historia, está ya disponible para su descarga como libro electrónico en multitud de formatos.

La descarga es totalmente gratuita, aunque si aprecias el trabajo de Mercé puedes hacer un donativo usando los enlaces que hay al final de la página de descarga.

Ajedrez aleatorio

Random Chess
En azul: duración de las partidas aleatorias en simulación;
en marrón: partidas reales entre maestros

La curiosidad llevó a @BillAutomata –que personalmente dice no ser un gran jugador– a preguntarse cuán diferente sería normalmente una partida de ajedrez completamente aleatoria frente a las partidas que juegan los grandes maestros.

De modo que, armado con sus habilidades como programador, preparó las reglas del juego y ejecutó una simulación de unas 100.000 partidas que requirió unas 3 horas. Utilizó JavaScript y AWS porque si no en su portátil habría necesitado semanas.

Las partidas aleatorias son completamente alocadas y carentes de sentido, pero limitadas por las propias reglas del juego, tanto en movimientos como en duración: o bien hay un jaque mate o bien hay una triple repetición o se alcanzan los 50 movimientos sin que nadie capture otra pieza ni avance un peón.

El resultado del estudio es interesante y no me consta que se hubiera publicado antes. En la página del proyecto pueden verse todos los detalles: Random Chess Moves in Javascript. Lo más relevante podría resumirse en:

  • En las partidas entre maestros más o menos el 55% acaban con la victoria de alguno de los contrincantes; el 45% en tablas.
  • En cambio en las partidas aleatorias el 15% acaban con la victoria de algún bando, mientras que el 85% terminan en tablas. Este valor puede parecer sorprendentemente alto teniendo en cuenta que todos los movimientos son «a lo loco».

Aparte de «quién gana» BillAutomata examinó también la duración de las partidas.

Los maestros normalmente acaban sus enfrentamientos en 80 movimientos de promedio (suele haber un límite de tiempo para 40 movimientos por jugador; lo normal es cumplir con el tiempo o acordar tablas al llegar ahí). La más larga conocida requirió más de 400 movimientos (aunque según otras fuentes pudieron ser 269 o incluso 237 – las reglas han cambiado con el tiempo).

En cambio en las partidas aleatorias el número promedio de movimientos cuando termina el juego es 342 (victoria o tablas) y la partida más larga registrada en la simulación requirió 804.

Analizando a la velocidad del rayo

Watson. Foto: IBMWatson, el famoso superordenador de IBM, dejó hace tiempo los concursos contra humanos para dedicarse a temas más relevantes, como el trabajo en investigación médica y sectores del conocimiento especializados. Aunque todavía no esté claro qué parte de lo que lee «entiende», sí se sabe que es capaz de analizar 70.000 artículos sobre un tema determinado en un solo día, una tarea que a un científico humano le llevaría unos 38 años. [Fuente: Reuters.]

Una forma de resolver el problema del viajante, visualmente explicada

Tsp-Red

El problema matemático del viajante (en inglés: Travelling Salesman Problem, TSP) es un clásico en el mundo de los algoritmos: encontrar la ruta más corta posible que visite cada ciudad una sola vez en un mapa, regresando a la ciudad de origen.

Como es de suponer, esto tiene miles de aplicaciones prácticas, pues también es un ejemplo de optimización y muchos problemas de otros campos pueden considerarse –matemáticamente– equivalentes. Si existiera un algoritmo definitivo no solo se podría ahorrar combustible y tiempo en los viajes, también optimizar cómo colocar los libros en una gran biblioteca o recorrer una calle para dejar los sobres de correo.

Por desgracia no existe un algoritmo definitivo: aunque a veces se puede encontrar la mejor solución si aumenta el número de nodos (en este caso: «ciudades») la complejidad del problema crece sobremanera; al cabo de un tiempo es fácil ver que no hay forma de probar todas las posibles soluciones ni de demostrar que una sea mejor que otra. Y aunque existen algoritmos parciales o para casos concretos –que son los que se utilizan en la práctica– debido entre otras cosas a que se sabe que es un problema NP-difícil (NP-hard) encontrar una forma de hacerlo supondría un gran avance matemático.

En la imagen un programa llamado Parano utiliza un algoritmo genético para resolver el TSP, mostrando visualmente los avances a medida que se producen: una forma original de resolverlo aunque probablemente no la óptima.

Anteriormente, en la categoría Ordenadores