Oplossing en python code bij SOS-Spel: analyse
Het antwoord op de laatste vraag:
Net als bij $N = 16$ verliest de beginner.
Dan de code van Pi en Phi (of misschien toch van Tom en Iris?):
(Je kunt de code ook rechstreeks downloaden als .py bestand)
"""Python programma bij "Een wiskundige doet de afwas 14 -- Het SOS spel: analyse"
Pythagoras, 63ste jaargang, nummer 2, november 2023
Auteur: Tom Verhoeff, TU Eindhoven
In Python >= 3.9, `@lru_cache(maxsize=None)` kan vervangen worden door `@cache`.
De type hints kunnen in Python >= 3.9 in de functie aanhef opgenomen worden.
"""
from functools import lru_cache # vanaf Python 3.2
# from functools import cache # vereist Python 3.9
import datetime as dt
from typing import Callable
@lru_cache(maxsize=None) # onthoud vorige resultaten; gaat sneller maar kost meer geheugen
def analyseer_1(bord):
# type: (str) -> tuple[str, str]
"""Bepaal uitslag voor eerste speler wanneer die begint met `bord`.
In geval van winst 'W' of remise '=', geef ook een zet die dat bereikt.
Verlies wordt aangegeven met 'X'.
De aanname is dat beide spelers optimaal spelen.
Dit is het eerste programma van Pi (21 regels code + 11 commentaar/leeg).
"""
if "SOS" in bord:
return ('X', '')
elif '-' not in bord:
return ('=', '')
beste_uitslag, beste_zet = 'X', '' # voor als we niets beters vinden
mutable_bord = list(bord)
# als het bord een palindroom is dan hoeven we maar de helft te onderzoeken
for i, hokje in enumerate(bord[:(len(bord) + 1) // 2] if bord == bord[::-1] else bord):
if hokje == '-':
for letter in "OS":
mutable_bord[i] = letter
uitslag, zet = analyseer_1(''.join(mutable_bord))
mutable_bord[i] = '-'
if uitslag == 'X': # 2e speler verliest, hoe dan ook; 1e speler kan dus winnen
return 'W', f"{letter} {i + 1}"
elif uitslag == '=': # 2e speler kan alleen remise houden; 1e speler kan dat dus ook
if beste_uitslag == 'X':
beste_uitslag, beste_zet = '=', f"{letter} {i + 1}"
# else: uitslag == 'W', 2e speler kan winnen; 1e speler vermijdt dit liefst
return beste_uitslag, beste_zet
DIEPTE: int = 0 # tot welke diepte het verloop getoond wordt in analyseer_2
@lru_cache(maxsize=None)
def analyseer_2(bord, diepte=0):
# type: (str, int) -> tuple[str, str]
"""Tweede programma, na advies van Phi.
Kan ook het verloop laten zien.
"""
indent = diepte * ' '
if diepte < DIEPTE:
print(f"{indent}analyseer({bord!r})")
if "SOS" in bord:
return ('X', '')
elif '-' not in bord:
return ('=', '')
# optimalisaties van Phi (zijn niet nodig, maar maken het wel veel sneller)
elif "SO-" in bord:
return ('W', 'S bij SO-')
elif "S-S" in bord:
return ('W', 'O bij S-S')
elif "-OS" in bord:
return ('W', 'S bij -OS')
elif "S--S" in bord:
if bord.count('-') % 2 == 0: # je moet een keer als 1e tussen S--S zetten
return ('X', '')
else: # je kunt nog ergens buiten S--S zetten
return ('W', 'buiten S--S')
beste_uitslag, beste_zet = 'X', '' # voor als we niets beters vinden
mutable_bord = list(bord)
for i, hokje in enumerate(bord[:(len(bord) + 1) // 2] if bord == bord[::-1] else bord):
if hokje == '-':
for letter in "OS":
if diepte < DIEPTE:
print(f"{indent}zet {letter} {i + 1}")
mutable_bord[i] = letter
uitslag, zet = analyseer_2(''.join(mutable_bord), diepte + 1)
if diepte < DIEPTE:
print(f"{indent} -> {uitslag} met zet {zet}")
mutable_bord[i] = '-'
if uitslag == 'X': # 2e speler verliest, hoe dan ook; 1e speler kan dus winnen
return 'W', f"{letter} {i + 1}"
elif uitslag == '=': # 2e speler kan alleen remise houden; 1e speler kan dat dus ook
if beste_uitslag == 'X':
beste_uitslag, beste_zet = '=', f"{letter} {i + 1}"
return beste_uitslag, beste_zet
def maak_tabel(n_max, analyseer):
# type: (int, Callable[[str], tuple[str, str]]) -> None
""""Druk tabel af met uitslagen voor borden t/m n_max.
"""
start_alle = dt.datetime.now()
for n in range(n_max+1):
print(f"{n:2}", end=': ')
if hasattr(analyseer, 'cache_clear'):
analyseer.cache_clear() # type: ignore
start = dt.datetime.now()
print(analyseer(n * '-'), dt.datetime.now() - start, end=' ')
if hasattr(analyseer, 'cache_info'):
print(analyseer.cache_info()) # type: ignore
else:
print()
print("Totale looptijd:", dt.datetime.now() - start_alle)
def interactief(n, analyseer):
# type: (int, Callable[[str], tuple[str, str]]) -> None
"""Laat interactief een spel spelen.
Toon ook analyse resultaat (best haalbare uitslag).
"""
assert 1 <= n <= 16, f"Aantal {n} ligt niet tussen 1 en 16"
mutable_bord = n * ['-']
zet_nr = 0
bord = ''.join(mutable_bord)
print(f"zet_nr: zet | analyseer({bord!r}) -> {analyseer(bord)}")
while True:
zet_nr += 1
while True:
zet = input(f"Zet {zet_nr} (letter, index)? ")
if len(zet) < 2:
print(f"Zet {zet!r} bevat niet genoeg informatie")
continue
letter = zet[0].upper()
if letter not in "OS":
print(f"Letter {letter!r} is geen O of S (kleine letter mag ook)")
continue
try:
i = int(zet[1:])
except ValueError:
print(f"Index {zet[1:]!r} is geen getal")
continue
if not (1 <= i <= len(mutable_bord)):
print(f"Index {i} ligt niet tussen 1 en {len(mutable_bord)}")
continue
if mutable_bord[i - 1] != '-':
print(f"Hokje {i} bevat al een {mutable_bord[i - 1]}")
continue
break
mutable_bord[i - 1] = letter
bord = ''.join(mutable_bord)
print(f"{zet_nr:6}: {zet:3} | analyseer({bord!r}) -> {analyseer(bord)}")
if "SOS" in bord:
print(f"{2 - zet_nr % 2}e speler wint")
break
elif '-' not in bord:
print("remise")
break
if __name__ == '__main__':
# Kies via "uitcommentariëren" welke functie je wilt aanroepen
# 1
# maak_tabel(16, analyseer_1) # kost ca. 5 minuten (op mijn laptop)
# 2
maak_tabel(16, analyseer_2) # kost ca. 1 minuut (op mijn laptop)
# 3
# DIEPTE = 2
# print(analyseer_2(7 * '-'))
# 4
# DIEPTE = 0
# interactief(7, analyseer_2)