# ---
# jupyter:
# jupytext:
# formats: ipynb,py:percent
# text_representation:
# extension: .py
# format_name: percent
# format_version: '1.3'
# jupytext_version: 1.15.2
# kernelspec:
# display_name: Python 3 (ipykernel)
# language: python
# name: python3
# ---
# %%
# %% [markdown] slideshow={"slide_type": "slide"}
# # Fondamenti di Programmazione
#
# **Andrea Sterbini**
#
# lezione 20 - 30 novembre 2023
# %% [markdown]
# # [NOI CI SIAMO](https://www.phys.uniroma1.it/fisica/archivionotizie/noi-ci-siamo-did-really-happen)
# ## 25 novembre:
# ## Giornata Internazionale per l'eliminazione della violenza sulle donne
# ## [Did This Really Happen?](https://didthisreallyhappen.net)
# %% RECAP [markdown] slideshow={"slide_type": "slide"}
# # RECAP:
# - Alberi di gioco
# - Somma di coppie pari o dispari in una sequenza di interi
# - Anagramma e numero di scambi
# - Dare i resti se si hanno certe monete
# %% [markdown]
# ## Una classe per visualizzare l'albero con Graphviz
# %% slideshow={"slide_type": "notes"}
from pygraphviz import AGraph
class GameNode:
_num_nodi = 0
def __init__(self):
GameNode._num_nodi += 1 # contatore condiviso per dare ID diversi alle istanze
self.__id = GameNode._num_nodi
self._sons = []
self._shape = 'box' # default shape
self._color = 'black' # default color
self._style = 'solid' # default style
def dot(self, G:AGraph) -> None:
"Costruisco la rappresentazione dell'albero da visualizzare con Graphviz"
G.add_node(self.__id, label=self, color=self._color, style=self._style)
for son in self._sons:
G.add_edge(self.__id, son.__id) # un arco per figlio
son.dot(G) # e ricorsivamente aggiungo i suoi figli
def show(self):
"layout e visualizzazione dell'albero"
G = AGraph()
G.node_attr['shape'] = self._shape
self.dot(G)
G.layout('dot')
return G
# %% [markdown] slideshow={"slide_type": "slide"}
# # GIOCO: Filetto/Tris
# - 2 giocatori
# - **configurazione**: scacchiera 3x3 con cimboli **o** oppure **x** (oppure spazio per la casella vuota)
# - **mosse possibili**: inserire il simbolo del giocatore di turno in una casella vuota
# - **vincita**: 3 simboli uguali in fila (riga, colonna o diagonale)
# - **convergenza**: max 9 caselle quindi max 9 mosse
# %% slideshow={"slide_type": "slide"}
import jdc
# nuovo tipo di errore per comunicare errori del gioco
class FilettoError(Exception):
pass
class Filetto(GameNode):
def __init__(self, configurazione=None):
"creazione di un nuovo nodo a partire da una data configurazione, rappresentata come matrice 3x3"
super().__init__()
self._shape = 'plain' # 'Mrecord' oppure 'record'
if configurazione is None: # se non viene passata
configurazione = [ [' ']*3 for i in range(3)] # ne creiamo una vuota
self._configurazione = configurazione
self._sons = [] # all'inizio non ci sono figli
def __repr__(self):
"rappresentazione sotto forma di stringa della tabella"
# graphviz mostra una scacchiera se il nodo ha shape='record'
# return '{' + '|'.join(['{'+ '|'.join(riga)+'}' for riga in self._configurazione ]) + '}'
# altrimenti se shape='plain' e label è racchiusa tra "<>" è un pezzo di HTML (in questo caso una tabella)
return ('<
' +
('
'.join( [ ('' +
' | '.join(riga) +
' | ' )
for riga in self._configurazione ] ) ) +
'
>')
# %% slideshow={"slide_type": "slide"}
F = Filetto()
F.show()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## Le mosse valide sono tutte le caselle libere
(MA SOLO se non è finita la partita)
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- elenco delle mosse valide
def mosse_valide(self):
"""Trovo le mosse valide (ma non ce ne sono se patta o qualcuno ha vinto)"""
if self.vittoria('X'): return []
if self.vittoria('O'): return []
if self.patta(): return []
return [ (x,y) # posso muovere in x,y se c'è uno spazio
for y,riga in enumerate(self._configurazione)
for x,casella in enumerate(riga)
if casella == ' ']
# definirò fra poco i metodi 'patta' e 'vincente'
# %% [markdown] slideshow={"slide_type": "slide"}
# ## il prossimo giocatore si ottiene contando le mosse
# - si inizia sempre con 'o'
# - però torniamo None se non ci sono più caselle libere
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- Prossimo giocatore
def prossimo_giocatore(self):
"si inizia sempre col simbolo 'o' quindi basta contare gli ' ' per sapere a chi tocca"
conteggio = sum( 1
for riga in self._configurazione
for cell in riga
if cell == ' ')
if conteggio == 0: # se non ci sono spazi
return None # non è il turno di nessuno
elif conteggio % 2 == 1: # inizia sempre 'o' (con 9 caselle libere)
return 'O'
else:
return 'X'
# %% slideshow={"slide_type": "fragment"}
Filetto().prossimo_giocatore()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## La partita è finita alla pari se non ci sono più mosse disponibili
# (ovvero nessuno ha già vinto)
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- Configurazione che dà patta
def patta(self):
"torno True se siamo in una patta (non ci sono caselle libere)"
return self.prossimo_giocatore() is None
# %%
# Una configurazione piena e senza filetti è
Filetto([[1,2,3],[4,5,6],[7,8,9]]).patta()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## una configurazione è vincente per un certo giocatore
se ci sono 3 simboli in fila uguali al suo
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- Configurazione vincente per un giocatore G o K (non intendo strategia)
def vittoria(self, giocatore):
"""la configurazione corrente è vincente per il giocatore se ci sono 3
dei suoi simboli in riga, colonna o diagonale"""
[[A,B,C],
[D,E,F], # spacchetto le celle
[G,H,I]] = self._configurazione
return (A == B == C == giocatore # prima riga
or D == E == F == giocatore # seconda riga
or G == H == I == giocatore # terza riga
or A == D == G == giocatore # prima colonna
or B == E == H == giocatore # seconda colonna
or C == F == I == giocatore # terza colonna
or A == E == I == giocatore # diagonale
or C == E == G == giocatore # antidiagonale
)
# %% slideshow={"slide_type": "fragment"}
# tre 1 allineati in diagonale
Filetto( [[1,1,1],
[2,1,2],
[3,3,1]]).vittoria(1)
# %% slideshow={"slide_type": "slide"}
# le mosse valide all'inizio sono 9
Filetto().mosse_valide()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## Per applicare una mossa basta mettere
il simbolo GIUSTO nella casella
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- Mosse: inserire il simbolo di turno in una delle caselle vuote
def applica_mossa(self, x, y):
G = self.genera_figlio(x,y) # costruisco il figlio con la mossa x,y
self._sons.append(G) # e lo aggiungo ai figli
return self # torno self per concatenare metodi
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
def genera_figlio(self, x, y):
"""data una coordinata x,y inserisco il giocatore di turno,
e costruisco un nuovo figlio con la nuova configurazione"""
if self._configurazione[y][x] != ' ': # se la casella NON è libera lancio errore
raise FilettoError(f"La casella {x} {y} è già occupata")
# altrimenti tutto OK
copia = [ riga.copy() for riga in self._configurazione ] # copio la configurazione
copia[y][x] = self.prossimo_giocatore() # e ci metto il simbolo alle coordinate x,y
return self.__class__(copia) # e creo un altro oggetto dello stesso tipo (NOTA: potrebbe essere una sottoclasse))
# %% slideshow={"slide_type": "slide"}
Filetto().applica_mossa(0,2).show()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## Finalmente generiamo tutto l'albero di gioco
# %% slideshow={"slide_type": "fragment"}
# %%add_to Filetto
# --- generare l'albero di gioco
def genera(self):
"Se ci sono mosse valide genero i figli, quindi espando anche i figli"
mosse = self.mosse_valide()
if not mosse:
self._color = 'red' # coloro le foglie di rosso
for x,y in mosse:
self.applica_mossa(x, y)
for figlio in self._sons:
figlio.genera()
return self # torno self per concatenare metodi
# %% slideshow={"slide_type": "slide"}
board = [['X','O',' '],
['X','X','O'],
['O',' ',' ']]
Filetto(board).genera().show()
# %% [markdown] slideshow={"slide_type": "slide"}
# ## Strategia vincente per il giocatore G
# - casi base
# - se patta NO
# - se vincente per G SI
# - se vincente per K NO
# - altrimenti: esiste una mossa per G tale che per tutte le mosse di K si arriva sempre ad una posizione vincente x G?
# - se è il turno di G e basta UNA mossa che porti alla vittoria di G
# - se è il turno di K e devono TUTTE portare alla vittoria di G
# %% slideshow={"slide_type": "slide"}
# %%add_to Filetto
# --- Strategia vincente per il giocatore G
def esiste_strategia_vincente(self, giocatore):
"vedo se questa posizione ha una strategia vincente per il giocatore"
if self.vittoria(giocatore): # sì se ho già vinto
return True
altro = 'O' if giocatore == 'X' else 'X'
if self.vittoria(altro): # no se ha vinto l'altro giocatore
return False
if self.patta(): # no se siamo alla patta
return False
# altro modo: se non ho figli e ho vinto True else False
pg = self.prossimo_giocatore()
if giocatore == pg: # se tocca a me
for figlio in self._sons: # e c'è almeno un figlio che è vincente posso muovermi lì e quindi questa posizione è vincente per me
if figlio.esiste_strategia_vincente(giocatore):
return True
else:
return False # altrimenti nessuno dei figli è vincente, questa posizione non è vincente
else: # se invece non è il giocatore a dover giocare
for figlio in self._sons: # per vincere, nessuna delle scelte dell'avversario deve essere vincente
if figlio.esiste_strategia_vincente(altro): # se una lo è, questa posizione NON è vincente per me
return False
else: # se nessuno dei figli è vincente per l'avversario
return True # allora io posso vincere da qui
# TODO: estrarre la sequenza di mosse vincenti
# %% slideshow={"slide_type": "slide"}
f1 = Filetto([
['O', ' ', 'X'],
[' ', ' ', 'O'],
['X', ' ', 'O'],
])
print('è posizione vincente per X? ', f1.vittoria('X'))
print('prossimo giocatore ', f1.prossimo_giocatore())
print('è patta? ', f1.patta())
f1.genera()
print("c'è una strategia vincente per X?", f1.esiste_strategia_vincente('X'))
f1.show()
# %% [markdown] slideshow={"slide_type": "slide"}
#
# ## Ottimizzazione: EVITIAMO di generare configurazioni EQUIVALENTI
# - questo riduce molto l'albero di gioco
# %% slideshow={"slide_type": "slide"}
class FilettoEfficiente(Filetto):
"specializzazione di Filetto che ricorda se due nodi sono equivalenti"
def __init__(self, board=None):
super().__init__(board) # come Filetto
self._equivalent = None # per default non sono equivalente a nessuno
# %% [markdown] slideshow={"slide_type": "slide"}
#
# ### quando due configurazioni sono EQUIVALENTI?
# - due configurazioni sono equivalenti se:
# - sono uguali per rotazioni (4 direzioni)
# - sono uguali per riflessione (4 direzioni)
# %% slideshow={"slide_type": "slide"}
# %%add_to FilettoEfficiente
def is_equivalent(self, other:AGraph) -> bool :
"controllo le 4 rotazioni e 4 riflessioni"
C1 = self._configurazione
[[A,B,C],[D,E,F],[G,H,I]] = other._configurazione
return ( C1 == [[A,B,C],[D,E,F],[G,H,I]] # identica (non serve?)
or
C1 == [[C,F,I],[B,E,H],[A,D,G]] # rot 90° antioraria
or
C1 == [[I,H,G],[F,E,D],[C,B,A]] # rot 180°
or
C1 == [[G,D,A],[H,E,B],[I,F,C]] # rot 90° oraria
or
C1 == [[A,D,G],[B,E,H],[C,F,I]] # diag. princ.
or
C1 == [[A,D,G],[B,E,H],[C,F,I]] # diag. second.
or
C1 == [[G,H,I],[D,E,F],[A,B,C]] # sopra sotto
or
C1 == [[C,B,A],[F,E,D],[I,H,G]] # sinistra destra
)
# %% [markdown]
# ## Un nodo equivalente non ha figli (niente mosse valide)
# %%
# %%add_to FilettoEfficiente
def mosse_valide(self):
if self._equivalent: # mosse vuote se equivalente
return []
return super().mosse_valide() # altrimenti come al solito
# %% [markdown]
# ## in applica_mossa se sono equivalente mi ricordo di chi
# - basta che guardo i "fratelli"?
# - oppure tutte le configurazioni costruite finora? (a questo livello) TODO
# %% slideshow={"slide_type": "slide"}
# %%add_to FilettoEfficiente
def applica_mossa(self, x, y):
"nell'applicare una mossa controllo se un altro figlio è equivalente e lo ricordo"
G = self.genera_figlio(x,y) # la generazione del nodo è come prima
for son in self._sons:
# se però è una configurazione equivalente ad una già generata
if son.is_equivalent(G):
G._equivalent = son # ricordo il nodo di cui sono equivalente
break # mi fermo al primo equivalente che trovo
self._sons.append(G) # e lo aggiungo ai figli per farlo vedere
return self
# %% [markdown]
# ## nel cercare se una configurazione è vincente, l'equivalente guarda all'altro nodo
# %%
# %%add_to FilettoEfficiente
# --- Strategia vincente per il giocatore G
def esiste_strategia_vincente(self, giocatore):
if self._equivalente:
return self._equivalente.esiste_strategia_vincente(giocatore)
else:
return super().esiste_strategia_vincente(giocatore)
# %% [markdown]
# ## Mettiamo assieme il codice (super() non lavora bene son jdc)
# %% slideshow={"slide_type": "slide"}
class FilettoEfficiente(Filetto):
"specializzazione di Filetto che ricorda se due nodi sono equivalenti"
def __init__(self, board=None):
super().__init__(board) # come Filetto
self._equivalent = None # per default non sono equivalente a nessuno
def is_equivalent(self, other:AGraph) -> bool :
"controllo le 4 rotazioni e 4 riflessioni"
C1 = self._configurazione
[[A,B,C],[D,E,F],[G,H,I]] = other._configurazione
return ( C1 == [[A,B,C],[D,E,F],[G,H,I]] # identica (non serve?)
or
C1 == [[C,F,I],[B,E,H],[A,D,G]] # rot 90° antioraria
or
C1 == [[I,H,G],[F,E,D],[C,B,A]] # rot 180°
or
C1 == [[G,D,A],[H,E,B],[I,F,C]] # rot 90° oraria
or
C1 == [[A,D,G],[B,E,H],[C,F,I]] # diag. princ.
or
C1 == [[A,D,G],[B,E,H],[C,F,I]] # diag. second.
or
C1 == [[G,H,I],[D,E,F],[A,B,C]] # sopra sotto
or
C1 == [[C,B,A],[F,E,D],[I,H,G]] # sinistra destra
)
def mosse_valide(self):
if self._equivalent: # mosse vuote se equivalente
return []
return super().mosse_valide() # altrimenti come al solito
def applica_mossa(self, x, y):
"nell'applicare una mossa controllo se un altro figlio è equivalente e lo ricordo"
G = self.genera_figlio(x,y) # la generazione del nodo è come prima
for son in self._sons:
# se però è una configurazione equivalente ad una già generata
if son.is_equivalent(G):
G._equivalent = son # ricordo il nodo di cui sono equivalente
G._color = 'cyan' # e mi coloro di azzurro
break # mi fermo al primo equivalente che trovo
self._sons.append(G) # e lo aggiungo ai figli per farlo vedere
return self
def dot(self, G:AGraph):
if self._equivalent: self._color = 'cyan' # visualizzo gli equivalenti azzurri
return super().dot(G)
# --- Strategia vincente per il giocatore G
def esiste_strategia_vincente(self, giocatore):
if self._equivalent:
# se equivalente chiedo all'equivalente
return self._equivalent.esiste_strategia_vincente(giocatore)
else:
# altrimenti esamino la situazione come al solito
return super().esiste_strategia_vincente(giocatore)
# %% [markdown]
# ## Esempio di albero di gioco con equivalenze
# %%
f2 = FilettoEfficiente([
['X', ' ', ' '],
[' ', 'O', 'O'],
[' ', 'O', 'X'],
])
print(f2.mosse_valide())
f2.genera().show()
# %% [markdown]
# ### Vediamo quali strategie sono disponibili
# %%
print('prossimo giocatore ', f2.prossimo_giocatore())
print('è patta? ', f2.patta())
player = f1.prossimo_giocatore()
print(f'è posizione vincente per {player}? ', f2.vittoria(player))
player = 'O'
print(f'è posizione vincente per {player}? ', f2.vittoria(player))
print(f"c'è una strategia vincente per {player}?", f2.esiste_strategia_vincente(player))
player = 'X'
print(f"c'è una strategia vincente per {player}?", f2.esiste_strategia_vincente(player))