Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Rédacteur/Modérateur

    Représentation de l'arbre d'un livre d'ouvertures aux échecs
    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é.

  2. #2
    Rédacteur/Modérateur

    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 ?

  3. #3
    Expert confirmé
    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.
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  4. #4
    Rédacteur/Modérateur

    @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.

  5. #5
    Rédacteur/Modérateur

    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...
    M.Dlb - Modérateur z/OS - Rédacteur et Modérateur Pascal

  6. #6
    Rédacteur/Modérateur

    @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.

  7. #7
    Rédacteur/Modérateur

    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.
    M.Dlb - Modérateur z/OS - Rédacteur et Modérateur Pascal

  8. #8
    Rédacteur/Modérateur

    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.

  9. #9
    Rédacteur/Modérateur

    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))

  10. #10
    Rédacteur/Modérateur

    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
    M.Dlb - Modérateur z/OS - Rédacteur et Modérateur Pascal

  11. #11
    Rédacteur/Modérateur

    Citation Envoyé par M.Dlb Voir le message
    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.

  12. #12
    Rédacteur/Modérateur

    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.

  13. #13
    Expert confirmé
    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;
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  14. #14
    Rédacteur/Modérateur

    @anapurna

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

  15. #15
    Rédacteur/Modérateur

    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.

  16. #16
    Rédacteur/Modérateur

    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.

  17. #17
    Expert confirmé
    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  18. #18
    Rédacteur/Modérateur

    @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 !

  19. #19
    Rédacteur/Modérateur

    Liste d'arbres
    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).

###raw>template_hook.ano_emploi###