Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2283: implemented test problems for MCTS

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