Giochi in PHP: Forza 4

In questo paragrafo verrà spiegato come implementare un programma per far giocare il computer a forza 4. Questo gioco è abbastanza noto sia ai bambini che agli adulti. Verrà ripresa la metodologia ricorsiva del min-max, e introdotta la metodologia dei tagli Alfa-Beta. Vengono invece tralasciate le euristiche che permetto di far giocare al meglio il computer.

Consideriamo le variabili contenenti i dati dello schema del gioco:

La variabile ($matrice) contenente lo schema, è un array di 42 elementi dove gli indici sono impostati nel modo seguente.

0	1	2	3	4	5	6

7	8	9	10	11	12	13

14	15	16	17	18	19	20

21	22	23	24	25	26	27

28	29	30	31	32	33	34

35	36	37	38	39	40	41

La costante COMPUTER definisce il simbolo relativo alla mossa del computer

La costante UTENTE definisce il simbolo relativo alla mossa dell’utente

La costante MAX_PUNTEGGIO definisce il valore con il quale il computer vince

La costante MIN_PUNTEGGIO definisce il valore con il quale il computer perde

La costante ALTEZZA definisce il numero di righe della matrice del gioco

La costante LARGHEZZA definisce il numero di colonne della matrice del gioco

La prima funzione che andremo ad implementare è quella relativa al controllo della vittoria: ovvero la funziona verifica se l'utente o il computer è riuscito a comporre una sequenza di quattro elementi successivi, disposti in verticale, orizzontale o in diagonale. Poiché la vittoria è data dall'inserimento di un pezzo in una data casella, invece di controllare tutto il gioco, la funzione controlla se inserendo un pezzo alla posizione [$x $y], si ottengono quattro elementi successivi. Di seguito il codice.

La visualizzazione del gioco a fine partita è piuttosto semplice. Di seguito la funzione che lo implementa.

La funzione successiva è molto utile e a partire dalla coordinata ($x) calcola la rispettiva coordinata ($y), in pratica cerca l'ultima posizione libera.

Di seguito l'implementazione dell'ambiente grafico di gioco, con la visualizzazione dello schema, e la possibilità da parte dell'utente di selezionare la sua prossima mossa. L'utente ha anche la possibilità di decidere di far iniziare il computer. Di seguito il codice.

if (!$partita) 
{
 ?><input type="hidden" name="prima_mossa" value="si">
 <input type="submit" name="iniziatu" value="Inizia Tu"><?php 
} 
?>
</form>

Infine vediamo il controllo del gioco

//funzioni utili

function getmicrotime()
{ 
    list($usec, $sec) = explode(" ",microtime()); 
    return ((float)$usec + (float)$sec); 
}

//definizione varibili

$time_start = getmicrotime();

define ('COMPUTER', 'X');
define ('UTENTE', 'O');
define ('ALTEZZA', 6);
define ('LARGHEZZA', 7);
define ('MAX_PUNTEGGIO', 100);
define ('MIN_PUNTEGGIO', -100);

$matrice = $_POST['matrice'];
$iniziatu = $_POST['iniziatu'];
$mossa_utente = $_POST['mossa_utente'];
$prima_mossa = $_POST['prima_mossa'];

//funzioni utili del gioco

function stampa_forza4(&$matrice)
{
......
}

function CalcolaY(&$matrice, $x)
{
......
}

function Verifica4(&$matrice, $x, $y)
{
......
}

//funzioni di ricerca della mossa

function CercaMossa(&$matrice, &$pos_x, &$pos_y)
{
......
}

//controllo del gioco

if ( ($matrice) || ($iniziatu) )
{
    if ($mossa_utente)
    {
      $y=(int)($mossa_utente/LARGHEZZA);
      $x=$mossa_utente-($y*LARGHEZZA);
      $r=Verifica4(&$matrice, $x, $y);
      if ($r<0)
      {
          stampa_forza4($matrice);
          echo "<br>Hai vinto!";
          exit();
      }
    }
    
    if ( ($prima_mossa=='si') || (!$mossa_utente) )
    {
        $x=rand(1,5);
        $y = CalcolaY($matrice, $x);
    }
    else
    {
      $conto=0;
      $taglio_alfa=0;
      $taglio_beta=0;
      CercaMossa($matrice, &$x, &$y);
    }
    $matrice[$x+$y*LARGHEZZA] = COMPUTER;
    $r=Verifica4(&$matrice, $x, $y);
    if ($r>0)
    {
        $time_end = getmicrotime(); 
        $time = $time_end - $time_start;
         
        echo "Nodi visitati: $conto; Tagli Alfa: $taglio_alfa; Tagli Beta: $taglio_beta<br>Tempo di esecuzione: ".number_format($time, 4, ',', '.');
        stampa_forza4($matrice);
        echo "<br>Ho vinto!";
        exit();
    }

$time_end = getmicrotime(); 
    $time = $time_end - $time_start;
     
    echo "Nodi visitati: $conto; Tagli Alfa: $taglio_alfa; Tagli Beta: $taglio_beta<br>Tempo di esecuzione: ".number_format($time, 4, ',', '.');
    $partita=true;
}
else
{
    $matrice = array (
    		  '', '', '', '', '', '', '',
    		  '', '', '', '', '', '', '',
    		  '', '', '', '', '', '', '',
    		  '', '', '', '', '', '', '',
    		  '', '', '', '', '', '', '',
    		  '', '', '', '', '', '', ''
    );
    $partita=false;
}

// ambiente grafico del gioco
......

Mossa random
La successiva funzione implementa la ricerca di una mossa valida, che come visto precedentemente con il tris si tratta di una ricerca stupida.

Mossa Max
La successiva funzione implementa la ricerca semplice della vittoria.

Mossa Min-Max
Di seguito l'implementazione del metodo min-max.

function CercaMossaMax(&$matrice, $x, $y, $livello)
// torna 0 se patta
// torna MAX_PUNTEGGIO se vince computer
// torna MIN_PUNTEGGIO se vince utente
{
    $r = Verifica4($matrice, $x, $y);
    if ($r==MIN_PUNTEGGIO) return $r;
    if ($livello==0) return 0;
    $controllo = MIN_PUNTEGGIO;
    $mosse_minime=0;
    for($x=0; $x<LARGHEZZA; $x++)
    {
        $y = CalcolaY($matrice, $x);
        if ($y<0) continue;
        $matrice[$x+$y*LARGHEZZA] = COMPUTER;
        $r = CercaMossaMin($matrice, $x, $y, ($livello-1));
        $matrice[$x+$y*LARGHEZZA] = '';
        if ($r==MAX_PUNTEGGIO) return $r;
        if ($r==MIN_PUNTEGGIO) $mosse_minime++;
        if ($controllo<$r) $controllo=$r;
    }
    if ($controllo==0) return -$mosse_minime;
    return $controllo;
}

function CercaMossaMin(&$matrice, $x, $y, $livello)
// torna 0 se patta
// torna MAX_PUNTEGGIO se vince computer
// torna MIN_PUNTEGGIO se vince utente
{
    $r = Verifica4($matrice, $x, $y);
    if ($r==MAX_PUNTEGGIO) return $r;
    if ($livello==0) return 0;
    $controllo = MAX_PUNTEGGIO;
    $mosse_massime=0;
    for($x=0; $x<LARGHEZZA; $x++)
    {
        $y = CalcolaY($matrice, $x);
        if ($y<0) continue;
        $matrice[$x+$y*LARGHEZZA] = UTENTE;
        $r = CercaMossaMax($matrice, $x, $y, ($livello-1));
        $matrice[$x+$y*LARGHEZZA] = '';
        if ($r==MIN_PUNTEGGIO) return $r;
        if ($r==MAX_PUNTEGGIO) $mosse_massime++;
        if ($controllo>$r) $controllo=$r;
    }
    if ($controllo==0) return $mosse_massime;
    return $controllo;
}

Si osservi che diversamente dal tris, il tempo necessario per esplorare l'intero albero min-max non è accettabile, quindi occorre prefissare un limite sulla profondità della visita.

Tagli Alfa-Beta
La metodologia dei tagli alba-bata consiste nel poter evitare di visionare tutti i possibili cammini dell’albero min-max, cioè di tagliare alcuni rami partendo da alcuni ragionamenti. Questi tagli permettono di poter aumentare il limite sulla profondità della visita.

Si osservi che il ragionamento dei tagli alfa-beta, consiste nel tagliare dei percorsi inutili.
Se ci troviamo nel livello max (funzione CercaMossaMax()), la variabile $alfa contiene il minimo cercato finora dalla visita di altri nodi dello stesso livello ($alfa è calcolato da CercaMossaMin() del nodo superiore), quindi se ai primi sotto-percorsi si arriva ad un punteggio maggiore o uguale ad $alfa, allora è inutile continuare a visitare gli altri sotto-percorsi, in quanto il livello min superiore, scarterà ugualmente questo nodo.
Se ci troviamo nel livello min (funzione CercaMossaMin()), la variabile $beta contiene il massimo cercato finora dalla visita di altri nodi dello stesso livello ($beta è calcolato da CercaMossaMax() del nodo superiore), quindi se ai primi sotto-percorsi si arriva ad un punteggio minore o uguale ad $beta, allora è inutile continuare a visitare gli altri sotto-percorsi, in quanto il livello max superiore, scarterà ugualmente questo nodo.

Scarica documento e sorgenti

(235 Kb)