Thread Subject:

MATLAB Programming Contest: May 11-18, 2005

The next MATLAB Programming Contest will start tomorrow at 9 a.m. EST
and run through Wednesday, May 18 at 5 p.m. EST. Topics and rules
will be posted on the morning of the contest:
 
 <http://www.mathworks.com/contest/>
 
As in recent contests, there will be three stages, darkness,
twilight, and daylight. During darkness, both the code and scores for
all entries will be hidden. In twilight, the scores will be visible
but the code will still be hidden. When daylight arrives, all scores
and code are visible. We'll also be holding several mid-contest prize
giveaways of MATLAB jackets, caps, and other good stuff, so don't
wait until the last minute to participate.
 
Please use this thread to talk about the contest, strategies, or to
ask related questions. If you have an "administrative" type of
question that you don't feel applies to anyone else, e-mail us at
contest@mathworks.com.
 
We look forward to seeing your entry. Good luck!
 
- The MATLAB Contest Team -

No testsuit yet.

Is it possible to have multiple ants and anthills?

Laszlo

Is there an easy way to check that an entry does not contain any
toolbox functions?

Laszlo Sragner wrote:
>
>
> No testsuit yet.
>
> Is it possible to have multiple ants and anthills?
>
> Laszlo

The testsuite is here:

 <http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=7621>

Nick Howe wrote:
>
>
> Is there an easy way to check that an entry does not contain any
> toolbox functions?
one way is starting with no functions in memory (clear mex), run the
function and call "inmem". Then you can call for any function
(possible in a loop) and ask "which(f{i})" where f is the output of
inmem.
From that location, you can check if the code is in a toolbox.
Maybe it is better to remove all toolbox-paths from the path(?).

There are other possibilities...

Stijn

Another question: I do not see any specific prohibition in the
rules, but the problem description implies that use of global
variables is not allowed. Is that correct?

Is it possible to see which ants are carrying food within the local
viewpoint? Or do we simply see ants and cubes without any information
as to whether or not those cubes are being carried? Or when a cube is
carried does it disappear from the sugar cube map?

Ed

In the text it is stated that any number of ants are possible. But
in "antMap" it is stated "shown as 1". Is that map only having zeros
and ones, or has it the number of ants?
I suppose so, but....

Stijn
(just to be sure)

Nick, you've got the right idea about global variables. I added this
to the rules section:

"You're not allowed to explicitly pass information from one ant to
the next through the use of programming techniques, like persistent
variables, global variables, or similar. The challenge in this
contest is to find ways to externalize information using smell or the
like."

If there are multiple ants on one "field", and some food. As I
understand, the time steps are done "in parallel" for the ants (or am
I wrong), I didn't check runcontest (yet).
(I thought that when reading in the scentMap-info "all ants get
....".)
How is it possible to know which ant can pick food?

Stijn

Download the testsuit, there is the runcontest.m function which is
used for the evaluation of the solver. I think from this that the
sugar is moving with the ant, and You can see it.

But the ants are not takeing up the sugar. Just moving them, so they
can stop moving it and an other can move it further.

The main problem I think is how to locate the anthills and how to
inform the other ants about finding it. The other question is if an
ant finds a big sugarfield how to inform the others to bring them
closer to the anthill.

I think one solution is to command the ants to walk randomly till
they found an anthill or a sugarfield and then start to leave
definite scents according to the relative location. So if the ant
moves East from a Sugarfield then leave a scent that
"Sugarfield_West".

But while it can see the scent what it leaves in the last two steps
with the appropriate coding it is possible to remember the exact
relative coordinates of the field.

Laszlo

Ed Manlove wrote:
>
>
> Is it possible to see which ants are carrying food within the local
> viewpoint? Or do we simply see ants and cubes without any
> information
> as to whether or not those cubes are being carried? Or when a cube
> is
> carried does it disappear from the sugar cube map?
>
> Ed

Can we rely that the total "field" is bounded by rocks? Or can an
ant get lost totally. (I don't see this possibility in the
runcontest, so I suppose it is.)

Stijn

Stijn Helsen wrote:
>
>
> Can we rely that the total "field" is bounded by rocks? Or can an
> ant get lost totally. (I don't see this possibility in the
> runcontest, so I suppose it is.)
>
> Stijn

I think it does not count.

If an ant has no information about the whereabout of the anthill
better not to do anything. But for example an ant can leave a message
on one side of the wall where is the anthill and the ants can bring
the sugars closer despite they do not have access to it.

Laszlo

Laszlo,

Remember that there is no memory (per say) between turns so an ant
simply can't sit there and watch to see that a particular cube is
being carried.

As for a starting solution I am thinking of a big switch statement
along the lines of

if not carrying food and if I see ...

  nothing - move in a random diagonally position and leave a trail
  trail - follow it
  food - go towards it
  
but if I am carring food ...
  anthill - go towards it and leave trail

Of course this is oversimplified (with some contradictions) but it
was where I was thinking of starting.

Ed

Laszlo Sragner wrote:
>
>
> Download the testsuit, there is the runcontest.m function which is
> used for the evaluation of the solver. I think from this that the
> sugar is moving with the ant, and You can see it.
>
> But the ants are not takeing up the sugar. Just moving them, so
> they
> can stop moving it and an other can move it further.
>
> The main problem I think is how to locate the anthills and how to
> inform the other ants about finding it. The other question is if an
> ant finds a big sugarfield how to inform the others to bring them
> closer to the anthill.
>
> I think one solution is to command the ants to walk randomly till
> they found an anthill or a sugarfield and then start to leave
> definite scents according to the relative location. So if the ant
> moves East from a Sugarfield then leave a scent that
> "Sugarfield_West".
>
> But while it can see the scent what it leaves in the last two steps
> with the appropriate coding it is possible to remember the exact
> relative coordinates of the field.
>
> Laszlo
>

freeants=ant-food>0
freefood=food-ant>0

I think it is obvious that an ant always carrying a food with what it
is on the same location.

Laszlo

.

Ed Manlove wrote:
>
>
> Laszlo,
>
> Remember that there is no memory (per say) between turns so an ant
> simply can't sit there and watch to see that a particular cube is
> being carried.
>
>

It would be better to stop running through the code if in one
timestep no ant has moved. That means that the following steps
nothing will happen either....

Ok, an aside. As I was thinking about my pseudo solution description
below, I thought back to some reasearch in "Literate Programing" and
how it could be used with this contest. For those who don't know what
"Literate Programming" is, it is a convergance of "explanatory text
... with code" [1]. In other words you write both code and the
documentation of that code within one source. Then using various
tools you compile the documentation into let say a pdf document and
the code into an executable source from the single source. A perfect
example and description of "Literate Programming" is [1].

Now those who are familar with the MathWorks products will
immediately think about the HTML publishing capabilities within
MATLAB and the seperate MATLAB Report Generator product. I am not
familar with these either these tools or built-in functionality but I
would be interested in how users might use them in the context of the
contest.

It would be interesting to see people post, submitt, or otherwise
publish some "Literate Programming" contest entries explaining what
they are doing and why. There could be even a sub contest for such
entries.

Ed Manlove

[1] "Catherdrals, Bazaars, and News Readers" Jeffery Copeland and
Jeffery Haemer, SunExpert Magazine, July 1998.
 <http://www.literateprogramming.com/sejul98.pdf>
 <http://alumnus.caltech.edu/~copeland/work/thread.html>

Ed Manlove wrote:
>
>
> Laszlo,
>
[SNIP]
>
> As for a starting solution I am thinking of a big switch statement
> along the lines of
>
> if not carrying food and if I see ...
>
> nothing - move in a random diagonally position and leave a trail
> trail - follow it
> food - go towards it
>
> but if I am carring food ...
> anthill - go towards it and leave trail
>
> Of course this is oversimplified (with some contradictions) but it
> was where I was thinking of starting.
>
> Ed
>
[SNIP]

Laszlo,

Not necessarily! Think of the situation where there are ants and
food as shown here

foodMap = [ . . 1 . . ]
          [ . . . . . ]
          [ . . . . . ]
          [ . . . . . ]
          [ . . . . . ]

 antMap = [ . . 1 . . ]
          [ . . . . . ]
          [ . . 1 . . ]
          [ . . . . . ]
          [ . . . . . ]

If you assume that ant on top is carrying the food and the contest
algorithm you design has a rule which states that all ants should
move away from those carrying food (assuming again that we say the
ant on top is carrying that food) then you would move down. But what
if the ant on top is not carrying that food and is seeing

foodMap = [ 9 9 9 9 9 ]
          [ 9 9 9 9 9 ]
          [ 9 9 9 9 9 ]
          [ . . . . . ]
          [ . . . . . ]

then you just missed the BIG PINIC! Yes, of course there is a lot of
other factors in this but...

the moral of the story is don't make assumptions on the base rules.

(Note to simplify our algorithm we could make general statments like
"ants in same square as food are assumed to be carrying that food"
but these are generalizations created but not a fundamental truth).

Ed

Laszlo Sragner wrote:
>
>
> freeants=ant-food>0
> freefood=food-ant>0
>
> I think it is obvious that an ant always carrying a food with what
> it
> is on the same location.
>
> Laszlo
>

Ed Manlove wrote:

> It would be interesting to see people post, submitt, or otherwise
> publish some "Literate Programming" contest entries explaining what
> they are doing and why. There could be even a sub contest for such
> entries.

Perhaps not as interesting as you might think -- submissions are
restricted to 65535 *characters*, so while I'm a big fan of Literate
Programming, I would probably opt out of it for this contest -- at
least until I had my code working!

Cheers,
Phil Mendelsohn

Dept. of Mathematics
U. of Mantioba

Phil,

I not suggesting that contest entries be submitted or forced to be
submitted through some literate programing source code but a seperate
side contest take place.

One reason for sharing ideas, code, etc. through the use of literate
program is to better communicate those ideas and sample code or
algorithms in an easily readable format.

People could submit there examples of MATLAB contest related literate
Programming examples to the MATLAB Central File Exchange server.

Since you mentioned your affection for Literate Programming do you
have any examples that involve MATLAB code that others can see what
we are talking about?

Ed

Phil Mendelsohn wrote:
>
>
> Perhaps not as interesting as you might think -- submissions are
> restricted to 65535 *characters*, so while I'm a big fan of
> Literate
> Programming, I would probably opt out of it for this contest -- at
> least until I had my code working!
>
> Cheers,
> Phil Mendelsohn
>
> Dept. of Mathematics
> U. of Mantioba

I found a problem with the runcontest.m file:

quote start

            % move ant
            locs(antCtr,:)=[ny nx];
    -----> ants(y,x) = ants(y,x) -1; <-----
            ants(ny,nx) = ants(ny,nx)+1;

quote end
The marked line enables the ant matrix to have negative values.
It should be changed to:
ants(y,x) = max(0,ants(y,x) -1);

Yuval

Nick Howe wrote:
>
>
> Is there an easy way to check that an entry does not contain any
> toolbox functions?

You can use pathtool and remove path to toolboxes. do not save for
future use.

Hope this works

rungun

I don't think it is a bug. old place one less, new place one more.
If nx==x and ny==y then that place is incremented and decremented,
so no change.
it is OK

Yuval Cohen wrote:
>
>
> I found a problem with the runcontest.m file:
>
> quote start
>
> % move ant
> locs(antCtr,:)=[ny nx];
> -----> ants(y,x) = ants(y,x) -1; <-----
> ants(ny,nx) = ants(ny,nx)+1;
>
> quote end
> The marked line enables the ant matrix to have negative values.
> It should be changed to:
> ants(y,x) = max(0,ants(y,x) -1);
>
> Yuval

Stijn Helsen wrote:
>
>
> It would be better to stop running through the code if in one
> timestep no ant has moved. That means that the following steps
> nothing will happen either....
Or stop when no further optimisation is possible...

Are ants allowed to move diagonally?

so dx=1 dy=1

?

brian

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start tomorrow at 9 a.m.
> EST
> and run through Wednesday, May 18 at 5 p.m. EST. Topics and rules
> will be posted on the morning of the contest:
>
> <http://www.mathworks.com/contest/>
>
> As in recent contests, there will be three stages, darkness,
> twilight, and daylight. During darkness, both the code and scores
> for
> all entries will be hidden. In twilight, the scores will be visible
> but the code will still be hidden. When daylight arrives, all
> scores
> and code are visible. We'll also be holding several mid-contest
> prize
> giveaways of MATLAB jackets, caps, and other good stuff, so don't
> wait until the last minute to participate.
>
> Please use this thread to talk about the contest, strategies, or to
> ask related questions. If you have an "administrative" type of
> question that you don't feel applies to anyone else, e-mail us at
> contest@mathworks.com.
>
> We look forward to seeing your entry. Good luck!
>
> - The MATLAB Contest Team -

brian wrote:
>
>
> Are ants allowed to move diagonally?
Yes. (written in the Rules)

Anybody know an easy soultion to detect wether a location on the
minimap is blocked by rocks or not?

Of course the location should be on the boarder of the minimap.

Laszlo

Laszlo,

You might try out a maze routing algorithm. See <http://foghorn.cadlab.lafayette.edu/cadapplets/MazeRouter.html>
or an example. And in this case instead of a diamond patern you could
use a square pattern.

Ed

Laszlo Sragner wrote:
>
>
> Anybody know an easy soultion to detect wether a location on the
> minimap is blocked by rocks or not?
>
> Of course the location should be on the boarder of the minimap.
>
> Laszlo

Is the scoring computer really 16 hours behind? If so, it seems
we'll find out the overall contest winner in a few weeks, since it
just gets worse in daylight. It would be interesting though to go
through a few days of "daylight" before anyone knew who won the
"twilight" phase. We wouldn't know who to tweak!

Mike Bindschadler wrote:
> Is the scoring computer really 16 hours behind? If so, it seems
> we'll find out the overall contest winner in a few weeks, since it
> just gets worse in daylight. It would be interesting though to go
> through a few days of "daylight" before anyone knew who won the
> "twilight" phase. We wouldn't know who to tweak!

It seems they started the queue processing just when the darkness
ended.
jan

The queue backup is my fault. I noticed a potential problem this
morning and had to re-score all the entries for consistency. I
expect the queue to be caught up by the end of the day (a few more
hours). I'm sorry about the wait.

Matthew Simoneau wrote:
> The queue backup is my fault. I noticed a potential problem this
> morning and had to re-score all the entries for consistency. I
> expect the queue to be caught up by the end of the day (a few more
> hours). I'm sorry about the wait.

got the queue stuck again? there appears to be no progress over the
past half hour.
jan

jan, the queue has been processing non-stop, but we were having a
problem updating the web pages with the results.

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start ...

By my calculation, the scoring constants are

k1 = 0.1
k2 = exp(-9)
k3 = 0.1

Hi all

There is a huge discrepancy between the timing result I get for my
entry Zee on my PC and what it scores on the server. On my PC this
entry runs WAY faster than anything else I've submitted. The runtimes
of my previous entries were almost the same as what I got for them on
my own PC, but Zee deteriorates from 60s to 170s. I'm running on
Matlab 6.5.1. release 13. Any ideas?

Thanks
Cobus Potgieter

Folks,
 
I have a question - I am not sure if this answered in the rules
 
Can I make the following assumption at the beginning of any new
testsuite? It does help to write the solver.
 
1. No ant will on food
2. No ant will on home
3. No any will on another ant
 
thanks
 
rungun

Rungun Nathan:

hi, as for your question, I think:

> 1. No ant will on food
     no correct.
> 2. No ant will on home
     no correct.
> 3. No any(t?) will on another ant
     maybe right.

Compared with the former contest, the contest of this time has a
different style. In my entry, I can't take advantage of the scent
very well. Too many scent is trival and no use. How to mark?But I
think we should code an entry based on the scent.
oh, I need go to sheep:)

Jin

Cobus Potgieter wrote:
>
>
> Hi all
>
> There is a huge discrepancy between the timing result I get for my
> entry Zee on my PC and what it scores on the server. On my PC this
> entry runs WAY faster than anything else I've submitted. The
> runtimes
> of my previous entries were almost the same as what I got for them
> on
> my own PC, but Zee deteriorates from 60s to 170s. I'm running on
> Matlab 6.5.1. release 13. Any ideas?
>
> Thanks
> Cobus Potgieter

Your algorithm takes longer to finish on some testcase found on the
sever (stuck in a loop maybe?). Just my guess...

/Christian

It is always humbling when daylight dawns and you see all the good
ideas that others thought of when you couldn't think of any other way
to do it.
I just watched some of the top entries - BUGFIX, bedlam, and my own,
and they each look different in style. (Sadly, the style of my own
entry was not as successful. :-)

That brings me to my main point, however: Given the use of random
numbers in most of the solutions, there is even more variability in
the scoring than is usual from timing discrepancies. On the test
case, my results can vary by as much as 20% between runs of the same
code. I predict a free-for-all at the end of the contest, with
everyone trying to submit a version of whatever code is at the top
then. The result will be more like a lottery than a programming
contest.

Don't get me wrong; I have had a marvelous time working on this
project. Thanks to all the folks at Mathworks for making it happen!

Nick Howe wrote:
>
>
> It is always humbling when daylight dawns and you see all the good
> ideas that others thought of when you couldn't think of any other
> way
> to do it.
> I just watched some of the top entries - BUGFIX, bedlam, and my
> own,
> and they each look different in style. (Sadly, the style of my own
> entry was not as successful. :-)
>

I had the same experience :) Watching the FoodTrain is pretty
impressive. Congrats to the Zee team!

One idea I had that I haven't seen in any of the top entries and
probably won't have any more time to try to implement myself is that
there should be a way to implement scent patterns which lead TO food
and not just back to anthills. There are several ways one might do
this, here are a few I've started work on, but won't finish.
1)Information and directionality in trails can be encoded in the
differences between adjacent values along the trail. For example, a
trail leading back to an anthill might be created by an ant leaving a
hill and laying down 100 scent each time. This would create a trail
which decreases by one in the direction of the hill, so an ant seeing
a scented patch with an adjacent scented patch which was one less
would know that an anthill lies in that direction and could follow
that path back. OK, so a -1 difference means towards an anthill and
+1 means away from an anthill on that trail. A different kind of
trail could be created by an ant which has seen more food that it can
carry, and therefore wants to communicate that to other ants. If
such an ant alternates between laying a scent of 96 and 99, the
resulting trail will have differences of 4 and -2 in the direction of
the food, and differences of -4 and 2 away from the food. As long as
they don't cross, these two trail types could coexist freely,
broadcasting information about the location of hills AND food more
widely than they can be seen. These marked trails can carry
information over time because the *differences* are persistent even
though the scent values are decaying. An ant which has no food looks
for a trail leading to food and an ant which has food looks for a
trail leading to a hill.
2. A different idea would be to encode these two networks in the
spatial patterning of scented squares. For example, if food has
been seen in an area but it is not connected to the general gradient
leading back to the anthill, that area could be set up with a
checkered pattern of scented squares. It's easy to set this up, you
just determine the marking level as you would for leading back to the
nest, but you set the marking level to 0 if any of your 4-connected
neighbors are scented. Now, if you are an ant with no food, you
follow the checkered gradient up to food, then back down to the
non-checkered gradient which you follow up to get back to the nest.

I tried the directional trail one the most, and if anyone wants to
pursue it, I have some functions which might be useful (for example,
one which can decompose any scent-map into various trail types with
specified differences and with directional information), just drop me
an email and I'd be happy to send them to you.

-Mike

Nick Howe wrote:

> code. I predict a free-for-all at the end of the contest, with
> everyone trying to submit a version of whatever code is at the top
> then. The result will be more like a lottery than a programming
> contest.

I've no doubt that the winner will be using < 1% original code but
for the algorythm to get much stronger, the randomness will have to
be removed. My prediction is that the next big jump in score will be
when the random bits are replaced my better search code.

The team of Hannes Naudé & Cobus Potgieter won the Twilight phase of
the contest with their entry "BUGFIX". (Is that title a pun?) They
developed their entry without being able to see anyone else's work.
We have a MATLAB cap for each of them, but they'll have to share
their spot in the Hall of Fame.

The other top performers in Darkness and Twilight were Nick Howe, Jan
Langer, and Stijn Helsen.

Chief challenge developer Lucio Cetto, with some help from Ned
Gulley, created a Mid-Contest Analysis. It examines some of the
algorithmic developments that have happened so far.

Daylight has now begun and the code is open to everyone. The next
mid-contest prize is the ever-popular Big Sunday Push. We award it to
the contestant who makes the biggest cumulative improvement to the
top score over the course of Sunday, as measured on the Statistics
page. Be sure to fill out your name exactly the same for all your
entries so we can accurately tally your total contribution (the
Google Toolbar can help with this).

Does anyone know where I can find instructions for adding maps to my
test suite?

Tom Lemke wrote:
>
>
> Does anyone know where I can find instructions for adding maps to
> my
> test suite?
I work with an additional input to the runcontest-function. There I
can give the number(s) in the testsuite, or I can give a structure,
which is used in place of the loaded testsuite.
I've also changed the loading of the testsuite. I've used a global
variable. If that is not empty I use that, otherwise I load the
testsuite. Of course, I had to remove the line "clear global". But
since I'm not using globals, it doesn't influence the result.

Does this help?

The results of the same codes (in different times) are equal. That
means that there is some "random-seed-number-resetting" in the
testing of the codes. (I have done that in my runcontest-routine
too.)

So, of course there is a big inpact on the test-suite, with some luck
(or not). But copying code, without change, can't give you a sudden
improvement...

Stijn

Nick Howe wrote:
> That brings me to my main point, however: Given the use of random
> numbers in most of the solutions, there is even more variability in
> ....

Actually, I know so little about MATLAB that I'm fishing for the
explicit details to viewing the contents of the mat file, making my
own maps, and shoving them into the mat file with the others.

> I work with an additional input to the runcontest-function. There
> I
> can give the number(s) in the testsuite, or I can give a structure,
> which is used in place of the loaded testsuite.
> I've also changed the loading of the testsuite. I've used a global
> variable. If that is not empty I use that, otherwise I load the
> testsuite. Of course, I had to remove the line "clear global".
> But
> since I'm not using globals, it doesn't influence the result.
>
> Does this help?

Matthew Simoneau wrote:

> The next
> mid-contest prize is the ever-popular Big Sunday Push.

Maybe I misunderstand something, but Timothy Alderson's TLL127 seems
to have gotten far too much credit in the Big Sunday Push.

the cyclist wrote:
>
>
> Matthew Simoneau wrote:
>
>> The next
>> mid-contest prize is the ever-popular Big Sunday Push.
>
> Maybe I misunderstand something, but Timothy Alderson's TLL127
> seems
> to have gotten far too much credit in the Big Sunday Push.

This seems rather petty, now that our tweaking has been crushed by
genuine algorithmic improvements!

It's fun to see how the bucket brigade strategy mops the floor so
well. However, it's not always ideal. On open fields with no rocks,
the simple food gradients seem to work better than the bucket
brigade. For example, try map 10 from the example suite. On average,
the brigade tends to score around 1100 - 1200. My measly gradient
code, however, tends to score around 400 - 500 with as low as 200.
And my code is still buggy and inefficient!
 
Has anyone else noticed this? Perhaps there's a way to capitalize on
this and mix the two strategies somehow.

cyclist, I took a look at the credit we gave TLL127 for the Sunday
Push. It looks like your entry "nq8 a" was on top with a score of
2218 until Timothy Alderson's "TLL127" bumped it off with a score of
2205, for a difference of 13. Let me know if I'm missing something.

To better track how the lead is changing, I added an "All the
Leaders" section to the Statistics page.

Jan Langer is the winner of Big Sunday Push. We award this prize to
the contestant who makes the biggest cumulative improvement to the
top score over the course of Sunday. Other big movers on Sunday were
Timothy Alderson, Tom Lemke, and nathan q. For the complete listing,
see the statistics.

In honor of Jan, winner of our last mid-contest prize, our next
mini-contest is called Midnight in Chemnitz. We'll award a prize for
the best entry submitted before midnight Chemnitz time (6PM EDT).

Matthew Simoneau wrote:
>
>
> cyclist, I took a look at the credit we gave TLL127 for the Sunday
> Push. It looks like your entry "nq8 a" was on top with a score of
> 2218 until Timothy Alderson's "TLL127" bumped it off with a score
> of
> 2205, for a difference of 13.

I see the misunderstanding I had. I was not looking at the
difference between his code my the former leader. Instead, I was
looking at the difference between his code and the second-place at a
later time. The new leader board makes that clear. Thanks.

Matthew Simoneau wrote:

> We'll award a prize
> for
> the best entry submitted before midnight Chemnitz time (6PM EDT).

Is that 6PM EDT on Monday?

Yes, that's 6PM EDT Moday, which is now about 3 hours away.

Hello All,
 
A colleague and I at Teachers College, Columbia University are
studying evolutionary dynamics in collective problem solving,
specifically the extent and intensity with which concepts emerge,
diversify, persist, and converge upon multiple, viable solutions. The
MATLAB programming contests offer a microcosmic view of how these
dynamics play out on the organizational and, possibly, global scales.
 
The current contest seems especially applicable, in a metaphorical
sense, to our study. Thus, while we have yet to design a proper
survey, I could not resist introducing our intentions and throwing
out a few informal and exploratory questions. I would love to know:
 
1. your background and experience with MATLAB;
 
2. what motivated your participation;
 
3. your impressions of wiki-style collaboration (in general);
 
4. and whether and to what extent you perceive that collective
dynamics yield the best/most-satisfactory solution?
 
Thank you for your help,
 
John

Timing is inaccurate again. After doing some trials with timing
improvements that didn't work, I did a test with the currently
winning entry (midnight push).
 That entry had a CPU timing of 80.07, while two copies of it had
81.94 and 82.14 seconds. This is high (again).

So, you have to be lucky if you only try to do timing optimisations.
This is especially true in this contest where "smart programs" get
quickly too slow.
Therefore it is also a pitty that the running of the program is done
just 1000 times for each testcase. If the calculation was stopped if
"all food was gone", then you gained something extra by solving a
case quickly.
In that case you could have better timing by better programs, even if
the the program itself is slower.

"""But then.... you needed a super-ant to call all ants to stop
working....."""

Stijn

Stijn Helsen :

      hi,Stijin. About the timing, I have the same feeling like
yours. And I have another question. That is, why the statement of
"rand(1,5);" without any assignment works well for the leading
entries? Is it really useful? Is the contest server wrong, or am I
wrong? Or is this statement very tricky? Thanks for reply,first:)

Jin

Jin wrote:
> And I have another question. That is, why the statement of
> "rand(1,5);" without any assignment works well for the leading
> entries? Is it really useful? Is the contest server wrong, or am I
> wrong? Or is this statement very tricky? Thanks for reply,first:)
>
> Jin

That's a "magic trick" used in other contests too in solutions where
random numbers are used. That statement does nothing to the
algorithm, except that it changes the random numbers that the program
gets.
So, clearly in the current solution, the use of 5 random numbers in
every call gives more "lucky choices" than others.
That is also a reason why it is possible that improving the algorithm
gives a worse result, just because you get less "lucky choices".
Maybe that program needs other "random-number-order-change-lines".
(maybe something like rand(ceil(rand*4)))

Stijn

Stijn Helsen:

    Thanks, Stijn!It's magic!This trick makes the random more "not
random":) Thanks again:)

Jin

Stijn Helsen wrote:
>
>
> Timing is inaccurate again. After doing some trials with timing
> improvements that didn't work, I did a test with the currently
> winning entry (midnight push).
> That entry had a CPU timing of 80.07, while two copies of it had
> 81.94 and 82.14 seconds. This is high (again).
>
> So, you have to be lucky if you only try to do timing
> optimisations.
> This is especially true in this contest where "smart programs" get
> quickly too slow.
> Therefore it is also a pitty that the running of the program is
> done
> just 1000 times for each testcase. If the calculation was stopped
> if
> "all food was gone", then you gained something extra by solving a
> case quickly.
> In that case you could have better timing by better programs, even
> if
> the the program itself is slower.
>
> """But then.... you needed a super-ant to call all ants to stop
> working....."""

I did some similar timing analysis, and I also found variations of up
to about 2.4 seconds for identical submissions. Frustrating for us
tweakers!

One minor improvement to prevent sniping of code near the deadlines
would be to only allow code to be visible after the entry had been
scored, rather than immediately after submission. (You would also
need to disallow "blind" resubmission until after scoring.) This
would allow participants to submit entries near the closing buzzer,
without fear that their entry will be duplicated. Maybe not quite in
the open-source spirit, though.

Niilo Sirola is the winner of our most recent mid-contest prize,
Midnight in Chemnitz. We awarded it for the best entry submitted
before midnight Chemnitz time (6PM EDT) on Monday. Congratulations!

It's about this time in the contest that discussion of timing
variability often arise. Even with very small timing variability,
which we're not even close to, resubmitting an entry has a 50% chance
of doing better the second time. Still, in general, we want to
reward contestants who make real improvements in efficiency, even if
the improvements are small.

Recognizing these limitations, however, let's take timing off the
table for a while. Our next mini-contest is the Three Minute
Challenge, a prize for the lowest result achieved between 12 PM and 8
PM EDT today (17 May). You get to use all three minutes before your
entry times out, and your CPU time will not be counted against you.
Any ties will be resolved by who gets to the lowest result first. To
track this mini-contest, refer to the statistics page. We'll send the
winner a MATLAB toolkit.

In TLL236 I change the following row:

mark=400-scent(13);

to

mark=401-scent(13);

It does not do anything but marks the cell near to the anthill with a
1 point larger scent. This is not a major change but the score
changes up by 1%. Is that means that TLL236 is a lucky one, and
changing it even a little loses this luck?

My idea was to completely clear the area around the hill to minimize
the movements without sugar (If the ant has a sugar and the anthill
is next to it, it is very easy to bring the sugar to the hill and
step back). Despite my expectations the method performs very badly.
But why? Anybody any ideas?

My other idea is to use some kind of neural method, is there anybody
who tried this? For example Temporal Difference or with a simple NN
using the previous algorithms results as input-output data.

Laszlo

> It's about this time in the contest that discussion of timing
> variability often arise. Even with very small timing variability,
> which we're not even close to, resubmitting an entry has a 50%
> chance
> of doing better the second time. Still, in general, we want to
> reward contestants who make real improvements in efficiency, even
> if
> the improvements are small.
When writing the comment, I new. I just "had to write it"....

> Recognizing these limitations, however, let's take timing off the
> table for a while. Our next mini-contest is the Three Minute
> Challenge, a prize for the lowest result achieved between 12 PM and
> 8
> PM EDT today (17 May). You get to use all three minutes before your
> entry times out, and your CPU time will not be counted against you.
> Any ties will be resolved by who gets to the lowest result first.
Nice idea, but I'm affraid that I've been focusing too much on
tweaking.... maybe....

When doing tests with other calculations, first with results that
should be the same, didn't give the same results. The cause is that
the loop to find "new food" is not correct. 'm' is not initialized
correctly.
But, ..., correcting it gives worse results....

Matthew Simoneau and others:

  Timing variability always exists. However, for a algorithm using
random methods, running the entries several times and taking the
average value of their results
 may be a better choice to evaluate the worth of a random algorithm .
A lucky random one could suppress the mirror improvement made by the
modified entries on the
average level:)
  So hard, so tired...

Jin

Jin wrote:
> Timing variability always exists. However, for a algorithm using
> random methods, running the entries several times and taking the
> average value of their results
> may be a better choice to evaluate the worth of a random algorithm
> .
> A lucky random one could suppress the mirror improvement made by
> the
> modified entries on the
> average level:)
> So hard, so tired...

I'm not sure this would help much. Yesterday I tried _a lot_ of other
magic numbers and the results never even got close to the current
score of 18500. The worst result was something like 23500 and I
wonder why the state of the random number generator can influence the
score to about 25%. On the other hand I wonder why I found the really
lucky number of 5 so quickly.

In my opinion it now becomes very difficult if not impossible to find
algorithmic improvements. Me and probably many others already found
some things improving the local testsuite score a little bit, but on
the real testsuite no improvement can be achieved.

But we will see. Maybe someone can come up with some great new
improvements.
jan

PS: Additionally, I would like to state that I am really impressed
how the collective effort has improved the timing of my butz benser
entry from 160seconds to 77seconds (Though it doesn't look as nice
anymore ;-)

Jan Langer wrote:
>
>
> Jin wrote:
> I'm not sure this would help much. Yesterday I tried _a lot_ of
> other
> magic numbers and the results never even got close to the current
> score of 18500. The worst result was something like 23500 and I
> wonder why the state of the random number generator can influence
> the
> score to about 25%. On the other hand I wonder why I found the
> really
> lucky number of 5 so quickly.
>
> In my opinion it now becomes very difficult if not impossible to
> find
> algorithmic improvements. Me and probably many others already found
> some things improving the local testsuite score a little bit, but
> on
> the real testsuite no improvement can be achieved.
I expect that there is a big testcase where the "lucky numbers" have
big impact. The gain in other cases are lost by one (or some) cases,
... I think.

I hope we get the full case this time. Last contest it was "said to
be given", but there didn't seem to be a difference between the
testsuite and the real suite, while there were other results....

Stijn

Is it possible that the luck depends on a very special test sample?

For example some kind of maze-like lab, where only one sugar is
hidden somewhere, and only one ant is present.

Laszlo

Laszlo Sragner wrote:
>
>
> Is it possible that the luck depends on a very special test sample?
>
> For example some kind of maze-like lab, where only one sugar is
> hidden somewhere, and only one ant is present.
>
> Laszlo
Could be, but I think that there are a lot of possibilities. For
example a separated "room" with food and another with hills. You
have to be lucky to find first a hill and then early enough some food
to go back. Only then you can start bringing the food in.
If there is a lot of food there, it can have big impact on the total
score.
(maybe score "zero" for each case should be set to the theoretical
minimal???)
Stijn

Jan Langer wrote:
>
> In my opinion it now becomes very difficult if not impossible to
find
> algorithmic improvements. Me and probably many others already found
> some things improving the local testsuite score a little bit, but
on
> the real testsuite no improvement can be achieved.

This time, I only watch the contest. But since it is so easy to get
an impression on how the algorithms work by using runcontest, I found
something where the leading entry wastes time. If it does not finish
a testcase, and moves food when time is over, this might be a way to
improve the score for the case.

The observation is that ants move towards solid walls when in search
mode, i.e. if they already know that there is no food and no further
movement possible in that direction. The next move then is either
backwards, or at an angle +-90 deg of backwards. This means that two
moves are wasted, because no new (or fewer than possible) tiles have
been observed. Example:

x impassable
a,b,c consecutive ant positions in open space
d,e possible other ant positions in open space
. open space

x....
x....
x.a..
xbde.
x.c..

The current algorithm often produces the a-b-c patterns, but an ant
at a can know already that a move to b is of no use, since d and e
are better in respect of the number of possible food locations
observed. An ant *can know* means that I have no idea how to code
this into the leading entry. Good luck if you want to give it a try!

Heinrich

Heinrich Acker wrote:
>
>
> Jan Langer wrote:
>>
>> In my opinion it now becomes very difficult if not impossible
to
> find
>> algorithmic improvements. Me and probably many others already
> found
>> some things improving the local testsuite score a little bit,
but
> on
>> the real testsuite no improvement can be achieved.
>
> This time, I only watch the contest. But since it is so easy to get
> an impression on how the algorithms work by using runcontest, I
> found
> something where the leading entry wastes time. If it does not
> finish
> a testcase, and moves food when time is over, this might be a way
> to
> improve the score for the case.
>
> The observation is that ants move towards solid walls when in
> search
> mode, i.e. if they already know that there is no food and no
> further
> movement possible in that direction. The next move then is either
> backwards, or at an angle +-90 deg of backwards. This means that
> two
> moves are wasted, because no new (or fewer than possible) tiles
> have
> been observed. Example:
>
> x impassable
> a,b,c consecutive ant positions in open space
> d,e possible other ant positions in open space
> . open space
>
> x....
> x....
> x.a..
> xbde.
> x.c..
>
> The current algorithm often produces the a-b-c patterns, but an ant
> at a can know already that a move to b is of no use, since d and e
> are better in respect of the number of possible food locations
> observed. An ant *can know* means that I have no idea how to code
> this into the leading entry. Good luck if you want to give it a
> try!
>
> Heinrich

    if BAD(6)&&BAD(11)&&BAD(16)
        BAD(12)=1;
    end
    if BAD(22)&&BAD(23)&&BAD(24)
        BAD(18)=1;
    end
    if BAD(10)&&BAD(15)&&BAD(20)
        BAD(14)=1;
    end
    if BAD(2)&&BAD(3)&&BAD(4)
        BAD(8)=1;
    end

I try this but I am not sure.

Laszlo

Laszlo Sragner wrote:
>
>
> Heinrich Acker wrote:
>>
>>
>> Jan Langer wrote:
>>>
>>> In my opinion it now becomes very difficult if not
impossible
> to
>> find
>>> algorithmic improvements. Me and probably many others
already
>> found
>>> some things improving the local testsuite score a little
bit,
> but
>> on
>>> the real testsuite no improvement can be achieved.
>>
>> This time, I only watch the contest. But since it is so easy to
> get
>> an impression on how the algorithms work by using runcontest, I
>> found
>> something where the leading entry wastes time. If it does not
>> finish
>> a testcase, and moves food when time is over, this might be a
way
>> to
>> improve the score for the case.
>>
>> The observation is that ants move towards solid walls when in
>> search
>> mode, i.e. if they already know that there is no food and no
>> further
>> movement possible in that direction. The next move then is
either
>> backwards, or at an angle +-90 deg of backwards. This means
that
>> two
>> moves are wasted, because no new (or fewer than possible) tiles
>> have
>> been observed. Example:
>>
>> x impassable
>> a,b,c consecutive ant positions in open space
>> d,e possible other ant positions in open space
>> . open space
>>
>> x....
>> x....
>> x.a..
>> xbde.
>> x.c..
>>
>> The current algorithm often produces the a-b-c patterns, but an
> ant
>> at a can know already that a move to b is of no use, since d
and
> e
>> are better in respect of the number of possible food locations
>> observed. An ant *can know* means that I have no idea how to
code
>> this into the leading entry. Good luck if you want to give it a
>> try!
>>
>> Heinrich
>
> if BAD(6)&&BAD(11)&&BAD(16)
> BAD(12)=1;
> end
> if BAD(22)&&BAD(23)&&BAD(24)
> BAD(18)=1;
> end
> if BAD(10)&&BAD(15)&&BAD(20)
> BAD(14)=1;
> end
> if BAD(2)&&BAD(3)&&BAD(4)
> BAD(8)=1;
> end
>
> I try this but I am not sure.
>
> Laszlo

Probably a better idea to use the 'if' sequence which updates the BAD
matrix to predict the discovered squares in the next step. How to
code it efficiently?

Laszlo

Timothy Alderson won our Three Minute Challenge with an entry
"TLL280", submitted only 13 seconds after the start. His entry
achieves a result of 18564, the level that Niilo Sirola first reached
with "poking at TLL166" more that 24 hours earlier (though it now
runs significantly faster).

It has been more than two days since anyone has been able to improve
on this result. From our inspection of how the current best entry
performs on the actual test suite, we're guessing that further
improvement to this already impressive algorithm is still possible.
Although there are several boards that the algorithm is able clear,
there are some that have accessible food remaining. The algorithm is
in a deep local minimum, where the random numbers and magic constants
used by the leading entry have been tuned so finely to the test suite
that any small change produces a significantly worse result. To
better this result may require both a significant algorithmic
improvement plus additional tuning.

To encourage innovation, we're offering two more prizes in addition
to the traditional contest winner. The first is the "Crack the Nut"
prize for the first entry to break through the current result
barrier. The second is the "Generality" prize. After the contest is
over, we will rescore all the entries against a different, but
similar in character, test suite. Hopefully this validation step
will pick out the entry that best solves the problem without being
over-fitted to the specific tests we used for the contest.

We're interested to hear your feedback about the character of this
contest. Why do you think entries in this contest have been
relatively short in length? How did that affect your enjoyment of
the contest? We think the tendency to fall into a deep local minimum
is directly related to the relatively small number of tests in this
test suite. Are there other factors that you've identified? Are
there aspects of this problem that made it harder or easier? Are
there problems or types of problems you can think of that avoid some
of the issues we've identified?

We look forward to your feedback and we hope you enjoy the rest of
the contest.

> We're interested to hear your feedback about the character of this
> contest. Why do you think entries in this contest have been
> relatively short in length?

Because it relies on only part of the data of each testcase. It is
impossible to combine 2 good algorithms into one as it was possible
in earlier contests.

  How did that affect your enjoyment of
> the contest?

First it was fun but it is not good to see that the last to day was
spent on timetunining and magic number searching. The problem is
challenging, and exciting even to watch the ants collecting the
sugar.

We think the tendency to fall into a deep local
> minimum
> is directly related to the relatively small number of tests in this
> test suite.

Probably You should give out the testcases what the leader can clean
and then we can blindly deal with the rest of the test suit.

anyway it was fun

Laszlo

Matthew Simoneau wrote:
>
> We're interested to hear your feedback about the character of this
> contest. Why do you think entries in this contest have been
> relatively short in length? How did that affect your enjoyment of
> the contest?

Of the contests I've seen, this has been the most enjoyable. The
problem is nice and the solutions are beautiful. When I first saw
BUGFIX in action it was hard to believe the ants didn't have some
global map (but then, I am not very bright). Because the local
problem is so compact, and there's no opportunity to try multiple
algorithms, the code has been a joy to work with. Also I like the
fact that timing isn't really an issue, at least in the sense that a
tiny result improvement at this stage would outweigh speed gains.

thanks Mathworks

Nathan

PS It seems that real ants do have some memory and long-range vision.
See, for example, <http://www.informatics.susx.ac.uk/users/paulgr/>

Matthew Simoneau wrote:

> To encourage innovation, we're offering two more prizes in addition
> to the traditional contest winner. The first is the "Crack the
> Nut"
> prize for the first entry to break through the current result
> barrier.

I would have bet that the "Crack the Nut" prize would never be
claimed. Congrats to JohanH!

Matthew Simoneau wrote:
> It has been more than two days since anyone has been able to
> improve
> on this result. From our inspection of how the current best entry
> performs on the actual test suite, we're guessing that further
> improvement to this already impressive algorithm is still possible.

Let's hope that someone finds it... (I think I will not try
anymore.)

> Why do you think entries in this contest have been
> relatively short in length?
I think it is clear. In the beginning of the contest (after the
"darker periods"), I was surprised to see long entries. I beleive
that the reason is that the program can't be sure if it is doing
good. And so, it can not choose well between different results.
Above that, now the well optimised code is taking 70 seconds. Some
complexer codes, which start not optimised don't solve it in 180
seconds. If you have than more than one algorithm and try to choose,
there is no time at all. So, a short entry is obvious, I beleive.

> How did that affect your enjoyment of
> the contest? We think the tendency to fall into a deep local
> minimum
> is directly related to the relatively small number of tests in this
> test suite.
I don't beleive this compeletely. I've written it earlier, and I
don't have the real suite, so I can't be sure, but I think that it is
with one or a couple of cases that are behaving well now, and behave
much worse in other situations (other "magic numbers").
I beleive that that is a reason. Maybe it is good to mension (again)
the difficult choice of combining the results of different cases.
Now it is just the sum. "Big cases" have then much effect. But,
remembering earlier remarks about this difficulty, I don't have a
better option (except my earlier given proposal of having "zero" for
the "theoritical minimum" (which can be an easy estimated underlimit)
(and that would improve it really, it would only give more feeling
about how much improvement could be possible...)).

I think that this problem together with a shorter contest would be
optimal. I'm too tired and too angry at myself because I'm spending
too much time on it while I have other things to do. Therefore I
tried to get it out of my mind, but because it didn't work I started
sometimes trying things, but with very bad programming techniques,
with more errors than lines of code.... (That is just my problem...)

Something that was also very good in this contest (you could also
dislike it), what that the tester of code was "flexible". The output
was tolerant to faults, or to things that were not possible. Trying
to carry food when there was nothing, trying to climb on a rock,
trying to move further away, it didn't give errors, it just did
something as close as possible to what was requested.
That was nice. Maybe the reason why it was nicest was that in
earlier contests, where the tester was less tolerant, some faults
were possible or were not tested. Then it was not nice that you
could have programs that didn't work on many testcases but did run
with the final testcase. Now it was just allowed, "officially".

> Are there aspects of this problem that made it harder or easier?
It is difficult to decide about what is harder or not. It was a
nice, easy to understand (and visualise), and still interesting
enough. I liked it.

> Are there problems or types of problems you can think of that avoid
> some of the issues we've identified?
I liked it. Many contests have some special characteristics. And
that is good. It is normal that "special characteristics" have
"special disadvantages", so I don't mind.

I liked it ((((but shorter would have been nicer)))).

Regards,
Stijn

I wanted to add one thing. I've written it earlier. But in my
"evaluation" I wanted to tell that stopping evaluating when all food
is gone, for example, than you would gain more.
Not just by getting a faster program, because with these CPU-times
the total score is not too much influenced, but you can spend more
time with algorithms.

Matthew Simoneau wrote:

>
> We're interested to hear your feedback about the character of this
> contest.
> We look forward to your feedback and we hope you enjoy the rest of
> the contest.

I didn't get much chance to participate this time, but I thought it
was a great one to think about and to watch. It's not ideal when the
best result stagnates at one number for too long, but I don't really
see a way to avoid it, and the Three-Minute, Crack The Nut, and
Generality prizes are all good attempts to foster innovation.
Overall, I think these contests are great, and I look forward to the
next one!

Mike

Matthew Simoneau wrote:

> The second is the "Generality" prize. After the contest
> is
> over, we will rescore all the entries against a different, but
> similar in character, test suite.

I hope that while rescoring the entries for the Generality prize, a
new "Top 20" listing (and maybe one or two of the more interesting
statistics graphs) will be kept active on the site. It will be
interesting to see how things develop over time, as compared to the
current suite of maps. (I estimate that it will take a few days to
do the rescoring.)

Every friends:

  The contest ended again:)The course is too short, and too long.The
reason of my saying 'short' is that the current leading entry may be
not a perfect solution obviously. The reason of my saying 'long' is
that no new breaking algorithm has benn submitted since the entry by
Hannes Naudé & Cobus Potgieter(or Jan Langer, not too sure).
  I also dived into the problem at the weekend, a weekend full of ML
and ants:) I find the problem is very hard for the local scope of
ants and just one controlable variable-scent. Until now, there are
two main algorithm: A. by scent but some randpm, such as 'bedlam'(I
have tweaked it, but it seem to be worse in offical testsiute);B. by
a building trail, such as the current leadeing entry.
  Aglorithm A is better than B under the condition of no inner wall,
such as testsuite data#3,#10 in the startet kit.
  ... some exception...can't continue...sorry.But the contest is
still impressive for me.

Jin

Jin wrote:
> I also dived into the problem at the weekend, a weekend full of
> ML
> and ants:) I find the problem is very hard for the local scope of
> ants and just one controlable variable-scent. Until now, there are
> two main algorithm: ....
I've tried something else with no result. I'm not sure that it was
because of bad programming or not. I tried to have two different
scent-ranges. The choice that I've tested most was low scent (below
s0 in some submissions) was "bad-position". Higher was good (and
zero was unknown). I've also tried the opposite. Very high is bad.
For that I've tried to stay a while if a bad position was found until
the score was really high.
But... it didn't work. And I wasn't convinced enough that it could
really work, so I didn't spend much time on it....

Stijn Helsen wrote:
>
>
> Jin wrote:
>> I also dived into the problem at the weekend, a weekend full of
>> ML
>> and ants:) I find the problem is very hard for the local scope
of
>> ants and just one controlable variable-scent. Until now, there
> are
>> two main algorithm: ....
> I've tried something else with no result. I'm not sure that it was
> because of bad programming or not. I tried to have two different
> scent-ranges. The choice that I've tested most was low scent
> (below
> s0 in some submissions) was "bad-position". Higher was good (and
> zero was unknown). I've also tried the opposite. Very high is
> bad.
> For that I've tried to stay a while if a bad position was found
> until
> the score was really high.
> But... it didn't work. And I wasn't convinced enough that it could
> really work, so I didn't spend much time on it....

Hi all.

since we are sharing ideas and all...

One of my favorite unimplemented ideas is a solver that works similar
 to bedlam (i. e. scent hill based) but uses modular arithmetic to
interpret the scent. All scents are interpreted in mod 100 e.g. a
trail
698 499 200 701 is seen as
 98 99 0 1.
This means that an ant can always reinforce an existing trail without
altering it by dumping scent of 100. It also eases the implementation
of food trails (as described by Mike), which would work just as well
as the food train on scenarios where the food is hidden and just as
well as the scent hill on scenarios where the food is plentiful
(since the nearest food will necessarily be fetched first.

An ant could even erase a food trail as it brings the last morsel of
food from a stash and it would be possible to mark dead ends. If it
could be arranged that all anthills have the same (or very close to
the same) value of scent modulo 100, then an ant could always choose
the shortest known route to a hill rather than simply the most
heavily used route (as in the current implementation). Initially this
synchronization between hills that are far apart seemed an impossible
requirement, but the initialization scent trail effectively provides
all ants in the init phase with a clock that tells the time modulo
98. This knowledge can be used to sync the scent on all hills that
are discovered by ants in init phase (as most hills should be).

The downside of this approach is that it becomes possible for a scent
trail to break in the middle, where previously they would never break
but merely shrink from the end. This could be alleviated using a
trail repairing strategy as the first recourse, and if this fails an
ant on a broken trail could backtrack, erasing it as he goes.

I got the basic ideas working while we were still in twilight, but
the proper strategies for trail repair and erasing only became clear
to me once we were in an advanced stage of daylight and I was much
too hassled to go back to that. (besides Jan's code was just sooo
much nicer to work with than either my own or Cobus's)

This was a brilliant contest and I certainly think the problem is
one of the most beautiful and challenging ones I've ever come across.
Thanks and congrats to the Matlab contest team.

Regards
Hannes Naudé

When will we get the two contest testsuits?

Laszlo

Stijn Helsen wrote:
 
> I've tried something else with no result.

That one sentence encompasses most of the contest for me! There were
lots of ideas that made improvements to the test suite, but could not
dig out of the deep local minimum that the magic numbers took us to
in the contest suite.

I thought I was going to have a real improvement in the case where an
ant is near food and other ants, but nothing else. The target
function being maximized was "food - ants". While conceptually
probably correct, it is not clear that moving closer to food should
be exactly equally weighted with moving away from other ants. I
experimented with changing the relative weighting, which worked great
on the test suite. But my "More Sociable Ants" and "Less Sociable
Ants" entries could not make a dent in the contest lead.

First off, it was an enjoyable contest as both a participant and
spectator. Great job Mathworks team!

A few comments:

- When I search the entries I get a list with score, time, and
result. It sure would be nice to list current rank as well.

- I propose a four-part contest to encourage algorithm development:
1) Darkness. 2) Sunrise - Same as twilight now. 3) Twilight - Allow
full access to all code from darkness and sunrise, but none of the
twilight entries. 4) Daylight - Same as daylight now, but only the
last day of the contest.

I think this would prevent good algorithms from being swamped by
tweak entries but still allow a sharing of ideas early on.

- The generality prize is a great idea. However, with all the tweak
entries, it is likely that one of those will find a deep local minima
in the new test suite.

- I agree Stijn's comments that this contest was easier to get
started with because it is more forgiving. I.e., if I try to do
something illegal, don't give an error, just don't do it. It was much
easier to get started than with the furniture contest.

- Will the official test suite and generality test suites be made
available for download? I'd like to see them along with the contrived
tests used for the mid-contest analysis.

Steve Hoelzer

Steve Hoelzer wrote:
>
>
> First off, it was an enjoyable contest as both a participant and
> spectator. Great job Mathworks team!

Can't fault these sentiments. However, what made it a "MATLAB
Programming Contest" as opposed to a "Programming Contest"? Other
than it was posed, monitored and judged by TMW?

Steve Amphlett wrote:
>
>
> Steve Hoelzer wrote:
>>
>>
>> First off, it was an enjoyable contest as both a participant
and
>> spectator. Great job Mathworks team!
>
> Can't fault these sentiments. However, what made it a "MATLAB
> Programming Contest" as opposed to a "Programming Contest"? Other
> than it was posed, monitored and judged by TMW?

Well, the early entries in Fortran, C++, and Java didn't really
perform very well, so most people didn't tweak them.

----------------------------------------
"the cyclist" <thecyclist@gmail.com> writes:
> Steve Amphlett wrote:
>>
>>
>> Steve Hoelzer wrote:
>>>
>>>
>>> First off, it was an enjoyable contest as both a participant
> and
>>> spectator. Great job Mathworks team!
>>
>> Can't fault these sentiments. However, what made it a "MATLAB
>> Programming Contest" as opposed to a "Programming Contest"? Other
>> than it was posed, monitored and judged by TMW?
>
> Well, the early entries in Fortran, C++, and Java didn't really
> perform very well, so most people didn't tweak them.

I submitted an entry using the Whitespace language.

http://compsoc.dur.ac.uk/whitespace/index.php

Apparently this went entirely unnoticed.

--
Steve Eddins

Development Manager, Image Processing Group
The MathWorks, Inc.

will we be able to watch the generality get processed through the
queue?

when will it be?

Steve Eddins wrote:
>
> I submitted an entry using the Whitespace language.
>
> <http://compsoc.dur.ac.uk/whitespace/index.php>
>
> Apparently this went entirely unnoticed.

Ah, but if you submitted in Darkness...

I was sure that there would be a way to get more food from hills with
few rocks, where the bucket brigades tend to take windy paths
backward, so I sent several versions that would go forward if there
were enough food items around to maintain a trail...

I also tried to implement leaving hill and food scents in sort of a
checkerboard pattern or with modulo arithmetic, but since every ant
runs the same code, trying to smash two ideas together always lead to
ants that were stuck moving back and forth between two cases.

The generality prize is a good idea, even though it will still be
pretty random who gets it. It's all for the fun of the challenge
anyway...

Steve Hoelzer wrote:
>
> - I propose a four-part contest to encourage algorithm development:
> 1) Darkness. 2) Sunrise - Same as twilight now. 3) Twilight - Allow
> full access to all code from darkness and sunrise, but none of the
> twilight entries. 4) Daylight - Same as daylight now, but only the
> last day of the contest.
>
> I think this would prevent good algorithms from being swamped by
> tweak entries but still allow a sharing of ideas early on.

I think this is great idea. I question all this tweaking. I could not
partake this time because I am travelling but have tried to follow
along. When I run the leading entry on the testsuite, everytime I get
a substantial different result score (ignore timing, just results).
That is not entirly suprising because of the in part random moves
that occur. Maybe it is just me, but as long as that happens I don't
feel confortable with the end results.

That being said, it is/was a very interesting contest!

Leendert Combee wrote:
> ....
> That is not entirly suprising because of the in part random moves
> that occur. Maybe it is just me, but as long as that happens I
> don't
> feel confortable with the end results.
>
> That being said, it is/was a very interesting contest!
In the real testing the random-generator is always reset. Then, the
result is always the same.

Stijn

Hannes Naude wrote:
>
>
> Just wondering.
>
> What is the best score that anyone ever saw on the sample
> testsuite.
> We once got 13700 but I have to admit that took some serious
> random
> number mining.
>
> regards
> Hannes Naudé

How was this "random mining" really done?

Laszlo

Just wondering.

What is the best score that anyone ever saw on the sample testsuite.
We once got 13700 but I have to admit that took some serious random
number mining.

regards
Hannes Naudé

Laszlo Sragner wrote:
>
>
> Hannes Naude wrote:
>>
>>
>> Just wondering.
>>
>> What is the best score that anyone ever saw on the sample
>> testsuite.
>> We once got 13700 but I have to admit that took some serious
>> random
>> number mining.
>>
>> regards
>> Hannes Naudé
>
> How was this "random mining" really done?
>
> Laszlo

In essence it just means we ran our code lots of times with different
seeds every time, but our approach was slightly more sophisticated
than that. We modified runcontest so that a random seed could
optionally be specified. The random number generator is then reset to
this seed before every scenario. This allowed repeatability which
helps greatly in debugging. Later we also wrote a little "caretaker"
script that would run the runcontest multiple times and log all the
scores together with the seeds that produced those scores. This
allowed us to determine (at the cost of time) whether a given mod was
really an improvement or not by taking the average score over
multiple runs. Our best entry (The early ant catches the worm) scores
between 19780 and 13700 (seed 208147.9) with an average of 16270
evaluated over 277 runs.

We use this to compute all manner of statistics comparing Early Ant
to other TLL166 variants and prove beyond any reasonable doubt that
we should have won ;-) ;-)

Hannes

> ...was really an improvement or not by taking the average score
over
> multiple runs. Our best entry (The early ant catches the worm)
> scores
> between 19780 and 13700 (seed 208147.9) with an average of 16270
> evaluated over 277 runs.
Maybe just taking the average wasn't the best choice. More something
like the median was better ???

Stijn Helsen wrote:
>
>
>> ...was really an improvement or not by taking the average
score
> over
>> multiple runs. Our best entry (The early ant catches the worm)
>> scores
>> between 19780 and 13700 (seed 208147.9) with an average of
16270
>> evaluated over 277 runs.
> Maybe just taking the average wasn't the best choice. More
> something
> like the median was better ???
Yes, that's true, the median would be a better indicator of
performance. As it happens the distribution appears to be roughly
Gaussian (we did histograms and the works, its really difficult to
get back to work after all the excitement) so it makes very little
difference. The median comes out to 16180.
H

I've updated the File Exchange submission with the actual and
validation test suites.

We're busy re-scoring the entries to determine the Generalization
winner. Although you can't watch it live, we'll be sure to post some
statistics when we announce the winner.

The feedback here has been great. Please keep it coming.

Stijn Helsen wrote:

> In the real testing the random-generator is always reset.
> Then, the result is always the same.

I know, but isn't that the "problem" in the sense that it hides
performance variations by each algorithm if you simply feeded with
different random nr seeds. The rand(1,5) really doesn't help to solve
this issue. See also other recent messages here. Maybe this is as
good as it gets given the cputime penalty, but I do interpret it as
that there is more potential in smarter solutions.

Working with a lot of 'rand' was attractive at this contest, because
'rand' is so fast. Some of the issues that have been mentioned would
disappear if 'rand' would be more expensive. How about this
suggestion:

1. 'rand' and, just to be sure, also 'randn', 'randperm', 'sprand',
'sprandn' are disabled by filefilt.
2. instead, there is this function:

function r = contestrand
for k=1:1e3, end
r = rand;

Choose whatever constant you like. The higher, the better for
programmers who find algorithmic improvements that might be
computationally expensive. Of course, I did not forget to pass
arguments to 'rand' inside the function. Getting many random numbers
should require more time, also.

The following function is also funny, you might get in trouble if you
recklessly started your solver with
'rand(1,5)':

function r = contestrand
global N
N = N+1;
for k=1:N, end
r = rand;

Needless to mention, replacing 'N+1' by the expression of your choice
is a way for the contest designer to trim the contest accordung to
the needs of the problem.

Heinrich

Heinrich Acker schrieb:
> Working with a lot of 'rand' was attractive at this contest, because
> 'rand' is so fast. Some of the issues that have been mentioned would
> disappear if 'rand' would be more expensive. How about this
> suggestion:
>
> 1. 'rand' and, just to be sure, also 'randn', 'randperm', 'sprand',
> 'sprandn' are disabled by filefilt.
> 2. instead, there is this function:
>
> function r = contestrand
> for k=1:1e3, end
> r = rand;

but then it would not be too difficult to generate your own random
numbers (probably derived from the current state of the system). so in
this contest you could have used the scent, food and main maps for that.

in general i think random numbers are important in a good algorithm of
that sort. for example the use in the pathfinder function helps to find
shorter paths home. unfortunately, the 1000 time steps are not enough to
exploit that.

however, i have no idea how to decrease the variances due to different
random nunbers, without making the runtime much longer (it was already
quite large this time, resulting in a very long queue at times).
probably it was just bad luck (maybe good luck for me on sunday ;-) )
that we reached this "deep local minimum".
jan

--
jan langer ... jan@langernetz.de
"pi ist genau drei"

Another aspect of this contest that I wonder how much is exploited or
can be exploited is that the result depends strongly about how far
the remaining food (if any) is away from the anthills. It is not just
the amount of food (which to me sounds more logical in a real-life
situation), but how far it is away. I am not sure to what extend the
ants can prioritse food at large distance. Maybe one way is to let
some ants (by chance) search for food and let others move it...?

Bringing distant food object n units closer to the base reduces the
score by the same amount as moving a nearby food closer by the same
distance. The cost (time taken) of moving food n units usually
involves the equivalent of a trip from base to food and back, and is
independent of distance from the base.

The direction towards food from the base is more significant because
the score is based on Euclidean distance. Consider a base at (1,1) -
food at (10,10) has a bigger impact on the score than food at (10,1),
but can be brought to base for the same cost.

Nathan

Leendert Combee wrote:
>
>
> Another aspect of this contest that I wonder how much is exploited
> or
> can be exploited is that the result depends strongly about how far
> the remaining food (if any) is away from the anthills. It is not
> just
> the amount of food (which to me sounds more logical in a real-life
> situation), but how far it is away. I am not sure to what extend
> the
> ants can prioritse food at large distance. Maybe one way is to let
> some ants (by chance) search for food and let others move it...?

nathan q wrote:
> The cost (time taken) of moving food n units usually
> involves the equivalent of a trip from base to food and back, and
> is independent of distance from the base.

Sorry, that doesn't make sense. I should have said that if you move
food all the way to base, the score reduction per unit time invested
is about the same regardless of initial distance. If you don't get
the food all the way back, it's probably a less efficient use of
time.

Nathan

I think it is worth to bring home the food closer to the hills. If
there are more anthills than it has a chance that the ant will bring
the food to the more distant hill just because its track leads it to
there. If You leave food next to the hill and search for more distant
then You raise the chance of this case.

I think the good measure of goodness of the algorithms should be the
coordinate distance abs(x_food-x_hill)+abs(y_food-y_hill) and in this
way the neccesairy moves to deliver the food in a 4 connected way. If
You take the max(abs(x_food-x_hill),abs(y_food-y_hill)) then You
measure the 8 connected way. I think this lowers the randomness of
the outcome of the algorithms because the result will not depend on
the direction of the found food.

Laszlo

An important point to note is that random numbers were not merely
convenient in this contest, but required. To demonstrate consider the
following scenario, if no random numbers are allowed, in what
direction should an ant go if it can see no scent, no rocks, no hills
and no food. If the answer is "up" this implies that ALL ants in this
situation will go upwards and the ants will therefore tend to cover
the top part of the sandbox much more thoroughly than the bottom.

No matter which deterministic answer we select to the above question,
biased ants result, which will help in some cases and hurt in others
but should fare worse on average. While the case described above may
seem unlikely and the influence of deterministic behaviour vs. random
behaviour therefore expected to be small, the same reasoning applies
to any symmetric "ant-view".

In my opinion, the best way to remove the random influence from the
leaderboard, would have been to disallow the use of rand inside
solver. But since solver may need random behaviour it is allowed to
return multiple acceptable moves (that is a vector of dx's a vector
of dy's etc.) runcontest then selects randomly from this vector.

While this approach obviously still has a random component it at
least ensures that each algo only gets a single shot at the lottery.
Adding rand(x,y) with different values of x and y to solver would not
influence the result (in fact it would be disallowed). If you want a
different run you would have to modify the guts of the algorithm.

In any case, lottery or not, this contest is extremely addictive, and
you can be sure we will be competing again in the next one.

Cheers
Hannes

Hannes Naudé wrote:
> In my opinion, the best way to remove the random influence from
the....
I don't think it is needed to try to remove the random influence. I
think that the problem is that a "local minimum" can be reached for
which it is difficult to leave, and I suppose that any algorithm with
and without or with restricted use of rand's can lead to it.
It is just part of the ...game/contest...

Stijn

How's the Genreality coming along?

Oops! Generality that is.. :)

>
> How's the Genreality coming along?

Dear Organizers,

How the recalculation is going on?

Laszlo

David Jones's "TLL280variant9" is our Generalization winner.
Congratulations!

Re-scoring all the entries against the new test suite took almost as
long as the contest itself. We started the queue on Thursday and it
finished on Tuesday.

The table below lists the top 25 finishers. The columns are as
follows: place author "title" score (result, time).

# 1 David Jones, "TLL280variant9" 2426.835 (24265.9246, 75.7)
# 2 Timothy Alderson, "TLL268" 2452.045 (24517.7332, 76.8)
# 3 Stijn Helsen, "Dinfluence01_test" 2455.302 (24548.1962, 82.6)
# 4 Stijn Helsen, "Dinfluence01" 2455.305 (24548.1962, 82.7)
# 5 Timothy Alderson, "TLL245" 2469.534 (24692.8709, 75.9)
# 6 Hannes Naudé & Cobus Potgieter, "The Early Ant catches the worm
I" 2475.470 (24647.9880, 113.5)
# 7 David Jones, "concisex1" 2476.971 (24766.9017, 77.2)
# 8 Stijn Helsen, "calcdxdy3_test3" 2477.098 (24766.9017, 80.9)
# 9 Timothy Alderson, "TLL319" 2481.238 (24809.7803, 76.4)
#10 Timothy Alderson, "TLL159" 2482.149 (24766.9017, 106.8)
#11 Niilo Sirola, "spot the difference 2" 2488.887 (24877.0800, 91.5)

#12 Tom Lemke, "monday003" 2489.022 (24877.0800, 92.6)
#13 Niilo Sirola, "spot the difference" 2489.555 (24877.0800, 96.0)
#14 zox, "zox2" 2489.626 (24891.3385, 82.8)
#15 Timothy Alderson, "TLL323" 2495.463 (24952.3048, 75.3)
#16 dur, "sf4" 2498.613 (24984.7186, 70.3)
#17 carl, "testc17" 2501.459 (25012.0554, 76.1)
#18 carl, "testc20" 2501.459 (25012.0554, 76.2)
#19 carl, "testc16" 2501.477 (25012.0554, 76.8)
#20 PU, "L1" 2501.773 (25014.8570, 77.4)
#21 Stijn Helsen, "againagain06" 2503.386 (25032.4410, 70.4)
#22 Stijn Helsen, "againagain03" 2505.790 (25056.5185, 70.1)
#23 zox, "zox4" 2509.802 (25093.1958, 82.6)
#24 Timothy Alderson, "TLL249" 2511.771 (25114.9410, 77.0)
#25 Jan Langer, "mir werds daweng gar e bill zu bleede" 2513.453
(25131.5717, 77.7)

Will the Generalization winner (and maybe a longer list) be published
in the Ants-pages?

Stijn

can we have the test suite for this as well?

Stijn Helsen wrote:
>
>
> Will the Generalization winner (and maybe a longer list) be
> published
> in the Ants-pages?
>
> Stijn

This is included in the testsuite (published shortly after the end of
the contest).

Stijn
Tom Lemke wrote:
>
>
> can we have the test suite for this as well?

Thanks, I hadn't noticed the third .mat file

Stijn Helsen wrote:
>
>
> This is included in the testsuite (published shortly after the end
> of
> the contest).
>
> Stijn
> Tom Lemke wrote:
>>
>>
>> can we have the test suite for this as well?

Hi Mike,

Yes, this is a problem we are experiencing with our newsreader
software. We are investigating this. Meanwhile you can access earlier
threads here:

Laszlo Sragner, "MATLAB Programming Contest: May 11-18, 2005" #1, 11 May 2005 9:32 am </WebX?14@@.ef0580d/0>


Min

Mike Bindschadler wrote:
>
>
> I went to look over some of the earlier posts on this thread, and
> they seem to be missing. The first message says it's message 1,
> and
> the second message says it's message 47. Is this normal for very
> long threads?