Oplossing Rubik-kubus stapje versneld

Het is Tomas Rokicki gelukt om een stap dichterbij 'God's Number' te komen: hij heeft een manier gevonden om de Rubik-kubus altijd in 25 stappen op te lossen. Het oude record stond op 26 slagen.

Halverwege augustus vorig jaar wisten twee studenten van de universiteit in Boston een methode te ontwikkelen om de Rubik-kubus in maximaal 26 slagen op te lossen, ongeacht de beginstand. Wiskundige Tomas Rokicki heeft hun record echter aangescherpt met een verlaging van het maximumaantal slagen naar 25. Het minimumaantal stappen dat nodig is om elke verhusselde Rubik-kubus op te lossen, ook wel bekend als 'God's Number', zou volgens wetenschappers tussen de 20 en 25 liggen.

Rokicki heeft zijn record bewerkstelligd door alle mogelijke configuraties van de kubus in te delen in twee miljard verzamelingen, die ieder weer uit twintig miljard elementen bestaan. Een groot aantal verzamelingen kon dankzij symmetrie genegeerd worden, waardoor het totaal aantal mogelijke posities gereduceerd werd. Door oplossingen voor de overgebleven verzamelingen met zestien miljoen posities per seconde door te rekenen, kostte het de gebruikte computer een kleine 63 dagen om alle mogelijke oplossingen te beschouwen. Terwijl de onderzoekers uit Boston van een supercomputer gebruikmaakten, heeft Rokicki het rekenwerk weten te klaren met een workstation met 8GB aan geheugen en een Intel Core 2 Quad Q6600, die op 1.6GHz geklokt was. Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.

Reacties (77)

[waffels]

Heeft er iemand enig idee hoeveel verschillende configuraties zo'n kubus in totaal kan hebben? Ik ga er vanuit dat dit getal zo groot is dat men ze niet allemaal kan nagaan om het gods number te berekenen?

[slow whoop]

Aantal verschillende permutaties voor een 3x3x3 kubus = 43,252,003,274,489,856,000

[Reactie gewijzigd door slow whoop op 23 juli 2024 14:16]

[.oisyn]

Simpel. Elk middelste blokje van een 3x3 vlak zit "vast" op de kubus. Je kunt ze wel roteren, maar daardoor verandert z'n positie niet. Je hebt 8 hoekpunten en 12 zijkanten, dus als je een kubus in elkaar zou zetten kun je (8! * 3⁸) * (12! * 2¹²) = 519.024.039.293.878.272.000 verschillende combinaties maken.

Echter, niet al die combinaties zijn mogelijk zonder blokjes van de kubus af te halen en er weer op te zetten. Zo kun je twee zijkanten niet omwisselen (combinaties / 4) en hoekpunten niet roteren (combinaties / 3). Je houdt dus 519.024.039.293.878.272.000 / (3*4) = 43.252.003.274.489.856.000 combinaties over . In woorden: meer dan 43 triljoen mogelijkheden.

[Reactie gewijzigd door .oisyn op 23 juli 2024 14:16]

[Gamo]

"Rokicki heeft zijn record bewerkstelligd door alle mogelijke configuraties van de kubus in te delen in twee miljard verzamelingen,..."

Hij heeft ze allemaal laten berekenen, en wat de oplossing daarvan dan is.

[Anoniem: 236645]

Allemaal erg knap enzo, maar waarom word er eigenlijk zoveel tijd, geld en aandacht gestoken in een puzzel? Puur om nieuwe bewijstechnieken te testen of zijn er mensen ook daadwerkelijk zo geïnteresseerd in een spelletje?

Ik zie het nut van dit onderzoek niet direct.

[g4wx3]

Nieuwe inzichten krijgen om een oplossing voor een probleem te berekenen. Er zijn namelijk nog talrijke problemen te bedenken, die niet via een algoritme oplosbaar zijn, sommige zijn zelfs niet met de computer te berekenen.
Onrechtstreeks komen we misschien meer te weten over de werking van onze hersens.

Bijvoorbeeld zou het schaakprobleem zou worden aangepakt. Hoe kunnen hersenen zo snel een beslissing maken, terwijl een computer eerst naar 1000den voorbeelden moet kijken. Zoude onze hersens Alle mogelijke zetten die op elkaar lijke van elkaar wegfilteren, waardoor we ons kunnen concentreren op de gevolgen van een zet?

[Anoniem: 217986]

Euh .. Klein foutje gevonden, 't waren geen 63 hele dagen (wat echt ziek lang is voor een supercomputer ):

"Next month, at a symposium in Canada, Dan Kunkle, a doctorate student in computer science, and Gene Cooperman, a professor of computer science, will announce the lowest proven "God's number" to date: 26.

To achieve this feat, they relied not on a religious higher power, but on a computing higher power: 128 CPUs that ran for over 63 hours to do the bulk of the calculation. If you tried the same calculation on a personal computer, it would take about 8,000 hours, according to Kunkle."
Bron

"The ultimate solution to the Rubik's cube has come closer thanks to hours of number crunching conducted on a supercomputer, which took 63 hours to crank out the proof."
Bron2

[dcm360]

Tja, maar het gaat ook niet om de supercomputer maar om een redelijk normaal werkstation:

heeft Rokicki het rekenwerk weten te klaren met een workstation met 8GB aan geheugen en een Intel Core 2 Quad Q6600

[MneoreJ]

Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.

Tja, wat is normaal de gedachte achter onderklokken? Ten eerste energiebesparing (lijkt me hier niet relevant), ten tweede het verhogen van de betrouwbaarheid. En dat laatste is best aannemelijk, want je hebt tenslotte geen zak aan het doorrekenen van een paar miljard scenario's om tot een maximum te komen als blijkt dat er hier en daar wel een paar foutjes gemaakt kunnen zijn die het resultaat waardeloos maken.

Maar natuurlijk kan de gast ook gewoon een tikfout hebben gemaakt, of zijn BIOS verkeerd afgesteld hebben...

Edit: maximum, geen minimum. Belangrijk detail.

[Reactie gewijzigd door MneoreJ op 23 juli 2024 14:16]

[bbob]

betrouwbaarheid vraag ik me af. Intel cpu's zijn zelfs perfekt te overclocken dus kun je zelfs stellen dat ze zoals ze geleverd worden eigenlijk al standaard underclocked zijn.

Het lijkt me ook sterk dat er bij underclocken minder fouten zijn in vergelijking tot de standaard snelheid. Dit soort cpu's mogen dat soort fouten niet eens maken.

[MneoreJ]

Welnu, CPUs maken nou eenmaal fouten. Hoe hoger de termperatuur, hoe meer. Er is geen temperatuur waarbij je kan zeggen dat de CPU foutloos loopt; je kunt alleen zeggen dat het interval tussen fouten dan zo lang is dat het niet meer relevant is. Zelfs Intel zal jou niet snel de garantie geven dat je CPU foutloos functioneert, al mogen ze het ding diepvriezen en in twee meter lood installeren. Dat "perfect te overklokken" wordt meestal ook maar beperkt getest, hoor -- dat bijvoorbeeld je CPU SuperPI X minuten lang goed uitvoert bewijst nog niet dat alles goed werkt.

Als je vier cores meer dan een maand op volle belasting gaat draaien om een zeer discontinu probleem op te lossen is underclocken voor de zekerheid zo slecht nog niet. Hadden de cores het ook goed gedaan op volle snelheid? Waarschijnlijk wel, maar ik moet dan ook zeggen dat ik zoiets nog nooit heb geprobeerd.

Een alternatief zou zijn geweest om twee (of meer) onafhankelijke systemen hetzelfde te laten berekenen en de resultaten naast elkaar te leggen. Dat is beter dan één systeem zo betrouwbaar mogelijk maken.

Edit: "discontinu" is minder dubbelzinnig dan "discreet".

[Reactie gewijzigd door MneoreJ op 23 juli 2024 14:16]

[Madrox]

Lijkt me toch sterk wat je nu zegt. Volgens mij moet een CPU die Intel levert, die bijv. op 3 GHz is gecertificeert, foutlous werken. Ook op volle CPU-belasting.

[MneoreJ]

Natuurlijk, maar definieer "foutloos". Denk daar voor mijn part aan zoiets als "een kans van 50% op één enkelbitsfout per 1,000 jaar bij een temperatuur van 40 graden en een stralingsniveau van niet meer dan 1 mSv per jaar" of zoiets extreems, wat in de praktijk dus "foutloos" is omdat de chip allang gestorven is aan natuurlijke oorzaken voor die periode bereikt wordt. Ik heb geen idee van wat voor garanties Intel aflevert, trouwens.

Zo vaag als "100% correct" zal het in ieder geval niet zijn; je kunt natuurlijke processen nou eenmaal niet voor 100% beheersen. We denken graag dat CPU's perfecte machientjes zijn die alleen de fout in kunnen gaan als een of ander botte boer een ontwerpfout heeft gemaakt, maar zo is het natuurlijk niet. CPU's zijn wel opmerkelijk betrouwbaar, maar desondanks niet volmaakt. Een kans op fouten bestaat altijd; het gaat erom dat die kans bij normaal gebruik zo irrelevant mogelijk is.

[CyBeR]

Niks sterks aan. Waarom denk je dat ze in de ruimtevaart 200MHz processoren gebruiken? (En dan nog een speciale uitvoering ook). Om rekenfouten te voorkomen.

Die dingen maken fouten. Net als geheugen. Dat gebeurt niet vaak, maar 't gebeurt wel. (En meestal merk je 't aan een random crash.)

[kimborntobewild]

@CyBeR:
Omdat in de ruimte veel meer straling is. Moderne quad-core CPU's hebben veel minder weerstand tegen straling. Op aarde heb je daar niet zoveel last van, maar in de ruimte des te meer.
Bij 200Mhz chips zijn de schakelingen groter waardoor er veel minder kans is op schade door straling.

[Bever!]

Gedachte achter het onderklokken zal het minimaliseren van rekenfoutjes zijn..

[Anoniem: 196662]

Misschien durfde meneer een cpu geen 2maand laten draaien op volle lading (hallo folding? ).
Of de cpu werktte gewoon niet op maximale belasting en underclockte naar 1.6 is ook een mogelijkheid.

[Soze]

Of domweg energiebesparing. Dikke kans dat het doorrekenen net zo snel werkt op 1.6 GHz omdat de FSB of het geheugen de bottleneck is voor dit probleem en niet de CPU snelheid...

[HenkEisDS]

Ik geloof dat bij supercomputers het belangrijker is de data snel genoeg toe en af te voeren naar/van de processor dan de kracht van de processor zelf. Misschien dat de verhouding tussen doorvoorsnelheid en processorkracht zo beter klopte?

A supercomputer is a device for turning compute-bound problems into I/O-bound problems. - Ken Batcher

[Moe_Szyslak]

Dat kan best kloppen ja. Ik heb ook een Q6600 en als hij niet genoeg belast word, dan clocked hij automatisch terug naar 1,6Ghz. Dit is in de BIOS in te stellen. Je kan het automatisch underclocken ook uit zetten, mocht je dat willen.

[TD-er]

Mijn eerste idee was dat mogelijk de verhouding van het gebruikte geheugen en de bus-frequentie mogelijk iets beter op elkaar aansluit, waardoor het geheugen mogelijk net een fractie sneller zou kunnen voor deze specifieke toepassing.
Zo'n 70 dagen geleden was 2 GB 1066 MHz geheugen mogelijk wat minder goed verkrijgbaar?

[Reactie gewijzigd door TD-er op 23 juli 2024 14:16]

[fevenhuis]

Wellicht probeerde men met het onderklokken het kacheleffect van een 100% load quadcore wat te verminderen. Je kunt er je kantoor er aardig mee verwarmen hoor.
Laat staan hoeveel herrie een gemiddelde ungetweakte machine produceerd onder lange load sessies, je zal dan toch echt wat harder door de telefoon moeten praten

[Anoniem: 242982]

wel ferm dat hij het heeft uitgerekend met een gewone computer, ik vraag me ook af hoe snel die supercomputer het de vorige keer heeft gedaan?

[g4wx3]

volgende keer is het iemand die het op zijn laptop heeft gedaan, onderweg naar huis
//of op zijn iphone...

[Reactie gewijzigd door g4wx3 op 23 juli 2024 14:16]

[LOTG]

Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.

Of er een dikke FSB op zetten.

Maar het is toch opzich een snelle verbetering van het record vind ik. Als je bedenkt dat er toch wel wat tijd achter zit om het algoritme te bedenken en te testen.

[Reactie gewijzigd door LOTG op 23 juli 2024 14:16]

[Anoniem: 244576]

Ik geloof dat de kans dat, als je hem uit elkaar haalt en weer @ random in elkaar zet, dat de kubus dan nog oplosbaar is 1/12 is.

Ik kan hem in ieder geval onder de 50 seconden oplossen , ik heb alleen wel iets meer dan 25 moves nodig, ik denk een fractie 3 keer zoveel of zo

[_Dexter_]

Die rubix cube van de foto bij het artikel is nou niet echt heel moeilijk op te lossen

[Vaan Banaan]

Klopt, dat hadden ze bij de redactie ook in de gaten. (Tip: houd de muispointer eens boven het plaatje)

[JonathanP]

Oplossen van een Rubik's Cube? Daar is toch Lego voor?
Je kunt ook gewoon een paar oplossingen uit je hoofd leren