Undercut



Fiona Douma
Gerben Blom

Inleiding met spelregels en doel

Dit werkstuk is de afsluiting van het vak Multi Agent Systems. In dit vak wordt een basis wordt gelegd voor een beschrijvingswijze van verschillende soorten systemen waar verschillende agents kennis over elkaar hebben, kennis over elkaar proberen te verzamelen, of kennis zo efficient mogelijk proberen te verdelen.

Het spel Undercut is een eenvoudig spelletje wat door D.H. Hofstadter bedacht is tijdens een lange saaie autorit met een vriend van hem. Het idee achter het spel is om je tegenstander te verleiden tot het doen van bepaalde zetten, zodat je daar zelf gebruik van kunt maken.
De spelregels zijn als volgt. Beide spelers geven tegelijkertijd, onafhankelijk van elkaar een zet door. Deze zet bestaat uit het noemen van een geheel getal tussen de 1 en de 5. In eerste instantie krijg je het aantal punten wat je gezegt hebt bij je totaal bijgeschreven, maar om af te straffen dat iemand constant maar 5 blijft zeggen, krijgt diegene die bij twee achtereen volgende getallen (bv. 3 en 4) het laagste getal gezegd heeft de som van beide getallen op zijn conto bijgeschreven.
Het doel van het spel is zoveel mogelijk punten te verzamelen en dat gaat het beste door steeds eeb getal te noemen dat 1 onder die van je tegenstander zit. Door je tegenstander te verleiden een getal te noemen, kun je hem 'undercutten', dus op basis van een gevoel over wat hij gaat zeggen maak je je keuze.

Het doel van deze opdracht is om een implementatie te maken van dit spel om interactief op het internet te spelen. Het achterliggende computerbeslissysteem is gebaseerd op verschillende strategieprincipes.

Beschrijving

We hebben vijf verschillende strategieen onderscheiden om aan te houden tijdens het spel.

1. Compleet random

2. Gewichten berekenen op basis van payoff (zonder rekening te houden met beliefs)

3. Alleen 4 zeggen.

4. Zeg steeds wat de tegenstander de vorige beurt zei.

5. Een 'menselijke' strategie die zijn keuze baseerd op wat in zijn 'geheugen' zit.

Strategie 1:
De computer baseert zijn keuze compleet op de pseudo-random getallengenerator die in elke programeertaal aanwezig is. Bij elke nieuwe ronde wordt een nieuw getal tussen 1 en 5 gegenereerd. Een goede strategie tegen deze tegenstander is oom alleen maar 4 te zeggen. Dat levert per 5 beurten een netto winst van 7 punten.
Dit komt omdat de computer gemiddeld even vaak alle getallen gaat zeggen.

Voor de speler:
Speler Computer Totaal
41 4
42 4
43 0
44 4
45 9
21

Voor de computer:
Speler Computer Totaal
4 1 1
4 2 2
4 3 7
4 4 4
4 5 0
14

Dus de computer scoort gemiddeld 14 punten per 5 beurten, terwijl de speler gemiddeld 21 punten scoort.

Strategie 2:
Met game-theory is de optimale stategie van Undercut te bepalen. Uit de Pay-off matrix per beurt en de aanname dat het een zero-sum spel is volgen de frequenties van de getallen, hoe vaak ze gemiddeld in random volgorde moeten voorkomen.

Payoff-functie bij het kiezen van een bepaald getal
1: 0a + 3b - 2c - 3d - 4e = 0
2: -3a + 0b + 5c - 2d - 3e = 0
3: 2a - 5b + 0c + 7d - 2e = 0
4: 3a + 2b - 7c + 0d + 9e = 0
5: 4a + 3b + 2c - 9d + 0e = 0

hieruit volgt:
a (=1) = 10
b (=2) = 26
c (=3) = 13
d (=4) = 16
e (=5) = 1

Deze wel heel erg rationele tactiek druist wel heel erg tegen de eigenlijke bedoeling van het spelletje. Dit was ontworpen om de tegenstander tot 'fouten' te verleiden, en met geslepen tacktieken de tegenstander om de tuin te leiden.
Een goede manier om deze tactiek aan te pakken is om net als tegen de complete random strategie steeds 4 te zeggen. Dit is de meest optimale 'rationele' strategie tegen game-theory. Uit de statistiek volgt dan een gelijkspel.

Strategie 3:
Deze speler zegt bij elke ronde 4. Dit is een beetje een flauwe strategie maar tegen random spelers erg effectief. Tegen de compleet random strategie is het zelfs een winnende strategie en tegen de gametheory stragtie de optimale. Tegen menselijke tegenstanders is het echter een niet goed om deze strategie toe te passen aangezien die het snel genoeg door hebben.

Strategie 4:
De keuze van deze speler is steeds de vorige zet van de tegenstander. Ook een vorm van random spel. Maar wel erg doorzichtig. Deze strategie is meer grapje toegevoegd.

Strategie 5:
Voor de menselijke strategie hebben we enerzijds rekening gehouden met de manier waarop mensen dit spel spelen en aan de andere kant geprobeerd dit met kennislogica te beschrijven.
De mens neemt vaak niet de moeite om het gehele spel de zetten bij te houden en strategieen uit eerdere pogingen te onthouden. We zijn daarom uitgegaan van een temporeel geheugen van 5 zetten, waar strategieen op worden toegepast.
We zijn uitgegaan van een aantal basis strategieen die toegepast worden. Dit zijn een beetje losse manieren om het spel te spelen, maar als persoon heb je ook vaak de neiging om 'maar wat te zeggen'.

Om een ook een logische beschrijving te maken zijn we uitgegaan van het Kripke model dat het spel Undercut beschrijft.
Het Kripke model van het spel ziet er als volgt uit:

Het Kripke model M is een tupel <S,pi,R1,...,Rm> waar voor m agents geldt
1) S is een niet-lege verzameling toestanden.
2) pi: S => (P => {T,F}) waarheidstoekenning.
3) Ri deelverzameling van S x S (i = 1,...,m) toegankelijkheidsrelaties.
4) zi,j: agent i zegt j: vertaalsleutel.


Bijvoorbeeld toestand {1,2}:
pi(z1,1) = T;
pi(z2,2) = T;
({1,2},{1,3}) element van R1;
({1,2},{1,4}) element van R1;
({1,2},{1,5}) element van R1;
({1,2},{1,2}) element van R1;
({1,2},{1,1}) element van R1;
({1,2},{5,2}) element van R2;
({1,2},{4,2}) element van R2;
({1,2},{3,2}) element van R2;
({1,2},{2,2}) element van R2;
({1,2},{1,2}) element van R2;

Alle relaties zijn reflexief en symmetrisch. En transitief voor individuele spelers.

De manier waarop onze 'menselijke' computer speler speelt is gebaseerd op 4 regels en een afsluitstap:

1. Als mijn tegenstander 2 keer achter elkaar hetzelfde zegt dan probeer ik hem voor te zijn met undercutten. Met die twee keer hetzelfde 'verleidt' hij mij tot het zeggen van een getal net onder de zijne, dus gaat hij alvast daaronder zitten, dus zeg ik nog 1 lager. Dus als mijn tegenstander 2 keer 5 zegt, zeg ik de volgende ronde 2. Als ik echter 1 moet zeggen omdat mijn tegenstander 2 gaat zeggen, kan ik net zo goed 5 zeggen omdat het undercutten geen extra effect heeft.

R1: M |= t-2 K1 z2,x and M |= t-1 K1 z2,y and x = y and M |= t M1 z2,x-2 => M |= t z1,x-3

2. Als mijn tegenstander alleen maar hetzelfde getal zegt ga er dan 1 onder zitten.

R2: M |= t-1 K1 z2,x and M |= t-2 K1 z2,y and M |= t-3 K1 z2,v and M |= t-4 K1 z2,w and x = y = v = w and M |= t M1 z2,x => M |= t z1,x-1

3. Als mijn tegenstander in de laatste 5 zetten een undercut probeerde (bv. hij zegt 5 en daarna 3), zeg daarna na het volgende grote getal 3 eronder om hem weer te undercutten.

R3: M |= t-3 K1 z2,x and M |= t-2 K1 z2,y and x - y = 2 and M |= t-1 K1 z2,z and z >= 4 and M |= t M1 z2,z-2 => M |= t z1,z-3

4. Als ik geen wijs wordt uit mijn tegenstanders zetten zeg ik 4 omdat dat goed scoort tegen random strategieen.

Afsluit: Als uit mijn berekening een getal <= 1 is gekomen zeg ik 5.

Hier kunt U tegen de verschillende strategieen spelen.