Je leest:

Killing Cluedo

Killing Cluedo

Auteur: | 10 april 2004

In Cluedo proberen de spelers als eerste een moord op te lossen, door vragen en antwoorden over elkaars kaarten, en doordenken. Het spelverloop is geheel te beschrijven met kennislogica. Hoe je Cluedo kunt winnen, blijft echter onduidelijk. Gelukkig hebben we een goed advies voor ijverige detectives.

Een stijlvol diner in een fraai Brabants kasteel. De gastheer dr Swart is vermoord. Wie heeft het gedaan? Dit is Cluedo. Het doel van het spel is om de moord op te lossen, en oplossen betekent: ontdekken wie van de zes gasten de moord gepleegd heeft, met welk van de zes mogelijke wapens, en in welke van de negen ruimten van het kasteel. Cluedo wordt gespeeld met een bord waarop dit huis is afgebeeld. Het bord bepaalt over welke kamer een speler een vraag mag stellen.

De gasten, wapens en kamers worden vertegenwoordigd door speelkaarten. Van ieder type kaart wordt er aan het begin van het spel, na schudden, één apart gelegd, ondersteboven op tafel. Deze kaarten staan voor de moordenaar, het moordwapen en de moordkamer. De overige achttien van de in totaal 21 kaarten worden opnieuw geschud en onder de zes spelers verdeeld. De kaarten die jij hebt, vertellen je dus iets over de moord: omdat ze niet op tafel liggen, zijn het niet de moordkaarten. Dit is de informatie waarmee je begint.

Een zet in het spel begint met een vraag over drie kaarten van de verschillende typen, net alsof hiermee een verdenking geuit wordt, bijvoorbeeld ‘Ik denk dat dominee Groenewoud het heeft gedaan met de kandelaar in de balzaal’. Als de speler aan wie de vraag wordt gesteld geen van deze drie kaarten heeft, beantwoordt deze de vraag met ‘nee’. Zolang het antwoord ‘nee’ is stel je de vraag aan de volgende speler. De eerste speler die wel (ten minste) een van de drie kaarten heeft, toont (naar keuze) een van deze aan de vrager. De andere spelers zien dan alleen dat een kaart getoond wordt, maar niet welke het is. Je beurt is voorbij als een speler je een kaart laat zien. Door de kennis die je zo verzamelt over de kaarten van anderen kun je er dus geleidelijk achter komen welke kaarten op tafel liggen. Je verzamelt hiermee als het ware aanwijzingen voor het oplossen van de moord. In het Engels zijn dat clues, vandaar de naam van het spel.

Kandelaar geen moordwapen

Een zet in het spel.

Laten we eerst eens kijken naar zo’n zet in het spel (zie afbeelding). In de zet vraagt speler 1 naar ‘Groenewoud, Kandelaar, Balzaal’, heeft speler 2 geen van die kaarten en zegt dus ‘nee’, en antwoordt speler 3 door de kandelaar-kaart (alleen) aan speler 1 te laten zien. Tevens nemen we aan dat speler 4 de kaarten Groenewoud en Balzaal heeft.

Hoe is de kennis van de spelers veranderd als gevolg van deze zet? Speler 1 weet nu de kaart van speler 3. Speler 1 kan de kandelaar dus elimineren als moordwapen: omdat speler 3 de kandelaar heeft, kan dit immers niet de kaart zijn die op tafel ligt. Speler 3 weet dat speler 1 dit van hem weet, speler 1 weet dat speler 3 dit weer weet, enzovoort. In dit geval kunnen we tot in het oneindige doorgaan met het stapelen van kennis.

Dit stapelen gaat ook wel eens mis: speler 4 heeft de andere twee van de drie gevraagde kaarten. Daarom weet speler 4 dat speler 3 de kandelaar getoond moet hebben. Echter, speler 3 weet niet (als dit de eerste zet van het spel is) dat speler 4 dit van hem weet.

Door dit soort complicaties was tot voor kort onduidelijk wat de precieze informatiestroom is bij zetten als in dit spel, maar inmiddels weten we hierop het antwoord. Deze precisie is van belang, want uit kennis over elkaar kunnen spelers uiteindelijk soms weer kennis over kaarten afleiden, en dus sneller winnen. Het volgende voorbeeld maakt dit duidelijk:

Tijdens je beurt mag je ook nog een ‘definitieve beschuldiging’ uiten, omdat je weet (of denkt te weten) hoe de moord gepleegd is. Een van de eigenaardigheden van Cluedo is, dat je er soms informatie aan kunt ontlenen dat een speler die beschuldiging niet uit, dat wil zeggen: zijn zet eenvoudigweg beëindigt.

Stel dat speler 1 het spel begint en naar drie kaarten vraagt, en alle andere spelers zeggen ‘nee’ (‘ik heb geen van de drie gevraagde kaarten’). Speler 1 laat nu de beurt aan speler 2. Eigenlijk ‘zegt’ speler 1 dan, dat hij niet weet wat de moordkaarten zijn. De overige spelers kunnen hieruit afleiden dat speler 1 dus een van de drie gevraagde kaarten zelf moet hebben. Met andere woorden: uit je kennis over de onwetendheid van een speler, kun je soms kennis over de kaarten zelf afleiden.

Kennislogica

Cluedo bevat 21 kaarten en is alleen al daarom nogal ingewikkeld te analyseren. Ter vereenvoudiging beschouwen we daarom drie spelers (1, 2 en 3) en drie kaarten (zwart, geel en rood (de kleuren van de Belgische vlag dus). Iedere speler houdt één kaart vast. Spelers kunnen alleen hun eigen kaart zien. We nemen aan dat speler 1 zwart heeft, speler 2 geel en speler 3 rood. Ze weten dat iedereen een kaart heeft en welke kaarten er in het spel zijn, maar ze kunnen alleen hun eigen kaart zien. Het doel van het spel is om met vragen en antwoorden erachter te komen wat de kaartverdeling is.

De logica biedt een exacte en beknopte manier om de kennistoestanden van het spel, zowel als de veranderingen daarin, bij te houden. De formele taal om dit spel te beschrijven is de taal van de kennislogica. We geven alleen wat voorbeelden van hoe je beweringen in dit spel beknopt en exact kunt noteren. De bewering z1 staat voor ‘speler 1 heeft zwart’, en K1 z1 staat voor ‘speler 1 weet dat hij zwart heeft’. De operator K1 heet de modale kennisoperator en staat voor ‘speler 1 weet dat’. Bewering K1 z1 /\ ØK2 z1 staat voor ‘speler 1 weet dat hij zwart heeft en speler 2 weet niet dat speler 1 zwart heeft’. Het symbool /\ staat voor ‘en’ en het symbool Ø staat voor ‘niet’. Bewering ØK2 Øz1 staat voor ‘speler 2 weet niet dat speler 1 niet zwart heeft. Dit is hetzelfde als ’speler 2 kan zich voorstellen dat speler 1 zwart heeft’.

Speltoestand

Kennisverdeling. De kennis van de spelers in de beginsituatie van het spel. Bijvoorbeeld Zwart/Geel /Rood staat voor de kaartverdeling waar speler 1 zwart heeft, speler 2 geel, en speler 3 rood. Deze kaartverdeling kan speler 1 niet onderscheiden van de kaartverdeling Zwart/Rood/Geel waarbij speler 1 nog steeds zwart heeft, maar waarbij speler 2 rood heeft en speler 3 geel. Dit wordt in de afbeelding weergegeven door een verbinding van Zwart/Geel /Rood naar Zwart/Rood/Geel gelabeld met een 1. De kaartverdeling Zwart/Geel /Rood staat in een kader, om aan te geven dat dit de werkelijke kaartverdeling is.

Dit soort beweringen kunnen we nu gaan interpreteren, ofwel uitrekenen of er waar of onwaar uitkomt. We gaan uit van een model zoals in de afbeelding. De combinatie van mogelijke verdelingen noemen we de toestand of speltoestand (Hexa, Zwart/Geel/Rood ). Hexa is Grieks voor zes, en verwijst naar de zes mogelijke speltoestanden in dit geval.

De afbeelding geeft de kennis van de spelers weer in de beginsituatie van het spel. Bijvoorbeeld Zwart/Geel/Rood staat voor de kaartverdeling waar speler 1 zwart heeft, speler 2 geel, en speler 3 rood. Deze kaartverdeling kan speler 1 niet onderscheiden van de kaartverdeling Zwart/Rood/Geel waarbij speler 1 nog steeds zwart heeft, maar waarbij speler 2 rood heeft en speler 3 geel. Dit wordt in de afbeelding weergegeven door een verbinding van Zwart/Geel/Rood naar Zwart/Rood/Geel gelabeld met een 1. In plaats van ‘speler 1 kan Zwart/Geel/Rood niet onderscheiden van Zwart/Rood/Geel’ kunnen we ook zeggen ‘Zwart/Geel/Rood is voor speler 1 hetzelfde als Zwart/Rood/Geel’, of ’Zwart/Geel/Rood is voor speler 1 equivalent met Zwart/Rood/Geel ’. Er zijn zes verschillende verdelingen van drie kaarten over drie spelers. Deze verzameling van zes kaartverdelingen kunnen we zo opdelen in drie groepjes van twee, de zogenaamde equivalentieklassen voor speler 1. Als we ook voor de andere spelers weergeven welke kaartverdelingen ze niet van elkaar kunnen onderscheiden is de afbeelding bijna compleet. Bovendien staat in de afbeelding de kaartverdeling Zwart/Geel/Rood in een kader. Dit is om aan te geven dat Zwart/Geel/Rood de werkelijke kaartverdeling is.

We zeggen ook wel dat Hexa een Kripke-model is, en de zes kaartverdelingen de werelden van het model. De logicus Saul Kripke bedacht deze manier van interpreteren van logica, die veel algemener toepasbaar is dan alleen voor kennislogica.

Werelden

We kunnen beweringen in onze logische taal nu interpreteren in de toestand ( Hexa, Zwart/Geel/Rood) dat wil zeggen: in de wereld Zwart/Geel/Rood van het model Hexa. We geven opnieuw alleen wat voorbeelden. Om te beginnen is bewering z1 waar in de toestand Zwart/Geel/Rood (speler 1 heeft inderdaad zwart) en z3 onwaar in de toestand Zwart/Geel/Rood (speler 3 heeft immers rood in deze toestand). Verder is K1z1 waar in Zwart/Geel/Rood, want in alle kaartverdelingen die voor speler 1 hetzelfde zijn als Zwart/Geel/Rood, namelijk Zwart/Geel/Rood zelf en Zwart/Rood/Geel, geldt z1.

Ook weet speler 1 dat speler 2 weet dat hij zelf (2) niet zwart heeft. In onze logische taal noteren we dat als: K1K2Øz2. Dit is waar omdat in alle werelden die hetzelfde zijn voor speler 1 (Zwart/Geel/Rood en Zwart/Rood/Geel) in de werelden die – vanuit die werelden – hetzelfde zijn voor speler 2 [(Zwart/Geel/Rood en Rood/Geel/Zwart) respectievelijk (Zwart/Rood/Geel en Geel/Rood/ Zwart)] het niet zo is dat speler 2 zwart heeft.

De geldigheid van deze bewering hangt dus af van vier kaartverdelingen! Zo zijn er nog legio andere voorbeelden. Ook wordt ‘kennis’ geacht een paar algemene eigenschappen te hebben, die inderdaad ook in de speltoestand Hexa gelden, zoals bijvoorbeeld Als je iets weet, dan is het waar: Kp > p, voor willekeurige K en p (hier staat > voor ‘als …, dan’).

Om uit te drukken dat speler 1 en 3 tot in het oneindige van elkaar weten dat 3 de kandelaar-kaart heeft, kunnen we ook nog zogenaamde gemeenschappelijke kennis-operatoren invoeren. Kennislogica met meerdere kennisoperatoren, zoals K1 en K2, en tevens met zogenaamde gemeenschappelijke-kennis-operatoren, is goed bruikbaar voor het precies beschrijven van zogenaamde multi-actorsystemen, systemen met meerdere actoren. Hieronder valt het beschrijven van gedistribueerde computersystemen, van communicatie in telefoonnetwerken, en van informatieoverdracht met veiligheidsaspecten, zoals bij smartcards.

Kennisverandering

Kennisverandering. Het resultaat van de acties zwart-op-tafel, toon-zwart en fluister-niet-rood in de toestand ( Hexa, Zwart/Geel /Rood ) waarin speler 1 zwart, speler 2 geel en speler 3 rood vasthoudt. Ook werelden die door een pad van 3-verbindingen gelabeld zijn, zijn hetzelfde voor 3 (speler 3 kan dus drie groepen van elk vier werelden van elkaar onderscheiden).

In de begintoestand ( Hexa, Zwart/Geel/Rood) weet speler 2 niet welke kaart 1 heeft. Speler 2 houdt zowel voor mogelijk dat 1 zwart heeft als dat 1 rood heeft. Hij heeft vele manieren waarop hij erachter kan komen welke kaart speler 1 heeft:

(a) Speler 1 legt de zwarte kaart op tafel. Deze actie noemen we zwart-op-tafel.

(b) Speler 1 laat alleen speler 2 zijn zwarte kaart zien. Speler 3 ziet niet welke kaart het is, maar wel dat een kaart getoond wordt. Deze actie noemen we toon-zwart.

© Speler 2 vraagt speler 1: “Vertel me een kaart die je niet hebt”. Speler 1 fluistert in het oor van speler 2: “Ik heb rood niet”. Speler 3 hoort het antwoord niet, maar ziet wel dat het gegeven wordt. Dit noemen we fluister-niet-rood.

In alledrie de gevallen veronderstellen we tevens dat het publieke deel van de actie gemeenschappelijk bekend is, bijvoorbeeld, bij zwart-op-tafel, dat 2 en 3 zien dat 1 die kaart op tafel legt, en 1, 2 en 3 dat van elkaar weten, enzovoort. In de afbeelding zien we het resultaat van deze drie acties in de gegeven speltoestand. Na het uitvoeren van zwart-op-tafel zijn de kaartverdelingen verwijderd waarin 1 zwart niet heeft. In deze toestand weten zowel speler 2 als speler 3 wat de kaartverdeling is, omdat er vanuit de omkaderde wereld Zwart/Geel/Rood (de werkelijke speltoestand) geen alternatieven voor 2 en voor 3 zijn. Ook met redeneren hadden we hier achter kunnen komen: 2 heeft zelf geel, 2 heeft geleerd dat 1 zwart heeft, en omdat er maar drie kaarten zijn kan 2 afleiden dat 3 rood heeft. Speler 2 weet dus, net als speler 3, wat de kaartverdeling is. Alleen speler 1 weet het nog steeds niet! Ook na het uitvoeren van toon-zwart weet 2 dat 1 zwart heeft (en dus wat de kaartverdeling is), maar nu weet 3 het niet. Spelers 3 en 1 zijn toch wel wat wijzer geworden: beiden weten nu dat 2 de kaartverdeling kent!

Fluister-niet-rood

Zelfs na het uitvoeren van fluister-niet-rood weet 2 dat 1 zwart heeft: wederom is er vanuit de omkaderde wereld Zwart/Geel/Rood (de werkelijke toestand) geen alternatief voor 2. Er is echter ook nog een met stippellijnen omkaderde wereld Zwart/Geel/Rood. Deze geeft de toestand weer als 1 in plaats van ‘Ik heb niet rood’ had gefluisterd ‘Ik heb niet geel’. Dat wist 2 immers al, dus dat was voor hem niet informatief geweest! Anders dan na toon-zwart, weet speler 3 na fluister-niet-rood niet of speler 2 weet welke kaart speler 1 heeft.

Op een vergelijkbare manier kunnen we het resultaat zichtbaar maken van acties zoals ‘Ik heb de gele kaart niet’ en ‘Ik kan niet winnen’ (dat wil zeggen: ik weet niet wat de kaartverdeling is). Uiteraard zoeken we een systematische methode om volgende speltoestanden te kunnen berekenen. Dat is mogelijk omdat we dit soort acties zelf kunnen modelleren als een soort van Kripke-model van mogelijke werelden, maar nu met verzamelingen kaartverdelingen als werelden, in plaats van kaartverdelingen zonder meer.

Dit nieuwe inzicht heb ik uitgewerkt in mijn proefschrift (te vinden op mijn website). En net zoals we een logische taal voor beweringen over kennis kunnen interpreteren in modellen, kunnen we ook een logische taal voor dit soort acties definiëren. Ook dat gebeurt in mijn proefschrift. Aan een kennislogische taal kunnen we dan zogenaamde dynamische operatoren toevoegen voor acties. We kunnen dan uitdrukken dat in de begintoestand van het spel na het uitvoeren van de actie toon-zwart speler 2 weet dat speler 1 de zwarte kaart heeft: in ( Hexa, Zwart/Geel/Rood) geldt [toon-zwart]K2r1.

Terug naar Cluedo

In de actie toon-zwart laat speler 1 (alleen) aan speler 2 zijn zwarte kaart zien. We kunnen dit ook anders formuleren: 2 vraagt aan 1 zijn kaart, dat wil zeggen een van alle (drie) kaarten, en 1 ‘kiest’ ervoor om van de gevraagde kaarten (alleen) aan 2 de zwarte kaart te laten zien. Kaarttoonacties in Cluedo zijn net zulke combinaties van vragen en antwoorden: een speler vraagt aan een andere speler een van drie kaarten (dus niet een van alle 21) en de andere speler kiest een kaart om (alleen) aan de vrager te laten zien. In dit geval is het soms echt kiezen, namelijk als de kaarttoner meer dan een van de gevraagde kaarten in de hand houdt.

Behalve het tonen van een kaart zijn er in Cluedo dus nog drie andere typen acties: acties waarin een speler een vraag met ‘nee’ beantwoordt, die waarin een speler zijn zet beëindigt (en daarom publiek maakt dat hij niet kan winnen) en die waarin een speler wint. Het is wel gevaarlijk om de informatie te gebruiken dat een speler zijn zet beëindigt: ‘gewone’ mensen hadden soms kunnen winnen maar waren zich daarvan nog niet bewust. Als andere spelers dan ten onrechte aannemen dat die spelers niet konden winnen, leiden ze daaruit incorrecte informatie af, bijvoorbeeld dat ze – nog steeds ten onrechte dus – weten wat de moordkaarten zijn, dat publiek maken en dus zelf verliezen!

Meer acties zijn er niet. Hiermee kunnen we het spelverloop van Cluedo uitputtend beschrijven. Nu is dit nog niet voldoende: we willen niet alleen weten hoe het spel verliep, we willen ook weten wat de beste volgende vraag is die we kunnen stellen op een willekeurig spelmoment. Wat zijn goede strategieën, en waarom? Een antwoord op deze vraag is niet eenvoudig. Om te beginnen moet je kunnen bepalen met welke van alle mogelijke vragen je de meeste informatie verzamelt. Dit is een combinatorische vraagstelling.

Gokje

Combinatoriek is een deelgebied van de discrete wiskunde. Is het bij Cluedo beter om naar drie kaarten te vragen die je niet hebt en nog niet kent, of naar drie kaarten waarvan je er één of twee zelf hebt? Maar zelfs als we die vraag beantwoord hebben, zijn we nog niet klaar: een speler hoeft niet te wachten totdat hij de moordkaarten kent voordat hij een definitieve beschuldiging uit, maar mag ook een gokje wagen. Sterker nog, als je vermoedt dat de volgende speler over voldoende informatie beschikt – of gaat beschikken – om het spel te winnen, dan is het wel zo verstandig om die gok te wagen! Dit soort problemen wordt bestudeerd door de speltheorie, een deelgebied van de economie. Ook deze vraag is onbeantwoord, en notoir lastig voor dit soort spelen voor meer dan twee personen. Er is dus nog genoeg werk te doen. Wel duidelijk is dat de beschrijving met kennislogica onmisbaar is voordat je over strategieën kunt gaan nadenken.

Hoe win je Cluedo nu wel?

Boekhouden in Cluedo.

We zetten nu al het voorgaande even overboord. We moeten beseffen dat Cluedo gedeeltelijk een kansspel is: als ik in de eerste zet toevallig naar de drie moordkaarten vraag, heb ik meteen gewonnen.

Dus een winnende strategie zit er niet in. En, zoals hiervoor uitgelegd, zelfs een optimale, die je winstkansen maximaliseert, is nog ver van ons bed. Gelukkig kun je met uitsluitend goed boekhouden je tegenstanders al ver voorblijven! Het Cluedo-spel heeft daar een formuliertje voor, waarop je kunt afkruisen wie het niet is. Het kan echter veel effectiever:

In de afbeelding laten we twee speltoestanden zien van een spelletje Cluedo, vanuit het gezichtspunt van Frits. Het is een tabel van 21 rijen, voor de 21 kaarten, bij zeven kolommen, voor zes spelers en de tafel, waarop de moordkaarten liggen. Als je weet dat speler x kaart y heeft, zet je een 1 op die plaats, als je weet dat speler x kaart y niet heeft, een 0, en als je niet weet of speler x kaart y heeft, in eerste instantie niets.

Zoals we zien, heeft Frits de kaarten Groenewoud, De Wit en Dolk. Alle andere spelers en de tafel hebben die dus niet. De tabel geeft de situatie weer nadat Anna, de verdenking heeft geuit dat Groenewoud het heeft gedaan met een touw in de danszaal, en Bert, die de Danszaal-kaart heeft, die aan Anna heeft laten zien.

Uiteraard weet Frits niet dat Bert Danszaal heeft, maar hij weet wel dat Bert een van Danszaal, Touw en Groenewoud heeft. Dit verwerkt hij (en alle overige spelers ook) door in de kolom van Bert drie keer hetzelfde symbool, bijvoorbeeld een 2, te zetten, in de rijen voor die kaarten. Echter, in zijn geval is twee keer al voldoende: omdat hij zelf Groenewoud heeft, zodat daar al een 0 staat in Berts kolom. Frits heeft dus nu, per tabel, afgeleid dat Bert Touw of Danszaal moet hebben, terwijl Bert niet weet dat Frits dit van hem weet!

Bert aan zet

Zo gaan we verder. Bert is nu aan zet, en vraagt ‘De Wit, Revolver, Zitkamer’. Charlotte en Dirk hebben die kaarten niet, dus zeggen nee. Dit levert in principe zes nullen voor onze tabel, maar voor Frits twee minder, omdat hij zelf De Wit heeft. Eva laat nu Bert haar Zitkamer-kaart zien. Dit verwerken we door opnieuw (ten hoogste) drie keer een nieuw symbool, bijvoorbeeld 3, op de juiste plaats in de kolom van Eva te zetten. Enzovoort. Er zijn wat eenvoudige regels voor het verwerken van verschillende symbolen in dezelfde kolom, en het verwerken van verschillende symbolen in dezelfde rij. De informatie die volgt uit het beëindigen van je zet, door niet te winnen, wordt echter niet verwerkt in dit schema. Niettemin: probeer het maar eens, en gegarandeerd dat je van de andere spelers wint. Daarna wordt het moeilijker om te winnen: tot je verbazing gebruiken de volgende keer nu ook al je medespelers dit notatieschema, en je voordeel is weer verspeeld!

Literatuur

Dit artikel is een publicatie van Natuurwetenschap & Techniek.
© Natuurwetenschap & Techniek, alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 10 april 2004

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.