Een nieuw wiskundig model, dat de beste strategie oplevert om het populaire bordspel CLUEDO te winnen, zal wellicht ooit robots kunnen helpen door onbekende omgevingen naar verborgen explosieven te navigeren.

Volgens de onderzoekers van Duke University, vertonen spelers van CLUEDO en genoemde robots veel overeenkomsten. Zowel een CLUEDO speler als een mijnrobot moet in onbekende ruimten op zoek naar aanwijzingen (clues, vandaar: cluedo).

Bij CLUEDO bewegen spelers een pion over een bord en gaan ‘kamers’ binnen op zoek naar informatie over de moordenaar en het moordwapen, voordat ze naar de volgende kamer gaan om meer informatie te verzamelen.
“Op dezelfde manier moeten sensoren – zoals de pionnen in CLUEDO – informatie waarnemen uit hun omgeving om de robots te helpen langs obstakels te manoeuvreren”, zegt Chenghui Cai, die samenwerkt met Silvia Ferrari, assistent professor mechanical engineering and materials science aan de Duke’s Pratt School of Engineering.

Schatzoek-probleem

“De sleutel tot succes, voor zowel de CLUEDO speler als de robots, is niet alleen de nieuwe informatie die ze ontdekken op te nemen, maar ook te gebruiken voor de volgende zetten”, vervolgt Cai. “Dit lerend gedrag duurt voort totdat de speler heeft gewonnen of de robot de mijnen heeft gevonden.”
Onderzoekers op het gebied van kunstmatige intelligentie noemen dit soort situaties “schatzoek”-problemen en hebben uiteenlopende wiskundige benaderingen om de jacht naar de schat te verbeteren. Games worden vaak gebruikt om de modellen te testen of dit soort complexe problemen te illustreren.

“Wij vinden dat we onze nieuwe wiskundige modellen het beste met het bordspel CLUEDO kunnen duidelijk maken. We ontdekten dat spelers met strategieën gebaseerd op onze algoritmen consequent beter presteren dan menselijke spelers en andere computerprogramma’s.”

Ferrari, die ook leiding geeft aan Duke’s Laboratory for Intelligent Systems and Controls, is gespecialiseerd in de ontwikkeling van systemen die proberen de menselijke denkprocessen na te bootsen voor toepassing in mechanische systemen die snel moeten kunnen reageren op sterk wisselende omstandigheden. Denk daarbij niet alleen aan mijnenvegende robots, maar ook aan beveiliging, straaljager vluchtleiding en zelfs profiling van criminelen.

Ontdekt aan de keukentafel

Het CLUEDO-verband schoot Ferrari letterlijk te binnen tijdens een familiespelletje.
“Op een avond speelden we CLUEDO aan de keukentafel en het overviel me”, zegt Ferrari. “In het spel CLUEDO kun je niet alle kamers aan het einde van het spel bezoeken, dus moet je een manier bedenken om het aantal zetten te beperken, terwijl je het bereiken van je doel maximaliseert. Als je naar mijnen zoekt, wil je dat je robot zo weinig mogelijk tijd verspilt en maximale informatie oplevert.”

Aan de hand hiervan hebben Ferrari en Cai de afgelopen drie jaar gewerkt aan een wiskundig model om de keuzes en informatievergaring die bij deze activiteiten plaatsvinden in beeld te brengen. Na de ontwikkeling van het nieuwe algoritme heeft het onderzoeksteam dit getest bij zowel ervaren CLUEDO spelers als bij spelers die algoritmen van andere spellen toepassen.

Daaruit kwam bijvoorbeeld naar voren dat spelers met het nieuwe algoritme tegenover spelers met een kunstmatige intelligentie-strategie die bekend staat als constraint satisfaction, maar liefst 70% tijdwinst boekten. Tegenover spelers met een andere kunstmatige intelligentie-strategie, die gebruikmaakt van een zogenaamd Bayesian netwerk, leidde het nieuwe algoritme tot een winstpercentage van 68%. Bij weer een ander type neuraal netwerk steeg het winstpercentage naar 72%.

“Uit deze resultaten concluderen we dat het succes van de spelers met het nieuwe algoritme komt door de strategie van juiste richtingkeuze en optimalisatie van de mogelijkheid om nieuwe infomatie te verwerken en tegelijkertijd de reisafstand van de pion te minimaliseren”, zegt Ferrari. “Op deze manier kon het algoritme het spel zo snel als mogelijk winnen.”

Bron: Duke University