[m-dev.] ICFP Contest

[Ralph Becket]

My thoughts for a strategy:

(1) "ink blot" the route from the finishing line until we hit the car,
assigning higher "distances" to points on the track that take longer for
the ink blot to reach.

- We could consider the finishing line a special kind of impenetrable
  barrier and start the ink blot to its left - this should discourage
  the search from examining paths that cross the finishing line from the
  right.

(2) use depth-limited non-deterministic search at each time step to find
the next move by considering the next several moves; the car attempts to
follow the "distance gradient" down to the finishing line.

- Crossing the finishing line will require a little more care since the
  finishing line forms a valley in the distance gradient map.

- We could experiment with beam search - namely, breadth first search
  limited to examining a fixed number of vertices where only the top N
  branches are retained for consideration at each step.  This would
  improve the search depth at the cost of sacrificing optimality.

COMPLICATIONS

It takes 2730 time steps to accelerate from zero to crossing one square
per time step, the car's speed limit.  It takes 1820 time steps to brake
to zero from this speed.  So approaching the speed limit is going to
lead to a crash!

One thought is that we could plot ahead what would happen if we just did
the same thing (accelerating, turning, accelerating and turning etc.)
for the next N time steps and pick the best option there.  Hmm, I think
we're going to have to experiment with several strategies.  Either way,
the fact that the car's top speed should be (considerably) less than
one square per time step makes things a little more complex.

FIRST STEPS

- Write a fixed-point library.
- Write code to read in the track format (we could represent tracks
  efficiently as either array(string) or bitmap plus some data for the
  start and the finishing line.
- Write code to simulate the car (I'm not sure we'll need to worry about
  the skidding stuff, but that shouldn't be too hard to add later.)
- Write code to inkblot the track.
- Write a very simple search mechanism to get us started.

Any opinions?  I won't be able to do much work on this one until
tomorrow, but it looks fairly straightforward.

-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------