Proefstuderen 2014
Chomp
Chomp!
Strategisch happen
28 november 2014
J.M. de Graaf, Informatica, Universiteit Leiden
1
Proefstuderen
Regels
Gegeven een m bij n chocoladereep (m rijen en n kolommen), waarvan het stukje linksboven giftig is:
→
m = 3 en n = 7
Twee personen nemen om de beurt een hap vanaf rechtsonder. Een hap nemen betekent in feite dat een stukje
wordt aangewezen, en dat dat stukje plus alle stukjes rechts
daaronder (inclusief de stukjes uit de betreffende rij en
kolom) worden weggehapt. Degene die het giftige stukje
opeet verliest uiteraard.
2
Proefstuderen
Het spel
Gegeven een rechthoekig rooster bestaande uit m rijen en
n kolommen. Het vakje (1, 1) is giftig.
kolommen →
rijen
↓
i,j x
x
x
x
x
Twee spelers, A en B, nemen om de beurt een hap. Ze
wijzen dus om de beurt een vakje aan met co¨
ordinaten
(i,j) (d.w.z. rij i en kolom j) en halen vervolgens dat vakje
en alle andere vakjes met eerste co¨
ordinaat ≥ i EN tweede
co¨
ordinaat ≥ j weg. De speler die het giftige vakje weghaalt
(= opeet) verliest.
3
Proefstuderen
x
x
x
Een spelverloop
(2, 6)
(3, 3)
−→
A
−→
B
x
(1, 5)
−→
A
(1, 2)
−→
A
(2, 1)
x
−→
B
B verliest
A wint
4
Proefstuderen
Spelboom 2 bij 2
×
×
×
×
··
⌣
A
··
⌣
×
··
⌣
×
··
⌣
×
×
×
··
⌣
··
⌣
··
⌣
×
··
⌣
··
⌣
··
⌣
B
A
B
A
5
Proefstuderen
Spelboom
De spelboom (toestand-actie-ruimte) bevat alle standen
en alle mogelijke zetten (hier: happen), dus alle mogelijke
spelverlopen. Hieruit kun je halen of de beginnende speler
kan winnen, en zo ja hoe (winnende zet, winnende strategie).
Een stand is winnend voor de speler die aan de beurt is, als
diegene altijd kan winnen∗, ongeacht wat de tegenstander
doet.
Een stand is verliezend voor de speler die aan de beurt
is als, wat diegene ook doet, de tegenstander altijd kan
winnen∗.
∗ en,
bij perfect spel, ook z´
al winnen
6
Proefstuderen
2 bij 2
×
×
×
×
··
⌣
A
··
⌣
×
··
⌣
×
··
⌣
×
×
×
··
⌣
··
⌣
··
⌣
×
··
⌣
··
⌣
··
⌣
B
A
B
A
7
Proefstuderen
2 bij 2
×
×
×
×
··
⌣
A
··
⌣
×
··
⌣
×
··
⌣
×
×
×
··
⌣
··
⌣
··
⌣
×
··
⌣
··
⌣
··
⌣
B
A
B
A
8
Proefstuderen
2 bij 2
×
×
×
×
··
⌣
A
··
⌣
×
··
⌣
×
··
⌣
×
×
×
··
⌣
··
⌣
··
⌣
×
··
⌣
··
⌣
··
⌣
B
A
B
A
9
Proefstuderen
2 bij 2
×
×
×
×
··
⌣
A
··
⌣
×
··
⌣
×
··
⌣
×
×
×
··
⌣
··
⌣
··
⌣
×
··
⌣
··
⌣
··
⌣
B
A
B
A
10
Proefstuderen
Winnend?
Uit de toestand-actie-ruimte (spelboom) op de vorige pagina’s is het spel voor m = n = 2 helemaal te analyseren.
We hebben gevonden:
Chomp is voor m = n = 2 winnend voor de speler die
begint. Winnende beginhap: (2, 2).
Hoe zit dat voor andere waarden van m en n? En voor
tussenstanden?
11
Proefstuderen
Bijzondere gevallen -1-
- 1 bij n:
- L-vorm met benen even lang:
12
Proefstuderen
Bijzondere gevallen -1-
↓
- 1 bij n:
WINNEND
Winnende zet: (1, 2)
- L-vorm met benen even lang:
VERLIEZEND
Winnende strategie voor de
tegenstander: ’gespiegeld’ na-apen
13
Proefstuderen
Bijzondere gevallen -2-
- L-vorm met benen van verschillende lengte:
- n bij n:
14
Proefstuderen
Bijzondere gevallen -2-
- L-vorm met benen van verschillende lengte:
WINNEND
Winnende strategie: benen gelijk maken
→
en vervolgens ’gespiegeld’ na-apen
- n bij n:
∗
WINNEND
Hap (2,2) en vervolgens
’gespiegeld’ na-apen
15
Proefstuderen
2 bij 3
×
×
A
×
I
×
II
III
×
IV
×
B
V
Vervolgtoestanden I, II, IV en V zijn allemaal winnend voor
de speler die aan de beurt is, dus hier winnend voor B.
16
Proefstuderen
2 bij 3
×
×
A
×
×
×
×
I
×
×
II
III
×
×
B
A
IV
Vervolgtoestanden I, II, III en IV zijn allemaal winnend voor
de speler die aan de beurt is, dus hier winnend voor A.
Ergo . . . . . .
17
Proefstuderen
2 bij 3
×
×
A
×
×
×
×
×
×
×
×
B
A
18
Proefstuderen
2 bij 3
×
×
A
×
×
×
×
×
×
×
×
B
A
19
Proefstuderen
2 bij 3 is winnend
×
×
A
×
×
×
×
×
×
×
×
B
A
Chomp is voor m = 2, n = 3 winnend voor de speler die
begint. Winnende beginhap: (2, 3).
20
Proefstuderen
Bijzondere gevallen -3-
- 2 bij n:
←
WINNEND
Winnende strategie: neem in de eerste zet blokje (2, n) en
hap in de volgende zetten zo, dat telkens weer de bovenste
rij 1 blokje langer wordt dan de onderste rij. Dit is altijd
mogelijk, en leidt tot winst.
21
Proefstuderen
2 bij n
(2, 8)
x
x
−→
A
(2, 6)
x
x
−→
A
−→
B
(2, 4)
−→
A
(1, 5)
(1, 7)
x
x
−→
B
(1, 3)
−→
B
(2, 2)
x
−→
A
en B verliest
22
Proefstuderen
m bij n
m bij n Chomp is winnend voor de speler die begint: deze
kan dus altijd winnen, ongeacht wat de tegenstander doet.
Bewijs∗ (niet-constructief):
De hap (m, n) is een winnende beginhap (1) of niet (2).
1. (m, n) is een winnende beginhap
2. als (m, n) niet winnend is, is er is blijkbaar een winnende tegenhap, zeg (p, q), voor de tweede speler. Echter die hap had de
beginnende speler ook als eerste kunnen nemen, en dan was (p, q)
dus een winnende hap voor h´
em geweest.
Conclusie: er is altijd een winnende hap voor de speler die begint.
Helaas is in het algemene geval de winnende beginhap onbekend, laat staan een strategie om te winnen.
∗
dit soort bewijs heet strategy stealing
23
Proefstuderen
m bij n
In principe kun je voor elk m bij n Chomp-rooster een
spelboom tekenen, waaruit een winnende strategie is af te
leiden, dat wil zeggen, hoe de speler in elke beurt moet
happen om te winnen.
De
spelboom
wordt echter heel groot: er zijn maar liefst
m+n
verschillende standen mogelijk. Voor m = n = 5 is
m
dit 252, voor m = 6 en n = 7: 1716, voor m = n = 10:
184.756 en voor m = n = 20 is dit al bijna 138 miljard.
Met de hand is het al voor vrij kleine rechthoeken niet
meer mogelijk om de winnende beginhap (laat staan een
winnende strategie) te vinden. Misschien wel met behulp
van een computerprogramma?
24
Proefstuderen
Recursie
We noemen iets recursief als het naar zichzelf verwijst.
Voorbeeld:
leeftijd(nu) = leeftijd(een jaar geleden) + 1
Hoe oud ben ik?
Let op eeuwige recursie:
stopcriterium/basisgeval:
leeftijd(28−11−1959)=0
25
Proefstuderen
Recursie en 2persoonsspelen
Probleem: is een gegeven Chomp-stand winnend of niet?
Een stand is winnend voor degene die aan de beurt is als
een der directe vervolgstanden niet winnend is voor de
tegenstander.
Een winnende zet is dan natuurlijk een zet die leidt tot
zo’n niet winnende vervolgstand.
Een stand is verliezend (= niet winnend) voor degene die
aan de beurt is als alle directe vervolgstanden winnend zijn
voor de tegenstander.
Het ligt (dus) voor de hand om het probleem recursief op
te lossen.
26
Proefstuderen
Recursieve functie
We schrijven een recursieve functie winnend in C++ die
voor een gegeven (tussen)stand aangeeft of deze winnend
(True) is voor de speler die aan de beurt is of niet (False):
bool winnend(bool stand[m][n])
↑
↑
representatie Chomp-stand
Laat stand een (tussen)stand bij Chomp aangeven, en volg1,
volg2, . . ., volgs al diens mogelijke directe vervolgstanden
(dus via ´
e´
en hap verkregen uit stand). Dan:
winnend(stand) = not winnend(volg1) or
not winnend(volg2) or · · · or
not winnend(volgs)
27
Proefstuderen
Representatie
We representeren een Chomp-stand in C++ bijvoorbeeld
als volgt:
×
←→
1.
T
T
T
stand
T
T
T
T
T
T
T
T
T
T
T
F
T
F
F
boolean array
2-dimensionaal
×
←→
7
5
4
2.
stand
integer array
1-dimensionaal
28
T
F
F
Proefstuderen
Winnend
bool winnend(bool stand[m][n]) {
bool kopie[m][n]; int k,l;
if (allesisop(stand))
return true; // tegenstander heeft giftige stukje gegeten
else {
for (k=0; k<m;k++){
for (l=0; l<n; l++){
// loop alle vervolgstanden af
if (stand[k][l]) // het blokje bestaat
{
copieer(stand, kopie); // zet in een kopie
doezet(kopie,k,l); // doe de hap (k,l) aldaar
if (!winnend(kopie)) { // niet winnend voor tegenstander
return true; // dan winnend voor jou
}
}
}
}
return false; // geen winnende zet gevonden
} // else
} // winnend
29
Proefstuderen
Winnende zet
bool winstzet (bool stand[m][n], int & rij, int & kolom ){
bool kopie[m][n]; int k,l;
// nu wordt ook een winnende zet gegenereerd
if (allesisop(stand))
return true; // tegenstander heeft giftige stukje gegeten
else {
for (k=0; k<m; k++){
for (l=0; l<n; l++){
if (stand[k][l])
{
copieer(stand, kopie);
doezet(kopie,k,l);
rij = -1; kolom = -1;
if (!winstzet(kopie,rij,kolom)) { // verlies tegenstander
rij = k; kolom = l; // dan winnende zet voor jou
return true;
}
}
}
}
return false; // geen winnende zet gevonden
} // else
} // winstzet
30
Proefstuderen
m
2
3
2
3
4
2
3
4
5
2
3
4
5
6
n
3
3
4
4
4
5
5
5
5
6
6
6
6
6
winzet
(2,3)
(2,2)
(2,4)
(2,3)
(2,2)
(2,5)
(3,4)
(3,3)
(2,2)
(2,6)
(2,4)
(2,3)
(3,4)
(2,2)
Resultaten
tijd (sec)
0
0
0
0
0
0
0
0
0
0
0
0
21
702
m
2
3
4
5
2
3
4
2
2
2
2
2
3
3
3
n
7
7
7
7
8
8
8
9
10
11
12
13
9
10
11
winzet
(2,7)
(3,5)
(3,4)
(2,3)
(2,8)
(2,5)
(2,4)
(2,9)
(2,10)
(2,11)
(2,12)
(2,13)
(3,7)
(2,6)
(2,7)
tijd (sec)
0
2
105
22
0
2
105
0
3
14
62
293
222
231
552
Opm. Tijd op hele seconden afgerond; gemeten in 2011; in 2014 ruwweg 3x zo snel
Voor grotere repen gaat het veel te lang duren. Het geval 6 bij 7,
bijvoorbeeld, was na een uur n´
og niet klaar (2014).
31
Proefstuderen
Watervaleffect
Vraag: Waarom is ons programma zo langzaam? Voor m =
6, n = 7 zijn er maar 1716 standen die onderzocht moeten
worden. Dat is voor de computer toch geen probleem?
Antwoord: Er is hier sprake van een watervaleffect: heel
veel standen worden vele malen opnieuw bekeken en doorgerekend.
32
Proefstuderen
Voorbeeld: 2 bij 4
Dit is een klein stukje
van de spelboom voor
het geval 2 bij 4.
×
×
×
Stand * komt daar al
4 keer voor en wordt
dus 4 keer bekeken.
×
*
×
×
*
watervaleffect
×
*
×
*
33
Proefstuderen
Dynamisch programmeren
Een mogelijke oplossing voor het watervalprobleem is het
gebruiken van een geschikte datastructuur∗ waarin we alle
tussenresultaten opslaan. We hoeven standen dan maar
´
e´
en keer uit te werken.
Dit is een vorm van dynamisch programmeren.
Blijft echter het probleem dat het aantal standen exponentieel toeneemt met m en n .....
∗ vaak
is dat een array, d.w.z. een soort tabel
34
Proefstuderen
Van chocola tot recursie
het Droste-effect
werkcollege recursief Programmeren
www.liacs.nl/home/graaf/proefstuderen/practicum.html
35
© Copyright 2024 ExpyDoc
