Hi! This is my code to AI of Connect 4 game. I wrote a minimax (it´s working very well) but i have to implement a Alpha Beta pruning... and i need help. Can you see the code and help me? Thanks for the help, and sorry by the poor english (I´m Brazilian and don't talk very well)...
package Jogadores;
import java.util.*;
public class JogadorBEst implements Jogador {
private static int recurDepth = 0;
private static final int MAX_RECURDEPTH = 7;
private static int WIDTH, HEIGHT;
private int[][] board;
private int[] columnHeight;
private int me;
public JogadorBEst() {
}
public int jogada(int[][] tabuleiro, int corDaMinhaBola) {
getBoardLength(tabuleiro);
getColumnHeight(tabuleiro);
this.board = copyBoard(tabuleiro);
this.me = corDaMinhaBola;
int action = 0;
int value = 0;
Vector moves = new Vector();
moves.removeAllElements();
int prevValue = -MAX_RECURDEPTH - 1;
for (int col = 0; col < WIDTH; col++) {
if (columnHeight[col] >= HEIGHT) {
continue;
}
value = minimax(this.me, col);
if (value > prevValue) {
moves.removeAllElements();
prevValue = value;
}
if (value == prevValue) {
moves.add(new Integer(col));
}
}
if (moves.size() > 0) {
Collections.shuffle(moves);
action = ((Integer) moves.get(0)).intValue();
}
return action;
}
private void getBoardLength(int[][] board) {
WIDTH = board.length;
HEIGHT = board[0].length;
}
private void getColumnHeight(int[][] board) {
columnHeight = new int[WIDTH];
int aux = 0;
for (int col = 0; col < WIDTH; col++) {
for (int row = 0; row < HEIGHT; row++) {
if (board[row][col] == 0) {
aux++;
}
}
columnHeight[col] = HEIGHT - aux;
aux = 0;
}
}
private int[][] copyBoard(int[][] board) {
int[][] copia = new int[WIDTH][HEIGHT];
int aux = 0;
for (int row = WIDTH - 1; row >= 0; row--) {
for (int col = 0; col < HEIGHT; col++) {
copia[col][aux] = board[row][col];
}
aux++;
}
return copia;
}
int minimax(int player, int column) {
if (columnHeight[column] >= HEIGHT) {
return 0;
}
int value = 0;
recurDepth++;
this.board[column][columnHeight[column]] = player;
columnHeight[column]++;
if (fourInARow() > 0) {
if (player == this.me) {
value = MAX_RECURDEPTH + 1 - recurDepth;
} else {
value = -MAX_RECURDEPTH - 1 + recurDepth;
}
}
if (recurDepth < MAX_RECURDEPTH && value == 0) {
value = MAX_RECURDEPTH + 1;
for (int col = 0; col < WIDTH; col++) {
if (columnHeight[col] >= HEIGHT) {
continue;
}
int v = minimax(3 - player, col);
if (value == (MAX_RECURDEPTH + 1)) {
value = v;
} else if (player == this.me) {
if (value > v) {
value = v;
}
} else if (v > value) {
value = v;
}
}
}
recurDepth--;
columnHeight[column]--;
this.board[column][columnHeight[column]] = 0;
return value;
}
int fourInARow() {
int num, player;
for (int y = 0; y < HEIGHT; y++) {
num = 0;
player = 0;
for (int x = 0; x < WIDTH; x++) {
if (this.board[x][y] == player) {
num++;
} else {
num = 1;
player = this.board[x][y];
}
if (num == 4 && player > 0) {
return player;
}
}
}
for (int x = 0; x < WIDTH; x++) {
num = 0;
player = 0;
for (int y = 0; y < HEIGHT; y++) {
if (this.board[x][y] == player) {
num++;
} else {
num = 1;
player = this.board[x][y];
}
if (num == 4 && player > 0) {
return player;
}
}
}
for (int xStart = 0, yStart = 2; xStart < 4;) {
num = 0;
player = 0;
for (int x = xStart, y = yStart; x < WIDTH && y < HEIGHT; x++, y++) {
if (this.board[x][y] == player) {
num++;
} else {
num = 1;
player = this.board[x][y];
}
if (num == 4 && player > 0) {
return player;
}
}
if (yStart == 0) {
xStart++;
} else {
yStart--;
}
}
for (int xStart = 0, yStart = 3; xStart < 4;) {
num = 0;
player = 0;
for (int x = xStart, y = yStart; x < WIDTH && y >= 0; x++, y--) {
if (this.board[x][y] == player) {
num++;
} else {
num = 1;
player = this.board[x][y];
}
if (num == 4 && player > 0) {
return player;
}
}
if (yStart == HEIGHT - 1) {
xStart++;
} else {
yStart++;
}
}
// Ninguem está ganhando
return 0;
}
public String getNome() {
return "Jogador BE";
}
public String printTabuleiro() {
String resultado = "";
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
resultado = resultado + " | " + this.board[j];
}
resultado = resultado + " | " + "\n";
}
return resultado;
}
}
I have tried this:
int minimax(int player, int column, int alpha, int beta) {
if (columnHeight[column] >= HEIGHT) {
return 0;
}
int value = 0;
recurDepth++;
this.board[column][columnHeight[column]] = player;
columnHeight[column]++;
if (fourInARow() > 0) {
if (player == this.me) {
value = MAX_RECURDEPTH + 1 - recurDepth;
} else {
value = -MAX_RECURDEPTH - 1 + recurDepth;
}
}
if (recurDepth < MAX_RECURDEPTH && value == 0) {
if (player == this.me) {
value = alpha;
} else {
value = beta;
}
for (int col = 0; col < WIDTH; col++) {
if (columnHeight[col] >= HEIGHT) {
continue;
}
if (player == this.me) {
value = Math.max(value, minimax(3 - player, col, alpha, beta));
alpha = value;
} else {
value = Math.min(value, minimax(3 - player, col, alpha, beta));
beta = value;
}
if (alpha >= beta) {
recurDepth--;
columnHeight[column]--;
this.board[column][columnHeight[column]] = 0;
return value;
}
}
}
recurDepth--;
columnHeight[column]--;
this.board[column][columnHeight[column]] = 0;
return value;
}
But still no working...
