Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs @ 11981

Last change on this file since 11981 was 11981, checked in by gkronber, 9 years ago

#2283: cleanup and included HeuristicLab.dlls to create a self-contained branch
File size: 10.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Runtime.InteropServices;
6using System.Runtime.Remoting.Messaging;
7using System.Text;
8using System.Text.RegularExpressions;
9using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
10
11namespace HeuristicLab.Problems.GrammaticalOptimization {
12  public class SantaFeAntProblem : ISymbolicExpressionTreeProblem {
13    private const string grammarString = @"
14G(A):
15A -> l | r | m | ?(A)(A) | lA | rA | mA
16";
17    // for tree-based GP in HL we need a different grammar for the same language
18    // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
19    private const string hlGrammarString = @"
20    G(A):
21    A -> l | r | m | P | I
22    P -> AA | AAA
23    I -> AA
24    ";
25
26
27    // original koza grammar
28    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
29    //
30    // here we use a modified grammar which has only one syntax tree for each sentence
31
32
33    private readonly IGrammar grammar;
34
35    public SantaFeAntProblem() {
36      this.grammar = new Grammar(grammarString);
37      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
38    }
39
40    public double BestKnownQuality(int maxLen) {
41      // for now only an upper bound is returned, ideally all food pellets are discovered
42      return 89;
43    }
44
45    public IGrammar Grammar {
46      get { return grammar; }
47    }
48
49    public double Evaluate(string sentence) {
50      var ant = new Ant();
51      int p = 0;
52      Run(ant, sentence, ref p);
53      return ant.FoodEaten;
54    }
55
56    private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false) {
57      while (!ant.Done()) {
58        if (p >= sentence.Length) {
59          if (stopAfterFirst) return;
60          p = 0; // restart
61        }
62        switch (sentence[p]) {
63          case 'r': {
64              ant.TurnRight();
65              p++;
66              break;
67            }
68          case 'l': {
69              ant.TurnLeft();
70              p++;
71              break;
72            }
73          case 'm': {
74              ant.Move();
75              p++;
76              break;
77            }
78          case '?': {
79              p++; // skip p
80              if (ant.IsFoodAhead()) {
81                if (sentence[p] != '(') throw new ArgumentException();
82                p++;
83                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
84                if (ant.Done()) return;
85                if (sentence[p] != '(') throw new ArgumentException();
86                p++;
87                Skip(sentence, ref p);
88              } else {
89                if (sentence[p] != '(') throw new ArgumentException();
90                p++;
91                Skip(sentence, ref p);
92                if (sentence[p] != '(') throw new ArgumentException();
93                p++;
94                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
95              }
96              break;
97            }
98          case '.': {
99              // nop
100              p++;
101              ant.Nop();
102              break;
103            }
104          case ')': {
105              p++; // skip
106              return;     // caller must continue processing
107            }
108          default: {
109              throw new ArgumentException();
110            }
111        }
112      }
113    }
114
115    private static void Skip(string sentence, ref int p) {
116      int openCount = 1;
117      while (openCount > 0) {
118        if (sentence[p] == '(') openCount++;
119        else if (sentence[p] == ')') openCount--;
120        p++;
121      }
122    }
123
124    public string CanonicalRepresentation(string phrase) {
125      //phrase = phrase.Replace("A", ".");
126      var sb = new StringBuilder(phrase);
127      string canonicalPhrase = phrase;
128      string oldPhrase;
129      do {
130        oldPhrase = canonicalPhrase;
131        sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
132        //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
133        canonicalPhrase = sb.ToString();
134      } while (canonicalPhrase != oldPhrase);
135      return canonicalPhrase;
136    }
137
138    public IEnumerable<Feature> GetFeatures(string phrase) {
139      phrase = CanonicalRepresentation(phrase);
140      var isTerminal = grammar.IsTerminal(phrase);
141
142      yield return new Feature(isTerminal + ToString(), 1.0);
143     
144      yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
145      if (!isTerminal) {
146        for (int i = 4; i < phrase.Length; i++) {
147          if (!grammar.IsTerminal(phrase[i])) {
148            yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
149            break;
150          }
151        }
152      }
153   
154      yield return new Feature(phrase, 1.0);
155    }
156
157    public IGrammar TreeBasedGPGrammar { get; private set; }
158    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
159      var sb = new StringBuilder();
160      ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
161      return sb.ToString();
162    }
163    private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
164      if (node.SubtreeCount == 0) {
165        // terminal
166        sb.Append(node.Symbol.Name);
167      } else if (node.Symbol.Name == "I") {
168        Debug.Assert(node.SubtreeCount == 2);
169        sb.Append("?(");
170        ConvertTreeToSentence(node.GetSubtree(0), sb);
171        sb.Append(")(");
172        ConvertTreeToSentence(node.GetSubtree(1), sb);
173        sb.Append(")");
174      } else {
175        foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
176      }
177    }
178  }
179
180  public class Ant {
181    private int maxSteps = 600;
182    public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
183    public enum HeadingEnum { North, East, South, West };
184    public int FoodEaten { get; private set; }
185    private readonly char[][] world = new char[32][];
186    private int posX;
187    private int posY;
188    private int steps;
189    private HeadingEnum heading;
190    public int PosX { get { return posX; } }
191    public int PosY { get { return posY; } }
192    public HeadingEnum Heading { get { return heading; } }
193    private bool recordTrail = false;
194    private StringBuilder trailBuilder;
195
196    public string Trail {
197      get {
198        if (!recordTrail) throw new NotSupportedException();
199        else return trailBuilder.ToString() + heading; // add final heading as state
200      }
201    }
202
203    public Ant(bool recordTrail = false) {
204      world[00] = " ###                            ".ToCharArray();
205      world[01] = "   #                            ".ToCharArray();
206      world[02] = "   #                    .###..  ".ToCharArray();
207      world[03] = "   #                    #    #  ".ToCharArray();
208      world[04] = "   #                    #    #  ".ToCharArray();
209      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
210      world[06] = "            #       .        #  ".ToCharArray();
211      world[07] = "            #       #        .  ".ToCharArray();
212      world[08] = "            #       #        .  ".ToCharArray();
213      world[09] = "            #       #        #  ".ToCharArray();
214      world[10] = "            .       #        .  ".ToCharArray();
215      world[11] = "            #       .        .  ".ToCharArray();
216      world[12] = "            #       .        #  ".ToCharArray();
217      world[13] = "            #       #        .  ".ToCharArray();
218      world[14] = "            #       #  ...###.  ".ToCharArray();
219      world[15] = "            .   .#...  #        ".ToCharArray();
220      world[16] = "            .   .      .        ".ToCharArray();
221      world[17] = "            #   .      .        ".ToCharArray();
222      world[18] = "            #   #      .#...    ".ToCharArray();
223      world[19] = "            #   #          #    ".ToCharArray();
224      world[20] = "            #   #          .    ".ToCharArray();
225      world[21] = "            #   #          .    ".ToCharArray();
226      world[22] = "            #   .      ...#.    ".ToCharArray();
227      world[23] = "            #   .      #        ".ToCharArray();
228      world[24] = " ..##..#####.   #               ".ToCharArray();
229      world[25] = " #              #               ".ToCharArray();
230      world[26] = " #              #               ".ToCharArray();
231      world[27] = " #     .#######..               ".ToCharArray();
232      world[28] = " #     #                        ".ToCharArray();
233      world[29] = " .     #                        ".ToCharArray();
234      world[30] = " .####..                        ".ToCharArray();
235      world[31] = "                                ".ToCharArray();
236
237      posX = 0;
238      posY = 0;
239      heading = HeadingEnum.East;
240      FoodEaten = 0;
241      steps = 0;
242
243      this.recordTrail = recordTrail;
244      if (this.recordTrail) trailBuilder = new StringBuilder();
245    }
246
247    public bool Done() {
248      return steps > maxSteps;
249    }
250
251    public void TurnRight() {
252      if (steps <= maxSteps) {
253        steps++;
254        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
255        else heading++;
256      }
257    }
258
259    public void TurnLeft() {
260      if (steps <= maxSteps) {
261        steps++;
262        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
263        else heading--;
264      }
265    }
266
267    public void Move() {
268      if (steps <= maxSteps) {
269        steps++;
270        MoveInternal(ref posX, ref posY);
271        if (world[posY][posX] == '#') {
272          FoodEaten++;
273          world[posY][posX] = '.';
274        }
275        if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
276      }
277    }
278
279    public void Nop() {
280      // wait one time step
281      if (steps <= maxSteps) {
282        steps++;
283      }
284    }
285
286    private void MoveInternal(ref int posX, ref int posY) {
287      switch (heading) {
288        case HeadingEnum.North:
289          posY = (posY + 31) % 32;
290          break;
291        case HeadingEnum.East:
292          posX = (posX + 1) % 32;
293          break;
294        case HeadingEnum.South:
295          posY = (posY + 1) % 32;
296          break;
297        case HeadingEnum.West:
298          posX = (posX + 31) % 32;
299          break;
300      }
301    }
302
303    public bool IsFoodAhead() {
304      int nextPosX = posX;
305      int nextPosY = posY;
306      MoveInternal(ref nextPosX, ref nextPosY);
307
308      if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
309
310      return world[nextPosY][nextPosX] == '#';
311    }
312  }
313}
Note: See TracBrowser for help on using the repository browser.