Giochi in PHP: Filetto (Tris)

In questo paragrafo verrà spiegato come implementare un programma che permette di far giocare il computer al gioco del filetto. Questo gioco è noto ai bambini in quanto molto semplice, ed è quindi l'ideale per introdurre la metodologia ricorsiva del min-max. Questa metodologia sia basa su un semplice presupposto: l'utente A cerca la mossa che gli porta il punteggio massimo, e nella mossa successiva l'avversario B cercherà la sua mossa migliore, che corrisponderà al punteggio minimo di A. Per spiegare questo algoritmo si procederà per esempi, dapprima si implementerà un algoritmo stupido con soluzioni random, quindi si procederà con vari affinamenti fino ad arrivare ad ottenere l'algoritmo di ricerca definivo.

Consideriamo le variabili contenenti i dati dello schema del gioco:

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

0	1	2

3	4	5

6	7	8

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 prima funzione che andremo ad implementare è quella relativa al controllo del tris: ovvero la funziona verifica se l'utente o il computer è riuscito a comporre una sequenza di tre elementi successivi, disposti in verticale, orizzontale o in diagonale. L'implementazione è piuttosto semplice in quanto si tratta di verificare questa sequenza in tutti i possibili modi.

return 0;
}

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

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) echo "<br><br>";
?>
<script>
function Muovi(td, n)
{
    td.innerHTML='<?=UTENTE?>';
    document.tris.elements[n].value='<?=UTENTE?>';
    document.tris.submit();
}
</script>
<form name="tris" action ="<?php echo $_SERVER['PHP_SELF']; ?>" method="post">
<?php
$n=0;
for ($i=0; $i<9; $i++)
{
    echo "<input type=\"hidden\" name=\"matrice[$n]\" value=\"$matrice[$n]\">";
    $n++;
}
?>
<table border="0" cellpadding="0" cellspacing="0">
<?php
for ($i=0; $i<3; $i++)
{
    if ($i>0) 
    {
          ?><tr><td height="1" colspan="5" bgcolor="#aaaaaa"></td></tr><?php 
    }
    $n1 = $i*3;
    $n2 = $i*3+1;
    $n3 = $i*3+2;
    
    $m1 = $matrice[$n1];
    $m2 = $matrice[$n2];
    $m3 = $matrice[$n3];
    
    $td1 = '';
    $td2 = '';
    $td3 = '';
    
    if (!$m1) 
    {
        $m1="&nbsp;"; 
        $td1 = "style=\"cursor:hand\" onClick=\"javascript:Muovi($n1);\" "; 
    }
    if (!$m2) 
    {
        $m2="&nbsp;";
        $td2 = "style=\"cursor:hand\" onClick=\"javascript:Muovi($n2);\" ";
    }
    if (!$m3) 
    {
        $m3="&nbsp;";
        $td3 = "style=\"cursor:hand\" onClick=\"javascript:Muovi($n3);\" ";
    }
?>
<tr>
    <td <?=$td1?> width="30" align="center"><?=$m1?></td>
    <td width="1" bgcolor="#aaaaaa"></td>
    <td <?=$td2?> width="30" align="center"><?=$m2?></td>
    <td width="1" bgcolor="#aaaaaa"></td>
    <td <?=$td3?> width="30" align="center"><?=$m3?></td>
</tr>
<?php } ?>
</table>
<?php 
if (!$partita) 
{
 ?><br><input type="submit" name="iniziatu" value="Inizia Tu"><?php 
} 
?>
</form>

Si osservi che quando l'utente seleziona la casella, la funzione javascript Muovi() visualizza la mossa dell'utente prima di ricaricare la pagina; in questo modo l'utente vede subito l'esecuzione della sua mossa, ed aspetta per vedere la mossa del computer (invece di aspettare per vedere la sua mossa e contemporaneamente quella del computer).

Quando è il computer ad iniziare, è possibile far scegliere la sua prima mossa in modo random tra una serie di posti ritenuti buoni. Le caselle evidenziate (in grassetto e sottolineato) indicano quali siano questi posti.

0	1	2

3	4	5

6	7	8

Vediamo il codice

Infine vediamo il controllo del gioco

<?php
//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 ('MAX_PUNTEGGIO', 100);
define ('MIN_PUNTEGGIO', -100);

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

//funzioni utili del gioco

function stampa_tris(&$matrice)
{
………………
}

function verifica_tris(&$matrice)
{
………………
}

//funzioni di ricerca della mossa

function CercaMossa(&$matrice)
{
………………
}

//controllo del gioco

if ( ($matrice) || ($iniziatu) )
{
    $r=verifica_tris($matrice);
    if ($r<0)
    {
        stampa_tris($matrice);
        echo "<br>Hai Vinto!";
        exit();
    }
    if ($iniziatu)
    {
        $posti_liberi=array(0, 2, 4, 6, 8);    
        $k=array_rand($posti_liberi);
        $elemento=$posti_liberi[$k];
    }
    else $elemento=CercaMossa($matrice);
    $matrice[$elemento]=COMPUTER;

$r=verifica_tris($matrice);
    if ($r==MAX_PUNTEGGIO)
    {
        $time_end = getmicrotime(); 
        $time = $time_end - $time_start;
         
        echo "Tempo di esecuzione: ".number_format($time, 4, ',', '.');
        stampa_tris($matrice);
        echo "<br>Ho Vinto!";
        exit();
    }

$time_end = getmicrotime(); 
    $time = $time_end - $time_start;
     
    echo "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 detto precedentemente si tratta di una ricerca stupida.

Si osservi che viene cercata una mossa valida random tra tutti i posti liberi.

Mossa Max
La successiva funzione implementa la ricerca di un tris, anche qui si tratta di una ricerca stupida.

Si osservi che se non trova un tris, restituisce una mossa valida random.

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

S osservi che la natura semplice del gioco, permetta l'esplorazione di tutte le possibili soluzioni in tempi ragionevoli.

Min-Max migliore
Finora le funzioni di ricerca hanno restituito un valore tra le tre possibili:

0: Possibile patta

MAX_PUNTEGGIO: Vince il computer

MIN_PUNTEGGIO: vince l'utente

In pratica quando il computer gioca, se non riesce a innescare una "trappola", gioca a caso senza neanche tentare un approccio di tris; questo perché parte dal presupposto che l'utente sia comunque in grado di bloccarlo. Quello che invece il computer dovrebbe fare, è provarci ugualmente.
Per fare questo le funzioni di ricerca dovrebbero restituire un valore tra le quattro possibili:

0: Possibile patta

1: Il computer potrebbe vincere

MAX_PUNTEGGIO: Vince il computer

MIN_PUNTEGGIO: vince l'utente

Nella funzione CercaMossaMin(), viene valutata anche la possibilità da parte dell'utente di commettere un errore quindi in questo caso di tornare il valore '1' al posto del valore '0'. Nella funzione CercaMossaMax() viene calcolato il massimo punteggio. Nella funzione CercaMossa in caso non ci siano mosse vincenti, viene data la possibilità di selezionare una mossa random tra quelle che hanno una qualche probabilità di vittoria (qualora l'utente sbagli).

Di seguito le modifiche alle funzioni di ricerca.

Scarica documento e sorgenti

(235 Kb)