Utility
Home Messaggi odierni FAQ Ricerca avanzata Lo staff del forum Regolamento Utenti Archivio
Visualizzazione dei risultati da 1 a 1 su 1
  1. 20-09-2011, 18:10 #1
    Blackkiss7
    Blackkiss7 non è in linea
    Utente di HTML.it
    Registrato dal
    Sep 2011
    Messaggi
    1

    problema minimax per la dama

    Questo codice di IA è per la dama.
    ci sono dei casi in cui il gioco va in ricorsione infinita, perchè?
    da una prima stima l'errore sembra essere nel metodo minimax. AIUTATEMI...

    codice:
    public class Engine {

final static int INFINITY = Integer.MAX_VALUE;
final static int PESO_PEDINA = 100;
final static int PESO_DAMA = 200;

public static ArrayList<Mossa> miniMax (int[][] board, int player, ArrayList<ArrayList<Mossa>> sequenceList, int depth, int maxDepth) {
int score;
int bestMax = -INFINITY;
int bestMin = INFINITY;
int tempScore = bestMax;
ArrayList<Mossa> bestSequence = new ArrayList<Mossa>();

if (sequenceList.size() > 1) {
for (ArrayList<Mossa> sequence : sequenceList) {
int[][] simulation = simulate(sequence,board);
score = minimize(simulation, player, depth+1, maxDepth, opponent(player), bestMax, bestMin);
if (score >= tempScore) {
tempScore = score;
bestSequence = sequence;
}
//if (tempScore >= bestMin) {
//}
bestMax = Math.max(bestMax, tempScore);
}
}
else {
bestSequence = sequenceList.get(0);
}
return bestSequence;
}

public static boolean isQuiescent (int[][] board, int player) {
Dama testDama = new Dama();
testDama.setScacchiera(board);
testDama.generaMosseValideNew(player);
if (testDama.listaSequenze.size() == 0)
return true;
else {
for (ArrayList<Mossa> lista : testDama.listaSequenze) {
for (Mossa m : lista) {
if (m.isJump())
return false;
}
}
}
return true;
}

public static int maximize (int[][] board, int player, int depth, int opponent, int maxDepth, int bestMax, int bestMin) {
int score;
if (depth >= maxDepth && isQuiescent(board, player)) {
return evaluate(board, player);
}
else {
score = -INFINITY;
Dama testDama = new Dama();
int[][] boardCopy = Dama.copyBoard(board);
testDama.setScacchiera(boardCopy);
testDama.generaMosseValideNew(player);
for (ArrayList<Mossa> sequence : testDama.listaSequenze) {
int[][] simulation = simulate(sequence,board);
score = Math.max(score, minimize(simulation, player, depth+1, maxDepth, opponent(player), bestMax, bestMin));
if (score >= bestMin)
return score;
bestMax = Math.max(bestMax, score);
}
return score;
}
}

public static int minimize (int[][] board, int player, int depth, int opponent, int maxDepth, int bestMax, int bestMin) {
int score;
if (depth >= maxDepth && isQuiescent(board, player)) {
return evaluate(board, player);
}
else {
score = INFINITY;
Dama testDama = new Dama();
int[][] boardCopy = Dama.copyBoard(board);
testDama.setScacchiera(boardCopy);
testDama.generaMosseValideNew(player);
for (ArrayList<Mossa> sequence : testDama.listaSequenze) {
int[][] simulation = simulate(sequence,board);
score = Math.min(score, maximize(simulation, player, depth+1, maxDepth, opponent(player), bestMax, bestMin));
if (score <= bestMax)
return score;
bestMin = Math.min(bestMin, score);
}
return score;
}
}

public static int opponent (int player) {
if (player == 1)
return 2;
else
return 1;
}

public static int evaluate (int[][] board, int player) {
int score = 0;
for (int i=0; i<8; i++) {
for (int j=0; j<8; j++) {
if (board[i][j] == Dama.BIANCO) {
score -= PESO_PEDINA;
score -= i*i;
score -= evalWhite(board, i, j);
}
else if (board[i][j] == Dama.NERO) {
score += PESO_PEDINA;
score += (7-i)*(7-i);
score -= evalBlack(board, i, j);
}
}
}
return score;
}

public static int evalBlack (int[][] board, int i, int j) {
int score = 0;
int temp;

if (!isValidPosition(i,j) || ( (isValidPosition(i-1,j-1) && board[i-1][j-1]!=Dama.NERO) && (isValidPosition(i-1,j+1) && board[i-1][j+1]!=Dama.NERO)))
if(i==8)
return 0;
else
return -1;
else {
temp = evalBlack(board, i-1, j-1);
if(temp != -1)
score += temp+2;
temp = evalBlack(board, i-1, j+1);
if(temp != -1)
score += temp+2;
}
return score;
}

public static int evalWhite (int[][] board, int i, int j) {
int score = 0;
int temp;

if (!isValidPosition(i,j) || ( (isValidPosition(i+1,j-1) && board[i+1][j-1]!=Dama.NERO) && (isValidPosition(i+1,j+1) && board[i+1][j+1]!=Dama.NERO)))
if(i==8)
return 0;
else
return -1;
else {
temp = evalWhite(board, i+1, j-1);
if(temp != -1)
score += temp+2;
temp = evalWhite(board, i+1, j+1);
if(temp != -1)
score += temp+2;
}
return score;
}

public static boolean isValidPosition (int i, int j) {
if (i>-1 && i<8 && j>-1 && j<8)
return true;
return false;
}

public static int[][] simulate (ArrayList<Mossa> sequence, int[][] board) {
int[][] boardCopy = Dama.copyBoard(board);
Dama testDama = new Dama();
testDama.setScacchiera(boardCopy);
for (Mossa m : sequence) {
testDama.muoviPezzo(m);
}
return testDama.getScacchiera();
}
}

    codice:
    public class Dama {

private int[][] scacchiera;

ArrayList<ArrayList<Mossa>> listaSequenze;

public final static int VUOTO = 0;
public final static int BIANCO = 1;
public final static int NERO = 2;
public final static int DAMA_BIANCO = 3;
public final static int DAMA_NERO = 4;

public Dama(){
scacchiera = new int[8][8];
resetta();
}

public int[][] getScacchiera() {
return scacchiera;
}

public void setScacchiera(int[][] scacchiera) {
this.scacchiera = scacchiera;
}

public void resetta() {
for (int j=1;j<=7;j=j+2)
scacchiera[0][j] = BIANCO;
for (int j=0;j<=6;j=j+2)
scacchiera[1][j] = BIANCO;
for (int j=1;j<=7;j=j+2)
scacchiera[2][j] = BIANCO;
for (int j=0;j<=6;j=j+2)
scacchiera[3][j] = VUOTO;
for (int j=1;j<=7;j=j+2)
scacchiera[4][j] = VUOTO;
for (int j=0;j<=6;j=j+2)
scacchiera[5][j] = NERO;
for (int j=1;j<=7;j=j+2)
scacchiera[6][j] = NERO;
for (int j=0;j<=6;j=j+2)
scacchiera[7][j] = NERO;
}

public void svuota() {
for (int i=0;i<8;i++)
for (int j=0;j<8;j++)
scacchiera[i][j] = 0;
}

public void muoviPezzo(Mossa m){
int fromRiga = m.getFromRiga();
int fromColonna = m.getFromColonna();
int toRiga = m.getToRiga();
int toColonna = m.getToColonna();

scacchiera[toRiga][toColonna] = scacchiera[fromRiga][fromColonna];
scacchiera[fromRiga][fromColonna] = VUOTO;
if (fromRiga - toRiga == 2 || fromRiga - toRiga == -2)
scacchiera[(fromRiga+toRiga)/2][(fromColonna+toColonna)/2] = VUOTO; //Rimuove il pezzo mangiato
if (toRiga == 0 && scacchiera[toRiga][toColonna] == NERO)
scacchiera[toRiga][toColonna] = DAMA_NERO; //Diventa Dama
if (toRiga == 7 && scacchiera[toRiga][toColonna] == BIANCO)
scacchiera[toRiga][toColonna] = DAMA_BIANCO; //Diventa Dama
}

public ArrayList<Mossa> generaMosseValide(int colore) {
if (colore != BIANCO && colore!= NERO)
return null;
int dama;
if (colore == BIANCO)
dama = DAMA_BIANCO;
else
dama = DAMA_NERO;
ArrayList<Mossa> listaMosse = new ArrayList<Mossa>();
//Scorre tutta la scacchiera alla ricerca di pedine del giocatore
for (int riga = 0; riga < 8; riga++) {
for (int colonna = 0; colonna < 8; colonna++) {
if (scacchiera[riga][colonna] == colore || scacchiera[riga][colonna] == dama){
if (puoMangiare(colore,riga,colonna,riga+1,colonna+1,riga+2,c olonna+2))
listaMosse.add(new Mossa(riga,colonna,riga+2,colonna+2));
if (puoMangiare(colore,riga,colonna,riga-1,colonna+1,riga-2,colonna+2))
listaMosse.add(new Mossa(riga,colonna,riga-2,colonna+2));
if (puoMangiare(colore,riga,colonna,riga+1,colonna-1,riga+2,colonna-2))
listaMosse.add(new Mossa(riga,colonna,riga+2,colonna-2));
if (puoMangiare(colore,riga,colonna,riga-1,colonna-1,riga-2,colonna-2))
listaMosse.add(new Mossa(riga,colonna,riga-2,colonna-2));
}
}
}
//Se non si puo' mangiare nessun pezzo
if (listaMosse.size() == 0) {
for (int riga = 0; riga < 8; riga++) {
for (int colonna = 0; colonna < 8; colonna++) {
if (scacchiera[riga][colonna] == colore || scacchiera[riga][colonna] == dama){
if (puoMuoversi(colore,riga,colonna,riga+1,colonna+1))
listaMosse.add(new Mossa(riga,colonna,riga+1,colonna+1));
if (puoMuoversi(colore,riga,colonna,riga-1,colonna+1))
listaMosse.add(new Mossa(riga,colonna,riga-1,colonna+1));
if (puoMuoversi(colore,riga,colonna,riga+1,colonna-1))
listaMosse.add(new Mossa(riga,colonna,riga+1,colonna-1));
if (puoMuoversi(colore,riga,colonna,riga-1,colonna-1))
listaMosse.add(new Mossa(riga,colonna,riga-1,colonna-1));
}
}
}
}
//Se non esistono mosse possibili
if (listaMosse.size() == 0)
return null;
else
return listaMosse;
}

public void generaMosseValideNew (int colore) {
listaSequenze = new ArrayList<ArrayList<Mossa>>();
int dama;
if (colore == BIANCO)
dama = DAMA_BIANCO;
else
dama = DAMA_NERO;
for (int riga = 0; riga < 8; riga++) {
for (int colonna = 0; colonna < 8; colonna++) {
if (scacchiera[riga][colonna] == colore || scacchiera[riga][colonna] == dama){
ArrayList<Mossa> list = new ArrayList<Mossa>();
int[][] boardCopy = copyBoard(scacchiera);
getCaptureSequence(colore,riga,colonna,boardCopy,list);
}
}
}
if (listaSequenze.size() == 0) {
for (int riga = 0; riga < 8; riga++) {
for (int colonna = 0; colonna < 8; colonna++) {
if (scacchiera[riga][colonna] == colore || scacchiera[riga][colonna] == dama){
if (puoMuoversi(colore,riga,colonna,riga+1,colonna+1)) {
ArrayList<Mossa> temp = new ArrayList<Mossa>();
temp.add(new Mossa(riga,colonna,riga+1,colonna+1));
listaSequenze.add(temp);
}
if (puoMuoversi(colore,riga,colonna,riga-1,colonna+1)) {
ArrayList<Mossa> temp = new ArrayList<Mossa>();
temp.add(new Mossa(riga,colonna,riga-1,colonna+1));
listaSequenze.add(temp);
}
if (puoMuoversi(colore,riga,colonna,riga+1,colonna-1)) {
ArrayList<Mossa> temp = new ArrayList<Mossa>();
temp.add(new Mossa(riga,colonna,riga+1,colonna-1));
listaSequenze.add(temp);
}
if (puoMuoversi(colore,riga,colonna,riga-1,colonna-1)) {
ArrayList<Mossa> temp = new ArrayList<Mossa>();
temp.add(new Mossa(riga,colonna,riga-1,colonna-1));
listaSequenze.add(temp);
}
}
}
}
}
}

public ArrayList<Mossa> generaSaltiValidi(int colore,int riga,int colonna, int[][] scacchiera){
if (colore != BIANCO && colore!= NERO)
return null;
int dama;
if (colore == BIANCO)
dama = DAMA_BIANCO;
else
dama = DAMA_NERO;
ArrayList<Mossa> listaSalti = new ArrayList<Mossa>();
if (scacchiera[riga][colonna] == colore || scacchiera[riga][colonna] == dama){
if (puoMangiare(colore,riga,colonna,riga+1,colonna+1,riga+2,c olonna+2))
listaSalti.add(new Mossa(riga,colonna,riga+2,colonna+2));
if (puoMangiare(colore,riga,colonna,riga-1,colonna+1,riga-2,colonna+2))
listaSalti.add(new Mossa(riga,colonna,riga-2,colonna+2));
if (puoMangiare(colore,riga,colonna,riga+1,colonna-1,riga+2,colonna-2))
listaSalti.add(new Mossa(riga,colonna,riga+2,colonna-2));
if (puoMangiare(colore,riga,colonna,riga-1,colonna-1,riga-2,colonna-2))
listaSalti.add(new Mossa(riga,colonna,riga-2,colonna-2));
}
if (listaSalti.size() == 0)
return null;
else
return listaSalti;
}

private boolean puoMangiare(int colore,int riga1,int colonna1,int riga2,int colonna2,int riga3,int colonna3){
if (riga3 < 0 || riga3 > 7 || colonna3 < 0 || colonna3 > 7)
return false; //(riga3,colonna3) fuori dalla scacchiera
if (scacchiera[riga3][colonna3] != VUOTO)
return false; //(riga3,colonna3) contiene gi� un pezzo
if (colore == BIANCO) {
if (scacchiera[riga1][colonna1] == BIANCO && riga3 < riga1)
return false; //le pedine bianche possono muoversi solo dall'alto verso il basso
if (scacchiera[riga2][colonna2] != NERO && scacchiera[riga2][colonna2] != DAMA_NERO)
return false; //non c'e' un pezzo nero da mangiare
return true;
}
else {
if (scacchiera[riga1][colonna1] == NERO && riga3 > riga1)
return false; //le pedine nere possono muoversi solo dal basso verso l'alto
if (scacchiera[riga2][colonna2] != BIANCO && scacchiera[riga2][colonna2] != DAMA_BIANCO)
return false; //non c'e' un pezzo bianco da mangiare
return true;
}
}

private boolean puoMuoversi(int colore,int riga1,int colonna1,int riga2,int colonna2){
if (riga2 < 0 || riga2 > 7 || colonna2 < 0 || colonna2 > 7)
return false; //(riga3,colonna3) e' fuori dalla scacchiera
if (scacchiera[riga2][colonna2] != VUOTO)
return false; //(riga3,colonna3) contiene gia' un pezzo
if (colore == BIANCO) {
if (scacchiera[riga1][colonna1] == BIANCO && riga2 < riga1)
return false; //le pedine bianche possono muoversi solo dall'alto verso il basso
return true;
}
else {
if (scacchiera[riga1][colonna1] == NERO && riga2 > riga1)
return false; //le pedine nere possono muoversi solo dal basso verso l'alto
return true;
}
}

public void getCaptureSequence (int colore, int riga, int colonna, int[][] scacchiera, ArrayList<Mossa> list) {
ArrayList<Mossa> listaSalti = generaSaltiValidi(colore,riga,colonna,scacchiera);
if (listaSalti != null) {
for (Mossa m : listaSalti) {
int[][] boardCopy = copyBoard(scacchiera);
Dama testDama = new Dama();
testDama.setScacchiera(boardCopy);
testDama.muoviPezzo(m);
ArrayList<Mossa> listCopy = copyArrayList(list);
listCopy.add(m);
getCaptureSequence(colore,m.getToRiga(),m.getToColonna(),b oardCopy,listCopy);
}
}
else {
if (list.size() != 0)
listaSequenze.add(list);
}
}

}
    Immagini allegate Immagini allegate
    Rispondi quotando Rispondi quotando
« Discussione precedente | Prossima discussione »

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  

Regole del Forum

Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.