wally

De dagen dat je je suf zocht naar Wally in de bekende ‘Waar is Wally?’-boeken zijn voorbij. Een student heeft een computeralgoritme ontwikkeld dat Wally praktisch altijd razendsnel kan opsporen.

Je kent ze vast wel: de ‘Waar is Wally’-boeken, waarin je op overvolle pagina’s op zoek moet naar de standaard in blauwe broek en rood met wit gestreepte trui gekleed gaande Wally. Het kan soms een hele zoektocht blijken te zijn. Maar die tijden zijn voorbij. Randal Olson, student aan de Michigan State University heeft een computeralgoritme ontwikkeld dat Wally recordbrekend snel op kan sporen.

Waar is Wally niet? Of zelden?
Het algoritme is gebaseerd op de 68 locaties waarop Wally zich in de zeven edities van de ‘Waar is Wally?’-boeken bevindt. Een analyse van die locaties laat allereerst zien dat Wally bijna nooit opduikt in de linkerbovenhoek van de pagina. Ook bevindt Wally zich zelden aan de randen en nooit aan de onderkant van de rechterpagina.

Maar waar bevindt Wally zich dan wel?
Om dat uit te zoeken, besloot Olson dit probleem te benaderen als het ‘probleem van de reizende koopman’. “We moeten elke mogelijke locatie waar Wally zich kan bevinden controleren, terwijl we daarbij zo min mogelijk tijd verspillen. Dat betekent dat we een zo groot mogelijk oppervlak moeten bestrijken zonder dat we plaatsen daarbij meerdere keren bezoeken.” Klinkt logisch. Maar hoe? “In computertermen betekent dat dat we een lijst maken van de 68 punten waarop Wally zich kan bevinden en dan de volgorde waarin we ze gaan bezoeken, bepalen. Dus we moeten elke mogelijke volgorde van deze punten proberen en zo de volgorde vinden waarbij de afgelegde afstand het kortst is.” En dat is nog niet zo eenvoudig als je wellicht zou denken. “Deze 68 punten kunnen op ~2.48 x 10^96 manieren geordend worden. Om dat in het juiste perspectief te plaatsen: dat zijn meer mogelijkheden dan het aantal atomen in het universum.” Zelfs wanneer een supercomputer zich over dit vraagstuk zou buigen, zou het nog miljarden jaren duren voor we tot een oplossing komen. En dus moet Olson het over een andere boeg gooien.

Genetisch algoritme
En dat heeft hij gedaan. Hij besloot er een genetisch algoritme op los te laten. Zo’n algoritme ‘evolueert’. Het stelt een mogelijke oplossing vast en past vervolgens die oplossing aan totdat het op een betere oplossing stuit. Zodra het algoritme een betere oplossing heeft gevonden, verwerpt het de eerste oplossing en gaat verder knutselen aan de betere oplossing. Uiteindelijk komt het algoritme zo uit bij de beste oplossing.

De route
Als je het paadje dat het algoritme heeft uitgestippeld, volgt vind je Wally heel snel. Het pad ziet er zo uit:

optimaal

Natuurlijk is dat allemaal leuk en aardig, maar hoe kun je dat exacte pad nu onthouden zodra je een pagina uit het Waar is Wally?-boek voor je hebt? Olson erkent dat dat lastig is, maar hij denkt dat we enkele lessen uit het algoritme kunnen trekken. Namelijk: “De onderkant van de linkerpagina is een goede plek om te beginnen. Als Waldo niet op de onderste helft van de linkerpagina is, is hij waarschijnlijk helemaal niet op de linkerpagina te vinden. De bovenste 25 procent van de rechterpagina is de op één na beste plek om te kijken. Wally lijkt zich het liefst te verstoppen op dit deel van de rechterpagina.” En als je ‘m dan nog niet hebt: “Check de onderste helft van de rechterpagina. Wally heeft een afkeer van de onderste linkerhelft van de rechterpagina.”

Olson benadrukt dat het zelfs wanneer je deze route volgt, mogelijk is dat je Wally niet vindt. In de boeken zijn een paar pagina’s te vinden die hij aanduidt als ‘buitenbeentjes’. Als je Wally na het volgen van deze route nog niet gevonden hebt, heb je waarschijnlijk met zo’n buitenbeentje te maken en moet je het midden van de pagina’s of linksboven en rechtsboven zoeken. Als je het tenminste nog leuk vindt om Wally om te sporen, want laten we eerlijk zijn: met dit algoritme gaat de lol er wel een beetje af.