Jump to content
  • Advertisement
Sign in to follow this  
XXChester

help using results of alpha-beta pruning

This topic is 2783 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, I have been struggling with Minimax and alpha-beta pruning over the last week and I have the algorithm(s) down, I just cannot seem to figure out how to interpret the results correctly to determine the best move. Essentially when the code runs, it will either return a -1, 0, or +1 which is correct according to everything I have read, however because of the way I am using these results it is just playing moves sequentially in the beginning. So here is the run down, it is a tic tac toe game and just for the hell of it and wanting to see this thing actually working I wanted to implement the Minimax alpha-beta pruning algorithm, and now I am here.

Here is how I am reading the algorithms results and trying to figure out the best move. Please give it a read or explain the process of what to do with the result. From my understanding I should just be assign the index to the best possibility but sense at early stages of the game everythign is a valid move it just takes the first one.



public override int getMove(Flower[] board) {
int result = -1;

Flower.FlowerType[] types = LogicUtils.getFlowerTypes(board);

// figure out if this is our first move

bool firstMove = true;

for (int i = 0; i < types.Length; i++) {

if (types != Flower.FlowerType.None) {

firstMove = false;

break;

}

}

if (firstMove) {

result = base.generateMove(board);

} else {

int temp;

int alpha = -INFINITY;

int beta = INFINITY;

int[] values = new int[9];// for debugging

for (int i = 0; i < types.Length; i++) {

if (types == Flower.FlowerType.None) {

types = LogicUtils.cloneFlowerTypes(types);

types = LogicUtils.COMPUTERS_TYPE;

temp = alphaBeta(types, StateManager.TurnType.Computers, alpha, beta);

values = temp;

if (temp > alpha) {

alpha = temp;

result = i;

}

}

}

}

return result;

}




Thank you for your help, I appreciate it.

Share this post


Link to post
Share on other sites
Advertisement
I usually write a separate search function for the root of the search tree. which is similar to the function that handles all the other nodes, with some important differences. The first difference is that this one returns a move instead of a score. It may also have many other things, like iterative deepening, time control, sending the user some information about the state of the search, clearing the hash tables...

Of course in tic-tac-toe this function won't have most of the features I just described, but I bet you have some more interesting games in mind.

Share this post


Link to post
Share on other sites
Thanks guys I will give it a try. Yeah I do have more interesting games in mind, I am way ahead of tic-tac-toe but I just jumped to XNA so I wanted to write something simple to make sure everythign I ported over is still functional and than pick up where I left off. But I decided to try out the minimax algorithm as an addition.

Anyway I will give your suggestions a try, I think I am very close to having the way you search the root tree correct but I am jsut not quite sure.

Share this post


Link to post
Share on other sites
Thanks for your suggestions. They were not helpful to me as I was already doing both of these things but both of your answers are correct for MiniMax and alpha beta pruning. My problem was a damn equality problem in my recursive function, for some reason == on my enum would work sometimes when checking whose turn it was but other times it wouldn't. When I flipped it to be CONSTANT.equals(turn) the algorithm started to work as expected.

Thanks again for your suggestions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!