MATLAB Programming Contest: May 11-18, 2005
Min Poh
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
con...@mathworks.com.
We look forward to seeing your entry. Good luck!
- The MATLAB Contest Team -
Laszlo Sragner
Is it possible to have multiple ants and anthills?
Laszlo
Nick Howe
toolbox functions?
Matthew Simoneau
Matthew Simoneau
<http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=7621>
Stijn Helsen
>
>
> Is there an easy way to check that an entry does not contain any
> toolbox functions?
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
Nick Howe
rules, but the problem description implies that use of global
variables is not allowed. Is that correct?
Ed Manlove
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
Stijn Helsen
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)
Matthew Simoneau
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."
Stijn Helsen
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
Stijn Helsen
Laszlo Sragner
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
Stijn Helsen
ant get lost totally. (I don't see this possibility in the
runcontest, so I suppose it is.)
Stijn
Laszlo Sragner
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
Ed Manlove
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
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
.
Stijn Helsen
timestep no ant has moved. That means that the following steps
nothing will happen either....
Ed Manlove
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]
Ed Manlove
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
Phil Mendelsohn
> 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
Ed Manlove
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
Yuval Cohen
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
Rungun Nathan
>
>
> 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
Stijn Helsen
If nx==x and ny==y then that place is incremented and decremented,
so no change.
it is OK
Stijn Helsen
brian
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
> con...@mathworks.com.
>
> We look forward to seeing your entry. Good luck!
>
> - The MATLAB Contest Team -
Stijn Helsen
>
>
> Are ants allowed to move diagonally?
Laszlo Sragner
minimap is blocked by rocks or not?
Of course the location should be on the boarder of the minimap.
Laszlo
Ed Manlove
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
Mike Bindschadler
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!
Jan Langer
It seems they started the queue processing just when the darkness
ended.
jan
Matthew Simoneau
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.
Jan Langer
got the queue stuck again? there appears to be no progress over the
past half hour.
jan
Matthew Simoneau
problem updating the web pages with the results.
Matthew Simoneau
Jack Snoeyink was on the top of the list. We'll send him a MATLAB cap
and reserve his place in the MATLAB Contest Hall of Fame.
Congratulations!
We are now in Twilight, which ends on 5PM EST on Friday. At that
point, we'll award another mid-contest prize and expose all the code
for the final phase.
the cyclist
>
>
> The next MATLAB Programming Contest will start ...
By my calculation, the scoring constants are
k1 = 0.1
k2 = exp(-9)
k3 = 0.1
Cobus Potgieter
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
Rungun Nathan
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
Jin
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
Christian Ylämäki
Your algorithm takes longer to finish on some testcase found on the
sever (stuck in a loop maybe?). Just my guess...
/Christian
Nick Howe
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!
Mike Bindschadler
>
>
> 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
Tom Lemke
> 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.
Matthew Simoneau
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).
Tom Lemke
test suite?
Stijn Helsen
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?
Stijn Helsen
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
> ....
Tom Lemke
explicit details to viewing the contents of the mat file, making my
own maps, and shoving them into the mat file with the others.
the cyclist
> 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
This seems rather petty, now that our tweaking has been crushed by
genuine algorithmic improvements!
James Nagel
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.
Matthew Simoneau
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.
Matthew Simoneau
the contestant who makes the biggest cumulative improvement to the
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).
the cyclist
>
>
> 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.
the cyclist
> We'll award a prize
> for
> the best entry submitted before midnight Chemnitz time (6PM EDT).
Is that 6PM EDT on Monday?
Matthew Simoneau
John Voiklis
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
Stijn Helsen
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
Jin
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
Stijn Helsen
> 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
Jin
Thanks, Stijn!It's magic!This trick makes the random more "not
random":) Thanks again:)
Jin
the cyclist
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.
Matthew Simoneau
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.
Laszlo Sragner
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
Stijn Helsen
> 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.
Nice idea, but I'm affraid that I've been focusing too much on
tweaking.... maybe....
Stijn Helsen
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....
Jin
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
Jan Langer
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 ;-)
Stijn Helsen
>
>
> 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.
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
Laszlo Sragner
For example some kind of maze-like lab, where only one sugar is
hidden somewhere, and only one ant is present.
Laszlo
Stijn Helsen
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
Heinrich Acker
>
> 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
Laszlo Sragner
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
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
Matthew Simoneau
"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.
Laszlo Sragner
> 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
nathan q
>
> 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/>
the cyclist
> 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!
Stijn Helsen
> 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
Stijn Helsen
"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.
Mike Bindschadler
>
> 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
the cyclist
> 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.)
Jin
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
Stijn Helsen
> 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
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....
Hannes Naude
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é
Laszlo Sragner
Laszlo
the cyclist
> 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.
Steve Hoelzer
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 Amphlett
>
>
> 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?
the cyclist
Well, the early entries in Fortran, C++, and Java didn't really
perform very well, so most people didn't tweak them.
Steve Eddins
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.
Tom Lemke
queue?
when will it be?
Jack Snoeyink
>
> 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...
Leendert Combee
>
> - 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!
Hannes Naude
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
How was this "random mining" really done?
Laszlo
Stijn Helsen
> ....
> 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!
result is always the same.
Stijn
Hannes Naudé
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
Stijn Helsen
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.
like the median was better ???