|
|
Thanks to all those who returned the emailed questionaires. I have
compiled these responses below for your enjoyment. The top finishers
are near the top but otherwise the order is fairly arbitrary.
In addition to these write-ups, please check out the consolation awards
using the link at the left.
_____________________________________________________________
scrunch was submitted by Xavier Bernardy (xavier)
scrunch finished in position 01 and 10 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy scrunch used for the SOLO POTM.
I first tried construction heuristics with some backtracking but it quickly
turned out to be very inefficient, so I gave up and decided to use
improvement heuristics.
I eventually found a paper about "Guided Local Search" and decided to give it a try.
So, my squirrel iterates a 2-opt improvement heuristic over some initial
random path. After each iteration, the cost of some edges figuring in
the path is increased. The chosen edges are usually the longest ones,
but shorter edges will also be see their cost increased as the search goes on.
The search stops after a fixed number of iterations, and the best path
is saved in the temp file.
Some useful links:
TSPBIB home page - general information about the TSP:
http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
Guided Local Search:
ftp://ftp.essex.ac.uk/pub/csc/technical-reports/CSM-247.ps.Z
Interactive demos of some TSP heuristics:
http://itp.nat.uni-magdeburg.de/~mertens/TSP/index.html
Describe briefly the strategy scrunch used for the MULTIPLE POTM.
I was running out of time when I started to think about this problem,
so I implemented something very simple.
All I do is to sort the list of nuts:
- the ones that my squirrel can eat before anyone else come first.
- the ones he may have to share with other squirrels come next.
- the remaining ones are sorted according to their distances
to other squirrels and to other nuts.
My squirrel then ran towards the first nut in that list, trying to grab
other nuts on his way if possible.
During the multi tests, it turned out that most of these little hungry
monsters were trying to grab the same nuts, so I simply changed
the target nut : if several nuts are almost equally good, my
squirrel dashes towards one figuring at a lower rank in the list.
If I had it to do all over again, here's what I'd try:
Start earlier and go to the zoo, watch some real squirrels in action.
I named my squirrel scrunch because ...
If you look closer you'll see my squirrel does not carry any nut-case
but scrunch every single nut as soon as it finds it. I think this will
allow him to run faster in the 1st POTM because he doesn't have to
spend time wondering how all those nuts could fit within his tiny nut-case.
Of course, after having scrunch'ed all the nuts in the 1st POTM, he'll
not be so hungry anymore for the 2nd POTM, so I do not expect him to
do very well there....
Where do you live? do for fun? do for work? innermost secret?
- Brussels, Belgium
- I'm playing go for 2 years now. This is a fascinating game and I
think It will keep me busy for some more years. I was also
training virtual squirrels these days...
- I was writing embedded software for digital TV's, but we went
through a collective layoff and our development group
will be closed very soon...
- I like to watch Derrick on TV. It's a german TV serie, popular
mostly with elderly people. As I'm still < 30y, don't tell anyone :-)
_____________________________________________________________
Filbert_Einstein was submitted by William Little (Tempus)
Filbert_Einstein finished in position 04 and 01 on POTM1 and POTM2.
_____________________________________________________________
++ Describe briefly the strategy Filbert_Einstein used for the SOLO POTM.
To start things off, it picks a random path
Around the field, through all the nuts it hath,
Then uses an insertion-based heuristic.
(Rendering it nondeterministic)
This is how it picks a starting place
Within a quite humongous searching space.
With steps made by reversal of a section,
It then tries to make each small correction.
Feeling out the slope of nearby ground,
It tries to take a step that won't lead down.
It fumbles in the dark to climb a hill,
As Monte Carlo algorithms will.
A million such attempts are made, and then
It starts back at a random path again,
And thus it plans to circumambulate,
'Till sys+user time is fifty-eight.
++ Describe briefly the strategy Filbert_Einstein used for the MULTIPLE POTM.
...But when the count of squirrels is more than one,
Then something very different will be done.
It guesses paths for other squirrels, when able,
Sticking the results into a table.
When it finds the table is complete,
It then must choose a likely nut to eat.
The table tells when each should disappear,
Which helps it figure out which way to steer.
It knows that things would work out for the best
If it can reach the nut before the rest,
But if the claim is not so cut-and-dried, it
Knows just how the nut will be divided.
Utilizing 3-ply lookahead,
And all else here that I've already said,
It tries to meet the POTM paradigm,
By maximizing nuts per unit time.
++ If I had it to do all over again, here's what I'd try:
Less coding, more sleeping.
++ I named my squirrel Filbert_Einstein because ...
Top 10 reasons I named my squirrel Filbert_Einstein:
10. I wasn't sure the crowd was sufficiently versed in official
multi-squirrel nomenclature to fully appreciate names
such as "DoomsDray" and "Trial_by_Scurry".
9. The voices in my head were most insistent.
8. I didn't think of Cheek_Full_O_Nuts until much later.
7. Because of that old story of how Sir Isaac Einstein discovered
gravity when a nut fell on his head while he was sitting
under a filbert tree.
6. It had a better ring to it than "Pistachio_Heisenberg".
5. It anagrams to "Finest Libertine".
4. That's just what it said on his squirrel tags.
3. I wanted to avoid having "nut" in the name, i.e. nutcase,
nutpick, I'm_a_nut, nutjob, etc., ad infinutum.
2. He's the smartest guy in all of macademia.
And the number one reason I chose the name Filbert_Einstein...
1. Someone had to.
++ Where do you live? do for fun? do for work? innermost secret?
Where I live: The USA. More specifically, right here, or in the general
vicinity of nearby.
What I do for fun: Evade questions.
What I do for work: Try to keep everything from falling apart.
Innermost secret: Even *I* don't have THAT kind of clearance.
The above poem and top ten list are copyright (C) 2004 William Little.
Limited right to publish granted to Fred Hicinbothem.
All other rights reserved.
_____________________________________________________________
101 was submitted by Bill Wade (billybob)
101 finished in position 02 and XX on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy 101 used for the SOLO POTM.
This was the first time I've programmed a TSP problem.
The references below were a big help to me.
Most of the work is done by a fast 3-opt (break up to three edges in the
path and reassemble) to find local minima, followed by a swap of five random
pairs of nuts to "widen" the definition of "local". I spend several seconds
at the end of the minute trying up to a full 8-opt search. In very rare
cases this improves the solution.
For fast 3-opt see http://www.research.att.com/~dsj/papers/TSPchapter.pdf
I estimate the Held-Karp lower bound to the TSP problem so that I can stop
looking (tie breaker is CPU) a bit earlier. I was surprised to see how
small the gap between the lower bound and my solutions typically were (one
or two steps on most randomly distributed boards).
See
http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf
Describe briefly the strategy 101 used for the MULTIPLE POTM.
1) Score each nut = 1/(number of closest squirrels)
2) Score each square as sum of nut scores divided by (distance to nut,
squared). If one or more squirrels are as close or closer to the nut,
divide by another factor of 100.
3) If my squirrel is not sharing a square, or if the problem is currently
very large (squirrels * nuts > 10000), then go to the adjacent square with
the highest score.
4) If my squirrel is not alone and the problem is not too big, assume that
all squirrels are likely to move to an adjacent square with a probability
proportional to that square's score. With that assumption, play and replay
an entire simulated game varying my first move to each adjacent square (I
use the "assumed" strategy for the rest of the game) and see which "first"
move leads to the best final result.
If I had it to do all over again, here's what I'd try:
I never got around to doing some straightforward speed-ups (ie changing
function calls to macros).
I'd do more research on figuring out whether a path that I've found that is
above the held-karp limit is optimal or not.
Try splicing together sub-solutions from various local-minima solutions.
I named my squirrel 101 because ...
In the second world war, elements of the US 101st airborne division were
surrounded in Bastogne during the battle of the bulge. When asked to
surrender, the commander's reply was "NUTS".
Where do you live? do for fun? do for work? innermost secret?
Houston. Puzzles and mind games. Program (pipeline industry).
I'm not going to tell.
_____________________________________________________________
NutCracker4 was submitted by Mike Sweeney (mjs)
NutCracker4 finished in position 07 and 03 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy NutCracker4 used for the SOLO POTM.
NutCracker4 is a squirrel using 195 lines of python
(roughly 80 solo + 80 melee + 35 utility).
It produces POTM1 results in 5 to 9 minutes using a
home-grown algorithm (more fun that way ).
Most of the work is done on the first move taking 10 seconds.
nutcracker uses the follwing heuristic:
load previous best tour from file
while time left,
shuffle nuts
tour = first three
for nut in nuts[3 to N],
add nut to tour where cheapest
if more than one best choice, choose randomly
add start point (squirrel position) where cheapest
if tour length is best or close to it,
optimise each sliding six nut window of the tour
if best, store tour
write best tour to file
return location closest to first nut on tour
Describe briefly the strategy NutCracker4 used for the MULTIPLE POTM.
NutCracker4 tries to find a path with maximum reward (most nuts), but also
tries to minimise risk (that another squirrel will steal the nut before him),
and also has a mean streak - if he can get a nut one move before other
squirrels he will.
Algorithm:
make row and column indexes
make distance indexes (dist 1 to 5 only) for
nut-nut, nut-squirrel, squirrel-nut, and me-nut
initialize paths starting at my location
while time left,
for each path,
for each nut near the end of the path,
if nut not already on the path,
get nut-value considering other squirrel & nut locations
add new path including this nut
assign new path reward to be path reward plus this nut-value
keep 30 best paths (of highest reward value)
return location closest to first nut on best path
Nut value is determined by:
if other squirrels can get to it first,
reduce value by number of squirrels & how much closer they are
otherwise if squirrels are same distance away,
value is shared,
otherwise if I am one move closer,
value is boosted by how many I annoy by getting it first :-),
increase value by number of surrounding nuts
decrease value by distance from me
NutCracker4 uses 5 seconds per move.
It iteratively computes the best paths from the current location,
and when the time is up, it picks the best one and outputs the first move
on the best path. In 5 seconds, the program computes paths about 8 nuts
long. It does not rest.
If I had it to do all over again, here's what I'd try:
Spend more time sleeping and less watching squirrels run around in the simulator...
I named my squirrel NutCracker4 because ...
I could not find an algorithm that would allow me to gather whole nuts in the
melee, so I was resigned to making a squirrel that carried a nutcracker, scales,
and sharp knife. So NutCracker he became. It is the fourth version that is entered
in the comp.
Where do you live?
Canberra, Australia (the nation's capital) with wife, 3 kids, cat,
lots of computers, and lots of books.
do for fun?
Muck about with computers.
do for work?
Muck about with computers.
innermost secret?
Now it wouldn't be a secret if I told you, would it?
Don't tell anyone, but I have recently become a little obsessed with SQUIRRELS,
SQUIRRELS, SQUIRRELS, my SQUIRRELS, SQUIRRELS, and SQUIRRELS, SQUIRRELS,
SQUIRRELS, SQUIRRELS, and more SQUIRRELS, SQUIRRELS, SQUIRRELS, SQUIRRELS,
SQUIRRELS, those SQUIRRELS!, SQUIRRELS, SQUIRRELS, SQUIRRELS.........arrrrrg!
Oh, where did I put my pills?...
_____________________________________________________________
harlem_shuffle was submitted by Davor Slamnig (Slama)
harlem_shuffle finished in position 12 and 07 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy harlem_shuffle used for the SOLO POTM.
For boards with up to 9 nuts, harlem_shuffle enumerates all paths
and finds the best one. I don't think Fred would be that devious
in the finals, but I don't want to take any chances.
For boards with 10 or more nuts, harlem_shuffle connects nuts into
"strings", which are concatenated until the final string is the
squirrel path. Connect two nuts or strings closest to each other, iterate.
Then it tries to optimize the resulting path using a nut-shuffling
loop (harlem_shuflle, ne?).
Describe briefly the strategy harlem_shuffle used for the MULTIPLE POTM.
Go for the closest nut that gives the best payoff, assuming that all
other squirrels in range are going for the same nut. If more than
one nut satisfies the description, pick the one which is closest to
some other nuts.
If I had it to do all over again, here's what I'd try:
For solo mode, I'd probably try to do some more intelligent optimization.
For multiplayer mode, I'd make the squirrel a little bit smarter.
But not too much, plain greed seems to work best here.
I named my squirrel harlem_shuffle because ...
You move it to the left
And you go for yourself
You move it to the right
Yeah if it takes all night
Now take it kinda slow
With a whole lot of soul
Don't move it too fast
Just make it last
(Harlem Shuffle, Relf/Nelson)
Where do you live? do for fun? do for work? innermost secret?
I live in Zagreb, Croatia.
For fun, I make furniture, play guitar, do POTMs...
Work is computer programming.
My innermost secret seems to be pretty deep, I haven't uncovered it yet.
_____________________________________________________________
SANE was submitted by Wolfram Hinderer (Kuno)
SANE finished in position 17 and 06 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy SANE used for the SOLO POTM
Greedy - I did not want to code for speed. My code is ugly
enough already :-)
Describe briefly the strategy SANE used for the MULTIPLE POTM.
SANE estimates the expected numbers nuts each squirrel will
get for a certain move. It then adjusts the probabilities for
each of that moves. Iterate. When stability is more or less
reached, one of the possible moves for SANE is randomly chosen,
according to the probabilities.
(This randomization at least eliminates the possibility of
being outguessed permenantly...)
If I had it to do all over again, here's what I'd try:
Start earlier...
I named my squirrel SANE because ...
I searched alltheweb for the largest suitcase... and found
SANE SPORTS WEAR. At this point, I really started thinking
about participating.
(Squirrel Acces Now Easy later crossed my mind, but the
above story is the truth...)
Where do you live? do for fun? do for work? innermost secret?
I live in Mannheim, Germany. Fun is: staying with friendly
people. I work for a live insurance company...
I have no secrets. No. Certainly not. None that I would
give away, that is.
_____________________________________________________________
grinnie was submitted by Mark Mammel (mmammel)
grinnie finished in position 10 and 15 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy grinnie used for the SOLO POTM.
Grinnie solved the TSP by simulating annealing -- first
generate a random path then swap edges looking for
improvements. As the "temperature" lowers, the probability of
jumping around to worse positions decreases.
Describe briefly the strategy grinnie used for the MULTIPLE POTM.
A simple algorithm -- grinnie found the distance from each
squirrel to each nut, then for each nut that grinnie could
reach before or at the same time as others, it was scored as
1 / number of squirrels reaching it (plus a small random
value). Then for each of the 8 possible moves, add scores for
nuts that are now closer.
If I had it to do all over again, here's what I'd try:
For the MULTIPLE, I would make a more complex algorithm that
looks for an optimal PATH rather than at single moves.
I named my squirrel grinnie because ...
grinnie is another name for ground squirrel
Where do you live? do for fun? do for work? innermost secret?
I live in Laurel, MD and work at the FDA doing
bioinformatics. For fun I play with my kids and play Pente and juggle.
My secret is that I started programming on a Commodore VIC-20
with 3 and 1/2 Kb RAM
_____________________________________________________________
W was submitted by Paul Banta (potm_junkie)
W finished in position 03 and 24 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy W used for the SOLO POTM
Simulated Annealing followed by Genetic Algorithm. In the Simulated Annealing
stage I ran for 28 seconds creating a population of 20 paths - the best 20 out
of as many as I could generate. In the Genetic Algorithm stage I ran for
another 28 seconds and randomly mutated the 20 paths from the simulated
annealing stage.
Describe briefly the strategy W used for the MULTIPLE POTM.
On the first move chose to move up, down, left, or right - move that direction
to the edge collecting as many nuts as possible. Once done with this treat nuts
and squirrels as electric / magnetic particles that either attract or repel me
respectively. Sum the attractions and repulsions to get a direction to move.
If I had it to do all over again, here's what I'd try:
I would research more. I saw many references to a program called Concorde that
seems to be tops at solving the Traveling Salesman Problem. I did not spend
enough time understanding how it works.
I named my squirrel W because ...
In the United States we just finished the election season. One of the
politicians running for President was George W. Bush. He is often referred to
as simply "W" (His father, George H. W. Bush, was also President). The Nuts
problem is exactly the same as the campaigning politician problem, I mean the
traveling salesman problem. The multiple politician, I mean multiple weasel, I
mean multiple squirrel problem is very different, though.
Where do you live?
Colorado Springs, Colorado, USA
do for fun?
POTM, Volleyball, Scouting (Boy Scouts of America)
do for work?
Software Engineer for Credence Systems Corporation (stock symbol CMOS)
innermost secret?
I was not clever enough to think of a Bozo program for this contest
_____________________________________________________________
Alvin was submitted by Harro Lissenberg (dehark)
Alvin finished in position 22 and 11 on POTM1 and POTM2
_____________________________________________________________
Describe briefly the strategy Alvin used for the SOLO POTM.
Alvin uses the so-called NearestNut(TM) strategy. A
highly sophisticated algorithm in wich Alvin goed for
the nut that is closest to his own location. Who needs
this "Traveling Salesman" stuff when you are dealing
with nuts and squirrels anyway??? ;)
Describe briefly the strategy Alvin used for the MULTIPLE POTM.
Alvin is very ego-centric. He will try and find a nut
wich he is closer to than any other squirrel, so he
can claim it for himself. If he can't find a nut wich
he can keep for himself he will go for the nut with
the least squirrels nearby. If he can't find a nut he
might be able to grab he will fall back to the "NearestNut" strategy.
If I had it to do all over again, here's what I'd try:
I might take a look at this "traveling salesman" stuff
I saw on the forum for better solo results.
I named my squirrel Alvin because ...
My girlfriend suggested it, she love(s)/(d) the Chipmunks!
Where do you live?
Netherlands
do for fun?
work
do for work?
think about squirrels a lot.
innermost secret?
you wish
_____________________________________________________________
belka was submitted by Denis Konovalchik (Dyuk)
belka finished in position 28 and 14 on POTM1 and POTM2
_____________________________________________________________
Describe briefly the strategy belka used for the SOLO POTM.
The strategy is very simple (maybe, too simple). Every time my
squirrel finds the nearest nut and comes to it one step nearer.
Surprisingly, but in the test run such a strategy let my squirrel
collect nuts quicker than 2/3 of her colleagues ;-)
Describe briefly the strategy belka used for the MULTIPLE POTM.
Every time my squirrel scores each possible variant of move. It
analyses all nuts on the field and sums the balls received for each nut:
1.0 when the move allows to reach nut before all competitors,
or 1.0 / (N+1) when the move allows to reach nut
simultaneously with N competitors,
or 0.001 when the move allows to approach to the nut.
The move with highest score is chosen as a solution.
If I had it to do all over again, here's what I'd try:
I would spend more time walking in the park full of squirrels.
I named my squirrel belka because ...
I'm Russian. "Belka" is a "squirrel" in my native language.
Where do you live? do for fun? do for work? innermost secret?
I live in Magnitogorsk (Russia, Urals).
For fun I write letters to the Russian "Computerra" magazine
(www.computerra.ru). My sin is that I cannot keep silence about
amazing things. So, 6 years ago two Russian boys read my article about
POTM in the magazine and became its champions. Sorry, my unfortunate
colleagues, I was a loser then, too. Remembering of that mistake, I'll
publish the article about current POTM only after its deadline ;-)
I'm a former C++ programmer who nowadays is forced to create programs
in F++ laguage (haven't heard about it? Don't worry: it's created in
Magnitogorsk! ;-)
This year my small family become larger -- now we have a pretty
daughter Alice (my wife Alyona sometime calls her "Belka", too ;-)).
_____________________________________________________________
nutcracker was submitted by Doug Beardsley (mightybyte)
nutcracker finished in position 05 and 43 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy nutcracker used for the SOLO POTM.
Nutcracker uses an algorithm similar to simulated annealing with
hand-tuned parameters to govern the probability of backtracking.
Describe briefly the strategy nutcracker used for the MULTIPLE POTM.
Run an evaluation function on each legal move and choose the best one.
If I had it to do all over again, here's what I'd try:
I'd probably try an ant colony optimization algorithm and use a
genetic algorithm to tune its parameters. I tried this a little, but
didn't put enough time into it to get it to work well.
I would also probably put more time into the multiple version. I
didn't really spend much time on it at all.
I named my squirrel nutcracker because ...
It just fit. I'm surprised nobody else took the name. I like double
entendres.
Where do you live? do for fun? do for work? innermost secret?
I live in Florida. I program computers for work and fun. I also
enjoy swimming, water skiing, snow skiing, and mountain biking.
_____________________________________________________________
CrazyNut was submitted by Alexander Sobol (Zovirax) at sobol-at-mccme-dot-ru
CrazyNut finished in position 48 and 02 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy CrazyNut used for the SOLO POTM.
First of all, if there are n nust total, the solution is a permutation of 1..n.
I use simulated annealing with launched few times, starting from best
solution found so far each time.
Annealing uses two major transformations:
first (quite standard one) - reverse (it takes a subpath and reverses it).
second (i found it working quite well) - greedy drop.
we choose i: 0 <= i < n at random and keep first i elements of the
permutation. The after i-th nut we go strait to the closest nut
(if there are few nuts at the same (minimum) distance, I choose
a random one.)
The probability of greedy drop increases with time.
I also used time-based cooldown (cool temperature faster if we are low on time).
I also save the best solution found and start from it at next step.
Describe briefly the strategy CrazyNut used for the MULTIPLE POTM.
I try all possible first moves and for each move record profit my
squirrel would get if all squirrels (including my own) choose a random
nut (closest with highest probability).
Then i make a move that is the best in average.
I also save latest squirrel position to avoid aimless moving back and forward.
If I had it to do all over again, here's what I'd try:
I MULTIPLE POTM i would probably leave same randomized startegy, but
would search moves of my squirrel deeper.
I named my squirrel CrazyNut because ...
I do not know :)
Where do you live? do for fun? do for work? innermost secret?
I live in Moscow, Russia.
For fun i read books, play chess/chess variants, listen to
jazz and classical music
_____________________________________________________________
Abert was submitted by Doug Jones (dajones)
Abert finished in position 46 and 05 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy Abert used for the SOLO POTM.
The main method is 3 Opt local search. A random list of nuts is generated in
the order they are to be collected. The local search tries each combination
of 2 or 3 nuts. The list is broken into pieces at the selected nuts and
all possible recombinations are tried to find a list with a smaller number
of moves. A new random list is generated when a local minimum is found.
This continues until time runs out or nNuts^2 random starts have been tried.
Branch and bound is used instead of local search if the number of nuts is
small. This was done mostly so that the local search code didn't have to
deal with degenerate cases.
The location of the first nut on the best path and the cost of the best
path are saved between moves and used to initialize the local search
(if the nut still exists). The random number generator seed is changed
in this case so that different starts are tried.
Describe briefly the strategy Abert used for the MULTIPLE POTM.
A heuristic is used to calculate a table of expected values for each nut
as a function of the number of moves used to reach it. The expected value
is 1 if my squirrel reaches the nut first. The value goes down as more other
squirrels can reach the nut in the same number of moves. The value goes
down more for each additional move the other squirrels are allowed.
A recursive search is performed to find an ordered list of nuts with maximum
expected value. The recursion is cut off whenever the expected value of a
nut is less than the largest expected value that could be obtained for that
nut. A small fraction of the value of each nut not visited due to the
cut off is added to the total expected value of a given list. This tends
to cause the starting move to be toward the side with the most nuts.
If I had it to do all over again, here's what I'd try:
I would probably do the same thing.
I named my squirrel Abert because ...
Abert is a species of squirrel that live near me.
Where do you live? do for fun? do for work? innermost secret?
I live in Evergreen Colorado. I hike and ski in the back country for fun
and write software for AT&T.
_____________________________________________________________
CocoNuts was submitted by Pascal
CocoNuts finished in position 45 and 09 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy CocoNuts used for the SOLO POTM.
The solo POTM uses Keld Helsgaun's code LKH-1.3, which is
an efficient implementation to solve the traveling salesman
problem, based on the Lin-Kernighan algorithm. So, if my
squirrel gets good results, credits should go to him, and
not to me.
http://www.akira.ruc.dk/~keld/research/LKH/
I had to modify his algo a little to adapt it to the current
situation (we want an open path, with a fixed starting point).
I use LKH to compute "good" optimal tour for the nuts, then
try to find the optimal point where to cut the cycle and start
our tour. This adapted cost is not only used at the end, but
also directly in LKH (not as much as I would have liked though),
in order to find better solutions. I compute a tour on the first
move, then store it in a temp file for further moves.
Describe briefly the strategy CocoNuts used for the MULTIPLE POTM.
The multiple POTM uses a simple strategy: find a nut we can
go to in shorter or same time as some other squirrels. In
case of multiple possibilities, choose the nut which will
give most points after splitting, and choose the nearest if
there are still multiple possibilities.
If we cannot reach a nut before or at the same time of
someone else, go towards the gravity centre of all remainings nuts.
If I had it to do all over again, here's what I'd try:
Perform a deeper search in multiple mode, using some variant of min-max
algorithm. In the beginning of a game, it might be more interesting to
avoid taking one of the closest nut with everybody else, and just head
for a further one, so that afterwards you are one or two steps in
advance on all your competitors, and you can grab a lot of nuts alone. A
deeper search should be able to find those cases.
And, of course, code the traveling salesman problem myself !
I named my squirrel CocoNuts because ...
Just tried to find a stupid name ;-)
Where do you live? do for fun? do for work? innermost secret?
I am living now in Aarhus, Denmark (but I'm French), working as an
assistant professor in computer science.
And my favourite hobby is to keep my innermost secrets... secret
______________________________________________________
warhole was submitted by Pascal Alfadian Nugroho (dirk_sinner)
warhole finished in position 43 and 16 on POTM1 and POTM2.
________________________________________________
Describe briefly the strategy warhole used for the SOLO POTM.
Describe briefly the strategy warhole used for the MULTIPLE POTM.
Both use a simple strategy, scoring each nuts based on
its distance from me and other squirells, & the
density of nuts nearby.
If I had it to do all over again, here's what I'd try:
I don't think I would do it all over again
I named my squirrel warhole because warhol (from "Andy
Warhol"), added with e for an anagram.
Where do you live? Indonesia
do for fun? yes
do for work? no
innermost secret? I'll never give it to you :)
_____________________________________________________________
chipmonk was submitted by Robert Nix (rpnix)
chipmonk finished in position 39 and 20 on POTM1 and POTM2.
_____________________________________________________________
Describe briefly the strategy chipmonk used for the SOLO POTM.
For the solo attempt, my goal was to try to clear quarters of the board,
starting with the most populated quad, being sure to work the corners,
and moving within these parameters to the closest possible nut on each
move.
Surprisingly, even with several changes to the algorithm, the best I've
done to date on the test board is 73 moves. With that said, my main goal
wasn't really the solo board; it could be brute forced by calculating
the "perfect" solution via exhaustive spanning of the paths, and
probably several better methods. I wanted to evaluate my area of the
board, rather than trying to build trees of possible solutions. In any
case, I was much more interested in the Multi contest....
Describe briefly the strategy chipmonk used for the MULTIPLE POTM.
This was the problem I found to be really interesting. In the end, I
followed several main principles:
For both solo and multi, my first step was to calculate the "squirrel to
nut" distances for each nut. I kept track of my distance to each nut,
along with the closest competitor's distance to the nut. The one thing I
didn't see a need for was any sort of two dimensional array to represent
the board. It would have been wasteful and totally unnecessary.
Easiest of all: If you're next to a nut, and it doesn't compromise any
other goals, get it, even if you have to share. There just weren't
enough moves in the 15 x 15 board to stand on high principles, and I
didn't feel that the larger boards would be much more forgiving.
Next: If you find yourself stacked with a bunch of squirrels, then
chances are you're all going to be traveling together unless you take
some alternate action. I added a tuning parameter (called "panic") and
if there were this many squirrels in the stack, I picked a nut other
than the closest to chase after. My thought was that hopefully, most of
my stack-mates would chase after the closer targets.
Next: If you can get to a nut before anyone else does, then head for it.
In the end, I weighed this against the time it would take to get there;
if you are six moves away, it probably isn't wise to get the whole nut,
and possibly sacrifice one or several other partial ones. For purposes
of fine tuning, I included a parameter to set this distance, called
"greed".
If none of these apply, then I head for the closest possible nut, hoping
to at least share in the meal.
If I had it to do all over again, here's what I'd try:
Due to problems beyond my control (i.e. an unexpected stay in the
hospital) I ran out of time, but my last thought had been to add code to
look at the board one move ahead whenever I had multiple choices that
seemed equally good. i.e. If I was next to two nuts, then which might
place me in a better position on the next move. This would have involved
"drawing" an eight square box around each squirrel, and then checking if
one move might put me in a position to get an unshared nut, where the
other move might not.
I named my squirrel chipmonk because ...
Growing up, we didn't really see many squirrels, but always had
chipmonks around. It seemed to fit the theme, and conjured up a vision
of a cute little guy trying to compete against the other big, evil squirrels.
Where do you live? do for fun? do for work? innermost secret?
Originally, I was from Indiana, but we relocated to the frozen north
five years ago. We now reside in Minnesota, very near the Mayo Clinic.
Other than programming, and working with IBM mainframes, I enjoy fly
fishing and photography. (The eagle icon used in the forum is one of my
photographs.) In real life, I work with IBM z/OS, zLinux, WebSphere and
several other products, providing support and services to the
development team and users at the Mayo Clinic.
_____________________________________________________________
BlackAdder_04 was submitted by Jan Doornaert (BlackAdder)
_____________________________________________________________
Describe briefly the strategy BlackAdder_04 used for the SOLO POTM.
The "strategy" is rather easy to describe:
* DO
* look for the best of a few random paths
* optimize this best-of-random path (replace a stretch with a
better stretch is possible and fix the rest of the path)
* REPEAT UNTIL TIME IS UP
Describe briefly the strategy BlackAdder_04 used for the MULTIPLE POTM.
* Try to predict what step the others squirrels will take
* For all possible steps my squirrel might take, determine the one
which maximizes some metric (based on my chances to get
to another nut before the rest)
If I had it to do all over again, here's what I'd try:
* Look for another job - one that allows me to spend some time doing
what I *really* like to do: programming stuff!
I named my squirrel BlackAdder_04 because ...
* BlackAdder is my favorite nickname - and 04 is the fourth
iteration of my algo...
* Disappointing? Then have a look at the TV-series ;-)
Where do you live? do for fun? do for work? innermost secret?
* I live in a house (where else?) in Ghent, Belgium.
* I like to program (surprise!), reading SF, tinkering with old
(read: ancient) PC hardware.
* For a living, I try to program in PL/SQL at Radar Automation
(http://www.radaraut.com - promise not to laugh!).
* As for my innermost secret(s), I'd like to keep 'm that way.
Secret. And mine. Now **** off!
_____________________________________________________________
DeepNut was submitted by Enric Capo (DeepButi)
_____________________________________________________________
Describe briefly the strategy DeepNut used for the SOLO POTM.
Since the problem is a very well known and studied and
since I'm not an expert coder (just my second C program)
I decided to test something verysimple: find the best path
to the n nearer nuts. With my (poor) code I tested until n
fits on 60s. and launched it at n==15. Curiously enough,
on the test board, n==10 produces th best result :).
Describe briefly the strategy DeepNut used for the MULTIPLE POTM.
a) Forget about nuts with a squirrel next to it,
b) Forget about nuts in the center squares (the ones that
will becovered by the initial squirrels)
c) Compute the sum of distances between nuts plus the
distance to myself... and go to the smallest sum nut,
allowing a small detour to catchany nearby nuts.
d) If there is a free nut (one that I can reach before
any one else) go for it without any detour allowed.
With about 50 squirrels, getting a whole nut is a must!!
If I had it to do all over again, here's what I'd try:
I did it just for fun, so I'm satisfied with it.
I named my squirrel DeepNut because ...
DeepBlue plays chess, DeepButi plays a local card game
(it's the name of arobot of mine, try it at www.butinet-org),
... and DeepNut catches nuts, easy eh?!
Where do you live? do for fun? do for work? innermost secret?
St Cugat, Catalunya. Play board games. Computing consultant.
_____________________________________________________________
peas was submitted by Stefan Foerster (HotblackDesiato)
_____________________________________________________________
Describe briefly the strategy peas used for the SOLO POTM.
First a word about the 'nuts problem' - as a problem very
closely related to the symmetric travelling salesman problem
it is of course NP-hard, i.e. if we accept the usual assumption
that NP<>P, then we won't find any algorithm finishing within
polynomial time (run time = polynomial of the size of the input).
That's discouraging.
This also means that for very large problems it is very
difficult to prove that a solution is optimal. One can only
prove upper and lower bounds.
But there are numerous fast and more or less good heuristics
that find approximations. These can easily be adapted for
this problem.
'peas' successively calls the following heuristics (as long
as it is still within the 60sec limitation:
* Christofides
* Nearest Neighbour
* Spanning Tree
* Nearest Farthest Insert [that's something I created]
* Cheapest Insert
* Farthest Insert
* Sweep
After each of these start heuristics a sequence of three
improvement methods is used:
* 2-NODE-OPT
* 3-OPT
* 4-OPT
A good reference for all these algorithms is (in German):
http://www.math.tu-berlin.de/Vorlesungen/SoSe03/GuNA/SkriptADM-I.pdf
I don't use the above algorithms for each and every move.
'peas' calculates the tour during the first move and stores the
result in a tmp file. The first recalculation of the remaining
tour is done after about 125 moves.
The bad thing is that my method of checking the 60s limit doesn't
work on the final boards :-(( More testing in that direction would
have been better...
A comment about the C/C++ compiler on Fred's machine: The hosting
company 1&1 probably still uses Debian 'Woody' with a relatively old
2.95 version of gcc. That made testing quite difficult for me in the
beginning because program versions running perfectly on my Linux
box crashed on his. I found out that there must be differences in
the stack handling of gcc 2.95 and gcc 3.3.x when using recursive
functions [I wanted to use a recursive function to test all possible
permutations in the endgame but I had to give up]. During my desperate
trials to get a squirrel running on Fred's machine I also changed from
dynamic memory allocation to static arrays. This resulted in very
big differences of the size of the binaries produced: On 1&1's machine
about 350kB, on mine only 79kB. I really hope that Debain finally
releases Debian 'Sarge' and that 1&1 quickly upgrades to it.
Describe briefly the strategy peas used for the MULTIPLE POTM.
1) 'peas' reads the positions of all nuts and squirrels from
the input file. If 'peas' finds the initial position
(all squirrels in the middle of the board) then 'peas'
deletes the tmp file that may still be hanging around
from the last battle.
2) If there is a tmp file then 'peas' reads the coordinates
of the target nut and looks if it is still available,
that the distance to the nut is == 1 or other squirrels
are more than 1 step away - then 'peas' continues to go
for it i.e. sets 'target' to TRUE and stores the 'target distance'.
3) 'peas' then looks for nuts that no other squirrels can reach
within the same number of moves - these are very valuable
nuts because we don't get fractions of nuts, we get the whole nut !
If it finds more than one it of course takes the nearest one.
If one such nut is found, then if (target==FALSE) or (target==TRUE
and the distance to it is less than or equal to the 'target distance')
then 'peas' goes for it + GOTO 6)
4) For every nut (that a realistic goal is) and then looking only
for squirrles having the same or less distance to the respective nut,
'peas' computes:
FACTOR1 * SUM_NEARERSQUIRRELS(DIST(NUT-YOU)+1-DIST(NUT-SQUIRREL)) * (Num_Nearer_Squirrels-1) +
FACTOR2 * DIST(NUT-YOU) * (Num_nuts-1) +
FACTOR3 * SUM_OTHERNUTS(DIST(NUT-OTHER NUT))
A 'realistic goal' is a nut that has no squirrels within 'give up distance'
(that I have set to 2), unless 'you' is also in the vicinity of the nut.
The first part of the formula is a kind of punishment function, i.e.
the nut's value gets increased the more other squirrels are there and
the nearer they are. The second part simply takes into account that the
nearer a nut the faster it can be eaten... The third one helps to
find accumulations of nuts. The problem is the calibration of the factors FACTOR1-3...
5) 'peas' chooses the nut with the smallest value. If there is more than
one nut with smallest value, 'peas' takes the nearest one.
6) In case a valid target had been read from the tmp file, 'peas' tests
whether the newly calculated target is nearer to 'you' than the old one.
If that's the case then 'peas' forgets about the old target and goes for the new one.
7) 'peas' calculates the next move to reach the target and creates a tmp
file with the target coordinates.
8) 'peas' makes a final 'en passant test'. If there are one or more nuts
directly next to 'you' then it takes the one that is nearest to the
previously chosen target.
9) 'peas' prints the move to stdout
If I had it to do all over again, here's what I'd try:
POTM1: I'd try to implement the Lin-Kernighan algorithm
POTM2: Maybe I should have implemented several simple
algorithms which I then could have uses to extrapolate the
most reasonable next moves/targets of the other squirrels.
Game theory...
I named my squirrel peas because ...
... collecting nuts and counting peas is not so different...
Where do you live? do for fun? do for work? innermost secret?
I live in Aschheim, Germany (near Munich). Most of my spare time
belongs to my family and my house. But of course I am a computer addict.
I am mathematician/actuary. I work with Swiss Re Germany.
Innermost secret... won't be disclosed
_____________________________________________________________
squirrel2 was submitted by Michael Jørgensen (MJoergen)
_____________________________________________________________
Describe briefly the strategy squirrel2 used for the SOLO POTM.
That's a tough question! Basically, the program selects which nut to head
for. It considers all nuts in turn, and for the remaining nuts it just
selects the closest nut. That way it can estimate the total number of moves
needed to catch all nuts, depending on which nut is chosen first. Then the
program simply selects the nut that leads to the fewest number of total
moves. If two nuts have equal value, then it goes away from the center, thus
providing a bias for the outlying nuts.
Describe briefly the strategy squirrel2 used for the MULTIPLE POTM.
Exactly the same as above. It pays no attention to the other squirrels!
If I had it to do all over again, here's what I'd try:
For the SOLO POTM I'm very satisfied. Perhaps an extra level of look-ahead.
For the MULTIPLE POTM I spent long hours trying to come up with a better
strategy, but I didn't find anything satisfactory. Basically, I wanted to
take the other squirrels into consideration, for instance by going in a
direction completely different from the rest of the group. But I made some
experiments, and I found that on average my present squirrel2 fared much
better than the more "intelligent" versions.
I named my squirrel squirrel2 because ...
Simply due to lack of imagination.
Where do you live? do for fun? do for work? innermost secret?
I live in Denmark. I work as a software designer in the telecom business. At
home I play with my kids and practice Tai Chi. My innermost secret? Well,
I've always dreamt of becoming a rock star!
_____________________________________________________________
thyra was submitted by Olaf Jansen-Olliges (o.jansen)
_____________________________________________________________
Describe briefly the strategy thyra used for the SOLO POTM.
it is the simplest algorithm to collect nuts. take the one which is the
nearest :-( I submitted it first only as a test.
Describe briefly the strategy thyra used for the MULTIPLE POTM.
no differences
If I had it to do all over again, here's what I'd try:
1.) collect at first nuts which can't be reached by another Squirrel
2.) calculate short ways
3.) start somwhere with high density of nuts
I named my squirrel thyra because ...
the last potm entry was named like my 1. daughter (rayka) and now we have 2
daughters -- so the choice was very easy. But last time i had much more time.
Where do you live?
Sarstedt in the near of Hannover - Lower Saxony - Germany
do for fun?
listen music - playing with the children - LINUX
_____________________________________________________________
the_selfish_gene was submitted by Marcel van Apeldoorn (mvapldrn)
_____________________________________________________________
Describe briefly the strategy the_selfish_gene used for the SOLO POTM.
The program uses a technique (written from scratch) from genetic programming.
The program starts with an initial population, each individual in the
population has a chromosone consisting of a number of genes equal to the
number of nuts on the field. The chromosone represents the individuals order
of nuts to collect. Each individual is assessed for fitness. The fitness
function for the SOLO POTM exhibits LAZE_GENE behaviour and is the inverse of
the distance of the solution.
Each individual is given the opportunity to reproduce based on its rank;
a survival of the fittest principle. Reproduction can involve copying the
father or mother, crossover (part father, part mother) and based on
random chance; mutation. A new population is created this way.
This evolves for a fixed amount of time. When time is up, the best
gene is used for the next step.
(On my machine AMD64 3400, a population size of 80 evolves for 63000
generations in 50 seconds in the POTM 15x15 system test to produce
distances of between 62-64 steps)
Several tuning possibilities have been applied; o.a. creating the initial
population is based on an initial assessment of the field, optimizations
in the gene have been applied, twin removal, storing the population at the
end of each step in a file in order to get a better initial population
for the next step, etc.
Describe briefly the strategy the_selfish_gene used for the MULTIPLE POTM.
The program is _identical_ to the SOLO POTM with the single exception of the
fitness function. The fitness function exhibits SELFISH_GENE behaviour.
A chromosone is rated better if it collects high valued nuts (i.e. nuts
that are located close to lots of other nuts) early in the route, and
more early than other squirrels on the field.
If I had it to do all over again, here's what I'd try:
The performance of a genetic algorithm improves when it gets 'trained'
or tuned to the situation. I could have tuned it a bit better to the field
layout (i.e. different settings for fields with lots of evenly dispersed nuts,
lots of clustered nuts or only a few nuts, etc)
I named my squirrel the_selfish_gene because ...
...of Richard Dawkins book called 'The Selfish Gene' which I was reading
when I got the invitation for the POTM. After a short introduction into biology
and DNA/genetics in specific, he introduces the gene-centered view of evolution;
the selfish gene. Dawkins shows that how fundamental axiom of natural selection
(that the genes best at surviving and reproducing will eventually spread through
the gene pool) leads directly to the selfish gene and the behavior exhibited by
nearly all animals including humans.
Coincidence or not, the POTM/nuts competition looks a lot like one of the famous
competition he (Dawkins) describes in his book. It's called the Prisoner's Dilemma.
His conclusion was more or less ;-) 'There is no winning strategy. Whether a
strategy is winning or not depends entirely upon the other strategies'.
Does this ring a bell?
So I decided to use a genetic algorithm for both POTM competitions and trained
it to be LAZY (shortest path) when alone in a field of nuts and SELFISH when
with multiple squirrels in a field of nuts. Obviously I had to call my entry
'the_selfish_gene'.
Where do you live? do for fun? do for work? innermost secret?
I live in the Netherlands (Heerhugowaard, 40 km north of Amsterdam). Lately
I do POTM for fun, but am also involved in Archery and other geeky stuff
involving computers (programming and games)
I'm a research engineer at the National Aerospace Laboratory, responsible
(with a team of 7) for desiging, producing and maintaining software for the
real-time air-traffic control radar and tower simulators.
My innermost secrets?? I'm 35 years old and finished playing Half-Life 2
on hardest level in 2 weekends...
_____________________________________________________________
alariq_v0_2 was submitted by Sergey Beloshitsky (snowman)
_____________________________________________________________
Describe briefly the strategy alariq_v0_2 used for the SOLO POTM.
i was using a kind of genetic algorithm
Describe briefly the strategy alariq_v0_2 used for the MULTIPLE POTM.
at this stage it is same as in SOLO POTM
If I had it to do all over again, here's what I'd try:
improve some pieces of code for speed and tune algorithm
parameters for more precisious(?)
I named my squirrel alariq_v0_2 because ...
arariq is what i use when my main nick(snowman) already used
also it is the name of one of the teleports in Uukrul
game(old x8086 RPG game)
Where do you live? Ukraine, Kiev
do for fun? fishing
do for work? programming
innermost secret? can't make myself come on time
_____________________________________________________________
nutty_professor was submitted by Raghavan Viswanathan (rambo)
_____________________________________________________________
Describe briefly the strategy nutty_professor used for the SOLO POTM.
The strategy was to build a Minimum Spanning tree(MST) with the "YOU" as one
of the Vertices and then simply follow the MST. I got into issues with the
Multiple invocations not getting the same MST. I resolved the problem by
ordering the vertices starting from (0,0) as 1, 2 ,3 etc. This gave me
the Same MST across multiple invocations. My program can actually give
ALL the moves at One shot by using "-a" option.
Describe briefly the strategy nutty_professor used for the MULTIPLE POTM.
Damn!. Did not get time to do this. I simply pretend that there is NO
squirrel Apart from me. I just IGNORE squirrel lines. I know it is
suicidal coz I could be chasing mirages.But, hey such is Life.
If I had it to do all over again, here's what I'd try:
I wasted some precious time pursuing Genetic Algo.
I would not do that in retrospect.
I named my squirrel nutty_professor because ...
Just a PUN on a movie by the same name.
Where do you live? do for fun? do for work? innermost secret?
I Live in Bangalore, India. I play with my Kid - Pranav for Fun. I am a
Technical Manager at the Embedded and Product Engineering Division in
Wipro technologies.
I have been telling my inner most secrets each time I participated in
POTM. I don't have em anymore.
_____________________________________________________________
pnut was submitted by David Wales (mongbei)
_____________________________________________________________
Describe briefly the strategy pnut used for the SOLO POTM.
(please inclued any references you think might be of value!)
'Go to the nearest' :-( Ha! - never got round to submitting a second version.
Describe briefly the strategy pnut used for the MULTIPLE POTM.
Same as solo strategy.
If I had it to do all over again, here's what I'd try:
I'd try harder!
I named my squirrel pnut because ...
The p is silent.
Where do you live? do for fun? do for work? innermost secret?
Shanghai, Travel, Seismic data visualization, errrr...
|
