Prima di proseguire...
Potrebbe interessarti la nostra collezione di esercizi C risolti?
Vi siete mai chiesti come creare un algoritmo per il tris? sapete che cos’è il minimax? Avete mai sentito parlare della teoria dei giochi?
Bene allora siete nel posto giusto, oggi infatti vedremo come creare in javascript (ma è possibile usare qualsiasi altro linguaggio) un gioco di tris completo con intelligenza artificiale, il tutto usando l’algoritmo minimax.
Teoria:
Secondo la teoria dei giochi qualsiasi gioco a stati finiti è risolvibile con l’uso di un algoritmo, in questo caso noi utilizzeremo il minimax, un algoritmo inventato da von Neumann.
Questo algoritmo consiste nel valutare tutte le mosse possibili e assegnare ad ognuna di esse un punteggio, dove le mosse che portano alla vincita dell’avversario hanno un punteggio che tende a meno infinito, quelle che portano alla nostra vincita(alla vincita del computer in questo caso) hanno punteggio più infinito, tutte le altre mosse hanno un punteggio in base alle loro conseguenze.
Algoritmo:
Il nostro obbiettivo sarà quindi quello di implementare l’algoritmo che troviamo su wikipedia. Adattandolo ovviamente ai linguaggi di programmazione moderni e al gioco del tris: l’infinito diventerà un numero intero molto alto, le diverse mosse del tris avranno un punteggio in base alle loro conseguenze nel gioco e il ciclo interno sarà adattato al nostro tris.
Dato che l’algoritmo minimax è molto generale dobbiamo, nella funzione che controlla il movimento del computer, valutare ogni singola mossa possibile con il minimax e scegliere quella con il punteggio maggiore.
Ovviamente oltre all’intelligenza artificiale dobbiamo anche implementare un semplice algoritmo che gestisca il tris, verificando chi vince, anche se con l’algoritmo minimax il computer vincerà o al massimo pareggerà sempre.
Implementazione:
Per semplificare il codice ho deciso di creare una classe chiamata tris, in questo modo basterà creare le 9 celle di gioco e creare un istanza della classe con gli appositi parametri.
Codice:
Non mi soffermerò nella spiegazione della classe, la quale risulta abbastanza semplice una volta capito l’algoritmo minimax, il quale è implementato nel metodo minimax.
Utilizzare la classe è alquanto semplice:
- Per utilizzare questa classe basta creare 9 campi button e numerarli da 0 a 8, identificandoli con un prefisso definito.
- In seguito basterà creare un’istanza della classe tris passando come parametro il prefisso dei button, ad esempio: “var tris = new Tris(“bot”);“.
- Infine dovremo in ogni button richiamare il metodo premuto passando come parametro il button stesso: “onclick=”tris.premuto(this)”“.
Nell’esempio che segue ho inserito oltre alla classe la parte completa e funzionante in HTML appena descritta, in modo da poter provare fin da subito il tutto.
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>tris minimax</title>
<script language="javascript1.5" type="text/javascript">
function Tris(prefix){
this.prefix = prefix;
this.bottoni = new Array(9);
}
Tris.prototype.premuto = function(bott){
var fin;
//mosa giocatore
this.bottoni[bott.id.substr(3,1)] = true;
bott.value = "O";
bott.disabled = true;
if(fin = this.controlla()){
this.fine(fin);
return ;
}
//mossa pc
this.computer();
if(fin = this.controlla()){
this.fine(fin);
return ;
}
}
Tris.prototype.controlla = function(){
var i;
//orizzontale
for(i=0;i<9;i+=3)
if(this.bottoni[i] != undefined && this.bottoni[i] == this.bottoni[i+1] && this.bottoni[i] == this.bottoni[i+2])
return this.bottoni[i]?1:2;
//verticale
for(i=0;i<3;i++)
if(this.bottoni[i] != undefined && this.bottoni[i] == this.bottoni[i+3] && this.bottoni[i] == this.bottoni[i+6])
return this.bottoni[i]?1:2;
//diagonale
if(this.bottoni[0] != undefined && this.bottoni[0] == this.bottoni[4] && this.bottoni[0] == this.bottoni[8])
return this.bottoni[0]?1:2;
if(this.bottoni[2] != undefined && this.bottoni[2] == this.bottoni[4] && this.bottoni[2] == this.bottoni[6])
return this.bottoni[2]?1:2;
//partita non ancora conclusa
for(i=0;i<9;i++)
if(this.bottoni[i] == undefined)
return false;
//pareggio
return 3;
}
Tris.prototype.computer = function (){
var i
var max=-100000,mi=4,t;
for(i=0;i<9;i++)
if(this.bottoni[i]==undefined)
{
this.bottoni[i]=false;
t=this.minimax(true, 20);
if(t>max)
{
max=t;
mi=i;
}
this.bottoni[i]=undefined;
}
this.bottoni[mi]=false;
document.getElementById(this.prefix+mi).value = "X";
document.getElementById(this.prefix+mi).disabled = true;
}
Tris.prototype.minimax = function(gioc, profondita){
var i, res, tmp;
//punteggi mosse
if(this.controlla()==2)
return (99980+profondita);
else if(this.controlla()==1)
return (-99980-profondita);
else if(this.controlla()==3 || profondita==0)
return 0;
//tocca all'aversario
if(gioc){
res = 100000;
for(i=0;i<9;i++)
if(this.bottoni[i]==undefined)
{
this.bottoni[i]=true;
res = Math.min(res, this.minimax(false,profondita-1));
this.bottoni[i]=undefined;
}
//tocca a noi
}else{
res = -100000;
for(i=0;i<9;i++)
if(this.bottoni[i]==undefined)
{
this.bottoni[i]=false;
res = Math.max(res, this.minimax(true,profondita-1));
this.bottoni[i]=undefined;
}
}
return res;
}
Tris.prototype.fine = function(mod){
switch(mod){
case 1:
alert("hai vinto");
break;
case 2:
alert("hai perso");
break;
case 3:
alert("pareggio");
break;
}
this.azzera();
}
Tris.prototype.azzera = function(){
for(i=0;i<9;i++){
this.bottoni[i] = undefined;
document.getElementById(this.prefix+i).value = " ";
document.getElementById(this.prefix+i).disabled = false;
}
}
var tris = new Tris("bot");
</script>
</head>
<body onload="tris.azzera()">
<table>
<tr>
<td>
<input type="button" id="bot0" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot1" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot2" value=" " onclick="tris.premuto(this)" />
</td>
</tr>
<tr>
<td>
<input type="button" id="bot3" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot4" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot5" value=" " onclick="tris.premuto(this)" />
</td>
</tr>
<tr>
<td>
<input type="button" id="bot6" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot7" value=" " onclick="tris.premuto(this)" />
</td>
<td>
<input type="button" id="bot8" value=" " onclick="tris.premuto(this)" />
</td>
</tr>
</table>
</body>
</html>
Tris con minimax in javascript by cardinale claudio is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.