This is the last email on Loyd's Dilemma ... I hope it was fun
(complaints >/dev/null)! I'm off to think up the NEXT one, coming
within a few weeks with luck!
Beware of long mail .... but there ARE gems buried!
Even if you don't study the whole thing, you might
want to scan the first four or five writeups!
Thanks to all the contributors!!!
The attached mail is the collection of write-ups I received. As usual
they are mostly unedited (only personal POTM-master insults were removed).
They are provided in order of finish (more or less).
=Fred
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
======================================= shufflemania =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
shufflemania 25/94 25/89 25/98 25/90 25/82 125/0453/062 2928770ms
=================
shufflemania was submitted by Stan Peijffers
at hvgtw!hvssa01!speijffe@attmail.att.com
=================
HOW DID shufflemania ATTACK THE PROBLEM (in general)?
Shufflemania is based on hybrid search. It contains 2 search algoritms
that (recursively) call each other.
The first search algoritm is an Iterative Deepening A* (IDA*) Algorithm.
This is a well known algoritm initially developped by Korf
(ref Artificial Intelligence 27 (1985)).
It has the following characteristics :
- depth-first search using an evaluation function f*
f* = g* + h*
where g* = number of moves sofar
h* = (underestimate of the) number of moves to reach goal
= sum of Manhattan distances
- looks for an optimal solution
- does not eliminate duplicate positions
- requires little memory (it is a recursive algoritm that only uses
stack space)
- rather CPU intensive
The second search algoritm is a variant of the A* algorithm
(as described in any book on heuristic search).
It has the following characteristics :
- heuristic search using an evaluation function f* that systematically
overestimates the distance to the goal
f* = g* + a.h*
where g* = number of moves sofar
h* = (overestimate of the) number of moves to reach goal
a = factor that increases weigth of h* as the search goes deeper.
Note that the original A* algorithm works with a h* function that
always UNDERestimates the distance to the goal and has an "a" factor
that DEcreases the weight of h* as the search goes deeper.
- The advantage of using an h* function that does not have to
underestimate the distance to the goal (typically h* is the sum of
the Manhattan distances) is that the h* function can be tailored
to steer the search into a particular direction.
The h* function used is the following :
h* = sum over all tiles of "long" distances,
where "long" distance is dependent on
the number of moves (as opposed to distance) to make to get the
tile to the goal.
This dependency takes into account the actual distance to the goal,
and this dependency is non-linear, such that higher distances
are favored more than lower distances. (It is indeed rather wasteful
to spend time in placing tiles at the correct place when there are
still many tiles far away from their final place).
Another dependency which is factored in is the degree of mobility
of a tile. There are 3 different levels of mobility : corner tiles
(A,E, etc), border tiles and central tiles. The dependency on the
h* function is such that corner tiles are more mobile (i.e moved
more quickly) than border tiles, which are more mobile than
central tiles. The net result of this is that the algorithm will
first of all attempt to get corner tiles in place before border
tiles, before central tiles.
- does not strictly expand nodes on a best-first basis.
- does not use a single queue, rather a set of queues.
- performs a substantial amount of pruning
+ solutions that deviate too much from the best solution sofar
are pruned.
+ solutions that will not be able to improve on the currently
best solution are pruned
(To this end a second h* function based on Manhattan distances
is maintained as well, but this second h* function does
not steer the search. It is only used for pruning).
- When memory becomes full, the most-promising position is used
as the starting point for a new search.
As a consequence of the above limitations :
does not search for optimal solutions
(but recognizes an optimal solution when it sees one).
- does not eliminate duplicate positions
(only avoids sequences of moves that would generate duplicates
such as lr, du, etc)
- requires a lot of memory for the queues
- prime characteristics of the algoritm are : speed and the possibility
of generating long sequences of moves leading to (sub)optimal
solutions.
These 2 algoritms are complementary from a CPU and memory usage
viewpoint.
The solution that was adopted is a hybrid search based on the above 2
algoritms where the IDA* algorithm is used at the top of the search
tree and the A* algorithm used at the bottom of the search tree.
This approach has been mentioned in "Heuristics : Intelligent Search
Strategies for Computer Problem Solving" By Judea Pearl.
[Note : an interesting article describing a hybrid search method with
A* used at the top and IDA* used at the bottom is
"Effective use of memory in iterative deepening search" by
Sarkar, Chakrabarti, Ghose, De Sarkar - Information Processing Letters
42(1992).]
The depth d0 at which the IDA* algoritm stops and hands over control
to the A* algorithm is fixed and is a linear function of the
"complexity" of the initial problem (complexity = number of misplaced
tiles). The upperbound for d0 is 30.
This means that in practice problems with an optimal solution less than or
a little over 30 moves will always be found.
In a number of instances the A* algorithm calls the IDA* algorithm
(and the associated A* algorithms) again
lower in the search tree. The IDA* algorithm is then called
at the point where the next higher IDA* algorithm was stopped.
This happens in 3 cases :
1. A* detects a new solution which is an improvment over the currently
best solution. IDA* is called to see whether it is not possible to
still improve the solution.
2. A* has found too many "promising" intermediate solutions (i.e queue
overflow). This is an interesting situation in which an IDA* search
may uncover good solutions.
(Note that in "normal" situations the queue overflow will not
happen because of the substantial amount of pruning in A*).
3. A* has not found a solution at all. i.e all examined positions
are worse than the starting position.
This happens e.g in cases where all tiles are in place except
for 2 that need to be swapped.
The maximum depth of recursive calls to the IDA* algorithm is limited
to 4.
Some other characteristics of the program :
- The algorithm stops when the 10 minute limit is reached
(unless an optimal solution is found by either the IDA* or the
A* algoritm).
A time check is made at anytime the A* algorithm is started.
- The handover point between IDA* and A* is not exactly d0, but
the first "negative" move before d0 is reached. This is done
to avoid working with locally optimized solutions detected by
IDA*.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Surprisingly one of the more difficult parts of the program turned out to
be the administration necessary to print out the final solution.
This was rather difficult because of the recursivity (at 2 levels)
and the fact that each algorithm detects parts of the solution.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
Work in Intl 5E development in Hilversum, Netherlands (AT&T-NSI).
Maybe more importantly for this contest : I wrote a chess program
a couple of years ago, so I had some experience with heuristics.
=================================================================
======================================= scrambloyd =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
scrambloyd 25/86 25/87 25/94 25/84 25/78 125/0429/065 1050890ms
=================
scrambloyd was submitted by Bill Tanenbaum at tan@intgp8.att.com
=================
HOW DID scrambloyd ATTACK THE PROBLEM (in general)?
First and foremost, scrambloyd has an evaluation
routine that takes any position and returns an integer
that is an estimator of the number of moves needed to reach
the perfect position from the given position.
If the evaluation routine were perfect (i.e if its return
value were a monotonically increasing function of the actual
number of moves required), all the program would have to do
to produce the optimal solution is, one move at a time, chose
the next move as one of those that gives the smallest return value.
What could be simpler?
But alas, the evaluation routine is imperfect. So the
program first makes all possible first moves, storing each
possible position (including move history) that can occur after
one move. Then the program loops through each of those positions,
making every possible move (except it skips any move that reverses
the previous move), and storing each possible position. It now
has stored every position that can occur after two moves.
The positions that occur after one move can now be discarded.
Now from the two move positions we can calculate all possible
three move positions, etc. The idea is to keep this up until
we reach the perfect position. If this were possible,
we would have an optimal solution.
But alas, the number of positions goes up exponentially
with the number of moves, so we cannot keep this up too long.
So, at any number of moves, I keep no more than 8000 positions (8000
was determined by experimentation). When the number of positions
rises above 8000 or so, the evaluation function is applied
to all positions, and positions with the worst evaluation
are pruned to bring the total below 8000. (This means that the
solution found is no longer guaranteed to be optimal.)
One complication is that the same position may
appear multiple times after the same number of moves, since
it is possible to arrive at the same position by different paths.
If this were left unchecked, many fewer than 8000 actual positions
would eventually fill up the 8000 available slots. So at every
number of moves, there is an elimination performed on duplicate
positions, with the duplicate with the fewest transport moves
being saved. A hashing on the full position is necessary to do
this in time linear in the number of slots. For solving most
squares, this pruning is not necessary. However, some
maliciously chosen squares cause infinite looping if this
pruning is not done.
A good evaluation function itself is critical.
I won't describe it here. If interested, look at the source code.
HOW DID scrambloyd "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
Not necessary. By the nature of the program (one move at a time),
the first solutions found were the shortest ones that were going
to be found. So the program simply picked one with the fewest
transport moves.
HOW DID scrambloyd AVOID POSITIONS THAT WERE EVALUATED PREVIOUSLY?
Except for not making any move that reversed the previous move,
nothing was done to explicitly avoid such positions. They are
inherently suboptimal, and are weeded out naturally.
HOW DID scrambloyd DEAL WITH "loops" OR "impossible" END POSITIONS?
It didn't have to deal with loops explicitly, since they
are inherently suboptimal.
I don't know what an "impossible" end position is.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
My program is "stupid" in the sense that it doesn't try to "solve"
the square by finding solutions and evaluating them.
It simply tries all possible moves until it finds a solution.
By going one move at a time, the first solution is the "best"
solution. The evaluation function is used only for pruning.
The evaluation function evaluates positions only. It has
no concept of solutions.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
Write software, mostly.
=================================================================
======================================= dilloydemma =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
dilloydemma 25/104 25/95 25/112 25/104 25/82 125/0497/078 2985100ms
=================
dilloydemma was submitted by Bob Ashenfelter at ash@hotsoup.att.com
=================
HOW DID dilloydemma ATTACK THE PROBLEM (in general)?
Because different squares are best attacked with different techniques,
several techniques were used with lots of variations of one of them
rather than spending all the time on just one attack. When time ran
out the best solution was printed.
The first technique uses priority lists. There is a list for the order
in which the tiles should be placed and another for where to place them.
Of course, the final few tiles must be initially placed in "wrong" pos-
itions and moved to their final positions at the end, so the lists are
slightly longer than the number of tiles. This, however, is too rigid a
procedure so there is a third list which specifies a range of tiles in
the other lists that are eligible to be placed when the first n tiles are
in place. There are several situations where either of two symmetrically-
placed tiles could be placed first (e.g. either 'T' or 'X' will be in the
lower right corner until the last move). In such cases the first to arrive
is fixed and the lists are dynamically reordered if necessary. For each
move, the procedure is as follows: If an eligible tile is in the center,
the empty space is moved toward its listed position. When the empty space
arrives, a transport move places the tile and it is then fixed in place.
If no eligible tile is in the center, then the highest priority tile is
moved toward the center by repetitively moving the empty space toward the
tile and then transporting it back to the center. (This part of the alg-
orithm leaves room for improvement!) At any point where two possible moves
are judged equally good, the choice is made randomly. This technique can
find several hundred solutions per second which is a good thing since it
may require thousands or more random solutions to find the best that it
is capable of.
The second technique is an exhaustive search. For each position, all
possible moves are evaluated avoiding only those which move out of the
square, or backtrack ('r' after 'l', etc.) or transports which are the
same as regular moves or move nowhere. With about 3.3 eligible moves
per position, the number of positions grows exponentially with the depth
of the search and there is only enough time to search about 12 moves deep
(and that assuming all time is spent on a single solution). The tricky
part is evaluating all those positions to choose the initial move which
leads to the best one. I used a 25-by-25 array of penalty values for
each tile at each position. How to choose this array? One choice is the
distance from each tile to its final spot, but this is good only for very
easy squares. A more generally useful penalty array has the values for
the various tiles weighted according to their positions in the priority
lists above. It is also necessary to arrange the penalties of the 'S',
'T' and 'X' so they can be appropriately out of place with only a small
penalty. But how to optimize it? I considered running an optimization
program but with ~600 variables and many seconds to evaluate each choice,
it seemed like it would be a waste of time. Probably I should have tried.
I ended up with a handful of arrays generated by hand, each of which did
best for certain squares and worse for others.
So here is what the final version of dilloydemma does. First it tries a
shallow search looking to find a quick optimum solution in case the square
is "trivial". Then it runs off 100 priority-list solutions, as much as
anything to provide a limit on the number of moves since I always stop
a solution when it has used as many moves as the best solution so far.
Then it tries a moderately deep search (6 moves) looking to solve an "easy"
square. Next it runs the priority-list solver 10,000 times which will
likely find a solution that is close to the best it can do. Then it runs
the exhaustive search solver for each of nine penalty arrays and for all
depths from one move up to however many it can do (usually 9) until 70%
of the time is used up. This is followed by a single search of depth
between 4 and ~10 depending on how hard the square is and with a penalty
function consisting of the fewest moves the priority-list solver takes in
two tries. Finally, it runs the priority-list solver until time has almost
run out, and then prints the best solution it found by any means.
Why so many different solutions? Because I can't predict which one will
do best on any given square. Even the results for the exhaustive search
for various penalty arrays do not correlate well for different depths and
the best result often does not come from the greatest depth.
HOW DID dilloydemma "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
As it reads in the square it adds up the minimum number of moves and trans-
ports that would be needed for each tile and if one of the early solutions
matches this, the program quickly terminates. But afterwards it doesn't
even bother checking and continues running for nearly the full 10 minutes.
HOW DID dilloydemma AVOID POSITIONS THAT WERE EVALUATED PREVIOUSLY?
It doesn't.
HOW DID dilloydemma DEAL WITH "loops" OR "impossible" END POSITIONS?
The priority lists were carefully fine-tuned to place and fix tiles in an
order that would always allow subsequent tiles to be placed. This would
have been harder without the transport move! It often does go into dead
ends but it can back out and with its random move selection will sooner or
later go the right way. Such backtracks are removed from the move string.
The exhaustive search often does get stuck in loops, especially for shallow
depths and/or simple-minded penalty functions. Such incomplete solutions
are terminated as soon as the move total exceeds the previous best.
The exhaustive search using the priority-list solver penalty function has
been observed to "hang" very occasionally after quite a few moves when
given a "tough" square, and so it terminates after 33 moves after which it
never seems to give the best solution anyway. I took a calculated risk
here since a hung program would not stop at the time limit, but it does
find the best solution for some squares. I did catch the interrupt signal
so I could print an answer when the program was terminated but this was
more for my benefit in running it. I don't know if Fred would be big-
hearted enough to accept such an answer, nor do I think he should.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Well, by now I've given away all the TRICKs and WHATEVERs, but I do have
a COMMENT:
I must say that I am surprised and a little disappointed with the final
test squares. They are all alike! All are based on word play with no
consideration of how easy or hard they are to solve. All have the empty
space at the lower right corner. Worst of all, they are all of similar
difficulty, neither easy nor representative of the very hardest. This is
in sharp contrast to the previous POTM where each final test was carefully
and cleverly chosen to be the best and most challenging example of each of
a number of different types of problem. I consider FOXY to be in this
company, but not the others.
I am also surprised that the final evaluation procedure was changed without
any prior notice. Not that I am complaining; if the results had been based
on FOXY alone, I would have dropped from second to third.
For what its worth, here is what I expected to happen: Realizing that only
a single final square would not necessarily sniff out the best program, I
anticipated that the final square would be relatively easy so that more
than one program would reach the GRAND FINALE. And then I expected to see
a variety of different kinds of squares. I fact, I was looking forward to
seeing what clever and unexpected challenges there would be. Perhaps one
or two would be easy, for example
+ABCD
GHIJE
FKLMN
QRSTO
PUVWX
which has every tile out of place but the answer is trivially obvious (to a
human, not necessarily to a computer program). And then something that is
rather simple but challenging and unobvious, for example, swap just the 'A'
and 'B'. Next, how about something fiendish that is designed to trap the
unwary, for example
FBCDE
KAGHJ
PLMIO
UQRNT
VWXS+
The solution (as far as I know) is "ddddrrrulluuurrrddddlllluuuu". Note
that you must move 7 tiles that are initially in their right places before
you start unscrambling the ones that are in the wrong places! You could
have put 6 tiles in their places with those 7 moves or better yet put 10
tiles in place with 12 moves, but then.... As you try to generate clever
squares with ever-larger solutions, you (soon!) get squares that a clever
program can solve better than your clever solution. Such problems, near
the boundary between the domains of very different optimum solution tech-
niques, would make excellent tests. Finally, there is the realm of problem
squares which I would designate CHAOS, at least from the point of view of
finding the best solution. The system test square and all of the final
squares appear to belong here, however I expected to see something designed
to have the longest possible solution. The toughest square I know is
perfection rotated 180 degrees.
How did I expect to do? Realizing that I was not as good at CHAOS as the
best (scrambloyd), I concentrated on getting the smaller solutions right.
I didn't really expect to recoup enough on the smaller solutions to over-
come the deficit from the larger solutions, but it was my only hope short
of wishing disasters (core dumps) on the others. In the end, second place
was better than I expected.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
Circuit design.
Bicycling, sailing, grow orchids, travel.
AT&T/Network Systems/GPN
No way...
=================================================================
======================================= slowmotion =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
slowmotion 25/112 25/99 25/116 25/110 25/96 125/0533/089 1260620ms
=================
slowmotion was submitted by Michael Strauch
at strauch@emmy.mathematik.uni-dortmund.de
=================
HOW DID slowmotion ATTACK THE PROBLEM (in general)?
"slowmotion" attacks the problem in two stages. The first stage moves
all outer tiles to their correct places, that means, it constructs a
square of the form
ABCDE
F---J
K---O
P---U
UVWSX .
The second stage solves the inner 3x3 frame without moving the outer
tiles any more. This gives a square of the form
ABCDE
FGHIJ
KLMNO
PQR*T
UVWSX ,
and this one can be solved easily by an "UP" and a "LEFT" move.
Let`s begin with the second stage. A 3x3 square is small enough to
find a minimal possible solution by constructing the directed graph of
all possible situations. The vertices of this graph are the possible
orders of the tiles (9!=362880 different), and two vertices are
connected by an edge if there is a move that transforms the
corresponding order of the first vertice into the order of the second
vertice. "slowmotion" runs a shortest-path-finding algorithm on this
graph giving an optimal solution for this partial problem.
For the complete square the method of the second stage would not work,
because one would have to store up to 25! different orders
(approx. 1.551121* 10^25), that would be a little bit too much time and
memory consuming. Therefore "slowmotion" uses another strategy for the
outer tiles. It moves one outer tile after another to it's place and
blocks every placed tile against further moving. Here occur two
problems: in which sequence should the tiles be moved; and how shall
the program move a tile to its destination?
The sequence of moving is determined in the following manner. First,
"slowmotion" generates a list of tiles that can be placed next. It has
to make sure that, for example, it does not place the tiles B and F
both before placing the tile "A" - otherwise A cannot be placed any
more. Then it counts how many moves are needed to move each tile of
the list to its destination. This is done in a backtracking manner for
the next five possible tiles. The tile that is choosen as the one to
be placed next really is the tile that gives the least number of moves
for all different possibilities of moving five tiles.
After placing all outer tiles, "slowmotion" has found a good, but
perhaps not best, order in which the outer tiles should have been
placed. Thus it tries to optimize this order by exchanging any two of
those tiles and looks if using this new order for the outer tiles
needs less moves than the old order. This step is repeated as long as
it improves the length of the list of moves.
How does the program move an outer tile to its destination? Lets first
describe how the program moves the empty spot to a given destination
without using any blocked tiles. This is done in a way similar to
stage two with a shortest-path-in-a-graph algorithm. Here the vertices
of the graph are the up to 25 possible positions of the empty spot,
where the blocked positions are not included. Two positions are
connected by an edge if there is a move "UP,"DOWN","LEFT","RIGHT", or
"TRANSPORT" that transforms position 1 into position 2. Using this it
is easy to move a tile to its destination while not moving blocked tiles:
a) block the tile to move
b) move the empty spot "in front" of the tile , that means: on
the position that lies in the direction where you want the
tile to be moved to.
(up to 2 possibilities, choose the one with less moves,
avoiding that you make it impossible to move the empty spot
any more.)
c) unblock the tile and move it
d) repeat steps a-c until the tile is at its place.
That is roughly the idea of what happens, but there are some special
cases that are important to mention. Perhaps it needs less moves to
bring the tile you want to move to the middle position, move the empty
tile to the destination position and transport. Sometimes this is the
only possibility to move, sometimes it needs more moves than moving
the tile directly to its place, and sometimes it needs less. Therefore
"slowmotion" tries both strategies and selects the better one.
HOW DID slowmotion "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
This question doesn't fit to my kind of solution, sorry. I tried a
completely different algorithm for the outer tiles using such a
scoring system, but until I increased the search depth to a level
where things got awfully slow, it got only solutions with more moves
than my algorithm described above.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Use more C++ :) Are you AT&T folks only C programmers? Give C++ a try.
***************************************************************************
* Michael Strauch * email: *
* University of Dortmund * strauch@emmy.mathematik.uni-dortmund.de *
* Department of Mathematics * *
***************************************************************************
=================================================================
======================================= O+PTM_rtll =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
O+PTM_rtll 25/116 25/115 25/128 25/100 25/92 125/0551/090 3000170ms
=================
O+PTM_rtll was submitted by Keith Vollherbst at keithv@mtgzfs3.mt.att.com
=================
HOW DID O+PTM_rtll ATTACK THE PROBLEM (in general)?
Fill one position with the correct tile at each step. Don't move a tile after
it's in the correct position. Keep a list of possible positions to
fill at the next step. Figure out the shortest sequence(s) that will move the
correct tile into each of the positions on the list. Make a list of the
shortest of these, and examine tile positions reached from each one. As a tile
is moved into position, examine nearby positions to see if they can be added to
(or in less common situations, need to be removed from) the list of possible
positions to fill at the next step.
Shoot for one of the tile ABCDE ABCDE ABCDE ABCDE ABCDE ABCDE
arrangement to the right FGHIJ FGHIJ FGHIJ FGHIJ FGHIJ FGHIJ
and then add a final move KL+MN KL+MO KL+MO KL+NO KL+NO KL+NO
of lluu, lulu, luul, uull, PQRSO PQRNS PQRNT PQMST PQMRT PQMRS
ulul or ullu. UVWXT UVWXT UVWSX UVRWX UVWSX UVWXT
This appoach seems to find a "reasonable" solution pretty quickly.
Unfortunately, my implementation takes a long time to find the best solution
this algorithm is capable of (and even that isn't good enough!). I didn't do
anything to score intermediate tile positions to try to search them in a
sensible order or even to determine if I had ever seen that position before.
E.g., if at a given step, I determined that the shortest possible sequence
to move a single tile into place had x moves and that there were y different
sequences of length x that did that, I examined all y of these (or at least
as many as I could in 10 minutes). The implication of all this is that I had
to get lucky with Fred's choice of boards and with the order I checked move
sequences.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Although not obvious from my results, I thought I had a pretty good algorithm
for finding the shortest sequence that moves a single tile to where I want it
to be. Basically, I initialized a data structure indexed by the current
position of a given tile and the current position of the blank (i.e., '+') with
pointers to positions from which the given positions could be reached.
Starting with a list of goal positions with the given tile in the correct spot
and the blank anywhere you can then trace your way back to the starting
position pretty quickly.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
For a living - Software developer for DEFINITY PBX; AT&T/GBCS. For fun,
run my kids around; thinking a lot about my garden lately; still trying to
get one last ski trip in! Thanks Fred -- always enjoy these things!
=================================================================
======================================= pinkfLoyd =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
pinkfLoyd 25/136 25/125 25/128 25/116 25/102 125/0607/092 970690ms
=================================================================
======================================= dubious =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
dubious 25/132 25/131 25/140 25/130 25/94 125/0627/102 2116180ms
=================
dubious was submitted by Mark Studebaker at mds@pdn.paradyne.com
=================
HOW DID dubious ATTACK THE PROBLEM (in general)?
Do depth-first search through tree of moves. Look ahead minimum
of 11 moves, which was best I could do given time & memory constraints.
Find move with best "score", prune rest of tree, and do it again.
Increase the search depth if stuck and as tiles get fixed.
HOW DID dubious "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
Manhattan distance of a tile to where it's supposed to be, multiplied
by a tile's "priority". The farther from the lower left corner a tile
belongs, the higher its priority. This encourages the program to
work from upper left to lower right.
HOW DID dubious AVOID POSITIONS THAT WERE EALUATED PREVIOUSLY?
Other than making sure that it didn't undo a move it just did
(that is, end up the same as it was two moves ago), nothing.
HOW DID dubious DEAL WITH "loops" IN THE MOVES OR "impossible" END POSITIONS?
The scoring function together with a large lookahead
keeps the program moving forward.
It avoids impossible end positions by working from upper left to
lower right.
Also, when it gets down to the last four tiles (STX+), it recognizes
positions that are "backwards" and scores them bad. If you are backwards,
it takes about 15 moves to finish from there, so that's really bad.
I couldn't figure out how to compute the "parity" of a position so
I figured out by hand which 12 of the 24 end positions were backwards
and the program checks for those one by one.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
When tiles get put in the right position, the program "fixes" them
if the one above and to the left of it are fixed, so the program
doesn't waste time undoing good positions. But you have to be careful
what to fix when so you don't leave yourself with a "hole" that
is hard to fill.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
HW Engineer, AT&T Paradyne, Largo FL
What I do for fun IS my innermost secret.
=================================================================
======================================= twobits =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
twobits 25/144 25/137 25/154 25/140 25/136 125/0711/141 710ms
=================
twobits was submitted by Warren Montgomery at warren@ixserve.ih.att.com
=================
HOW DID twobits ATTACK THE PROBLEM (in general)? It systematically
places the tiles to form something near the end pattern, with the
center square open (the final pattern is formed by 4 more simple
moves). Each tile is positioned either by moving it to the
center, moving the "hole" to the desired spot and transposing, or
moving direct. Tiles are moved by moving the "hole" to the next
position I wanted the tile and then moving it into the hole. I
transposed the hole back to the middle again if that was advantages
(as it usually was). As such, twobits does no searching, does not
have to deal with impossible positions (because the order in which
the tiles are placed guarantees that each one is placeable), but
doesn't find a very optimal solution. I experimented with various
searching strategies but never had the time to put it all together.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
Make the time limit shorter. I like these contests, but don't have
the time to spend on a 3 month optimization job.
=================================================================
======================================= tilex =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
tilex 25/158 25/171 25/182 25/166 25/140 125/0817/136 370ms
=================
tilex was submitted by Joe Eccles at joe@mink.mt.att.com
=================
HOW DID tilex ATTACK THE PROBLEM (in general)?
This program took a simple approach to trying to guarantee
that a solution would be found. It simply places the tiles one at a time
in the proper spot, working from the outside to the inside, and using
the transport to actually place the tile in the proper place. To allow
"outside to inside" ordering of moves, the T, O, N, and M were put into
a temporary space shifted one from their proper place, and corrected at
the end. This guaranteed that a solution would be found. There were
lots of "local" optimizations - looking for shorter paths, never
using a transport when the space was one move up, down, right or left
of the center, etc. Some effort was put into making this as fast as
possible.
The intention was to use this as a starting point for a
search based algorithm, but the appropaches I tried were too
expensive, and I settled for a very fast solution.
WHAT DO YOU DO FOR A LIVING?
Design/development of telecommuncations software.
FOR FUN?
Music, golf, POTM.
COMPANY/DIVISION?
BCS
INNERMOST SECRET?
I haven't told myself yet.
=================================================================
======================================= Nilssonized =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
Nilssonized 25/290 25/387 25/236 25/250 25/264 125/1427/158 78090ms
=================
Nilssonized was submitted by V. Raghavan at rags@mt747.mt.att.com
=================
HOW DID Nilssonized ATTACK THE PROBLEM (in general)?
It was a simple implementation of Nilsson's A* Algorithm.
HOW DID Nilssonized "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
I used 2 Hueristics
1) The Number of tiles in the correct position.
2) The "Manhattan Distance" of the tile from the correct position.
HOW DID Nilssonized AVOID POSITIONS THAT WERE EALUATED PREVIOUSLY?
As per the Algo , There are 2 lists (1) OPEN containing nodes which have not
been evaluated (2) CLOSED which have been evaluated. So the strategy is
inherent to the Algo.
HOW DID Nilssonized DEAL WITH "loops" OR "impossible" END POSITIONS?
I wrote this program with a intention to get "A solution " and not
"THE SOLUTION". So the job was easy , I did not bother to get into
loops or anything. It is a simple generate & Test till you reach the goal state.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I used a Hash Table to speed up the search in the OPEN & CLOSED Lists. It
improved the speed by atleast 7 times.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I generate a commodity that people call as software ,to live.
I participate in POTM for fun.
I work for AT&T Paradyne.in NJ.
To do research in PURE SOFTWARE at AT&T Research division
=================================================================
======================================= alphabits =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
alphabits 20/144 25/119 25/144 25/150 25/138 120/0695/149 647000ms
=================
alphabits was submitted by Jim Porter at jwp@drmail.dr.att.com
=================
HOW DID alphabits ATTACK THE PROBLEM (in general)?
Alphabits used the "transport" mechanism to move tiles from the center to
their final resting place. The outside corners were first populated and
as each corner was placed the adjacent side tiles would become "candidates"
for placement. The tile that was closest to center that was on the
candidate list would be chosen. Once the outside corners and edges were
done then a search was done for the best sequence of movements to place
the inside 8 tiles leaving the center with the plus. The final position
would allow the "+" to moved to the right edge and then down to create
the final correct board position.
HOW DID alphabits "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
Initial algorithms calculated the number of moves out of position for a square
but this was not used in the final solution.
HOW DID alphabits AVOID POSITIONS THAT WERE EVALUATED PREVIOUSLY?
No avoidance.
HOW DID alphabits DEAL WITH "loops" OR "impossible" END POSITIONS?
The use of transport eliminated impossible end positions (I think!).
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I was going to include a search for populating the outside edge but never got
time to do it...ah well.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
MTS in GBCS doing OO/C++ on the CMS application (too many acronyms?).
For fun I play racquetball.
=================================================================
======================================= lwr =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
lwr 25/268 25/277 0/ILL 25/258 25/266 105/1069/085 1490ms
=================
lwr was submitted by Debbie Brown at dwb@arch4.att.com
=================
HOW DID lwr ATTACK THE PROBLEM (in general)?
I decided not to worry about minimizing number of moves or transpositions
but just tried to find a way to get all the squares back into position.
(That was hard enough!)
I defined a number of "paths" through the grid. For each path, the positons in the grid
were labelled with numbers 0 through 24. The middle square was labelled 0,
the bottom, right-hand square was labelled 24. The path was defined such
that the label n+1 was assigned to a square that was adjacent to the square
labelled n. All the integers 0 through 24 were used exactly once.
For example:
4 3 2 19 20
5 6 1 18 21
8 7 0 17 22
9 12 13 16 23
10 11 14 15 24
is such a path.
If (conceptually) you straighten that path out, my approach was sort the path
from the end position back to the beginning position. Assuming at some point
the last n positions of the path are in order, I would place the tile into
the end portion of the path, such that the last n+1 positions would be sorted.
(Something like an insertion sort).
By always following this path, I made sure that any tiles that were in the
proper order, stayed in that order. Only when I was ready to insert the tile
at the beginning of the path (i.e., the center tile) into its position,
would I do a transport.
I try this approach for several different paths, and pick the one that yields
the best results. It's easy to see, however, that even in very simple cases,
this approach yields results which are much worse than the optimum.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I'm a software developer. Lately, I've worked on developing prototype
speech recognition applications in the Voice Processing Architecture Group
of the Architecture Area. (If I told you my innermost secret, it wouldn't
be secret, now would it?)
=================================================================
======================================= slider =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
slider 25/102 25/91 25/104 25/88 0/TIM 100/0385/051 1485830ms
=================
slider was submitted by Andrew Shaw at shaw@apache.att.com
=================
HOW DID slider ATTACK THE PROBLEM (in general)?
It employed (what I subsequently learned to be) an A* search.
Essentially it did a breadth-first search of the solution
space, keeping track of previously seen boards to prevent
re-evaluations, and ordering nodes on a priority queue (heap)
so that boards of "least distance" from the solution were worked
on first.
HOW DID slider "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
The evaluation was a variation of Manhattan Distance (sum of the
blockwise distance of each tile from its target position). The
first variation was the recognition that Transpose could save up
to three moves for the middle tile, so for that tile the minimum
of the blockwise distance and 1 plus the blockwise distance after
transposition was added. The second variation was also adding the
Pair Distance (paper by Bernard Bauer) -- this is the recognition
that if two tiles in a row (or column) are "swapped" then two
additional moves are needed so that they can pass each other.
Note that this doesn't take into account that Transpose might be
able to reorder the tiles without the sidestep, so the heuristic
is slightly inadmissable. However, we needed to weight 'g' (cost
so far) over 'h' (evaluated distance to go) at about 2/3 to get
any solution at all in the time given, so optimality was already
out the window.
HOW DID slider AVOID POSITIONS THAT WERE EALUATED PREVIOUSLY?
Previous positions were kept in an AVL tree and any move that
generated a hit thereto was discarded. As an optimization,
any move that "undid" the previous move (eg up after down) was
immediately discarded.
HOW DID slider DEAL WITH "loops" IN THE MOVES OR "impossible" END POSITIONS?
Firstly any move sequence involving loops would be longer than
the equivalent non-loop sequence and so would be farther back
in the priority queue, thus a loop would have a harder time being
worked on. Secondly as above, previous positions were recorded,
so the loop branch would be immediately abandoned if the loop
ever came to completion.
I'm not sure what an "impossible" end position would be -- I
didn't direct the search (no goal seeking) so application of
Transpose would eventually make any starting configuration
solvable.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
I tried IDA*, but since time, rather than space, turned out to
be the limiting constraint, it was not a win (but I'm still
fooling with it so who knows). IDA* with tree preservation is
still NP-space and takes slightly longer than A*; however, since
of necessity IDA* must eliminate previously-seen checking, we might
be able to improve it with 1) random operator ordering and 2)
longest path(s) priority.
I was stuck at one point and, not realizing this was an AI
problem, couldn't find anything in the literature. So I
posted for help in comp.theory and was kindly given pointers
including a Web site that contains recent (1994) papers on this
very problem. Have a look at
http://www.uni-paderborn.de/pcpc/pcpc.html
to see where I got PD and IDA*-enhancement.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I do development (shocking, but true) on a project that provides
provisioning (formerly maintenance) software to the workcenters
-- automating the complex process of providing AT&T long-distance.
For fun I play with my 10-month old son and struggle with these
deceptively difficult POTMs (and between the two my free time is
completely used up). My innermost secret is that I have only a
vague idea what division I work for at Bell Labs (or is it AT&T
post-alignment?); however, I do know where my desk is, and what
I'm trying to build, so all is not lost.
=================================================================
======================================= bittwister =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
bittwister 25/110 0/TIM 25/112 25/122 25/106 100/0450/088 799780ms
==============================================
bittwister spieters@cs.vu.nl P.Frants S.Pieterse 03/23 GCC
==============================================
About BitTwister by Seppo Pieterse & Patrick Frants.
We're two CS students at the Vrije University of Amsterdam. We like competing
in contests and solving these kind of problems. We especially liked this
problem because of the creativity required to produce a competitive program.
Let's get to business:
Our algorithm consists of two stages:
- First make the borders
- Then solve the middle 9 squares
Making the borders
For every square that had to be moved to the border we calculated the number
of moves required to get at it's position using the following algorithm:
First get the square to the middle
Then move the + to the goal-position
Transport
The square that needed the least number of moves was moved to it's
goal-position. This was repeated for all 16 border-squares.
Solve the middle 9 squares
To solve the last 9 squares we used the well-known A*-algorithm to find an
optimal solution. Obviously our algorithm was very fast.
Seppo Pieterse & Patrick Frants
=================================================================
======================================= ramduf =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
ramduf 25/154 25/141 0/TIM 25/114 25/136 100/0545/078 1436190ms
=================
ramduf was submitted by Randy Saint at saint@phoenix.phoenix.net
=================
HOW DID ramduf ATTACK THE PROBLEM (in general)?
I used a type of Branch and Bound search (there may be a more correct
name for this algorithm). I maintained a list of possible board positions
which included the moves to get to that position. That list was sorted on
the value EST_COST + NUM_MOVES. Where EST_COST is my board position evaluator.
(EST_COST==0 means a completed board).
I pop a position off the top of the list, determine valid moves and put
the new moves into the list (sorted with the new EST_COST + (NUM_MOVES+1)).
I repeat this loop until the position popped off the top of the list has
an EST_COST of 0.
HOW DID ramduf "score" A SQUARE TO DETERMINE IF THE SOLUTION WAS "good"?
This algorithm is sensitive to the "proper" EST_COST for a position. If
it is (in general) too high, then the algorithm doesn't mind wasting moves
to reduce the EST_COST. If it's too low, the algorithm spends too much
time exhaustively searching too many board positions.
I first tried Manhattan Distance, then Euclidian Distance, then Euclidian
Distance squared, and that seemed to work better, but it still took a long
time to come to a solution. So I decided to weight the top and left rows
heavier so the agorithm would put a priority on moving them into position
first.
HOW DID ramduf AVOID POSITIONS THAT WERE EVALUATED PREVIOUSLY?
I used the tsearch() subroutine that UNIX provides. It uses a tree search
technique to see if a node is in the storage space. If it's not in there,
it inserts it into the storage space. I used this to store my previously
visitied board positions (stored as char strings of len 25). The tree
just sorted the board positions alphabetically.
HOW DID ramduf DEAL WITH "loops" OR "impossible" END POSITIONS?
Normally ramduf could find a solution that avoided impossible positions
just through the normal actions of the agorithm,
but occasionally, it seemed that it would get into a situation that it
could not solve. It would fill up the "already visited" board position
storage space without coming to an answer.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
It's fascinating what the different evaluations for board positions could
change. I started with a 3x (multiply by 3) factor for the top and left
row, and 2x for the 2nd from top and 2nd from left, and 1x for the rest (3x3
in the lower right corner).
Ramduf got an answer but it wasn't very good. When I changed the factors
to 2x for top and left, 1.5x for 2nd, and 1x for the last 3x3, Ramduf found
an answer in just 10 SECONDS! The solution for the test problem was 113
moves which wasn't bad for such a quick answer.
I figured it was just a case of adjusting those factors right, so I set
up a Genetic Algorithm to fiddle with the numbers and try and come up with
a good solution. I let it run on a DEC 5000 at work over the weekend, and
it came up with some Ok numbers, but nothing spectacular. Well, I took
the best solution that it came up with and sent that in to Fred, but it
took too long on his machine. So I went back to the 2x, 1.5x, 1x solution
and sent that in for my entry.
I'm frustrated that the GA didn't come up with a better board evaluator.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I'm a software engineer at Loral Space Information Systems in Houston, TX.
In my spare time I enter programming contests. I wasn't able to concentrate
fully on this POTM contest, as I was geting a robot driver car ready for the
RARS (Robot Automated Racing Simulator) contest (also due April 30). I won,
BTW.
Innermost secret? Well, I am planning on trying to create a newsgroup
called comp.programming.contests. I'm going to submit a RFD on some of
the relevant newsgroups. But I want to find out if there's anything I
need to do, like line up an impartial vote counter, before I post the
RFD. If there's anyone who can let me know how to find an impartial
person to collect the votes, please let me know.
=================================================================
======================================= Brute.Force =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
Brute.Force 0/TIM 25/231 25/276 25/246 25/208 100/0961/096 622600ms
=================================================================
======================================= escort =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
escort 25/216 15/122 14/171 14/172 25/174 093/0855/109 430ms
=================
escort was submitted by Mary Kaminski at mfk@ieain.ih.att.com
=================
HOW DID escort ATTACK THE PROBLEM (in general)?
I thought of the problem as taking each letter from its current location
to its final location. Since that can only be done by moving the letter
into an adjacent empty (+) space, the problem become that of the "+"
"escorting" the letter to its destination.
HOW DID escort AVOID POSITIONS THAT WERE EALUATED PREVIOUSLY?
I set up a handling order for the letters based on distance of final position
from the center which I considered the command post.
The problem then became a sequence of 24 problems.
HOW DID escort DEAL WITH "loops" IN THE MOVES OR "impossible" END POSITIONS?
To prevent undoing work already done, I kept an array of positions not
to be disturbed subsequently.
I used a similar technique to prevent infinite loops in positioning a single
letter.
ANY OTHER COMMENTS, TRICKS, WHATEVER?
My solution was mechanical. The C language encourages that approach.
With the lisp/clos language, I probably would have used a mapping
approach.
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I work for AT&T in switching. I was content with the SDE until I experienced
a Lisp/CLOS environment. Inexplicably, that project solution is being
dismantled - ah, progress!
=================================================================
======================================= snails-pace =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
snails-pace 16/202 11/88 16/202 18/202 15/202 076/0896/124 2461550ms
=================================================================
======================================= 10.pound.sledge =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
10.pound.sledge 25/160 0/TIM 25/148 25/142 0/TIM 075/0450/088 2369780ms
=================
10.pound.sledge was submitted by Fred Hicinbothem at fah@potm
=================
HOW DID 10.pound.sledge ATTACK THE PROBLEM (in general)?
Brutally. My approach was to break the problem up into six phases, each of
which successively put another five or so letters in position. First the
top row, then the left, right, and bottom. Then I closed in the middle
in two steps. Since the empty square had to end up in the middle 9 squares
for this approach to work, there was the final step of reorienting the empty
square. During each phase I examined every possilbe N-tuple of moves that
involved the unplaced positions ... I found I was able to look ahead between
9 and 12 moves in the allotted time at each phase (9 for the earlier phases
and 12 for the later ones). I chose the next move based on the score of the
end of the N-tuple ... basically selecting the first half of the N moves that
got me to the best "score".
HOW DID 10.pound.sledge "score" A SQUARE?
For each phase, I added the row and column distance of each letter to be
placed in that phase. If there were ties, I chose the N-tuple that put
the target squares closest to the center. If there STILL were ties, I chose
the N-tuple that had the squares in the NEXT phase closest to the center.
When all letters for a phase were in place, I moved to the next phase and
made sure I din't move any letters that were already placed..
HOW DID 10.pound.sledge AVOID POSITIONS THAT WERE EVALUATED PREVIOUSLY?
uhhhh ... that would have been a good idea, except I wasn't smart enough
to find an efficient way to keep track of 9^9 (387M) potential positions.
Maybe if I had another three months ...
HOW DID 10.pound.sledge DEAL WITH "loops" OR "impossible" END POSITIONS?
I avoided the obvious "rl", "ud" kinds of two-step loops, but didn't get
around to looking at the longer ones like "tlltllt"
ANY OTHER COMMENTS, TRICKS, WHATEVER?
recursion for the lookahead ... if I do enough of these I may eventually
learn a little C! (nahhhhh ...)
WHAT DO YOU DO FOR A LIVING? FOR FUN? COMPANY/DIVISION? INNERMOST SECRET?
I are a systems enjinear ... I think. Most of what I do is paper, but I
get to be in on some interesting AT&T services. The POTM has become more
of an addiction than an enjoyment, but still more than enough fun to keep
doing it! Secret: I still can't code worth a damn! (no secret to those
who know me)
=================================================================
======================================= detangler =============
=================================================================
ENTRY FOXY AID TYPO FAQ WARN TOTAL (5) TOTAL T
detangler 0/ILL 0/ILL 25/230 0/TIM 25/254 062/0484/053 1034530ms
=================================================================