Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2283 commit for 'realistic' (same settings for ant and symbreg) experiment
File size: 12.2 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 sb.ToString();
136    }
137
138    public IEnumerable<Feature> GetFeatures(string phrase) {
139      phrase = CanonicalRepresentation(phrase);
140      var isTerminal = grammar.IsTerminal(phrase);
141
142
143      //yield return new Feature("const", 0.0);
144      //if (phrase.Length > 0) {
145      //  var ant = new Ant(recordTrail: true);
146      //  int pos = 0;
147      //  Run(ant, phrase, ref pos, true);
148      //  //yield return new Feature("food", ant.FoodEaten);
149      //  yield return new Feature(ant.Trail, 1.0);
150      //}
151      //yield return new Feature(isTerminal + "const", 0.0);
152      //yield return new Feature(isTerminal.ToString() + phrase.Length, 1.0);
153      //int ntIdx;
154      //for (ntIdx = 0; ntIdx < phrase.Length; ntIdx++) if (grammar.IsNonTerminal(phrase[ntIdx])) break;
155      //for (int l = ntIdx-2; l >= 0; l--) {
156      //  yield return new Feature(phrase.Substring(l, ntIdx-l-1), 1.0);
157      //}
158      //
159      ////yield return new Feature("$" + phrase[0], 1.0);
160      // if (!isTerminal) {
161      //   for (int i = 4; i < phrase.Length; i++) {
162      //     if (grammar.IsNonTerminal(phrase[i])) {
163      //       yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 0.1);
164      //       break;
165      //     }
166      //   }
167      // }
168      // var d = 0;
169      // var ls = 0;
170      // var rs = 0;
171      // var qs = 0;
172      // foreach (var ch in phrase) if (ch == 'l') { d--; ls++; } else if (ch == 'r') { d++; rs++; } else if (ch == '?') qs++;
173      // yield return new Feature(isTerminal + "D" + Math.Abs(d), 1.0);
174      // yield return new Feature(isTerminal + "R" + rs, 1.0);
175      // yield return new Feature(isTerminal + "L" + ls, 1.0);
176      // yield return new Feature(isTerminal + "?" + qs, 1.0);
177
178      yield return new Feature(phrase, 1.0);
179      //for (int i = 0; i < phrase.Length; i++)
180      //  yield return new Feature(i.ToString() + phrase[i].ToString(), 1.0);
181      // yield return new Feature("Length", phrase.Length); //
182      // foreach (var pair in phrase.Zip(phrase.Skip(1), Tuple.Create)) {
183      //   yield return new Feature(pair.Item1.ToString() + pair.Item2, 1.0);
184      // }
185      // number of occurances for each symbol
186    }
187
188    public IGrammar TreeBasedGPGrammar { get; private set; }
189    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
190      var sb = new StringBuilder();
191      ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
192      return sb.ToString();
193    }
194    private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
195      if (node.SubtreeCount == 0) {
196        // terminal
197        sb.Append(node.Symbol.Name);
198      } else if (node.Symbol.Name == "I") {
199        Debug.Assert(node.SubtreeCount == 2);
200        sb.Append("?(");
201        ConvertTreeToSentence(node.GetSubtree(0), sb);
202        sb.Append(")(");
203        ConvertTreeToSentence(node.GetSubtree(1), sb);
204        sb.Append(")");
205      } else {
206        foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
207      }
208    }
209  }
210
211  public class Ant {
212    private int maxSteps = 600;
213    public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
214    public enum HeadingEnum { North, East, South, West };
215    public int FoodEaten { get; private set; }
216    private readonly char[][] world = new char[32][];
217    private int posX;
218    private int posY;
219    private int steps;
220    private HeadingEnum heading;
221    public int PosX { get { return posX; } }
222    public int PosY { get { return posY; } }
223    public HeadingEnum Heading { get { return heading; } }
224    private bool recordTrail = false;
225    private StringBuilder trailBuilder;
226
227    public string Trail {
228      get {
229        if (!recordTrail) throw new NotSupportedException();
230        else return trailBuilder.ToString() + heading; // add final heading as state
231      }
232    }
233
234    public Ant(bool recordTrail = false) {
235      world[00] = " ###                            ".ToCharArray();
236      world[01] = "   #                            ".ToCharArray();
237      world[02] = "   #                    .###..  ".ToCharArray();
238      world[03] = "   #                    #    #  ".ToCharArray();
239      world[04] = "   #                    #    #  ".ToCharArray();
240      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
241      world[06] = "            #       .        #  ".ToCharArray();
242      world[07] = "            #       #        .  ".ToCharArray();
243      world[08] = "            #       #        .  ".ToCharArray();
244      world[09] = "            #       #        #  ".ToCharArray();
245      world[10] = "            .       #        .  ".ToCharArray();
246      world[11] = "            #       .        .  ".ToCharArray();
247      world[12] = "            #       .        #  ".ToCharArray();
248      world[13] = "            #       #        .  ".ToCharArray();
249      world[14] = "            #       #  ...###.  ".ToCharArray();
250      world[15] = "            .   .#...  #        ".ToCharArray();
251      world[16] = "            .   .      .        ".ToCharArray();
252      world[17] = "            #   .      .        ".ToCharArray();
253      world[18] = "            #   #      .#...    ".ToCharArray();
254      world[19] = "            #   #          #    ".ToCharArray();
255      world[20] = "            #   #          .    ".ToCharArray();
256      world[21] = "            #   #          .    ".ToCharArray();
257      world[22] = "            #   .      ...#.    ".ToCharArray();
258      world[23] = "            #   .      #        ".ToCharArray();
259      world[24] = " ..##..#####.   #               ".ToCharArray();
260      world[25] = " #              #               ".ToCharArray();
261      world[26] = " #              #               ".ToCharArray();
262      world[27] = " #     .#######..               ".ToCharArray();
263      world[28] = " #     #                        ".ToCharArray();
264      world[29] = " .     #                        ".ToCharArray();
265      world[30] = " .####..                        ".ToCharArray();
266      world[31] = "                                ".ToCharArray();
267
268      posX = 0;
269      posY = 0;
270      heading = HeadingEnum.East;
271      FoodEaten = 0;
272      steps = 0;
273
274      this.recordTrail = recordTrail;
275      if (this.recordTrail) trailBuilder = new StringBuilder();
276    }
277
278    public bool Done() {
279      return steps > maxSteps;
280    }
281
282    public void TurnRight() {
283      if (steps <= maxSteps) {
284        steps++;
285        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
286        else heading++;
287      }
288    }
289
290    public void TurnLeft() {
291      if (steps <= maxSteps) {
292        steps++;
293        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
294        else heading--;
295      }
296    }
297
298    public void Move() {
299      if (steps <= maxSteps) {
300        steps++;
301        MoveInternal(ref posX, ref posY);
302        if (world[posY][posX] == '#') {
303          FoodEaten++;
304          world[posY][posX] = '.';
305        }
306        if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
307      }
308    }
309
310    public void Nop() {
311      // wait one time step
312      if (steps <= maxSteps) {
313        steps++;
314      }
315    }
316
317    private void MoveInternal(ref int posX, ref int posY) {
318      switch (heading) {
319        case HeadingEnum.North:
320          posY = (posY + 31) % 32;
321          break;
322        case HeadingEnum.East:
323          posX = (posX + 1) % 32;
324          break;
325        case HeadingEnum.South:
326          posY = (posY + 1) % 32;
327          break;
328        case HeadingEnum.West:
329          posX = (posX + 31) % 32;
330          break;
331      }
332    }
333
334    public bool IsFoodAhead() {
335      int nextPosX = posX;
336      int nextPosY = posY;
337      MoveInternal(ref nextPosX, ref nextPosY);
338
339      if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
340
341      return world[nextPosY][nextPosX] == '#';
342    }
343  }
344}
Note: See TracBrowser for help on using the repository browser.