lunes, 23 de abril de 2012

Matemática online

Una entrada breve.

El otro día descubrí que si uno escribe en Google, por ejemplo: y=x/sin(x) además de los resultados, Google nos pinta la gráfica y nos permite interactuar con ella. El resultado es mejor que ningún programa de pintar funciones que haya visto hasta ahora. Desgraciadamente, no tiene muchas opciones y no tiene muchas funciones definidas.



Ayer me encontré este otro. El resultado gráfico no es tan bueno, aunque no está nada mal, y permite pintar varias funciones a la vez, y tiene muchas funciones predefinidas:


Y no sólo eso, también permite hacer derivadas e integrales de funciones y otras cosas. Aún le faltan algunas cosillas, pero me parece que está muy bien.

No deja de sorprenderme que a veces se vean mejores aplicaciones para web (o Android, o IPad) que para Windows, Linux o Apple (sí, soy consciente que estoy comparando cuatro cosas diferentes, pero se me entiende ¿no?). Por ejemplo, desde mi punto de vista, gmail le da mil vueltas a casi cualquier cliente de email existente (digo casi porque no los conozco todos, no porque haya visto uno mejor), cuando lo lógico sería que fuese al revés.

Dejo la puerta abierta a que pongáis enlaces a más páginas de este tipo.



sábado, 21 de abril de 2012

Reglas de Golomb y turbulencia

Reglas de Golomb

Imaginad que queremos construir una regla pero que, por alguna razón, tenemos un límite en el número de marcas que podemos hacer en ésta. ¿Cuál sería la forma óptima de situar las rayas?

La respuesta a esta pregunta es una regla de Golomb. La siguiente figura muestra una de orden 4:


Como se puede ver, en este caso con sólo cuatro marcas podemos medir seis distancias diferentes. De hecho, todas las distancias enteras entre 1 y 6 están incluidas. Cuando esto ocurre se dice que es una regla de Golomb perfecta.

Lamentablemente, para reglas mayores que 6, no existe ninguna regla de Golomb perfecta, a lo más que podemos aspirar es a reglas de Golomb optimas (hay varias definiciones de óptimo), para lo cual no existen algoritmos eficientes, que se sepa.

¿Qué tiene esto de interesante? Por un lado me resulta curioso que no exista un buen algoritmo para generarlas. Hubiera jurado que usando algún tipo de potencia de dos en la localización de las marcas (inicialmente pensé en algo como 1,2,4,8...) se conseguiría, pero no, no es tan sencillo.

Por otro lado, tengo la impresión de que las reglas de Golomb tienen que tener alguna utilidad. Wikipedia dice que se usan en códigos de correción de errores y para determinar puntos de colocación de antenas, así que me puse a pensar si se me ocurría alguna otra aplicación. Al final pensé en algo que requiere una digresión...

Turbulencia y autocorrelación

No voy a ponerme aquí a hablar de la turbulencia en detalle (entre otras cosas porque si me pusiera me daría cuenta de que no tengo los conceptos lo suficientemente claros como para explicarlos). Sólo voy a hablar de la parte relacionada con las reglas de Golomb.


Lo primero que uno piensa sobre la turbulencia es que es un fenómeno más o menos aleatorio. Y eefectivamente, en muchos aspectos así es. La clave está en ese "más o menos". Si uno se fija en un flujo turbulento se ve que está formado por "remolinos" de diferentes tamaños, y que pese a que en conjunto tenemos una estructura aleatoria, localmente las velocidades entre puntos cercanos tendrán una cierta correlación estadística. Dicho de otra forma, cuanto más cerca estén dos puntos en el fluído, más probable será que ambos formen parte del mismo remolino turbulento y, por tanto, más probable será que las velocidades del fluido en ambos puntos estén relacionadas.

De hecho, gran parte de lo que se sabe sobre turbulencia no son más que expresiones de correlación temporal y espacial de las diferentes componentes de la velocidad de un fluido. La siguiente gráfica muestra un ejemplo típico. En ordenadas tenemos la correlación y en abcisas la separación entre los puntos:
Un valor de 1 significa que las velocidades son iguales (los dos puntos son el mismo), un valor negativo que existe una correlación, pero con el signo cambiado (podemos imaginar que los puntos están en lados opuestos de un remolino) y cero significa que no hay correlación estadistica entre ellos.

Una de las cosas que se puede hacer, tanto con modelos numéricos como con datos experimentales, es estudiar la correlación entre componentes de la velocidad. De esta forma podemos obtener otras magnitudes relacionadas con la turbulencia. Por simplicidad, supongamos que queremos hacerlo en un laboratorio.

La forma trivial de hacerlo sería colocar N sensores de velocidad en posiciones \(x=n\Delta x \), donde \(n=0,1,2,...N-1\). De esta forma tendríamos N-1 distancias para construir una gráfica como la de arriba.

El caso es que lo único que nos importa al hacer las correlaciones es la distancia entre los sensores. Aquí es donde entran las reglas de Golomb, podemos conseguir muchos más puntos usando el mismo número de sensores. Mi estimación es que para conseguir N distancias es necesario, aproximadamente, \(\sqrt{2N}\) sensores.

Lo mismo es aplicable a modelos numéricos o a otros métodos experimentales como el PIV

¿Alguna otra idea?


viernes, 6 de abril de 2012

Las ecuaciones de Navier-Stokes (I)

Atendiendo a la petición de Nabil de hablar de las derivadas materiales, me he ido por la tangente y he decidido hacer un especial, en al menos dos partes, sobre las ecuaciones de Navier-Stokes.

Sé que es un tema que no interesa a todo el mundo, así que muchos ni lo leerán y los que lo lean me temo que algunas cosas les parecerán básicas. Son básicas a propósito por dos razones: Una porque a mi me cuesta entender las cosas hasta que no consigo convertirlas en algo sencillo y la otra porque entro en unos detalles que muchas veces damos por sabidos y no nos detenemos a pensar mucho en ellos.

En cualquier caso, entenderé si nadie se lo lee... excepto Nabil. ¡A ti no te queda más remedio, por abrir la boca!

Ecuaciones de conservación

Una ecuación de conservación es cualquier ecuación en derivadas parciales de la forma:
\begin{aligned} \frac{\partial\phi}{\partial t}+\nabla\cdot\mathbf{F}=0 \end{aligned}

Donde \(\mathbf{F}\)  es un campo vectorial cualquiera. La razón de que estas ecuaciones se llamen así es que si la integramos en un dominio inmovil \(\Omega\) cualquiera tenemos:

\begin{aligned} \int_{\Omega}\frac{\partial\phi}{\partial t}+\int_{\Omega}\nabla\cdot\mathbf{F}=0 \end{aligned}

Commutando la derivada temporal con la integral y aplicando el teorema de la divergencia:

\begin{aligned} \frac{\partial}{\partial t}\int_{\Omega}\phi+\int_{\Gamma}\mathbf{n}\cdot\mathbf{F}=0 \end{aligned}

Donde \(\Gamma\)  es el contorno del dominio y \(\mathbf{n}\)  un vector perpendicular a éste en cada punto. De la ecuación anterior se deduce que los cambios en la magnitud \(\phi\)  dentro del dominio sólo son debidos a cosas que ocurren en el contorno, es decir, no hay creación o destrucción de \(\phi\)  dentro del dominio.

En realidad he hecho trampas, porque la derivación tendría que haberla hecho al revés. Generalmente uno empieza con la ecuación integral, que suele tener mucho más sentido físico y luego obtiene la ecuación diferencial. De hecho, creo que la mayor parte de las ecuaciones diferenciales tienen mucho más sentido en forma integral, pero no hablemos de eso ahora...

Como sabemos, las ecuaciones de Navier-Stokes no son más que la ecuaciones de conservación de la masa y el momento de un fluído y como ya imaginaréis, tienen exactamente la forma descrita.

Vamos a empezar por la conservación de la masa. Supongamos que tenemos un dominio fijo en el espacio y queremos calcular la variación de masa total en su interior en un intervalo de tiempo. Dicho de otra forma, el cambio en la masa es debido a la masa que entra o sale por los contornos:

\begin{aligned} \int_{\Omega}\rho\left(\mathbf{x},t_{1}\right)-\int_{\Omega}\rho\left(\mathbf{x},t_{0}\right)+\int_{\Gamma}\left[\int_{t_{0}}^{t_{1}}\rho\left(\mathbf{x},t\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t\right)\right]=0 \end{aligned}

Donde el término de la derecha es la integral en el contorno \(\int_{\Gamma}\)  del flujo de materia en cada punto del contorno \(\rho\left(\mathbf{x},t\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t\right)\)  integrada en el intervalo de tiempo \(\int_{t_{0}}^{t_{1}}\).

Esta ecuación es válida sin importar si las velocidades o densidades son continuas o no. Por supuesto, tienen que ser integrables, pero esa es una condición muchísimo menos restrictiva. Por ejemplo, esta ecuación es válida tanto para fluídos como para partículas extensas o, incluso puntuales. Es igual de válida para un fluído continuo como para el mismo fluído considerado como moléculas.

Sin embargo, también es un poco fea, así que vamos a intentar simplificarla (perdiendo algo de generalidad por el camino). Si consideramos que la cantidad total de materia dentro del dominio nunca varía bruscamente podemos tomar el límite cuando \(t_{1}\rightarrow t_{0}^{+}\) . Luego, dividiendo por \(t_{1}-t_{0}\)  y usando la definición de derivada en los dos primeros términos tenemos:

\begin{aligned} \left.\frac{\partial}{\partial t}\int_{\Omega}\rho\right|_{t_{0}}  \end{aligned}

Y en el último término, conmutando las integrales tenemos:

\begin{aligned} \lim_{t_{1}\rightarrow t_{0}^{+}}\frac{1}{t_{1}-t_{0}}\int_{t_{0}}^{t_{1}}\left[\int_{\Gamma}\rho\left(\mathbf{x},t\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t\right)\right]  \end{aligned}

Que, si nos damos cuenta, no es otra cosa que la derivada de la primitiva de \(\int_{\Gamma}\rho\left(\mathbf{x},t\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t\right)\)  en \(t_{0}\) y por tanto igual a:
\begin{aligned} \int_{\Gamma}\rho\left(\mathbf{x},t_{0}\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t_{0}\right)  \end{aligned}

En resumen, la ecuación de conservación de la masa resulta:

\begin{aligned} \left.\frac{\partial}{\partial t}\int_{\Omega}\rho\right|_{t_{0}}+\int_{\Gamma}\rho\left(\mathbf{x},t_{0}\right)\mathbf{n}\cdot\mathbf{u}\left(\mathbf{x},t_{0}\right)=0 \end{aligned}

Que es válida para todo \(t_{0}\)  y por tanto podemos escribir como:

\begin{aligned} \frac{\partial}{\partial t}\int_{\Omega}\rho+\int_{\Gamma}\rho\mathbf{n}\cdot\mathbf{u}=0  \end{aligned}

Esta ecuación tiene la forma integral de una ecuación de conservación. Haciendo la suposición (y, de nuevo, perdiendo generalidad) de que la velocidad y la densidad son derivables en el espacio, según lo dicho anteriormente, la podemos poner en forma diferencial:

\begin{aligned} \frac{\partial\rho}{\partial t}+\nabla\cdot\left(\rho\mathbf{u}\right)=0 \end{aligned}

Este es un tipo importante de ecuación de conservación en el que la magnitud conservada sólo está sujeta a convección por un campo de velocidades. A continuación veremos que las ecuaciones de Navier-Stokes son poco más que esto aplicado también a la cantidad de movimiento.

Vamos a ello, empecemos por suponer que estamos tratando con moléculas y no con fluídos, y que la ecuación de conservación de cada componente de momento tiene la siguiente forma:

\begin{aligned} \frac{\partial}{\partial t}\int_{\Omega}\rho u_{i}+\int_{\Gamma}\rho u_{i}\mathbf{n}\cdot\mathbf{u}=\int_{\Omega}F_{i}  \end{aligned}

Donde \(F_{i}\)  es la combinación de las fuerzas externas (gravitación, por ejemplo) y las fuerzas moleculares entre partículas. Por el momento no vamos a entrar en ellas, solo diré que aunque en principio parecen ser una fuente de momento (ya que la para que la ecuación sea realmente de conservación el lado derecho del igual tiene que ser cero), al final veremos que en realidad tiene la forma de la divergencia de un vector y que el momento efectivamente conserva.

Para este caso he escogido la ecuación integral en la que asumimos que las variaciones en el tiempo son derivables. Una condición que no es muy restrictiva si consideramos que cada molécula es extensa y tiene densidad finita.

El término advectivo es el único que incluye una integral en el contorno. Sin necesidad de suponer diferenciabilidad (en el sentido tradicional), podemos usar el teorema de la divergencia y escribir:

\begin{aligned} \frac{\partial}{\partial t}\int_{\Omega}\rho u_{i}+\int_{\Omega}\nabla\cdot\left(\rho u_{i}\mathbf{u}\right)=\int_{\Omega}F_{i}  \end{aligned}

En este caso, estoy usando la divergencia definida por la teoría de las distribuciones (o funciones generalizadas). Esta divergencia no devuelve una función, sino un objeto que podemos integrar, pero que no tiene mucho significado fuera de una integral. Ganamos generalidad a costa de usar un cálculo un pelín más complicado. Esto mismo podría haberlo hecho más arriba, cuando mostré la ecuación diferencial de la conservación de la masa.

Pese a lo dicho en el párrafo anterior, sabiendo que las distribuciones sólo tienen sentido una vez integradas en algún dominio, nada nos impide trabajar con ellas mientras tanto sin integrarlas. Es decir, podemos escribir:

\begin{aligned} \frac{\partial}{\partial t}(\rho u_{i})+\nabla\cdot\left(\rho u_{i}\mathbf{u}\right)=F_{i}  \end{aligned}

Donde la ecuación anterior es válida para campos de velocidades no diferenciables siempre y cuando seamos conscientes de que en realidad sólo tiene sentido cómo ecuación integral y que este operador divergencia es un objeto distinto al que usé en la ecuación de conservación de la masa.

Desde el punto de vista estético, la ecuación anterior aún tiene un problema. En realidad son tres ecuaciones y además la notación es una especie de mezcla entre notación tensorial y vectorial. Escrita púramente en notación tensorial sería:

\begin{aligned} \partial_{t}left(\rho u_{i}right)+\partial_{j}\left(\rho u_{i}u_{j}\right)=F_{i} \end{aligned}

Que no está mal, aunque personalmente, la notación tensorial no me acaba de convencer. Otra cosa que podemos hacer es darnos cuenta de que el producto \(u_{i}u_{j}\)  es lo que suele llamarse producto diádico o diada y que suele representarse en forma vectorial simplemente como \(\mathbf{uu}\) , aunque las formas \(\mathbf{u}\mathbf{u^{T}}\)  y \(\mathbf{u}\otimes\mathbf{u}\)  también son comunes. Yo voy a usar \(\mathbf{u}\mathbf{u}^{T}\)  porque no requiere notación especial, es simplemente el producto matricial de dos vectores (recordemos que , por otro lado, \(\mathbf{u}^{T}\mathbf{v}\)  es el producto escalar \(\mathbf{u}\cdot\mathbf{v}\)).

 Claramente, \(\mathbf{u}\mathbf{u}^{T}\) es un tensor de 3x3 elementos. Es posible definir la divergencia de un tensor, basta ver la fórma tensorial para ver qué efecto tiene. En este caso, podemos ver \(\nabla\cdot(\mathbf{u}\mathbf{u}^{T})\) como el vector formado por las divergencias de cada columna de \(\mathbf{u}\mathbf{u}^{T}\) (Otra forma de escribirlo sería: \((\nabla^T\mathbf{u}\mathbf{u}^{T})^T\), que es más consistente, pero tiene demasiadas T para mi gusto)

Finalmente, la ecuación de conservación del momento resulta:

\begin{aligned} \frac{\partial}{\partial t}\left(\rho \mathbf{u}\right)+\nabla\cdot\left(\rho \mathbf{u}\mathbf{u}^{T}\right)=\mathbf{F}  \end{aligned}

Que tiene la brevedad justa como para que yo pueda entenderla en su totalidad. El término advectivo así escrito suele decirse que está en “forma conservativa”, aunque a mi me gusta pensar que está en la “forma que tiene que estar”.

Yo con esa ecuación me conformo; pero si queremos aún más brevedad podemos definir los vectores \(\mathbf{q}^{T}\equiv\left(1,u_{1},u_{2,}u_{3}\right)\), \(\mathbf{f}^{t}=\left(0,F_{1},F_{2},F_{3}\right)\)  y el operador \(\square\equiv\left(\frac{\partial}{\partial t},\frac{\partial}{\partial x_{1}},\frac{\partial}{\partial x_{3}},\frac{\partial}{\partial x_{3}}\right)\) , de forma que:

\begin{aligned} \square\cdot\left(\rho \mathbf{q}\mathbf{q}^{T}\right)=\mathbf{f} \end{aligned}

Donde \(\mathbf{q}\) es el cuadrivector velocidad (1 es la velocidad del tiempo 1 s/s). Esta fórmula es equivalente a las ecuaciones de conservación de la masa y el momento. Sin embargo no estoy seguro de que ganemos claridad con ello.

Así que por el momento nos quedaremos con dos ecuaciones de conservación de la masa y el momento, válidas para magnitudes discontinuas (teniendo en cuenta que en ese caso sólo tienen sentido integradas) y, por tanto, válidas para fluídos considerados como medios continuos o como partículas:

\begin{aligned} \frac{\partial\rho}{\partial t}+\nabla\cdot\left(\rho\mathbf{u}\right)=0 \end{aligned}

\begin{aligned} \frac{\partial}{\partial t}\rho \mathbf{u}+\nabla\cdot\left(\rho \mathbf{u}\mathbf{u}^{T}\right)=\mathbf{F}  \end{aligned}

En la próxima edición, hablaré de \(\mathbf{F}\)  y de cómo obtener la viscosidad (y la turbulencia) a partir del término convectivo.

...Y quizás de las derivadas materiales.

jueves, 29 de marzo de 2012

Asteroides blandos

Para los que no lo sepáis, gran parte de mi investigación consiste en estudiar el transporte de sedimentos (arena, generalmente) por una corriente de agua. Para ello lo que hacemos es considerar que, en las escalas en las que estamos interesados, el sedimento se comporta como si fuera un fluido continuo.

El resultado final son unas ecuaciones bastante largas que modelan, por un lado el agua y por otro el sedimento considerado como un fluído, con un par de términos de interacción entre ambos.

Como imaginaréis, el sedimento no se comporta exatamente como un fluído. Entre otras cosas, las colisiones entre moléculas son elásticas, mientras que las colisiones entre granos de arena no lo son. Existen también fricciones entre granos y otros detalles más. Eso implica que tanto la presión como las fuerzas viscosas requieren un tratamiento distinto. En resumen, lo que se hace es modelar los granos de arena como esferas (lo típico), introducir un par de coeficientes de pérdida de energía (fricción, inelasticidad) y usar la teoría cinética de gases densos.

Esta es, para mí, la parte divertida. La parte aburrida es que mi futuro, una vez que mi programa esté funcionando, consistirá en estudiar cómo se va erosionando léntamente el terreno cercano a un pilar sujeto a oleaje. ¡Apasionante!

Pero aún hay esperanzas. Estoy yendo a una clase sobre fluídos granulares. En ella se estudian todo tipo de flujos de este tipo: avalanchas de rocas secas, avalanchas de rocas no tan secas, avalanchas de rocas cayendo al agua, avalanchas de rocas en el agua y... avalanchas de rocas en el espacio.

O dicho de otra forma: "asteroides".

Y no, no es esto:

Vamos a aparcar en uno de esos grandes
Con lo de avalanchas me refiero a que el asteroide en sí puede considerarse una avalancha de rocas. Al parecer la estructura de los asteroides se desconoce. Es decir, se sabe de qué están hechos pero no se sabe si son una única masa sólida o están formados por agregados de rocas sujetas por gravedad. Se sospecha que es lo segundo.

Una de las razones para sospecharlo es que muchos asteroides y cometas se parten con demasiada facilidad cuando están sujetos a fuerzas de marea débiles. Eso le pasó, por ejemplo, al Shoemaker Levi 9 cuando impactó en Júpiter.

Las ciudades más importantes de Júpiter reciben impactos
Otra razón es que algunos asteroides tienen cráteres tan grandes (en relación a su tamaño) que de haber sido sólidos se habrían partido; mientras que si fueran agregados de partículas, la fricción entre ellas habría reducido los daños.


Un poco más, y el de en medio tiene un crater mayor que sí mismo.
Pero la razón fundamental es que no existen asteroides grandes que giren a la velocidad que haría que las partículas de su superficie saliesen disparadas. Hay muchos asteroides con velocidades de rotación altas, justo hasta el límite en el que se partirían si no fuesen sólidos; pero no se conoce ninguno que gire más deprisa.

Sorprendentemente, esto que acabo de explicar es el estado del arte en la materia. Incluso aunque se hayan mandado satélites al encuentro de asteroides y alguno se haya hecho chocar a propósito contra uno, aún no se conoce bien su estructura. De hecho, este artículo (escrito, entre otros, por el profesor que me da la asignatura) es del 2007 y da una idea de lo que se sabe sobre el tema.

¿De qué va? pues esencialmente modela los asteroides como elipsoides, constituidos por granos sólidos (esferas idénticas) sujetos a las mismas ecuaciones que mis granos de arena. Con ese modelo, estudia lo que le ocurre a un asteroide cuando pasa cerca de un planeta, es decir: en qué momento se rompe debido a las fuerzas de marea.

La idea es que si el modelo coincide más o menos con los casos conocidos de asteroides que se rompen cuando se acercan a planetas, eso daría otro argumento a favor de los asteroides "blandos".

En todo caso, el tema me parece interesante, así que a parte de sentarme a ver como se va creando un hoyito al lado de un pilar, intentaré meterme un poco en el asunto este de los asteroides, a ver qué pasa.



sábado, 24 de marzo de 2012

¿Cómo funciona un programa (engine) de ajedrez?

   
Desde hace un tiempo estoy interesando en el mundo de los engines de ajedrez, y aunque en gran parte me sirva para aclararme, creo que puede ser un tema interesante.

Básicamente un engine de ajedrez necesita tres componentes esenciales:
  1. Un generador de movimientos
  2. Una función de evaluación
  3. Una función de búsqueda

El generador de movimientos se encarga de crear una lista de los movimientos posibles en un posición determinada, así como de chequear la legalidad de los mismos. Esta es una de las partes más difíciles, ya que es muy “bug prone”. El generador de movimientos debe ser capaz también de deshacer movimientos, por razones que veremos más adelante.

La función de evaluación (que se suele denominar “estática”, ya que evalúa factores puramente estáticos tales como el material, la estructura de peones, la seguridad del rey, etc. pero no se para a mirar si, por ejemplo, en el siguiente movimiento vamos a perder la dama: de eso se encarga la función de búsqueda, como se explica más adelante) tiene la finalidad de asignar una valoración a una posición dada. La implementación más sencilla sería la puramente material: contar el material que hay por cada bando en el tablero. La evaluación se suele dar tomando el valor de un peón como 100, y el resto de las piezas en función de esta. Así, valores típicos para las piezas serían de 100 para los peones, 300 para caballos y alfiles, 500 para las torres y 900 para las damas.
Sin embargo, una evaluación basada solamente en el material daría lugar a un engine muy débil. Por ejemplo, valoraría como igualada una posición con equilibro material, aunque uno de los bandos tuviera todas sus piezas desarrolladas y el otro las mantuviera en sus casillas iniciales. Además mientras no viera una ganancia de material, todos los movimientos le parecerían equivalentes, dando lugar a un juego cuasialeatorio.
Una mejora realmente sencilla y muy eficiente son las piece square tables (pst). Se trata de asignar una puntuación extra a cada pieza dependiendo del tipo de pieza en cuestión y de su posición en el tablero. Por ejemplo, una pst para los caballos blancos podría ser la siguiente;

int knight_pst[64] = {
-10, -10, -10, -10, -10, -10, -10, -10,
-10,   0,   0,   0,   0,   0,   0, -10,
-10,   0,   5,   5,   5,   5,   0, -10,
-10,   0,   5,  10,  10,   5,   0, -10,
-10,   0,   5,  10,  10,   5,   0, -10,
-10,   0,   5,   5,   5,   5,   0, -10,
-10,   0,   0,   0,   0,   0,   0, -10,
-10, -30, -10, -10, -10, -10, -30, -10
};

El primer elemento del array es la casilla a8, y el último la h1. Cuando la función de evaluación escanee el tablero en una posición determinada, al encontrarse con un caballo blanco en la casilla n-sima, le dará un bonus (o malus) que será el valor n-simo (en puridad “n-simo menos uno”) del array knight_pcsq. Podemos ver que con esta pst para los caballos, como norma general se penaliza que se sitúen en los bordes del tablero y se incentiva que estén en el centro del mismo. Con algunas pst más para el resto de piezas (añadido a la evaluación material) el juego del engine pasa a ser con mucho más sentido a un coste muy bajo.
Por convenio se suele tener que la función de evaluación da valores positivos cuando la ventaja es de las blancas y negativos cuando la ventaja es de las negras.

La verdad es que por lo dicho hasta ahora nada diferencia cómo juega un programa de ajedrez de cómo lo hace un humano. Básicamente hemos dicho que debe saber las reglas (generador de movimientos) y que tenga ciertos conocimientos para evaluar si una posición es mejor que otra (función de evaluación). Pero a partir de aquí, ¿cómo usa estas herramientas un engine de ajedrez? Una vez que sabemos mover las piezas y evaluar la posición, el paso siguiente es buscar el mejor movimiento de todos los posibles.
Para seguir con esto debemos introducir al menos un término para no inducir a errores, el ply de profundidad. Cuando se habla de ajedrez, se suele entender que “un movimiento” equivale a que el bando blanco y el negro han movido. Sin embargo, en el mundo de los engines de ajedrez, la unidad fundamental de movimientos es el “ply”, que es simplemente un movimiento hecho por cualquiera de los bandos. Así, para calcular nuestro movimiento y la respuesta del rival, estamos analizando con una profundidad de 2 plies. O si un engine dice que ha analizado con una profundidad de 14 plies, se puede “traducir” como que ha profundizado a 7 movimientos.

Una vez dicho esto, supongamos que un engine quiere decidir cuál es el mejor movimiento disponible a una profundidad de 3 plies (es decir, movemos nosotros, mueve el contrario, y respondemos). El árbol de variantes (el esquema de todos los posibles movimientos hasta una determinada profundidad) tendría un aspecto similar a este:

 
Por supuesto, un árbol de variantes de una posición cualquiera es mucho más profuso, pero por razones prácticas se ha reducido drásticamente. El número “23”, abajo a la izquierda, debajo de la celda en la que pone “e4”, significa:
“Si en la posición actual yo muevo d4 y el contrario mueve d6 y yo respondo e4, entonces la valoración de la posición es de 23 (centésimas de peón, es decir, ligeramente favorable al blanco)”. Y así con el resto. Un dato importante: la función de evaluación sólo se aplica a las posiciones últimas, las que se encuentran en la última fila (llamados leaf nodes).

Vale, supongamos entonces que hemos creado el árbol de variantes hasta la profundidad deseada y que tenemos las puntuaciones de todas (to das) las posiciones resultantes. Lo primero que se nos puede ocurrir es algo como “bueno, cojamos el movimiento que mayor puntuación da a nuestro bando y ya está, es decir, 35, tras jugar d5 en el ply 3”. Para que se dé esa posición, nosotros debemos mover primero d4, entonces el negro debe mover Cc6, y vualá, hacemos d5 y a seguir jugando. Pero estamos obviando algo: el negro no tiene ninguna obligación de responder Cc6 a nuestro d4. De hecho, lo que tratará de hacer el negro tras cada movimiento nuestro, es precisamente elegir el movimiento que menos le perjudique (o más le beneficie). Es decir, si nosotros movemos d4, precisamente el negro evitará mover Cc6, porque él es tan buen jugador como nosotros, y verá que tras d4, Cc6, d5 da ventaja al blanco.

De modo que si el blanco mueve d4, ¿qué movimiento elegirá el negro? Pues el que deje la peor mejor opción al blanco, teniendo en cuenta que el blanco moverá maximizando sus posibilidades. Si hemos llegado hasta aquí, veremos enseguida que la respuesta del negro a d4 del blanco será 0-0, que deja como mejor opción del blanco Tb1, con -12 (ligera ventaja negra). Es decir, a la posición que se da tras d4 y 0-0 se le asigna una valoración de -12, y esta valoración no la hemos sacado de aplicar la función de evaluación a dicha posición sino de las valoraciones de las posiciones derivadas.
La misma técnica se aplica sobre cada serie de movimientos que tienen un padre común, y llegaríamos a tener un diagrama como el siguiente:

 
Las valoraciones de las posiciones tras el ply 2, en marrón (sí, soy un petardo eligiendo colores), se obtienen maximizando los valores que ha devuelto la función de evaluación en el ply 3 a las posiciones hijas, en azul. Sin embargo, los valores de las posiciones tras el ply 1 se obtienen minimizando las puntuaciones del ply 2 (por eso a esta técnica se la llama mini-max). Ocurre que cada vez que subimos o bajamos un ply, cambia el bando que mueve. Así, cuando mueve el blanco, trata de maximizar la puntuación, mientras que el negro trata de minimizarla. Finalmente, aplicando el mismo sistema, llegamos a la conclusión de que la valoración de la posición a tres plies de profundidad es de 11 centésimas de peón (ligera ventaja blanca).

Nótese que tal y como comentaba, la función de evaluación sólo se usa en las posiciones finales [por cierto, en todo este proceso estamos suponiendo que nuestra función de evaluación es “la verdad”. Evidentemente, ninguna función de evaluación es perfecta (aunque algunas se acercan bastante), pero es que sencillamente es lo que tenemos], y es a partir de estos valores como se toma la decisión del mejor movimiento.
También aquí vemos por qué el generador de movimientos debe ser capaz también de deshacerlos. Al comenzar a analizar, lo primero que se hace es generar los movimientos disponibles. Si entonces no nos encontramos en el ply de profundidad deseado, volvemos a generarlos hasta que se cumpla la condición. De modo que la función de búsqueda (que es como se suele llamar, ya que se encarga de buscar el mejor movimiento en el árbol de variantes) es recursiva, llamándose a sí misma y generando los movimientos posibles hasta llegar a la profundidad deseada. Entonces se aplica la función de evaluación a las posiciones, y se deben deshacer los movimientos para seguir moviéndonos por el árbol de variantes.

Bueno, para una introducción puede valer. Evidentemente tanto sobre la generación de los movimientos como sobre la evaluación y la búsqueda hay muchísimo más que contar, pero creo que con esto puede ser suficiente para hacernos una primera idea de cómo funcionan estos programitas. En próximas entradas trataré de explicar algunos de estos asuntos con más detalle.

PS: si alguien tiene curiosidad por ver el código de alguno de estos programas, hay bastantes, y algunos muy fuertes, que están bajo licencia GPL o open source. En particular servidor tiene debilidad por secondchess, un engine que se basa en un código en C escrito por Pham Nguyen llamado firstchess, con fines puramente didácticos. El código de secondchess se puede encontrar aquí (muy comentado y con un nivel de juego medianamente interesante, en especial teniendo en cuenta lo sencillo que es).

jueves, 22 de marzo de 2012

Desahogo matemático

Acabo de tener la típica reunión con mi director de tesis (en adelante "el chino") en la que nos hemos gritado mutuamente (algo relativamente normal) y necesito desahogarme, así que voy a hablar de un par de afirmaciones matemáticas cuestionables que he oído a muchos profesores (entre ellos al chino).

La primera es algo que asocio con los ingenieros porque sólo se lo he visto hacer a ingenieros, aunque admitiré de buena gana estar equivocado si alguien me muestra pruebas. Es una queja que algunos me habrán oído ya, comienza cuando alguien escribe algo así en la pizarra:


Donde \(\phi\) es una magnitud cuya variación en \(x\) queremos conocer. Obviando el hecho de poner \(dx\) como si fuera un infinitesimal (Leibnitz estaría orgulloso), el problema es que luego dicen:
Restando el valor la izquierda \(\phi\) del valor a la derecha \(\phi + \frac{\partial \phi}{\partial x} dx \) y dividiendo por el intervalo \(dx\), obtenemos que la variación es  \(\frac{\partial \phi}{\partial x} \)
¡Y se quedan tan anchos! Muchas veces he tratado de explicar que ya están suponiendo que la variación es esa cuando hacen el dibujo, y que hacer el proceso de restar y luego dividir no hace más que recuperar la suposición inicial. No han hecho más que dar una vuelta para llegar a algo que ya sabían.

Lo curioso es que hacerlo bien no es más difícil, todo lo contrario:




En este caso, la variación es \( \frac{\phi(x+\Delta x)-\phi(x)}{\Delta x}\), tomando el límite y aplicando la definición de derivada parcial llegamos al mismo resultado, esta vez de verdad.

Que conste que no me parecía mal que dijesen el resultado final sin más, lo que me molesta es que den esa "vuelta" para nada.

***


Otra cosa que he oído muchas veces es eso de "si tienes n incógnitas necesitas n equaciones para resolverlas". De hecho ese fue el detonante de una discusión con el chino.

No recuerdo de qué problema hablábamos, pero si recuerdo que me salió con eso y como ya me tenía de mal humor le dije con sequedad que eso no era cierto. Se quedó mirándome con odio un momento y me preguntó "¿cómo que no es cierto?" Con tranquilidad, escribí lo siguiente en la pizarra:

\begin{aligned} x^2+y^2=0 \end{aligned}

"Dos incógnitas, una ecuación y una única solución, x=y=0", dije sabiendome ganador.

Se quedó pensando y me dijo "hombre claro, pero esa es la solución trivial". No me esperaba que me saliera con esas, de haberlo sabido le habría escrito:

\begin{aligned} x^2+y^2+3-2x-4y=0 \end{aligned}

Que no es otra cosa que \( (x-1)^2+(y-2)^2=0\) camuflado y que, evidentemente, tiene solución única, x=1, y=2. No sé si consideraría que esa solución también es "trivial", aunque según esa lógica, todas las soluciones lo son. En cualquier caso, también me dijo que no era una ecuación que tuviese sentido físico, y que a menos que tuviese un ejemplo de una, era mejor que me callase (más o menos con esas palabras).

Ahí sí que no supe qué decirle. No conozco sistema de ecuaciones que provenga de un problema físico real que tenga más incognitas que ecuaciones y que tenga solución única ¿alguna idea?




martes, 20 de marzo de 2012

10 colores

El otro día leí en algún sitio que los humanos usamos un sistema de numeración de base 10. No es una cita exacta, así que es posible que no dijese "humanos", pero lo que sí recuerdo es que ponía diez con cifra.

Creo que nunca antes lo había visto así escrito. Lo que es seguro es que es una afirmación totalmente correcta, pero que da muy poca información: todos los sistemas de numeración son en base 10, al menos, todos los de base mayor que uno.

Otra cosa es si decimos "base diez". En ese caso puede interpretarse que "diez" es el número que viene tras el "nueve", que a su vez sigue al ocho, etc. Aunque también puede interpretarse como la versión escrita de 10 (en hexadecimal he usado alguna vez "diez" para referirme al 10h). En este caso, decir "base diez" sería ambiguo, pero es mejor una ambigüedad que una frase púramente vacía de contenido (¿o no?).

El caso es que la cosa se pone complicada si uno quiere eliminar la ambigüedad. Según Wikipedia:

Para indicar en qué sistema de numeración se representa una cantidad se añade como subíndice a la derecha el número de símbolos que se pueden representar en dicho sistema. 
Es decir, habría que decir "base \(10_{10}\)", pero entonces nos quedaría la duda de en qué base está el subíndice. Esta podría ser una buena ocasión para usar los números romanos, que ya que gastamos tiempo y memoria en aprenderlos, hay que darles uso. Además, "base X" tiene un toque a película de ciencia ficción de los 50 que me gusta.

Otro al que le gusta la idea

Siguiendo con cosas ambiguas, hace poco me di cuenta de una tontería que me llamó la atención. Muchas veces, en un seminario o reunión alguien conecta un proyector y, sin apagar las luces, comienza una presentación. Esto sólo funciona si la iluminación de la sala no es muy fuerte, pero la realidad es que muchas veces se dan las condiciones para ello.

El caso es que la pantalla es blanca y, por más que la iluminemos, no va a dejar de ser blanca. Por tanto, los caracteres en negro son en realidad blancos, pero de un blanco menos luminoso que los alrededores.

Como esto, pero diferente
Como digo, es una tontería y no creo que sorprenda a nadie; pero no deja de ser llamativo que pasemos tan rápidamente, y sin darnos cuenta, de ver blanca una cosa a verla negra. Supongo que algo ayude el hecho de que nuestras pupilas se cierren un poco debido al incremento de iluminación y la cantidad de luz que llegue de las partes "negras" de la pantalla sea en realidad algo inferior a la que llegaba con el proyector desconectado Sin embargo no creo que eso afecte mucho, al fin y al cabo la sala ya estaba iluminada inicialmente.