HW8 la ricorsione

Question

Ciao a tutti,

vorrei avere delle delucidazione nella ricorsività ...

al momento sto facendo il hw8 e sto procedendo senza le classi ma tramite le classiche funzioni e una delle prime cose che faccio e crearmi una matrice rappresentante la scacchiera.

Da questo momento in poi faccio implemento una funzione che prende in input la scacchiera e comincia ciclare per riga e per colonna per vedere se trovo una casella vuota dove poter inserire le pedine e se la trovo controllo se intorno ho delle pedine adiacenti dopodichè ho un vuoto totale sul da farsi perchè proseguendo in questa maniera io finirò per completare una evoluzione partendo dalla prima mossa che ha fatto il B ma non avrò le altre...

quindi qui entra in gioco capire la ricorsività e non capisco come sia possibile che richiamando la funzione con la matrice modificata (con l'ultima mossa effettuata)  io riesca a fare le altre evoluzioni

spero che qualcuno mi spieghi questa ricorsività

Answer 1

cosa non hai capito? la ricorsività in generale o come potresti inserirla nel programma?

Comments

non ho capito come funziona la ricorsività applicata a questo homework

---

La ricorsivitàio l'ho utilizzata per generare tutte possibili evoluzioni della partita. Ogni volta che la funzione ricorsiva viene chiamata, essa calcola tutte le possibili mosse che il giocatore di turno può fare nella scacchiera corrente. Per ognuna di queste mosse, la funzione chiama se stessa con il colore del giocatore opposto e la nuova scacchiera dopo che la mossa è stata eseguita.

Ad esempio, se abbiamo questa scacchiera di gioco:

.      .    W W
.     .     B B
W W W B
W B B W
 

Se il giocatore corrente è il nero, la funzione ricorsiva calcola tutte le possibili mosse che il giocatore nero può fare nella scacchiera in cui stiamo giocando. Nel caso cheti ho rappresentato il giocatore nero può mettere una pedina nella cella (0, 2) o nella cella (1, 2). In entrambi i casi, la funzione chiama se stessa con il colore del giocatore opposto (bianco) e la nuova scacchiera dopo che la mossa è stata eseguita:

B . W W
. . B B
W W W B
W B B W

. B W W
B . B B
W W W B
W B B W

La funzione continua a chiamarsi sempre ricorsivamente finché non raggiunge una configurazione di scacchiera in cui non sia più possibile effettuare alcuna mossa. A quel punto, la funzione restituisce il risultato della partita che può essere la vittoria del nero, vittoria del bianco e i risultati vengono accumulati e la funzione ritornerà la tripla:

(2, 16, 0)

che viene restituita dalla funzione dumbothello. 

non so se mi sono spiegata, io l'ho applicata in questo modo ma te puoi variare! basta che ci sia nel programma, non importa dove!

---

se ti risulta più semplice puoi vedere la scacchiera come un albero (che abbiamo fatto a lezione quindi magari puoi aiutarti anche con i pdf) e ricorrere alla ricorsione in quel caso lì

---

allora ricapitolando mi devo calcolare tutte le mosse possibili quindi immagino che devo  mettermele da una parte tipo una lista che conterrà appunto le cordinate delle mosse possibili che posso effettuare e questa funzione la piazzo immagino in quella dove sto facendo la ricorsività poi mi itero tutte ste possibili mosse(che ho ottenuto dalla funzione che mi ha controllato quali sono le mosse possibili) e per ognuna di queste richiamo la funzione di nuovo

---

sì, alla fine la funzione la puoi chiamare direttamente nella principale def dumbothello ad esempio. Dopo aver letto i file che contengono la configurazione inziale della scacchiera ritorni la funzione *ricorsione_esempio* per generare "l'albero di gioco completo".  ricordati che è una tupla. Oppure in alternativa potresti richiamare ricorsivamente la funzione sullo stato della scacchiera modificato, utilizzando come parametro il giocatore successivo (in base al turno). alla fine della ricorsione restituisce appunto la tupla

---

Ricorda che in generale la ricorsione viene utilizzata quando un problema o un'algoritmo può essere espresso in termini di se stesso. Ciò significa che per risolvere il problema o eseguire l'algoritmo, è necessario eseguire la stessa operazione o una serie di operazioni simili più volte. per questo è molto utile utilizzarlo per verificare le pedine e la scacchiera!

PS. ti consiglio di vederti questo pdf https://twiki.di.uniroma1.it/pub/Programmazione1/AA22_23/DiarioDelleLezioni-CanaleAL/lezione19.pdf. Il professore tratta di un gioco molto più semplice ma la logica di base c'è.

---

Perdonate se mi intrometto un secondo, ma nell'esempio che hai proposto:

Nel caso che ti ho rappresentato il giocatore nero può mettere una pedina nella cella (0, 2) o nella cella (1, 2).

Le mosse possibili del nero non dovrebbero essere 4? Una per ogni ".", ovvero casella vuota? 

---

Le mosse possibili sono una per ogni "." solo però nel caso in cui ci sia una pedina avversaria nelle 8 caselle adiacenti. Quindi i possibili spazi dove mettere una pedina che rendono la mossa valida sono 3, quello in alto a sinistra non è una mossa valida.

---

Ah giusto, grazie 

---

Scusami, ma in questo esempio le mosse del nero non dovrebbero essere (0, 1), (1,0) e (1,1)?

Answer 2

prima di applicare la mossa di piazzare la pedina in un determinato punto, potresti copiarti la matrice della scacchiera ed effettuare la mossa di piazzare la pedina solo sulla copia della matrice, così da avere sempre l'originale da parte senza alcuna modifica, in questo modo potrai fare tutte le evoluzioni possibili piazzando la pedina negli altri punti(se presenti), ovviamente tenendoti sempre da parte l'originale

Comments

ma tutto questo lo faccio come facendo la ricorsività ?? e perche mi serve avere sempre la matrice originale da parte ??

---

Ti serve perché così sull'originale puoi iterarci senza modificarla e creare delle copie della matrice modificate che tutti insieme compongono tutte le possibili nuove mosse. Su ognuna di queste nuove scacchiere con queste nuove mosse riapplichi la funzione ricorsiva fino ad arrivare ad un caso base, una foglia.