|
Strategie ottimali
di Ennio Peres
Marcel Duchamp, Study
for Chess Players, late 1911.
immagine da: http://www.guggenheimcollection.org/site/medium_work_lg_Work_on_paper_43_3.html
Un teorema della Teoria dei Giochi,
dovuto a Ernst Friedrich Zermelo, sostiene l’esistenza teorica
di una strategia ottimale per ogni gioco di competizione a due che,
come gli scacchi, non preveda mosse nascoste o affidate al caso e termini
sempre con un preciso risultato. In particolare, se un gioco di tale
tipo (che viene detto determinato) non prevede un risultato
finale di parità, la strategia ottimale è vincente
per uno (ed uno solo) dei due giocatori.
La garanzia dell’esistenza di una tale strategia non aggiunge
però alcuna informazione, né sulla sua struttura, né
su quale dei due giocatori favorisce.
Per poter applicare, in pratica, una strategia vincente bisogna essere
in grado di riconoscere quali configurazioni, ottenibili nel corso di
una partita, debbano considerarsi vincenti e quali perdenti,
secondo le seguenti definizioni:
- una configurazione è detta vincente, se determina
la vittoria immediata del giocatore cui toccherebbe muovere, o se consente
almeno una mossa che generi una configurazione perdente per il suo avversario;
- una configurazione è detta perdente, se determina
la sconfitta immediata del giocatore cui toccherebbe muovere, o se consente
solo mosse che generano configurazioni vincenti per il suo avversario.
Allargando questa impostazione ai giochi determinati che prevedono anche
il risultato di parità, si può introdurre il concetto
di configurazione equa, nel seguente modo:
- una configurazione è detta equa, se determina immediatamente
il risultato di parità tra i due giocatori, o se consente almeno
una mossa che generi una configurazione equa per il suo avversario (ma
nessuna che generi una configurazione perdente).
Honoré Daumier,
Giocatori di scacchi, 1868
È possibile ricavare delle strategie
ottimali complete solo se i giochi presi in considerazione sono relativamente
semplici.
Per la quasi totalità dei giochi più complessi (come scacchi,
dama, go, ecc.), non è stata ancora trovata una strategia ottimale,
neanche con tecniche informatiche.
Allo stato attuale, infatti, è impossibile anche per un supercomputer,
generare e classificare l’insieme di tutte le configurazioni ottenibili
da tali giochi.
In ogni caso, lo studio delle strategie ottimali costituisce un ottimo
esercizio per affinare la capacità di analisi di strutture ramificate;
un’attitudine del genere è, tra l’altro, preziosa
proprio per poter utilizzare proficuamente i linguaggi di programmazione
per computer.
I quindici fiammiferi
Uno dei più semplici esempi di gioco
determinato può essere così descritto.
1. Si mettono sul tavolo, in ordine sparso, 15 fiammiferi.
2. Dopo aver stabilito a chi spetta la prima mossa, ogni giocatore,
al proprio turno, deve togliere un numero di fiammiferi compreso tra
1 e 4, a sua scelta.
3. Perde chi è costretto a prendere l’ultimo fiammifero.
Per prima cosa, si può notare che
questo gioco non ammette un risultato di pareggio, per cui la sua strategia
ottimale è, più precisamente, vincente.
Per individuare tale strategia, il sistema migliore è quello
di partire dalla configurazione finale e procedere a ritroso fino a
ritornare a quella iniziale.
A questo scopo (denominando le configurazioni, in base al numero di
fiammiferi da cui sono composte), si può cominciare a osservare
che:
- 0 è vincente,
perché l’ultimo fiammifero è stato tolto dal giocatore
che ha appena effettuato la mossa e, quindi, chi sarebbe adesso di turno
ha vinto la partita.
- 1 è perdente, perché il giocatore di
turno non può far altro che prelevare l’unico fiammifero
rimasto.
- 2, 3, 4, 5 sono vincenti, perché il giocatore
di turno ha la possibilità di effettuare una mossa che lasci
a tavola un solo fiammifero .
- 6 è perdente perché, il giocatore di
turno, qualsiasi mossa faccia, non può fare a meno di porgere
all’avversario una configurazione vincente (2, 3, 4, o 5).
Proseguendo con questo ragionamento, non è difficile costruire
la seguente tabella, nella quale, in corrispondenza a ogni possibile
configurazione è riportata la relativa caratteristica (P
= perdente ; V = vincente) e la quantità
di fiammiferi che bisogna togliere per effettuare la mossa giusta.
Osservando il prospetto così ottenuto,
si può notare, in particolare, che il giocatore a cui spetta
la prima mossa ha la possibilità di vincere la partita, in quanto
la configurazione di partenza (15 fiammiferi sul tavolo) è vincente.
Sintetizzando le indicazioni riportate nella
tabella, si può enunciare la seguente semplice strategia:
- per vincere, bisogna prelevare un numero di fiammiferi tale che sul
tavolo ne restino: o 11, o 6, o 1.
Se non è possibile effettuare una mossa del genere, vuol dire
che la configurazione che si ha di fronte è perdente e che, quindi,
non si ha alcun modo per influire direttamente su un esito vittorioso
della partita (si può solo sperare che l’avversario, al
proprio turno, compia una mossa sbagliata...).
Thomas Couperthwaite Eakins, The Chess Players, 1876
Pari e dispari
Un altro esempio di gioco determinato, un
po’ più complesso di quello appena esaminato, può
essere così descritto.
1. Si mette sul tavolo, in ordine sparso, un qualsiasi numero dispari
di fiammiferi.
2. Dopo aver stabilito a chi spetta la prima mossa, ogni giocatore,
al proprio turno, deve togliere un numero di fiammiferi compreso tra
1 e 4, a sua scelta.
3. Quando non ci sono più fiammiferi a tavola, perde chi ha prelevato
globalmente un numero dispari di fiammiferi.
Si può osservare, intanto, che neanche
questo gioco ammette un risultato di pareggio (essendo dispari il numero
totale di fiammiferi, le quantità prelevate alla fine dai due
giocatori, dovranno essere necessariamente di diversa parità)
per cui, anche in questo caso, la sua strategia ottimale è,
più precisamente, vincente.
Analogamente a quanto visto in precedenza, il sistema migliore per individuare
tale strategia consiste nel partire dalla configurazione finale e procedere
a ritroso fino a quella iniziale. Questa volta, però, le considerazioni
da fare sono diverse a seconda se il giocatore a cui tocca muovere,
ha prelevato fino a quel momento una quantità pari di fiammiferi
(ovvero se, detto in maniera sintetica, è: pari in mano)
o se ne ha prelevato una quantità dispari (ovvero se, detto in
maniera sintetica, è: dispari in mano). Infatti,
si può cominciare a osservare che:
- la configurazione 0 è:
vincente, per il giocatore pari in mano;
perdente, per il giocatore dispari in mano.
- la configurazione 1 è:
perdente, per il giocatore pari in mano;
vincente, per il giocatore dispari in mano.
Cecil Aldin, Chess Players,
1901
immagine da: http://www.antique-maps-books.co.uk/acatalog/prints_3464_aldin.htm
Proseguendo con questo tipo di analisi,
si può costruire la seguente tabella (parziale, dato che il numero
di fiammiferi è indeterminato) nella quale, oltre ad avere affiancato
i dati relativi alle due possibili condizioni del giocatore di turno
(pari o dispari in mano), è stata introdotta anche un’analoga
informazione, relativa al suo avversario.
Osservando il prospetto così ottenuto,
si può notare che, in entrambe le situazioni, ogni sei righe
si ripresenta sempre lo stesso gruppo di dati.
In sintesi, quindi, si può affermare quanto segue.
- Il giocatore pari in mano si trova in una situazione perdente,
se sul tavolo c’è una quantità di fiammiferi uguale
a un multiplo di 6 più 1 (ovvero: 1, 7, 13, 19, 25, ecc.); indicando
con N il numero di fiammiferi che stanno sul tavolo, questa condizione
può essere sinteticamente espressa dalla formula: N = 6K+1 (con
K = 0, 1, 2, 3, ...).
- Il giocatore dispari in mano si trova in una situazione predente,
se sul tavolo c’è una quantità di fiammiferi uguale
a un multiplo di 6 (ovvero: 0, 6, 12, 18, 24, ecc.) o a un multiplo
di 6 meno 1 (ovvero: 5, 11, 17, 23, ecc.); indicando con N il numero
di fiammiferi che stanno sul tavolo, questa condizione può essere
sinteticamente espressa dalle due formule: N = 6K; N = 6K-1 (con K =
0, 1, 2, 3, ...).
In definitiva, la strategia da adottare consiste nel compiere sempre,
al proprio turno, una mossa che consenta di lasciare sul tavolo una
quantità di fiammiferi uguale a:
- 6K+1 (con K = 0, 1, 2, 3...), se l’avversario
in quel momento è pari in mano;
- 6K o 6K-1 (con K = 0, 1, 2, 3...), se l’avversario
in quel momento è dispari in mano.
Se non è possibile effettuare una mossa del genere, vuol dire
che la configurazione che si ha di fronte è perdente e che, quindi,
non si ha alcun modo per influire direttamente su un esito vittorioso
della partita (anche in questo caso, si può solo sperare che
l’avversario, al proprio turno, compia una mossa sbagliata...).
David Joseph BLES (1802 – 1872), Chess players, senza
data.
|
