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.