Engine.java
Codice
import java.util.*;
/**
* Classe Engine per la gestione dell'intelligenza artificiale.
* Tale classe e' stata realizzata basandosi sulla strategia di MiniMax con alpha-beta pruning e ricerca di quiescenza
*/
public class Engine {
// I) Definizione dei campi della classe: costanti che indicano il peso dei pezzi del gioco
final static int INFINITY = Integer.MAX_VALUE; // valore di infinito
final static int CHECKER = 100; //one checker worth 100 // peso di una pedina
final static int POS=1; //one position along the -j worth 1 // peso di una posizione
final static int KING=200; //a king's worth // peso di una dama
final static int EDGE=10; // effect of king being on the edge // penalita' per i bordi
final static int RANDOM_WEIGHT=10; // weight factor // peso random
private static final int tableWeight[] = { // tabella con i pesi variabili delle posizioni
4, 4, 4, 4,
4, 3, 3, 3,
3, 2, 2, 4,
4, 2, 1, 3,
3, 1, 2, 4,
4, 2, 2, 3,
3, 3, 3, 4,
4, 4, 4, 4};
// II) Definizioni delle funzioni di valutazione
// A) Funzione di valutazione
Indice
// A.1) EvalSpettacolo:
/**
* Funzione di valutazione EvalSpettacolo:
* realizza la teoria secondo la quale, la board viene divisa in quattro quadranti e ognuno ha, rispetto ad un
* giocatore una certa importanza.
* @param position la board di partenza
* @param player il colore del giocatore del turno
* @return ritorna il valore della valutazione della configurazione della board
*/
public static int EvalSpettacolo(int[][] position, int player){ //Valuto dal punto di vista del NERO
int score=0; // azzerro la variabile ove salvare la valutazione
int numeroPedine=0; // variabile ove salvare il numero di pedine
boolean damaTrovata=false; // flag per impostare la presenza di almeno una dama
boolean pedinaTrovata=false; // flag per impostare la presenza di una pedina
final int LIMITE_PEDINE = 18; // limite massimo di pedine
final int PESO_PEDINA = 100; // peso di una pedina
final int PESO_DAMA = 200; // peso della dama
final int PESO_AVERE_MOSSA = 20; // peso di avere la mossa
final int PESO_RANDOM = 10; // peso random
//controllo in che fase di gioco siamo
for (int i=0; i<8 && !damaTrovata; i++)
for (int j=0; j<8 && !damaTrovata; j++){
if(position[i][j] != Checkers.EMPTY)
numeroPedine++;
if(position[i][j] == Checkers.BKING || position[i][j] == Checkers.WKING)
damaTrovata=true;
}
// - FASE INIZIALE
if(!damaTrovata || numeroPedine>LIMITE_PEDINE){
// scorro la board
for (int i=0; i<8; i++)
for (int j=0; j<8; j++){
if (position[i][j] == Checkers.BLACK){
if((7-i)<=5) //parte del NERO
score += PESO_PEDINA*(8-j)*(8-j)*(7-i)*(7-i);
else
score += PESO_PEDINA*j*j*(7-i)*(7-i);
}
if (position[i][j] == Checkers.WHITE){
if(i<=3) //parte del BIANCO
score -= PESO_PEDINA*(8-j)*(8-j)*i*i;
else
score -= PESO_PEDINA*j*j*i*i;
}
}
//FASE FINALE
}else{
int r=0, c=0;
int numeroCoppiePari=0;
for (int i=0; i<8; i++)
for (int j=0; j<8; j++){
if(position[i][j] != Checkers.EMPTY){
if(!pedinaTrovata){
r=i;
c=j;
pedinaTrovata=true;
}
else{
pedinaTrovata=false;
if(Math.max(Math.abs(r-i),Math.abs(c-j))%2 == 0){ //distanza coppia e' pari
numeroCoppiePari++;
}
}
if (position[i][j] == Checkers.BLACK){
score+=PESO_PEDINA*(7-i)*(7-i);
}
else if (position[i][j] == Checkers.WHITE){
score-=PESO_PEDINA*i*i;
}
else if (position[i][j] == Checkers.BKING){
score+=PESO_DAMA;
}
else if (position[i][j] == Checkers.WKING){
score-=PESO_DAMA;
}
}
}
if((numeroCoppiePari % 2) ==1) //chi muove e' privilegiato
if(player == Checkers.BLACK) //player DEVE essere WHITE o BLACK
score += PESO_AVERE_MOSSA;
else
score -= PESO_AVERE_MOSSA;
}
score += (int)(Math.random() * PESO_RANDOM);
return score;
}
Indice
// A.2) Evaluation2Compl:
/**
* Metodo ausiliario di Evaluation2Compl.
*/
public static int valutaPos(int i, int j, int[][] position){
int value;
if (position[i][j] == Checkers.WHITE )
if (i == 1)
value = 7;
else
value = 5;
else if (position[i][j] == Checkers.BLACK)
if (i == 6)
value = 7;
else
value = 5;
else // dama
value = 10;
return value*tableWeight[(i/2)*4+j/2]*i*i;
}
Indice
/**
* Funzione di valutazione Evaluation2Compl:
*
* @param position la board di partenza
* @return ritorna il valore della valutazione della configurazione della board
*/
public static int Evaluation2Compl(int[][] position){
final int CHECKER=150;
final int POS=1;
final int KING=300;
int score=0;
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
{
if (position[i][j] == Checkers.WHITE)
{
score-=valutaPos(i, j, position);
}
else if (position[i][j] == Checkers.BLACK)
{
score+=valutaPos(i, j, position);
}
else if (position[i][j] == Checkers.WKING){
score-=valutaPos(i, j, position);
}
else if (position[i][j] == Checkers.BKING){
score+=valutaPos(i, j, position);
}
}//end for
score += (int)(Math.random() * RANDOM_WEIGHT);
return score;
}
Indice
// A.3) Evaluation2
/**
* Funzione di valutazione Evaluation2:
* Si comporta come la funzione Prima, ma in questo caso le dame vengono favorite affinche' occupino posizioni centrali della damiera
* @param position la board di partenza
* @return ritorna il valore della valutazione della configurazione della board
*/
public static int Evaluation2(int[][] position){ //Valuto dal punto di vista del NERO
final int CHECKER=150; // peso di una pedina
final int POS=1; // valore di una posizione
final int KING=300; // pesi di una dama
int score=0; // azzerro variabile ove salvare il punteggio
// scorro l'intera board e calcolo i valori delle pedine e delle posizioni
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
{
if (position[i][j] == Checkers.WHITE)
{
score-=CHECKER;
score-=POS*i*i;
score-=supportoWHITE(position,i,j);
}
else if (position[i][j] == Checkers.BLACK)
{
score+=CHECKER;
score+=POS*(7-i)*(7-i);
score+=supportoBLACK(position,i,j);
}
else if (position[i][j] == Checkers.WKING){
score-=KING;
score-=(4-Math.abs(3.5-i))*(4-Math.abs(3.5-i))+(4-Math.abs(3.5-j))*(4-Math.abs(3.5-j));
}
else if (position[i][j] == Checkers.BKING){
score+=KING;
score+=(4-Math.abs(3.5-i))*(4-Math.abs(3.5-i))+(4-Math.abs(3.5-j))*(4-Math.abs(3.5-j));
}
}//end for
score += (int)(Math.random() * RANDOM_WEIGHT);
return score;
}
Indice
// A.4) EvalPrima
/**
* Metodo ausiliario EvalPrima
*/
public static int supportoBLACK(int[][] position, int i, int j){
int score =0;
int tmp=0;
if(!Move.inRange(i,j) || (( Move.inRange(i+1,j-1) && position[i+1][j-1] != Checkers.BLACK ) && (Move.inRange(i+1,j+1) && position[i+1][j+1] != Checkers.BLACK)))
if(i==8)
return 0;
else
return -1;
else{
tmp=supportoBLACK(position, i+1, j-1);
if(tmp!=-1)
score+=tmp+2;
tmp=supportoBLACK(position, i+1, j+1);
if(tmp!=-1)
score+=tmp+2;
}
return score;
}
Indice
/**
* Metodo ausiliario EvalPrima
*/
public static int supportoWHITE(int[][] position, int i, int j){
int score =0;
int tmp=0;
if(!Move.inRange(i,j) || (( Move.inRange(i-1,j-1) && position[i-1][j-1] != Checkers.WHITE ) && (Move.inRange(i-1,j+1) && position[i-1][j+1] != Checkers.WHITE)))
if(i==-1)
return 0;
else
return -1;
else{
tmp=supportoWHITE(position, i-1, j-1);
if(tmp!=-1)
score+=tmp+2;
tmp=supportoWHITE(position, i-1, j+1);
if(tmp!=-1)
score+=tmp+2;
}
return score;
}
Indice
/**
* Funzione di valutazione Prima.
* Sfrutta l'idea secondo la quale e' preferibile far avanzare i pezzi sulla damiera tenendoli ben compatti
* e ben saldati alla base. Per quanto riguarda le dame, le penalizza nel caso si muovano lungo i bordi della damiera.
* @param position la board virtuale con tutti i pezzi posizionati.
* @param player il giocatore che deve fare la mossa.
* @return ritorna la valutazione della board passata in input
*/
public static int EvalPrima(int[][] position, int player){
final int CHECKER=100; // peso di una pedina
final int POS=1; // valore di una posizione
final int KING=200; // peso di una dama
int score=0; // azzero la variabile ove salvare il punteggio
int[][] posKW=new int[12][2];
int[][] posKB=new int[12][2];
int nKW=0, nKB=0;
// scorro la board per valutarla
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
{
if (position[i][j] == Checkers.WHITE)
{
score-=CHECKER;
score-=POS*i*i;
score-=supportoWHITE(position,i,j);
}
else if (position[i][j] == Checkers.BLACK)
{
score+=CHECKER;
score+=POS*(7-i)*(7-i);
score+=supportoBLACK(position,i,j);
}
else if (position[i][j] == Checkers.WKING){
posKW[nKW][0]=i;
posKW[nKW][1]=j;
nKW++;
score-=KING;
if (i==0 || i==7)
score += EDGE;
if (j==0 || j==7)
score += EDGE;
}
else if (position[i][j] == Checkers.BKING){
posKB[nKB][0]=i;
posKB[nKB][1]=j;
nKB++;
score+=KING;
if (i==0 || i==7)
score -= EDGE;
if (j==0 || j==7)
score -= EDGE;
}
}//end for
// for(int i=0;iIndice
// A.6) EvalOriginale
/**
* Funzione di valutazione originale del codice.
* Attribuisce ad ogni pezzo un peso e alle pedine il peso in base alla distanza dalla base avversaria. Inoltre
* vengono penalizzate le dame se stanno sui bordi.
* @param position la board virtuale con tutti i pezzi posizionati.
* @return ritorna la valutazione della board passata in input
*/
public static int EvalOriginale(int[][] position) //originale
{
int score=0; // azzero il valore della variabile ove salvare il punteggio
// scorro la board
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
{
if (position[i][j] == Checkers.WHITE)
{
score-=CHECKER;
score-=POS*i*i;
}
else if (position[i][j] ==Checkers.WKING){
score-=KING;
if (i==0 || i==7)
score += EDGE;
if (j==0 || j==7)
score += EDGE;
}
else if (position[i][j] == Checkers.BKING){
score+=KING;
if (i==0 || i==7)
score -= EDGE;
if (j==0 || j==7)
score -= EDGE;
}
else if (position[i][j] == Checkers.BLACK)
{
score+=CHECKER;
score+=POS*(7-i)*(7-i);
}
}//end for
score += (int)(Math.random() * RANDOM_WEIGHT);
return score;
}//end Evaluation
Indice
// A.7) EvalOriginale
/**
* Funzione di valutazione che calcola solo il peso associato ad ogni pezzo e valuta la posizione delle pedine.
* @param position la board di partenza
* @return il valore della funzione di valutazione applicata alla configurazione di pedine presente nella board passata * in input.
*/
public static int EvalSoloPedine(int[][] position) //originale
{
int score=0; // inizializzazione della variabile per contare la valutazione
// ciclo che scorre l'intera board analizzando il contenuto di ogni casella della damiera.
// I valori dello score sono calcolati dal punto di vista del giocatore nero.
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
{
if (position[i][j] == Checkers.WHITE) // 1) se nella casella c'e' una pedina bianca
{
score-=CHECKER; // - si sottrae il peso di una pedina
score-=POS*i*i; // - si sottrae il valore della casella occupata dalla pedina
}
else if (position[i][j] ==Checkers.WKING){ // 2) se nella casella c'e' una dama bianca
score-=KING; // - si sottrae il peso di una dama
}
else if (position[i][j] == Checkers.BKING){ // 3) se nella casella c'e' una dama nera
score+=KING; // - si aggiunge il peso di una dama
}
else if (position[i][j] == Checkers.BLACK) // 4) se nella casella c'e' una pedina nera
{
score+=CHECKER; // - si aggiunge il peso di una pedina
score+=POS*(7-i)*(7-i); // - si aggiunge il valore della casella occupata dalla pedina
}
}//end for
score += (int)(Math.random() * RANDOM_WEIGHT); // si aggiunge il peso random alla fine
return score;
}//end Evaluation
Indice
// B) Metodo che ritorna il colore dell'avversario
/**
* Metodo che dato ritorna il colore dell'avversario del giocatore passato in input
* @param turn il valore del giocatore che sta giocando
* @return ritorna il valore dell'avversario del giocatore in input
*/
static int opponent(int turn){
return turn==Checkers.BLACK ? Checkers.WHITE : Checkers.BLACK;
}
/*
static int which_turn(int turn) {
return Move.color(turn)==Checkers.BLACK ? -INFINITY : INFINITY;
}
*/
Indice
// C) Metodo che realizza l'Engine del modulo di intelligenza artificiale
/**
* Metodo che realizza la ricerca MiniMax con analisi di alpha-beta pruning e ricerca di quiescenza
* @param board la damiera con la configurazione corrente
* @param depth la profondita' raggiunta all'interno dell'albero
* @param maxDepth la massima profondita' che si puo' raggiungere nell'albero di ricerca
* @param theMove la mossa che si vuole eseguire
* @param player il giocatore che sta giocando
* @param counter
* @param BFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore nero
* @param WFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore bianco
* @param scacchiera un oggetto di tipo board
* @param ritorna il valore della funzione di valutazione
*/
public static int MiniMax(int[][] board, int depth, int maxDepth, Vector theMove, int player, int[] counter, int BFunction, int WFunction, Board scacchiera)
{
// Move.trasponiBoard(board);
int firstTurn=player; // variabile ove salvare il giocatore che deve eseguire la mossa
//System.out.println("GIOCA PLAYER:"+player);
int[][] newBoard= new int [8][8]; // variabile ausiliaria per la board
int score; // variabile per il punteggio
Vector> moves=new Vector>();// variabile ove salvare le mosse possibili
int bestMax=-INFINITY; // setto il valore di alpha
int pippo=bestMax;
int bestMin=INFINITY; // setto il valore di beta
moves=Move.generate_moves(board,player); // genero le mosse
if(moves.size()>1) //non ho una sola mossa obbligata
for(int ind=0;ind=pippo){
pippo=score;
theMove.clear();
// salvo la mossa
for(int h=0;h=bestMin) // valuto il pruning
return pippo;
bestMax=Math.max(bestMax, pippo);
}
// se c'e' una sola mossa la salvo
else if(moves.size() == 1){
theMove.clear();
for(int h=0;h= 1)
// System.out.println("MOSSA MINIMAX: ("+theMove.elementAt(0)[0]+","+theMove.elementAt(0)[1]+")->("+theMove.elementAt(1)[0]+","+theMove.elementAt(1)[1]+")");
// else
// System.out.println("MOSSA MINIMAX: NESSUNA MOSSA");
return pippo;
}
Indice
// C.1) Funzione ausiliaria di MiniMax per la ricerca di quiescenza
/**
* Metodo che permette di effettuare la ricerca di quiescenza
* @param board la damiera con la configurazione corrente
* @param player il giocatore che sta giocando
* @param moves vettore con le mosse
* @return ritorna vero nel caso in cui lo stato sia queiscente, falso altrimenti
*/
static boolean quiescent(int[][] board, int player, Vector> moves){
//Vector> moves=new Vector>();
moves=Move.generate_moves(board,player);
if(moves.size()==0){ //non ci sono mosse possibili
//System.out.println("QUIESCENTE. PLAYER: "+player);
return true;
}
else if(Math.abs(moves.elementAt(0).elementAt(0)[0]-moves.elementAt(0).elementAt(1)[0])==1){ //non ci sono catture
//System.out.println("QUIESCENTE. PLAYER: "+player);
return true;
}
//System.out.println("NON QUIESCENTE. PLAYER: "+player);
return false;
//return true;
}
Indice
// C.2) Funzione ausiliaria di MiniMax: maximize
/**
* Metodo che realizza il metodo maxValue
* @param firstTurn variabile nella quale viene salvato il giocatore del primo turno
* @param board la damiera con la configurazione corrente
* @param depth la profondita' raggiunta all'interno dell'albero
* @param maxDepth la massima profondita' che si puo' raggiungere nell'albero di ricerca
* @param player il giocatore che sta giocando
* @param counter
* @param bestMin il valore di beta
* @param bestMax il valore di alpha
* @param BFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore nero
* @param WFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore bianco
* @param scacchiera un oggetto di tipo board
* @param ritorna il valore della funzione di valutazione
*/
static int maximize(int firstTurn, int[][] board, int depth, int maxDepth, int player, int[] counter, int bestMin, int bestMax, int BFunction, int WFunction, Board scacchiera)
{
// System.out.println("maximize depth:"+depth);
int[][] newBoard= new int [8][8];
int score;
Vector> moves=new Vector>();
moves=null;
if(depth>=maxDepth && quiescent(board, player, moves))
// se si e' raggiunta la condizione di terminazione e la configurazione e' stabile, applico la funzione di valutazione selezionata
if(firstTurn==Checkers.WHITE)
switch(WFunction){
case 0:return -EvalOriginale(board);
case 1:return -EvalPrima(board, firstTurn);
case 2:return -Evaluation2(board);
case 3: return -EvalSpettacolo(board, Move.color(player));
case 4: return -EvalSoloPedine(board);
case 5: return -Evaluation2Compl(board);
default: return -EvalOriginale(board);
}
else
switch(BFunction){
case 0:return EvalOriginale(board);
case 1:return EvalPrima(board, firstTurn);
case 2:return Evaluation2(board);
case 3: return EvalSpettacolo(board, Move.color(player));
case 4: return EvalSoloPedine(board);
case 5: return Evaluation2Compl(board);
default: return EvalOriginale(board);
}
else { //branch
score=-INFINITY;
if(moves==null)
moves=Move.generate_moves(board,player);
for(int ind=0;ind=bestMin)
return score;
bestMax=Math.max(bestMax, score);
}
return score;
}
} //end maximize
Indice
// C.3) Funzione ausiliaria di MiniMax: minimize
/**
* Metodo che realizza il metodo minValue
* @param firstTurn variabile nella quale viene salvato il giocatore del primo turno
* @param board la damiera con la configurazione corrente
* @param depth la profondita' raggiunta all'interno dell'albero
* @param maxDepth la massima profondita' che si puo' raggiungere nell'albero di ricerca
* @param player il giocatore che sta giocando
* @param counter
* @param bestMin il valore di beta
* @param bestMax il valore di alpha
* @param BFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore nero
* @param WFunction il tipo di funzione di valutazione che e' stata selezionata per il giocatore bianco
* @param scacchiera un oggetto di tipo board
* @param ritorna il valore della funzione di valutazione
*/
static int minimize(int firstTurn, int[][] board, int depth, int maxDepth, int player, int[] counter, int bestMin, int bestMax, int BFunction, int WFunction, Board scacchiera)
{
// System.out.println("minimize depth:"+depth);
int[][] newBoard= new int [8][8];
int score;
Vector> moves=new Vector>();
moves=null;
if(depth>=maxDepth && quiescent(board, player, moves))
if(firstTurn==Checkers.WHITE)
switch(WFunction){
case 0:return -EvalOriginale(board);
case 1:return -EvalPrima(board, firstTurn);
case 2:return -Evaluation2(board);
case 3: return -EvalSpettacolo(board, Move.color(player));
case 4: return -EvalSoloPedine(board);
case 5: return -Evaluation2Compl(board);
default: return -EvalOriginale(board);
}
else
switch(BFunction){
case 0:return EvalOriginale(board);
case 1:return EvalPrima(board, firstTurn);
case 2:return Evaluation2(board);
case 3: return EvalSpettacolo(board, Move.color(player));
case 4: return EvalSoloPedine(board);
case 5: return Evaluation2Compl(board);
default: return EvalOriginale(board);
}
else { //branch
score=INFINITY;
if(moves==null)
moves=Move.generate_moves(board,player);
for(int ind=0;indIndice
// D) Metodi ausiliari
/**
* Metodo che realizza una copia profonda della board originale passata in input
* @param board la board passata in input
* @return ritorna la copia della board passata in input
*/
int[][] copy_board(int[][] board){
int[][] copy = new int[8][8];
for (int i=0; i<8; i++)
for (int j=0; j<8; j++)
copy[i][j]=board[i][j];
return copy;
}//end copy_board
/*
static boolean better(int the_score, int best, int turn){
if (turn==Checkers.BLACK )
return the_score>best;
return the_score
|
