1 pièce(s) jointe(s)
Lecture d'un fichier texte et choix d'une variante, peut-on rendre intelligente la bibliothèque d'ouverture*?
Maintenant que mon programme connaît les règles de déplacement des pièces et de manière à commencer à le faire jouer un peu, j'ai décidé de créer la bibliothèque d'ouverture.
J'ai pu récupérer quelques fichiers au format texte contenant les ouvertures sous la forme e2e4 e7e5 b1c3 b8c6 etc... Ce type de fichier présente plusieurs avantages:
- Il est d'une simplicité biblique, quand on l'ouvre on comprend tout de suite comment l'utiliser.
- Il est relativement facile à compléter, puisqu'il suffit de saisir à la suite les variantes sous la forme case départ case arrivée, on peut pour cela se contenter du bloc note windows.
- La mise en œuvre est immédiate.
- On peut même structurer le fichier, trier les variantes (dans un traitement de texte), rajouter des titres par groupe d'ouverture etc, sans altérer le contenu puisque le programme devra simplement recherche dans ces chaines de caractère une série qui correspond à une liste de coups joués provenant du programme, s'il y a des lignes supplémentaires ou des commentaires il ne les retiendra pas comme variante.
Inconvénients:
- La modification du fichier est simple mais elle demande une grande rigueur car il n'y a aucun contrôle de cohérence des coups saisies, il faut donc bien préparer son travail et se relire, c'est un peu long et fastidieux pour saisir de très nombreuses variantes, on pourrait toutefois imaginer un petit utilitaire qui permettrait un plus grand confort et un contrôle automatique, mais ce serait long à développer.
- On trouve très peu de fichiers de ce type sur internet et ceux qu'on trouvent contiennent assez peu de données, le plus gros que j'ai trouvé est celui du programme d'échecs open source tscp de Tom Kerrigan's écrit en C,un fichier d'environ 4000 demi-coups, ce qui est suffisant pour démarrer. J'ai utilisé ce fichier en le modifiant un peu et en rajoutant des variantes.
Une fois muni d'un fichier de ce type on a envie de l'exploiter et pour cela il faut créer un module qui va lire le fichier texte pour rechercher une chaine de caractères identique à la liste des coups joués dans le programme. Chaque réponse trouvée est stockée dans un tableau, lorsqu'on arrive à la fin du fichier il suffit de relire le tableau et de choisir aléatoirement l'un des coups trouvés dans cette liste. Cette sélection aléatoire est nécessaire pour donner de la variété au programme sinon il jouera toujours la même chose dans une position donnée.
Ensuite je me suis posé la question de savoir s'il ne fallait pas créer deux fichiers de bibliothèque l'un à utiliser par le programme quand il a les Blancs et l'autre quand il a les noirs. En effet un joueur humain procède de la même manière, il connaît un certain nombre d'ouverture mais ne les joue pas lui-même en premier, il doit les connaître pour riposter, mais quand il a l'initiative il les évite car elle ne conviennent pas à son style de jeu par exemple. Je pourrais développer d'avantage cette idée en donnant des exemples concrets pour vérifier l'opportunité de cette option. Il ne serait d'ailleurs pas nécessaire de créer deux fichiers, un seul suffirait avec un indicateur au début de chaque variante B pour signifier au programme qu'il peut jouer cette variante avec les Blancs (N pour Noir) et X dans les deux cas. De cette manière on donnerait déjà un peu d'intelligence au programme dans une phase de jeu qui généralement ne fait appel qu'à la mémoire. , Je ne sais pas comment procède les forts programmes mais je pense que leur module d'ouverture est sûrement très sophistiqué.
Pour l'instant je ne vais pas me compliquer la tâche et j'utiliserai donc un seul fichier contenant des ouvertures standards ce module d'ouverture aura pour but de conduire le programme à une position équilibrée à la fin de l'ouverture.
A noter que ces quelques lignes de programme préfigure ce que sera le logiciel le plus fort de tous les temps lorsqu'on aura déterminé la suite de coups qui à partir du début de la partie mène irrémédiablement au mat. Il suffira de stocker ces coups dans la bibliothèque d'ouverture et jamais le programme n'aura besoin de réfléchir (c'est déprimant).
Moyennant quelques modifications on pourrait transformer ce petit programme pour en faire un outil d'apprentissage personnalisé des ouvertures (affichage du nom de la variante, le programme compte un point chaque fois que vous trouvez la bonne suite etc..), à vous de saisir dans le fichier les variantes que vous souhaitez mémoriser.
Voici le source réalisé pour tester mon module d'ouverture, il me reste à l'adapter pour l'intégrer à mon programme. Il fonctionne en toute autonomie avec le fichier txt que vous trouverez en pièce jointe.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| Program ReadBook;
{*** Lire un fichier d'ouverture, retenir les variantes qui correspondent
*** à la liste des coups déjà joués, mettre les coups trouvés dans un tableau
*** Choisir au hasard l'un de ses coups
*** écrit par Gérard Legat 27 avril 2015}
{$h+} {permet d utiliser des variables string > 255}
uses Classes, sysUtils ; { necessaire pour lire fichier}
var
inc, i, alea : integer;
Filename : string;
f : Textfile;
enreg : string;
coupKempelen : string;
Listecoups : string;
longueur : shortint;
extrait : string;
nouveaucoup : string;
reponseBiblio : array[1..300] of string;
begin
FileName := 'c:\users\glegat\documents\bibliokempelenv1.txt';
if not FileExists(Filename) then
begin
writeln('fichier non trouve : ',FileName);
readln;
halt;
end;
randomize;
nouveaucoup := '';
listecoups :='';
while nouveaucoup <> 'fin' do
begin
writeln;
{writeln(listecoups);}
write(' Votre coup : ');
readln(nouveaucoup);
listecoups := listecoups + nouveaucoup + ' ';
longueur := length(listecoups);
for i := 1 to 300 do reponsebiblio[i] := '';
begin
assignFile(F,FileName);
Reset(F);
inc := 1;
While not Eof(F) do
begin
{on lit l'enregistrement}
readln(F,enreg);
{on extrait la portion de chaine qui correspond à la longueur de la chaine a chercher}
extrait := copy(enreg,1,longueur);
{on compare l'extrait avec la suite de coup de la partie}
if extrait = listecoups then
begin
{on enregistre toutes les reponses de la bibliotheque};
reponsebiblio[inc] := copy(enreg,longueur+1,4);
inc := inc +1;
end;
end;
CloseFile(F);
end;
nouveaucoup := 'fin';
alea := random(inc);
if alea = 0 then alea := 1;
coupKempelen := reponsebiblio[alea];
if coupKempelen = ''
then
writeln('fin bibliotheque')
else
begin
write(' Kempelen joue : ',coupKempelen);
nouveaucoup :='';
listecoups := listecoups + coupKempelen +' ';
end;
end;
writeln('Le programme doit maintenant reflechir pour trouver un coup');
readln;
end. |
Que ceux qui auront la curiosité de l'essayer n'hésitent pas à me faire part de leurs remarques et suggestions.
Vous trouverez en pièce jointe un fichier compressé contenant :
BiblioKempelenv1.txt (bibliothèque d'ouverture)
ReadBook.pas le source
ReadBook.exe l'exécutable (pour ceux qui ne pourrait pas compiler).
Si vous souhaitez faire jouer la bibliothèque du point de vue des noirs le premier de vos coups sera un demi-coup par exemple e2e4, si vous souhaitez faire jouer la bibliothèque du point de vue des Blancs, jouez un coup complet par exemple e2e4 e7e5 (un espace entre les deux demi-coups).
Attention : n'oubliez pas de changer le chemin d'accès au fichier BiblioKempelen si vous recompilez le source, et si vous utilisez l'exécutable vous devrez créer les répertoires prévus dans mon exemple.
Meilleur évaluation du premier coup ou analyse en profondeur, par quoi commencer maintenant ?
Voici l'état d'avancement de mon projet à ce jour :
Mon programme (Kempelen) commence à jouer. Il connait les règles de déplacement des pièces, il peut répondre aux coups théoriques del 'ouverture grâce à sa bibliothèque (dans laquelle je rajoute de nouvelles variantes chaque jour, et lorsque je rencontre des lacunes). Il me reste maintenant à lui donner un peu d'intelligence pour choisir le meilleur coup une fois qu'il a quitté sa bibliothèque, c'est la partie la plus difficile évidemment, mais aussi la plus passionnante. Aujourd'hui j'ai crée une procédure qui permet d'alimenter deux tableaux, l'un pour les noirs l'autre pour les blanc, ce tableau contient l'information suivante*:
Pour chaque case de l'échiquier ces tableaux me renseigne sur les cases contrôlées, ainsi pour la case e4 par exemple je trouverais la valeur 0 si la case n'est pas contrôlée et une valeur positive de 1 à 9 qui indique combien de fois cette case est contrôlée par les blancs (même chose pour les noirs). Je pense que cette procédure que j'ai crée initialement pour vérifier si les cases autour du roi sont contrôlées, si le roque est possible etc... me sera très utile par la suite dans mon système d'évaluation.
Donc maintenant je commence à réfléchir à l'évaluation de la position, je peux mettre en œuvre très rapidement le critère matériel et le critère mobilité/Cases contrôlées, mais je me pose la question de savoir si je dois commencer maintenant l'écriture du module d'analyse en profondeur ou si je dois encore travailler sur l'évaluation du premier coup de la racine, autrement dit pour l'instant mon programme joue sur un demi-coup de profondeur (autrement pas de profondeur du tout) (je rappelle mon objectif de départ faire un programme simple sans interface graphique qui analyse sur deux demi-coups seulement dans un premier temps, je n'en suis donc pas très éloigné), mais par quoi dois-je continuer ?, maintenant que j'obtiens une liste de coups potentiellement jouables ? J'aurais tendance à penser qu'il me faut le faire jouer le mieux possible à ce niveau avant de faire l'analyse en profondeur mais j'hésite et comment trouver des critères d'évaluation sans analyser la moindre réponse de l'adversaire*? (même si l'information sur les cases contrôlées est déjà une première approche de l'analyse en profondeur).
tableaux vs liste chainées
Personnellement, je me méfierais de l'usage des tableaux à 2 dimensions, coté complexité d'une recherche en profondeur. La double indexation T[i][j] est très coûteuse. Il est préférable de mettre pour chaque case une liste de liste de pointeurs sur les cases possibles. Ainsi, n'importe quelle case de l'échiquier serait une structure avec la pièce qu'elle contient (ou pas), la couleur de la pièce, la note noire, la note blanche (calcul stratégique), le numéro de la zone (zone d'attaque ou de défense), et la liste des coups possibles pour chaque pièce. Donc, un vecteur de vecteurs (ie: p[0] = liste des cases accessibles pour la pièce 0, soit le pion, p[1], pour le cavalier, etc.)
La représentation n'est pas visuelle. Les cases sont également chaînées entre elles par quatre ou 8 pointeurs (pour aller de A1 en B1 ou B2).
Les algorithmes doivent utiliser ces chaînages pour les recherches en profondeurs et la notation globale (chaque case est notée, pondérée par les zones, puis l'échiquier à l'instant T est noté, et ensuite, on élague ou non l'arbre de recherche, etc.)
C'est comme cela que je le referai.
Après, faut peaufiner les algos et mettre un peu de stratégie et quelques grandes règles: un ordinateur doit chercher à réduire le nombre de pièces par des échanges, pour augmenter la recherche en profondeur exponentielle au nombre de pièces; l'humain contre l'ordinateur doit au contraire, refuser les échanges et maintenir le maximum de pièces sur l'échiquier, surtout en blitz).
