Vandaag hebben wij niet heel veel meer gedaan. Ongeveer voor een half uur voor de presentatie hebben wij ontdekt dat twee implementaties meerdere keren dezelfde oplossing geeft. Dat was dus nog even spannend om het op te lossen. Maar, we hebben gevonden waar het zat, namelijk in het feit dat er meerdere oriëntatie predicaten zijn (voor meerdere oriëntaties) en dat deze dus allemaal waar zijn als er een nog hogere oriëntatie bestaat.
Daarna de presentatie. Waarin wij ons programma toegelicht hebben. Rémi heeft het meeste het woord gedaan, dat is omdat hij zo mooi spreken kan.
Na onze spetterende presentatie hebben wij onze blog nog eens onder handen genomen, het resultaat staat nu online en wij zijn nu eindelijk klaar met ons project!
vrijdag 24 juni 2011
donderdag 23 juni 2011
Dag 4
Onze laatste officiële werkdag! Vandaag zijn wij van plan om nog een methode te implementeren en de andere methoden nog efficiënter te maken.
Wij hebben op deze laatste dag zelf een methode verzonnen. Na wat hevige discussies zijn we erop uitgekomen een 'anti-chaos' methode te implementeren. Deze methode zal proberen een zo optimaal mogelijke oplossing te geven door alleen een beweging toe te passen als deze het aantal vakjes dat op de juiste plek zit vergroot.
Het is duidelijk dat dit niet vaak tot een oplossing zal leiden. Dit komt doordat er ergens tijdens het oplossen waarschijnlijk een beweging gemaakt worden moet die de chaos vergroot om vervolgens een betere toestand te bereiken. Maar, deze optie wordt natuurlijk uitgesloten in ons programma.
Volgens ons werkt dit programma wel heel goed met de laatste drie bewegingen, dus hebben wij bedacht dit in iedere final predicaat in de andere methoden te gebruiken. Zo is ons werk toch niet voor niets geweest.
Verder hebben wij nog één klein probleem opgelost. Wat in de door de programma's gegenereerde oplossingen vaak voorkwam waren twee oplossingen, bijvoorbeeld [rrr, u, d, r, l] en [rrr, u, d, l, r]. Hier kun je zien dat de laatste twee stappen in twee verschillende volgorden uitgevoerd kunnen worden en nog steeds tot dezelfde oplossing leiden. Wij hebben een predicaat geschreven (prior/2) waarbij de voorkeur van volgorde als volgt wordt: eerst r dan l, eerst u dan d en eerst f dan b. Door dit predicaat toe te passen binnen ieder next predicaat, hebben wij de 'dubbele' oplossing uit de output weten te verwijderen.
Wij hebben op deze laatste dag zelf een methode verzonnen. Na wat hevige discussies zijn we erop uitgekomen een 'anti-chaos' methode te implementeren. Deze methode zal proberen een zo optimaal mogelijke oplossing te geven door alleen een beweging toe te passen als deze het aantal vakjes dat op de juiste plek zit vergroot.
Het is duidelijk dat dit niet vaak tot een oplossing zal leiden. Dit komt doordat er ergens tijdens het oplossen waarschijnlijk een beweging gemaakt worden moet die de chaos vergroot om vervolgens een betere toestand te bereiken. Maar, deze optie wordt natuurlijk uitgesloten in ons programma.
Volgens ons werkt dit programma wel heel goed met de laatste drie bewegingen, dus hebben wij bedacht dit in iedere final predicaat in de andere methoden te gebruiken. Zo is ons werk toch niet voor niets geweest.
Verder hebben wij nog één klein probleem opgelost. Wat in de door de programma's gegenereerde oplossingen vaak voorkwam waren twee oplossingen, bijvoorbeeld [rrr, u, d, r, l] en [rrr, u, d, l, r]. Hier kun je zien dat de laatste twee stappen in twee verschillende volgorden uitgevoerd kunnen worden en nog steeds tot dezelfde oplossing leiden. Wij hebben een predicaat geschreven (prior/2) waarbij de voorkeur van volgorde als volgt wordt: eerst r dan l, eerst u dan d en eerst f dan b. Door dit predicaat toe te passen binnen ieder next predicaat, hebben wij de 'dubbele' oplossing uit de output weten te verwijderen.
woensdag 22 juni 2011
Dag 3
Deze dag hebben wij het Thistlethwaite's Algorithm én een ZZ achtige methode geïmplementeerd.
Over het Thistlethwaite's Algorithm. Één cube kan in een bepaalde 'groep' worden gezet. Een willekeurige cube staat in de groep G0 = < L, R, F, B, U, D>. Dit betekent dat van iedere zijde iedere mogelijke beweging gemaakt worden mag. In het originele algoritme wordt er als volgt door de groepen gewerkt:
Voor de overige groepen is er een vergelijkbare berekening mogelijk, die zal ik aan jullie laten ;) Wij hebben een kleine aanpassing op dit algoritme gemaakt, wij zetten de cube in de < L, R, F, B, U2, D2 > groep en dan meteen in de < L2, R2, F2, B2, U2, D2 > groep.
Over het Thistlethwaite's Algorithm. Één cube kan in een bepaalde 'groep' worden gezet. Een willekeurige cube staat in de groep G0 = < L, R, F, B, U, D>. Dit betekent dat van iedere zijde iedere mogelijke beweging gemaakt worden mag. In het originele algoritme wordt er als volgt door de groepen gewerkt:
G1 = < L, R, F, B, U2, D2 >
G2 = < L, R, F2, B2, U2, D2 >
G3 = < L2, R2, F2, B2, U2, D2 >
G3 is duidelijk een hele kleine groep, hier zijn nog slechts 6 bewegingen mogelijk. Zouden wij 7 bewegingen diep kijken, en gebruik maken van next/2 of next/3 dan zou de complexiteit zijn: 76 441 ( 6 * 5 * ( 1/5 * 4 + 4/5 * 5 ) wat natuurlijk heel veel kleiner is dan de aller lompste methode (machten van 18) die 612 220 032 permutaties zou betekenen.
Voor ons project is dat voldoende want het plaatsen van die extra groepen tussendoor is een koud kunstje als je eenmaal door hebt hoe het werkt.
--- Even tussendoor; Sorry als de informatie in deze blog erg hard gaat, maar wij hebben nou eenmaal heel veel kennis in dit domein en tijdens dit project nog meer kennis opgedaan. Alles in detail uitleggen is geen optie omdat er voor sommige stukjes nou eenmaal wat kennis verondersteld wordt die wij niet 1,2,3 bij jou kunnen leveren. ---
Voor de ZZ methode van Zbigniew Zborowski hebben wij eveneens aanpassingen gedaan. Van de EO+line hebben wij EO gemaakt. Dit is de eerste fase.
Wij vervolgen in de < L, R, F, B, U2, D2 > groep om een 2x2x2 block te maken.
Daarna blijven wij de in de < L, R, F, B, U2, D2 > groep naar een oplossing zoeken.
Hierdoor hebben wij duidelijk een orient-first methode gecombineerd met een blockbuilding methode (denk aan de Ryan Heise methode).
Ons inziens zou het een goede methode zijn om EO+line te doen om vervolgens in een bijzondere groep te komen (en te blijven) namelijk < U, XD, XF, XB, R, L > ofwel < U, R, L >
Deze groep heeft 3 * 3 bewegingen, maar vanwege de manier waarop next/2/3 in elkaar zitten zou de complexiteit 9 * 6 * 4 * 4 * 4 * ... zijn ( (1 / 3 * 6 + 2/3 * 3) = 4 ) . Let natuurlijk dat een computer x,y,z neutraal is en dat EO+line geen diepe ruimte zal zijn.
Zou er genoeg tijd zijn dan zou het heel leuk zijn dit verder uit te werken.
Ná deze week begint onze vakantie en kunnen wij écht leuke dingen gaan doen!
Ná deze week begint onze vakantie en kunnen wij écht leuke dingen gaan doen!
dinsdag 21 juni 2011
Dag 2
Nadat wij gisteren alle bewegingen én de opeloste toestand hebben beschreven, kunnen wij vandaag beginnen aan onze brute force methode! Wij hebben ervoor gekozen om deze implementatie niet verder te laten zoeken dan een oplossing van 7 bewegingen, om onze computers niet al te veel te belasten.
De implementatie lijkt heel simpel: voer een paar bewegingen uit en kijk of je iets goeds bereikt. Wij voorzagen al een aantal problemen...
Als eerste het probleem waarbij onze methode achter elkaar dezelfde moves blijft uitvoeren. Één keer r, dan rr, dan nog een keer r... Of eerst l dan r en dan weer l. Dat schiet niet op. Dus hebben wij twee predicaten geschreven om dit probleem op te lossen. Next/2 wordt eigenlijk alleen gebruikt voor de tweede beweging, omdat er nog maar één beweging aan vooraf is gegaan. Het controleert of de nieuwe beweging niet gemaakt wordt aan dezelfde zijde als waar de eerste beweging gemaakt werd. Daarna komt next/3, die ditzelfde nagaat, maar daarbij ook nog één stap verder terugkijkt.
Om het implementeren van deze predicaten makkelijk te houden, hebben wij bij moves/3 één argument toegevoegd, die beschrijft aan welke zijde de beweging plaatsvindt.
Onze code zou nu al heel wat meer kunnen doen, maar komt nu alleen nog maar terug met oplossingen die exact 7 bewegingen kosten, terwijl er ook oplossingen kunnen zijn die minder bewegingen gebruiken. Daarom hebben wij een nóg een extra predicaat in het leven geroepen namelijk solved1/2. Deze kijkt eerst of er een oplossing is gevonden, en zal deze als resultaat teruggeven (dit met behulp van solved/1, maar ook als er geen oplossing is gevonden zal dit predicaat slagen. Zo kan de brute force methode de hele zoekruimte doorzoeken, maar tegelijkertijd alle gevonden oplossingen teruggeven.
en mét
Als niet next/2 of next/3 gebruikt, dan is de complexiteit natuurlijk 18 * 18 * 18 * ... En dat is 'best wel groot.'
Mét next/2 of next/3 is de complexiteit kleiner, namelijk 18 * 15 * (1/5 * 12 + 4/5 * 15 = 14.4) * 14.4 * 14.4 * ...
Dit betekent dat als je 7 bewegingen diep kijkt zónder de optimalisatie dan is jouw ruimte 612 220 032 permutaties ( 18 ^ 7 ) en mét 167 176 883 ( 18 * 15 * ( 14.4 ^ 5 ) )
Alle bovengenoemde predicaten hebben wij overigens in het bestand gezet waarin de bewegingen worden beschreven, omdat wij denken dat deze bij andere methoden ook nog van pas kunnen komen.
Ons resultaat van vandaag: de methode kan binnen een redelijke tijd alle oplossingen vinden van een cube die binnen 7 bewegingen oplosbaar is. Maar, dit kan vast efficiënter...
De implementatie lijkt heel simpel: voer een paar bewegingen uit en kijk of je iets goeds bereikt. Wij voorzagen al een aantal problemen...
Als eerste het probleem waarbij onze methode achter elkaar dezelfde moves blijft uitvoeren. Één keer r, dan rr, dan nog een keer r... Of eerst l dan r en dan weer l. Dat schiet niet op. Dus hebben wij twee predicaten geschreven om dit probleem op te lossen. Next/2 wordt eigenlijk alleen gebruikt voor de tweede beweging, omdat er nog maar één beweging aan vooraf is gegaan. Het controleert of de nieuwe beweging niet gemaakt wordt aan dezelfde zijde als waar de eerste beweging gemaakt werd. Daarna komt next/3, die ditzelfde nagaat, maar daarbij ook nog één stap verder terugkijkt.
Om het implementeren van deze predicaten makkelijk te houden, hebben wij bij moves/3 één argument toegevoegd, die beschrijft aan welke zijde de beweging plaatsvindt.
Onze code zou nu al heel wat meer kunnen doen, maar komt nu alleen nog maar terug met oplossingen die exact 7 bewegingen kosten, terwijl er ook oplossingen kunnen zijn die minder bewegingen gebruiken. Daarom hebben wij een nóg een extra predicaat in het leven geroepen namelijk solved1/2. Deze kijkt eerst of er een oplossing is gevonden, en zal deze als resultaat teruggeven (dit met behulp van solved/1, maar ook als er geen oplossing is gevonden zal dit predicaat slagen. Zo kan de brute force methode de hele zoekruimte doorzoeken, maar tegelijkertijd alle gevonden oplossingen teruggeven.
en mét
Als niet next/2 of next/3 gebruikt, dan is de complexiteit natuurlijk 18 * 18 * 18 * ... En dat is 'best wel groot.'
Mét next/2 of next/3 is de complexiteit kleiner, namelijk 18 * 15 * (1/5 * 12 + 4/5 * 15 = 14.4) * 14.4 * 14.4 * ...
Dit betekent dat als je 7 bewegingen diep kijkt zónder de optimalisatie dan is jouw ruimte 612 220 032 permutaties ( 18 ^ 7 ) en mét 167 176 883 ( 18 * 15 * ( 14.4 ^ 5 ) )
Alle bovengenoemde predicaten hebben wij overigens in het bestand gezet waarin de bewegingen worden beschreven, omdat wij denken dat deze bij andere methoden ook nog van pas kunnen komen.
Ons resultaat van vandaag: de methode kan binnen een redelijke tijd alle oplossingen vinden van een cube die binnen 7 bewegingen oplosbaar is. Maar, dit kan vast efficiënter...
maandag 20 juni 2011
Dag 1
Vandaag begon onze dag om 11:00 op Science Park. Wij hadden een brainstomsessie met Arnoud Visser over de aanpak van ons project. Gelukkig kwamen wij goed voorbereid (zie dag 0). Na dit gesprek zijn wij snel het robolab uitgevlucht en zijn wij thuis aan de slag gegaan met onze cube.
Allereerst hebben wij besloten hoe wij de cube zullen gaan representeren in ons programma. Wij hebben voor een lijst gekozen met 54 elementen die elk één vlakje van de cube representeren. De vlakjes hebben ieder een unieke naam gekregen. Zo is R0 het middelste vlakje van de rechterzijde en U1 het hoekblokje helemaal linksonder aan de onderkant van de cube (zie foto). De cube die in de foto te zien is, heeft het voor ons een stuk makkelijker gemaakt de moves te beschrijven, maar daarover later meer.
Na het kiezen van de representatie, leek het ons het verstandigst om aan de implementatie van de bewegingen te beginnen. Dit, omdat de bewegingen in iedere methode hetzelfde blijven. Het lijkt ons het handigst om een apart bestand te maken waarin alle bewegingen worden beschreven en deze dan later in elke methode apart te 'consulten'.
Het beschrijven van move/3 was bijzonder veel werk, waar niet veel intelligentie voor vereist was. Het eerste argument van dit predicaat is de naam van de beweging (bijvoorbeeld uuu om de bovenkant van de cube drie keer naar rechts te draaien), het tweede argument is de huidige staat en het laatste argument is de nieuwe staat, die verkregen is door de beweging toe te passen.
Ook hebben wij in het bestand nog een solved/1 predicaat beschreven, die slaagt als de cube opgelost is en een scramble/3 predicaat dat een aantal bewegingen op de cube kan uitvoeren om deze door elkaar te brengen.
zondag 19 juni 2011
Dag 0
In plaats van naar de kerk te gaan, hebben wij ons op zondag verdiept in de verschillende methoden om een Rubic's Cube (cube) op te lossen. Een permutatie van een cube wordt in de wereld van de 'cubers' gedefinieerd als de zijde van de cubes, bijvoorbeeld r is 90° graden het rechter vlak met de klok mee en dd is 180° de 'down' kant van de cube bewegen.
Tijdens ons project zullen wij beginnen met een brute force implementatie van ons programma. In deze implementatie zal de computer alle mogelijke moves gaan toepassen om zo uiteindelijk tot een oplossing te komen. Wij denken nu al dat dit veel efficiënter kan (en dat brute force niet de grootste uitdaging is), dus wij zijn op zoek gegaan naar andere methoden om de cube zo optimaal mogelijk op te lossen.
Een beetje rondkijken op internet (en een hoop voorkennis van Rémi) leverde twee fijne methodes op: het Thistlethwaite's Algorithm en de ZZ method naar Zbigniew Zborowski.
In beide strategieën wordt er geprobeerd om het aantal bewegingen dat er gemaakt kan worden te reduceren. Aan het begin zijn dit natuurlijk 18 (6*3) bewegingen, daarna zijn er nog maar 15 nuttige bewegingen over, want twee keer achter elkaar aan hetzelfde vlak draaien kan natuurlijk ook in één beweging..
In het Thistlethwaite algoritme wordt de cube in een bepaalde stand gebracht waardoor deze met slechts 6 verschillende bewegingen oplosbaar is. De complexiteit neemt daarmee sterk af. Dit algoritme ligt aan de basis van bijna ieder algoritme dat gebruikt wordt door computers.
In de ZZ methode, dé methode die door cube fanaten gebruikt wordt, wordt de cube óók naar een bepaalde stand gebracht, maar ditmaal naar één waarbij de cube met 9 verschillende bewegingen oplosbaar is. Negen bewegingen zijn natuurlijk ook aanzienlijk veel minder dan 18, dus ook dit is een goede methode om het oplossen te starten.
Tijdens ons project zullen wij beginnen met een brute force implementatie van ons programma. In deze implementatie zal de computer alle mogelijke moves gaan toepassen om zo uiteindelijk tot een oplossing te komen. Wij denken nu al dat dit veel efficiënter kan (en dat brute force niet de grootste uitdaging is), dus wij zijn op zoek gegaan naar andere methoden om de cube zo optimaal mogelijk op te lossen.
Een beetje rondkijken op internet (en een hoop voorkennis van Rémi) leverde twee fijne methodes op: het Thistlethwaite's Algorithm en de ZZ method naar Zbigniew Zborowski.
In beide strategieën wordt er geprobeerd om het aantal bewegingen dat er gemaakt kan worden te reduceren. Aan het begin zijn dit natuurlijk 18 (6*3) bewegingen, daarna zijn er nog maar 15 nuttige bewegingen over, want twee keer achter elkaar aan hetzelfde vlak draaien kan natuurlijk ook in één beweging..
In het Thistlethwaite algoritme wordt de cube in een bepaalde stand gebracht waardoor deze met slechts 6 verschillende bewegingen oplosbaar is. De complexiteit neemt daarmee sterk af. Dit algoritme ligt aan de basis van bijna ieder algoritme dat gebruikt wordt door computers.
In de ZZ methode, dé methode die door cube fanaten gebruikt wordt, wordt de cube óók naar een bepaalde stand gebracht, maar ditmaal naar één waarbij de cube met 9 verschillende bewegingen oplosbaar is. Negen bewegingen zijn natuurlijk ook aanzienlijk veel minder dan 18, dus ook dit is een goede methode om het oplossen te starten.