Sign in to follow this  
jsmurthy4

alpha-beta pruning---MinMax

Recommended Posts

Hi Friends, i read article on alpha-beta pruning and minmax. i have some question on this. we take max and min value, max value is for computer and min value for the human player. a)why we need min value for human he may play better move i mean max value(move)? ///////////////////////////////////////////////////////////////////////////// logic below: http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html alpha=-inf,beta=inf ----------------------------------------------------------------------------- alpha-beta(player,board,alpha,beta) if(game over in current board position) return winner children = all legal moves for player from this board if(max's turn) for each child score = alpha-beta(other player,child,alpha,beta) if score > alpha then alpha = score (we have found a better best move) if alpha >= beta then return alpha (cut off) return alpha (this is our best move) else (min's turn) for each child score = alpha-beta(other player,child,alpha,beta) if score < beta then beta = score (opponent has found a better worse move) if alpha >= beta then return beta (cut off) return beta (this is the opponent's best move) ///////////////////////////////////////////////////////////////////// lets suppose i have 9 moves(Nine men's morris-Game) place-Rank--(4r=rank 4),(cball=computer ball),(hball=human ball) 1-4r 2-2r 3-1r---(min) 4-5r 5-4r 6-3r 7-2r 8-6r---(max) 9-4r What happens? i mean 1)it places cball at 1 and hball at 2 alternative all places? and later it checks rank? 2)cball in place 1--4R and hball in palce 2-2r where 4>2 it will cut off the loop? or else 3)loop cont.. and gets 8-6r to alpha? and one more thing i didn't get is depth how it will work? after getting 8-6r it checks for human, max or min value? if depth is 3 is this process cont.. for 3 times or else what? ***************************************************************** it will be great help if u try to answer the above question or with easy example u can thanks in advance Murthy

Share this post


Link to post
Share on other sites
The min in min max isn't the human making the worst move it is the human making the best move. On the max term I pick the move best for me. On the min term the opponent makes the best move for himself which is the move that minimizes my score. so it is called min because it minimizes my score for that move.

Share this post


Link to post
Share on other sites
Try to understand and implement minimax without alpha-beta pruning first. If you don't understand how that works, there is no way you'll understand it with alpha-beta thrown in the mix.

If you have trouble understanding minimax, feel free to post your questions here.

Share this post


Link to post
Share on other sites
Thanks for repling,
it helped me,
minimax will go through each possible child, and (by recursively calling itself) evaluate each possible move. Then, the best possible move will be chosen, where best is the move leading to the board with the most positive score for player 1, and the board with the most negative score for player 2.

it is to our advantage to generate the best moves first for max and the worst moves first for min; this will cause the algorithm to cut off more quickly. On average, using a good successor generator will allow alpha-beta to search to a level twice as deep as minimax in the same amount of time. also that alpha-beta returns the same score as minimax. it simply returns the same result in faster time.

Thanks again,

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this