Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2283 added SelectionIndicator for MCTS and problems SantaFeAnt, SymbolicRegression10, RoyalSymbol; updated SantaFeAnt grammar
File size: 19.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{
13    public class SantaFeAntProblem : ISymbolicExpressionTreeProblem
14    {
15        private const string grammarString = @"
16G(A):
17A -> l | r | m | ?(A)(A) | ?(A)(A)A | lA | rA | mA
18";
19        // for tree-based GP in HL we need a different grammar for the same language
20        // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
21        private const string hlGrammarString = @"
22    G(A):
23    A -> l | r | m | P | I
24    P -> AA | AAA
25    I -> AA
26    ";
27
28
29        // original koza grammar
30        // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
31        //
32        // here we use a modified grammar which has only one syntax tree for each sentence
33
34
35        private readonly IGrammar grammar;
36        public string Name { get { return "SantaFeAnt"; } }
37
38        public SantaFeAntProblem()
39        {
40            this.grammar = new Grammar(grammarString);
41            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
42        }
43
44        public double BestKnownQuality(int maxLen)
45        {
46            // for now only an upper bound is returned, ideally all food pellets are discovered
47            return 89;
48        }
49
50        public IGrammar Grammar
51        {
52            get { return grammar; }
53        }
54
55        public double Evaluate(string sentence)
56        {
57            var ant = new Ant();
58            int p = 0;
59            Run(ant, sentence, ref p);
60            return ant.FoodEaten;
61        }
62
63        private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false)
64        {
65            while (!ant.Done())
66            {
67                if (p >= sentence.Length)
68                {
69                    if (stopAfterFirst) return;
70                    p = 0; // restart
71                }
72                switch (sentence[p])
73                {
74                    case 'r':
75                        {
76                            ant.TurnRight();
77                            p++;
78                            break;
79                        }
80                    case 'l':
81                        {
82                            ant.TurnLeft();
83                            p++;
84                            break;
85                        }
86                    case 'm':
87                        {
88                            ant.Move();
89                            p++;
90                            break;
91                        }
92                    case '?':
93                        {
94                            p++; // skip p
95                            if (ant.IsFoodAhead())
96                            {
97                                if (sentence[p] != '(') throw new ArgumentException();
98                                p++;
99                                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
100                                if (ant.Done()) return;
101                                if (sentence[p] != '(') throw new ArgumentException();
102                                p++;
103                                Skip(sentence, ref p);
104                            }
105                            else
106                            {
107                                if (sentence[p] != '(') throw new ArgumentException();
108                                p++;
109                                Skip(sentence, ref p);
110                                if (sentence[p] != '(') throw new ArgumentException();
111                                p++;
112                                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
113                            }
114                            break;
115                        }
116                    case '.':
117                        {
118                            // nop
119                            p++;
120                            ant.Nop();
121                            break;
122                        }
123                    case ')':
124                        {
125                            p++; // skip
126                            return;     // caller must continue processing
127                        }
128                    default:
129                        {
130                            throw new ArgumentException();
131                        }
132                }
133            }
134        }
135
136        private static void Skip(string sentence, ref int p)
137        {
138            int openCount = 1;
139            while (openCount > 0)
140            {
141                if (sentence[p] == '(') openCount++;
142                else if (sentence[p] == ')') openCount--;
143                p++;
144            }
145        }
146
147        public string CanonicalRepresentation(string phrase)
148        {
149            //phrase = phrase.Replace("A", ".");
150            var sb = new StringBuilder(phrase);
151            string canonicalPhrase = phrase;
152            string oldPhrase;
153            do
154            {
155                oldPhrase = canonicalPhrase;
156                sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
157                //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
158                canonicalPhrase = sb.ToString();
159            } while (canonicalPhrase != oldPhrase);
160            return canonicalPhrase;
161        }
162
163        public IEnumerable<Feature> GetFeatures(string phrase)
164        {
165            phrase = CanonicalRepresentation(phrase);
166            var isTerminal = grammar.IsTerminal(phrase);
167
168            yield return new Feature(isTerminal + ToString(), 1.0);
169
170            yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
171            if (!isTerminal)
172            {
173                for (int i = 4; i < phrase.Length; i++)
174                {
175                    if (!grammar.IsTerminal(phrase[i]))
176                    {
177                        yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
178                        break;
179                    }
180                }
181            }
182
183            yield return new Feature(phrase, 1.0);
184        }
185
186        public IGrammar TreeBasedGPGrammar { get; private set; }
187        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
188        {
189            var sb = new StringBuilder();
190            ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
191            return sb.ToString();
192        }
193        private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb)
194        {
195            if (node.SubtreeCount == 0)
196            {
197                // terminal
198                sb.Append(node.Symbol.Name);
199            }
200            else if (node.Symbol.Name == "I")
201            {
202                Debug.Assert(node.SubtreeCount == 2);
203                sb.Append("?(");
204                ConvertTreeToSentence(node.GetSubtree(0), sb);
205                sb.Append(")(");
206                ConvertTreeToSentence(node.GetSubtree(1), sb);
207                sb.Append(")");
208            }
209            else
210            {
211                foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
212            }
213        }
214
215        private string[] solutions;
216
217        public void GenerateProblemSolutions(int maxLen)
218        {
219            if (maxLen > 17)
220            {
221                throw new NotImplementedException();
222            }
223            solutions = new string[12];
224            solutions[0] = "?(m)(ll?(m)(r))mr";
225            solutions[1] = "?(m)(rr?(m)(l))ml";
226            solutions[2] = "r?(m)(ll?(m)(r))m";
227            solutions[3] = "l?(m)(rr?(m)(l))m";
228            solutions[4] = "mr?(m)(ll?(m)(r))";
229            solutions[5] = "ml?(m)(rr?(m)(l))";
230            solutions[6] = "?(m)(ll?(m)(l))ml";
231            solutions[7] = "?(m)(rr?(m)(r))mr";
232            solutions[8] = "l?(m)(ll?(m)(l))m";
233            solutions[9] = "r?(m)(rr?(m)(r))m";
234            solutions[10] = "ml?(m)(ll?(m)(l))";
235            solutions[11] = "mr?(m)(rr?(m)(r))";
236
237            // A
238            // rA
239            // lA
240            // mA
241            // mlA
242            // mrA
243            // ?(A)(A)A
244            // mr?(m)(ll?(A)(A))
245            // ?(A)(A)?(A)(A)
246        }
247
248        private readonly List<string> validStarts3 = new List<string> { "A", "rA", "lA", "mA", "mlA", "mrA" };
249
250
251        public bool IsParentOfProblemSolution(string sentence, int maxLen)
252        {
253            //INFO: only works with maxlen 17!!
254
255            // eliminate wrong parents..
256            if (sentence.Length < 17 && !sentence.Contains('A'))
257            {
258                return false;
259            }
260            if (sentence.Length > 3 && !sentence.Contains('?'))
261            {
262                return false;
263            }
264            if (sentence.Length <= 3)
265            {
266                return validStarts3.Contains(sentence);
267            }
268            if (sentence.Contains("m?"))
269            {
270                return false;
271            }
272
273            if (sentence.Length <= 17 && sentence.Contains('A'))
274            {
275                // check front part of solutions..
276                // contains A, contains ?(x)(x), length > 3
277                int index = sentence.IndexOf('?');
278                if (index > 2) return false;
279
280                int firstCloseBracket = sentence.IndexOf(')');
281                // only one item in bracket
282                if ((firstCloseBracket - index) != 3) return false;
283                // must be m or A
284                if (sentence[firstCloseBracket - 1] != 'm' && sentence[firstCloseBracket - 1] != 'A') return false;
285
286                // check back and front part of solutions..
287                int lastCloseBracket = sentence.LastIndexOf(')');
288                // before first ? and after last ) either 1 left one right, or only two left (also A), or only two right (also A)
289                int diff;
290                if (index == 0)
291                {
292                    // must end with mr, ml, mA, A
293                    diff = sentence.Length - 1 - lastCloseBracket;
294                    if (diff == 0 || diff > 2) return false;
295                    if (diff == 1 && sentence[sentence.Length - 1] != 'A') return false;
296                    if (diff == 2 && (sentence[sentence.Length - 2] != 'm' || sentence[sentence.Length - 1] == 'm'))
297                        return false;
298                }
299                else if (index == 1 && (sentence[0] == 'm' || (sentence[sentence.Length - 1] != 'm' && sentence[sentence.Length - 1] != 'A'))) return false;
300                else if (index == 2)
301                {
302                    // must start with ml, mr, mA
303                    // must end with )
304                    if (sentence[sentence.Length - 1] != ')') return false;
305                    if (sentence[0] != 'm' || sentence[1] == 'm') return false;
306                }
307
308                // check middle part of solutions ..(ll?(m)(l))..
309                int index2 = sentence.IndexOf('?', index + 1);
310                if (index2 == -1)
311                {
312                    // no second ? so far..
313                    // allowed within second (..): A, lA, llA, rA, rrA
314                    int lastOpenBracket = sentence.LastIndexOf('(', lastCloseBracket);
315                    diff = lastCloseBracket - lastOpenBracket;
316                    if (diff > 4) return false;
317                    // last item must be A
318                    if (sentence[lastCloseBracket - 1] != 'A') return false;
319                    // first item must not be m
320                    if (sentence[lastOpenBracket + 1] == 'm') return false;
321                    // ll or rr
322                    if (diff == 4 && sentence[lastOpenBracket + 1] != sentence[lastOpenBracket + 2]) return false;
323                }
324                else
325                {
326                    // second ? there..
327                    // ?(x)(..?(x)(x))
328                    int secondLastCloseBracket = sentence.LastIndexOf(')', lastCloseBracket - 1);
329                    // has to end with '))'
330                    if (lastCloseBracket - secondLastCloseBracket != 1) return false;
331                    // only one item within second brackets
332                    if (sentence[secondLastCloseBracket - 2] != '(') return false;
333                    // the one item can be A, l or r
334                    if (sentence[secondLastCloseBracket - 1] == 'm') return false;
335                    // only one item in first brackets
336                    if (sentence[index2 + 3] != ')') return false;
337                    // only m or A allowed
338                    if (sentence[index2 + 2] == 'l' || sentence[index2 + 2] == 'r') return false;
339                    // ll or rr before second ? must already be there..
340                    if (sentence[index2 - 1] != 'l' && sentence[index2 - 1] != 'r') return false;
341                    if (sentence[index2 - 1] != sentence[index2 - 2]) return false;
342                }
343            }
344            else
345            {
346                // has to be solution or false..
347                return solutions.Any(solution => solution == sentence);
348            }
349
350            return true;
351        }
352    }
353
354    public class Ant
355    {
356        private int maxSteps = 600;
357        public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
358        public enum HeadingEnum { North, East, South, West };
359        public int FoodEaten { get; private set; }
360        private readonly char[][] world = new char[32][];
361        private int posX;
362        private int posY;
363        private int steps;
364        private HeadingEnum heading;
365        public int PosX { get { return posX; } }
366        public int PosY { get { return posY; } }
367        public HeadingEnum Heading { get { return heading; } }
368        private bool recordTrail = false;
369        private StringBuilder trailBuilder;
370
371        public string Trail
372        {
373            get
374            {
375                if (!recordTrail) throw new NotSupportedException();
376                else return trailBuilder.ToString() + heading; // add final heading as state
377            }
378        }
379
380        public Ant(bool recordTrail = false)
381        {
382            world[00] = " ###                            ".ToCharArray();
383            world[01] = "   #                            ".ToCharArray();
384            world[02] = "   #                    .###..  ".ToCharArray();
385            world[03] = "   #                    #    #  ".ToCharArray();
386            world[04] = "   #                    #    #  ".ToCharArray();
387            world[05] = "   ####.#####       .##..    .  ".ToCharArray();
388            world[06] = "            #       .        #  ".ToCharArray();
389            world[07] = "            #       #        .  ".ToCharArray();
390            world[08] = "            #       #        .  ".ToCharArray();
391            world[09] = "            #       #        #  ".ToCharArray();
392            world[10] = "            .       #        .  ".ToCharArray();
393            world[11] = "            #       .        .  ".ToCharArray();
394            world[12] = "            #       .        #  ".ToCharArray();
395            world[13] = "            #       #        .  ".ToCharArray();
396            world[14] = "            #       #  ...###.  ".ToCharArray();
397            world[15] = "            .   .#...  #        ".ToCharArray();
398            world[16] = "            .   .      .        ".ToCharArray();
399            world[17] = "            #   .      .        ".ToCharArray();
400            world[18] = "            #   #      .#...    ".ToCharArray();
401            world[19] = "            #   #          #    ".ToCharArray();
402            world[20] = "            #   #          .    ".ToCharArray();
403            world[21] = "            #   #          .    ".ToCharArray();
404            world[22] = "            #   .      ...#.    ".ToCharArray();
405            world[23] = "            #   .      #        ".ToCharArray();
406            world[24] = " ..##..#####.   #               ".ToCharArray();
407            world[25] = " #              #               ".ToCharArray();
408            world[26] = " #              #               ".ToCharArray();
409            world[27] = " #     .#######..               ".ToCharArray();
410            world[28] = " #     #                        ".ToCharArray();
411            world[29] = " .     #                        ".ToCharArray();
412            world[30] = " .####..                        ".ToCharArray();
413            world[31] = "                                ".ToCharArray();
414
415            posX = 0;
416            posY = 0;
417            heading = HeadingEnum.East;
418            FoodEaten = 0;
419            steps = 0;
420
421            this.recordTrail = recordTrail;
422            if (this.recordTrail) trailBuilder = new StringBuilder();
423        }
424
425        public bool Done()
426        {
427            return steps > maxSteps;
428        }
429
430        public void TurnRight()
431        {
432            if (steps <= maxSteps)
433            {
434                steps++;
435                if (heading == HeadingEnum.West) heading = HeadingEnum.North;
436                else heading++;
437            }
438        }
439
440        public void TurnLeft()
441        {
442            if (steps <= maxSteps)
443            {
444                steps++;
445                if (heading == HeadingEnum.North) heading = HeadingEnum.West;
446                else heading--;
447            }
448        }
449
450        public void Move()
451        {
452            if (steps <= maxSteps)
453            {
454                steps++;
455                MoveInternal(ref posX, ref posY);
456                if (world[posY][posX] == '#')
457                {
458                    FoodEaten++;
459                    world[posY][posX] = '.';
460                }
461                if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
462            }
463        }
464
465        public void Nop()
466        {
467            // wait one time step
468            if (steps <= maxSteps)
469            {
470                steps++;
471            }
472        }
473
474        private void MoveInternal(ref int posX, ref int posY)
475        {
476            switch (heading)
477            {
478                case HeadingEnum.North:
479                    posY = (posY + 31) % 32;
480                    break;
481                case HeadingEnum.East:
482                    posX = (posX + 1) % 32;
483                    break;
484                case HeadingEnum.South:
485                    posY = (posY + 1) % 32;
486                    break;
487                case HeadingEnum.West:
488                    posX = (posX + 31) % 32;
489                    break;
490            }
491        }
492
493        public bool IsFoodAhead()
494        {
495            int nextPosX = posX;
496            int nextPosY = posY;
497            MoveInternal(ref nextPosX, ref nextPosY);
498
499            if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
500
501            return world[nextPosY][nextPosX] == '#';
502        }
503    }
504}
Note: See TracBrowser for help on using the repository browser.