Trabajo Final de Licenciatura en Física

Correlaciones y Memoria en el Ajedrez

Autora: Ana Laura Schaigorodsky Directores: Orlando V. Billoni - Juan I. Perotti

Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba

Córdoba, 27 de Marzo de 2013

Dedicado a la memoria de Cecilia Bogudloff.

Agradecimientos A Orlando Billoni y Juan Perotti por su inconmensurable apoyo y confianza. A Carlos, Marga y Emilia, mis padres y hermana, por su eterno cariño y paciencia. A Matías, por estar siempre a mi lado. A mis amigos y compañeros, en especial a Belén, Gus, Xime y Rafa. A los profesores de FaMAF que me han enseñado tanto, en especial a Pancho, Omar, Ricardo y Anfi.

Resumen Un estudio reciente realizado por Blasius y Tönjes [1] ha atraído la atención de la comunidad científica, pues agrega el juego del Ajedrez a la lista de sistemas cuyo comportamiento se ajusta a una ley de tipo Zipf-Pareto. Específicamente, en el trabajo mencionado se muestra que la popularidad de las partidas se distribuye de acuerdo a leyes de potencias. Este escenario plantea nuevos interrogantes acerca de los mecanismos particulares que generan este tipo de distribución en el juego del ajedrez. En este trabajo se extenderá el análisis de dichos resultados empleando herramientas de la mecánica estadística para determinar la existencia de correlaciones de largo alcance en secuencias de partidas. Con este fin, se construyen series temporales a partir de una base de datos de partidas de ajedrez ordenada cronológicamente, similar a la empleada en el trabajo antes mencionado. Los resultados obtenidos indican que el sistema presenta correlaciones de largo alcance y que su existencia está determinada por la presencia de jugadores de alto nivel. Estos resultados son semejantes a los encontrados en otros sistemas complejos que se ajustan a una ley de Zipf, como lo es lengua escrita[2], indicando que los mecanismos que dan origen a esta ley deben tener en cuenta efectos de memoria.

Clasificación: 02.50.Ey Stochastic Processes - 01.80.+b Physics of Games ans Sports - 05.45.Tp Time Series Analysis. Palabras Calves: Serie Temporal - Ajedrez - Hurst - DFA - Rango Reescalado Correlaciones de Largo Alcance - Memoria. 5

Abstract A recent study by Blasius and Tönjes[1] has attracted the attention of the scientific community by adding the game of chess to the list of systems whose behaviour follows a Zipf-Pareto’s law. Specifically, in the study the authors find that the game popularity is distributed following with power laws. This scenery gives rise to new questions about the particular mechanisms that generate this kind of distribution in the game of chess. In this study we will extend the analysis of those results by employing tools of statistical mechanics to determine the existence of long-range correlations in game sequences. To that end, time-series are constructed using a chronological ordered chess data base, similar to the one used in the previously mentioned study. Our results indicate that the system exhibits long-range correlations and that its existence is determined by the presence of high level players. This result is similar to those found in other complex systems that follow Zipf’s law, like the written language[2], indicating that the mechanisms that give rise to this law have to take in to account memory effects.

7

Índice general 1. Introducción

11

2. Ajedrez

13

2.1. Reglas y Aspectos Generales del Juego . . . . . . . . . . . . . . . . . .

13

2.2. La Historia del Ajedrez . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3. Sistema de puntuación Elo . . . . . . . . . . . . . . . . . . . . . . . . .

17

3. Conceptos y Definiciones

21

3.1. Estadística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.2. El efecto Hurst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.3. Procesos Auto-similares

. . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.4. Incrementos Estacionarios en Procesos Auto-similares . . . . . . . . . .

27

3.5. Cálculo del exponente de Hurst H . . . . . . . . . . . . . . . . . . . . .

29

3.5.1. Método de Rango Reescalado R/S . . . . . . . . . . . . . . . .

30

3.5.2. Método DFA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.6. Ley de Zipf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.6.1. La Ley de Zipf en el Ajedrez . . . . . . . . . . . . . . . . . . . .

34

4. Resultados

41

4.1. Base de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.2. Estudio General de la Base de Datos . . . . . . . . . . . . . . . . . . .

42

9

10

ÍNDICE GENERAL 4.3. Distribuciones Libres de Escala . . . . . . . . . . . . . . . . . . . . . .

47

4.4. Análisis de Correlaciones . . . . . . . . . . . . . . . . . . . . . . . . . .

50

5. Conclusiones

67

A. Apéndice

69

A.0.1. Implementación del Método de Rango Reescalado . . . . . . . .

69

A.0.2. Implementación del Método de DF A . . . . . . . . . . . . . . .

71

1. Introducción El estudio de sistemas biológicos y sociales complejos ha atraido la atención de muchos científicos en el área de la física en las últimas décadas, hecho reflejado en la cantidad de trabajos publicados por los mismos en dichas áreas de investigación. Entre los sistemas estudiados se puede mencionar la distribución de votos en elecciones [3], popularidad [4], crecimiento poblacional[5], movimiento colectivo de aves[6] y dinámica y población de bacterias [7], por mencionar algunos tópicos significativos. Un aspecto poco estudiado debido a la falta de datos suficientes es la forma en la que ciertos agentes aprenden a tratar con sistemas de alta complejidad [8]. En particular, este aspecto está estrechamente relacionado con la toma de decisiones, donde un individuo (o grupo de individuos) tiene que elegir un curso acción entre una gran variedad de alternativas posibles. Este problema es ubicuo, ya que es posible identificarlo en una gran variedad de escenarios, los que comprenden decisiones personales, de negocios, en manejo de empresas, o en la política. Este es un problema extremadamente complejo dado el gran número de factores que influyen en un proceso de decisión, sumado a la enorme cantidad de posibilidades que usualmente se presentan a la hora de elegir. Un entendimiento de estos problemas en términos de leyes de estadíticas constituye un enorme desafío. En este contexto los juegos de mesa son muy estudiados actualmente[1, 9], debido a la existencia registros y de la disposición de bases datos suficientemente grandes como para realizar estudios estadísticos. En un juego de mesa usualmente dos oponentes deben decidir la continuación de una partida de entre un gran número de variantes determinadas por las reglas del juego. En particular el ajedrez ha tenido siempre un lugar privilegiado dentro de los juegos de mesa debido a su complejidad, siendo además necesario un arduo entrenamiento a fin de lograr un buen desempeño. Un trabajo reciente de Blasius et. al [1] puso en evidencia un nuevo aspecto del juego que despertó mucho interés en la comunidad científica [10, 11]. Estudiando cierto 11

12

CAPÍTULO 1. INTRODUCCIÓN

registro de partidas encontraron que, al ordenar las partidas de acuerdo a su popularidad, estas siguen una ley de Zipf. El hecho de que existan partidas populares no es sorprendente dado que las aperturas, es decir los primeros movimientos, son comunes a muchas partidas, sin embargo el hecho de que sigan una ley tipo Zipf-Pareto causa asombro. La ley de Zipf se ha observado en sistemas de naturaleza muy diversa incluyendo la frecuencia de palabras de un cuerpo literario[12, 13, 14], la distribución del producto bruto interno en paises[15], y la distribución de tormentas solares[16], por citar algunos ejemplos. A la par de la diversidad de sistemas en los cuales la ley se observa, existe un gran número de modelos estadísticos que logran explicarla[17], aún cuando los mecanismos particulares que dan origen a la ley quedan muchas veces ocultos al punto de poner en duda si esta ley posee algún significado profundo[18]. Sin embargo, un aspecto muy interesante ha sido observado en cuerpos literarios donde la ley de Zipf se manifiesta. Al estudiar una serie temporal asociada a secuencias de palabras, Montemurro y Pury [2] detectaron correlaciones de largo alcance en la serie. El origen de estas correlaciones es aún desconocido y continúa siendo estudiado en la actualidad[19]. La respuesta de muchos sistemas puede ser considerada como una secuencia estacionaria de símbolos que guardan cierta correlación, en particular, este tipo de análisis se vió impulsado en las últimas dos décadas a partir del estudio de secuencias de ADN[20]. Las secuencias simbólicas requieren de un mapeo previo a una serie temporal para lo cual se debe establecer previamente una función de asignación[19] la cual dependerá del tipo de correlaciones que se desee estudiar. Una vez obtenida la serie temporal es posible emplear diversas técnicas para el estudio de correlaciones como lo son el análisis de rango reescalado (R/S) o el detrended fluctuation analysis DF A. En este trabajo se utilizó una base de datos con una secuencia de partidas de Ajedrez ordenadas cronológicamente, similar a la empleada en el trabajo de Blasius y Tönjes[1], se estableció un mecanismo de para asignar una serie temporal a esta secuencia y luego se analizaron dichas series con las técnicas R/S y DF A a fin de determinar el tipo correlaciones presentes en las mismas. Previamente se realizó un estudio estadístico de la base de datos y se reprodujeron algunos resultados de Blasius y Tönjes.

2. Ajedrez 2.1.

Reglas y Aspectos Generales del Juego

El Ajedrez es un juego de mesa de estrategia entre dos jugadores y toma lugar en un tableto con 64 cuadrados en una cuadrícula de 8x8. Cada jugador comienza con 16 piezas: un rey, una dama, dos torres, dos caballos, dos alfiles y ocho peones, cada una de las cuales se mueve de forma diferente. Las piezas son utilizadas para atacar y capturar las piezas del oponente, con el objetivo de realizar “jaque mate” al rey del oponente colocándolo situación de inminente captura. El curso del juego esta dividido en tres etapas: apertura, medio juego y final. El tablero de ajedrez consiste en ocho filas, denotadas por números del 1 al 8, y ocho columnas, denotadas por letras de “a” a “h” (Figura 2.1). Las piezas se dividen convencionalmente en blancas y negras, y los jugadores son referidos como “las blancas” y “las negras”.

Figura 2.1: Posición inicial de las piezas en el tablero de ajedrez.

13

14

CAPÍTULO 2. AJEDREZ

El jugador blanco siempre mueve primero. Un jugador no puede realizar ningún movimiento el cual deje en situación de jaque a su rey, si un jugador no tiene movimientos legales posibles el juego concluye, ya sea en jaque mate (el jugador sin posibilidad de movimientos legales pierde) si el rey está en situación de jaque, o en ahogado (empate) si el rey no está en jaque. A continuación se describen los movimientos de cada pieza[21]: Rey: puede moverse un cuadrado en cualquier dirección. Esta pieza también tiene un movimiento especial llamado enroque, una sola vez en el juego cada rey tiene permitido moverse dos espacios a lo largo de la primera fila hacia la torre y luego la torre es colocada en el último cuadrado cruzado por el rey. Este movimiento está permitido siempre y cuando ambas piezas no hayan realizado ningún movimiento previo, el rey no se encuentra en situación de jaque y los casilleros que separan al rey y la torre no se encuentran ocupados. Torre: puede moverse cualquier número de casilleros a lo largo de cualquier fila o columna. Alfil: puede moverse cualquier número de casilleros diagonalmente. Dama: combina el poder del alfil y la torre. Caballo: puede moverse en forma de “L”, dos casillero verticalmente y uno horizontalmente, o uno verticalmente y dos horizontalmente. El caballo es la unica pieza que puede saltar sobre otras piezas. Peón: puede moverse hacia adelante a lo largo de la misma columna de a un casillero a la vez si el mismo está desocupado, excepto en su primer movimiento donde tiene permitido desplazarse dos cuadrados; o puede moverse a un casillero ocupado por una pieza del oponente si se encuentra diagonalmente a un solo movimiento de distancia. A su vez el peón posee una habilidad de captura especial llamada “captura al paso” en la cual, si un peón se desplaza dos casilleros en su primer movimiento dejando a éste junto a un peón del adversario, puede ser capturado como si hubiera avanzado solo un casillero. El peón también posee la capacidad de promoción, cuando avanza hasta la octava fila debe ser intercambiado por otra pieza a elección del jugador. Las jugadas y posiciones en el ajedrez son registrados mediante una notación especial, llamada notación algebraica la cual consiste de una letra mayúscula que indica

2.1. REGLAS Y ASPECTOS GENERALES DEL JUEGO

15

la pieza en movimiento (K para el rey, Q para la dama, R para la torre, B para el alfil y N para el caballo) más la coordenada de destino de la misma. Por ejemplo, Qg5 significa que la dama realiza un movimiento al casillero g5 (fila 5, columna g). La letra P que indica al peón no se utliza, por lo tanto e4 simplemente significa que el peón se desplaza hacia el casillero e4. En la situación particular donde dos piezas de la misma especie pueden moverse al mismo casillero se incluye una letra adicional indicando la columna de partida, por ejemplo Ngf3 significa que el caballo de la columna g realiza un movimiento hacia la posición f3. Si una pieza realiza una captura en uno de sus movimiento, se incluye una “x” antes del casillero de destino, entonces Bxf3 significa que el alfil captura la pieza ubicada en f3. Cuando un peón realiza una captura se utiliza la designación de la columna de la cual parte en lugar de la inicial de la pieza, y el número de fila es omitido en caso de ser inequívoco, por ejemplo, exd5 significa que el peón en la columna “e” captura a la pieza localizada en d5. El enroque es indicado por las notaciones especiales, 0-0 para el enroque hacia el flanco del rey y 0-0-0 para el enroque hacia el flanco de la reina. A su vez la promoción de un peón es indicado por el movimiento del mismo seguido de la primera letra de la pieza por la cual es intercambiado, por lo tanto d8Q indica que el peón que realiza un movimiento al casillero d8 es intercambiado por la dama. El símbolo “+” indica que el jugador ha colocado al rey del oponente en situación de jaque. Al finalizar la partida “1-0” indica que las blancas ganaron, “0-1” que las negras ganaron y “1/2-1/2” si la partida concluyó en empate. A continuación se muestra un ejemplo de una partida completa registrada entre Garry Kasparov (blancas) y Viktor Kortschnoj (negras) jugada en Islandia en el año 2000 cuyo resultado fué empate:

16

CAPÍTULO 2. AJEDREZ 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

e4 d4 Nc3 Bg5 e5 Be3 Qg4 a3 bxc3 Bd3 Qf4 Ne2 0-0 Bxe2 c4 Bxd4 Qxd4

e6 d5 Nf6 Bb4 h6 Ne4 Kf8 Bxc3+ c5 h5 Qa5 Nxc3 Nxe2+ Nc6 cxd4 Nxd4 Bd7

18. 19.

cxd5 exd5 Bf3 Bc6

1/2-1/2

2.2.

La Historia del Ajedrez

El juego del ajedrez ha fascinado a la humanidad por más de 1500 años. El predecesor más similar tuvo origen en el norte de la India con el nombre de chaturanga 1 , no obstante sus comienzos son tan remotos que resulta imposible determinar su origen exacto. La primera referencia escrita al juego es en un poema de finales del Siglo VI. La teoría más probable es que el chaturanga se expandiera hacia el este en dirección a China y Japón, y hacia el oeste a Persia, donde pasó a llamarse shatranj 2 [22]. Es desde Persia donde el ajedrez comienza a evolucionar hasta lograr su forma El término chaturanga significa cuatro secciones y refiere a una formación militar. Llevaba este nombre ya que se jugaba entre cuatro personas y en un tablero de 74 casillas. 2 El término shatranj se deriva de la palabla chaturanga. En la cultura popular Persa se escribía algunas veces como sad (’cien’) + ranj (’preocupaciones’). 1

2.3. SISTEMA DE PUNTUACIÓN ELO

17

actual. Esta versión más parecida al juego moderno fue transmitida primero a España y de allí al resto de Europa. La diferencia más grande entre el shatranj y el ajedrez actual es la movilidad de las piezas equivalentes a la dama y el alfil, las cuales sólo podían avanzar al igual que los peones, y la no existencia del enroque. Por esta diferencia de movilidad de estas piezas tan claves en el ajedrez actual, las aperturas eran, en comparación, increíblemente lentas. Hacia el Siglo XII el juego del ajedrez se había expandido prácticamente en todo el continente europeo, y dejó de ser simplemente un entretenimiento para convertirse en un atractivo para el arte y la ciencia. A finales del Siglo XV, con la finalidad de agilizar las aperturas, la movilidad de algunas piezas cambió, el peón ahora podría avanzar dos posiciones en el primer movimiento, y la dama y el afil adquirieron las capacidades de movilidad de la actualidad. Debido a que la reina se convirtió en la pieza más poderosa la nueva versión del juego fue apodada en algunos libros de los Siglos XV y XVI “ajedrez de la dama”. Entre los Siglos XVII y XIX, con la llegada del movimiento cultural e intelectual europeo que trajo consigo la Ilustración y la enmancipación del pensamiento, el ajedrez comienza a desligarse de las doctrinas medievales y se establece como el juego predilecto de la clase intelectual[22], al mismo tiempo que comienza a atraer cada ver más la atención de la clase aristocrática y las cortes reales, a las que fueron invitados los jugadores más prominentes de la época. A medida que el juego cobraba popularidad se establecieron ciertas reglas que persisten en la actualidad, como la limitación del tiempo de juego, el enroque y las reglas de ahogado (o stalemate) en la que el juego termina en empate, hasta entonces variaba dependiendo de la época y zona geográfica: victoria para el jugador en posición de tablas, el mismo solo perdía el turno, o simplemente no estaba permitido, entre otras posibilidades.

2.3.

Sistema de puntuación Elo

A través de la historia hubo numerosos intentos por determinar un sistema que fuera capaz de puntuar las capacidades de los jugadores. En 1970 la Federación Internacional de Ajedrez, FIDE, implementó un sistema de puntuación llamado Elo que utiliza un método estadístico para calcular los niveles relativos de habilidad de los jugadores. Este método fue inventado por el físico y ajedrecista aficionado Árpád Élő, y siendo aplicado

18

CAPÍTULO 2. AJEDREZ

también a otras formas de competición como scrabble y juegos de rol de participación masiva por internet como World of Warcraft. El problema de la calificación de los jugadores es un problema que cae dentro del área de la estadística del modelado de ’comparación de pares’, cuyos datos se obtienen de cualquier resultado que indique preferencia por un objeto sobre otro. En el caso ajedrez los resultados de los partidos no son mas que la consecuencia de la comparación entre dos jugadores para determinar cuál de ellos es el ’preferido’ (o si no existe ’preferencia’ como en el caso del empate). A partir del estudio de torneos pasados, Élő observó que la distribución de rendimientos, esto es, la distribución de probabilidades de que un jugador se desempeñe a un cierto nivel, era similiar a la de una distribución normal. Una de las ventajas de utilizar la distribución normal para modelar los desempeños de los jugadores es que la diferencia entre las distribuciones de rendimiento de dos jugadores es también una distribución normal, solo que más dispersa3 [23]. En la actualidad la Federación de Ajedrez Estadounidense (USCF) utiliza la distribución logística en lugar de la normal, a pesar de que al analizar datos de comparación de pares no existe una diferencia significativa si se asume una distribución normal o logística para las diferencias entre los rendimientos de los jugadores[24]. En el sistema de Elo cada jugador posee un puntaje numérico el cual no es calculado de forma absoluta sino que es estimado a partir de victorias, derrotas y empates en enfrentamientos contra otros jugadores. Calculando la diferencia entre los Elos de dos jugadores es posible estimar el resultado esperado del partido. Si un jugador A que posee un Elo RA se enfrenta a un jugador B con Elo RB , las puntuaciones esperadas de los jugadores serán, 1 EA = (R 1 + 10 B −RA )/400 1 EB = , (R 1 + 10 A −RB )/400 donde las puntuaciones que un jugador puede obtener en un partido son 1 si el jugador gana, 21 si el juego termina en empate y 0 si pierde. De esta forma una diferencia de 200 puntos significa que el jugador de mayor Elo posee un puntaje esperado de 0,75, que es la probabilidad de victoria Pv más la mitad de probabilidad de empate Pe , ya que en el sistema de Elo un empate se considera media victoria más media derrota, es Desviaciones estándar de las distribucines obtenidas por Élő: σ = 200 puntos para la distribución √ individual de un jugador y σ = 2 200 puntos para la distribución de dos jugadores. 3

2.3. SISTEMA DE PUNTUACIÓN ELO decir, EA = Pv +

19

Pe . 2

Una de las contribuciones más importantes de Élő fue la introducción de un algoritmo simple que actualiza las calificaciones de los jugadores en base a los resultados de un torneo. Si el jugador en cuestión supera el puntaje esperado su Elo aumenta, y en caso contrario disminuye. Estas actualizaciones se realizan de manera incremental y existe un límite máximo para los ajustes de los Elos de los jugadores por partido llamado Kfactor, el cual depende de la categoría (K = 16 Elo para maestros y K = 32 Elo para jugadores menos expertos). Suponiendo que un jugador A posee un puntaje esperado de EA puntos, pero en la realidad obtuvo SA , su actualización de Elo será, ′ RA = RA + K · (SA − EA ).

La escala de puntuaciones tiene un límite mínimo en cero, y por más que el máximo no está limitado, sería inaudito que un jugador excediera los 3000 Elo. En la actualidad, los jugadores de ajedrez poseen Elos menores a 2900, mientras que, debido al desarrollo de las reglas eurísticas, el puntaje de los motores de ajedrez 4 supera los 3000 Elo[9]. El sistema de puntuación de Elo es utilizado por FIDE y USCF para clasificar tanto los torneos como los jugadores en categorías. La FIDE clasifica los torneos considerando el promedio de Elo de los jugadores. Las categorías cambian cada 25 puntos, comenzando con la categoría 1 con Elos de 2251 a 2275, hasta la categoría 22 con Elos superiores a 2776 para los hombres, y las mismas categorías para el caso de las mujeres pero con 200 puntos menos, por lo tanto la correspondiente categoría 1 sería de 2051 hasta 2075. Por otra parte la Federación de Ajedrez Estadounidense clasifica a los jugadores en 14 categorías según su Elo, desde la categoría A (Elos de 100 a 199) hasta la categoría Senior Master (Elo 2400 ó superior) en incrementos de 200 Elo.

Un motor de ajedrez es un programa de computadora el cual calcula posiciones y movimientos de ajedrez y que a su vez se comunica con una interfaz gráfica para usuarios. 4

3. Conceptos y Definiciones 3.1.

Estadística

Un proceso estocástico (P.E.) es una colección de variables aleatorias ordenadas {X(t)}t∈T , donde T ⊆ R, t es un parámetro (generalmente asociado al tiempo) y X(t) representa el estado del proceso en el instante t. Si T es un conjunto numerable, entonces el proceso estocástico se dice que es en tiempo discreto, en caso contrario se dice que es en tiempo contínuo. Uno de los resultados de la estadística más utilizados de forma automática, y sin tomar cuidado de las condiciones bajo las cuales se deriva, es el que establece que la varianza del valor medio de una muestra es igual a la varianza de una observación dividido el tamaño de la muestra, es decir, dado un conjunto de observaciones independientes ordenadas X1 , ..., XN con media µ = E(Xi ) y varianza σ 2 = var(Xi ) = E[(Xi − µ)2 ], P donde E[Xi ] representa el valor de espectación de Xi , la varianza de X = n1 ni=1 Xi es var(X) =

σ2 n

(3.1)

A fin de estudiar las condiciones bajo las cuales esta ecuación es válida, se considera un conjunto de observaciones realizadas aleatoriamente {Xi : i = 1, ..., n}, donde el índice i denota un orden natural como por ejemplo tiempo o posición. De esta forma X1 , ..., XN son variables aleatorias que comparten la misma distribución marginal F . No es complicado establecer las condiciones bajo las cuales la Ec. (3.1) es válida 1. La media µ = E(Xi ) existe y es finita. 2. La varianza σ 2 = var(Xi ) existe y es finita. 3. X1 , ..., XN son no correlacionados, es decir ρ(i, j) = 0 21

i 6= j

22

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

donde ρ(i, j) =

γ(i, j) σ2

es la autocorrelación entre Xi y Xj , y γ(i, j) = E[(Xi − µ)(Xj − µ)] es la autocovarianza entre Xi y Xj . Las suposiciones 1 y 2 dependen solo de la distribución marginal F y es relativamente simple verificar su cumplimiento al momento de realizar un experimento. La suposición 3 resulta ser la más problemática. En ciertas situaciones se considera que la dependencia entre las observaciones es lo suficientemente débil como para ser despreciable a los fines prácticos. Sin embargo esto no es siempre posible, ya que correlaciones significativas pueden producirse a pesar de las precauciones tomadas. Es por esto que es de importancia estudiar cómo la Ec. (3.1) es afectada cuando las observaciones están correlacionadas. Con el fin de que X n sea significativo, se asume la media µ = E(Xi ) constante. La Ec. general de la varianza es var(X) =

n n 1 X σ2 X γ(i, j) = ρ(i, j). n2 i,j=1 n2 i,j=1

(3.2)

Si las correlaciones para i 6= j suman cero, esto es, n X

ρ(i, j) = 0,

(3.3)

i6=j

entonces

n X

ρ(i, j) = n

i,j

y la Ec. (3.1) resulta válida. Es decir, este es el caso donde X1 , ..., XN son no correlacionados. Si la Ec.(3.3) no se cumple la varianza de X es var(X) =

σ2 [1 + δn (ρ)] n

(3.4)

con un término de corrección distinto de cero δn (ρ) =

1X ρ(i, j). n i6=j

(3.5)

Si el proceso estocástico es estacionario la media µ = E(Xi ) es constante y las correlaciones ρ(i, j) solo dependen de la separación |i − j|, entonces es posible escribir

3.1. ESTADÍSTICA

23

la Ec. (3.5) de forma más simple de la forma δn (ρ) = 2

n X

k=1

!

k 1− ρ(k). n

(3.6)

Es importante también estudiar el comportamiento asintótico de var(X) cuando n → ∞. La varianza de X es proporcional a n−1 siempre y cuando δ(ρ) = n→∞ l´ım δn (ρ) = n→∞ l´ım

1X ρ(i, j) n i6=j

(3.7)

exista, sea finito y mayor a -1. Entonces se obtiene, para el comportamiento asintótico, var(X) ≈

σ2 σ2 [1 + δ(ρ)] = c(ρ) , n n

(3.8)

donde ≈ significa asintóticamente y c(ρ) = 1 + δ(ρ). La mayoría de las series temporales en la literatura exhiben este comportamiento. Los más conocidos son los procesos ARMA (autoregressive moving average) y los procesos de Markov[25]. La Ec. (3.8) es una generalización de la Ec. (3.1) ya que permite una contante c(ρ) distinta de 1. Sin embargo esta generalización no es suficiente, existen conjuntos de datos para los cuales la varianza de X difiere de la Ec. (3.1) no solo en una constante, sino también en la velocidad a la cual converge a cero. La forma más simple de modelar este comportamiento es considerar un decaimiento más lento proporcional a n−α para algún α ∈ (0, 1), es decir, σ2 var(X) ≈ c(ρ) α , (3.9) n donde ahora la constante c(ρ) está definida como: c(ρ) = n→∞ l´ım nα−2

X

ρ(i, j).

(3.10)

i6=j

La relación entre la Ec. (3.9) y la estructura de las correlaciones se observa simplemente al considerar correlaciones dependientes solamente de la distancia |i−j| (proceso estocástico estacionario). Analizando las Ec. (3.6) y (3.10) se concluye que el comportamiento asintótico de la suma de todas las correlaciones con separaciones −n+1, ..., n−1 debe ser proporcional a n1−α n−1 X

k=−(n−1)

ρ(k) ≈ constante · n1−α ,

(3.11)

24

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

lo que implica que

P∞

−∞

ρ(k) diverge, ya que α < 1.

Especificamente la Ec. (3.11) es válida si ρ(k) ≈ cρ |k|−α

(3.12)

cuando |k| → ∞, y donde cρ es una constante positiva. En este caso, como las correlaciones decaen más lentamente que 1/n no existe escala caracerística tal que las mismas puedan ser despreciadas. La interpretación intuitiva de la Ec. (3.12) es que el proceso tiene memoria de largo alcance. Es decir, la dependencia entre los eventos separados por una gran distancia disminuye lentamente con el aumento de |k|. Un proceso estacionario cuyas correlaciones decaen lentamente según la Ec. (3.12) es llamado proceso estacionario con memoria de largo alcance o dependencia de largo alcance. De otra manera, un proceso estacionario Xt es llamado estacionario con memoria de largo alcance o dependencia de largo alcance, o correlaciones de largo rango, si existe un número real α ∈ (0, 1) y una constante cρ > 0 tal que ρ(k) = 1. k→∞ cρ k −α l´ım

(3.13)

La definición dada por la Ec. (3.13) es una definición asintótica, y como tal solo describe el comportamiento de las correlaciones cuando las distancias tienden a infinito; cada correlación individual puede ser arbitrariamente pequeña. La densidad espectral f (λ) de una función de autocorrelación ρ(k) puede ser definida como ∞ σ2 X ρ(k)eikλ , f (λ) = 2π k=−∞ donde λ es la frecuencia. Entonces, la Ec. (3.12) implica que f (λ) ≈ cf |λ|α−1 = cf |λ|−β

(3.14)

cuando λ → 0 y donde cf es una constante positiva.

3.2.

El efecto Hurst

Desde la antigüedad el río Nilo ha sido conocido por su comportamiento característico a largo plazo. Extensos períodos de sequía, durante los cuales los niveles del río tendían a ser bajos, seguidos por extensos períodos de crecidas, con niveles altos.

3.2. EL EFECTO HURST

25

De forma general la serie temporal de niveles del Nilo resulta estacionaria. Al observar intervalos de tiempos reducidos, parecen surgir ciclos o tendencias locales. Sin embargo la serie completa no exhibe ciclos persistentes (Figura 3.1).

Figura 3.1: Nivel mínimo anual del río Nilo (622-1281 d.C.).

El hidrólogo Harold E. Hurst advirtió este compotamiento al investigar el problema de regularización del flujo del Nilo (1951). Más especificamente descubrió que puede ser descrito como sigue: Suponiendo que se desea calcular la capacidad de un reservorio ideal en un intervalo de tiempo (t, t + k), donde por ideal se refiere a que el flujo es uniforme dentro del reservorio, que el nivel al tiempo t+k es igual al nivel al tiempo t y que el reservorio no desborda. A fin de simplificar el problema, se asume que el tiempo es discreto y que no existen pérdidas en el reservorio (por evaporación, derrame, etc.). Denotando al flujo entrante al tiempo i por Xi y al flujo entrante acumulado al tiempo P j por Yj = ji=1 Xi , la capacidad ideal es igual a i i R(t, k) = m´ax [Yt+i − Yt − (Yt+k − Yt )] − m´ın [Yt+i − Yt − (Yt+k − Yt )], 06i6k 06i6k k k

(3.15)

donde R(t, k) es llamado rango ajustado. A fin de estudiar las propiedades independientemente de la escala utilizada, R(t, k) es normalizado mediante v u t+k u1 X 2 S(t, k) = t (Xi − X t,k ) ,

k

i=t+1

(3.16)

26

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

donde X t,k =

1 k

Pt+k

i=t+1

Xi . La razón R/S =

R(t, k) S(t, k)

(3.17)

es el rango reescalado ajustado o estadística R/S. Hurst observó que al graficar el logarítmo de R/S vs. k, para valores considerables de k, log (R/S) se encontraba dispersado alrededor de una recta con pendiente mayor a 21 . En términos probabilísticos esto es log E[R/S] ≈ a + H log(k),

H>

1 2

(3.18)

Hurst descubrió que en el caso del río Nilo, asi como en muchos registros hidrológicos, geofísicos y climatológicos, R/S se comporta como una constante por k H para algún H > 21 . Este es el llamado efecto Hurst. El parámetro α en la Ec. (3.12) está relacionada con el exponente de Hurst H mediante la ecuación α = 2 − 2H[26]. Es decir, H > 1/2 implica que α < 1, y por lo tanto se puede decir que se trata de un proceso con memoria de largo alcance.

3.3.

Procesos Auto-similares

Los procesos auto-similares fueron introducidos por Kolmogorov (1941) dentro de un contexto teórico. Sin embargo, los estadistas ignoraban la reelevancia de dicho concepto hasta que fue introducido por Mandelbrot. No obstante, la idea de auto-similitud es más antigua. Mandelbrot se refiere, por ejemplo, a las pinturas con flujos turbulentos de Leonardo da Vinci las que exhiben torbellinos coexistentes de todos los tamaños y por lo tanto auto-similitud. Una figura geométrica se dice auto-similar de forma determinística si las mismas estructuras geométricas son observadas independientemente de la distancia a la que se la examine. Desde el punto de vista estocástico, la auto-similitud está definida en términos de la distribución del proceso. Un proceso estocástico Yt con parámetro temporal contínuo t se dice auto-similar con parámetro de auto-similitud H si, para todo factor de estiramiento c positivo, el proceso reescalado con escala temporal ct, c−H Yct , es igual en distribución al proceso original, en otras palablas, la distribución posee invariancia de escala. Por lo tanto, recorridos habituales de la muestra son cualitativamente iguales, independientemente de la distancia a la cual se observe. Un proceso estocástico Yt tiene incrementos estacionarios si, para todo k > 1 y tiempos t1 , ..., tk cualesquiera, la distribución de (Yt1 +c − Yt1 +c−1 , ..., Ytk +c − Ytk +c−1 )

3.4. INCREMENTOS ESTACIONARIOS EN PROCESOS AUTO-SIMILARES

27

no depende de c ∈ R. Dada esta definición es posible obtener un resultado de sumo interés. Suponiendo que Yt es un proceso estocástico tal que Y1 6= 0 con probabilidad positiva e Yt es el límite en distribución de la secuencia de sumas parciales normalizadas [nt] 1 X Snt →d Yt Xi = an i=1 an

donde [nt] denota la parte entera de nt, →d significa convergencia en distribución1 , X1 , X2 , ... es una secuencia estacionaria de variables aleatorias, y a1 , a2 , ... es una secuencia de constantes positivas normalizadoras tales que log(an ) → ∞. Entonces existe una constante H > 0 tal que para todo u > 0, l´ım n→∞

anu = uH an

e Yt es auto-similar con parámetro de auto-similitud H y tiene incrementos estaciose narios. Es decir, independientemente del parámetro de estiramiento u elegido, aanu n comporta asintóticamente, para n → ∞, como una ley de potencias con el mismo exponente H. Esto significa que, cuando un proceso es el límite de las sumas parciales normalizadas de variables aleatorias, es necesariamente auto-similar. Por lo tanto se puede decir que el rol de los procesos auto-similares dentro de los procesos estocásticos es análogo al rol central de las distribuciones estables dentro de las distribuciones.

3.4.

Incrementos Estacionarios en Procesos Autosimilares

Dado un proceso auto-similar Yt con parámetro de auto-similitud H, la propiedad Yt =d tH Y1 , donde =d es igualdad en distribuciones, implica el siguiente comportamiento límite de Yt cuando t → ∞: 1. Si H < 0, entonces Yt →d 0. Una secuencia de variables aleatorias X1 , X2 , ... se dice converger en distribución a una variable aleatoria X si, ∀x ∈ R para el cual F es contínua, l´ımn→∞ Fn (x) = F (x), donde Fn y F son las funciones de distribución acumuladas de las variables Xn y X respectivamente. 1

28

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES 2. Si H = 0, entonces Yt =d Y1 . 3. Si H > 0 e Yt 6= 0, entonces |Yt | →d ∞. Analogamente, para t → 0 se tiene: 1. Si H < 0 e Yt 6= 0, entonces |Yt | →d ∞. 2. Si H = 0, entonces Yt =d Y1 . 3. Si H > 0, entonces Yt →d 0.

El rango de H puede ser restringido a H > 0, ya que si los incrementos del proceso auto-similar son estacionarios, entonces el proceso es matemáticamente patológico para valores negativos de H. Más especificamente, para H < 0, Yt no es un proceso mensurable. El aspecto de la función de covarianza γy (t, s) = cov(Yt , Ys ) = E[(Yt −µt )(Ys −µs )] de un proceso auto-similar Yt con incrementos estacionarios es el resultado de considerar H positivo e Y0 = 0 con probabilidad igual a 1. Asumiendo E(Yt ) = 0 a fin de simplificar notación, s < t, y denotando por σ 2 = E[(Yt − Yt−1 )2 ] = E[Y12 ] la varianza del proceso incremental Xt = Yt − Yt−1 , entonces, E[(Yt − Ys )2 ] = E[(Yt−s − Y0 )2 ] = σ 2 (t − s)2H . Por otro lado, E[(Yt − Ys )2 ] = E[Yt2 ] + E[Ys2 ] − 2E[Yt Ys ] = σ 2 t2H + σ 2 s2H − 2γy (t, s), por lo tanto,

1 γy (t, s) = σ 2 [t2H − (t − s)2H + s2H ]. 2

Las covarianzas de la secuencia de incrementos Xi = Yi − Yi−1 (i = 1, 2, 3, ...) son calculadas de forma similar. Utilizando la auto-similitud se obtiene, para la covarianza entre Xi y Xi+k (k > 0), 1 γ(k) = σ 2 [(k + 1)2H − 2k 2H + (k − 1)2H ] 2 para k > 0 y γ(k) = γ(−k) para k < 0. Y por lo tanto las correlaciones están dadas por 1 ρ(k) = [(k + 1)2H − 2k 2H + (k − 1)2H ] 2

3.5. CÁLCULO DEL EXPONENTE DE HURST H

29

para k > 0 y ρ(k) = ρ(−k) para k < 0. El comportamiento asintótico de ρ(k) es analizado mediante la expansión de Taylor: Primero cabe notar que ρ(k) = 21 k 2H g(k −1 ) donde g(x) = (1 + x)2H − 2 + (1 − x)2H . Si 0 < H < 1 y H 6= 1/2, entonces el primer término distinto de cero en la expansión de Taylor de g(x), expandido alrededor del origen, es 2H(2H − 1)x2 . Por lo tanto, para k → ∞, ρ(k) es equivalente a H(2H − 1)k 2H−2 , es decir, ρ(k) →1 H(2H − 1)k 2H−2 para k → ∞. Para 1/2 < H < 1, esto significa que las correlaciones decaen lentamente de forma que ∞ X

−∞

ρ(k) = ∞,

por lo tanto, la Ec. (3.13) es válida, lo que significa que el proceso posee memoria de largo alcance y que el exponente H resulta ser el exponente de Hurst. Un valor de H entre 1/2 y 1 indica un “comportamiento persistente”, esto significa que a un incremento en la serie temporal le sigue otro incremento a corto plazo. Para H = 1/2, todas las correlaciones para distancias no nulas son cero, y las observaciones Xi resultan no correlacionadas.

3.5.

Cálculo del exponente de Hurst H

Sea un conjunto de datos {Xi : i = 1, ..., N } en los cuales se desea estudiar las correlaciones de Xi y Xi+n sobre diferentes escalas temporales n a fin de determinar la presencia de memoria de largo alcance. Con el fin de librarse de un desplazamiento P (offset) constante en los datos se acostumbra sustraer la media hXi = m = N1 N i=1 Xi a f fin de obtener una serie centrada en cero, Xi ≡ Xi −m. Cuantitativamente la correlación entre dos valores de X separados por n está definida por la función de auto-correlación −n 1 NX fX f C(n) = X i i+n N − n i=1

Si {Xi } son no correlacionadas, C(n) es cero para n > 0. Además, como se mencionó previamente, en el caso de las correlaciones de largo alcance, C(n) decae como ley de potencia C(n) ∼ n−γ

30

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

con exponente 0 < γ < 1. Muchas veces no es posible realizar un cálculo directo de C(n) debido a la presencia de ruido superpuesto al conjunto de datos o bien, a tendencias subyacentes de origen desconocido cuyas escalas tampoco son conocidas [27], y por lo tanto se debe calcular el exponente γ de forma indirecta. Los métodos más utilizados a fin de determinar la existencia de correlaciones de largo alcance en una serie temporal se centran en el cálculo del coeficiente de Hurst H, entre los cuales se pueden mencionar el método de rango reescalado o estadística R/S, detrended fluctuation analysis o DFA, variancia agregada, periodograma, wavelet analysis y estimador local Whittel[26]. En este trabajo se emplearán los dos primeros métodos mencionados.

3.5.1.

Método de Rango Reescalado R/S

A fin de calcular H se debe primero estimar la dependencia del rango reescalado con los rangos temporales de las observaciones. Para esto la serie temporal de N observaciones es dividida en series de menor longitud n = N, N/2, N/4, ... no superpuestas. Para cada sub-conjunto de observaciones de longitud n, X = X1 , X2 , ..., Xn , se computa: 1. La media: m=

n 1X Xi n i=1

2. Una serie centrada en la media: f =X −m X t t

t = 1, 2, ..., n

3. La desviación acumulada de la serie respecto de la media: Y (t) =

t X i=1

4. El rango R:

f X i

t = 1, 2, ..., n

R(n) = m´ax[Y (1), Y (2), ..., Y (n)] − m´ın[Y (1), Y (2), ..., Y (n)] 5. La desviación estándar S:

v u n u1 X (Xi − m)2 S(n) = t

n i=1

3.5. CÁLCULO DEL EXPONENTE DE HURST H

31

Luego, se promedia el rango reescalado R(n)/S(n) sobre todas las series temporales parciales de hlongitud n, y finalmente, se estima H ajustando los datos a la ley de i R(n) potencias E S(n) = CnH . Para esto se emplea la Ec. (3.18) y se realiza una regresión lineal a fin de calcular la pendiente H.

3.5.2.

Método DFA

El DFA, Detrended Fluctuation Analysis[27], es un método de determinación de correlaciones de largo alcance en series temporales no estacionarias consolidado para determinar comportamiento de escala de conjuntos de datos con presencia de ruido y tendencias de origen y forma desconocida. En este sentido el método resulta más adecuado que el método R/S. El método calcula una función de fluctuación F (n) específica a una escala temporal n[28], la cual, para series temporales con correlaciones de largo alcance tiene la forma F (n) ∼ nζ

(3.19)

El procedimiento del DFA consiste de tres pasos. Primero se determina el perfil Y (t) =

t X i=1

de la serie de longitud N .

f X i

t = 1, 2, ..., N

El segundo paso consiste en dividir el perfil Y (t) en Nn = N/n segmentos de longitud n para cada uno de los cuales se determina una función de tendencia g(t), generalmente lineal y luego se calculan los residuos ε(t) = Y (t) − g(t) Finalmente, se obtiene F (n) como la media cuadrática de los residuos de la serie temporal v u N u1 X F (n) = t ε(t)2 (3.20) N i=1

Cuando ζ < 1 la serie temporal resulta estacionaria y ζ = H donde H es el exponente de Hurst.

32

3.6.

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

Ley de Zipf

Cuando la probabilidad de medir un valor particular de alguna cantidad varía inversamente como potencia de ese mismo valor, se dice que la cantidad en cuestión sigue una ley de potencias o una distribución libre de escala, también conocida como Ley de Zipf o distribución de Pareto. La frecuencia de uso de palabras en múltiples lenguas[29], las tormentas solares[16] y las ciudades más extensas[30] pueden ser descriptos en términos de la Ley de Zipf, la cual captura la relación entre la frecuencia de un set de objetos o eventos y su tamaño. En todos estos ejemplos mencionados el exponente de la distribución resulta cercano a 2, esto es, siguen una ley de potencias x−2 , donde x es el tamaño[10]. En el caso de una distribución de “tamaños” x dada por P (x) ∼ x−γ , un objeto de tamaño x posee rank r = N P≥ (x) ∼ x−γ+1 , donde N es el número total de cuidades, palabras, etc. estudiadas. Una ley de Zipf con exponente arbitrario −α corresponde a 1 lo cual se reduce a α = 1 x ∼ r−α . Combinando resultados puede verse que α = γ−1 para γ = 2. En la Figura 3.2 se muestra, a modo de ejemplo, el histograma de tamaños de las ciudades estadounidenses[30]; en el mismo se observa la existencia de un gran número de ciudades relativamente pequeñas, y un número reducido de ciudades cuya población supera considerablemente a la media. Resulta notable al estudiar el lado derecho de la Figura 3.2 como al graficar el histograma en escala logarítmica su aspecto general resulta similar a una función lineal. Denotando por p(x)dx a la fracción de ciudades con población entre x y x + dx, resulta ln p(x) = −α lnx + c, donde α y c son constantes, lo que es equivalente a p(x) = Cx−α (3.21) con exponente α = 2,3. La identificación del comportamiento de ley de potencia de sistemas naturales o artificiales es complicada. La estategía estándar utilizada[30] es la mostrada en el ejemplo anterior y consiste en obtener un histograma de una cantidad que al ser graficada en escala logarítmica es muy cercana a una recta. Esta no es la mejor forma de proceder, ya que generalmente se observa ruido en la cola de la distribución a causa de que los eventos en dicha zona son menos frecuentes (Figura 3.3), lo que significa que cada intervalo (“bin”) posee muy pocas mediciones. Una de las soluciones a este problema consiste en variar el ancho de los intervalos del histograma. Al realizar esto se debe normalizar, es decir, el número de elementos en un intervalo ∆x debe ser dividido por

3.6. LEY DE ZIPF

33

Figura 3.2: Izquierda: histograma de la población de las ciudades estadounidenses cuya población supera 10000 habitantes. Derecha: histograma del mismo conjunto de datos en escalas logarítmicas. Fuente: Newmann[30]

Figura 3.3: Datos artificiales que consta de números reales aleatorios extraídos de una distribución de probabilidad de ley de potencias según la Ec. (3.21) para α = 2,5. Fuente: Newmann[30]

34

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

la longitud ∆x, a fin de que el conteo normalizado de la muestra resulte independiente de la longitud del intervalo. La elección más usual es crear los intervalos tal que cada uno sea un múltiplo fijo más ancho que el anterior. Esto es conocido como bin logarítmico. Existen múltiples mecanismos los cuales generan distribuciones con comportamiento de leyes de potencias, entre los cuales se pueden mencionar la combinación de exponenciales, cantidades inversas, caminatas aleatorias, proceso de Yule, toleracia altamente optimizada, ruido coherente y modelos multiplicativos modificados[30, 17]. Cada sistema particular debe ser adecuado a un tipo de modelo que depende del mecanismo que le da origen.

3.6.1.

La Ley de Zipf en el Ajedrez

Las partidas de Ajedrez pueden describirse como las ramas de un grafo o árbol cuya raíz es la posición inicial del juego. Cada link de dicho árbol representa una movida legalmente permitida por las reglas del juego, y cada nodo una de las posibles posiciones. De este modo, una partida en particular puede representarse por una secuencia de nodos σ0 , σ1 , σ2 , ..., σd o equivalentmente por una secuencia de links l1 , l2 , ..., ld en el árbol. La raíz del árbol σ0 está presente en todas las partidas posibles. El árbol de partidas posee aproximadamente 10120 nodos (número de Shannon[31]), correspondiendo a un factor de ramificación promedio igual a 30 ramas por nodo y a una longitud promedio de las partidas en 40 movidas. Sin embargo, a pesar de la complejidad del árbol de partidas posibles tan sólo una pequeña fracción de las partidas son ejecutadas en la práctica. Esta observación es de crucial importancia para entender la naturaleza de los fenómenos de tomas de decisiones. En el trabajo de Blasius y Tönjes[1] se estudia una base de datos de partidas de Ajedrez entre humanos (SCIDBASE [32]) encontrando que la popularidad de las diferentes líneas de juego satisface la ley de Zipf. Este hallazgo se relaciona a la existencia de líneas de juego que son corrientes y que los jugadores tienden a elegir. Además, es importante ya que conecta los procesos de tomas de decisiones con un espectro de procesos complejos caracterizados por la ley de Zipf. Más precisamente, el estudio de Blasius y Tönjes se enfoca una versión pesada del árbol de partidas (Figura 3.4). Cada nodo σ en el árbol tiene asociado un número de partidas nσ , y cada link l una fracción rl de partidas que continúa por la correspondiente línea de juego. De este modo, si l es el link que va desde la posición σ hasta la posición σ ′ , luego se satisface nσ rl = nσ′ . La raíz tiene un número nσ0 de partidas que es igual al número N de partidas en la base

3.6. LEY DE ZIPF

35

de datos estudiada. En términos de los procesos de tomas de decisiones, nσ denota la popularidad con la cuál es jugada la correspondiente apertura o línea de juego. De acuerdo con Blasius and Tönjes, la fracción de partidas con popularidad n satisface una ley de potencias (Figura 3.5(A)) S(n) ∼ n−α con exponente α = 2, lo cuál corresponde a la ley de Zipf [30]. Al estudiar el fenómeno en más detalle, se encuentra que las frecuencias Sd (n) de los juegos correspondientes a los primeros d movimientos son consistentes con un comportamiento de ley de potencias (Figura 3.5.(B)) Sd (n) ∼ n−αd en donde los exponentes αd no son universales sino que aumentan linealmente con d. Las leyes de potencias con exponentes no universales pueden explicarse utilizando caminatas aleatorias multiplicativas[33, 34]. La propuesta de Blasius y Tönjes consiste en un modelo basado en este tipo de procesos que explica con gran precisión las distribuciones observadas. Más precisamente, el número nd de partidas tras d movimientos viene dado por la ecuación, nd = N

d Y

ri ,

n0 = N.

(3.22)

i=1

En el trabajo de Blasius y Tönjes se asume que el árbol de partidas de la Figura 3.4 es autosimilar de manera que cada factor de ramificación ri ∈ [0, 1] es una variable aleatoria correspondiente a una distribución de probabilidades q(r) que es independiente del nodo σ en consideración. En particular q(r) es independiente del número de partidas N , y de la profundidad d de la posición. La distribución q(r) fué medida por Blasius y Tönjes y se encuentra que la misma está bien descripta por la expresión no paramétrica (ver Figura 3.6(A)) 2 q(r) = √ . (3.23) π 1 − r2

correspondiente a la distribucion arcoseno. Tal distribución q(r) es aproximadamente constante para valores relativamente grandes de r y diverge como (1 − r)1/2 cuando r → 1. En el trabajo de Blasius y Tönjes se menciona que la forma de la distribución q(r) sugiere que en el caso del ajedrez no existe un proceso de crecimiento preferencial, sino algún factor relacionado con el proceso de decisión durante la etapa de apertura de las partidas de ajedrez[35].

36

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

Figura 3.4: (A) Representación del árbol de la base SCIDBASE. Las líneas sólidas representan las posibles continuaciones del juego junto con sus correspondientes probabilidades, y las líneas de puntos, otras posibles continuaciones menos probables que no se muestran. (B) Representación alternativa que destaca la segmentación sucesiva del conjunto de partidas. Cada nodo σ esta representado por un recuadro cuyo tamaño es proporcional a su frecuencia nσ . En la profundidad siguiente las partidas se dividen en sub-conjuntos de acuerdo con las posibles continuaciones del juego. Fuente: Blasius et al.[1].

3.6. LEY DE ZIPF

37

Figura 3.5: (A) Histograma de la frecuencia pesos S(n) de las aperturas hasta una profundidad d = 40 con bin logarítmico. Una regresión lineal resulta en un exponente de α = 2,05. (B) Número de aperturas Sd (n) de profundidad d con popularidad n para d = 16 e histogramas con bin logarítmico para d = 4, d = 16 y d = 22. Inset: pendiente αd en función de la profundidad d y la estimación analítica (Ec. 3.26) utilizando N = 1,4 × 106 y β = 0. Fuente: Blasius et al.[1].

38

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

A su vez el trabajo provee una derivación analítica de las distribuciones S(n) y Sd (n) partiendo de una aproximación a la distribución q(r) dada por, q(r) = (1 + β)rβ ,

(3.24)

0 ≤ r ≤ 1,

la cuál típicamente aparece en procesos de conexión preferencial2 [36] derivados de modelos de crecimiento preferencial[37]. Los cálculos determinan que 

N (1 + β)d log Sd (n) = N (d − 1)! n

d−1 

N n

1−β

.

(3.25)

Utilizando una expansión logarítmica en el rango 1 ≪ n ≪ N esta expresión exhibe una comportamiento tipo ley de potencias con exponente −αd dado por αd = (1 − β) +

1 (d − 1), log N

(3.26)

de modo que αd crece linealmente con la profundidad d más una correción logarítmica estando en buena concordancia con lo observado (Inset de la Figura 3.5(B)). Como se muestra en la Figura 3.6 las simulaciones del proceso multiplicativo (Ec. 3.22) empleando la distribución arcoseno (Ec. 3.23) resultan una buena aproximación de las frecuencias pesadas Sd (n) de la base de datos de ajedrez. Si las razones de ramificación son aproximadas por una distribución uniforme q(r) = 1, los valores de Sd (n) resultan sistematicamente pequeños, ya que esta distribución produce un mayor flujo hacia el estado absorbente n∗ = 1 que el observado en la base de datos. Sin embargo, debido al comportamiento asintótico de q(r) cuando r → 0, esta aproximación produce una pendiente correcta en el gráfico log-log de forma tal que el exponente αd puede ser estimado con la Ec. 3.26 y tomando β = 0. Posteriormente, en el trabajo de Blasius y Tönjes mediante el uso de la teoría de los procesos de renovación,3 se muestra que P el comportamiento asintótico de S(n) = d Sd (n), en el rango n ≫ 1, puede derivarse para un amplio espectro de distribuciones q(r) encontrándose que l´ım S(n) =

(n/N )→0

N , µn2

donde µ = h− log ri, lo cuál está en excelente acuerdo con lo encontrado empíricamente (Figura 3.5). Así, el proceso multiplicativo de la Ec. 3.22 siempre lleva un ‘scaling’ universal asintótico para n ≪ N , para cualquier distribución de ramificaciones q(r) bien comportada. Este resultado es importante ya que muestra que los procesos que 2 3

Del inglés preferential attachment Del inglés renewal processes.

3.6. LEY DE ZIPF

39

Figura 3.6: (A) Densidad de probabilidad q(r) de las razones de ramificación r medida utilizando la base de datos Scid con intervalos constantes ∆r = 0,01, y la distribución arcoseno n (Ec. 3.23). (B) Probabilidad Pd (n) = N Sd (n) de que un nodo a una distancia d del nodo raíz posea popularidad n para el caso d = 22 en la base de datos SCIDBASE (línea negra). Comparativamente se muestran las curvas correspondientes a una simulación directa del proceso multiplicativo con la distribución q(r) original (Ec. 3.22, línea azul), y una distribución q(r) uniforme (Ec. 3.24 con β = 0, línea roja). Resultados teóricos según la Ec. 3.25 (línea a rayas). Fuente: Blasius et al.[1].

40

CAPÍTULO 3. CONCEPTOS Y DEFINICIONES

dan lugar a distribuciones Zipf del peso de los subárboles de un árbol autosimilar es mucho más amplia que la clase de procesos basados en conexión preferencial o procesos de crecimiento[38]. Una de las consecuencias de la teoría de Blasius y Tönjes es que en un proceso de d decisiones mutuamente excluyentes, la distribución de las secuencias de decisiones, o estrategias, que toman lugar n veces, Sd (n) ∼ n−αd , pone en evidencia una transición desde exponentes αd ≤ 2, donde existen unas pocas estrategias que son muy comunes, a exponentes elevados αd > 2, donde todas las estrategias resultan uniformemente dominantes4 . Esta transición es causada por la divergencia del primer momento en leyes de potencias con exponentes mayores a −2 [30]. El número crítico de decisiones dcr para el cual ocurre la transición es calculado a partir de la Ec. 3.26, dcr = 1 + (1 + β)log N. Para el caso de SCIDBASE en donde N = 1,4 × 106 , se tiene que dcr = 15. Esto separa a la base en dos regímenes diferentes: en la fase inicial (d < dcr ) la mayor parte de las partidas de ajedrez están distribuídas entre un pequeño número de aperturas populares, mientras que más allá de la profundidad de juego crítica las secuencias raramente utilizadas son las dominantes de modo que al considerarlas todas juntas comprenden la mayoría de las partidas. Es importante resaltar que este resultado es un efecto de la estadística y no indican un cambio de comportamiento de los jugadores al incrementarse la profundidad del juego. 4

Cualquier estrategia presenta una popularidad n bien aproximada por la media hni

4. Resultados En esta sección se presentan los resultados obtenidos del estudio general de la base de datos, la reproducción de algunos resultados de Blasius y Tönjes y la generación de la serie temporal a partir de la base de datos de partidas de ajedrez con el consecuente estudio de la misma mediante los métodos de R/S y DF A. Para implemetar estos análisis se desarrollaron programas utilizando el lenguaje de programación FORTRAN 90.

4.1.

Base de Datos

La base de datos utilizada, SCIDBASE[32], cuenta con más de 3,5 × 106 partidas de ajedrez, desde el año 206 dC al 2007, y fué convertida al formato PGN (portable game notation) utilizando una variación de la SCIDBASE llamada Scid vs Pc[39]. El formato en el cual se encuentran registradas las partidas es el siguiente: #(indicando una nueva partida), número de partida (orden en la base), año, día, mes, jugador de las blancas, jugador de las negras, elo de las blancas, elo de las negras, resultado del partido, evento (por ejemplo si la partida fué jugada en un torneo) ; luego se encuentran registrados los movimientos realizados en dos columnas, la primera correspondiente a los movimientos de las blancas y la segunda a los movimientos de las negras. Como fué explicado anteriormente, el Elo es una calificación dinámica que cambia luego de que un jugador juega una partida, a pesar de esto, en la base de datos, los Elos de los jugadores son aproximados y permanecen constantes a través del tiempo. Además, como el sistema de puntuación Elo fué implementado en 1970, para los partidos que tomaron lugar antes de 1970, los Elos de los jugadores son una estimación. Del total de las partidas registradas solo 1,5 × 106 posee todos los datos completos, en particular en muchas de ellas los datos temporales se encuentran incompletos o los 41

42

CAPÍTULO 4. RESULTADOS

Elos de los jugadores están ausentes. Es por esto que en la mayor parte del trabajo estas partidas con “datos corruptos” son filtradas y se trabaja solamente con las partidas cuyos datos están completos.

4.2.

Estudio General de la Base de Datos

El Ajedrez ha capturado el interés de la humanidad por siglos. Dentro de este marco es de esperar que tanto los procesos sociales como los avances tecnológicos hayan ejercido una influencia notable en elementos como la cantidad de partidas registradas o las puntuaciones Elo de los jugadores. Como se mencionó previamente, la base de datos cuenta con partidas registradas a partir del año 206 Dc, sin embargo la cantidad de juegos hasta 1837 es muy pequeña y no es tomada en cuenta para el estudio general de la base. Con el fin de analizar la distribución de partidas por año se utilizó una base la cual consta de 1,5 × 106 partidas, resultante del filtrado de los elementos con datos corruptos y los correspondientes a años anteriores a 1837. En la Figura 4.1 se muestra la cantidad de partidas registradas en la base de datos por año utilizando escala logarítmica en el eje y. De forma general la cantidad de partidos registrados han ido aumentando con los años, sin embargo es posible distiguir tres períodos temporales que presentan diferentes tendencias de crecimiento. El más evidente de estos períodos es el que tiene lugar a partir del año 1997 y coincide con la generalización del acceso a Internet de la población mundial, esto permitió un gran aumento de registro de los partidos jugados, en parte debido al surgimiento de diversos servidores web de ajedrez los que vinieron a reemplazar los partidos por correspondencia escrita. Los otros dos períodos resultan más difíciles de identificar a simple vista y son los comprendidos entre los años 18371959 y 1960-1997. De 1960 a 1997 la distribución de partidas por año tiende a ser relativamente estable. Entre los años 1837 y 1959 se observan aumentos y disminuciones abruptas en la distribución, provocadas por diversos hechos, por un lado, en el mundo del ajedrez, comienzan a formarse las federaciones de ajedrez como la británica y a organizarse torneos internacionales, por otro lado es un período de grandes cambios tecnológicos y conflictos mundiales, en particular resulta evidente la disminución de las partidas registradas durante la segunda guerra mundial (1939-1945). Debido al incremento de la cantidad de partidas registradas, y al aumento del acceso de los jugadores a las mismas a través de diferentes medios de comunicación como libros,

4.2. ESTUDIO GENERAL DE LA BASE DE DATOS

43

Distribución de partidas por año 7

10

1837−1959 1960−1997 1998−2007

cantidad de partidas (escala logarítmica)

106

105

104

103

102

101

100 1820

1840

1860

1880

1900

1920

1940

1960

1980

2000

año

Figura 4.1: Cantidad de Partidas por año desde 1837 con un total de N = 1,5 × 106 partidas

y el perfil correspondiente . Escala logarítmica en el eje y.

2020

44

CAPÍTULO 4. RESULTADOS

Elo promedio de los Grand Masters 2450

2400

Elo promedio

2350

2300

2250

2200

2150

2100 1820

1840

1860

1880

1900

1920

1940

1960

1980

2000

año

Figura 4.2: Número promedio de Elo Grand Masters (Elo mayor a 2000) por año sobre N = 1,3 × 106 partidas.

2020

4.2. ESTUDIO GENERAL DE LA BASE DE DATOS

45

revistas, etc., resulta natural suponer que la habilidad de los jugadores más expertos, llamados Grand Masters (jugadores que superan los 2000 Elo), también ha aumentado a través del tiempo[9]. Partiendo de la base de datos constituída por 1,5 × 106 partidas y filtrando las partidas en las cuales el Elo mayor de los dos jugadores es menor a 2000, se calculó el promedio de los Elos máximos por año (Figura 4.2). Se observa como el Elo promedio oscila alrededor de un valor relativamente constante hasta el año 1970, a no ser por una disminución abrupta en 1917, donde el promedio en este período resulta 2239 Elo. En el año 1970 el Elo promedio sufre un salto significativo, que coincide con la racha ganadora de 20 partidas consecutivas de Bobby Fischer (1970-1971) y su consagración como campeón mundial al derrotar a Boris Spassky(1972). Luego de dicho salto, el Elo promedio oscila alrededor de 2341 Elo, valor que resulta cercano al promedio de Elo de un torneo olímpico (2300 Elo[9]). Resulta interesante también estudiar la distribución de partidas por Elo máximo, es decir la cantidad de partidas en los cuales el Elo máximo de los dos jugadores toma un cierto valor. Ya que la fracción de la base de datos con Elo máximo menor a 500 Elo es prácticamente despreciable, en la Figura 4.3 se grafica la distribución correspondiente a Elos superiores a este valor. La distribución fué calculada considerando los Elos máximos de cada partida en intervalos de 10 Elo. Se observa como la distribución de partidos se asemeja a la de una distribución normal, por lo tanto se realizó un ajuste de 2 el cual arrojó un valor de µ = 2303 Elo los datos con una función f (x) = c exp − (x−µ) 2σ 2 para la media de la distribución y σ = 208 Elo para la desviación estándar. Nuevamente el valor calculado para µ coincide con el promedio de Elo de un torneo olímpico, y el valor obtenido para la dispersión σ es similar a la esperada en el caso de la distribución de rendimientos de un jugador.

46

CAPÍTULO 4. RESULTADOS

Distribución de partidas por Elo máximo 30000

σ=208 Elo, µ=2303 Elo

cantidad de partidas

25000

20000

15000

10000

5000

0 500

1000

1500

2000

2500

Elo

Figura 4.3: Líneas rojas: cantidad de partidos por intervalo de 10 Elo, tomando el Elo máximo de cada partida, apartir de 500 sobre N = 1,5 × 106 partidas. Línea negra: Ajuste empleando una distribución normal con σ = 208 y media µ = 2303 Elo.

3000

4.3. DISTRIBUCIONES LIBRES DE ESCALA

4.3.

47

Distribuciones Libres de Escala

En el capítulo 3.6.1 se explica como Blasius y Tönjes[1] observaron un comportamiento de leyes de potencias al calcular la frecuencia de las partidas con popularidad n (cantidad de apariciones en la base de datos) Sd (n), a una profundidad fija d. Es decir, dada una profundida d se tiene que Sd (n) ∼ n−αd , donde el exponente αd crece al aumentar el parámetro d (Figura 4.5). Empleando la SCIDBASE[32] se propuso reproducir estos resultados tomando los valores d = 2, d = 4 y d = 8 por cuestiones de tiempo de cálculo. Se utilizó un total de 1,4 × 106 partidos posteriores a 1998 obtenidos luego de filtrar las partidas con datos corruptos de la base de datos original. A fin de obtener el histograma de frecuencias se calculó la popularidad n de cada apertura, esto es, la cantidad de veces que aparece en la base de datos, y luego la cantidad de aperturas Sd (n) con popularidad n en intervalos constantes para los valores de d antes mencionados. Asimismo, con el objetivo de calcular el exponente αd se utilizó un bin logarítmico donde cada intervalo es dos veces el anterior, es decir, los intervalos están definidos como [2i , 2i+1 ] i = 0, 1, 2, .... Los gráficos obtenidos se muestran en la Figura 4.4.

Los valores de αd fueron calculados realizando una regresión lineal de las distribuciones obtenidas con un bin logarítmico resultando en: d αd

2 4 8 1,28 ± 0,05 1,53 ± 0,03 1,9 ± 0,1

Observando la Figura 4.5 es posible concluir que los resultados obtenidos son equivalentes a aquellos calculados por Blasius y Tönjes.

48

CAPÍTULO 4. RESULTADOS

106

d=8 histograma d=8 logbin d=4 logbin d=2 logbin

5

10

104 103

frecuencia Sd(n)

102 101 100 10−1 10−2 10−3 10−4 10−5 0 10

1

10

2

3

10

10

4

10

popularidad n

Figura 4.4: Gráfico log-log de la cantidad de aperturas Sd (n) a una dada profundidad d con una dada popularidad n para d = 8 e histogramas calculados con bin logarítmico para d = 2, d = 4 y d = 8.

5

10

4.3. DISTRIBUCIONES LIBRES DE ESCALA

49

Figura 4.5: Puntos rojos: exponente α obtenido por Blasius y Tönjes para diferentes valores de d (Inset Figura 3.5 (B)).

50

CAPÍTULO 4. RESULTADOS

4.4.

Análisis de Correlaciones

Una vez obtenido el árbol de jugadas con las correspondientes razones de ramificación ri , Blasius y Tönjes proponen la reproducción de las partidas de la base de datos mediante un proceso multiplicativo (Ec. 3.22). Sin embargo, como menciona Sigman [8], la experiencia de un jugador se refleja en la combinación de su habilidad para calcular variaciones (búsqueda) y su habilidad para reconocer y recordar patrones significativos en el tablero. Por lo tanto resulta natural suponer que el ajedrez es un juego con memoria al menos a nivel de cada jugador. Por lo tanto, es de esperar que al estudiar una secuencia de partidas existan correlaciones no nulas entre ellas. Este aspecto no se ve reflejado en partidas generadas por un proceso multiplicativo. Es por esto que se propuso explorar la existencia de memoria de largo alcance en el conjunto de partidas de ajedrez empleando métodos de análisis de series temporales. Análogamente a los estudios realizados en cuerpos literarios[19, 2], las partidas de la base de datos se tradujeron a una serie temporal discreta, esto se realizó ordenando los elementos de la base cronológicamente, y definiendo a los elementos de la serie como X(t) =

t−1 X

C(t, t′ ),

(4.1)

t′ =t−τ

donde C(t, t′ ) es una medida de similitud entre partidas definida por la cantidad de coincidencias consecutivas en los movimientos entre las partidas a tiempos t y t′ ; en principio se tomó τ = 1. A su vez, a cada elemento de la serie temporal X(t) le fué asignado los datos correspondientes a los jugadores, Elos y resultados de la partida a tiempo t. Cabe mencionar que debido a que el registo de las partidas no es contínuo en el tiempo; es posible establecer el orden cronológico de las partidas, no así la escala temporal. El siguiente ejemplo muestra cómo se calcula X(t) para τ = 3. Dadas las siguientes secuencias de movimientos de cuatro partidas consecutivas: t − 3: e4 - d5 - exd5 - Qxd5 - Nc3 - Qa5 - d4 - Nf6 - Nf3 - c6 - Ne5 - Bf5 - g4 - Be4 t − 2: e4 - e5 - Nf3 - Nc6 - Bc4 - Bc5 - c3 - Nf6 - d3 - d6 - Bb3 - O-O - Nbd2 - Be6 t − 1: e4 - d5 - exd5 - Qxd5 - Nc3 - Qa5 - d4 - e6 - Nf3 - c6 - Bd3 - Nf6 - O-O - Be7 t: e4 - e5 - Nf3 - Nc6 - Bb5 - a6 - Ba4 - Nf6 - O-O - Be7 - Re1 - b5 - Bb3 - d6 se desea calcular la cantidad de coincidencias C(t, t′ ) entre la secuencia a tiempo t y las tres secuencias anteriores. En este ejemplo, C(t, t − 1) = 1, C(t, t − 2) = 4

4.4. ANÁLISIS DE CORRELACIONES

51

y C(t, t − 3) = 1. Finalmente se suman estas coincidencias dando como resultado X(t) = 6. Para el análisis de la serie temporal se utilizaron dos métodos, rango reescalado R/S y DFA, y se utilizó un total de 1,4 × 106 partidas posteriores a 1998. Tomando cada valor obtenido para los elementos de la serie temporal y calculando la cantidad de repeticiones que posee el mismo es posible realizar un histograma de frecuencias de coincidencias, el cual se muestra en la Figura 4.6. Se observa que la misma decae en forma exponencial con exponente α = −0,49, por lo tanto guarda cierta similitud con la frecuencia de apariciones de aperturas en la base S(n) (Figura 4.4) en el sentido que existen pocos pares de partidas que exhiben gran número de coincidencias consecutivas, mientras que la mayoría de los pares de partidas poseen escasas coincidencias. Más allá de X = 24 la cantidad de elementos de la serie son practicamente inexistentes, por lo tanto éstos no fueron tomados en cuenta para el cálculo de la frecuencia. Observando las Figuras 4.7 y 4.8, donde se muestran la serie temporal X(t) con 2000 puntos y el perfil Y(t) total calculado, se presume que la misma posee memoria ya que se advierten oscilaciones las cuales parecen tener un período largo, lo que indica que la serie no es equivalente a una caminata aleatoria a diferencia de la serie en la que se ha introducido shuffling aleatorio de los datos (Figura 4.9). Para comprobar esto se calculó el exponente de Hurst empleando las metodogías antes mencionadas. Tanto para la estadística R/S como para el DFA se dividió la serie temporal en series de menos longitud n = N, N/2, N/4, ..., N/29 . Para el método de rango reescalado la dispersión de cada punto fué estimada tomando los valores máximo y mínimo de R/S para cada n; sin embargo, el error correspondiente a n = N no fué incuído debido a que en este caso la serie se “divide” en un solo intervalo y por lo tanto, se dispone de una única muestra. En el caso del método DF A no fué posible definir el error para cada punto, por ende no fueron incluídos. Los gráficos obtenidos para E[R(n)/S(n)] y F (n) se muestran en las Figuras 4.10 y 4.11, respectivamente. El exponente calculado con el método DFA resulta ζ < 1, por lo tanto la serie temporal es estacionaria y ζ = H.

52

CAPÍTULO 4. RESULTADOS

frecuencia (escala logarítmica)

Histograma de coincidencias 10

6

10

5

10

4

10

3

10

2

10

1

10

0

0

5

10

15

20

25

X

Figura 4.6: Gráfico de la cantidad de repeticiones de coincidencias a un dado valor de X. Escala logarítmica en el eje y.

X(t)

Serie Temporal 16 14 12 10 8 6 4 2 0 0

200

400

600

800 1000 1200 orden temporal (t)

1400

1600

Figura 4.7: Serie temporal X(t) hasta 2000 puntos.

1800

2000

4.4. ANÁLISIS DE CORRELACIONES

53 Perfil

Y(t)

0 −1*10

3

−2*10

3

−3*10

3

−4*10

3

−5*10

3

−6*10

3

−7*10

3

0

2.0*10

5

4.0*10

5

5

6.0*10 8.0*10 orden temporal (t)

Figura 4.8: Perfil Y (t) =

Pt

5

i=1 (X(i)

1.0*10

6

1.2*10

6

− m).

Perfil con shuffling

Y(t)

2

2.0*10 0 2 −2.0*10 2 −4.0*10 2 −6.0*10 2 −8.0*10 3 −1.0*10 3 −1.2*10 3 −1.4*10 0

2.0*10

5

Figura 4.9: Perfil Y (t) = motrada en la Figura 4.7.

4.0*10

Pt

5

5

5

6.0*10 8.0*10 orden temporal (t)

i=1 (X(i) − m)

1.0*10

6

1.2*10

6

1.4*10

6

una vez realizado el shuffling de la serie temporal

54

CAPÍTULO 4. RESULTADOS

Hurst: rango reescalado 4

10

3

E[R(n)/S(n)]

10

2

10

R/S puntos extremos de R/S

1

10

3

10

4

5

10

Figura 4.10: Gráfico log-log de E

10 n

h

R(n) S(n)

i

6

10

vs. n. La regresión lineal devuelve una pendiente H = 0,68 ± 0,01. Las cruces indican los valores extremos que toma R(n)/S(n) en cada conjunto de muestras.

7

10

4.4. ANÁLISIS DE CORRELACIONES

55

Hurst: DFA 4

10

3

F(n)

10

2

10

1

10

3

10

4

10

5

10 n

6

10

Figura 4.11: Gráfico log-log de F (n) vs. n. La regresión lineal devuelve una pendiente H = 0,67 ± 0,01.

7

10

56

CAPÍTULO 4. RESULTADOS

Los exponentes de Hurst resultantes son indistinguibles entre si y mayores a 1/2, por lo tanto se puede inferir que la serie temporal de partidas de ajedrez tiene memoria de largo alcance. Como se mencionó antes, la base de datos cuenta con partidas tanto de jugadores expertos como de jugadores principiantes categorizados por su puntaje de Elo. Este hecho permitió el estudio de la memoria de las partidas de jugadores en diferentes categorías. Tomando el Elo mayor asignado a cada elemento X(t), se dividió la serie temporal en tres categorías, jugadores inexpertos cuyo Elo fuera menor a 999 con un total de N = 5,5 × 103 partidas, jugadores de experiencia intermedia con Elos entre 1000 y 1999 con un total de N = 1,8 × 105 partidas, y por último jugadores expertos, los llamados Grand Masters, con Elos mayores a 2000 con un total de N = 1,1 × 106 partidas. En las Figuras 4.12 y 4.13 se muestran las series temporales X(t) hasta t = 2000 y los perfiles Y(t) correspondientes a los tres intervalos de Elo. La diferencia entre las tres series temporales es sutil, aún así es posible observar pequeñas tendencias locales para Elos entre 2000 y 2900 (Figura 4.12 (A)), así como también para Elos entre 1000 y 1999 (Figura 4.12 (B)), aunque en menor medida; en cambio, en el caso de jugadores inexpertos (Figura 4.12 (C)) no se observa practicamente ninguna tendencia local. Por lo tanto, se esperaría obtener un exponente de Hurst H > 1/2 para Elos mayores a 1000 y cercano a 1/2 para Elos menores. En el caso de los jugadores inexpertos, debido al número reducido de partidas disponibles en estas categorías, al calcular H mediante R/S y DF A se utilizaron nueve muestras en lugar de diez. Los resultados obtenidos mediante los métodos de rango reescalado y DFA se presentan en las Figuras 4.14 y 4.15. Los dos métodos producen resultados muy similares y se muestran a continuación:

R/S DFA

Elo=1-999 Elo=1000-1999 Elo=2000-2900 H = 0,52 ± 0,04 H = 0,61 ± 0,03 H = 0,68 ± 0,01 H = 0,48 ± 0,03 H = 0,57 ± 0,04 H = 0,68 ± 0,01

4.4. ANÁLISIS DE CORRELACIONES

57

(A) Elo=2000-2900 16 14 12 10 8 6 4 2 0 0

200

400

600

800

1000

1200

1400

1600

1800

2000

1800

2000

1800

2000

(B) Elo=1000-1999

X(t)

16 14 12 10 8 6 4 2 0 0

200

400

600

800

1000

1200

1400

1600

(C) Elo=1-999 16 14 12 10 8 6 4 2 0 0

200

400

600

800

1000

1200

1400

1600

orden temporal (t)

Figura 4.12: Serie temporal X(t) hasta 2000 puntos. (A) Jugadores expertos con Elos mayores a 2000. (B) Jugadores de experiencia intermedia con Elos entre 1000 y 1999. (C) Jugadores inexpertos con Elos menores a 999.

58

CAPÍTULO 4. RESULTADOS

(A) Elo=2000-2900 0

-2*10

3

-4*10

3

-6*10

3

0

2*10

5

4*10

5

6*10

5

8*10

5

1*10

6

(B) Elo=1000-1999 2*10

2

Y(t)

0 -2*10

2

-4*10

2

-6*10

2

0

2*10

4

4*10

4

6*10

4

8*10

4

1*10

5

5

1.2*10

5

1.4*10

5

5

1.6*10

1.8*10

(C) Elo= 1-999 0 -2*10

1

-4*10

1

-6*10

1

-8*10

1

0

1*10

3

2*10

3

3*10

3

4*10

3

5*10

3

orden temporal (t)

Figura 4.13: Perfil Y (t) =

Pt

i=1 (X(i)

− m). (A) Jugadores expertos con Elos mayores a 2000. (B) Jugadores de esperiencia intermedia con Elos entre 1000 y 1999. (C) Jugadores inexpertos con Elos menores a 999.

4.4. ANÁLISIS DE CORRELACIONES

59

(A) Elo=2000-2900 10

4

10

3

10

2

10

1

10

3

10

4

10

5

10

6

10

7

10

6

10

4

E[R(n)/S(n)]

(B) Elo=1000-1999 10

4

10

3

10

2

10

1

10

2

10

3

10

4

10

5

(C) Elo=1-999 10

2

10

1

10

0

10

1

10

2

10

3

n

Figura i4.14: Cálculo de H mediante el método de Rango Reescalado: Gráfico log-log de h

E R(n) S(n) vs. n por intervalo de Elo donde los puntos grises representan los valores extremos de R/S. Las regresiones lineales devuelven una pendiente H = 0,52 ± 0,02 para Elo=1-999 (línea roja), H = 0,61 ± 0,03 para Elo=1000-1999 (línea verde) y H = 0,68 ± 0,01 para Elo=2000-2900 (línea azul).

60

CAPÍTULO 4. RESULTADOS

(A) Elo=2000-2900 4

10

3

10

2

10

1

10

3

4

10

5

10

6

10

10

7

10

(B) Elo=1000-1999 3

10 F(n)

2

10

1

10

0

10

2

10

3

4

10

5

10

10

6

10

(C) Elo=1-999 2

10

1

10

0

10

1

10

2

3

10

10 n

Figura 4.15: Cálculo de H mediante el método DF A: Gráfico log-log de F (n) vs. n por intervalo de Elo. Las regresiones lineales devuelven una pendiente H = 0,48 ± 0,03 para Elo=1-999 (línea roja), H = 0,57 ± 0,04 para Elo=1000-1999 (línea verde) y H = 0,68 ± 0,01 para Elo=2000-2900 (línea azul).

4

10

4.4. ANÁLISIS DE CORRELACIONES

61

Nuevamente los resultados generados por el método de DF A son menores a 1, por lo que las series temporales correspondientes a los tres intervalos de Elo son estacionarias. Por un lado, para los jugadores expertos los exponentes de Hurst resultan iguales a 0,68, lo que indica que las partidas están auto-correlacionadas y la presencia de memoria de largo alcance, esto era de esperarse ya que los jugadores de categorías superiores son los que disponen de un conocimiento más amplio del juego. En el caso de los jugadores de experiencia intermedia H ∼ 0,60, por lo tanto, se observa nuevamente memoria de largo alcance, estos jugadores tienen memoria de las partidas pasadas aunque, como lo indica la leve disminución en el coeficiente, no en la misma medida que los jugadores de categorias superiores. Por último, para los jugadores inexpertos, ambos coeficientes obtenidos son aproximadamente 1/2, lo que significa que para las categorías menores las partidas no están correlacionadas, estos jugadores no poseen aún el nivel de conocimiento tal que se refleje en su comportamiento en la toma de decisiones. A su vez es notable la similitud del exponente de Hurst calculado para jugadores expertos con aquel calculado sin discriminación por Elo. Esto se debe a que los jugadores de categorías superiores son dominantes en cantidad (86 % del total de partidas registradas) y por lo tanto determinan el valor de H. A fin de poner en evidencia la importancia del orden temporal a la hora de generar la serie X(t) se realizó un shuffling aleatorio de los elementos de la serie y se procedió a calcular el exponente de Hurst nuevamente utilizando el método R/S de rango reescalado para los tres intervalos de Elo. Los valores obtenidos se muestran en la siguiente tabla: Elo=1-999 Elo=1000-1999 Elo=2000-2900 H = 0,48 ± 0,02 H = 0,47 ± 0,04 H = 0,497 ± 0,006 En la Figura 4.16 las pendientes de las tres rectas son practicamente indistinguibles, de hecho, los valores obtenidos son todos cercanos a 1/2. Es decir, al realizar un shuffling aleatorio la serie temporal resulta no correlacionada y por lo tanto no posee memoria de largo alcance. Esto indica que la elección para la asignación de la serie temporal (Ec. 4.1) no intorduce correlaciones espurias. Los resultados anteriores corresponden a series temporales X(t) igual a la cantidad de coincidencias entre dos partidas consecutivas, es decir, τ = 1 en la Ec. (4.1). Si se define ahora a X(t) como la suma de las coincidencias de la partida a tiempo t con

62

CAPÍTULO 4. RESULTADOS

(A) Elo=2000−2900 4

10

3

10

2

10

1

10

3

4

10

5

10

6

10

10

7

10

(B) Elo=1000−1999 3

E[R(n)/S(n)]

10

2

10

1

10

2

10

3

4

10

5

10

10

6

10

(C) Elo=1−999 2

10

1

10

0

10

1

10

2

3

10

10 n

Figura i4.16: Cálculo de H mediante el método de Rango Reescalado: Gráfico log-log de h

E R(n) S(n) vs. n por intervalo de Elo una vez realizado el shuffling de la serie temporal. Las regresiones lineales devuelven una pendiente H = 0,48 ± 0,02 para Elo=1-999 (línea roja), H = 0,47 ± 0,04 para Elo=1000-1999 (línea verde) y H = 0,497 ± 0,006 para Elo=2000-2900 (línea azul).

4

10

4.4. ANÁLISIS DE CORRELACIONES

63

las diez partidas anteriores, tomando τ = 10, se obtiene una nueva serie temporal. Se calculó el coeficiente de Hurst con el método R/S para esta nueva serie temporal realizando las mismas divisiones en intervalos de Elo (Figura 4.17) a fin de observar la influencia del parámetro τ empleado para la generación de la serie temporal a la hora de determinar la presencia memoria de largo alcance. El método produjo los siguientes valores: Elo=1-999 Elo=1000-1999 Elo=2000-2900 H = 0,54 ± 0,02 H = 0,60 ± 0,02 H = 0,67 ± 0,01 Dada la similitud de los exponentes a los calculados con la serie generada con τ = 1, es posible establecer que, independientemente de la elección de τ , la serie temporal generada a partir de la base de datos de partidas de ajedrez mediante 4.1 posee memoria de largo alcance en los casos de los jugadores cuyos Elos superan los 1000 Elo, y no así para los jugadores más inexpertos con Elos menores a 999 Elo cuyas partidas resultan no correlacionadas. Todos los resultados antes expuestos fueron obtenidos tomando la porción de la base de datos posterior a 1998. Con el fin de estudiar el comportamiento del exponente de Hurst en diferentes períodos temporales se utilizó una base de datos extendida que cuenta con 3,5 × 106 partidas entre 1878 y 1997, este conjunto fue dividido en nueve sub-conjuntos tomando en cuenta eventos significativos de la historia tanto mundial como particular del ajedrez. Como fué mencionado anteriormente, las reglas del ajedrez sufrieron cambios a medida que pasaban los años, en especial la regla de limitación del tiempo de juego, por lo tanto se tuvo especial cuidado de no mezclar partidas que fueron jugadas con reglas diferentes en el mismo sub-conjunto de datos. En la Figura 4.18 se muestran los coeficientes de Hurst H obtenidos, donde el último valor corresponde al resultado previamente expuesto obtenido para el período temporal posterior a 1998. Los mismos fueron calculados utilizando series temporales generadas a partir de las partidas que tomaron lugar en los diferentes períodos indicados en la Figura 4.18 y tomando τ = 1. Se observa como H, y por lo tanto la auto-similitud, crece con el tiempo. Esto implica que las partidas de la actualidad poseen correlaciones más persistentes que en períodos temporales anteriores. Este comportamiento puede estar relacionado al hecho de que en la actualidad resulta más fácil acceder a bases de datos de partidas registradas.

64

CAPÍTULO 4. RESULTADOS

(A) Elo=2000−2900 4

10

3

10

2

10

1

10

3

4

10

5

10

6

10

10

7

10

(B) Elo=1000−1999 4

E[R(n)/S(n)]

10

3

10

2

10

1

10

2

10

3

4

10

5

10

10

6

10

(C) Elo=1−999 3

10

2

10

1

10

0

10

1

10

2

3

10

10 n

Figura i4.17: Cálculo de H mediante el método de Rango Reescalado:Gráfico log-log de h

E R(n) S(n) vs. n por intervalo de Elo correspondiente a la serie temporal calculada con τ = 10. Las regresiones lineales devuelven una pendiente H = 0,54±0,02 para Elo=1-999 (línea roja), H = 0,60 ± 0,02 para Elo=1000-1999 (línea verde) y H = 0,67 ± 0,01 para Elo=2000-2900 (línea azul).

4

10

4.4. ANÁLISIS DE CORRELACIONES

65

Exponente de Hurst por intervalo de tiempo

0.7

0.65

H

0.6

0.55

0.5

0.45

0.4

7

el punto rojo representan el valor obtenido utilizando la base desde 1998.

00

7

99

9

Figura 4.18: Coeficiente de Hurst en diferentes períodos temporales. La línea roja tanto como

-2

98

19 -1

98

9

97

-1

90

19

80

19

9

96

-1

70

19

9

95

-1

60

19

9

94

-1

50

19 -1

38

19 7

93

-1

20

19 9

91

-1

00

19

9

89

-1

78

18

intervalo de tiempo

5. Conclusiones Los resultados obtenidos en este trabajo se pueden resumir como sigue: Se reprodujeron los resultados de Blasius y Tönjes, lo que da consistencia al trabajo realizado. Las series temporales generadas a partir de la base de datos de ajedrez, independientemente de la elección del parámetro τ , no poseen correlaciones espurias, son estacionarias y muestran correlaciones de largo alcance, similarmente a los resultados obtenidos en el análisis de cuerpos literarios llevados a cabo por Montemurro y Pury[2]. La presencia de correlaciones de largo alcance está relacionada al nivel de los jugadores. Los jugadores de niveles superiores exhiben correlaciones significativas, mientras que en jugadores débiles no se observan correlaciones. Las correlaciones de largo alcance muestran una tendencia de crecimiento en el tiempo. Posibles continuaciones: Actualmente se está trabajando en un modelo para generar partidas, basado en un mecanismo de conexión preferencial, que produzca series temporales con correlaciones de largo alcance y posea una distribución de Zipf. Realizar el estudio de las correlaciones de largo alcance generando la serie temporal asignandolé a cada elemento de la misma la popularidad de las partidas a una profundidad definida, similarmente a la asignación realizada por Montemurro y Pury en el estudio de cuerpos literarios.

67

68

CAPÍTULO 5. CONCLUSIONES Estudiar la aplicación de la ley de Heaps[40] a las aperturas de la base de datos de ajedrez con el fin de observar la forma en la que crece el número de partidas nuevas en función del número total de las mismas.

A. Apéndice A.0.1.

Implementación del Método de Rango Reescalado

!Implementación del método R/S a una serie temporal con n_tot=1382894 elementos ! tomando num=10 muestras. program rs implicit none integer(16),parameter integer(16) integer(8),dimension(n_tot,10) real(8),dimension(num) real(16),dimension(:),allocatable real(8)

::n_tot=1382894,num=10 ::i,k,j,n,l,p,t,c,k_max,q ::x ::e_tot ::y,y2,z,r,s,e,w ::m

open(unit=1,file=’serie-temporal.txt’,action=’read’) open(unit=2,file=’rs.txt’) do i=1,n_tot read(1,*)x(i,:) end do !Se indica el número máximo de intervalos en los que se divide la serie !y se inicializan los valores de k (número de intervalos) y el contador c. k_max=2**num k=1 c=1 do while(k .lt. k_max) 69

70

APÉNDICE A. APÉNDICE

allocate(e(k)) allocate(r(k)) allocate(s(k)) !Se determina la cantidad de puntos de cada intervalo. if((n_tot-int(n_tot/float(k))) .le. 0.5)then n=int(n_tot/float(k)) else n=int(n_tot/float(k))+1 end if allocate(y(n)) allocate(y2(n)) allocate(z(n)) !Para cada intervalo: do j=0,k-1 m=0. !Se calcula la media do p=j*n+1,(j+1)*n m=m+x(p,2) end do m=m/float(n) y=0. y2=0. !Se calcula una serie centrada en la media do q=j*n+1,(j+1)*n y(q-j*n)=x(q,2)-m y2(q-j*n)=(y(q-j*n))**2 end do !Se calcula la desviación estándar s(j+1)=sqrt((1/float(n))*sum(y2)) z(1)=y(1) !Se calcula el perfil integrado do t=1,n-1 z(t+1)=z(t)+y(t+1)

71 end do !Se calcula el rango R y el cociente R/S r(j+1)=maxval(z)-minval(z) e(j+1)=r(j+1)/s(j+1) end do !Se promedia sobre todos los valores de R/S otenidos para cada intervalo e_tot(c)=(1/float(k))*sum(e) write(2,*)n,e_tot(c) c=c+1 k=k*2 deallocate(y) deallocate(y2) deallocate(z) deallocate(e) deallocate(r) deallocate(s) end do close(1) close(2) end program

A.0.2.

Implementación del Método de DF A

!Implementación del método DFA a una serie temporal con n_tot=1382894 elementos !tomando num=10 muestras. program dfa implicit none integer(16),parameter integer(16)

::n_tot=1382894,num=10 ::i, j, p, q, r, t,c

72 integer(16) integer(8),dimension(n_tot,7) real(16),dimension(:),allocatable real(16), dimension(n_tot) real(16)

APÉNDICE A. APÉNDICE ::k_max, k, n ::x ::w, e ::y,z ::m, a, b, e2, f

open(unit=1,file=’serie-temporal.txt’,action=’read’) open(unit=2,file=’dfa.txt’) do i=1,n_tot read(1,*)x(i,:) end do do p=1,n_tot m=m+x(p,2) end do m=m/float(n_tot) do q=1,n_tot y(q)=x(q,2)-m end do !Una vez obtenida la serie centrada en la media se calcula el perfil !integrado de toda la serie z(1)=y(1) do r=1,n_tot-1 z(r+1)=z(r)+y(r+1) end do !Se indica el número máximo de intervalos en los que se divide la serie !y se inicializan los valores de k (número de intervalos). k_max=2**num k=1 do while(k .lt. k_max)

73 !Se determina la cantidad de puntos de cada intervalo. if((n_tot-int(n_tot/float(k))) .le. 0.5)then n=int(n_tot/float(k)) else n=int(n_tot/float(k))+1 end if allocate(e(n)) allocate(w(n)) e=0. e2=0. !Para cada intervalo: c=0 do j=0,k-1 !Se extrae el sub-conjunto de datos de la serie temporal !correspondiente a cada intervalo tomado do i=j*n+1,(j+1)*n w(i-j*n)=z(i) end do write(*,*)k,c c=c+1 !Se realiza una regresión lineal para cada sub-conjunto de datos call regresion_lineal(w,n,a,b) !Se calculan los residuos do t=1,n e(t)=w(t)-(a*t+b) e2=(e(t))**2 +e2 end do end do !Se calcula la media cuadrática de los residuos de la serie f=sqrt(e2/float(n_tot)) write(4,*)n, (minval(e))**2, f-((minval(e))**2-f) write(2,*)n,f

74

APÉNDICE A. APÉNDICE

k=k*2 deallocate(w) deallocate(e) end do close(1) close(2) contains subroutine regresion_lineal(w,n,a,b) implicit none integer(16), intent(in) integer(16) real(16) real(16), intent(out) real(16),dimension(n), intent(in) sx=0. sy=0. sxy=0. sxx=0. do t=1,n sx=t+sx sy=w(t)+sy sxy=t*(w(t))+sxy sxx=t**2+sxx end do a=(sy*sx-n*sxy)/(sx**2-n*sxx) b=(sxy-a*sxx)/sx end subroutine end program

::n ::t ::sx,sy,sxy,sxx ::a,b ::w

Bibliografía [1] Bernd Blasius and Ralf Tönjes. Zipf’s Law in the Popularity Distribution of Chess Openings. Phys. Rev. Lett., 103:218701, Nov 2009. [2] Marcelo A. Montemurro and Pedro A. Pury. Long-range fractal correlations in literary corpora. Fractals, 10(04):451–461, 2002. [3] Santo Fortunato and Claudio Castellano. Scaling and universality in proportional elections. Phys. Rev. Lett., 99:138701, Sep 2007. [4] Jacob Ratkiewicz, Santo Fortunato, Alessandro Flammini, Filippo Menczer, and Alessandro Vespignani. Characterizing and modeling the dynamics of online popularity. Phys. Rev. Lett., 105:158701, Oct 2010. [5] Alejandro F. Rozenfeld, Sophie Arnaud-Haond, Emilio Hernández-García, Víctor M. Eguíluz, Ester A. Serrão, and Carlos M. Duarte. Network analysis identifies weak and strong links in a metapopulation system. Proceedings of the National Academy of Sciences, 105(48):18824–18829, 2008. [6] William Bialek, Andrea Cavagna, Irene Giardina, Thierry Mora, Edmondo Silvestri, Massimiliano Viale, and Aleksandra M. Walczak. Statistical mechanics for natural flocks of birds. Proceedings of the National Academy of Sciences, 109(13):4786–4791, 2012. [7] Fernando Peruani, Jörn Starruß, Vladimir Jakovljevic, Lotte Søgaard-Andersen, Andreas Deutsch, and Markus Bär. Collective motion and nonequilibrium cluster formation in colonies of gliding bacteria. Phys. Rev. Lett., 108:098102, Feb 2012. [8] Mariano Sigman, Pablo Etchemendy, Diego Fernandez Slezak, and Guillermo A Cecchi. Response time distributions in rapid chess: A large-scale decision making experiment. Frontiers in Neuroscience, 4(60), 2010. 75

76

BIBLIOGRAFÍA

[9] Haroldo V. Ribeiro, Renio S. Mendes, Ervin K. Lenzi, Marcelo del Castillo-Mussot, and Luís A. N. Amaral. Move-by-move dynamics of the advantage in chess matches reveals population-level learning of the game. PLoS ONE, 8(1):e54165, 01 2013. [10] Sergei Maslov. Viewpoint: Power laws in chess. Physics, 2:97, Nov 2009. [11] Statistical physics: Chess obeys the law. Nature, 462(7273):546–546, December 2009. [12] Marcelo A. Montemurro. Beyond the zipf-mandelbrot law in quantitative lingüistics. Physica A: Statistical Mechanics and its Applications, 300(3¿4):567 – 578, 2001. [13] Marcelo A. Montemurro and D. Zanette. New perspectives on zipf’s law in liguistics: form single texts to large corpora. Glottometrics, 4:87–99, 2002. [14] Alexander M. Petersen, Joel N. Tenenbaum, Shlomo Havlin, H. Eugene Stanley, and Matjaz Perc. Languages cool as they expand: Allometric scaling and the decreasing need for new words. Scientific Reports, 2:–, 2012. [15] Matthieu Cristelli, Michael Batty, and Luciano Pietronero. There is more than a power law in zipf. Sci. Rep., 2, November 2012. [16] Edward T. Lu and Russell J. Hamilton. Avalanches and the distribution of solar flares. The Astrophysical Journal, 380:L89, October 1991. [17] Michael Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226–251, 2003. [18] Wentian Li. Random texts exhibit zipf’s-law-like word frequency distribution. IEEE Transactions on Information Theory, pages 1842–1845, 1992. [19] Eduardo G. Altmann and Giampaolo Cristadoro. On the origin of long-range correlations in texts. Proceedings of the National Academy of Sciences, 2012. [20] C.-K. Peng, S. V. Buldyrev, A. L. Goldberger, S. Havlin, F. Sciortino, M. Simons, and H. E. Stanley. Long-range correlations in nucleotide sequences. Nature, 356(6365):168–170, March 1992. [21] http://www.fide.com/component/handbook/?id=124&view=article. [22] C. Padrón Sancho. Juego de Reyes. Historia y Vida, vol. 494, May 2009.

BIBLIOGRAFÍA

77

[23] Mark E. Glickman. Chess rating systems. American Chess Journal, 3:59–102, 1995. [24] Hal Stern. Are all linear paired comparison models empirically equivalent? Mathematical Social Sciences, 23(1):103 – 117, 1992. [25] Jan Beran. Statistics for Long-Memory Processes. Chapman-Hall, 1st edition, 1994. [26] Richard G. Clegg. A practical guide to measuring the Hurst parameter. 21st UK Performance Engineering Workshop, School of Computing Science Technical Report Series, CSTR-916, University of Newcastle, pages 43–55, 2006. [27] Jan W Kantelhardt, Eva Koscielny-Bunde, Henio H.A Rego, Shlomo Havlin, and Armin Bunde. Detecting long-range correlations with detrended fluctuation analysis. Physica A: Statistical Mechanics and its Applications, 295(3):441–454, 2001. [28] Y. Shao, G. Gu, Z. Jiang, W. Zhou, and D. Sornette. Comparing the performance of FA, DFA and DMA using different synthetic long-range correlated time series. Scientific Reports, 2:835, Nov 2012/online. [29] Zipf, George K. Human behavior and the principle of least effort. Cambridge, (Mass.): Addison-Wesley, 1949, pp. 573. Journal of Clinical Psychology, 6(3):306– 306, 1950. [30] M. E. J. Newman. Power laws, Pareto distributions and Zipf’s law. Contemporary Physics, 46(5):323–351, May 2005. [31] Claude E. Shannon. Programming a computer for playing chess. Philosophical Magazine, 41:256–275, 1950. [32] http://scid.sourceforge.net/. [33] Didier Sornette. Multiplicative processes and power laws. Physical Review E, 57(4):4811, 1998. [34] Didier Sornette and Rama Cont. Convergent multiplicative processes repelled from zero: power laws and truncated power laws. Journal de Physique I, 7(3):431–444, 1997. [35] Mark Levene and Judit Bar-Ilan. Comparing typical opening move choices made by humans and chess engines. The Computer Journal, 50(5):567–573, 2007.

78

BIBLIOGRAFÍA

[36] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1). [37] Herbert A Simon. On a class of skew distribution functions. Biometrika, pages 425–440, 1955. [38] Konstantin Klemm, Víctor M Eguíluz, and Maxi San Miguel. Scaling in the structure of directory trees in a computer cluster. Physical review letters, 95(12):128701, 2005. [39] http://scidvspc.sourceforge.net/. [40] Linyuan Lü, Zi-Ke Zhang, and Tao Zhou. Zipf’s law leads to heaps’ law: Analyzing their relation in finite-size systems. PLoS ONE, 5(12):e14139, 12 2010.