La mela avvelenata

Non commento l’argomento in esame, ma cercavo un blog su Internet che trattasse l’informatica teorica e pongo alcune domande alla fine del mio intervento.
Ho trovato una strategia (che ho inviato con il mio nominativo, Massimo Dacasto, a una rivista) per risolvere il gioco dell’Hex (le cui regole si imparano in 30 secondi) su tavolieri di lato pari senza regola della torta. Su tavolieri di lato dispari è conosciuta sin dagli anni ’50 una semplice strategia vincente per il primo giocatore consistente nell’occupare il centro (che è vietato), descritta nell’articolo di Martin Gardner su “Scientific American” del luglio 1957 e raccolta in un libro del 1959 che fu tradotto in italiano con il titolo “Enigmi e giochi matematici 1” (Sansoni).
La formalizzazione della mia strategia richiede nozioni topologiche, considerando che ogni casella ha 6 vicini e ci sono 3 direzioni delle caselle.
Come titolo di studio ho il diploma di maturità scientifica.
La strategia è la seguente:
si consideri un tavoliere di Hex con lato di 10 caselle con la diagonale maggiore disposta in orizzontale in cui il bordo superiore sinistro è blu e quello superiore destro rosso. Le caselle che confinano con il bordo superiore blu siano indicate con numeri dall’uno al dieci dal basso verso l’alto e quelle che confinano con il bordo inferiore rosso con lettere dalla “a” alla “j” dall’alto verso il basso. Si devono usare per convenzione gli stessi colori e orientamento del tavoliere (che a volte prevede la visualizzazione orizzontale di due bordi).
Nell’Hex difendersi equivale ad attaccare: in un gioco che non può finire in parità impedire all’avversario di creare una catena vincente equivale a crearne una propria.
Il Rosso muove in una delle due caselle centrali situate sulla diagonale minore. Il Blu effettua una mossa dove lo ritiene opportuno. Il Rosso risponde in una casella confinante e, in ordine di priorità,
- nell’unica casella confinante anche con due caselle rosse, quando viene minacciata la connessione tra le due caselle rosse stesse e manca una mossa per attuarla;
- connessa con il bordo rosso, se il Blu ha mosso a confine con il bordo rosso stesso e con una casella rossa contrassegnata dal numero 2 o 9 già esistente. In questo modo il Rosso attua la connessione al bordo rosso che viene minacciata;
- nell’unica casella contrassegnata dal numero 2 se esiste già una casella rossa a confine contrassegnata dal numero 3 e se sono libere le due caselle confinanti con il bordo rosso e con la casella stessa: quando mancano 2 caselle per connettersi a un bordo del suo colore il Rosso si avvicina ad esso, se la connessione viene minacciata. Un ragionamento analogo si può applicare all’altro bordo rosso del tavoliere;
- successiva di due lettere in ordine alfabetico e con un numero in meno, se sono libere le due caselle successive in ordine alfabetico a confine con quella in cui il Blu ha appena mosso. Se il Blu si avvicina a questa casella in cui è stato arginato dal Rosso quest’ultimo risponde nell’unica casella contrassegnata dalla stessa lettera nella quale ha effettuato il primo blocco.
- in basso a destra se il Blu ha giocato a sinistra della caselle centrale o sopra alla casella occupata alla prima mossa dal Rosso. Se il Blu ha giocato a destra della casella centrale o sotto alla casella occupata alla prima mossa dal Rosso quest’ultimo risponde nella casella in alto a sinistra.
Se però una catena blu inizia a sinistra della casella centrale e vi passa sopra o sotto il Rosso la argina in basso a destra. Per un ragionamento simmetrico se una catena blu inizia a destra della casella centrale e vi passa sopra o sotto il Rosso la argina in alto a sinistra. Se una catena blu inizia sopra alla casella in cui ha mosso il Rosso per primo e vi prosegue a destra il Rosso continua ad arginarla in basso a destra. Anche in questo caso per un ragionamento simmetrico se una catena blu inizia sotto alla casella in cui ha mosso il Rosso per primo e vi prosegue a sinistra il Rosso continua ad arginarla in alto a sinistra. In tutti questi casi può avvenire che il Blu giochi su una casella contrassegnata dalla stessa lettera di quella o quelle in cui ha giocato prima e con due numeri di differenza: il Rosso la argina allo stesso modo per evitare che il Blu le colleghi in seguito e soprattutto questa catena possa collegarsi successivamente a caselle con una lettera diversa, presupposto essenziale per vincere;
- se la casella di risposta in basso a destra è occupata il Rosso occupa quella in alto a sinistra, viceversa se la caselle di risposta in alto a sinistra è occupata il Rosso occupa quella in basso a destra, se neanche ciò è fattibile il Rosso allunga la sua catena di lunghezza massima e che ha più caselle vicine alla casella in cui ha effettuato la prima mossa (in ordine di priorità). Se due o più catene hanno gli stessi requisiti la scelta è indifferente.
Questa strategia si può generalizzare per un tavoliere di lato con un numero di caselle pari e maggiore di 8 (tavolieri ancora da risolvere).
La mia strategia ha implicazioni nella teoria della complessità computazionale? Risolvere l’Hex è PSPACE-complete, cioè risolubile con memoria polinomiale in tempi illimitati. Con questa funzione che associa ad ogni mossa del Blu una e una sola risposta del Rosso il tempo diventa limitato e si ha quindi una nuova classificazione? Si hanno ulteriori implicazioni su uno dei problemi del millennio che pone la questione se P sia uguale o meno a NP in informatica teorica? Posso avere una descrizione dettagliata con esempi semplici delle classi considerate e delle motivazione che portano ad affermare o negare che P e NP coincidano?

Massimo Dacasto
(angelodacasto@virgilio.it)