Originariamente inviato da Lucked
e la dama che è meno complessa degli scacchi, è matematicamente risolvibile? :master:
Allora, una precisazione: matematicamente risolvibile significa tutto e niente. Teoricamente significa "c'è un algoritmo che ti dà la soluzione", mentre nei nostri posto lo abbiamo usato con la definizione "c'è un algoritmo che ti dà la soluzione in un tempo ragionevole".
Quindi, il forza4 è matematicamente risolvibile: usi minmax su tutto l'albero e il computer riesce a giocare una partita in tempo reale dando la risposta in tempo ragionevole, mentre gli scacchi usa sempre il minmax ma siccome l'albero delle mosse è immenso ci vorrebbero miliardi di anni per ottenere la risposta. Di conseguenza non è matematicamente risolvibile in tempo ragionevole. Occorrono quindi diverse strategie per limitare la dimensione dell'albero.
Per quanto riguarda la dama sicuramente l'albero delle mosse è estremamente minore di quello degli scacchi, ma è anche estremamente maggiore di quello del forza 4.
Non so se i programmi che giocano a dama riescono a valutare l'intero albero o sono + simili a quelli di scacchi, non me ne sono mai interessato.
ciao