Che tipo di problema è? Una cosa ad hoc? No perché a vederlo così sembra di dinamica, ma l’unica soluzione che mi viene in mente è implementare una funzione che giochi con strategia perfetta e far giocare il PC contro sé stesso…però mi pare un po’ un mastodonte in termini di efficienza LOL
Qualcuno l’ha risolto?
l'unica soluzione che mi viene in mente è implementare una funzione che giochi con strategia perfetta e far giocare il PC contro sé stesso...però mi pare un po' un mastodonte in termini di efficienza LOLkmfrick
Fai bene a sospettare, quando un algoritmo è esponenziale… Tuttavia conta che il “search space” nel gioco del tris è abbastanza piccolo (non stiamo mica parlando degli scacchi).
Diciamo che vogliamo considerare anche le combinazioni palesemente non valide, come questa:
XXX
X.X
XXX
(non è valida perché la X e la O si devono alternare)
Quanti sono i possibili stati? 3^9 = 19\,683 (abbiamo 9 posizioni e 3 simboli: O, X ed il punto).
Volendo quindi, puoi vederlo anche come un problema su un grafo che ha meno di 20mila nodi.
Comunque, questo problema può essere risolto tramite programmazione dinamica, usando le bitmask. In ogni caso anche una “bruteforce” sta ampiamente nei limiti di tempo, dato che le combinazioni possibili e corrette sono poche 
1 Mi Piace