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 =================================================================