Dilemmi in 64 caselle...

[marcokrt]

Da secoli gli scacchi recano con sé dilemmi curiosi, legati all’esito di partite mai giocate. Paradossalmente, il più veloce scacco matto possibile (2 sole mosse a testa) risulta giocabile dal nero (colui che muove per secondo). Prevedere come si concluderà una partita tra avversari abilissimi è però un problema di tutt’altra natura, anche se possiamo affermare con certezza che lo scontro terminerà certamente entro il 5949-esimo turno [Chess Poster (2000), http://www.chess-poster.com/english/not ... u_know.htm].

Domanda 1: Se due super-computer (verosimilmente grandi quanto l’intera galassia) venissero messi a confronto in una partita a scacchi, con un limite di tempo per ogni giocatore di 1 anno (le possibili partite giocabili sono certamente meno di $10^(10^50)$ [G. H. Hardy (1999), G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, p. 17 // Walter Vannini (December 2003 − August 2007), 10, 10^10, 10^(10^10)… Infinity, http://www.gbbservices.com/math/large.html#Chess] – e verosimilmente meno di $10^(10^5)$ [J. R. Johnstone (2006), How many chess games are there… and who wins?, Australian Chess, pp. 39-41, http://members.iinet.net.au/~ray/Chessgames.htm] - con un numero massimo di disposizioni possibili dei pezzi stimabili in $10^47$), come finirebbe lo scontro (supponiamo che − per ipotesi - i due computer siano in grado di calcolare $10^(10^80)$ nodi al secondo)? Vittoria per il bianco o patta (il bianco ha il vantaggio della prima mossa – tecnicamente chiamato “tratto”)?

Domanda 2: Se fosse possibile giocare la “partita perfetta”, come si concluderebbe lo scontro (per partita perfetta si intende che entrambi i contendenti, prevedendo ogni possibilità, giocheranno solo mosse per arrivare alla vittoria o – qualora ciò non fosse possibile – per pattare o - se la patta non fosse raggiungibile - per perdere dopo il maggior numero di mosse possibile)?
Commento: Mentre non sono in grado di rispondere al primo quesito (se i processori giocassero a dama l’esito sarebbe chiaro − avendo a che fare con “sole” $5*1020$ possibili partite [Project - Chinook - World Man-Machine Checkers Champion. Retrieved 2007-07-19, http://webdocs.cs.ualberta.ca/~chinook/project/]), posso aggirare il secondo problema ricorrendo a un escamotage logico (un volgare trucco da baro).
La locuzione “partita perfetta” sottende che il nero giochi in modo ineccepibile, ma ciò comporta la patta! Infatti, una partita men che impeccabile, condurrebbe alla sconfitta del nero… il vantaggio del tratto (la mossa iniziale) appannaggio del bianco, qualora fosse sufficiente per la vittoria, escluderebbe “ex-ante” la consistenza ontologica del perfect game, ergo l’ipotesi stessa del secondo quesito ci porta a concludere che non siamo in questa situazione e che lo scontro terminerà senza vincitori né sconfitti.
In realtà, per “partita perfetta” potremmo anche intendere che il nero giochi forzando il bianco alla partita che implica, tra quelle a disposizione, il maggior numero di nodi da calcolare per pervenire alla vittoria, considerata la prima mossa del bianco. Tuttavia, se includiamo l’ipotesi di informazione completa da parte di entrambi gli opponenti circa le reciproche capacità computazionali (supponiamo per ipotesi che i processori – indistruttibili e imperturbabili - siano i medesimi e che in una frazione del tempo disponibile superino di gran lunga la numerosità delle partite giocabili dal punto di vista del potere predittivo), dobbiamo per forza concludere che la locuzione “partita perfetta”, al singolare, rappresenti un’imprecisione/errore espressivo qualora il nero non possa pattare.
Concretamente, i due processori inizierebbero a computare mosse; quando il bianco termina il processo, muove e allora, istantaneamente, la partita si conclude, giacché il nero ha ormai calcolato tutte le possibili varianti: la partita è già scritta e entrambi i computer ne sono al corrente, ma verranno comunque giocate (in un tempo infinitesimale) tutte le TOT mosse previste.

Congettura mia circa il primo quesito (Domanda 1): Finirà con un pareggio, opinione questa condivisa anche dalla maggior parte degli esperti del settore (http://www.chess.com/forum/view/general/perfect-game).

Osservazione: L’eventualità che il nero possa vincere non è stata presa in considerazione, giacché, seppur plausibile da un punto di vista “matematico”, non lo è nella pratica del gioco.

N.B.
Per ipotesi, il bianco calcolerà ogni possibile variante di gioco a partire dalla posizione iniziale, non si limiterà a giocare non appena avrà identificato una variante sicuramente vincente e non si arresterà nemmeno quando gli altri “rami” avranno superato, come numero di mosse, una variante vincente già trovata in precedenza. Si tratta di un’assunzione arbitraria, necessaria per poter risolvere univocamente i problemi aperti presentati in questa sezione.

Problema aperto 1: Quante mosse effettuerà al più il nero per pattare, al termine della (più lunga possibile) partita perfetta da ambo le parti (si esclude a priori la possibilità di accordo da parte del bianco fino a che non si verifica una condizione di “patta da manuale” – ripetizione di posizione, stallo, posizione morta, regola delle cinquanta mosse, scacco perpetuo)? Nel caso in cui la (più lunga possibile) partita perfetta dovesse concludersi con la vittoria del bianco, quante mosse effettuerà (al più) il nero prima di subire lo scacco matto?
Si noti che, per ipotesi, il bianco calcola ogni possibile variante e gioca per vincere nel minor numero di mosse possibile qualora ciò gli sia consentito, al netto dell’informazione (completa) che possiede circa le capacità (sovrabbondanti e pari alle sue) dell’avversario.
Se il bianco non riuscirà a spuntarla, si richiede di calcolare il più lungo match possibile per il quale il nero, giocando alla perfezione, non è in grado di sconfiggere l’avversario che muove per primo.

Problema aperto 2: Quante mosse dovrà effettuare almeno il nero per pattare, al termine della (più breve possibile) partita perfetta da ambo le parti (si esclude a priori la possibilità di accordo da parte del bianco fino a che non si verifica una condizione di “patta da manuale”). Nel caso in cui la (più breve possibile) partita perfetta dovesse concludersi con la vittoria del bianco, quante mosse effettuerà il nero prima di subire lo scacco matto?
Si noti che, per ipotesi, il bianco calcola ogni possibile variante e gioca per vincere nel minor numero di mosse possibile qualora ciò gli sia consentito, al netto dell’informazione (completa) che possiede circa le capacità (sovrabbondanti e pari alle sue) dell’avversario.
Se il bianco non riuscirà a spuntarla, si richiede di calcolare il più corto match possibile per il quale il nero, giocando alla perfezione, non è in grado di sconfiggere l’avversario che muove per primo.

Problema aperto 3: Se, come assunto in precedenza, entrambi i processori prenderanno esaustivamente in considerazione tutte le possibili partite giocabili al fine di giocare la più rapida o la più lunga partita perfetta possibile, quanti nodi dovrà calcolare il bianco?

(Tratto dall'ebook Congetture su interrogativi inediti: tra speculazioni, voli pindarici e riflessioni spicciole)