Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11832 was 11832, checked in by gkronber, 8 years ago

linear value function approximation and good results for poly-10 benchmark

File size: 7.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Runtime.InteropServices;
5using System.Runtime.Remoting.Messaging;
6using System.Text;
7using System.Text.RegularExpressions;
8
9namespace HeuristicLab.Problems.GrammaticalOptimization {
10  public class SantaFeAntProblem : IProblem {
11    private const string grammarString = @"
12G(A):
13A -> l | r | m | ?(A)(A) | lA | rA | mA
14";
15
16
17    // original koza grammar
18    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
19    //
20    // here we use a modified grammar which has only one syntax tree for each sentence
21
22
23    private readonly IGrammar grammar;
24
25    public SantaFeAntProblem() {
26      this.grammar = new Grammar(grammarString);
27    }
28
29    public double BestKnownQuality(int maxLen) {
30      // for now only an upper bound is returned, ideally all food pellets are discovered
31      return 89;
32    }
33
34    public IGrammar Grammar {
35      get { return grammar; }
36    }
37
38    public double Evaluate(string sentence) {
39      var ant = new Ant();
40      int p = 0;
41      Run(ant, sentence, ref p);
42      return ant.FoodEaten;
43    }
44
45    private void Run(Ant ant, string sentence, ref int p) {
46      while (!ant.Done()) {
47        if (p >= sentence.Length) p = 0; // restart
48        switch (sentence[p]) {
49          case 'r': {
50              ant.TurnRight();
51              p++;
52              break;
53            }
54          case 'l': {
55              ant.TurnLeft();
56              p++;
57              break;
58            }
59          case 'm': {
60              ant.Move();
61              p++;
62              break;
63            }
64          case '?': {
65              p++; // skip p
66              if (ant.IsFoodAhead()) {
67                if (sentence[p] != '(') throw new ArgumentException();
68                p++;
69                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
70                if (ant.Done()) return;
71                if (sentence[p] != '(') throw new ArgumentException();
72                p++;
73                Skip(sentence, ref p);
74              } else {
75                if (sentence[p] != '(') throw new ArgumentException();
76                p++;
77                Skip(sentence, ref p);
78                if (sentence[p] != '(') throw new ArgumentException();
79                p++;
80                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
81              }
82              break;
83            }
84          case ')': {
85              p++; // skip
86              return;     // caller must continue processing
87            }
88          default: {
89              throw new ArgumentException();
90            }
91        }
92      }
93    }
94
95    private void Skip(string sentence, ref int p) {
96      int openCount = 1;
97      while (openCount > 0) {
98        if (sentence[p] == '(') openCount++;
99        else if (sentence[p] == ')') openCount--;
100        p++;
101      }
102    }
103
104    public string CanonicalRepresentation(string phrase) {
105      var sb = new StringBuilder(phrase);
106      string canonicalPhrase = phrase;
107      string oldPhrase;
108      do {
109        oldPhrase = canonicalPhrase;
110        sb.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
111        canonicalPhrase = sb.ToString();
112      } while (canonicalPhrase != oldPhrase);
113      return sb.ToString();
114    }
115
116    public IEnumerable<Feature> GetFeatures(string phrase) {
117      return Enumerable.Repeat(new Feature(CanonicalRepresentation(phrase), 1.0), 1);
118    }
119  }
120
121  public class Ant {
122    private const int maxSteps = 600;
123    public enum HeadingEnum { North, East, South, West };
124    public int FoodEaten { get; private set; }
125    private readonly char[][] world = new char[32][];
126    private int posX;
127    private int posY;
128    private int steps;
129    private HeadingEnum heading;
130
131
132
133    public Ant() {
134      world[00] = " ###                            ".ToCharArray();
135      world[01] = "   #                            ".ToCharArray();
136      world[02] = "   #                    .###..  ".ToCharArray();
137      world[03] = "   #                    #    #  ".ToCharArray();
138      world[04] = "   #                    #    #  ".ToCharArray();
139      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
140      world[06] = "            #       .        #  ".ToCharArray();
141      world[07] = "            #       #        .  ".ToCharArray();
142      world[08] = "            #       #        .  ".ToCharArray();
143      world[09] = "            #       #        #  ".ToCharArray();
144      world[10] = "            .       #        .  ".ToCharArray();
145      world[11] = "            #       .        .  ".ToCharArray();
146      world[12] = "            #       .        #  ".ToCharArray();
147      world[13] = "            #       #        .  ".ToCharArray();
148      world[14] = "            #       #  ...###.  ".ToCharArray();
149      world[15] = "            .   .#...  #        ".ToCharArray();
150      world[16] = "            .   .      .        ".ToCharArray();
151      world[17] = "            #   .      .        ".ToCharArray();
152      world[18] = "            #   #      .#...    ".ToCharArray();
153      world[19] = "            #   #          #    ".ToCharArray();
154      world[20] = "            #   #          .    ".ToCharArray();
155      world[21] = "            #   #          .    ".ToCharArray();
156      world[22] = "            #   .      ...#.    ".ToCharArray();
157      world[23] = "            #   .      #        ".ToCharArray();
158      world[24] = " ..##..#####.   #               ".ToCharArray();
159      world[25] = " #              #               ".ToCharArray();
160      world[26] = " #              #               ".ToCharArray();
161      world[27] = " #     .#######..               ".ToCharArray();
162      world[28] = " #     #                        ".ToCharArray();
163      world[29] = " .     #                        ".ToCharArray();
164      world[30] = " .####..                        ".ToCharArray();
165      world[31] = "                                ".ToCharArray();
166
167      posX = 0;
168      posY = 0;
169      heading = HeadingEnum.East;
170      FoodEaten = 0;
171      steps = 0;
172    }
173
174    public bool Done() {
175      return steps > maxSteps;
176    }
177
178    public void TurnRight() {
179      if (steps <= maxSteps) {
180        steps++;
181        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
182        else heading++;
183      }
184    }
185
186    public void TurnLeft() {
187      if (steps <= maxSteps) {
188        steps++;
189        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
190        else heading--;
191      }
192    }
193
194    public void Move() {
195      if (steps <= maxSteps) {
196        steps++;
197        MoveInternal(ref posX, ref posY);
198        if (world[posY][posX] == '#') {
199          FoodEaten++;
200          world[posY][posX] = '.';
201        }
202      }
203    }
204
205    private void MoveInternal(ref int posX, ref int posY) {
206      switch (heading) {
207        case HeadingEnum.North:
208          posY = (posY + 31) % 32;
209          break;
210        case HeadingEnum.East:
211          posX = (posX + 1) % 32;
212          break;
213        case HeadingEnum.South:
214          posY = (posY + 1) % 32;
215          break;
216        case HeadingEnum.West:
217          posX = (posX + 31) % 32;
218          break;
219      }
220    }
221
222    public bool IsFoodAhead() {
223      int nextPosX = posX;
224      int nextPosY = posY;
225      MoveInternal(ref nextPosX, ref nextPosY);
226      return world[nextPosY][nextPosX] == '#';
227    }
228  }
229}
Note: See TracBrowser for help on using the repository browser.