Beeldherkenning blijft nog altijd een zeer moeilijke opdracht voor computers. Mensen kunnen dit zonder probleem, maar zien het niet altijd zitten om dat voor een zeer grote collectie foto's te doen. Door van beeldherkenning een spel te maken, kunnen mensen echter verleid worden om deze opdracht lange tijd vol te houden. Dit is waar de ESP game¹ voor ontwikkeld werd: laat mensen een online computerspel spelen om zo metadata te verzamelen die anders moeilijk te verkrijgen is.

Het idee achter dit computerspelletje is om de intelligentie van het menselijk brein spelenderwijs in te zetten om een taak uit te voeren waar computers niet toe in staat zijn (oorspronkelijk dus beeldherkenning). Het werd oorspronkelijk bedacht door Luis von Ahn van de Carnegie Mellon University. Google kocht een licentie om in 2006 een eigen versie van het spel te kunnen aanbieden (Google Image Labeler²), waarmee het haar zoekresultaten voor online afbeeldingen aanzienlijk kon verbeteren. Probeer er niet meer achter te zoeken: de versie van Google werd op 16 september 2011 offline gehaald naar aanleiding van de sluiting van Google Labs in september 2011.

Eenmaal aangemeld bij de ESP game wordt een gebruiker automatisch gekoppeld aan een willekeurige partner. De partners kennen elkaars identiteit niet en kunnen ook niet met elkaar communiceren. Eenmaal gematcht krijgen beide partners dezelfde afbeelding te zien. Hun taak bestaat erin om zo snel mogelijk een gemeenschappelijk woord op te geven. Ze doen dit uiteraard door woorden in te voeren die ze met de afbeelding associëren, waarmee ze meteen ook goede zoektermen voor de afbeelding opgeven. Zodra beide partners hetzelfde woord hebben ingevoerd (niet noodzakelijk tegelijkertijd), krijgen ze een andere afbeelding te zien. Op die manier hebben ze twee en een halve minuut om 15 afbeeldingen te labelen.

Beide partners hebben de mogelijkheid om te passen. Dat wil zeggen dat ze opgeven om een bepaalde afbeelding te labelen. Zodra een partner opgeeft, krijgt de andere partner een bericht te zien dat zijn partner wil passen. Beide partners moeten passen voordat een nieuwe afbeelding getoond wordt.

Sommige afbeeldingen hebben ook taboewoorden die niet als label mogen ingevoerd worden. Deze woorden zijn meestal gerelateerd aan de afbeelding en maken het spel moeilijker omdat ze vaak gebruikt worden om de afbeelding te labelen. Taboewoorden worden uit het spel zelf verkregen. De eerste keer dat een afbeelding in het spel gebruikt wordt, heeft die nog geen taboewoorden. Als de afbeelding ooit opnieuw gebruikt wordt dan heeft die één taboewoord: het gemeenschappelijke woord dat bij het vorige spelletje ingevoerd werd. De volgende keer dat de afbeelding gebruikt wordt, heeft die twee taboewoorden, enzoverder. Taboewoorden worden automatisch door het systeem verzameld: als een afbeelding voldoende met hetzelfde woord gelabeld werd, dan wordt dat woord een taboewoord zodat de afbeelding een grotere verscheidenheid aan labels toegekend krijgt.

Af en toe wordt het spel solo gespeeld — zonder menselijke partner — waarbij de ESP game zelf als tegenstander optreedt en een reeks vooraf bepaalde labels aanlevert aan de menselijke speler. Deze labels werden uiteraard verzameld bij eerdere spelletjes die door echte mensen gespeeld werden. Deze functionaliteit is bijvoorbeeld nodig als er een oneven aantal mensen aangemeld zijn om het spel te spelen.

Eind 2008 werd het spel omgedoopt naar GWAP (game with a purpose), met een nieuwe gebruikersinterface. Enkele andere spelletjes die door Luis von Ahn ontwikkeld werden — zoals Peekaboom³ en Phetch⁴ — werden op dat moment ook geïntegreerd.

Opgave

Op basis van voorgaande spelletjes heeft de ESP game al een reeks taboewoorden verzameld die met een foto kunnen geassocieerd worden. Jouw opdracht bestaat erin om daaruit een willekeurig aantal woorden te selecteren die aan een nieuw paar spelers zal getoond worden. Hiervoor ga je als volgt te werk:

• Schrijf een functie taboelengte waaraan een reeks (list of tuple) met $$n \in \mathbb{N}$$ taboewoorden (str) moet doorgegeven worden. De functie heeft ook nog twee optionele parameters minimum en maximum waaraan respectievelijk gehele getallen $$a$$ en $$b$$ (int) kunnen doorgegeven worden. De functie moet een willekeurig getal $$s \in [a, b]$$ (int) teruggeven. Als er niet expliciet een waarde wordt doorgegeven aan de parameter minimum of als $$a$$ buiten het interval $$[0, n]$$ ligt, dan krijgt $$a$$ standaard de waarde 0. Als er niet expliciet een waarde wordt doorgegeven aan de parameter maximum of als $$b$$ buiten het interval $$[a, n]$$ ligt, dan krijgt $$b$$ standaard de waarde $$n$$.

• Schrijf een functie taboewoorden waaraan een reeks (list of tuple) met $$n \in \mathbb{N}$$ taboewoorden (str) moet doorgegeven worden. De functie heeft ook nog twee optionele parameters minimum en maximum waaraan respectievelijk gehele getallen $$a$$ en $$b$$ (int) kunnen doorgegeven worden. De functie moet een lijst (list) met een willekeurige selectie van $$s \in [a, b]$$ (int) verschillende woorden (str) teruggeven uit de gegeven reeks met taboewoorden. Daarbij moeten de woorden in alfabetische volgorde opgelijst worden, waar bij het sorteren geen onderscheid gemaakt wordt tussen hoofdletters en kleine letters. Als er niet expliciet een waarde wordt doorgegeven aan de parameter minimum of als $$a$$ buiten het interval $$[0, n]$$ ligt, dan krijgt $$a$$ standaard de waarde 0. Als er niet expliciet een waarde wordt doorgegeven aan de parameter maximum of als $$b$$ buiten het interval $$[a, n]$$ ligt, dan krijgt $$b$$ standaard de waarde $$n$$.

Voorbeeld

>>> woorden = ['forest', 'meadow', 'scenery', 'hills']
>>> taboelengte(woorden)
3
>>> taboelengte(woorden, minimum=2)
4
>>> taboelengte(woorden, maximum=3)
1
>>> taboelengte(woorden, minimum=2, maximum=3)
3
>>> taboelengte(woorden, minimum=-2, maximum=6)
1

>>> taboewoorden(woorden)
['forest', 'hills', 'meadow', 'scenery']
>>> taboewoorden(woorden, minimum=2)
['forest', 'meadow', 'scenery']
>>> taboewoorden(woorden, maximum=3)
['forest', 'hills', 'meadow']
>>> taboewoorden(woorden, minimum=2, maximum=3)
['hills', 'meadow', 'scenery']
>>> taboewoorden(woorden, minimum=-2, maximum=6)
['forest', 'hills', 'meadow', 'scenery']