Wie is het? is een spel voor twee spelers waarmee kinderen rudimentaire vaardigheden in logica aanleren. Elke speler heeft een identiek spelbord met portretten van 24 fictieve personages die neergeklapt kunnen worden. Elk personage heeft een unieke naam en meerdere kenmerken — er zijn mannen en vrouwen, sommigen hebben een baard, sommigen dragen een hoed, sommigen hebben een bril, enzovoort. Alle personages hebben een unieke combinatie van kenmerken.

Portretten van de 24 fictieve personages in het spelletje Wie is het?

Bij het begin van het spel trekt elke speler — buiten het zicht van de tegenspeler — een kaart met een portret dat overeenkomt met één van de personages op het spelbord. Dit is de identiteit die de speler tijdens het spel aanneemt.

Het doel van het spel is om de identiteit van de tegenspeler te ontmaskeren. De spelers doen dit door om de beurt een vraag te stellen over de identiteit van hun tegenspeler, waarop de tegenspeler enkel met ja of neen mag antwoorden. Op basis van het antwoord kan een speler alle personages elimineren die niet aan de kenmerken voldoen, tot er slechts één personage overblijft. Zo kan speler 1 bijvoorbeeld op basis van de volgende conversatie

speler 1: "Heb je blond haar?"

speler 2: "Ja"

alle personages op zijn/haar spelbord zonder blond haar neerklappen, zodat enkel de personages met blond haar overblijven. Daarna kan speler 2 bijvoorbeeld op basis van de volgende conversatie

speler 2: "Draag je een bril?"

speler 1: "Neen"

alle personages met bril neerklappen. Bij elke beurt kan een speler slechts één vraag stellen aan de tegenstander. Het is dus slim om in één keer zoveel mogelijk personages te proberen elimineren op het spelbord.

Een gebruikelijke (maar in dit geval niet de optimale) strategie is binair zoeken¹, waarbij elke vraag het aantal overblijvende personages halveert. Op basis van deze strategie hou je na één vraag nog twaalf personages over, na twee vragen zes, na drie vragen drie en na vier vragen nog één of twee. Na vijf beurten kan je met zekerheid een antwoord geven op de vraag: "Wie is het?" en heb je de tegenspeler ontmaskerd.

Met individuele kenmerken is het echter niet altijd mogelijk om een vraag te stellen die het aantal overblijvende personages halveert. Dit kan wel door gebruik te maken van propositielogica² en meerdere kenmerken te combineren. Zo kan speler 1 bijvoorbeeld op basis van de volgende conversatie

speler 1: "Heb je een baard én geen bril?"

speler 2: "Ja"

alle personages op zijn/haar spelbord neerklappen die een bril dragen of geen baard hebben (of allebei). Was het antwoord "Neen" geweest, dan zou hij/zij alle personages moeten wegklappen die wel een baard hebben maar juist geen bril dragen.

Opgave

Namen en kenmerken van personages worden voorgesteld als strings (String).

Een beschrijving van personages wordt voorgesteld als een object (Object) waarvan de sleutels kenmerken zijn, die afgebeeld worden op een Booleaanse waarde (Boolean). Een kenmerk dat afgebeeld wordt op de waarde true geeft aan dat het personage dat kenmerk moet hebben. Een kenmerk dat afgebeeld wordt op de waarde false geeft aan dat het personage dat kenmerk niet mag hebben. Zo beschrijft {"bril": true} personages met bril en beschrijft {"baard": true; "bril": false} personage met baard maar zonder bril. Een object zonder sleutels beschrijft per definitie alle personages.

Personage

Definieer een klasse Personage waarmee personages uit het spel Wie is het? kunnen voorgesteld worden. Bij het aanmaken van een personage moeten twee of meer strings (String) doorgegeven worden. Het eerste argument stelt de naam van het personage voor. De overige argumenten stellen de kenmerken van het personage voor. Als er minder dan twee argumenten doorgegeven worden, dan moet een Error opgeworpen worden met de boodschap geen kenmerken.

Een personage $p$ (Personage) moet minstens de volgende methoden hebben:

Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een expressie (String) teruggeven die een nieuw personage (Personage) aanmaakt met dezelfde naam en kenmerken als personage $p$ . In de expressie moeten de kenmerken in dezelfde volgorde opgelijst worden als bij het aanmaken van personage $p$ .
Een methode kenmerken waaraan geen argumenten moeten doorgegeven worden. De methode moet een opgemaakte string (String) teruggeven met de naam en een oplijsting van de kenmerken van personage $p$ . De kenmerken moeten in dezelfde volgorde opgelijst worden als bij het aanmaken van personage $p$ . Ze worden telkens van elkaar gescheiden voor een komma (,) en een spatie, behalve de laatste twee kenmerken die van elkaar gescheiden worden door een spatie, het woord en, en nog een spatie. De rest van de opmaak kan je afleiden uit onderstaand voorbeeld.
Een methode voldoet waaraan een beschrijving van personages moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of personage $p$ aan de gegeven beschrijving voldoet.

Product

Definieer een functie product waaraan twee argumenten moeten doorgegeven worden: een array $A$ (Array) en een getal $n \in N$ . De functie moet het $n$ -aire Carthesisch product $A^{n}$ teruggeven dat gedefinieerd wordt als $A^{n} = \underset{n}{\underset{⏟}{A \times A \times \dots \times A}} = {(a_{1}, \dots, a_{n}) | a_{i} \in A voor elke i \in {1, \dots, n}}$ Zowel de verzameling als de $n$ -tuples uit deze definitie worden voorgesteld door arrays (Array), waarbij geldt dat je vrij mag bepalen in welke volgorde de elementen van de verzameling in de array opgelijst worden.

Tip

Het Carthesisch product $A^{0}$ is per definitie gelijk aan ${()}$ . Voor $n > 0$ kan het Carthesisch product dan ook recursief gedefinieerd worden als $A^{n} = A^{n - 1} \times A = {(\bar{a}, a) | \bar{a} \in A^{n - 1}, a \in A}$ Daarbij gaan we ervan uit dat geneste tuples afgevlakt worden: $((1, 2), 3) \equiv (1, 2, 3)$ .

Opmerking

De functie product heb je enkel nodig bij de implementatie van de (laatste) methode besteBeschrijving van de klasse Spelbord (zie verder).

Als je een array van kenmerken hebt ( $[k 1, k 2, \dots, k_{n}]$ ) dan kan je alle mogelijke beschrijvingen van personages met die kenmerken genereren op basis van het $n$ -aire Carthesisch product van de array [null, true, false]. In een $n$ -tuple van dit Carthesisch product geeft de waarde null op de $i$ -de positie aan dat het kenmerk $k_{i}$ niet gebruikt wordt in de beschrijving, de waarde true dat het kenmerk $k_{i}$ afgebeeld wordt op true in de beschrijving, en de waarde false dat het kenmerk $k_{i}$ afgebeeld wordt op false in de beschrijving.

Spelbord

Definieer een klasse Spelbord waarmee spelborden kunnen voorgesteld worden die een speler kan gebruiken om Wie is het? te spelen. Dat betekent onder andere dat de speler tijdens de loop van het spel personages moet kunnen neerklappen volgens de identiteit van de tegenstander. Bij het aanmaken van een spelbord (Spelbord) moet de naam van de tegenspeler (zijnde van diens identiteit) doorgegeven worden, samen met de personages (Personage; als afzonderlijke argumenten) die bij het begin van het spel op het spelbord staan. Als de identiteit van de tegenspeler (eerste argument) niet overeenkomt met de naam van één van de personages op het spelbord, dan moet een Error opgeworpen worden met de boodschap onbekende identiteit.

Een spelbord $s$ (Spelbord) moet minstens de volgende methoden hebben:

Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een expressie (String) teruggeven die een nieuw spelbord (Spelbord) aanmaakt met dezelfde naam (identiteit tegenspeler) en de personages op spelbord $s$ die nog niet neergeklapt zijn. In de expressie moeten de personages in dezelfde volgorde opgelijst worden als bij het aanmaken van spelbord $s$ .
Een methode kenmerken waaraan geen argumenten moeten doorgegeven worden. De methode moet een array (Array) teruggeven met de kenmerken van alle personages die nog niet neergeklapt zijn op spelbord $s$ . De kenmerken moeten in alfabetische volgorde opgelijst worden. Kenmerken die bij meerdere personages voorkomen, worden slechts één keer opgelijst.
Een methode vraag waaraan een beschrijving van personages moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of de identiteit van de tegenspeler aan de gegeven beschrijving voldoet. Het resultaat van deze functie correspondeert dus met het antwoord dat de speler krijgt als hij met de gegeven beschrijving een vraag stelt aan de tegenstander.
Een methode neerklappen waaraan een beschrijving van personages moet doorgegeven worden. De methode moet alle personages neerklappen die nog rechtop staan op spelbord $s$ en die niet voldoen aan het antwoord dat de speler krijgt als hij met de gegeven beschrijving een vraag stelt aan de tegenstander. De methode moet een verwijzing teruggeven naar spelbord $s$ .
Een methode isOntmaskerd waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven, die aangeeft of er nog maar één personage rechtop staat op spelbord $s$ .
Een methode potentieel waaraan een beschrijving van personages moet doorgegeven worden. De methode moet teruggeven hoeveel van de personages die nog rechtop staan op spelbord $s$ voldoen aan de gegeven beschrijving. We noemen dit het potentieel van de gegeven beschrijving.
Een methode besteBeschrijving waaraan een array (Array) van kenmerken moet doorgegeven worden. Van alle mogelijke beschrijvingen die je met de gegeven kenmerken kan maken (zie functie product), moet de methode die beschrijving teruggeven waarvan het potentieel het dichtst ligt bij het helft van het aantal personages die nog rechtop staan op spelbord $s$ . Als er meerdere beschrijvingen zijn waarvan het potentieel het dichtst bij de helft van het aantal personages op spelbord $s$ ligt, dan maakt het niet uit welke van deze beschrijvingen de functie teruggeeft.

Voorbeeld

        > const anne = new Personage("Anne", "vrouw", "oorringen", "krulhaar");
> anne.toString()
'new Personage("Anne", "vrouw", "oorringen", "krulhaar")'
> anne.kenmerken()
"Anne heeft als kenmerken: vrouw, oorringen en krulhaar"
> anne.voldoet({})
true
> anne.voldoet({"vrouw": true})
true
> anne.voldoet({"vrouw": false})
false
> anne.voldoet({"man": true})
false
> anne.voldoet({"vrouw": true, "baard": false})
true
> anne.voldoet({"krulhaar": true, "vrouw": true, "oorringen": true})
true

> const bernard = new Personage("Bernard", "man");
> bernard.toString()
'new Personage("Bernard", "man")'
> bernard.kenmerken()
"Bernard heeft als kenmerken: man"
> bernard.voldoet({"man": true})
true
> bernard.voldoet({"vrouw": false, "hoed": false, "oorringen": false, "baard": false})
true

> product(["Anne", "Bernard", "Claire", "David"], 1)
[["Anne"], ["Bernard"], ["Claire"], ["David"]]
> product([1, 2, 3], 2)
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
> product([true, false], 3)
[[true, true, true], [true, true, false], [true, false, true], [true, false, false], [false, true, true], [false, true, false], [false, false, true], [false, false, false]]

> const claire = new Personage("Claire", "vrouw", "hoed");
> const david = new Personage("David", "man", "baard");
> const spelbord = new Spelbord("Claire", anne, bernard, claire, david);
> spelbord.toString()
'new Spelbord("Claire", new Personage("Anne", "vrouw", "oorringen", "krulhaar"), new Personage("Bernard", "man"), new Personage("Claire", "vrouw", "hoed"), new Personage("David", "man", "baard"))'
> spelbord.kenmerken()
["baard", "hoed", "krulhaar", "man", "oorringen", "vrouw"]
> spelbord.isOntmaskerd()
false
> spelbord.potentieel({"man": true})
2
> spelbord.potentieel({"baard": false, "oorringen": false})
2
> spelbord.besteBeschrijving(["man", "oorringen"])
{"man": true}
> spelbord.besteBeschrijving(["baard", "oorringen"])
{"baard": false, "oorringen": false}
> spelbord.vraag({"man": true})
false
> spelbord.vraag({"baard": false, "oorringen": false})
true
> spelbord.neerklappen({"man": true}).toString()
'new Spelbord("Claire", new Personage("Anne", "vrouw", "oorringen", "krulhaar"), new Personage("Claire", "vrouw", "hoed"))'
> spelbord.isOntmaskerd()
false
> spelbord.kenmerken()
["hoed", "krulhaar", "oorringen", "vrouw"]
> spelbord.potentieel({"oorringen": true})
1
> spelbord.besteBeschrijving(["hoed", "krulhaar", "oorringen", "vrouw"])
{"oorringen": true}
> spelbord.vraag({"oorringen": true})
false
> spelbord.neerklappen({"oorringen": true}).toString()
'new Spelbord("Claire", new Personage("Claire", "vrouw", "hoed"))'
> spelbord.isOntmaskerd()
true

Bronnen

Nica M (2016). Optimal strategy in "guess who?": Beyond binary search. Probability in the Engineering and Informational Sciences 30(4), 576–592. ³
O'Neill B (2021). Optimal guessing in "Guess Who". PLOS ONE, 16(3), e0247361. ⁴