Juego de la Vida de Conway en C# con interfaz gráfica

Hoy os traigo un proyecto que realizamos Daniel Bazaco y yo. Se trata del clásico de juego de la vida, esta vez hecho en C# con .NET Core y Avalonia como librería gráfica. Funciona tanto en Windows como en GNU/Linux. El programa tiene la peculiaridad de que tiene implementados dos algoritmos totalmente distintos para el juego de la vida:

  • El clásico algoritmo de la matriz infinita.
  • Un algoritmo usando Quadtrees y tablas de dispersión optimizadas, que permite tener patrones precalculados.

La velocidad de este segundo algoritmo es muy superior a la del primero, aunque he de confesar que este segundo algoritmo no resulta evidente y tiene una desventaja en el modo gráfico. Este segundo algoritmo avanza a trompicones, por lo que no es posible realizar una animación gráfica idónea, a no ser que lo modifiquemos ligeramente. Este tercer algoritmo que es una modificación del segundo, es más lento, pero permite ser mostrado por la pantalla.

El programa admite ficheros tanto en formato estándar RLE como un formato propio, que hemos llamado Vaca. Puedes pasarte por la wiki del juego de la vida y probar los ficheros RLE que encuentres. No obstante, hay que tener cuidado, pues algunos ficheros RLE no son del juego de la vida, sino de otros juegos con normas ligeramente modificadas.

¿En qué consiste el Juego de la Vida?

El juego de la vida es un autómata celular de dos dimensiones. También se le ha categorizado como juego para cero jugadores.

El juego tiene unas normas sencillas. Cada celda puede estar viva o muerta. En la siguiente evolución, las celdas pueden pasar a vivas o muertas siguiendo este esquema:

  • Una célula muerta con exactamente 3 células vecinas vivas “nace” (es decir, al turno siguiente estará viva).
  • Una célula viva con 2 o 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por “soledad” o “superpoblación”).

Unas condiciones de partida determinadas podrán desencaminar comportamientos complejos y emergentes muy interesantes como las pistolas de gliders.

Uso

Pantalla de inicio de Conway

Desde aquí podemos dar a Nuevo patrón o Cargar patrón. Si le damos a Nuevo Patrón tendremos una matriz vacía y limpia. Podemos hacer click con el ratón para ir activando/desactivando las casillas. Puedes usar las teclas W, A, S y D o las flechas en pantalla para moverte por el universo infinito de Conway.

Una vez lo tengamos podemos guardarlo para no tener que volver a dibujarlo. Otra opción es cargar un patrón de la lista. Este programa admite formato RLE y Vaca, pero solo guarda archivos en formato Vaca.

Para ejecutar el juego de la vida hay tres botones importantes. El primero es Ejecutar, que ejecuta el juego de la vida indefinidamente. Se para cuando pulsamos Parar (el mismo botón).

El otro es Siguiente, que nos permite avanzar de iteración en iteración manualmente, muy interesante para observar al detalle ciertos patrones. Por otro lado tenemos Iterar N veces, que permite iterar N veces y que sirve para pruebas de rendimiento. Hay que tener en cuenta que tanto Siguiente como Iterar N veces funcionan un poco distinto con el algoritmo Quadtree (el activado por defecto), ya que este algoritmo hace varias evoluciones de golpe, para ser todavía más rápido. La parte mala es que no es posible ver en detalle cada algoritmo.

Algoritmo Matriz
Algoritmo Quadtree

Línea de comandos

Es posible ejecutar el juego de la vida en línea de comandos. Este modo permite cargar un archivo Vaca o RLE y ejecutarlo N iteraciones. Al finalizar se muestran estadísticas y se permite guardar el resultado o mostrarlo por pantalla con caracteres ASCII.

Hay dos parámetros, -i para indicar el fichero de entrada y -n para indicar las iteraciones a calcular.

Algoritmo Quadtree

¿Cómo funciona el algoritmo quadtree que tanto mejora el rendimiento del juego de la vida? Siendo sinceros, no es algoritmo sencillo o evidente. Su nombre más correcto es algoritmo Hashlife y fue descrito por Bill Gosper en los laboratorios de investigación de Xerox Palo Alto.

La idea básica es que muchas veces en el juego de la vida nos encontramos con patrones que se van repitiendo periódicamente y grandes zonas vacías.

Para ello recurre a un almacén de cuadrantes. Y es que ahora el universo ya no es una matriz infinita, sino un cuadrante. Y cada cuadrante tiene cuatro cuadrantes hijos (noroeste, noreste, suroeste y sureste), así hasta llegar al cuadrante mínimo ya no tiene hijos sino que es una celda viva o muerta. Esto evidentemente pone limitaciones al tamaño del universo, que será siempre potencia de dos.

El almacén es una tabla hash, pero no una corriente tipo HashMap de Java o Dictionary de C# sino que toma 4 elementos como índice, cuatro subcuadrantes. Si existe un elemento cuyos cuatro subcuadrantes son iguales (no se comprueba la igualdad exactamente, sería muy lento), se devuelve la siguiente iteración del cuadrante del almacén que cumple esos requisitos. De este modo no hace falta calcular los cuadrantes nada más que la primera vez que el programa se encontró con ellos.

Este sistema consume más memoria, pero mejora de forma sustancial la velocidad de ejecución. El algoritmo luego tiene bastantes más detalles (el diablo está en los detalles), pero esa es la idea principal, no calcular los cuadrantes más que una sola vez.

Descargar Conway

Podéis descargar Conway desde GitHub y compilarlo en Windows y GNU/Linux (Mac no está probado pero en principio funcionaría), con .NET Core 2.0 instalado.

Conway en GitHub

 

 

Estadística en Python: ajustar datos a una distribución (parte VII)

Ya hemos visto con anterioridad que existen modelos que nos hacen la vida más sencilla. Sin embargo, en esos modelos conocíamos ciertos datos de antemano. ¿Qué pasa si tenemos datos y queremos ver si podemos estar ante un modelo de los ya definidos?

Este tipo de ajuste es muy interesante, ya que nos permite saber si los datos en bruto pueden parecerse a los modelos de Normal u otros y aprovecharlo.

Ajuste de datos a una distribución

Para ajustar datos a una distribución, todas las distribuciones continuas de SciPy cuentan con la función fit. Fit nos devuelve los parámetros con los que ajusta nuestros datos al modelo. ¡Ojo, no nos avisa si es un buen ajuste o no!

Ejemplo: Queremos saber si la altura de los hombres adultos del pueblo de Garray sigue una distribución normal. Para ello tomamos una muestra de 80 alturas de hombres adultos en Garray.
Los datos los tenemos en este CSV, cada altura en una línea:

Vamos a ajustarlo.

En este caso nos informa de que estos datos parecen encajar con los de una distribución normal de media 160,37 y desviación típica 17,41.

¿Cómo de bueno es el ajuste? Kolmogorov

Hemos hecho un ajuste, pero no sabemos qué tan bueno es. Existen varios métodos para poner a prueba los ajustes. Existen varios métodos, siendo los más populares Chi-Cuadrado y Kolmogorov-Smirnov.

Chi-Cuadrado no se puede aplicar directamente sobre distribuciones continuas, aún así voy a explicar como se haría. Sin embargo, primero vamos a probar con Kolmogorov-Smirnov, que en SciPy es ktest.

Este test nos devuelve dos valores: D y el p-valor. Yo voy a fijarme en el p-valor. El p-valor es el nivel mínimo de significación para el cual rechazaremos el ajuste. Cuanto más cerca del 1 esté, más confianza hay en el ajuste, cuanto más cerca de cero esté, menos confianza hay en el ajuste. ¿Pero cómo se interpreta exactamente?

Una forma sencillo de entenderlo es hacer obtener el nivel de significación, que es 1 – NivelConfianza/100. Así para una confianza del 95%, este será de 0.05, para una confianza del 99%, el valor se reduce a 0.01. Si el p-valor es inferior a este nivel de significación, el ajuste probablemente no es correcto.

Aquí algún estadístico más serio se tiraría de los pelos, porque en realidad lo único que se puede demostrar con seguridad es en el caso de que no se ajuste. Si salta que se puede ajustar a una normal, simplemente querría decir que no se puede rechazar la hipótesis de partida (que sea normal), pero no confirma que sea normal.

Esto es algo común en el contraste de hipótesis y con los p-valores en particular y ha suscitado crítica, hasta tal punto que en 2016, la American Statistical Association publicó una serie de consejos para tratar con p-valores. El p-valor en este caso solo puede demostrar que no se ajusta a una normal. No obstante, para ir poco a poco, podemos simplificar esto un poco.

Chi-Cuadrado

Para hacer el test de Chi-Cuadrado primero hay que dividir los datos continuos. Para uso podemos usar la función de NumPy, histogram o la de SciPy binned_statistic. Tenemos que construir una lista con las frecuencias esperadas si siguiéramos al 100% la distribución a la que queremos ajustarnos.

Una vez tengamos una lista con los valores esperados, simplemente podemos comparar las frecuencias reales con las esperadas con chisquare. Esto nos devolverá C y el p-valor. El significado del p-valor es exactamente igual.

Con esto ya hemos visto como empezar con estadística en Python. No sé si haré más artículos de este estilo, si no es así, espero que os hayan gustado esta serie de artículos. El mundo del data science es inmenso y os invito a seguirlo explorando.

Yew, crea webapps al estilo Angular/React en Rust

Hoy os traigo una librería muy potente y muy útil, ahora que Rust compila a WebAssembly de forma nativa. Se trata de Yew, una librería para diseñar frontends, single-page-applications y en general, una librería que es una alternativa a Angular, React, Vue y Elm.

En particular, Yew se basa en The Elm Architecture, por lo que los usuarios de Elm serán los que encuentren más familiar a Yew.

Yew significa tejo. He aquí uno de los tejos más famosos de Valladolid, en la plaza del Viejo Coso

Instalar cargo-web y el soporte a WebAssembly

Antes de empezar a programar necesitaremos instalar un plugin para Cargo, llamado cargo-web, que nos ayudará en el desarrollo web con Rust. Por otro lado, hace falta instalar el soporte de Rust a WebAssembly. Existen tres opciones actualmente: asmjs-unknown-emscripten, wasm32-unknown-emscripten y wasm32-unknown-unknown. Para los primeras opciones hace falta tener instalado Emscripten. Para la última, no hace falta nada, por lo que es mi opción recomendada. Por otro lado, wasm32 significa WebAssembly y asmjs es asm.js, que es simplemente JavaScript y será compatible con más navegadores.

The Elm Architecture

Los principios de The Elm Architecture se basan en: modelo, mensajes, actualización y vista.

Para este tutorial vamos a hacer la típica aplicación de una lista donde guardamos notas. Nuestro modelo se va a componer de una lista de tareas, para simplificar, pongamos que una tarea es simplemente un String y un ID. Entonces también nos hará falta almacenar un contador para ir poniendo IDs. También, al tener un campo de texto, nos hará falta una variable para ir almacenando temporalmente lo que escribe el usuario.

Lo siguiente es diseñar los mensajes. Los mensajes interactúan con el modelo y desencadenan una actualización de la vista. En esta aplicación solo nos hacen falta dos mensajes: añadir mensaje y borrar mensaje. Pero como tenemos un campo de texto, tenemos que introducir un mensaje Change y siempre viene bien un mensaje que no haga nada.

Una vez hecho esto pasamos a crear la función update, en la que hacemos distintas cosas según el mensaje que recibamos.

Así pues, si se lanza un mensaje Msg::Add lo que hacemos es copiar el valor de la variable temporal input, crear una nueva tarea con su ID y añadirla a la lista de tareas. Ya está. Yew mágicamente actualizará la página para reflejar que la lista de tareas ha sido modificada. Lo mismo pasa con Remove.

Ahora vamos a las vistas. Una vista es una función que devuelve Html<Msg> y se pueden componer varias funciones así. En nuestro caso, tenemos una vista principal donde se ve un campo de texto y un sitio donde se ejecuta un bucle for con las tareas del modelo. Y a cada tarea se le aplica la vista view_task.

La macro html! nos permite escribir HTML directamente en Rust, con algunas diferencias (¡prestad atención a las comas!). También nos permite introducir código Rust (entre llaves) y closures (observad onclick, oninput y onkeypress).

Finalmente en el método main, inicializamos el modelo y llamamos a program, que empieza a ejecutar Yew.

El código final queda así.

Ejecutando la aplicación web

Usando cargo web, es muy sencillo generar la aplicación web. Simplemente ejecuta:

El resultado, se montará en un mini servidor web. Si accedes a la URL que indica Cargo con tu navegador web, verás algo similar a esto:

Añade items y bórralos. Observa como la aplicación funciona perfectamente.

Distribuyendo la aplicación

Realmente cargo web ha hecho muchas cosas por nosotros. Si nosotros queremos usar Yew en la vida real, no usaremos cargo web. Para ello, compilamos la aplicación web:

Y accedemos a la carpeta target/wasm32-unknown-unknown/release. Allí encontraremos dos archivos que vamos a necesitar. Uno acabado en .js y otro acabado en .wasm. Ambos ficheros deberemos copiarlos donde queramos usarlos. Por último, será necesario un fichero HTML. En el fichero HTML solo hace falta cargar el fichero JS. Yew hará el resto.

Si quieres saber más, puedes descargarte el código de ejemplo que se encuentra en GitHub.