From cube-lovers-errors@oolong.camellia.org Fri May 30 21:24:38 1997 Return-Path: cube-lovers-errors@oolong.camellia.org Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id VAA23782; Fri, 30 May 1997 21:24:38 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Sender: Haym Hirsh Date: Fri, 30 May 97 21:10:39 EDT From: Haym Hirsh Reply-To: Haym Hirsh To: joemcg3@snowcrest.net Subject: Re: The rest of us In-Reply-To: Your message of Fri, 30 May 1997 11:14:19 -0700 Cc: cube-lovers@ai.mit.edu Message-ID: Here's a brief attempt at a "layman's" description of Professor Korf's work: Imagine you have a function that takes as input a messed-up Rubik's cube, and outputs a guess of how many moves it will take to get it to the solved state. Further, assume this guess is never greater than the correct number of moves -- sometimes your solution-length guesser may make a correct guess, but sometimes (or even perhaps always) it may underestimate the number. There is an algorithm called A* that is guaranteed to find a shortest solution sequence for any Rubik's cube it is given, as long as it is given a solution-length guesser that has this never-overestimates-the- number-of-moves-to-solved guarantee. The problem is that A*'s guarantee is only that it will return a shortest solution to any cube, with no guarantee on how long it will take to find it. Due to this run-time issue A* is only applicable to the most trivial of problems. However, in the mid-80s Professor Korf presented a tractable variant of A*, called IDA* (Iterative Deepening A*) that has the same guarantee as A* on finding shortest solutions, but is much faster. The problem now, though, is that even IDA* can also take a long time. Its salvation, however, is that, loosely speaking, the better the solution-length-guessing-function is, the faster IDA* will run. Thus, for example, you could use a function that always returned 0 as the guess for how many moves you are from the start. It's not a particularly clever guess, but it obeys the rule that it never overestimates the solution length. Therefore, you could use it with IDA* (or, for that matter, A*) to find shortest solutions to any cube. Except that it would run too slow, because the solution-length guesser is so dumb. A better solution-length guesser would help IDA* run faster. Professor Korf came up with a way to more intelligently guess what the solution length will be for arbitrary cubes -- it gives something much closer to the true value, but still without overestimating. A simplified form of this would be to figure out how many moves at minimum it will take to get the corners in place, and use this corners-only solution length as a guess. This will never overestimate the solution length, since to get everything in place you certainly have to get at least the corners into their proper positions, and it is better than a guesser that always returns 0. Professor Korf also had to figure out how to compute these guesses in an efficient fashion, since guesses will be requested many many times by IDA* as it explores possible intermediate cubes in its search for the solution. To do this he enumerated all 88 million configurations of corners (different cubes with different arrangements of edges but with identical corners are considered identical configurations). For each he figured out the minimum number of moves that would be necessary to get them into their correct position in a solved cube if edges were ignored (taking a non-trivial, but non-infinite, amount of time to do this for each of the 88 million configurations). Finally, he generated a table with 88 million entries, with each entry corresponding to a corner configuration and containing the solution length for that configuration. This created a way to quickly compute his more accurate corner-centric solution-length guesser, via table lookups. In truth Professor Korf improves on this even further by developing a better solution-length guesser that does similar things with edges as I just described with corners, also using tables for efficient guess calculation. The result is a solution-length guesser that is accurate enough to allow IDA* to solve the 10 random cubes that he generated. More specifically, Professor Korf generated random cubes by taking a solved cube and making 100 random turns to it. He did this 10 separate times, and got 10 messed-up cubes. He then ran IDA* using his table-based solution-length guesser, and solved all 10, one in 16 moves, three in 17 moves, and the rest in 18 moves. Because he used IDA*, and because his solution-length guesser never overestimates solution lengths, his solutions are guaranteed to be optimal (due to IDA*'s mathematical guarantees). This does not argue that 18 is the longest solution possible for any cube. Just that for the 10 he generated randomly, none required more than 18. Perhaps some cubes are more than 18 moves away from start. None simply happened to arise amongst his 10 cases.