# Minimax with efficient Alpha-beta pruning for an AI game

As my university project, I develop a minimax agent with alpha-beta pruning for the Hex game. For those who are not familiar with the game, HEX is similar to tic-tac-toe but a bit more complex!

This is the code I have written until now. However, I am willing to optimize my heuristic function to make the alpha-beta run better (with higher degrees of performance). In my code, for heuristic function, I use the principles of tic-tac-toe game which is not the best heuristic (I believe that there may exists better heuristics for the game). The agent often does his best by using heuristic function (e.g. It defeats Random agent 90%). But I'm not sure if it can play optimally against other minimax agents.

Now the question is approximately turned out! Do you know a better efficient heuristic for optimizing the alpha-beta pruning?

I read some heuristics such as killer heuristic but I don't know how I can apply them on my code.

Any help would be appreciated.

MinimaxAgent.java:

``````public class MinimaxAgent extends AbstractPlayer {
private Integer[] currentBoard;
private Board currentBoardObj;
private ArrayList<Integer> availableMoves;
private final int N = 7;
private final int MYTURN = 2;
private final int OPPTURN = 1;

@Override
public Move getMove(Board board) throws BadMoveException {
callMinimax(board, MYTURN);
int minimaxMove = bestMove();
if (board.isSwapAvailable()){
return new Swap();
}
return new Move(new Cell(minimaxMove/N, minimaxMove%N));
}

private void callMinimax(Board board, int turn) throws BadMoveException {
this.currentBoardObj = board;
finalScore = new ArrayList<>();
//Conversion to an integer array for facilitate calculation
board2Array(board);
//Calling minimax function to construct the best move - Starting at depth 0
minimax(0, turn, Integer.MIN_VALUE, Integer.MAX_VALUE);

//print the score of the each move - (Test)
for (Advanced_Node score : finalScore) {
System.err.println("Point:" + (score.point + 1) + " -> Score: " + score.score);
}

System.err.println();

}

//Minimax algorithm
private int minimax(int depth, int turn, int alpha, int beta) throws BadMoveException {

List<Integer> availableMove = getAvailableMoves();

//base case recursive - if there is whether a winner or a draw is captured
if (currentBoardObj.win() == MYTURN)    return 1;
if (currentBoardObj.win() == OPPTURN)   return -1;
if (availableMove.isEmpty())    return 0;

//If we reach the cutoff depth, so call the heuristic function to evaluate the score!
if(depth == 3){
int totalScore = 0;
totalScore = totalScore + Heuristic.heuristic_score(currentBoard);

//Maximizer should return positive value of total score i.e. totalScore
else    return -totalScore;
}

//Maximizer
if (turn == 1) {
//take alpha as a bound
int newScoreBound = alpha;

//For each possible move in the current state
for (Integer anAvailableMove : availableMove) {
int point = anAvailableMove;

//Make the move simultaneously, both on the board array and board object
makeMove(point, 1);
makeMoveObj(point, 1);

//Call the function recursively
int currentScore = minimax(depth + 1, 2, alpha, beta);

//If it comes back to the top, add the score to the final list
if (depth == 0)

//Update the alpha(lower bound) if currentScore is bigger
newScoreBound = Math.max(currentScore, newScoreBound);

//Reset the board array and object
currentBoard[point] = 0;
resetBoardObj(point);

//If the calculated score is bigger than beta, so prune the game tree
if (newScoreBound > beta)
return beta;
}
return newScoreBound;
}

//Minimizer
else{
int newBound = beta;

//for each possible move
for (Integer anAvailableMove : availableMove) {
int point = anAvailableMove;
//make the move
makeMove(point, 2);
makeMoveObj(point, 2);

//recursive call
int currentScore = minimax(depth + 1, 1, alpha, beta);

//update the upper bound if it's lower
newBound = Math.min(currentScore, newBound);

//reset the board
currentBoard[point] = 0;
resetBoardObj(point);

//if the score is bigger than alpha, prune tree
if (newBound < alpha)
return alpha;
}
return newBound;
}
}

private int bestMove() {
int max = Integer.MIN_VALUE;
int best = 0;

//get the highest score
for (int i = 0; i < finalScore.size(); i++) {
if (finalScore.get(i).score > max) {
max = finalScore.get(i).score;
best = i;
}
}

//check if there are moves with identical highest scores;
List<Integer> index = new ArrayList<>();

for(int i=0;i<finalScore.size();i++){
if(finalScore.get(i).score == finalScore.get(best).score)
}

//if there are several moves with identical highest score, randomly pick one
Random ran = new Random();
best = ran.nextInt(index.size());

return finalScore.get(index.get(best)).point;
}

private List<Integer> getAvailableMoves() {
availableMoves = new ArrayList<>();
for (int i = 0; i < N*N; ++i) {
if (currentBoard[i] == 0)
}
return availableMoves;
}

private void resetBoardObj(int point) throws BadMoveException {
//        currentBoardObj.move(new Move(), 0);
currentBoardObj.undo(new Cell(point/N,point%N));
}

private void makeMoveObj(int point, int turn) throws BadMoveException {
currentBoardObj.move(new Move(new Cell(point/N,point%N)), turn);
}

private void makeMove(int point, int player) {
currentBoard[point] = player;
}

private void board2Array(Board board) {
currentBoard = new Integer[N*N];
int k=-1;
for (int i = 0; i < N; ++i) {
for (int j=0; j<N; ++j){
k++;
currentBoard[k] = board.get(new Cell(i,j));
}
}
}
}
``````

Heuristic.java:

``````public class Heuristic {

public static int heuristic_score(Integer[] a){
int total = 0;
//row & col wins
for (int i=0; i<7; i++){
total = total + seventhValue(a[i*7],a[i*7+1],a[i*7+2],a[i*7+3],a[i*7+4],a[i*7+5],a[i*7+6]);
total = total + seventhValue(a[i],a[i+7],a[i+14],a[i+21],a[i+28],a[i+35],a[i+42]);
}
//diagonal wins
total = total + seventhValue(a[0],a[8],a[16],a[24],a[32],a[40],a[48]);
total = total + seventhValue(a[6],a[12],a[18],a[24],a[30],a[36],a[32]);

}

//calculate number of X,Y in a given row/column/diagonal
public static int seventhValue(int a, int b, int c, int d, int e, int f, int g){
int sumX = 0;
int sumY = 0;

if(a == 1)
sumX = sumX+1;
else if(a == 2)
sumY = sumY+1;

if(b == 1)
sumX = sumX+1;
else if(b == 2)
sumY = sumY+1;

if(c == 1)
sumX = sumX+1;

else if(c == 2)
sumY = sumY+1;

if(d== 1)
sumX = sumX+1;

else if(d == 2)
sumY = sumY+1;

if(e == 1)
sumX = sumX+1;

else if(e == 2)
sumY = sumY+1;

if(f == 1)
sumX = sumX+1;

else if(f == 2)
sumY = sumY+1;
if(g == 1)
sumX = sumX+1;
else if(g == 2)
sumY = sumY+1;
if(sumX == 0 && sumY == 7)
return -100;
else if(sumX == 0 && sumY == 6)
return -90;
else if(sumX == 0 && sumY == 5)
return -80;
else if(sumX == 0 && sumY == 4)
return -70;
else if(sumX == 0 && sumY == 3)
return -60;
else if(sumX == 0 && sumY == 2)
return -50;
else if(sumX == 0 && sumY == 1)
return -1;

//if there is 1 X and no Y, X can win
else if(sumX == 1 && sumY == 0)
return 1;
//if there are 2 X and no Y, X can win
else if(sumX == 2 && sumY == 0)
return 50;
else if(sumX == 3 && sumY == 0)
return 60;
else if(sumX == 4 && sumY == 0)
return 70;
else if(sumX == 5 && sumY == 0)
return 80;
else if(sumX == 6 && sumY == 0)
return 90;
//if there are 7 X, X wins
else if(sumX == 7 && sumY == 0)
return 100;

//else(either empty or full), no one has advantages.
else
return 0;
}
}
``````