Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs @ 12893

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

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