skytreader

July 27th, 2011, 04:50 PM

So, I have already created a minimax method for tic tac toe. However, I don't get how AB-Pruning can work for it. Let me explain.

The way I understand minimax: generate a game tree all the way to the endgames. If a branch can lead to a (win|lose) for (max|min), pursue. Else, pick another branch.

The way I understand AB-Pruning: The moment a branch becomes (less|greater) than current (max|min), discard.

I don't see how ABP can help minimax. Minimax "passes" through the tree twice: one to generate the endgames and another one to "ripple up" the values of endgames to the "caller" nodes. So, for ABP to know if a branch becomes (less|greater) than current (max|min), it still needs to generate the endgames and then wait for the ripple up.

I already have this code:

int computer_move(char** board, char piece1, char piece2){

//Some code here...

int max = -1;

int min = 1;

for(i = 0; i < blankcount; i++){

//Will be given to the recursive call

char** clonechild = (char**) malloc(sizeof(char*) * 3);

int j;

for(j = 0; j < 3; j++){

clonechild[j] = (char*) malloc(sizeof(char) * 3);

}

//All children has been pre-generated. Recurse on each one.

copyboard(children[i], clonechild);

int nextmove = computer_move(clonechild, piece2, piece1);

//In other words: if this node is greater than current min

//ignore. But still, we generated endgames.

if(piece1 == PLAYER1 && nextmove < min){

min = nextmove;

theindex = i;

}

//In other words: if this node is less than current max

//ignore. But still, we generated endgames.

else if(piece1 == PLAYER2 && nextmove > max){

max = nextmove;

theindex = i;

}

}

//...and then some more.

}

So it seems to me that I'm already doing ABP (or at least, how I understand it).

Thanks to anyone who'd take the time to explain.

The way I understand minimax: generate a game tree all the way to the endgames. If a branch can lead to a (win|lose) for (max|min), pursue. Else, pick another branch.

The way I understand AB-Pruning: The moment a branch becomes (less|greater) than current (max|min), discard.

I don't see how ABP can help minimax. Minimax "passes" through the tree twice: one to generate the endgames and another one to "ripple up" the values of endgames to the "caller" nodes. So, for ABP to know if a branch becomes (less|greater) than current (max|min), it still needs to generate the endgames and then wait for the ripple up.

I already have this code:

int computer_move(char** board, char piece1, char piece2){

//Some code here...

int max = -1;

int min = 1;

for(i = 0; i < blankcount; i++){

//Will be given to the recursive call

char** clonechild = (char**) malloc(sizeof(char*) * 3);

int j;

for(j = 0; j < 3; j++){

clonechild[j] = (char*) malloc(sizeof(char) * 3);

}

//All children has been pre-generated. Recurse on each one.

copyboard(children[i], clonechild);

int nextmove = computer_move(clonechild, piece2, piece1);

//In other words: if this node is greater than current min

//ignore. But still, we generated endgames.

if(piece1 == PLAYER1 && nextmove < min){

min = nextmove;

theindex = i;

}

//In other words: if this node is less than current max

//ignore. But still, we generated endgames.

else if(piece1 == PLAYER2 && nextmove > max){

max = nextmove;

theindex = i;

}

}

//...and then some more.

}

So it seems to me that I'm already doing ABP (or at least, how I understand it).

Thanks to anyone who'd take the time to explain.