Dimostrazione per furto di strategia

Da Wikipedia, l'enciclopedia libera.

Le dimostrazioni per furto di strategia (dall'inglese strategy-stealing argument) sono usate nella teoria dei giochi combinatoria, per verificare, in svariati giochi, che il secondo giocatore non può avere una strategia vincente (ovvero una strategia che lo porti a vincere il gioco per qualunque scelta di mosse dell'altro giocatore). Questo avviene tramite una dimostrazione per assurdo.

Esempio[modifica | modifica wikitesto]

Una tipica dimostrazione per furto di strategia si applica nel tris (o filetto): supponiamo per assurdo che il giocatore B (che gioca per secondo) abbia una strategia vincente S. Possiamo allora convertire S in una strategia vincente per il giocatore A (che gioca per primo) nel seguente modo:

  1. A gioca la prima mossa deponendo il suo simbolo in una casella c a caso.
  2. Dalla seconda mossa, A gioca scegliendo la propria mossa applicando la strategia S ad una partita ipotetica in cui non sia mai stata fatta la mossa c di cui al punto 1, e la prima mossa sia stata fatta da B. In tale situazione, A è il secondo giocatore, e può dunque applicare la strategia S.
  3. Qualora la strategia S disponesse di muovere proprio nella casella c, A muoverà invece in una nuova casella libera scelta a caso, e questa sarà la casella ignorata d'ora in poi al punto 2.

Poiché S è una strategia vincente, A vincerà la partita ipotetica di cui al punto 2 e così anche la partita reale, poiché avere una pedina in più in gioco non porta svantaggio. In altre parole, quella appena descritta è una strategia vincente per A.

Quindi, l'esistenza di una strategia vincente S per il secondo giocatore implica l'esistenza di una strategia vincente per il primo giocatore, il che porta una contraddizione, dato che uno solo dei due giocatori può vincere una partita. Di conseguenza, non può esserci una strategia vincente per il secondo giocatore (un'analisi più approfondita mostrerebbe che il massimo che il secondo giocatore nel tris ha a disposizione è una strategia per non perdere, ovvero per garantirsi almeno il pareggio).

Applicabilità[modifica | modifica wikitesto]

Le dimostrazioni per furto di strategia si applicano a qualsiasi gioco simmetrico (ovvero in cui le regole che regolano le mosse permesse e la vittoria sono identiche per i due giocatori, per cui il primo può seguire una strategia del secondo) in cui una mossa in più per un giocatore non possa mai portare uno svantaggio al giocatore stesso. Alcuni esempi di giochi in cui una tale dimostrazione funziona sono i giochi m,n,k (di cui, oltre al tris, un esempio è il gomoku), hex e il gioco di commutazione di Shannon. Negli ultimi due giochi citati, una partita non termina mai con un pareggio, quindi con lo stesso criterio si dimostra un risultato più forte, e cioè che c'è una strategia vincente per il primo giocatore.

Le dimostrazioni a furto di strategia sono non costruttive: dimostrano che il primo giocatore ha una strategia vincente per pareggiare o vincere, ma non forniscono tale strategia.

Negli scacchi, è risaputo che muovere per primo è un vantaggio significativo per il Bianco, dato che gli permette di sviluppare i pezzi prima. Tuttavia, non esiste una dimostrazione per furto di strategia valida per gli scacchi. Aaron Nimzowitsch, o un altro ipermoderno, disse una volta scherzando che dopo 1.e4, la partita del Bianco è in stato di agonia. Secondo questo punto di vista, 1.e4 lascia il Bianco con una sistemazione dei pedoni debole, di cui il Nero può approfittare. Ciononostante, anche una mossa iniziale tranquilla, come 1.a3 o 1.Cf3, cambia la posizione in un modo che potrebbe, almeno in teoria, dimostrarsi successivamente svantaggioso per il Bianco.

È risaputo che negli scacchi si può arrivare a situazioni in cui un giocatore vince se è il turno dell'avversario, mentre perde o raggiunge una patta se è il suo turno. L'obbligo di muovere, raggiungendo un risultato non ottimale, è detto zugzwang. La disposizione iniziale di una partita di scacchi è probabilmente non zugwang, ma l'esistenza di zugzwang impedisce di applicare agli scacchi una dimostrazione per furto di strategia. In pratica, perché una dimostrazione per furto di strategia funzioni, bisogna che il giocatore, con una o più mosse supplementari, non peggiori mai la propria situazione. Quindi il zugzwang è solo uno dei molti possibili casi in cui tali dimostrazioni non funzionano.

Bibliografia[modifica | modifica wikitesto]