Free cookie consent management tool by TermsFeed Policy Generator

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

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

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