Discussion :

[Roland Chastain]

Bonjour !

Je suis en train de chercher (péniblement) comment représenter et manipuler l'arbre d'un livre d'ouvertures pour les échecs.

Ce qui m'a motivé à faire cette recherche, c'est la découverte du format imaginé par Kathe Spracklen et utilisé dans le programme d'échecs de Marc-Philippe Huget (voir les liens dans ce message). Je trouve ce format amusant et j'aurais bien aimé écrire un programme qui puisse gérer un fichier conçu sur ce modèle.

Dans la notice du programme de M.-Ph. Huget permettant de construire un livre à partir d'un fichier PGN, l'auteur donne l'exemple du livre d'ouvertures suivant :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    e4 e5 d4
    e4 c5
    d4 d5

Ce qui dans le format Spracklen donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

    (e4(e5(d4))(c5))(d4(d5))

Et moi j'aimerais avoir du code qui me permette 1° de construire le livre 2° de le lire 3° de l'éditer.

Mais je ne sais pas trop dans quelle direction partir. J'ai eu trois idées jusqu'à présent.

La première était une espèce de liste chaînée qui ressemblerait à quelque chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
uses
  SysUtils;
 
type
  PBranches = ^TBranches;
  TBranches = array of record
    Donnee: string;
    Suivantes: PBranches;
  end;
 
 
var
  Branches, NouvellesBranches: PBranches;
  i, j: integer;
 
begin
  New(Branches);
  SetLength(Branches^, 2);
  Branches^[0].Donnee := 'e4';
  Branches^[0].Suivantes := nil;
  Branches^[1].Donnee := 'd4';
  Branches^[1].Suivantes := nil;
 
  New(NouvellesBranches);
  SetLength(NouvellesBranches^, 2);
  NouvellesBranches^[0].Donnee := 'e5';
  NouvellesBranches^[0].Suivantes := nil;
  NouvellesBranches^[1].Donnee := 'c5';
  NouvellesBranches^[1].Suivantes := nil;
 
  Branches^[0].Suivantes := NouvellesBranches;
 
  for i := 0 to High(Branches^) do
  begin
    Write('(');
    Write(Branches^[i].Donnee);
    if Branches^[i].Suivantes <> nil then
      for j := 0 to High(Branches^[i].Suivantes^) do
      begin
        Write('(');
        Write(Branches^[i].Suivantes^[j].Donnee);
        Write(')');
      end;
    Write(')');
  end;
end.

La deuxième idée, que j'ai trouvée dans une discussion sur un forum, c'était d'utiliser des TStringList comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
uses
  SysUtils, Classes;
 
var
  Arbre, Branche: TStringList;
  i: integer;
 
begin
  Arbre := TStringList.Create;
  Arbre.AddObject('e4', TStringList.Create);
  Arbre.AddObject('d4', TStringList.Create);
 
  for i := 0 to Pred(Arbre.Count) do WriteLn(Arbre[i]);
 
  i := Arbre.IndexOf('e4');
  if i >= 0 then
  begin
    Branche := Arbre.Objects[i] as TStringList;
    Branche.AddObject('e5', TStringList.Create);
    Branche.Add('c5');
  end;
 
  Arbre.Free;
end.

La troisième idée était d'utiliser le format JSON avec une bibliothèque appropriée.

Comment verriez-vous la chose ?

P.-S. Le programme Book de M.-Ph. Huget fonctionne bien et il est livré avec son code source, en C++, que je n'ai pas encore vraiment étudié.

[Roland Chastain]

J'avance tout doucement, en continuant de chercher dans plusieurs directions (JSON, TVirtualStringTree...).

Ma tentative la plus avancée, c'est ce code Lua. Je vais me faire gronder si je vante ici les mérites d'un autre langage que le Pascal, mais je suis toujours étonné par la facilité avec laquelle on peut tout faire en Lua.

Code Lua :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
--[[
  Exemple :
  
    e4 e5 d4
    e4 c5
    d4 d5
  
  Résultat :
  
    (e4(e5(d4))(c5))(d4(d5))
--]]
 
json = require "json"
 
-- Création de l'arbre
local arbre = {["e4"] = {["e5"] = {["d4"] = {}}, ["c5"] = {}}, ["d4"] = {["d5"] = {}}}
 
-- Convertir l'arbre en chaîne JSON
print(json.encode(arbre))
-- {"d4":{"d5":[]},"e4":{"c5":[],"e5":{"d4":[]}}}
 
-- Liste des propositions pour le premier coup
for clef, valeur in pairs(arbre) do
  print(clef)
end
-- d4
-- e4
 
-- Liste des propositions après e4
for clef, valeur in pairs(arbre["e4"]) do
  print(clef)
end
-- c5
-- e5
 
-- Liste des propositions après e4 e5
for clef, valeur in pairs(arbre["e4"]["e5"]) do
  print(clef)
end
-- d4
 
-- Ajout d'une proposition après e4 c5
arbre["e4"]["c5"] = {["d4"] = {}}
print(json.encode(arbre))
-- {"d4":{"d5":[]},"e4":{"c5":{"d4":[]},"e5":{"d4":[]}}}
 
-- Utilisation de la fonction next()
local clef, valeur = next(arbre)
print(clef)
-- d4

Le seul défaut des tables Lua, c'est qu'elles ne conservent pas l'ordre.

Autrement, ce code fait à peu près tout ce dont j'ai besoin. Comment feriez-vous la même chose en Pascal ?

[anapurna]

Salut !

Bon a priori ce sont les parenthèses qui te donnent l'ordre.

 (e4(e5(d4))(c5))(d4(d5))

 E4 D4 
 E5 C5 D5
 D4

En cherchant les rangs on s'aperçoit que c'est un peu comme une fonction récursive.

  e4 = rg1
  e5 = rg2
  d4 = rg3
  c5 = rg2 
  d4 = rg1
  d5 = rg2

En analysant la fonction on s'aperçoit aussi que l'on pourrait placer une condition "ou" à chaque ")(".

 (e4(e5(d4)) ou (c5)) ou (d4(d5))

Ce qui en terme d'arbre pourrait donner un truc qui ressemble à ceci :

Root
|_E4_E5_D4
|    |_C5  
|_D4_D5

Donc l'utilisation d'un arbre binaire est très fortement recommandée. Voir ici pour plus d'informations.

[Roland Chastain]

@anapurna

Merci pour ta réponse. Oui, il y a des idées à prendre dans la page que tu indiques, mais (sauf erreur de ma part) l'arbre binaire ne convient pas, puisqu'il peut y avoir plus de deux coups proposés. Mais peut-être pourrait-on remplacer les deux enfants (gauche et droite) par un tableau d'enfants ?

C'était l'idée que je proposais dans mon premier message, mais j'aurais bien aimé que quelqu'un me le confirme, voire m'indique un code prêt à l'emploi.

J'ai aussi regardé du côté de TVirtualStringTree, mais tous les exemples sont des applications graphiques avec des composants, ce qui ne facilite pas la compréhension des choses, pour moi en tout cas.

[M.Dlb]

Hello, oui il semblerait qu’un arbre convienne. Pour une arborescence complète, tu peux implémenter ton propre objet, ce n’est pas extrêmement complexe si tu prends en considération qu’un nœud a un unique parent, un pointeur vers ses frères (liste chainée simple ou circulaire) et un pointeur vers ses enfants (liste chaînée simple ou circulaire).
J’avais fait une implémentation similaire, il faudrait que je retrouve le code source...

[Roland Chastain]

@M.Dlb

Merci pour ta réponse. Si jamais tu retrouves le code en question, je serais preneur. Sinon je vais essayer de m'en sortir avec tes indications.

[M.Dlb]

Hello, voici le code de l'unité complète, donc évidemment certaines définitions ne sont pas intéressantes pour toi (surtout au début).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
unit FolderRepCommon;
 
interface
 
uses ComCtrls, Windows, SysUtils, FolderRepSync, Messages;
 
const
  ftFolder = 0001;
  ftFile = 0002;
  clGray1 = $00D8D8D8;
  clGray2 = $00A6A6A6;
  clDarkGray = $00969696;
  clGrayLine = $004C4C4C;
  clProgress = $0014AB45;
  FileDrawGridIndent = 19;
  WM_ICONRESPONSE = WM_USER + 1;
 
type
  TSwitchFilesDrawGrid = procedure(Enabled: Boolean);
 
  PFilePair = ^TFilePair;
  TFilePair = record
    FileType: Integer;
//    SourceRelativeFileName, DestinationRelativeFileName: String;
    RelativeFileName: String;
    FileName: String;
    SourceFileSize, DestinationFileSize: Int64;
    SourceFileModificationDate, DestinationFileModificationDate: TDateTime;
    Status: Integer;
  end;
 
  PTreeLeaf = ^TTreeLeaf;
  TTreeLeaf = record
    Parent: PTreeLeaf;
    Children: PTreeLeaf;
    Sibling: PTreeLeaf;
    FilePair: PFilePair;
  end;
 
  TTree = class(TObject)
  private
    Root: PTreeLeaf;
//    procedure AddLeafToTreeView(TreeView: TTreeView; Parent: TTreeNode; CurrentLeaf: PTreeLeaf);
    procedure ClearNode(Node: PTreeLeaf);
  public
    Count: Integer;
    InUpdate: Boolean;
    constructor Create;
    procedure Free;
    function Add(Parent: PTreeLeaf; FilePair: PFilePair): PTreeLeaf;
    function GetLeafFromRelativeFileName(RelativeFileName: String): PTreeLeaf;
    function GetChildByFileName(Parent: PTreeLeaf; FileName: String): PTreeLeaf;
    function GetNextChildByFileName(Parent: PTreeLeaf; FileName: String): PTreeLeaf;
    function InsertBefore(Sibling: PTreeLeaf; FilePair: PFilePair): PTreeLeaf;
//    procedure GenerateTreeView(TreeView: TTreeView);
    procedure Clear;
    function GetLeafLevel(Leaf: PTreeLeaf): Integer;
    function GetChildCount(Leaf: PTreeLeaf): Integer;
    function GetRoot: PTreeLeaf;
    function GetNext(Leaf: PTreeLeaf): PTreeLeaf;
  end;
 
  TFolderPair = class(TObject)
  public
    Description: String;
    Source: String;
    Destination: String;
    Status: Integer;
    Items: TTree;
    Lock: TSemaphore;
    constructor Create(Description, Source, Destination: String);
    procedure Free;
  end;
 
var
  GlobalEnding: Boolean;
 
implementation
 
constructor TFolderPair.Create(Description, Source, Destination: String);
begin
  inherited Create();
  Self.Description := Description;
  Self.Source := Source;
  Self.Destination := Destination;
  Items := TTree.Create;
  Lock := TSemaphore.Create(1, 1);
  Status := 0;
  Items.InUpdate := False;
end;
 
procedure TFolderPair.Free;
begin
  Lock.Ask;
  Items.Free;
  Lock.Release;
  Lock.Free;
  inherited Free;
end;
 
//******************************************************************************
//**  TTree  *******************************************************************
//******************************************************************************
 
constructor TTree.Create;
begin
  inherited Create;
  Count := 0;
end;
 
procedure TTree.Free;
begin
  Clear;
  inherited Free;
end;
 
function TTree.Add(Parent: PTreeLeaf; FilePair: PFilePair): PTreeLeaf;
var
  CurrentLeaf: PTreeLeaf;
begin
  if Parent = Nil then
  begin
    New(Root);
    Root^.Parent := Nil;
    Root^.Sibling := Nil;
    Root^.Children := Nil;
    Root^.FilePair := FilePair;
    Result := Root;
  end else
  begin
    if (Parent^.Children = Nil) then
    begin
      New(Parent^.Children);
      CurrentLeaf := Parent^.Children;
      CurrentLeaf^.Parent := Parent;
      CurrentLeaf^.Sibling := Nil;
      CurrentLeaf^.Children := Nil;
      CurrentLeaf^.FilePair := FilePair;
      Result := CurrentLeaf;
    end else
    begin
      CurrentLeaf := Parent^.Children;
      while (CurrentLeaf^.Sibling <> Nil) do
        CurrentLeaf := CurrentLeaf^.Sibling;
      New(CurrentLeaf^.Sibling);
      CurrentLeaf := CurrentLeaf^.Sibling;
      CurrentLeaf^.Parent := Parent;
      CurrentLeaf^.Sibling := Nil;
      CurrentLeaf^.Children := Nil;
      CurrentLeaf^.FilePair := FilePair;
      Result := CurrentLeaf;
    end;
  end;
  Count := Count + 1;
end;
 
function TTree.GetLeafFromRelativeFileName(RelativeFileName: String): PTreeLeaf;
var
  CurrentLeaf: PTreeLeaf;
begin
  CurrentLeaf := Root;
  while CurrentLeaf <> Nil do
  begin
    if (CurrentLeaf^.FilePair^.RelativeFileName = RelativeFileName) then Break;
    CurrentLeaf := GetNext(CurrentLeaf);
  end;
  Result := CurrentLeaf;
end;
 
function TTree.GetChildByFileName(Parent: PTreeLeaf; FileName: String): PTreeLeaf;
var
  CurrentLeaf: PTreeLeaf;
begin
  CurrentLeaf := Parent.Children;
  while CurrentLeaf <> Nil do
  begin
    if (CurrentLeaf^.FilePair^.FileName = FileName) then Break;
    CurrentLeaf := CurrentLeaf.Sibling;
  end;
  Result := CurrentLeaf;
end;
 
function TTree.GetNextChildByFileName(Parent: PTreeLeaf; FileName: String): PTreeLeaf;
var
  CurrentLeaf: PTreeLeaf;
begin
  CurrentLeaf := Parent.Children;
  while CurrentLeaf <> Nil do
  begin
    if (CurrentLeaf^.FilePair^.FileName > FileName) then Break;
    CurrentLeaf := CurrentLeaf.Sibling;
  end;
  Result := CurrentLeaf;
end;
 
 
function TTree.InsertBefore(Sibling: PTreeLeaf; FilePair: PFilePair): PTreeLeaf;
var
  InsertedLeaf: PTreeLeaf;
  Parent: PTreeLeaf;
begin
  if Parent = Nil then
  begin
    Result := Nil;
    Exit;
  end else
  begin
    if (Parent^.Children = Sibling) then
    begin
      New(InsertedLeaf);
      InsertedLeaf^.Parent := Parent;
      InsertedLeaf^.Sibling := Parent^.Children;
      InsertedLeaf^.Children := Nil;
      InsertedLeaf^.FilePair := FilePair;
      Parent^.Children := InsertedLeaf;
      Result := InsertedLeaf;
    end else
    begin
      New(InsertedLeaf);
      InsertedLeaf^.Parent := Parent;
      InsertedLeaf^.Sibling := Sibling^.Sibling;
      InsertedLeaf^.Children := Nil;
      InsertedLeaf^.FilePair := FilePair;
      Sibling^.Sibling := InsertedLeaf;
      Result := InsertedLeaf;
    end;
  end;
end;
 
procedure TTree.ClearNode(Node: PTreeLeaf);
begin
  if Node = Nil then Exit;
  if Node^.Sibling <> Nil then ClearNode(Node^.Sibling);
  if Node^.Children <> Nil then ClearNode(Node^.Children);
  if ((Node^.Sibling = Nil) and (Node^.Children = Nil)) then
    Dispose(Node);
end;
 
procedure TTree.Clear;
begin
  ClearNode(Root);
  Root := Nil;
  Count := 0;
end;
 
{procedure TTree.AddLeafToTreeView(TreeView: TTreeView; Parent: TTreeNode; CurrentLeaf: PTreeLeaf);
var
  CurrentNode: TTreeNode;
begin
  if Parent = Nil then
    CurrentNode := TreeView.Items.Add(Parent, CurrentLeaf^.FilePair^.FileName)
  else
    CurrentNode := TreeView.Items.AddChild(Parent, CurrentLeaf^.FilePair^.FileName);
  CurrentNode.Data := CurrentLeaf^.FilePair;
  if CurrentLeaf^.Children <> Nil then
  begin
    CurrentNode.ImageIndex := 0;
    CurrentNode.SelectedIndex := 0;
    AddLeafToTreeView(TreeView, CurrentNode, CurrentLeaf^.Children);
  end else
  begin
    CurrentNode.ImageIndex := 2;
    CurrentNode.SelectedIndex := 2;
  end;
  if CurrentLeaf^.Sibling <> Nil then
    AddLeafToTreeView(TreeView, Parent, CurrentLeaf^.Sibling);
end;
 
procedure TTree.GenerateTreeView(TreeView: TTreeView);
begin
  TreeView.Items.Clear;
  TreeView.Items.BeginUpdate;
  AddLeafToTreeView(TreeView, Nil, Root);
  TreeView.Items.EndUpdate;
  TreeView.Repaint;
end; }
 
function TTree.GetLeafLevel(Leaf: PTreeLeaf): Integer;
var
  CurrentLeaf: PTreeLeaf;
  I: Integer;
begin
  if Leaf = Nil then
  begin
    Result := -1;
    Exit;
  end;
  I := 0;
  CurrentLeaf := Leaf;
  while (CurrentLeaf^.Parent <> Nil) do
  begin
    CurrentLeaf := CurrentLeaf^.Parent;
    I := I + 1;
  end;
  Result := I;
end;
 
function TTree.GetChildCount(Leaf: PTreeLeaf): Integer;
var
  CurrentLeaf: PTreeLeaf;
  Count: Integer;
begin
  CurrentLeaf := Leaf^.Children;
  Count := 0;
  while CurrentLeaf <> Nil do
  begin
    CurrentLeaf := CurrentLeaf^.Sibling;
    Count := Count + 1;
  end;
  Result := Count;
end;
 
function TTree.GetRoot: PTreeLeaf;
begin
  Result := Root;
end;
 
function TTree.GetNext(Leaf: PTreeLeaf): PTreeLeaf;
var
  NextLeaf: PTreeLeaf;
begin
  if Leaf <> Nil then
  begin
    if Leaf^.Children <> Nil then
    begin
      Result := Leaf^.Children;
      Exit;
    end;
    if Leaf^.Sibling <> Nil then
    begin
      Result := Leaf^.Sibling;
      Exit;
    end;
    if ((Leaf^.Children = Nil) and (Leaf^.Sibling = Nil)) then
    begin
      NextLeaf := Leaf^.Parent;
      while ((NextLeaf <> Nil) and (NextLeaf^.Sibling = Nil)) do
        NextLeaf := NextLeaf^.Parent;
      if (NextLeaf = Nil) then
        Result := Nil
      else
        Result := NextLeaf^.Sibling;
    end;
  end else
    Result := Nil;
end;
 
initialization
  GlobalEnding := False;
end.

Ce qui sera intéressant de reprendre c'est l'objet TTree, dont chaque noeud pointe sur un record TFilePair, qu'il faudra donc que tu remplaces soit par ton propre objet (si ça en vaut la peine), soit par une string. Désolé, je n'ai pas fait de ménage donc ça ne compilera pas en l'état, il faudra élaguer un peu
Le code est pour Delphi mais devrait être réutilisable sans difficultés.

[Roland Chastain]

Bon, je crois qu'elle va faire mon affaire, cette unité. Merci !

Donc j'ai un début d'exemple qui fonctionne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
uses
  SysUtils, Tree;
 
var
  LTree: TTree;
  PLeaf: PTreeLeaf;
 
begin
  LTree := TTree.Create;
 
  PLeaf := LTree.Add(nil, 'e2e4');
  PLeaf := LTree.Add(PLeaf, 'e7e5');
  PLeaf := LTree.Add(PLeaf, 'd2d4');
 
  LTree.Print(LTree.GetRoot);
 
  LTree.Clear;
  LTree.Free;
end.

(e2e4(e7e5(d2d4)))

Je n'ai pas trouvé comment ajouter les frères. J'ai essayé d'utiliser la procédure InsertBefore mais sans succès.

J'ai toujours un doute aussi sur la façon de lier les coups proposés pour le premier coup (dans mon exemple, e2e2 et d2d4). Ils n'ont pas de parents. Donc il y aura plusieurs arbres en fait ? Un tableau d'arbres ?

P.-S. Ah ben non, je suis bête : d2d4 sera le "frère" de e2e4. Je ne sais pas pourquoi ça a du mal à rentrer cette histoire de frère.

[Roland Chastain]

Il y a du progrès. Cette unité est ce qu'il me fallait.

Concernant les premiers coups, j'ai hésité entre : ajouter une procédure qui permettrait de créer des frères de la racine ; déclarer un tableau d'arbres ; créer une racine vide. J'espère que vous comprenez ce que je raconte.

J'ai opté provisoirement pour la dernière solution.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
uses
  SysUtils, Tree;
 
var
  LTree: TTree;
  n, o, p: PTreeNode;
 
begin
  LTree := TTree.Create;
 
  n := LTree.Add(nil, '');
 
  o := LTree.Add(n, 'e2e4');
  n := LTree.Add(n, 'd2d4');
 
  p := LTree.Add(o, 'e7e5');
  o := LTree.Add(o, 'c7c5');
 
  p := LTree.Add(p, 'd2d4');
 
  n := LTree.Add(n, 'd7d5');
 
  Assert(LTree.Count = 7);
  LTree.WriteAll(LTree.GetRoot^.Child);
 
  LTree.Clear;
  LTree.Free;
end.

(e2e4(e7e5(d2d4))(c7c5))(d2d4(d7d5))

[M.Dlb]

Hello !

La racine vide est acceptable, conceptuellement, car ça simplifie la vie. L’idéal est certainement une liste (TList) d’arbres mais ça nécessite une gestion supplémentaire !

Bon courage

[Roland Chastain]

La racine vide est acceptable, conceptuellement, car ça simplifie la vie. L’idéal est certainement une liste (TList) d’arbres mais ça nécessite une gestion supplémentaire !

Merci pour la confirmation. Donc pour le moment je vais continuer comme ça.

J'ai déplacé la création de la racine dans le contructeur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{$DEFINE CREATE_ROOT}
 
constructor TTree.Create;
begin
  inherited Create;
{$IFDEF CREATE_ROOT}
{$WARNING Root created in constructor}
  Root := Add(nil, '');
  Count := 1;
{$ELSE}
  Root := nil;
  Count := 0;
{$ENDIF}
end;

Et j'ai fait une procédure qui permet d'ajouter une ligne de coups.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var
  LTree: TTree;
  n: PTreeNode;
  LLine: TStringList;
 
begin
  LTree := TTree.Create;
  Assert(LTree.Count = 1);
 
  LLine := TStringList.Create;
  LLine.DelimitedText := 'e2e4 e7e5 d2d4';
  n := LTree.AddLine(LLine);
  LLine.DelimitedText := 'e2e4 c7c5';
  n := LTree.AddLine(LLine);
  LLine.DelimitedText := 'd2d4 d7d5';
  n := LTree.AddLine(LLine);
  LLine.Free;
 
  WriteLn(LTree.AsText1);
  WriteLn(LTree.AsText2);
 
  LTree.Clear;
  LTree.Free;
end.

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
(e2e4(e7e5(d2d4))(c7c5))(d2d4(d7d5))
e2e4
  e7e5
    d2d4
  c7c5
d2d4
  d7d5

Je crois qu'il ne me reste qu'à savoir lire un livre au format "parenthèses", et j'aurais à peu près tout ce dont j'ai besoin.

[Roland Chastain]

Voilà, l'unité est finie et mise au propre.

On peut maintenant ajouter les lignes de coups comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  LTree.AddLine('e2e4 e7e5 d2d4');
  LTree.AddLine('e2e4 c7c5');
  LTree.AddLine('d2d4 d7d5');

On peut obtenir une chaîne de caractères contenant l'arbre entier, dans deux formats différents :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

(e2e4(e7e5(d2d4))(c7c5))(d2d4(d7d5))

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
e2e4
  e7e5
    d2d4
  c7c5
d2d4
  d7d5

Enfin on peut charger l'arbre à partir d'un fichier, et le sauvegarder. Le fichier doit contenir des lignes complètes comme ceci :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
e2e4 e7e5 d2d4
e2e4 c7c5
d2d4 d7d5

Le seul truc que je n'ai pas réussi à faire, c'est charger l'arbre à partir d'une chaîne du type "(e2e4(e7e5(d2d4))(c7c5))(d2d4(d7d5))". Il faudrait transformer ça en lignes comme ci-dessus. Je suis preneur des éventuelles contributions.

[anapurna]

Salut

Pour te mettre sur la voie...

Rien de bien compliqué, je pense qu'en utilisant un tableau des éléments antérieurs il y a moyen de faire ce que tu veux :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Procedure TForm1.AddEnfant(aParent : Integer;aStToken : String);
begin
  Memo1.Lines.Add(Format('%d - %s',[aParent,aStToken]));
end;
 
procedure TForm1.Process(AStrFormul : String);
var
  Lg,IParent,Ipos : Integer;
  StToken  : String;
  ch : Char;
  Fin : Boolean;
begin
  IParent := 0;
  Ipos := 0;
  StToken := '';
  Lg := Length(AStrFormul);
  Fin := Ipos = Lg;
  While not(fin) do
  begin
    Ch := AStrFormul[Ipos];
    if Ch = ')' Then
    begin
      AddEnfant(iParent,StToken);
      iParent := iParent-1;
      StToken:='';
    end;
    if Ch = '(' Then
    begin
      AddEnfant(iParent,StToken);
      iParent := iParent+1;
      StToken:=''
    end;
    if  (Ch <> ')') and  (Ch <> '(')  Then
      StToken := StToken + Ch;
    Inc(Ipos);
    fin := Ipos >= Lg;
  end;
end;

[Roland Chastain]

@anapurna

Merci. Ta solution semble fonctionner. J'étais occupé à autre chose. Je reviens ici dès que j'ai mis le code au propre.

[Roland Chastain]

Voilà, après quelques dernières mises au point, tout semble fonctionner.

Le programme est capable de lire et d'écrire un livre dans les deux formats ("lignes" et "parenthèses"). J'ai fait des essais avec 1° un petit livre de trois lignes que j'avais fabriqué pour l'occasion (minibook.txt) 2° le livre du programme TSCP (book.txt) 3° le livre livré avec le programme BookBuilder (book) et 4° un livre que j'ai fabriqué avec le programme BookBuilder, à partir d'un fichier PGN (fischer60.txt).

Merci à tous !

Ah oui, j'allais oublier. Voici ma version de la solution proposée par anapurna.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
uses
  SysUtils, Classes;
 
const
  CMaxMoves = 3;
 
var
  LMoves: array[1..CMaxMoves] of string;
  LIndex: integer;
  LDone: boolean;
  LList: TStringList;
 
procedure Store(const AIndex: integer; const AMove: string);
var
  i: integer;
begin
  (*
  WriteLn(Format('AIndex=%d AMove=%s', [AIndex, AMove]));
  *)
  if AIndex > LIndex then
  begin
    LMoves[AIndex] := AMove;
    LDone := FALSE;
  end;
  if (AIndex < LIndex) and not LDone then
  begin
    for i := 1 to Succ(AIndex) do
       LList.Append(LMoves[i]);
 
    WriteLn(LList.DelimitedText);
 
    LList.Clear;
    LDone := TRUE;
  end;
  LIndex := AIndex;
end;
 
procedure Process(const AStr: string);
var
  LLen, LLevel, LPos: integer;
  LData: string;
  c: char;
begin
  LLevel := 0;
  LPos := 1;
  LData := '';
  LLen := Length(AStr);
  while LPos <= LLen do
  begin
    c := AStr[LPos];
    if c = '(' then
    begin
      Store(LLevel, LData);
      Inc(LLevel);
      LData := ''
    end else
    if c = ')' then
    begin
      Store(LLevel, LData);
      Dec(LLevel);
      LData := '';
    end else
      LData := LData + c;
    Inc(LPos);
  end;
  Store(0, 'Au revoir !');
end;
 
const
  CStr = '(e2e4(e7e5(d2d4))(c7c5))(d2d4(d7d5))';
 
begin
  LIndex := 0;
  LDone := FALSE;
  LList := TStringList.Create;
  LList.Delimiter := ' ';
  Process(CStr);
  LList.Free;
end.

[Roland Chastain]

J'ai inclus l'unité arbre dans le programme Alouette, avec des livres fabriqués au moyen de l'outil pgn-extract, à partir de centaines de parties de grands joueurs. Pendant les trois premiers coups vous avez l'impression de jouer contre Philidor. Après ça se gâte.

En tout cas l'unité fonctionne impeccablement. Par rapport à la dernière version que j'ai postée ici, j'ai ajouté une fonction permettant de choisir un enfant au hasard lorsqu'il y en a plusieurs.

Ci-joint la version légère des livres.

[anapurna]

Salut

j'ai un peu lu le code, il y a je pense des simplifications à faire .

Par exemple dans la méthode process, si tu l'intègres directement à l'arbre tu pourrais faire un truc du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
procedure Process(const AStr: string);
var
  LLen, LLevel, LPos: integer;
  LData: string;
  c: char;
begin
  LLevel := 0;
  LPos := 1;
  LData := '';
  LLen := Length(AStr);
  aParent := Root;
  while LPos <= LLen do
  begin
    c := AStr[LPos];
    if c = '(' then
    begin
	Acurent := Add(aParent,LData);
	aParent := GetParent(Acurent);
        LData := ''
    end else
    if c = ')' then
    begin
	Acurent := Add(aParent,LData));
	aParent := GetParent(aParent);
        LData := '';
    end 
    else
      LData := LData + c;
      Inc(LPos);
  end;
end;

Je l'ai fait from scratch mais à mon avis je ne suis pas très loin du résultat, de même que l'unité arbre je l'aurais réécrite un peu plus finement, exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
function TTree.Add(AParent: PTreeNode; AData: string): PTreeNode;
var
  LNode: PTreeNode;
begin
  if AParent = nil then
  begin
    New(Root);
    Root^.Parent := nil;
    Root^.Sibling := nil;
    Root^.Child := nil;
    Root^.Data := AData;
    result := Root;
  end else
  begin
    if (AParent^.Child = nil) then
      result := AddEnfant(AParent,AData)
    else
      result := AddFrere(AParent,AData);
  end;
  Count := Count + 1;
end;
 
function TTree.AddEnfant(AParent: PTreeNode; AData: string): PTreeNode;
var
  LNode: PTreeNode;
Begin
  New(AParent^.Child);
  LNode := GetEnfant(AParent);
  LNode^.Parent := AParent;
  LNode^.Sibling := nil;
  LNode^.Child := nil;
  LNode^.Data := AData;
  result := LNode;
end;  
 
function TTree.GetLastFrere(ANode: PTreeNode): PTreeNode;
begin
  Result := ANode;
  while (Result.Sibling <> nil) do
    Result := GetFrere(Result);
end;
 
function TTree.AddFrere(AParent: PTreeNode; AData: string): PTreeNode;
var
  LNode: PTreeNode;
begin
  LNode := AParent^.Child;
  LNode := GetLastFrere(LNode);
  New(LNode^.Sibling);
  LNode := LNode^.Sibling;
  LNode^.Parent := AParent;
  LNode^.Sibling := nil;
  LNode^.Child := nil;
  LNode^.Data := AData;
  result := LNode;
end;

Les quelques fonctions réécrites mais parlantes te permettent ensuite de clarifier d'autres fonctions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
////////////////////////////////////////////// 
function TTree.GetRoot: PTreeNode;
begin
  result := Root;
end;
//////////////////////////////////////////////
function TTree.GetParent(ANode: PTreeNode): PTreeNode;
begin
  Result := ANode^.Parent;
end;
 //////////////////////////////////////////////
function TTree.GetEnfant(ANode: PTreeNode): PTreeNode;
begin
  Result := ANode^.Child;
end;
//////////////////////////////////////////////
function TTree.GetFrere(ANode: PTreeNode): PTreeNode;
begin
  Result := ANode^.Sibling;
end;
 //////////////////////////////////////////////
function TTree.GetNext(ANode: PTreeNode): PTreeNode;
var
  NextLeaf: PTreeNode;
begin
  result := nil;
  if ANode <> nil then
  begin
    if ANode^.Child <> nil then
    begin
      result := GetEnfant(ANode);
      Exit;
    end;
 
    if ANode^.Sibling <> nil then
    begin
      result := GetFrere(ANode);
      Exit;
    end;
 
	if ((ANode^.Child = nil) and (ANode^.Sibling = nil)) then
    begin
      NextLeaf := GetParent(ANode);
      while ((NextLeaf <> nil) and (NextLeaf^.Sibling = nil)) do
        NextLeaf := GetParent(NextLeaf);
 
      if (NextLeaf = nil) then
        result := nil
      else
        result := GetFrere(NextLeaf);
    end;
  end; 
end;

Ce qui au final pourra te permettre de passer cette version "pointer" en version "objet" sans trop de difficulté.

Mes 2 cents

[Roland Chastain]

@anapurna

Merci pour ces indications. Pour le moment je suis déjà content d'avoir quelque chose qui fonctionne mais prochainement si j'en ai le courage je ferai les modifications que tu proposes.

À bientôt !

[Roland Chastain]

Je me suis décidé à abandonner le "truc" de la racine vide créée automatiquement (qui permettait de faire un seul arbre avec toutes les ouvertures), et à utiliser à la place une liste d'arbres comme Mathieu l'avait suggéré.

J'ai inclus dans le fichier ci-joint une unité contenant différentes versions d'une fonction qui permet de savoir si deux fichiers sont identiques. L'unité est utilisée dans la démo, pour vérifier que le programme fonctionne correctement (c'est-à-dire que le fichier écrit est exactement identique au fichier lu).