Submission: Here
Ant 1: Here
Ant 2: Here
I had two goals for this year's contest: have fun and learn C#. I accomplished both, so I consider it a win regardless of where my ant brains end up in the final standings. As I'm sure was true with other teams, I felt I just got started figuring out really good ant algorithms. Also, it's very hard to evaluate your algorithms in the absence of anyone else's work. I wish these contests were done in two or three stages, where the submissions from each stage are published prior to the next stage being started.
My submission made use of a custom state machine macro language. The language has very terse commands for the things the ant can do. For example, move forward is "^" and drop food is "-".
Sequences of actions are specified in a named macro phrase. For example:
turnThreeTimes = < < <.
The turn left command is "<". The macro phrase is specified by a name, an equals, a series of commands, and a period. The macros can, of course, be used in other macros:
turnNineTimes = turnThreeTimes turnThreeTimes turnThreeTimes.
Each command can succeed or fail. If it succeeds, it proceeds to the next command. If it fails, it aborts the phrase and fails upward. But any command (or command sequence) can be appended with code that executes only if the command succeeds or fails. Success code is surrounded by squirrelly brackets ("{" and "}"). Failure code is surrounded by square brackets ("[" and "]"). For example:
moveAndTurnIfYouCant = ^ [>].
Sensing is just another command, specified by a "?" followed by what to sense. For example, "?f" senses food in the current cell; "?^f" senses food in the cell ahead; "?4m" senses marker 4. Flip is just another sense: "?14".
Any command can have it's success/failure sense reversed by preceding it with an "!". For example:
moveIfNoHomeAhead = !?h ^.
Note that because a command will fail upward, we don't need to surround the "then" section with anything so long as we want a failure to exit the phrase.
There can also be multiple phrases of the same name. In this case, the first one is tried. If it fails, the second one is tried. If it fails, the third one is tried, etc. (But there is no backtracking in the event of failure; this isn't Prolog.) For example:
pointAtMarker2 = ?^2m.
pointAtMarker2 = ?<2m <.
pointAtMarker2 = ?>2m >.
Finally, you can cause a phrase to cycle (repeat from the start) using the "~" command.
Execution always begins with the "start" phrase.
Using this language, a simple random walk looking for food, and
random walk returning it to the anthill is:
start = explore.
explore = ?h ^[] ~.
explore = ?f + takeHome ~.
explore = ?20 {>}[] ~.
explore = ^ [>] ~.
takeHome = ?h -.
takeHome = ?20 {>}[] ~.
takeHome = ^ [<] ~.
We can quickly get more complicated by leaving a gradient behind to follow when returning to the anthill (made of repeated 0/1/2 markers):
start = explore.
explore = explore0 explore1 explore2 ~.
explore0 = ?h ^[] ~.
explore0 = ?f + takeHome ~.
explore0 = ?20 {>}[] ~.
explore0 = ?1m [?2m [/0]] ^[~].
explore1 = ?h ^[] ~.
explore1 = ?f + takeHome ~.
explore1 = ?20 {>}[] ~.
explore1 = ?0m [?2m [/1]] ^[~].
explore2 = ?h ^[] ~.
explore2 = ?f + takeHome ~.
explore2 = ?20 {>}[] ~.
explore2 = ?0m [?1m [/2]] ^[~].
takeHome = ?h -.
takeHome = ?0m ?^2m {^ ~}[] ?<2m {< ~}[] ?>2m {> ~}.
takeHome = ?1m ?^0m {^ ~}[] ?<0m {< ~}[] ?>0m {> ~}.
takeHome = ?2m ?^1m {^ ~}[] ?<1m {< ~}[] ?>1m {> ~}.
takeHome = ^ [>] ~.
This generates the following 105 state machine:
Sense here 1 2 home
Move 0 2
Sense here 3 29 food
PickUp 4 29
Sense here 5 6 home
Drop 0
Sense here 7 13 marker 0
Sense ahead 8 9 marker 2
Move 4 13
Sense leftAhead 10 11 marker 2
Turn left 4
Sense rightAhead 12 13 marker 2
Turn right 4
Sense here 14 20 marker 1
Sense ahead 15 16 marker 0
Move 4 20
Sense leftAhead 17 18 marker 0
Turn left 4
Sense rightAhead 19 20 marker 0
Turn right 4
Sense here 21 27 marker 2
Sense ahead 22 23 marker 1
Move 4 27
Sense leftAhead 24 25 marker 1
Turn left 4
Sense rightAhead 26 27 marker 1
Turn right 4
Move 4 28
Turn right 4
Flip 20 30 31
Turn right 0
Sense here 34 32 marker 1
Sense here 34 33 marker 2
Mark 0 34
Move 35 0
Sense here 36 37 home
Move 35 37
Sense here 38 64 food
PickUp 39 64
Sense here 40 41 home
Drop 35
Sense here 42 48 marker 0
Sense ahead 43 44 marker 2
Move 39 48
Sense leftAhead 45 46 marker 2
Turn left 39
Sense rightAhead 47 48 marker 2
Turn right 39
Sense here 49 55 marker 1
Sense ahead 50 51 marker 0
Move 39 55
Sense leftAhead 52 53 marker 0
Turn left 39
Sense rightAhead 54 55 marker 0
Turn right 39
Sense here 56 62 marker 2
Sense ahead 57 58 marker 1
Move 39 62
Sense leftAhead 59 60 marker 1
Turn left 39
Sense rightAhead 61 62 marker 1
Turn right 39
Move 39 63
Turn right 39
Flip 20 65 66
Turn right 35
Sense here 69 67 marker 0
Sense here 69 68 marker 2
Mark 1 69
Move 70 35
Sense here 71 72 home
Move 70 72
Sense here 73 99 food
PickUp 74 99
Sense here 75 76 home
Drop 70
Sense here 77 83 marker 0
Sense ahead 78 79 marker 2
Move 74 83
Sense leftAhead 80 81 marker 2
Turn left 74
Sense rightAhead 82 83 marker 2
Turn right 74
Sense here 84 90 marker 1
Sense ahead 85 86 marker 0
Move 74 90
Sense leftAhead 87 88 marker 0
Turn left 74
Sense rightAhead 89 90 marker 0
Turn right 74
Sense here 91 97 marker 2
Sense ahead 92 93 marker 1
Move 74 97
Sense leftAhead 94 95 marker 1
Turn left 74
Sense rightAhead 96 97 marker 1
Turn right 74
Move 74 98
Turn right 74
Flip 20 100 101
Turn right 70
Sense here 104 102 marker 0
Sense here 104 103 marker 1
Mark 2 104
Move 0 70
My primary ant entry for the contest is the program below. The resulting state machine has 1545 states.
It orients all the ants facing outward, specializes six for guard duty, then explores leaving return gradients. If food is found, it leaves another marker on the way back to make it easier to return to it. This only works partially, but does seem to improve the scores.
With a couple more days, I would have figured out how to make death squads. But this version is essentially pacifistic. There are also several groups that could be specialized for different tasks, but currently there are only explorers and guards.
I'm not posting the compiler code since it's too quick-and-dirty to show to others without some clean-up. But if I get few people expressing interest, I'll clean and post it.
start = orientation.
orientation = !?<h !?^h circle5.
orientation = ?<2m ?^2m circle4.
orientation = ?<1m ?^1m circle3.
orientation = ?<0m ?^0m circle2.
orientation = ?<5m ?^5m circle1.
orientation = ?<4m ?^4m circle0.
orientation = > ~.
circle5 = /2 circle5Op.
circle4 = /1 circle4Op.
circle3 = /0 circle3Op.
circle2 = /5 circle2Op.
circle1 = /4 circle1Op.
circle0 = /3 circle0Op.
circle5Op = explore.
circle4Op = explore.
circle3Op = explore.
circle2Op = explore.
circle1Op = protectStart.
circle0Op = mustMove mustMove > mustMove mustMove mustMove explore.
protectStart = mustMove mustMove mustMove >>> mustMove mustMove mustMove >>>
protect.
protect = ?<f < ~.
protect = ?>f > ~.
protect = ?^f [~] mustMove +[] >>> mustMove findCenter mustMove - >>> mustMove
~.
findCenter = ?^3m.
findCenter = ?<3m <.
findCenter = ?>3m >.
findCenter = > ~.
explore = explore0 explore1 explore2 ~.
explore0 = ?h ^[] ~.
explore0 = ?f + takeHome ~.
explore0 = ?^1m ?^3m ^[] \3 ~.
explore0 = ?<1m ?<3m < ^[] \3 ~.
explore0 = ?>1m ?>3m > ^[] \3 ~.
explore0 = ?20 {>}[] ~.
explore0 = ?1m [?2m [/0]] ^[~].
explore0 = ?50 > ^[] ~.
explore1 = ?h ^[] ~.
explore1 = ?f + takeHome ~.
explore1 = ?^2m ?^3m ^[] \3 ~.
explore1 = ?<2m ?<3m < ^[] \3 ~.
explore1 = ?>2m ?>3m > ^[] \3 ~.
explore1 = ?20 {>}[] ~.
explore1 = ?0m [?2m [/1]] ^[~].
explore1 = ?50 > ^[] ~.
explore2 = ?h ^[] ~.
explore2 = ?f + takeHome ~.
explore2 = ?^0m ?^3m ^[] \3 ~.
explore2 = ?<0m ?<3m < ^[] \3 ~.
explore2 = ?>0m ?>3m > ^[] \3 ~.
explore2 = ?20 {>}[] ~.
explore2 = ?0m [?1m [/2]] ^[~].
explore2 = ?50 > ^[] ~.
takeHome = ?5m - >> mustMove15 >> mustMove15 < \3.
takeHome = ?0m ?^2m {^[> ^] /3 ~}[] ?<2m {< ~}[] ?>2m {> ~}.
takeHome = ?1m ?^0m {^[> ^] /3 ~}[] ?<0m {< ~}[] ?>0m {> ~}.
takeHome = ?2m ?^1m {^[> ^] /3 ~}[] ?<1m {< ~}[] ?>1m {> ~}.
takeHome = ?^5m mustMove ~.
takeHome = ^ [>] ~.
mustMove = ^[~].
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^.
mustMove15 = ^[].