simulator (Re: [Icfp04-discuss] three liberal arts)

[Jack Diederich]

Zsban Ambrus ambrus at math.bme.hu
Wed Jun 9 12:00:11 EDT 2004
> On Wed, Jun 09, 2004 at 01:40:14AM +0200, Laurent Desnogues wrote:
> > Jed Davis wrote:
> > 
> > Some gain could come by encoding the map as a one-
> > dimensional array so that direction selection is
> > just loading an offset instead of switching and
> > computing x and y.  Since the border of the world
> > is rocky, you can't get wrong using offsets.

> I would be really interesetd about how the combat rules could be done fast. 
> As implemented in the pseudocode I belive it might be too slow.  It might
> help much as I think it is executed a lot of times.
>
> Two things that might help are 1. change the coordinate system so that the
> adjacent_cell function could be as simple as adding one of the vectors
> [1,0], [1,1], [0,1], [-1,0], [-1,-1], [0,-1]; or 2. calculating the number
> of neighbours short-circuitting, that is, if you see two cells which does
> not have red ants, than it's impossible that there are 5 red ants in the 6
> cells. I didn't do any of these optimizations.
>
> (My simulator was very slow, I think it might have been the slowest out of
> all, as I wrote it in ruby.  Also, I was stupid and used a slow machine. 
> See "mailto:icfp04-discuss at lists.seas.upenn.edu")

My C version of Board looks like
  typedef struct {
    int stepped;
    int width;
    int height;
    Space *board; // (x,y) is at board[y*width + x]
    int ant_count;
    Ant *ants; // ant id 7 is at ants[7]
  } Board;

typedef struct myspace{
  Point pos;
  Ant *ant;
  space_type type; // ROCK|CLEAR|RED_HOME|BLACK_HOME
  int food;
  unsigned char redmark;
  unsigned char blackmark;
  struct myspace *neigh[6]; // eg neigh[ant.dir] == 'Ahead'
} Space;

So during board initialization each space calculates a pointer to it's neighbors
for dirs 0,1,2,3,4,5.  It also makes it quick to move ants, space->neigh[ant->dir]
is where to test for move, sense, et al.
The Space->ant pointer is either NULL, or a pointer into the Board->ants array.
This runs TWO full rounds in 1 second (switching red/black) on an Athlon 1.8GHz.
My dead ant check isn't smart, it tries HERE and all six neighbors on each successful
move.  Plenty fast without getting tricky.

I did this the day _after_ the competition ended.  My simulator for the actual
competition was in pure python and took 30+ seconds per full round.  The C based
program & board are wrapped in a python wrapper so they are drop-in replacements
for the original pure-python versions.

-Jack

http://performancedrivers.com/icfp2004/