Teoria dei giochi - un esempio pratico

di Andrea Benoni www.infocare.it
(copyright nessuna parte è riproducibile senza il consenso dell'autore, l'uso per fini didattici è libero)


La teoria dei giochi è la disciplina che studia i problemi di interazione strategica tra decisori in ambiti molto diversi, da quello economico ai giochi.
Questa è una variazione presa da una richiesta da Francesco R. sul newsgroup it.hobby.giochi.
Lo scopo del gioco è riempire le caselle di un rettangolo muovendosi solo orizzontalmente e verticalmente sulle caselle libere limitrofe (vedi figura seguente).

0
3@1
2

Ad ogni mossa si hanno potenzialmente 4 caselle su cui compiere la seguente, sempre che la destinazione ricada su una casella libera e all'interno della matrice.

Tipicamente le caselle sono una matrice 5x5 ma il gioco si presta ad essere usato anche in altre dimensioni e su altri fattori di forma.

Le strutture dati del programma sono quelle visualizzate sulla pagina html:
  1. La matrice - che riporta la sequenza delle mosse
  2. L Che rappresenta la mossa seguente che si sta tentando dalla posizione corrente
  3. X Che rappresenta la posizione X della mossa del livello
  4. Y Che rappresenta la posizione Y della mossa del livello

Tutte le matrici hanno 25 caselle come la profondità massima dell'albero delle mosse da esplorare.
Partendo dall'angolo in alto sulla sinistra l'albero ha i seguenti percorsi possibili, al primo livello:
2 e 3
il 2 ha come possibili sotto-nodi 1,2
il 3 ha come possibili sotto-nodi 1,2
e così via dicendo.

Il programma prova tutte le combinazioni riportando quelle complete nell'ultimo riquadro. Nelle "caselle finali" riporta il totale delle volte in cui trova una soluzione finendo su ciascuna.

Premendo esegui, il programma esegue una sola volta il riquadro "Inizializza" e poi a cadenze regolari (il tempo specificato) esegue un ciclo di valutazione.
Ad ogni ciclo viene valutata se la mossa successiva è all'interno della matrice, in caso positivo viene richiamata la funzione prova che, se trova la casella libera, la imposta come successiva mossa.
In coda alla pagina vengono riportate alcune note sulla programmazione.

Per iniziare la ricerca delle soluzioni premere esegui


Matrice:

Caselle finali:
00000
00000
00000
00000
00000
   L
X
Y

ogni millisecondi




Note di programmazione:
- Il programma è costruito interamente in JavaScript ed è liberamente e facilmente modificabile.
- Cambiando le caselle testate nel riquadro del programma è possibile provare alte variazioni sul sistema di spostamento della pedina. Una delle varianti del gioco implica un movimento orizzontale e verticale di due caselle e in diagonale di 1 (sempre 8 destinazioni).
- La funzione prova è all'interno del codice html della pagina per esigenze di programmazione. Per chiarezza il codice è riportato in uno dei riquadri.
- Il programma non è ricorsivo perché in questa forma è più semplice da dimostrare. La conversione in ricorsivo è un esercizio interessante per classi informatiche più avanzate.
- Le operazioni che operano sulle matrici sono in realtà funzioni nel codice html. Per questo motivo hanno il formato x(n) ma emulano a tutti gli effetti l'accesso alle matrici.