{"id":2129,"date":"2005-07-25T00:00:00","date_gmt":"2005-07-24T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"2129","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/2129\/","title":{"rendered":"È possibile costruire un algoritmo che permetta di calcolare tutto l’albero di varianti in una partita a scacchi?\r\nCos\u00ec da poter ottenere una sequenza di mosse fino ad una posizione teoricamente vinta.\r\nPer essere pi\u00f9 realistici, considerando l’enorme numero di mosse da calcolare, \u00e8 possibile eseguire questo calcolo in parallelo?\r\nGrazie fin d’ora"},"content":{"rendered":"

Il problema della valutazione delle mosse per risolvere il problema degli scacchi, ovvero per giocare in modo esatto, non \u00e8 un problema di algoritmo, che anzi \u00e8 concettualmente molto semplice:
data una configurazione valida della scacchiera, con la mossa al giocatore A, si pu\u00f2 generare una lista di tutte le mosse permesse, ogni mossa porta ad una nuova configurazione valida, o ad uno scacco matto, o ad una patta; per tutte le mosse che portano a configurazioni valide si ripete il procedimento (ricorsione) generando cos\u00ec “l\u2019albero delle mosse”.
Alla fine si avrebbe la radice con la posizione di partenza, tutte le possibili ramificazioni, e le “foglie” sarebbero tutte costituite da “scacchi matti” o “patte”.
Si scoprirebbe allora se per il giocatore bianco \u00e8 possibile vincere con certezza, o se la soluzione esatta \u00e8 la patta;
oppure, cosa assai meno probabile, il nero potrebbe avere sempre delle contromosse vincenti. <\/p>\n

\"\"\/<\/p>\n

Come giustamente intuisce chi ha posto la domanda, e per la fortuna di tutti quelli che giocano a scacchi, il problema \u00e8 la complessit\u00e0 computazionale dell\u2019algoritmo, che \u00e8 di tipo esponenziale: il numero di mosse da analizzare (e da memorizzare da qualche parte) cresce esponenzialmente col numero di mosse della partita.
Questo significa che si raggiungono presto dei numeri grandi ma cos\u00ec grandi che non bastano tutti i computer costruiti nel mondo per analizzare tutte le mosse in un tempo ragionevole; oppure se il pi\u00f9 potente supercomputer mai costruito si imbarcasse in questa avventura gli ci vorrebbe un tempo pari a molte volte l\u2019et\u00e0 dell\u2019universo… d\u2019altra parte il gioco degli scacchi a quanto si dice \u00e8 cominciato proprio con un aneddoto “esponenziale”: il famoso compenso che il suo inventore, il bramino Sissa, avrebbe “modestamente” chiesto al Re, un chicco di riso per la prima casella, due chicchi per la seconda, quattro per la terza e cos\u00ec via… fanno per la sessantaquattresima casella circa sedici miliardi di miliardi di chicchi,<\/p>\n

tenete presente la scorciatoia: 210<\/sup>~1000, 260<\/sup>~10006<\/sup>=1018<\/sup> <\/p>\n

Proviamo a fare qualche conto di massima:
supponiamo per semplicit\u00e0 che ad ogni turno ogni giocatore abbia la possibilit\u00e0 di fare 10 mosse, (in realt\u00e0 il numero di mosse possibili dipende dalla posizione, e spesso \u00e8 molto maggiore di 10; ad esempio in apertura ciascuno ha a disposizione 20 mosse: 16 di pedone e 4 di cavallo); una partita di media lunghezza di solito supera le 50 mosse,
fanno 1050<\/sup> posizioni da analizzare!
Per chi non ama gli esponenziali lo scrivo per esteso: 100.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000. <\/p>\n

Deep Blue analizza un miliardo di posizioni al secondo; supponiamo che un supercomputer possa analizzare 1 milione di miliardi di mosse al secondo, cio\u00e8 1015<\/sup> mosse al s; \u00a0
il tempo impiegato sarebbe 1050<\/sup>\/1015<\/sup>=1050-15<\/sup>s=1035<\/sup> s , peggio del decadimento del protone!
Supponiamo allora di far girare in parallelo un miliardo di questi supercomputer;
avremmo una capacit\u00e0 di calcolo pari a 109<\/sup>\u00b71015<\/sup> = 1024 <\/sup>mosse al secondo,
ma ci vogliono comunque 1026<\/sup> secondi, cio\u00e8 sempre alcuni miliardi di volte l\u2019et\u00e0 dell\u2019universo. <\/p>\n

Quindi possiamo essere sicuri che con le attuali tecnologie il problema degli scacchi rimarr\u00e0 insoluto.
Una possibilit\u00e0 futura potrebbe risiedere nel calcolo quantistico, che si dovrebbe prestare bene a questo tipo di problemi. <\/p>\n

Gli attuali programmi per computer invece, per cavarsela analizzano solo alcuni rami dell\u2019albero, quelli pi\u00f9 appetibili, e solo fino ad un certo livello di profondit\u00e0; per scegliere il ramo migliore utilizzano un punteggio legato alla posizione e alla quantit\u00e0 di materiale (i pezzi). <\/p>\n

Gli esseri umani giocano in modo ancora diverso: i rami analizzati sono molti meno di quelli presi in considerazione da un computer, ma il giocatore umano si basa su un piano strategico, che magari si realizzer\u00e0 in un numero di mosse superiore alla visibilit\u00e0 del computer.<\/p>\n

Link:<\/p>\n

Potete trovare quasi tutto sugli scacchi su questo splendido sito:<\/p>\n

http:\/\/scacchi.qnet.it<\/a><\/p>\n

in particolare potete trovare le partite Deep Blue – Kasparov<\/p>\n

http:\/\/scacchi.qnet.it\/manuale\/comp02.htm<\/a><\/p>\n\n\n","protected":false},"excerpt":{"rendered":"

[…]<\/p>\n","protected":false},"author":155,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"class_list":["post-2129","post","type-post","status-publish","format-standard","hentry","category-domande-varie-informatica-e-telecomunicazioni"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/155"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2129"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2129\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}