Het spel dat we in deze oefening bekijken, wordt door 2 spelers gespeeld op een speelbord met genummerde vakjes. Het spel bevat 1 pion, en de spelers verplaatsen om beurten deze ene pion. Hierbij gelden volgende regels:

• bij de aanvang van het spel, staat de pion op het veld met nummer s
• de pion kan enkel op een vakje met een priemgetal als nummer landen (met uitzondering van de startpositie, zijn alle vakjes die door de pion bezocht worden dus priemvakjes)
• bij elke beurt MOET de speler de pion een aantal vakjes vooruit zetten. Dit aantal ligt tussen 1 en N (grenzen inbegrepen)
• indien een speler geen geldige zet kan doen, verliest hij het spel.

Je kan aantonen dat het spel voor elke waarde van N eindigt. Er bestaat m.a.w. steeds een vakje waarbij het eerstvolgende priemgetal meer dan N vakjes verder ligt. Voor N=5 en startpositie 0, is dit eindvakje het vakje met nummer 23 (eerstvolgende priemgetal is 29, dus onbereikbaar vanuit vakje 23 indien grootste stap 5 bedraagt!). Het is dus zaak om als eerste op dit eindvakje te komen, waardoor de tegenspeler geen geldige zet meer heeft!

In deze opgave bouwen we volgende klassen:

• Speler: bevat voornamelijk een basisstrategie om het PriemSpel te spelen
• PriemSpel: bevat de logica van het spel zelf (spelregels), alsook de logica om het spel effectief te spelen met 2 spelers, waarvan de spelstrategie gekend is (zie klasse Speler)
• SpelerStrategie: erft over van de klasse Speler en bevat een alternatieve spelstrategie

Opmerking: bij de opsomming van methoden in een klasse, wordt het argument self in de opgave nooit expliciet vermeld. Wanneer er dus aangegeven wordt dat een methode geen argumenten heeft, wordt eigenlijk bedoeld dat de methode enkel self als argument heeft. Wanneer vermeld wordt dat een methode 2 argumenten heeft, wordt bedoeld dat de methode naast het self-argument nog 2 bijkomende argumenten heeft.

Klasse Speler

Programmeer in deze klasse:

• een constructor met 1 argument, namelijk een string die de naam van de speler voorstelt. Wanneer een object aangemaakt wordt, is de toestand van de speler als volgt:
  • de speler is NIET aan de beurt
  • de speler heeft het spel NIET gewonnen en ook NIET verloren
  Voorzie dus attributen om naast de naam ook deze gegevens bij te houden.
• reset(): deze methode plaatst de toestand van de speler terug in de begintoestand (namelijk NIET aan de beurt, NIET gewonnen en ook NIET verloren)
• __str__(): levert een stringgedaante van de speler, afhankelijk van de toestand van de speler, namelijk:
  • indien de speler gewonnen heeft, wordt de stringgedaante de naam van de speler voorafgegaan door een +-teken
  • indien de speler verloren heeft, wordt de stringgedaante de naam van de speler voorafgegaan door een --teken
  • indien de speler noch gewonnen, noch verloren is, maar aan de beurt is,wordt de stringgedaante de naam van de speler voorafgegaan door een *-teken
  • in alle andere gevallen, bestaat de stringgedaante uit de naam van de speler
• zet(): deze methode heeft als enig argument een object van de klasse PriemSpel (zie hieronder). De methode levert het aantal vakjes dat de speler vooruit wenst te gaan. De basisstrategie bestaat erin om de kleinste aantal toegelaten vakjes vooruit te gaan (neem aan dat er zo een zet bestaat). Programmeer eerst de klasse PriemSpel voor je de methode zet() programmeert.

Klasse PriemSpel

Programmeer in deze klasse:

• constructor met 4 argumenten, namelijk
  • speler1: een object van de klasse Speler of een van een klasse die hiervan overerft. Dit object stelt de startspeler van het spel voor.
  • speler2: analoog, maar nu voor de speler die als 2de aan de beurt komt.
  • start: het nummer van het startvakje (je mag aannemen dat dit niet-negatief is, dit startvakje hoeft geen priemvakje te zijn, maar is zo gekozen dat minstens 1 zet mogelijk is)
  • N: grootste toegelaten sprong voorwaarts (je mag aannemen dat $$N > 1$$)
  Bij aanmaken van een nieuw spel, is de toestand van het spel als volgt:
  • de pion staat op het startveld
  • beide spelers worden in een begintoestand geplaatst, met als enige uitzondering dat speler1 aan de beurt is
• __str__(): geen argumenten, levert als stringgedaante volgende informatie, gescheiden door komma's en het geheel tussen vierkante haakjes:
  • de stringgedaante van speler1
  • de stringgedaante van speler2
  • het nummer van het vakje waarop de pion nu staat
• einde(): geen argumenten, levert het nummer van het eindvakje van het spel op
• operator +=: heeft als enig argument een geheel getal, dat het aantal vakjes aangeeft dat de speler die aan de beurt is wenst vooruit te zetten. Indien de zet ongeldig is (de pion landt niet op een priemveld, of de genomen stap is te groot), heeft de operatie helemaal geen effect op het spel of de spelers. Indien de zet wel geldig is, wordt de pion verplaatst naar het nieuwe vakje en wisselt de beurt. Indien met deze zet het einde van het spel bereikt wordt wordt de winnaar/verliezer bepaald, en wordt de toestand van beide spelers dus aangepast (en zijn geen van beiden nog aan de beurt).
• speel(): speelt het spel met de opgegeven spelers. Hiertoe wordt het spel in zijn beginsituatie gebracht (namelijk de toestand na aanmaken van het object), en wordt het spel volgens de regels zoals geïmplementeerd in de methode zet() van de klasse Speler (en afgeleide klassen)). Het resultaat van deze methode is een tuple, namelijk:
  • een lijst van stringgedaanten van het spel, na elke zet. Het eerste element van deze lijst stelt de startpositie van het spel voor, het laatste de eindpositie.
  • een geheel getal 1 of 2, naargelang speler1 of speler2 het spel won
• reset(): brengt het spel en de spelers terug naar hun beginsituatie (i.h.b. de pion komt terug op de startpositie, speler 1 is aan de beurt, en niemand heeft het spel al gewonnen of verloren)

TIP:Je kan onderstaande functie gebruiken, die aangeeft een het natuurlijke argument n al dan niet priem is.

def priem(n):
    if n<2:
        return False
    for i in range(2, int((n**0.5)+1)):
        if n % i ==0:
            return False
    return True

Voorbeelden

Tab 1

speler1 = Speler('Emile')
print(speler1)  #Emile
speler2 = Speler('Zoe')
spel = PriemSpel(speler1, speler2, 0, 5)
print(spel) #[*Emile,Zoe,0]
print(spel.einde()) #23
spel += 5
print(spel) #[Emile,*Zoe,5]
spel += 2
print(spel) #[*Emile,Zoe,7]
spel += 2
print(spel) #[*Emile,Zoe,7]

Tab 2

speler1 = Speler('Emile')
speler2 = Speler('Zoe')
spel = PriemSpel(speler1, speler2, 0, 5)
print(speler1.zet(spel)) #2
print(spel) #[*Emile,Zoe,0]
spel += speler1.zet(spel)
print(spel) #[Emile,*Zoe,2]
print(speler2.zet(spel)) #1
spel += speler2.zet(spel)
print(spel) #[*Emile,Zoe,3]

spel.reset()
spelverloop, winnaar = spel.speel()
print(spelverloop)
#['[*Emile,Zoe,0]', '[Emile,*Zoe,2]', '[*Emile,Zoe,3]', '[Emile,*Zoe,5]', '[*Emile,Zoe,7]', '[Emile,*Zoe,11]', '[*Emile,Zoe,13]', '[Emile,*Zoe,17]', '[*Emile,Zoe,19]', '[+Emile,-Zoe,23]']
print(winnaar) #1

Klasse SpelerStrategie

In deze klasse, die overerft van Speler wordt een iets geavanceerdere strategie uitgewerkt (niet de optimale strategie). Hiertoe bekijkt de speler alle mogelijke sequenties van vaknummers die in het spel kunnen voorkomen, vanaf de huidige positie van de pion. Deze sequenties starten dus steeds met de huidige pion-positie en eindigen op het nummer van het eindvakje (zie klasse PriemSpel).

De speler bedenkt dat indien hij/zij als volgende zet een zet kiest zodat alle daaropvolgende sequenties een even aantal elementen elementen hebben, winst verzekerd is! Indien een zet gekozen wordt, zodat alle daarop volgende sequenties een oneven elementen hebben, dan is verlies verzekerd. Immers, wanneer alle mogelijke sequenties (volgend op deze zet) een even aantal elementen hebben, zal de speler steeds als laatste een geldige zet doen, waardoor de tegenstander verliest.

Daarom bouwt de speler 3 lijsten, namelijk:

• een lijst w met alle zetten die zeker winst opleveren
• een lijst v met alle zetten die zeker verlies opleveren
• een lijst o met alle andere toegelaten zetten (die dus voor deze strategie een onzeker resultaat leveren).

Je mag aannemen dat minstens 1 van deze lijsten niet leeg is. De volgende zet wordt als volgt gekozen:

• indien de lijst w niet leeg is, wordt de grootste zet gekozen uit die lijst
• indien de lijst w leeg is, wordt de kleinste zet uit o gekozen
• indien de lijsten w en o beide leeg zijn, wordt de kleinste zet uit v gekozen

Programmeer in deze klasse volgende methoden:

• alle_sequenties(): enig argument is een object van de klasse PriemSpel, en levert als resultaat een lijst-van-lijsten. Elk van deze lijsten is een geldige sequentie van vaknummers (inclusief de huidige positie van de pion) om vanuit de huidige pionposities op het eindvak te raken.
• winst_verlies(): enig argument is een object van de klasse PriemSpel, levert 3 lijsten, namelijk de lijsten w, v en o (hier net boven gedefineerd)
• zet():enig argument is een object van de klasse PriemSpel, het resultaat is het aantal vakjes dat de speler die nu aan de beurt is vooruit wenst te gaan, volgens de hier geschetste strategie

Voorbeeld

speler1 = Speler('Emile')
speler2 = SpelerStrategie('Zoe')
speler3 = SpelerStrategie('Frank')
spel1_2 = PriemSpel(speler1, speler2, 0, 5)
s = speler2.alle_sequenties(spel1_2)
t = {tuple(e) for e in s}
print(t)
#{(0, 2, 3, 7, 11, 13, 17, 19, 23), (0, 2, 3, 5, 7, 11, 13, 17, 19, 23), (0, 3, 7, 11, 13, 17, 19, 23), (0, 2, 5, 7, 11, 13, 17, 19, 23), (0, 5, 7, 11, 13, 17, 19, 23), (0, 3, 5, 7, 11, 13, 17, 19, 23), (0, 2, 7, 11, 13, 17, 19, 23)}
w, v, o = speler2.winst_verlies(spel1_2)
print(set(w)) #{5}
print(set(v)) #set() - lege verzameling
print(set(o)) #{2, 3}

z = speler2.zet(spel1_2)
print(z) #5

spelverloop1, winnaar1 = spel1_2.speel()
print(spelverloop1)
#['[*Emile,Zoe,0]', '[Emile,*Zoe,2]', '[*Emile,Zoe,5]', '[Emile,*Zoe,7]', '[*Emile,Zoe,11]', '[Emile,*Zoe,13]', '[*Emile,Zoe,17]', '[Emile,*Zoe,19]', '[-Emile,+Zoe,23]']

print(winnaar1) #2
 
spel2_3 = PriemSpel(speler2, speler3, 0, 5)
spelverloop2, winnaar2 = spel2_3.speel()
print(spelverloop2)
#['[*Zoe,Frank,0]', '[Zoe,*Frank,5]', '[*Zoe,Frank,7]', '[Zoe,*Frank,11]', '[*Zoe,Frank,13]', '[Zoe,*Frank,17]', '[*Zoe,Frank,19]', '[+Zoe,-Frank,23]']
print(winnaar2) #1