Gioco dei fiammiferi
Di Massimo Fantin settembre 2001
Il gioco dei fiammiferi è un esempio di gioco di strategia, si tratta di giochi tra due giocatori che giocano alternativamente, ogni giocatore è obbligato a muovere, facendo passare il gioca dallo stato nel quale si trova ad un altro stato. Nei giochi di questo tipo esiste una posizione finale in genere perdente, il giocatore che si troverà in questa posizione avrà perso la partita, tutte le posizioni che permettono di giungere a tale posizioni sono vincenti perché il giocatore potrà con una mossa mettere l'avversario nella posizione finale perdente.
In generale sarà vincente una posizione se da essa si può giungere ad una vincente, mentre sarà perdente una posizione dalla quale comunque si muoverà si giungerà ad una posizione vincente. Facciamo un esempio di semplice gioco:
Il primo giocatore dice un numero da 1 a 10 , il giocatore successivo aggiunge un numero da 1 a 10. Perde chi supera 110 (Vince chi arriva per primo a 110.)
La strategia consiste nell'aggiungere in modo da arrivare sempre al multiplo dei 11 più vicino (stato perdente). Infatti se un giocatore arriva ad uno di questi numeri l'altro certamente dovendo aggiungere da 1 a 10 dovrà uscirne (posizione vincente) mentre il primo potrà sempre riportare l'avversario su una posizione perdente fino a giungere a 110 e vincere la partita.
In generale per trovare le posizioni vincenti e le perdenti si parte dalla posizione perdente finale (in questo caso 110) e si determinano tutte le posizioni dalle quali è possibile giungere ad essa, (in questo caso i numeri da 100 a 109) queste sono posizioni vincenti, il numero immediatamente prevedente sarà perdente, si procede come prima per classificare tutte le posizioni.
Nel gioco dei fiammiferi la cosa è più complicata infatti non esiste un metodo facile per capire se una posizione è vincente o perdente, occorre classificare le posizioni in modo ricorsivo, supponiamo di giocare con tre file di tre fiammiferi, le posizioni sono le combinazioni con ripetizioni di 4 oggetti di classe 3 ( perché bisogna considerare anche lo zero)
000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, 113, 122, 123 , 133, 222, 223, 233, 333
Ricordo che C'4,3 = 4*5*6 / 3! = 20.
Combinazioni con ripetizione perché supponiamo di poterle ordinare secondo il numero dei fiammiferi presenti nelle righe
La posizione iniziale perdente è la 001 che corrisponde ad avere un solo fiammifero in tavola.
Le posizioni che possono giungere ad essa con una mossa sono vincenti:
002, 003, 011, 012, 013
la posizione immediatamente successiva 022 è perdente infatti qualunque mossa si faccia si giungerà ad una vincente.
Alla 022 si può giungere da 023, 122, 222, 223, che sono vincenti, procedendo per ordine saliamo fino ad arrivare alla prima posizione non vincente che è la 0033 che è perdente in quanto da essa si può arrivare solo a posizioni vincenti. Si procede così fino alla fine classificando tutte le posizioni e indicando per le posizioni vincenti una delle posizioni perdenti alla quale si deve giungere per vincere:
Nella seguente tabella sono indicate tutte le posizioni, se sono perdenti o vincenti e per queste ultime le possibili mosse vincenti da giocare mentre per le perdenti tutte le mosse possibili che giungono sempre a configurazioni vincenti.
001, P 000
002, V 001
003, V 001
011, V 001
012, V 001
013, V 001
022, P 002, 012
023, V 022
033, P 003, 013, 023
111, P 011
112, V 111
113, V 111
122, V 022
123 , P 012, 013, 023, 112, 113, 122
133, V 033, 123
222, V 022
223, V 022, 123
233, V 033, 123
333 V 033
Il funzionamento del programma segue questo schema, individuato il tipo di gioco si costruisce una tabella sostanzialmente uguale a quella scritta sopra. Durante il gioco poi, classifica la posizione nella quale si trova e gioca di conseguenza.