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

[Christophe Poucet]

On Thu, 2004-06-10 at 10:32, Jack Diederich wrote:
We had two simulators.  One written in c++ and one written in ocaml.
In the end the c++ version even linked to the instruction/behaviour ADTs
in ocaml so we could easily insert and remove, replace instructions in
behaviours.  The c++ version took 1.5-2s on an athlon 1700xp+, the ocaml
one took about 4-5 seconds on the same computer.
For the ocaml one I pretty much used the code from the paper, except
that I kept an array of ants indexable by id (None | Some ant) and had a
double array (matrix) for the board.

-Christophe 
> 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/
> 
> _______________________________________________
> Icfp04-discuss mailing list
> Icfp04-discuss at lists.seas.upenn.edu
> http://lists.seas.upenn.edu/mailman/listinfo/icfp04-discuss
>