Un problema sugli scacchi

[RobStam]

Mi interesserebbe un suggerimento relativamente a questo problema assegnato alle gare a squadre di Cesenatico 2023.

"Maria è un’amante degli scacchi, e per passare il tempo decide di giocare al seguente solitario, sperando che duri
molto... Posiziona quattro cavalli ai vertici di una scacchiera 3×3. Poi muove i cavalli come negli scacchi, da un
vertice ad un altro di un sottorettangolo 2×3 della scacchiera. Inizialmente, n = 0. Ad ogni turno, Maria compie le seguenti operazioni:
A) muove ognuno dei cavalli in una casella che può legalmente raggiungere, scelta a caso, indipendentemente,
con probabilità uniforme: in questa operazione non è un problema se due o più cavalli si trovano nella stessa
B) casella incrementa n di 1.
C) se più cavalli si trovano nella stessa casella, li rimuove tutti tranne uno.
Se al termine di un turno rimane un solo cavallo, il gioco termina. Quanto vale n, in media, quando il gioco finisce?"

Io sto cercando di determinare le probabilità di chiudere il gioco in 3, 4, 5, ecc.. mosse, moltiplicare il numero delle mosse per la rispettiva probabilità e sommare il tutto per ottenere il valor medio.
All'inizio i quattro cavalli occupano i vertici della scacchiera. Dopo una mossa, in 3/4 dei casi i cavalli si riducono a 3, in 1/8 dei casi i cavalli si riducono a 2 in posizione opposta e in 1/8 dei casi rimangono 4.
Dopo la seconda mossa, nel caso siano rimasti dei tre cavalli, in metà dei casi rimangono tre cavalli, in 1/4 dei casi due cavalli in posizione diametralmente opposta e in 1/4 dei casi 2 cavalli in posizione tale da stare adiacenti ad un lato. Sempre dopo la seconda mossa nel caso in cui dopo la prima siano rimasti 2 cavalli, in metà dei casi i due cavalli si trovano in posizione opposta sulla diagonale e in metà casi sono adiacenti lo stesso lato. Nel caso in cui i cavalli si trovino adiacenti al lato, alla terza mossa c'è 1/4 di probabilità che il gioco termini. Quindi, dopo 3 mosse, la probabilità che il gioco termini a me risulta: (3/4x1/4x1/4+1/8x1/2x1/4)= 1/4.
Potrei proseguire in questo modo all'infinito, ma il procedimento mi sembra troppo macchinoso.
Ringrazio in anticipo chiunque mi fornisca qualche suggerimento per procedere nella soluzione del problema.
Cordiali saluti.

[Quinzio]

Provo a proporti una procedura, anche se non ne sono convinto al 100%.
Quello che devi arrivare a fare e' un grafo in cui i vertici sono il numero di cavalli e le frecce da un vertice all'altro e' la probabilita' di passare da una situazione all'altra, ad esempio da 3 cavalli a 2 cavalli.
Alla fine il grafo e' fatto cosi':
$4 -> 3 -> 2 -> 1$ .
In piu' c'e' il percorso alternativo
$4 -> 2$
Su ogni freccia scrivi la probabilita'.
Per la freccia $4 -> 3 $ e $4 -> 2$ le probabilita' le hai calcolate bene, $3/4$e $1/8$.
Anche $3->2$ con probabilita' $1/2$.
Per il caso $2->1$:
si considerano tutte le situazioni con uguale probabilita', quindi cavalli adiacenti o opposti.
Ad esempio con un cavallo in un angolo, l'altro cavallo puo' trovarsi nei due angoli adiacenti oppure all'angolo opposto.
Quindi i cavalli sono adiacenti con prob. $2/3$. Se sono adiacenti, finiscono sulla stessa casella con prob. $1/4$.
Quindi si rimane con 1 cavallo con prob. $1/6 = 2/3*1/4$.
Adesso il grafo e' completo.
Sostituiamo alla probabilita' il numero medio di mosse, che dovrebbe $m = 1/p$, e nel grafo alle probabilita' sostituiamo le medie delle mosse.
Quindi ricapitoliamo il grafo
$m(4->3) = 4/3$
$m(4->2) = 8$
$m(3->2) = 2$
$m(2->1) = 6$

Adesso per risolvere il grafo usiamo le stesse formule dei circuiti elettrici, non so se sei familiare con i circuiti.
Ovvero due resistenze in serie si sommano, due resistenze in parallelo si fa $(m_1 m_2)/(m_1 + m_2)$.
Se ci pensi ha senso: per due rami in serie, il numero medio di giocate e' la somma. E' molto intuitivo.
Per due rami un parallelo, se uno dei due rami ha una media bassissima di mosse, che so, $1/30$, si passera' molto spesso per quel ramo per concludere il gioco, quindi quel ramo ha un peso alto.

Quindi abbiamo
$m(4->3->2) = 4/3+2 = 10/3$
$m((4->3->2) "//" (4->2)) = m(4->2) = (10/3 8)/(10/3+8) = 40/17$
$m(4->2->1) = m(4->1) = 40/17 + 6 = 142/17$

Pero', ti ripeto, non sono sicuro che sia tutto corretto.

[RobStam]

Molte grazie per il suggerimento!

Ho provato a risolvere il problema con un grafo ad albero che procede all'infinito e che allego.
Ho scritto l'equazione risolvente:
1/8 x 1/6 + 3/4 x 1/2 x 1/6 + 1/8 x (1/8 x 1/6 + 3/4 x 1/2 x 1/6) + (1/8)^2 x (1/8 x 1/6 + 3/4 x 1/2 x 1/6) + ......... = (1/8 x 1/6 + 3/4 x 1/2 x 1/6) x ( 1 + 1/8 + (1/8)^2 +(1/8)^3 + ......) = 1/12 x ( 1 + 1/7) =
1/12 x 8/7 = 2/21.
Il numero medio di mosse risulta essere quindi 21/2, cioè 10,5 da cui la risposta 10 (viene richiesta la parte intera se il numero è decimale).

Può essere corretto ora il procedimento?
Cordiali saluti.

[Quinzio]

Si, l'idea e' corretta, pero' con il grafo "aperto" , ricorsivo, che procede all'infinito e' piu' facile fare errori. Se poi il grafo diventa piu' complesso e' ancora piu' difficile.
Credo che bisogna distinguere tra i due casi con 2 cavalli, quello con i cavalli adiacenti e quello con i cavalli opposti.
Nel grafo sono gli stati 2Opposti e 2Adiacenti.
Il problema e' che il grafo non e' un DAG, lo sarebbe se non ci fosse un loop tra gli stati 2O e 2A.
Per risolvere il loop bisogna considerare che il loop puo' essere percorso zero volte con probabilita' $(1/8)^0 = 1$, una volta con probabilita' $(1/8)^1$, due volte con probabilita' $(1/8)^2$ e cosi' via. Il totale di probabilita' aggiunta dal loop e' $sum_{n=0} 1/8^n = 8/7$.
Cioe' con zero volte, da 2A si va direttamente a 1, oppure da 2A si fa un loop e si va a 1, oppure due loop e si va a 1, ecc.
Quindi la probabilita' totale da 2A a 1 e' $8/7 1/4 = 2/7$.
Adesso che abbiamo "eliminato il loop", e il grafo e' un DAG, possiamo calcolare la probabilita' di tutti i percorsi
$3/4 * 1/4 *2/7 + 3/4 * 1/4 * 1/2 *2/7 + 1/8 * 1/2 * 2/7 = 11/112$.

Da cui la media a percorrerlo e' $112/11$.
Questa credo che sia la soluzione corretta.

come vedi e' meglio fare il grafo completo ma compatto in modo da poter seguire e tracciare tutti i percorsi e i loop.

[RobStam]

Grazie per la risposta esaustiva.
L'unico dubbio che mi rimane è che nel ciclo non viene considerato che c'è 1/8 di probabilità che alla prima mossa i cavalli rimangano in 4 e che quindi il tutto può ripetersi.
Non ha influenza sulla probabilità complessiva?
Ringrazio ancora, buona serata.