Analyzing Human Solving Methods

  • View
    192

  • Download
    2

Embed Size (px)

Text of Analyzing Human Solving Methods

Diploma Thesis Analyzing Human Solving Methods for Rubiks Cube and similar PuzzlesStefan Pochmann

Supervisor Prof. Dr. J. Furnkranz March 29, 2008

ii

Ehrenwortliche Erkl rung aHiermit versichere ich, die vorliegende Diplomarbeit ohne Hilfe Dritter und nur mit den angegebenen Quellen und Hilfsmitteln angefertigt zu haben. Alle Stellen, die aus den Quellen entnommen wurden, sind als solche kenntlich gemacht worden. Diese Arbeit hat in gleicher oder ahnlicher Form noch keiner Prufungsbehorde vorgelegen. Darmstadt, M rz 2008 a Stefan Pochmann

iii

iv

ContentsForeword 1 Cube basics and solving 1.1 1.2 1.3 1.4 Speedcubing . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cube structure . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithms and notation . . . . . . . . . . . . . . . . . . . . . Solving methods . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 1.4.2 1.4.3 1.5 2 Beginner method . . . . . . . . . . . . . . . . . . . . . Expert method . . . . . . . . . . . . . . . . . . . . . . Other methods . . . . . . . . . . . . . . . . . . . . . . xiii 1 1 2 4 6 6 8 9 11 13 14 14 15 16 17 17 18 19 19

Common aspects of human solving methods . . . . . . . . .

Previous programs and results 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Some numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . Thistlethwaite . . . . . . . . . . . . . . . . . . . . . . . . . . . Kociembas Cube Explorer . . . . . . . . . . . . . . . . . . . . New lower bound: 20 turns . . . . . . . . . . . . . . . . . . . Korfs pattern databases . . . . . . . . . . . . . . . . . . . . . Jelineks ACube . . . . . . . . . . . . . . . . . . . . . . . . . . Norskogs 4x4x4 solver/analysis . . . . . . . . . . . . . . . . My short solver . . . . . . . . . . . . . . . . . . . . . . . . . . Closing the gap . . . . . . . . . . . . . . . . . . . . . . . . . . v

vi 3 Hume 3.1 3.2 3.3 3.4

CONTENTS 21 21 22 23 23 24 24 25 25 27 29 30 31 36 36 39 39 40 40 43 47 47 48 49 49 50 50

Shortcomings of previous programs . . . . . . . . . . . . . . The Hume program . . . . . . . . . . . . . . . . . . . . . . . . Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 3.4.2 3.4.3 Describing the puzzle . . . . . . . . . . . . . . . . . . Describing the solving method . . . . . . . . . . . . . Describing what to do . . . . . . . . . . . . . . . . . .

3.5 3.6 4

Solving and output . . . . . . . . . . . . . . . . . . . . . . . . Overlapping subgoals . . . . . . . . . . . . . . . . . . . . . .

Evaluation of Rubiks Cube methods 4.1 4.2 4.3 4.4 Analyzed methods . . . . . . . . . . . . . . . . . . . . . . . . Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Analysis of found solutions . . . . . . . . . . . . . . . . . . . Tripod and combining statistics . . . . . . . . . . . . . . . . .

5

Implementation of Hume 5.1 5.2 Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . The solving algorithm . . . . . . . . . . . . . . . . . . . . . . 5.2.1 5.2.2 The outer layer search . . . . . . . . . . . . . . . . . . The inner layer search . . . . . . . . . . . . . . . . . .

6

Future 6.1 6.2 6.3 6.4 6.5 Analyzing more puzzles and methods . . . . . . . . . . . . . Orient rst, grouping . . . . . . . . . . . . . . . . . . . . . . . Movement restrictions . . . . . . . . . . . . . . . . . . . . . . More accurate measurements . . . . . . . . . . . . . . . . . . Memory usage . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5.1 The Successor tables . . . . . . . . . . . . . . . . . . .

CONTENTS 6.5.2 6.5.3 6.6 7 The Distance tables . . . . . . . . . . . . . . . . . . . . A* queue and visited states . . . . . . . . . . . . . . .

vii 51 51 52 53 53 59

Small subgoals . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conclusion

Bibliography A Lower bounds from counting arguments

viii

CONTENTS

List of Figures

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 3.1 3.2 3.3 3.4 3.5 4.1 4.2 4.3 4.4

Cubes from 2x2x2 to 5x5x5 . . . . . . . . . . . . . . . . . . . . Megaminx, Square-1, Pyraminx, Skewb . . . . . . . . . . . . Cube scrambled, one side solved, solved . . . . . . . . . . . . Cube centers, corners, edges . . . . . . . . . . . . . . . . . . . Solved side, solved layer . . . . . . . . . . . . . . . . . . . . . Effects of R, RU, and the T-permutation . . . . . . . . . . . . Typical corners-rst stages . . . . . . . . . . . . . . . . . . . . Typical block method . . . . . . . . . . . . . . . . . . . . . . . Case equivalence, hidden pieces . . . . . . . . . . . . . . . . Sticker names, edge effects of turning U . . . . . . . . . . . . Partial output of the Hume program . . . . . . . . . . . . . . Different block-style starts and extensions . . . . . . . . . . . Four overlapping 2x2x2 subcubes . . . . . . . . . . . . . . . . CrossF2L: Cross, then corner-edge pairs . . . . . . . . . . . . BlockF2L: Subcube, extended by more blocks . . . . . . . . . Graphical comparison between CrossF2L and BlockF2L . . . Graphical statistic for CrossF2L . . . . . . . . . . . . . . . . . ix

2 2 3 4 4 5 10 10 22 24 26 27 28 30 30 32 33

x 4.5 4.6 6.1 6.2 6.3 6.4 6.5

LIST OF FIGURES Graphical statistic BlockF2L . . . . . . . . . . . . . . . . . . . Tripod block-style . . . . . . . . . . . . . . . . . . . . . . . . . The four ways to turn the Skewb . . . . . . . . . . . . . . . . Orienting the last layer, 4x4x4 cube . . . . . . . . . . . . . . . Bandaged cube and the Square-1 . . . . . . . . . . . . . . . . Megaminx and a block-style subgoal . . . . . . . . . . . . . . Subgoals with incompatible distance tables . . . . . . . . . . 33 36 47 48 49 51 51

List of Tables1.1 4.1 4.2 4.3 4.4 4.5 5.1 Partial 3x3x3 records list (as of March 27, 2008) . . . . . . . . CrossF2L versus BlockF2L . . . . . . . . . . . . . . . . . . . . CrossF2L/BlockF2L steps, greedy versus xed order . . . . . 3 31 32

Detailed CrossF2L steps (T=turns, F=frequency, C=cumulative, A=average) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Detailed BlockF2L steps (T=turns, F=frequency, C=cumulative, A=average) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Tripod with xed/free start, BlockF2L . . . . . . . . . . . . . Visited nodes in serial/parallel search . . . . . . . . . . . . . 37 44 60

A.1 Overestimated numbers of states reachable . . . . . . . . . .

xi

xii

LIST OF TABLES

ForewordRubiks Cube became a worldwide phenomenon in the early 1980s, puzzling young and old alike. At rst it seemed nearly impossible to solve, but soon people invented solving methods and many were published in magazines or as books. Competitions arose in which people tried to solve the cube in the shortest time, culminating in a world championship in 1982 with competitors from 19 countries. Soon after this, the cubes popularity faded quickly. For many years, new puzzles similar to the original cube kept emerging from time to time, and fans around the world still existed. But it wasnt until around 2002 and internet discussion forums that they became aware of and connected to each other. In 2003, the rst ofcial championships after 20 years were held, and the year 2007 saw 53 ofcial championships around the world.

The solving times have improved a lot over the years. The world champion of 1982 took 22.95 seconds in his best of three attempts, now the world record is 9.18 seconds for a single solve and 11.33 for an average of ve solves. There are three main reasons for this: Better cubes, more highly devoted people, and better solving methods. This diploma thesis deals with that third aspect, solving methods. Several different methods are used to solve the cube, all working the same basic way. Each starts by solving a certain few pieces, adding some more, and so on until the cube is fully solved. For example, the typical beginxiii

xiv

FOREWORD

ner method starts by solving the top layer one piece at a time, adding the middle layer one piece at a time, then the bottom layer in four steps. Computer programs which can solve the cube already exist. Some implement a xed human method, others use general search algorithms to nd shortest solutions possible. In most cases the cube can be solved in 18 turns, and some programs are able to nd these very short solutions. Optimal solutions however are incomprehensible to humans. At best they can be somewhat followed, but humans arent able to repeat this feat except with specialized methods, a lot of time for trial and error, as well as some luck. The fastest human solvers usually use around 50 to 60 turns. This diploma thesis describes the development and results of a exible computer program for analyzing human solving methods. The idea is to let someone explain any method to the computer in a simple way, just specifying the subgoals on the path to the nal goal of a fully solved cube. The program then nds the actual turns to reach the subgoals and provides statistics to evaluate the quality of the method, as well as sample solves that the user can then study in detail. The overall purpose thus is to test new method ideas quickly without having to do the dirty work, judge methods to nd the best, and learn from the found solutions. Also, while this thesis covers only the standard cube, the program is actually designed to handle other puzzles as well. For this, the puzzle is described by the user as part of the input.

Overview The remainder of this thesis is organized as follows: Chapter 1 describes the Rubiks cube, introduces the cubing community, shows some human solving methods and observes what they have in common. Chapter 2 discusses several previous program