/* The Royal Tree benchmark problem for GP */
/* See paper: William F. Punch, How Effective are Multiple Populations in Genetic Programming */
/* for max. depth 7 (level: g) this is hard to solve. Full enumeration needs a lot of memory. */

PROBLEM RoyalTree
CODE <<
  const int MaxDepth = 7;
  const double FullBonus = 2;
  const double PartialBonus = 1;
  const double Penalty = 1.0 / 3.0;
  const double CompleteBonus = 2.0;
>>

NONTERMINALS
  S<<int depth, out double score, out char symb, out bool perfect>>. 
  A<<int depth, out double score, out char symb, out bool perfect>>. 
  B<<int depth, out double score, out char symb, out bool perfect>>. 
  C<<int depth, out double score, out char symb, out bool perfect>>. 
  D<<int depth, out double score, out char symb, out bool perfect>>. 
  E<<int depth, out double score, out char symb, out bool perfect>>.
  F<<int depth, out double score, out char symb, out bool perfect>>.
  G<<int depth, out double score, out char symb, out bool perfect>>.
  
TERMINALS
  X. Y. Z. 

RULES
  S<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << perfect = false; if (depth <= 0) { score = 0.0; symb = ' '; return; } >>
      A<<depth-1, out score, out symb, out perfect>>  
    | B<<depth-1, out score, out symb, out perfect>>
    | C<<depth-1, out score, out symb, out perfect>>
    | D<<depth-1, out score, out symb, out perfect>>
    | E<<depth-1, out score, out symb, out perfect>>
    | F<<depth-1, out score, out symb, out perfect>>
    | G<<depth-1, out score, out symb, out perfect>>                       /* "... it is extremely difficult to climb to a level-f tree and we have never succeeded in climbing to level-g." */
    | X                                                                    SEM << symb = 'X'; score = 1; >>
    | Y                                                                    SEM << symb = 'Y'; score = 0; >>
    | Z                                                                    SEM << symb = 'Z'; score = 0; >>
  .
  
  A<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s; 
                                                                             bool p;
                                                                             double w;
                                                                             char c; 
                                                                             symb = 'A'; perfect = false; 
                                                                           >> 
    S<<depth, out s, out c, out p>>                                        SEM << w = Penalty; if(c == 'X') { w = FullBonus; } >>
                                                                           SEM << score = w * s; >>
                                                                           SEM << if (c=='X') { perfect = true; score = CompleteBonus * score; } >>
  .
  
  B<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s0, s1; 
                                                                             bool p0, p1;
                                                                             double w0, w1;
                                                                             char c0 = ' '; char c1 = ' '; 
                                                                             symb = 'B'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'A') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'A') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1; >>
                                                                           SEM << if (c0=='A' && c1=='A' && p0 && p1) { perfect = true; score = CompleteBonus * score; } >>
  .
  
  C<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                            double s0, s1, s2; 
                                                                            bool p0, p1, p2;
                                                                            double w0, w1, w2;
                                                                            char c0 = ' '; char c1 = ' '; char c2 = ' ';
                                                                            symb = 'C'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'B') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'B') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'B') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2; >>
                                                                           SEM << if (c0=='B' && c1=='B' && c2=='B' && p0 && p1 && p2) { perfect = true;  score = CompleteBonus * score; } >>
  .
  
  D<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s0, s1, s2, s3; 
                                                                             bool p0, p1, p2, p3;
                                                                             double w0, w1, w2, w3;
                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' ' ; 
                                                                             symb = 'D'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'C') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'C') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'C') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'C') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3; >>
                                                                           SEM << if (c0=='C' && c1=='C' && c2=='C' && c3=='C' && p0 && p1 && p2 && p3) { perfect = true;  score = CompleteBonus * score; } >>
  .

  E<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s0, s1, s2, s3, s4; 
                                                                             bool p0, p1, p2, p3, p4;
                                                                             double w0, w1, w2, w3, w4;
                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' '; 
                                                                             symb = 'E'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'D') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'D') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'D') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'D') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'D') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4; >>
                                                                           SEM << if (c0=='D' && c1=='D' && c2=='D' && c3=='D' && c4=='D' && p0 && p1 && p2 && p3 && p4) { perfect = true;  score = CompleteBonus * score; } >>
  .
  
  F<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s0, s1, s2, s3, s4, s5; 
                                                                             bool p0, p1, p2, p3, p4, p5;
                                                                             double w0, w1, w2, w3, w4, w5;
                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' '; char c5 = ' ';
                                                                             symb = 'F'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'E') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'E') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'E') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'E') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'E') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
    S<<depth, out s5, out c5, out p5>>                                     SEM << w5 = Penalty; if(c5 == 'E') { w5 = PartialBonus; if(p5) { w5 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4 + w5 * s5; >>
                                                                           SEM << if (c0=='E' && c1=='E' && c2=='E' && c3=='E' && c4=='E' && c5=='E' &&
                                                                                      p0 && p1 && p2 && p3 && p4 && p5) { perfect = true;  score = CompleteBonus * score; } >>
  .
  
  G<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0; 
                                                                             double s0, s1, s2, s3, s4, s5, s6; 
                                                                             bool p0, p1, p2, p3, p4, p5, p6;
                                                                             double w0, w1, w2, w3, w4, w5, w6;
                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' '; char c5 = ' '; char c6 = ' ';
                                                                             symb = 'F'; perfect = false; 
                                                                           >> 
    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'F') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'F') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'F') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'F') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'F') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
    S<<depth, out s5, out c5, out p5>>                                     SEM << w5 = Penalty; if(c5 == 'F') { w5 = PartialBonus; if(p5) { w5 = FullBonus; }} >>
    S<<depth, out s6, out c6, out p6>>                                     SEM << w6 = Penalty; if(c6 == 'F') { w6 = PartialBonus; if(p6) { w6 = FullBonus; }} >>
                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4 + w5 * s5 + w6 * s6; >>
                                                                           SEM << if (c0=='F' && c1=='F' && c2=='F' && c3=='F' && c4=='F' && c5=='F' && c6 == 'F' &&
                                                                                      p0 && p1 && p2 && p3 && p4 && p5 && p6) { perfect = true;  score = CompleteBonus * score; } >>
  .
  
MAXIMIZE
  << 
    double score;
    char symb;
    bool perfect;
    S(MaxDepth, out score, out symb, out perfect); 
    return score;
  >>
END RoyalTree.