HW 4.2 non riesco a capire come procedere con la funzione strategia_vincente

gianpcr (4620 points)
5 16 34
asked Dec 2, 2017 in Es2 by gianpcr (4,620 points)
edited Dec 2, 2017 by gianpcr
Salve a tutti, sono circa 4 giorni che sto cercando di capire come approcciare il problema nella quarta funzione del secondo hw senza riuscirci. Ho provato a procedere dalle foglie, salendo fino alla radice, calcolando per ogni nodo l'esito. Questo metodo funziona purtroppo solo in alcuni casi. Ho provato a calcolare il percoso minimo per un nodo dove ci sono 2 vittorie per il giocatore ma niente. Se possibile vorrei chiarimenti su quello che stiamo cercando con questa funzione, poichè a questo punto non credo di aver capito la richiesta. Ho già letto l'altra domanda riguardante la quarta funzione ma sinceramente non ho capito bene. Grazie in anticipo a tutti.

2 Answers

Best answer
D
Domenicobrz (1470 points)
2 9 19
answered Dec 2, 2017 by Domenicobrz (1,470 points)
selected Dec 3, 2017 by gianpcr

Assumendo di cercare la strategia vincente per il giocatore 'o' a partire da una qualunque configurazione, se il turno successivo è del giocatore 'o', deve essere presente almeno un nodo fra i figli della configurazione che stiamo valutando in cui il giocatore 'o' vince.

In quel nodo i figli rappresenteranno il turno del giocatore 'x', in ognuno di questi figli il giocatore 'o' deve avere una possibilità di vittoria ( [...] qualunque siano le mosse dell'avversario ha sempre la possibilita' di rispondere in modo che la partita termini con la sua vittoria [...] )

Continuando la ricorsione è il turno del giocatore 'o' e si cerca nuovamente un nodo in cui vince, in quel nodo il giocatore 'o' deve poter nuovamente vincere qualunque sia la mossa di 'x'

Evito di scrivere l'algoritmo completo per ovvi motivi ma da qui in avanti l'implementazione dovrebbe essere semplice, basta testarla su configurazioni con due-tre mosse prima della fine della partita. In questo modo non è neanche necessario valutare manualmente il caso base (possibile vittoria al primo turno) perchè l'algoritmo deve tornare True appena si verifica che il giocatore 'o' ha una strategia vincente, anche se non sono stati valutati tutti i nodi ricorsivamente

gianpcr (4620 points)
5 16 34
commented Dec 2, 2017 by gianpcr (4,620 points)
Se ho capito bene, devo scorrere l'albero finchè non mi capita una situazione simile giusto? Poi ovviamente il caso base di vittoria al primo turno si può verificare manualmente prima dell'inizio della ricorsione.
D
Domenicobrz (1470 points)
2 9 19
commented Dec 2, 2017 by Domenicobrz (1,470 points)
Esattamente. Non dovrebbe essere necessario il check per il caso base, ma se pensi possa migliorare la velocità puoi farlo poco prima di chiamare la funzione ricorsiva
gianpcr (4620 points)
5 16 34
commented Dec 3, 2017 by gianpcr (4,620 points)
Una domanda, se mi trovo ai nodi più alti dove ancora non c'è un esito della partita, come lo applico il tuo metodo? Devo scorrermi prima dalle foglie l'albero e poi usare il tuo metodo?
D
Domenicobrz (1470 points)
2 9 19
commented Dec 3, 2017 by Domenicobrz (1,470 points)
Il metodo va usato direttamente sulla configurazione che ti da il grader, essendo ricorsivo se necessario visiterà tutte le foglie che soddisfano le richieste dell'algoritmo
commented Dec 5, 2017 by Anon1 (9,920 points)
Scusami se rispondo solo adesso ma ci sto riflettendo pure io da diversi giorni. Ipotizzando che la griglia data rappresenti il turno del giocatore X, e come strategia vincente da cercare per il giocatore O, noi dobbiamo vedere se fra i figli della configurazione data (ossa il turno di O) sia presente una vincita di O. Ipotizzando che stiamo ancora lontani dalle foglie, dobbiamo passare in modo ricorsivo la griglia del giocatore O.
In questo caso, dato che la griglia è del giocatore O, dobbiamo vedere se nel turno successivo X non vinca o pareggi, e quindi passare di nuovo in maniera ricorsiva la griglia.
Il tutto si fermerà alle foglie, perchè lì è banale controllare se il giocatore O ha vinto, e ci basta sapere che riesce a vincere, ossia a trovare una strategia vincente. Questo dato poi si ripropagherà all'indietro.

Ancora non mi è molto chiaro però, nel caso la configurazione iniziale sia proprio del giocatore O come dovremmo controllare se ha una strategia vincente?
m
mirko (1920 points)
3 12 19
answered Dec 2, 2017 by mirko (1,920 points)
In sostanza ti si chiede di dire se un giocatore può vincere, partendo da una specifica configurazione, assumendo che il suo avversario giochi in maniera ottimale.
Ad esempio, partendo dalla configurazione vuota, nessuno dei due giocatori ha una strategia vincente (perchè un avversario che gioca in modo ottimo, potrà sempre almeno pareggiare). Mentre partendo dalla configurazione [['o', 'o', ''], ['o', 'x', ''], ['', 'x', '']], il giocatore 'o' ha una strategia vincente (perchè anche se 'x' gioca in modo ottimo, non ha modo di impedire la vittoria di 'o').

Partire dalle foglie è una buona idea per approcciarlo, però conviene modellare un po' il problema per semplificarsi le cose.
Diciamo che per ogni nodo (configurazione) vogliamo sapere il miglior risultato che può ottenere il giocatore di turno, sempre assumendo che l'avversario giochi in maniera ottima, una volta che abbiamo quest'informazione dovrebbe essere abbastanza facile rispondere anche alla richiesta originale.
Calcolare questo valore per le foglie è facile (si trova guardando l'esito della configurazione), se invece stiamo considerando un nodo che non è una foglia, il risultato migliore ottenibile dal giocatore corrente sarà uguale all'opposto di quello che può fare l'avversario nel caso peggiore. Faccio un esempio per spiegarmi meglio (diciamo che 0 = pareggio, 1 = vittoria, -1 = sconfitta, del giocatore corrente),  ipotizza che stiamo considerando un nodo i cui valori per i figli sono [1, 0, -1] allora questo significa che se il giocatore di turno fa una mossa che lo porta alla  configurazione del primo figlio, l'avversario avrà una strategia per vincere (di conseguenza il giocatore di turno perderà), mentre se il giocatore va al terzo figlio, l'avversario potrà al meglio perdere, cioè il giocatore di turno vincerà. Infine andando al secondo nodo, l'avversario potrà al massimo pareggiare, quindi anche il giocatore corrente pareggerà (quindi, ovviamente, al giocatore corrente conviene andare sul terzo nodo).
(ho scelto questi valori per i risultati cosi l'opposto di vincere (1) è perdere (-1) e viceversa, e l'opposto di pareggiare (0) è sempre pareggiare)

Comunque probabilmente esistono anche modi più semplici di approcciarlo, senza dover ridurre il problema originale ad un altro.
commented Dec 2, 2017 by Anon1 (9,920 points)
Nell'esempio con i numeri che hai fatto, e quindi il nodo che ha per figli [1, 0, -1] ha o non ha una strategia vincente?
m
mirko (1920 points)
3 12 19
commented Dec 2, 2017 by mirko (1,920 points)
Il giocatore di turno del nodo che ha figli [1, 0, -1] ha una strategia vincente, perchè può fare una mossa che lo manda sul terzo figlio e da lì l'avversario può "al massimo" perdere. Però come ho detto, qui non stiamo più rispondendo alla richiesta originale, ma per ogni nodo ci chiediamo qual è il miglior risultato possibile del giocatore corrente. Quindi bisogna ancora fare qualche controllo per poter rispondere alla richiesta originale