[Icfp04-discuss] My entry: Team Lone Haskeller

[Carlos Scheidegger]

I have my entries available at: 

http://www.sci.utah.edu/~cscheid/icfp04

Readme for the regular entry follows.. Thanks everyone for this great weekend!

-carlos

----

Team Lone Haskeller
Carlos Eduardo Scheidegger
cscheid at sci.utah.edu

Carlos Eduardo Scheidegger  - cscheid at sci.utah.edu

My submission for the lightning division of the	ICFP programming
contest consists of basically three interesting things:

 - A simulator that runs in the exact same way as the traces provided
   (the dump is identical)

 - An embedded DSL in Haskell to specify the ant brains

 - Two of my hand-crafted ant brains.

My first idea was to develop a high-level specification language and
then evolve behaviors using genetic programming or some other
evolving process. I could not finish this for the lightning division,
but the idea is still in my mind.

The source directory is organized in pretty much the same way as the
task spec. The cartography section has two functions to dump the
results: one dumps info in a human-readable, concise form (to display
in a screen, for example), and the other in the same format as the
traces provided by the judges.

The DSL allows the user to specify higher-level constructs and pipe
them together to create complex ant behaviors. The language has a
simple optimizer that chases redundant jumps and eliminates
unnecessary instructions. The typical state machine reduction rate is
20%, but, in some cases, I experienced more than 60% reduction. The
optimizer can be inefficient in large (>2000 states) programs, but
because most likely the bottleneck is in one line (there's a linear
search in lists in there somewhere), it should be easy to fix it.

The strategy for my ants consist of a mix of roles. The roles are: 

- Searchers: An ant following this strategy will walk
  around pretty much randomly until it finds food. Then it will trace
  its steps back to the anthill. This is the main strategy for finding
  food.

- Followers: A small percentage of the ants will not look randomly
  for food, but will try to follow a previously traced path to
  food. This aims to explore the locality of food in blobs.

- Stickers: a searcher that comes across a foe anthill will stop and
  stick around until it gets surrounded by foes. This aims to lock
  the foes supply of food to the hill. I tried using stickers to
  throw some of the food in the enemy anthill outside, but it didn't
  work too well. I didn't try too hard, though.

- Milkmen & guards: To avoid being prey to locking strategies such as
  the one described above, I implemented a variant of the sentinel
  scheme that I described in the lightning division description
  file. Here, a searcher that brings back food acts like a
  milkman. Instead of dropping the food at the anthill, it leaves the
  food "at the front porch" for the guards to pick up and put it in
  the anthill. In the case that the milkmen doesn't find a guard, it
  will become a guard himself. This strategy leaves the perimeter of
  the hill defended, but still allows the friend ants to leave food
  without much trouble. I tried to implement a more sophisticated
  scheme based on opening doors with communication through markers,
  but it turned out to be too complex.

- Chaser: a searcher will become a chaser whenever it finds an enemy
  ant. A chaser will simply try to stick by the enemy ant, in the
  hopes that other ants will follow and that the enemy ant will end
  up surrounded and killed. This was my only attempt at martial arts.

The first ant I'm submitting has all the behaviors described above,
and the second one doesn't use the milkmen & guards scheme. The
milkmen & guards scheme may be unnecessary (and wasteful of searcher
ants) if the strategies of other people do not include anthill
blocking.

Other strategies besides sentinels that I implemented that also turned
out not to work too well were door-knocking ants and spiraler
ants. The spiraler ants would exaustively search around the anthill in
order to quickly seize any nearby food blobs. Since they didn't work
significantly better than the searcher/follower scheme, and they took
an enormous amount of states (approximately 6000 after optimizations),
I decided to simply leave this role out. The door-knocking ants was
an overly complex attempt at the same result that the milkmen &
guards roles had, but with much more complex mechanisms that didn't
work at all.

The most interesting thing about my searching strategy has to do with
the marks. Instead of using marks for different purposes, I used all
of the marks in the same way: to establish a hopefully ordered bread
crumble path. Using only one kind of marker to get the way to the
anthills is not good enough, because it can become hard to know the
right direction when you have crossing paths, for example. My strategy
is to use all 6 markers, and when an ant is not holding any food
(ie. it is searching for food, and getting away from the anthill), it
marks the areas with increasing numbers: 0, 1, 2, 3, 4, 5, ... When
the ant is holding food, it looks for a marker, and then tries to find
the previous number, thus going in the direction of the anthill. This
proved to be an effective way to get back home safely. 

Ideas that remained to be implemented:

- Some kind of evolutive process (even if it meant just tweaking the
  relative role populations)

- More aggressive martial arts

- Exploring the space "by layers": Trying to use markers to define an
  approximate distance field to the anthill, so that the return home
  would be as fast as possible. There's not enough markers to set all
  possible distance values, but a scheme similar to the ordering I
  used would have a chance of working.

- A special way to signal a path to the enemy anthill, since it is
  most likely the most concentrated blob of food (besides my own
  anthill). if the foe does not employ protection techniques, this
  could be a quick way of robbing it blind.


Thanks for, once again, coming up with a great task!

-carlos