Peter Suber, "Inductive Game of Rubik's Cube"

Copyright © 1985, Peter Suber.
Introduction to the Inductive Game
Of Rubik's Cube Peter Suber, Philosophy Department, Earlham College
The normal game of Rubik's cube is to return a randomized cube to its solved state by any number of twists of its planes. Successful cubists have algorithms that guarantee solution. Players are judged superior only by virtue of the elegance of their algorithms or the speed with which they can apply them.
The inductive game makes one small change with many large consequences. A player of the inductive game starts with a cube in the solved state, gives it n twists, and then tries to return it to the solved state in n or fewer twists. Typically the player is not the one to make the randomizing twists, or else does so behind her own back. In short:

Out of the sight of the player, the randomizer takes a solved cube and gives it a certain number, n, of twists.
The player attempts to return the cube to the solved state with the fewest number of twists (n or fewer), which usually means to retrace the path of the randomizer.

First we should notice that the normal and inductive games are both inductive in some sense. The normal game is inductive in the process undertaken by players to discover the algorithms sufficient for solution. That process has been said to model the scientific method, complete with the formulation and testing of theories, negative results, and confirmation. Once the inductive method produces algorithms, normal play is more deductive than inductive. That is where the inductive game differs. Instead of producing algorithms that may be applied infallibly by an idiot, the inductive game produces 'soft rules' or probabilistic guides that must be applied in each case with judgment, mother wit, and the weight of one's inductive experience. The inductive process of discovery does not come to an end in deductive methods of play. Both discovery and play are inductive.
The objective of the inductive game is to find the shortest path from a randomized state to the solved state. It helps play enormously to know how many twists one is from solution when one starts. For this purpose some standard terms are introduced below. But notice that on the 3x3x3 cube (the only type discussed here), it has been proved that every state of randomization is at most 23 twists from solution. This fact has many important consequences for the inductive game.
It means that the randomizer may give the player a randomized cube in which the shortest path to solution is shorter than the path that retraces the steps of the randomizer. For example, if the randomizer gives a solved cube 25 twists, then in principle there is a shorter path home than retracing those 25 steps. However, there is a good reason why the inductive game will not use cubes randomized by more than 23 twists. The reason is that players who can solve 23-twist randomizations in 23 steps have hit upon "God's Algorithm" and need no greater challenge.
We do not know whether the quadrillions of distinct paths from distinct randomized states to the solved state fall into patterns. That is, we do not know whether "God's Algorithm" is a family of methods with some learnable structure, or whether it is a chaotic tangle of disconnected pathways. If it is an organized family, or insofar as it is an organized family, then the inductive game is one way to learn it.
The difference between retracing the randomizer's path and finding a shorter one will not knowably affect play when there are fewer than 23 twists in the randomized cube. We do not know whether any 8-twist randomization, for example, when all twists are distinct, can be solved in fewer than 8 twists. But in any case, the 'rules' of the inductive game will yield the shortest path, not necessarily the retraced path of the randomizer.
Why Play the Inductive Game?

The inductive game has several advantages over the normal game. First, each randomization is a fresh challenge. In the normal game, a competent player has algorithms of sufficient generality that any randomized cube may be solved, if one is willing to spend 60 to 200 twists to do so. This is not the case with the inductive game. If one can solve the cube in the normal game and is bored by that challenge, then the inductive game offers endless variety and escalating difficulty.
Second, there is no equivalent to an algorithm in the inductive game. Hence, no matter how much one learns, nothing one knows can be applied automatically. Success cannot be reduced to a certainty, only to greater and greater probabilities.
Third, one learns more and more each time one plays the inductive game. In the normal game, after a while, one may diddle or even solve the cube without learning anything new. In the inductive game, all attempts at solution, even unsuccessful ones, add to one's bank of inductive experience. For mastery of the inductive game one must rely on inductive knowledge of the probability that certain configurations could have survived x twists. That sort of knowledge increases with every spin through the cube, in subtle and barely articulable ways.
Fourth, the inductive game cannot become routine or boring, except to gods. When one can solve 3-twist randomizations nearly 100% of the time, then one may move on to 4-twist randomizations. Difficulty increases exponentially. There is a foreseeable end to the series, of course. Players who patiently gather up their nuanced, ineffable knowledge of random patterns may reach the level of 23-twist randomizations. Improvement does not merely approach the banal satisfaction of more frequent success; it approaches hard knowledge of "God's Algorithm".
Terms

For convenience I will use the following terms in these special senses.

Twist
One 90-degree turn of one plane. Note that under this definition 180-degree turns amount to two twists. This convention is not merely terminological; it affects play. If the randomizer is told to produce a 6-twist randomization, then under this definition the player knows that the cube will be no more than six 90-degree turns from solution. When players know exactly how many 90-degree turns they are from solution at the beginning, then they can monitor their own success more effectively. For example, two turns into a 4-twist randomization should produce a cube only two twists from solution, which should be evident to the eye even of beginning players; if it is not, the player may confidently infer error at an earlier stage.
Home
The solved state of the cube (in which each of the six faces displays tiles of only one color).
Shortest path home
The shortest series of twists needed to move from a randomized state to the solved state. As noted, the shortest path home may occasionally be shorter than the path that retraces the steps of the randomizer.
Information
The adjacency of two or more tiles of the same color that need not (and ought not) to be separated on the shortest path home. This is not the same thing as the adjacency of any set of tiles of the same color, nor is it the same as the adjacency of tiles that 'properly belong together' or that are adjacent in the solved state. Sometimes called actual information for emphasis; see next.
Accidental information
The adjacency of two or more tiles of the same color that must be separated on the shortest path home, regardless whether they will be reunited in the solved state.
Apparent information
The adjacency of two or more tiles of the same color when the player is uncertain whether they make actual or accidental information.
Blocked
Of a plane on the cube, to be ineligible for twisting in the judgment of the player. A basic rule of strategy holds, for example, that a plane is blocked if twisting it would destroy actual information.
Above the tree line
A randomized state of the cube that offers no apparent information. It has been proved that 8 twists is the minimum number sufficient to put one above the tree line. In my experience randomizations of any degree rarely put one above the tree line; one must be seeking such a state to produce one. In a weak sense one is above the tree line whenever one suspects that all apparent information is accidental. In my experience this does not commonly occur at fewer than 10 or 12 twists from home. One is very far above the tree line if no single twist will produce apparent information. When one is above the tree line, one cannot use 'information' as a guide home. One must discover different kinds of clues. Hence, inductive games of roughly eight twists or less require the ability to discern actual from accidental information, while games of more than eight twists are quite different. The term is taken from mountaineering; the analogy is to the diminishing amount of life and information, and the increasing difficulty, as one ascends to the pinnacle of "God's Algorithm"

Basic Strategy Tips

At any given state of the cube there are only 12 possible moves. There are six planes and each may be twisted 90-degrees in either of two directions. Hence, one need never despair. One is not asked to pick like a god among quadrillions of pathways. One is asked merely to pick the best of 12 options. Each of the 12 is surveyable to human intelligence, if only human intelligence knew what to look for.
The two most basic 'rules' of the inductive game are:

Thou shalt not break up information.
Thou shalt endeavor to make more information.

A word on the subtlety of these basic rules is in order. The first is not comparative. It does not say to break up the least amount of information; it says to break up none. But in practice we must reduce it to a comparative rule, for in practice all we usually get is apparent information. Modified for fallen human beings, the rule says to break up the least amount of apparent information and none of what is most likely to be actual information.
The second rule is confessedly comparative. Sometimes no twist can make any even apparent information. Sometimes more than one possible twist will make the same amount of apparent information. The rule says to try, and to try to make the most information that one can on each twist. But of course all we get again is apparent information. In human language it tells us to maximize what we are willing to bet is actual information.
Both rules are qualified by a third rule:

The shortest path home may wind about. Do not expect information to grow on each twist.

This rule is a warning not to take the challenge of the inductive game as the mere inspection of 12 possible paths per turn. As much as one can, one must have an idea of the shape of the different paths that diverge in the 12 directions from where one finds oneself. A solution in the inductive game is not a series of individual good guesses, each surmounting twelve to one odds against success. It is a series of good guesses that form a coherent method of returning home. Masters of the normal game do not need to be told that the shortest path between two states of the cube usually requires a detour through apparent chaos. If one never expects this and insists on building information on each step, then one will inevitably build accidental information and move further from home. On the other hand, detours through chaos are much more frequent in the normal game than in the inductive game. (The perceptive reader should already know why.)
In other words, the best move will not always maximize new apparent information, although it will always preserve all actual information. If two possible twists give the same amount of new apparent information, no other gives more, and neither destroys apparent information, then obviously one must choose between them on other grounds. These 'other grounds' are just the kind that must be used above the tree line, and for the same reason. They will even have to be used below the tree line, occasionally, to distinguish between two moves when one makes more apparent information than another, and even when the actuality of the information is not an issue.
The relatively small array of options available on each turn allows ample room for experimentation. If one likes one may try each of the 12 possible twists and see which of the 12 new states makes the most interesting apparent information and destroys the least apparent information. However, one should experiment with care, and remember that not all apparent information is actual and that not every correct move will increase information.
Players may be helped in their experimentation if they write down their moves. Then, if they confidently infer that they made a mistake earlier, they may retrace their steps and try again. A simple notation for this is as follows. Use the first initial of the color of the center tile of the plane twisted; leave it unadorned if one twisted clockwise (while facing that plane); mark it with an asterisk if one twisted counter-clockwise. For example, "w*" means the white face (the plane with the white tile in the center) was twisted 90 degrees counter-clockwise. The six colors on most cubes are white, yellow, red, orange, blue, and green. Fortunately, these colors have no common initial letters.
Self-monitoring and experimentation might be aided even more if one writes down, next to each move made, one's judgment of its probable correctness and the most probable alternative moves. Then when one infers error and backs up, one may go back to the lowest probability number from the beginning and start from there.
If randomizers keep note of the steps they took to randomize the cube, then the same randmized state may be given as a challenge to different players.
Some Rules

The following probabilistic guides (or 'rules') go beyond the basics of the last section. They are based on my experience alone and can undoubtedly be supplemented by others. None should be followed absolutely. When they should be applied, and when overruled, are themselves subject to probabilistic guides that the player must learn by induction.
I have found it extremely difficult to state all the 'rules' that I use in practice, and extremely interesting to speculate why. In any event, these are not all the rules that even a moderate beginner knows 'by thumb'. Moreover, no matter how clearly they are stated, they all seem much more complex in writing than when thought, recognized, and applied. The task here is like trying to tell someone entirely through explicit rules how to recognize the face of your grandmother.

Always know how far from home one is supposed to be (assuming that every twist has been right). This is important for distinguishing accidental from actual information. One should be able to ask just how likely it is that any given configuration of apparent information would have been preserved after x twists.
A center tile and edge tile of the same color are very often accidental information. One should presume their adjacency is accidental unless one has corroboration for the opposite theory.
A 2-tile configuration of apparent information is much more likely to be actual information if it is adjacent to another 2-tile configuration such that the twist that would destroy the first would destroy both.
A configuration of apparent information is almost certainly accidental if its perimeter is not convex at every point. Important examples are the following: rectangles with missing corners; strings that turn in a single plane; a meeting of strings from different planes at a vertex; a 3-tile edge string plus the center.
Other things being equal, a configuration is more likely to be actual information if it spills over to another face of the cube where it also makes apparent information.
In choosing between a 2-tile and a 3-tile string, when one must be destroyed, do not automatically assume that the longer string is more (or less) likely to be the actual information. In my experience the odds are about equal either way, at least when one is under 8 twists from home. Above 8 twists, the shorter string is more likely to be actual information.
In general, the further one is from home, the less any apparent information is likely to be actual information. Similarly, at any stage, the larger a configuration of apparent information, the less likely it is to be (in every part) actual information, unless one is very close to home.
In a configuration of 3 or more tiles of apparent information, do not assume that one accidental adjacency makes the other(s) accidental. Similarly, do not assume that all the adjacencies of large configurations have the same status.
If the next twist has been narrowed down to one plane, and neither twist (clockwise or counter-clockwise) makes any apparent information, or both twists make the same amout of equally likely information, then one must choose the direction of the twist on other grounds.

Make the plane to be twisted the top plane. Look at the bottom plane and determine which planes it blocks. If only one plane is not blocked by the bottom plane (e.g. the front plane), then twist the top plane in whatever direction is needed to allow the front plane to twist (without blockage from the top plane) in the next move.
If two or more 'side planes' could be twisted for a given top plane, then try each move hypothetically (at least in your head) and compare the increases of apparent information.
If the next twist has been narrowed down to two or more planes, then apply the method above hypothetically to each eligible plane, and compare the increases in apparent information.
This procedure is the weakest —gives the lowest probability of the right answer— when the bottom plane is not blocked and could itself move without destroying apparent information. It is stronger when the bottom plane is blocked. It is strongest when the bottom plane is blocked and the top plane is the only movable plane or the most likely plane to be moved.

Craig Rutledge has written an AS/400 program implementing these rules. He's put the source code online for anyone who might be interested. His code recently (March 2001) earned him the title Games Master for the green screen masses from 400Times.