43 tryliony kombinacji, Google, roboty

Rok 1974. Erno - węgierski profesor architektury Budapeszteńskiej Akademii Sztuki Użytkowej tworzy łamigłówkę dla studentów, która w zamierzeniu ma im ułatwić pojmowanie przestrzeni. Jak dowiemy się z najróżniejszych źródeł, samemu autorowi rozwikłanie zagadki po raz pierwszy zajęło miesiąc. Nie mógł przypuszczać jaki sukces odniesie i z czym będzie kojarzone jego nazwisko przez kolejne 50 lat, a pewnie i dłużej. Pan ten (wtedy 30 letni wykładowca) nazywa się Rubik i chyba nikt nie powinien mieć już wątpliwości o czym będzie ten wpis.

Słowem wstępu

Niesamowicie popularna łamigłówka z Węgier, która choć najlepsze lata ma za sobą to wciąż pasjonuje całe rzesze ludzi. Czym będzie ten wpis? Postaram się przybliżyć tę kultową łamigłówkę i choć może się wydawać, że sama kostka nie jest w żaden sposób powiązana ze światem IT, dowiemy się np. jak Google pomogło zrozumieć działanie kostki oraz pojawi się dwa słowa o robotach. Nie będzie to natomiast poradnik typu „Jak ułożyć kostkę rubika” (Youtube pęka w szwach od tutoriali ludzi, którzy układają kostkę dużo szybciej ode mnie i pewnie potrafią to lepiej wytłumaczyć ;)). Zainteresowanych zapraszam do dalszej lektury.

Wpis ten zbiega się z Rubik's Cube World Championship 2015 (17‑19 lipca) czyli mistrzostwami świata w układaniu kostek na czas. Speedcuberzy spotykają się na kilku cyklicznych imprezach w roku, gdzie rywalizują ze sobą o miano najszybszego w najróżniejszych konkurencjach. Trzeba tutaj powiedzieć, że Polska ma kilku świetnych zawodników. W klasycznej konkurencji reprezentowali nas Michał Pleskowicz (5.81) i Jakub Kipa (6.36). Zawody w tym roku odbyły się w Sao Paulo, a fundusze na wzięcie udziału w wydarzeniu pierwszy z Polaków pozyskał dzięki polskiej platformie crowfundingowej: http://polakpotrafi.pl/projekt/mistrz-kostki-rubika. Poniżej klasyfikacja w konkurencji 3x3x3:

1. Feliks Zemdegs - Australia - 7.56
2. Mats Valk - Holandia - 8.56
3. Jakub Kipa - Polska - 8.63
4. Michał Pleskowicz - Polska - 8.82
5. Sayed Mohammad Hossein - Izrael - 8.82

Złoty okres dla Kostki Rubika to niewątpliwie lata ’80 ubiegłego wieku. Wtedy to fabryka magicznych sześcianów znajdująca się na Węgrzech nie nadążała z produkcją zabawek mimo pracy 24/7. W sumie sprzedano na całym świecie setki milionów tych łamigłówek, a trzeba zaznaczyć, że mowa tu tylko o oryginalnych kopiach.

Budowa, trochę matematyki i metody układania

Kostka Rubika to sześcian, w którym każda ze ścian podzielona jest na 9 pól. Celem gry jest takie rozwiązanie łamigłówki, aby każda ze ścian tworzyła jeden kolor. Biorąc pod uwagę liczbę kombinacji - jakie na kostce mogą się pojawić – wydawać to się może zadaniem niesłychanie trudnym. W przypadku tradycyjnej kostki (3x3x3) liczba ta wynosi aż 43 252 003 274 489 856 000 (43 tryliony). Aby zobrazować ogrom liczby znów możemy posłużyć się odległością Ziemia-Słońce. Wykorzystując taka liczbę kostek Rubika, aby każda z nich miała inny układ i by ściśle przylegały do siebie, moglibyśmy zbudować autostradę do Słońca, o szerokości… 900km.

Jeśli chodzi o metody rozwiązywania tej łamigłówki to jest ich przynajmniej kilka. Najpopularniejsza to LBL (Layer by Layer) oraz metoda Fridrich (CPOF). W pierwszej z nich układamy warstwa po warstwie. Nie jest najbardziej efektywna, jednak jednocześnie na tyle prosta do przyswojenia, że wielu od niej zaczyna. Wystarcza znajomość ok. 10 algorytmów do ułożenia kostki. Druga metoda jest uznawana za jedną z najbardziej efektywnych, stosowana przez wielu speedcuberów na całym świeci i pozwala osiągać czasy poniżej 10 sekund. Tutaj jednak trzeba znać ok. 120 algorytmów.

Robot vs. Kostka Rubika

CubeStormer 3 to nie pierwsza maszyna do rozwiązywania łamigłówki węgierskiego profesora, jednak to właśnie ona aktualnie dzierży miano najszybszej. Robot zbudowany na bazie Lego Mindstorms oraz Samsunga Galaxy S4. Telefon wykorzystywany jest do analizy kostki oraz instruowania czterech uchwytów robota jak manipulować poszczególnymi ścianami. Nie można zapominać też o sofcie stworzonym przez autorów odpowiadającym za rozwiązanie łamigłówki. 18 miesięcy – tyle zajęło autorom stworzenie i dopracowanie robota oraz optymalizacja programu. Jak najbardziej opłaciło się, 15 marca 2014 roku CubeStormer 3 pobił poprzedni rekord (5.270 – CubeStormer II) rozwiązując Kostkę Rubika w 3.253 sekundy i wpisując się do Księgi Rekordów Guinnessa (film poniżej, wszystko dzieje się dość szybko więc polecam uważnie oglądać ;)).

Liczba Boga i Google

Wszyscy układający kostki działają według algorytmów. Doprowadzenie do położenia rozwiązania łamigłówki zwykle zajmuje ponad 40 ruchów. God's number - nazwa pochodząca od jednego z algorytmów (God's), pozwalającego na ułożenie kostki wykorzystując najkrótszą sekwencję ruchów. W 2010 roku zespół naukowców przy pomocy infrastruktury Google i po kilku tygodniach obliczeń uzyskał odpowiedź na pytanie ile wynosi liczby Boga dla Kostki Rubika. 20 lub mniej - tyle ruchów wystarczy by ułożyć kostkę o dowolnym ułożeniu wejściowym. Warto dodać, że bez wsparcia Google, obliczenia na standardowym domowym komputerze z 2010 roku trwałby… 35 lat.

Ciekawostki

• Kostki sześcienne występują w wielu wydaniach (od 2x2x2 do 17x17x17)
• Wśród powszechnie dostępnych kostek dwunastościennych największy jest Petaminx (218 elementów), a liczba kombinacji ułożeń w jego wypadku to 19.5 sekswicyliardów (1.95*10^160)
• Aktualny rekord ułożenia kostki 3x3x3 stopami należy do Polaka (Jakub Kipa) i wynosi 20.57 sekund
• Aktualny rekord ułożenia kostki 3x3x3 z zawiązanymi oczami należy do Polaka (Marcin Kowalczyk) i wynosi 21.17 sekund

Co dalej?

Jeśli mowa o tradycyjnym układaniu kostek 3x3x3 (przez ludzi) to aktualne rekordy są dość mocno wyśrubowane i raczej nie ma co się spodziewać wielkich różnic na przestrzeni przyszłych lat. Jednak w przypadku robotów sprawa jest otwarta, kwestią czasu jest, aż znajdzie się kolejna grupa entuzjastów, która będzie chciała poświęcić swój czas i wiedzę na zbudowanie robota do układania tej kultowej łamigłówki w ekspresowym tempie wykorzystując nowsze rozwiązania software'owe/hardware'owe i inne podejście.

Na dzisiaj tyle jeśli chodzi o ciekawostki. Dziękuje za miłe przyjęcie pod poprzednim wpisem i do następnego razu!