Eric H. Eric H. - 6 months ago 10
Java Question

Tic-Tac-Toe Print the Path of Best Move in Game Tree Search?

I am working on the alpha-beta pruning algorithm with Tic-Tac-Toe game (3x3). Currently for any given instance of the 3x3 grid, I was able to figure out the best case:

public Best chooseAlphaBetaMove(int whosMov, int alpha, int beta) {

Best reply = new Best();
Best myBest = new Best();

if ((scoreGrid()==COMPUTER_WIN) || (scoreGrid()==OPPONENT_WIN) ||
(scoreGrid()==GAME_DRAW)) {
int score = scoreGrid();
return new Best(score,-3,-3,count);
}

if (whosMov==COMPUTER_MOVE) {
myBest.score = alpha;
} else {
myBest.score = beta;
}

for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (layOut[i][j]==0) {
moveGrid(whosMov,i,j);
reply = chooseAlphaBetaMove(-whosMov,alpha,beta);
unmoveGrid(i,j);

if ((whosMov==COMPUTER_MOVE)&&(reply.score>myBest.score)) {
myBest.score = reply.score;
alpha = reply.score;
myBest.row = i;
myBest.column = j;
}

if ((whosMov==OPPONENT_MOVE)&&(reply.score<myBest.score)) {
myBest.score = reply.score;
beta = reply.score;
myBest.row = i;
myBest.column = j;
}
if (beta <= alpha) return myBest;
}
}
}

return myBest;
}


Where the Best structure is:

public class Best {

public int score;
public int row;
public int column;
public int count
}


Given an initial grid and who will move next, I can know the best score and the best position for this next player to go. However, I can't figure out how to print the whole path for this best move. (Note - I don't want the whole search path. I only want to print out the single search path starting from this best move till the leaf). Any thoughts? thanks!

DNA DNA
Answer

As you go recursively down each path, you need to keep track of it, probably by passing a reference to a List/Stack into each chooseAlphaBetaMove call. When you find a better path than the current best path, you take a copy of the current path, and store it as the "best path so far". Once you have finished, you can then print out the best path.

Comments