Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12762 was 12762, checked in by aballeit, 9 years ago

#2283 GUI updates, Tree-chart, MCTS Version 2 (prune leaves)
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    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      phrase = CanonicalRepresentation(phrase);
141      var isTerminal = grammar.IsTerminal(phrase);
142
143      yield return new Feature(isTerminal + ToString(), 1.0);
144     
145      yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
146      if (!isTerminal) {
147        for (int i = 4; i < phrase.Length; i++) {
148          if (!grammar.IsTerminal(phrase[i])) {
149            yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
150            break;
151          }
152        }
153      }
154   
155      yield return new Feature(phrase, 1.0);
156    }
157
158    public IGrammar TreeBasedGPGrammar { get; private set; }
159    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
160      var sb = new StringBuilder();
161      ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
162      return sb.ToString();
163    }
164    private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
165      if (node.SubtreeCount == 0) {
166        // terminal
167        sb.Append(node.Symbol.Name);
168      } else if (node.Symbol.Name == "I") {
169        Debug.Assert(node.SubtreeCount == 2);
170        sb.Append("?(");
171        ConvertTreeToSentence(node.GetSubtree(0), sb);
172        sb.Append(")(");
173        ConvertTreeToSentence(node.GetSubtree(1), sb);
174        sb.Append(")");
175      } else {
176        foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
177      }
178    }
179  }
180
181  public class Ant {
182    private int maxSteps = 600;
183    public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
184    public enum HeadingEnum { North, East, South, West };
185    public int FoodEaten { get; private set; }
186    private readonly char[][] world = new char[32][];
187    private int posX;
188    private int posY;
189    private int steps;
190    private HeadingEnum heading;
191    public int PosX { get { return posX; } }
192    public int PosY { get { return posY; } }
193    public HeadingEnum Heading { get { return heading; } }
194    private bool recordTrail = false;
195    private StringBuilder trailBuilder;
196
197    public string Trail {
198      get {
199        if (!recordTrail) throw new NotSupportedException();
200        else return trailBuilder.ToString() + heading; // add final heading as state
201      }
202    }
203
204    public Ant(bool recordTrail = false) {
205      world[00] = " ###                            ".ToCharArray();
206      world[01] = "   #                            ".ToCharArray();
207      world[02] = "   #                    .###..  ".ToCharArray();
208      world[03] = "   #                    #    #  ".ToCharArray();
209      world[04] = "   #                    #    #  ".ToCharArray();
210      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
211      world[06] = "            #       .        #  ".ToCharArray();
212      world[07] = "            #       #        .  ".ToCharArray();
213      world[08] = "            #       #        .  ".ToCharArray();
214      world[09] = "            #       #        #  ".ToCharArray();
215      world[10] = "            .       #        .  ".ToCharArray();
216      world[11] = "            #       .        .  ".ToCharArray();
217      world[12] = "            #       .        #  ".ToCharArray();
218      world[13] = "            #       #        .  ".ToCharArray();
219      world[14] = "            #       #  ...###.  ".ToCharArray();
220      world[15] = "            .   .#...  #        ".ToCharArray();
221      world[16] = "            .   .      .        ".ToCharArray();
222      world[17] = "            #   .      .        ".ToCharArray();
223      world[18] = "            #   #      .#...    ".ToCharArray();
224      world[19] = "            #   #          #    ".ToCharArray();
225      world[20] = "            #   #          .    ".ToCharArray();
226      world[21] = "            #   #          .    ".ToCharArray();
227      world[22] = "            #   .      ...#.    ".ToCharArray();
228      world[23] = "            #   .      #        ".ToCharArray();
229      world[24] = " ..##..#####.   #               ".ToCharArray();
230      world[25] = " #              #               ".ToCharArray();
231      world[26] = " #              #               ".ToCharArray();
232      world[27] = " #     .#######..               ".ToCharArray();
233      world[28] = " #     #                        ".ToCharArray();
234      world[29] = " .     #                        ".ToCharArray();
235      world[30] = " .####..                        ".ToCharArray();
236      world[31] = "                                ".ToCharArray();
237
238      posX = 0;
239      posY = 0;
240      heading = HeadingEnum.East;
241      FoodEaten = 0;
242      steps = 0;
243
244      this.recordTrail = recordTrail;
245      if (this.recordTrail) trailBuilder = new StringBuilder();
246    }
247
248    public bool Done() {
249      return steps > maxSteps;
250    }
251
252    public void TurnRight() {
253      if (steps <= maxSteps) {
254        steps++;
255        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
256        else heading++;
257      }
258    }
259
260    public void TurnLeft() {
261      if (steps <= maxSteps) {
262        steps++;
263        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
264        else heading--;
265      }
266    }
267
268    public void Move() {
269      if (steps <= maxSteps) {
270        steps++;
271        MoveInternal(ref posX, ref posY);
272        if (world[posY][posX] == '#') {
273          FoodEaten++;
274          world[posY][posX] = '.';
275        }
276        if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
277      }
278    }
279
280    public void Nop() {
281      // wait one time step
282      if (steps <= maxSteps) {
283        steps++;
284      }
285    }
286
287    private void MoveInternal(ref int posX, ref int posY) {
288      switch (heading) {
289        case HeadingEnum.North:
290          posY = (posY + 31) % 32;
291          break;
292        case HeadingEnum.East:
293          posX = (posX + 1) % 32;
294          break;
295        case HeadingEnum.South:
296          posY = (posY + 1) % 32;
297          break;
298        case HeadingEnum.West:
299          posX = (posX + 31) % 32;
300          break;
301      }
302    }
303
304    public bool IsFoodAhead() {
305      int nextPosX = posX;
306      int nextPosY = posY;
307      MoveInternal(ref nextPosX, ref nextPosY);
308
309      if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
310
311      return world[nextPosY][nextPosX] == '#';
312    }
313  }
314}
Note: See TracBrowser for help on using the repository browser.