### Authors

- Alexis Leboeuf
- Minh Tuan Vu
- Thibaut Rochas
- Amaël Kesteman

#### Rapport au format PDF

Vous trouverez également le rapport au format PDF dans le projet.

# Introduction

Depuis la création du jeu d'échecs, celui-ci a toujours été considéré comme un symbole d'intelligence, où l'on considère les meilleurs joueurs de ce jeu comme parmi les personnes les plus intelligentes de notre monde.

Il fut donc logique pour les informaticiens, au fil du temps, de vouloir développer différents programmes d'échecs afin de montrer la supériorité de la machine et de ceux-ci. Un des premiers exemples de cette volonté est le programme **Turochamp**, développé par **Alan Turing** et **David Gawen Champernowne**.  
Turochamp a été conçu avant même la création des premiers ordinateurs, ce qui montre l'intérêt des échecs pour pouvoir comparer l'intelligence de la machine face à celle de l'homme.

L'ordinateur a pu battre pour la première fois l'homme lors du fameux match Deep Blue contre Garry Kasparov lors de **la revanche de 1997** ([source INA](https://www.ina.fr/ina-eclaire-actu/1997-l-ordinateur-deep-blue-bat-garry-kasparov-un-tournant-dans-l-histoire-des-echecs), [Wikipédia](https://fr.wikipedia.org/wiki/Matchs_Deep_Blue_contre_Kasparov)) avec un score de 3,5 à 2,5 (3 égalités, 2 victoires et 1 défaite pour Deep Blue).  
Lors de ce match, Deep Blue a utilisé pour la première fois « l'ancêtre » des *Tablebases*, inspiré d'une base de données à 5 pièces créée en 1980 par **Ken Thompson**. Depuis, différentes Tablebases ont été développées et vont jusqu'à **7 pièces** sur l'échiquier ; cependant, nous allons nous concentrer sur une Tablebase **3–5 pièces** pour des raisons de taille de la base. La Tablebase 3–5 contient donc toutes les combinaisons possibles de coups jusqu'à une fin de partie, en partant de 3 à 5 pièces sur le plateau.

Actuellement, les ordinateurs ont largement dépassé les joueurs humains et les Tablebases en sont une raison principale, car elles permettent de connaître le résultat des finales, peu importe les coups joués par les deux joueurs.

Pour étudier ces bases de données, nous allons nous concentrer sur **Redis** ([Wikipédia](https://en.wikipedia.org/wiki/Redis)), la base de données **key/value** ([source](https://en.wikipedia.org/wiki/Key%E2%80%93value_database)) la plus utilisée.  
Dans un premier temps, nous présenterons Redis, son fonctionnement et son histoire. Puis, dans un deuxième temps, nous expliquerons le fonctionnement du stockage de la position : comment transformer la position du plateau d'échecs en une simple clé. Enfin, nous analyserons les performances d’accès à l’aide de Redis et verrons si le nombre de pièces a une incidence sur ces performances.

# Redis

Redis est une structure de données **NoSQL**([NoSQL](https://fr.wikipedia.org/wiki/NoSQL)) clés/valeurs open source, elle a été lancée en 2009 par Salvatore Sanfilippo, son nom signifie **Re**mote **Di**ctionary **S**erver. Sa caractéristique principale est sa rapidité, car les données sont stockées et manipulées principalement en mémoire vive (RAM), contrairement aux systèmes classiques reposant sur le disque dur. Cette architecture permet des temps d'accès très faibles, ce qui la rend particulièrement adaptée comme cache applicatif.

Dans le cadre de notre étude, Redis est utilisé pour stocker les positions d'échecs dans les Tablebases. Chaque position est représentée par une clé unique dérivée par la notation **FEN** (Forsyth-Edwards Notation) et les informations associées comme les résultats WDL (Win/Draw/Loss) ou DTZ (Distance to Zeroing) sont stockées en tant que valeurs.

Cette approche présente plusieurs avantages. Le chargement et l’interrogation des positions pré-calculées sont extrêmement rapides, et ce, même lorsque les requêtes portent sur des millions d’entrées. Cela permet d’exploiter les Tablebases comme un "oracle" quasi instantané. Cependant, ces performances reposent sur un coût important : comme Redis stocke l'entièreté de ses données en mémoire vive, la consommation de celle-ci augmente directement avec le nombre de positions chargées. Pour des Tablebases à 3, 4 ou 5 pièces, la taille reste raisonnable, mais au fur et à mesure que le nombre de pièces augmente, le volume de données devient très important. Dans ce cas, l’utilisation de Redis peut atteindre des dizaines ou centaines de gigaoctets de mémoire, posant un compromis entre performance et ressources matérielles disponibles.

Ainsi, Redis offre une solution particulièrement efficace pour manipuler des positions d’échecs pré-calculées, mais nécessite une maîtrise fine du stockage mémoire et de la structure des données utilisées, surtout lorsque la taille des Tablebases augmente.

# Stockage

Afin de stocker efficacement les positions d’échecs, qui sont extrêmement nombreuses, nous utilisons la notation **FEN** (Forsyth–Edwards Notation). Celle-ci encode de manière compacte l’ensemble de l’état d’un échiquier dans une chaîne de caractères unique.  
Les bases de données de type **Syzygy** ([site officiel](https://syzygy-tables.info/), [GitHub](https://github.com/syzygy1/tb)) utilisent cette FEN comme point de départ : elle est ensuite hachée ou convertie en un index interne afin d’accéder rapidement aux informations de Tablebase.

Dans notre étude, nous utilisons **Redis**, qui peut stocker cette FEN directement comme clé dans un schéma *key/value*.  
Prenons pour exemple la FEN suivante :

4k3/8/3n4/8/7p/1P6/4B3/4K3 b - - 0 1

![Exemple FEN](image/FEN exemple.png)

Chaque élément de la FEN représente une ligne du plateau. Nous allons pouvoir la décomposer :

- `4k3` pour la 8e ligne indique **4 cases vides**, puis **le roi noir (k)**, puis **3 cases vides**.
- Les lettres **minuscules** (`k`, `q`, `r`, `b`, `n`, `p`) représentent les **pièces noires**.
- Les lettres **majuscules** (`K`, `Q`, `R`, `B`, `N`, `P`) représentent les **pièces blanches**.
- La lettre `b` indique que **c’est au tour des Noirs de jouer**.
- Les symboles qui suivent concernent les règles particulières du jeu : roque, prise en passant, compteur de coups et numéro du tour.

Voici les lettres correspondant à chaque pièce :

**K = roi, N = cavalier, B = fou, R = Tour, Q = Reine, P = pion**

Par la suite, il y a une lettre b ou w indiquant le jour qui joue le prochain coup. Enfin, il y a 4 caractères par la suite concernant les règles d'échecs particulières qui ne seront pas détaillés ici.
Voici un second exemple représentant la position de départ d'une partie d'échecs :
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

### Utilisation comme clé de stockage

Une fois la position encodée en FEN, on peut utiliser directement comme clé unique dans une base de données.
Dans le cas de Syzygy, la chaîne FEN est transformée en un index interne ou hachée pour pointer vers les données de Tablebase.
Dans Redis, cette même FEN peut servir telle quelle comme clé (string) d’où l’on peut associer des valeurs comme WDL ou DTZ.
Cette approche garantit qu'une position donnée correspond toujours à une clé unique et reproductible, ce qui permet un accès direct à l’information associée, sans ambiguïté.

# Approche Scientifique et Méthodologie Expérimentale

Cette section décrit la méthodologie utilisée pour évaluer les performances de **Redis** par rapport à **Syzygy** dans le stockage et l’accès aux positions d’échecs.  
L’objectif est d’obtenir des mesures **reproductibles**, **interprétables** et **valides**, tout en identifiant les biais possibles pouvant affecter l’analyse.

## Objectifs expérimentaux

Les expériences menées ont pour but de répondre aux hypothèses suivantes :

- **H1 – Incidence du nombre de pièces**  
  Nous supposons que le nombre de pièces présentes sur l’échiquier n’influe pas sur les performances d’accès de Redis.

- **H2 – Gain de performance**  
  Nous supposons que Redis, en tant que base de données spécialisée dans les systèmes *key/value*, offre de meilleures performances que l’accès direct sur disque aux tablebases **Syzygy**.  
  De plus, Redis stockant ses paires clé/valeur en mémoire vive, nous nous attendons à un gain de performance significatif dû au temps d’accès à la RAM, bien inférieur à celui du disque.

- **H3 – Optimisation des clés via Zobrist**  
  Nous supposons que l’utilisation du hash **Zobrist** fourni par la bibliothèque *python-chess* permet d’améliorer le temps d’accès ou l’utilisation mémoire par rapport à une clé FEN classique.

- **H4 – Optimisation des clés via un hash classique**  
  Nous supposons que l’utilisation d’un hash classique permet également d’améliorer le temps d’accès ou l’utilisation mémoire, mais de manière moins efficace que le hash Zobrist.

## Environnement expérimental

Cette section décrit l’environnement matériel et logiciel utilisé pour la réalisation des expériences (configuration matérielle, système d’exploitation, versions des logiciels et bibliothèques).

## Méthodologie de mesure

Afin de vérifier chacune de ces hypothèses, nous étudions différentes métriques sur des jeux de données de test :

1. **Temps moyen d’exécution** :  
   mesure du temps nécessaire pour accéder à une position dans Redis ou Syzygy, analysée à l’aide de tests statistiques.

2. **Espace mémoire utilisé par Redis** :  
   évaluation de la consommation de mémoire vive à partir des outils fournis par Redis.

3. **Nombre de requêtes par seconde (RPS)** :  
   mesure du débit maximal supporté par chaque solution.

4. **Temps médian et percentile 95** :  
   analyse de la dispersion des temps d’accès et des valeurs extrêmes.

## Génération des positions

Pour chacun de ces tests, nous utilisons une base de **2250 positions**, tirées des configurations de tablebases **Syzygy** que nous avons exploitées.  
Ce nombre a été choisi afin de permettre l’exécution des tests sur des machines disposant de capacités mémoire limitées, quelle que soit la quantité de mémoire vive (RAM) disponible.

## Comparatif

Étant donné que le même jeu de données est utilisé pour l’ensemble des expériences et que plusieurs machines sont à disposition, nous pouvons comparer le comportement de Redis en fonction :

- de la quantité de mémoire RAM,
- du type de disque utilisé,
- du processeur.

Nous analysons ainsi l’impact de ces paramètres sur le temps de réponse et l’utilisation des ressources.  
Si possible, nous envisageons également d’étendre les expériences à des jeux de données plus grands ou plus petits afin d’obtenir des statistiques plus fines et représentatives.

# Résultats et Interprétations

## Test 1 : Incidence du nombre de pièces

Afin de tester si le nombre de pièces présentes dans une configuration a une incidence sur le temps de chargement depuis **Redis**, nous avons réalisé un script permettant d’effectuer plusieurs requêtes sur un serveur Redis pour des configurations à **3, 4 et 5 pièces**.

Pour chaque configuration, nous avons exécuté un nombre variable de requêtes :

- 100
- 1 000
- 5 000
- 10 000
- 50 000
- 100 000

Pour chaque test, nous avons mesuré le **temps minimal**, **moyen** et **maximal** d’accès aux positions.

Après analyse des valeurs obtenues, nous constatons que les temps mesurés restent très proches, malgré l’augmentation significative du nombre de requêtes.  
De plus, que ce soit pour **3 ou 5 pièces**, on observe sur la **Figure 1** que les temps moyens restent de l’ordre du **dixième de seconde**.

![Moyenne du temps de requête](image/moyenne_temps.png)

Les graphiques des temps minimum et maximum montrent également des valeurs cohérentes. Les quelques valeurs aberrantes observées sont probablement liées au matériel plutôt qu’à l’algorithme lui-même.

En effet, la documentation indique que la mémoire **DDR4** cadencée autour de **3 000 MHz** permet des débits de lecture d’environ **20 Go/s**. Étant donné que les tables utilisées ne dépassent pas **20 Mo**, les résultats obtenus apparaissent cohérents.

Concernant les temps minimum et maximum, ceux-ci étant fortement dépendants du comportement matériel, ils sont moins représentatifs et ne permettent pas de tirer des conclusions solides.  
Néanmoins, l’analyse des temps minimum montre des valeurs proches entre les différentes configurations, ce qui confirme l’absence d’impact significatif du nombre de pièces sur les performances.

## Test 2 : Gain de performances

Après avoir testé **Syzygy** et **Redis** sur un même jeu de données (voir *Notebook Python*), nous sommes arrivés aux conclusions suivantes :

- Redis est **près de 11 fois plus rapide** que Syzygy.
- La latence moyenne de Redis est de **0,35 ms**, contre **3,82 ms** pour Syzygy.
- La médiane est également plus faible pour Redis (**0,33 ms**) que pour Syzygy (**1,06 ms**).
- Redis permet en moyenne **1 969 requêtes par seconde**, contre seulement **280 requêtes par seconde** pour Syzygy.

Ces résultats sont **statistiquement significatifs**, comme le montrent :
- le test *t* de Student apparié (*t* = 92,45, *p* < 0,001),
- le test de Kolmogorov–Smirnov (*KS* = 0,708, *p* < 0,001).

Ces résultats valident l’hypothèse **H2**.

## Test 3 : Optimisation des clés avec le hash Zobrist

Afin de vérifier si une autre structure de clé pouvait améliorer les performances ou l’utilisation mémoire, nous avons testé, en plus du stockage classique via la **FEN**, l’utilisation du **hash Zobrist** fourni par la bibliothèque *python-chess*.

La comparaison entre la base utilisant des clés FEN et celle utilisant des clés Zobrist met en évidence les points suivants :

- Le hash Zobrist est environ **20 % plus rapide** que le stockage en FEN  
  (moyenne de **252,5 s** contre **308,1 s**).
- Le débit est nettement supérieur, avec en moyenne **55 % de requêtes supplémentaires**  
  (**3 405** contre **2 197**).
- L’utilisation mémoire est également améliorée, avec une clé FEN occupant en moyenne  
  **117,26 bytes/clé**, contre **107,64 bytes/clé** pour Zobrist (gain d’environ **8 %**).

Ces résultats sont **statistiquement significatifs**, selon :
- le test *t* de Student apparié (*t* = 111,79, *p* < 0,001),
- le test de Kolmogorov–Smirnov (*KS* = 0,45, *p* < 0,001).

L’hypothèse **H3** est donc validée.

## Test 4 : Optimisation des clés avec un hash classique

Pour vérifier l’hypothèse **H4**, nous avons créé une base de données utilisant des **clés hashées classiques**, puis comparé ses performances avec une base utilisant des clés FEN.

Les résultats observés sont les suivants :

- Avec les clés FEN :
    - latence moyenne de **0,709 ms**,
    - **1 068 requêtes par seconde**.
- Avec les clés hashées :
    - latence moyenne de **0,448 ms**,
    - **1 496 requêtes par seconde** en moyenne.

Cela représente une amélioration de plus de **35 %** en termes de latence et de débit.

Le gain est également notable sur la consommation mémoire :
- une clé FEN occupe en moyenne **136,46 bytes**,
- une clé hashée occupe en moyenne **97,94 bytes**,

soit un gain de **28,3 %**.

Ces résultats sont **statistiquement significatifs**, comme l’indiquent :
- le test *t* de Student apparié (*t* = -44,042, *p* < 0,001),
- le test de Kolmogorov–Smirnov (*KS* = 0,69, *p* < 0,001).

L’hypothèse **H4** est ainsi validée.

# Conclusion

## Synthèse des résultats

Avec l’aide de nos expériences, nous avons pu montrer que d’autres solutions plus rapides que  
les solutions actuellement mises en place par les sites d’échecs existent. En effet, nous avons vu  
que Redis est nettement plus rapide que Syzygy et qu’il offre également un débit presque 7 fois  
supérieur. Il en va de même pour la façon de stocker les positions.Si l’on garde le système de  
stockage classique des échecs, on ralentit encore plus le système, car les fonctions de hashage  
nous permettent également de gagner en performance et en mémoire, avec pour chacune des  
fonctions, une augmentation de minimum 18% en termes de débit mais aussi d’un gain en  
mémoire conséquent avec plus de 25% pour la fonction de hashage classique. La question se  
pose alors de pourquoi l’on n’utilise pas Redis et le hashage. Utiliser le hashage reviendrait à  
perdre de l’information, ce qui est dans ce cas contradictoire comme c’est justement ce que l’on  
cherche à stocker. Enfin, le gain entre Redis et Syzygy est minime et n’est pas pertinent pour  
plusieurs raisons : Redis en tant que système in-memory est inadapté pour les Tablebases qui  
font des centaines de Go, il faut donc un système sur disque où Syzygy est bien meilleur grâce  
à la compression. L’accès aux Tablebases est aussi très rare et se fait de manière ciblée, sur  
une position et s’il y a un changement, cela se tourne vers une position très similaire, le gain de  
performances de Redis est donc moins pertinent dans le véritable usage. Enfin, il ne serait pas  
possible économiquement de maintenir un tel système avec Redis.

Cette étude nous a néanmoins permis de comparer les différences de performances entre les  
approches disques (Syzygy) et les approches mémoires (Redis), de démontrer le poids du choix  
de la structure des clés et de mieux comprendre quel système doit être utilisé selon le contexte.

Pour conclure, bien que Redis et le hashage offrent des gains non négligeables, le système  
actuel utilisant la FEN et Syzygy reste le meilleur en s’appuyant sur l’efficacité du stockage et  
la maintenabilité que la performance brute dans le cadre du stockage complet des Tablebases.

## Limites de l’étude

Même si les résultats obtenus sont informatifs, plusieurs aspects doivent être pris en compte.  
Tout d’abord, notre étude ne s’appuie que sur un sous-ensemble réduit des véritables tablebases  
Syzygy : seules les configurations jusqu’à 5 pièces ont été testées, ce qui exclut les tablebases  
plus volumineuses à 6 et 7 pièces. L’échantillon utilisé reste donc limité et ne permet pas de  
tirer des conclusions définitives sur la performance à grande échelle.

Les expériences ont été menées sur nos machines personnelles plutôt que sur des serveurs  
dédiés ou des configurations hautes performances utilisées par certaines organisations spécialisées.[8]  
Cela peut influencer à la fois la consommation mémoire observée et les temps d’accès, et limite  
la généralisation des résultats.

Enfin, notre analyse s’est concentrée uniquement sur les aspects performance (latence, RPS,  
mémoire vive). D’autres dimensions importantes des tablebases — telles que la fiabilité, la com-  
pression, l’intégrité des données, ou encore les implications pratiques pour les moteurs d’échecs  
— n’ont pas été explorées dans cette étude.

À ces limitations s’ajoute une contrainte méthodologique liée à la mesure de la mémoire :  
Redis stocke et traite ses données exclusivement en mémoire vive, ce qui rend impossible une  
séparation nette entre mémoire de stockage et mémoire d’exécution. Pour Syzygy, nous avons dû  
mesurer la mémoire du processus via la bibliothèque psutil, tandis que pour Redis nous n’avons  
accès qu’à la consommation totale rapportée par le serveur. Nous avons observé que Syzygy  
a utilisé environ 205Mo de RAM pour exécuter et lire des tablebases qui est 21,6 Mo, tandis  
que Redis a consommé seulement environ 169 Mo pour le même jeu de données. Toutefois, ces  
valeurs sont fortement dépendantes de la taille réduite du dataset utilisé. Sur des bases plus  
importantes, la consommation de Redis pourrait croı̂tre beaucoup plus rapidement, rendant les  
comparaisons moins triviales.

## Ouverture (Tablebases à 8 pièces)

Depuis 2012, Les Tablebases à 7 pièces existent, mais il a fallu attendre août 2018 avant qu’elles  
soient complètes. Ceci illustre la difficulté du jeu d’échecs et montre pourquoi, au contraire  
d’autres jeux comme le jeu de dames, ne sera pas résolu. Actuellement, les Tablebases à 8 pièces  
ont 15 % des finales sans pions résolues. [10] Ceci montre la difficulté de la progression pour finir  
les Tablebases. De plus, on estime la taille totale à plusieurs Pétaoctects, ce qui ne serait même  
pas utilisable pour la majorité des ordinateurs, même les plus puissants. Ceci vient du fait que  
la base serait 90 fois plus grande que la base à 7 pièces. Enfin ceci aurait seulement un intérêt  
théorique et changerait juste la vision de certaines finales (certaines fins de partie autrefois  
considérées comme perdantes ont été classifiées comme nulle avec l’apparition des tablebases).


# Annexe

Figure 2 : Minimum du temps de requête en fonction du nombre de pièces et du nombre de requêtes.

![Minimum du temps de requête](image/min_temps.png)

Figure 3 : Maximum du temps de requête en fonction du nombre de pièces et du nombre de requêtes.

![Maximum du temps de requête](image/max_temps.png)


# Glossaire

**FEN**  
Notation standard utilisée dans le monde des échecs pour exprimer une position en chaı̂ne  
de caractères.. 

**Tablebase**  
Base de données exhaustive, contenant toutes les possibilités dans un monde limité  
ainsi donc que leur résultat optimal.. 


## Références

- **1997 : l'ordinateur bat Garry Kasparov, un tournant dans l'histoire des échecs**  
  https://www.ina.fr/ina-eclaire-actu/1997-l-ordinateur-deep-blue-bat-garry-kasparov-un-tournant-dans-l-histoire-des-echecs

- **Matchs Deep Blue contre Kasparov — Wikipédia**  
  https://fr.wikipedia.org/wiki/Matchs_Deep_Blue_contre_Kasparov

- **Redis — Wikipédia (EN)**  
  https://en.wikipedia.org/wiki/Redis

- **Key/value — Wikipédia (EN)**  
  https://en.wikipedia.org/wiki/Key%E2%80%93value_database

- **NoSQL — Wikipédia**  
  https://fr.wikipedia.org/wiki/NoSQL

- **Syzygy Endgame Tablebases — Ronald de Man**  
  https://syzygy-tables.info/

- **Syzygy Endgame Tablebases — GitHub Repository**  
  https://github.com/syzygy1/tb

- **What is Redis? — IBM**  
  https://www.ibm.com/think/topics/redis

- **Eight-piece tablebases — Peter Wong**  
  https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-progress-update-and-some-results

- **Taux de transfert, bande passante et latences DDR4 — Jean-Pierre Novak**  
  https://www.eatyourbytes.com/fr/debit-vitesse-latences-et-voltage-des-memoires-ram-ddr4

- **Microsoft Azure, partenaire de la FFE**  
  https://www.echecs.asso.fr/Actu.aspx?Ref=14252