Archived

This topic is now archived and is closed to further replies.

Boston Whaler

Converting Minimax to Alpha Beta

Recommended Posts

Hi I require some assistance converting Minimax to alpha beta. Here are the Max play and Min play subs, can someone point out where I am making my error as I can''t get them to work. Thanks. Private Function Max_AB(state As clsGameTreeNode, maxdepth As Long, alpha As Long, beta As Long) As Long Dim val As Long, best As Long, move As Integer Dim lbnd As Integer, ubnd As Integer, i As Integer Dim moves As clsQueue Dim p As clsGameTreeNode DoEvents If cutoff_test(state, maxdepth) Then Max_AB = state.GameTreeNodeScore Exit Function End If ''best = -INFINITY ''---- BEGIN GENERATE MOVE LIST ------- Set moves = New clsQueue moves.MaxLen = 6 Select Case state.CurrentPlayer.WhoAmI Case 1 lbnd = 0: ubnd = 5 Case 2 lbnd = 6: ubnd = 11 End Select For i = lbnd To ubnd If state.ValidPlay(i) Then moves.Add i End If Next i ''---- END GENERATE MOVE LIST --------- Do While (Not moves.QEmpty) move = moves.Remove Set p = GetGameTreeNodeChild(state, move) val = Min_AB(p, maxdepth - 1, alpha, beta) If (val > alpha) Then alpha = val state.BestMove = move Else Exit Do End If DoEvents Loop Max_AB = alpha DoEvents End Function Private Function Min_AB(state As clsGameTreeNode, maxdepth As Long, alpha As Long, beta As Long) As Long Dim val As Long, best As Long, move As Integer Dim lbnd As Integer, ubnd As Integer, i As Integer Dim moves As clsQueue Dim p As clsGameTreeNode DoEvents If cutoff_test(state, maxdepth) Then Min_AB = state.GameTreeNodeScore Exit Function End If ''best = INFINITY ''---- BEGIN GENERATE MOVE LIST ------- Set moves = New clsQueue moves.MaxLen = 6 Select Case state.CurrentPlayer.WhoAmI Case 1 lbnd = 0: ubnd = 5 Case 2 lbnd = 6: ubnd = 11 End Select For i = lbnd To ubnd If state.ValidPlay(i) Then moves.Add i End If Next i ''---- END GENERATE MOVE LIST --------- Do While (Not moves.QEmpty) move = moves.Remove Set p = GetGameTreeNodeChild(state, move) val = Max_AB(p, maxdepth - 1, alpha, beta) If (val < beta) Then beta = val state.BestMove = move Else Exit Do End If DoEvents Loop Min_AB = beta DoEvents End Function

Share this post


Link to post
Share on other sites
Hi, I''ve seen that info.

However he does a little tweaking to the standard minimax which adds a level of complexity that I do not understand. And so with the AlphaBeta pseudo he has there.

What I wanted to know was how can I convert his standard minimax to a standard AB, that is which lines would I have to change.

thanks.

Share this post


Link to post
Share on other sites
So you want to know how to convert this into alpha-beta?

  
int MinMax(int depth)
{
if (SideToMove() == WHITE) // White is the "maximizing" player.

return Max(depth);
else // Black is the "minimizing" player.

return Min(depth);
}

int Max(int depth)
{
int best = -INFINITY;
if (depth <= 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Min(depth - 1);
UnmakeMove();
if (val > best)
best = val;
}
return best;
}

int Min(int depth)
{
int best = INFINITY; // <-- Note that this is different than in "Max".

if (depth <= 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1);
UnmakeMove();
if (val < best) // <-- Note that this is different than in "Max".

best = val;
}
return best;
}

Share this post


Link to post
Share on other sites
I myself am not entirely sure about how to do it, but I gave it a try, and got Bruce Moreland to help me out (I was doing some weird things in my attempt). This code is not tested, but it''s the best guess I have so far. I really think you should try using the AlphaBeta approach that he shows on his website. I have been using the nega-max style alpha-beta for so long that trying to convert the "pure" min-max to alpha-beta seems very awkward. Hopefully you are just using this to help you understand the alpha-beta algorithm. In any case, here goes...

  
int AlphaBeta(int depth)
{
if (SideToMove() == WHITE)
return Max(depth, -INFINITY, INFINITY);
else
return Min(depth, -INFINITY, INFINITY);
}

int Max(int depth, int alpha, int beta)
{
if (depth <= 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Min(depth - 1, alpha, beta);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}

int Min(int depth, int beta, int alpha)
{
if (depth <= 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1, alpha, beta);
UnmakeMove();
if (val <= beta)
return beta;
if (val < alpha)
alpha = val;
}
return alpha;
}

That''s what Bruce came up with after he repaired my broken code I sent him. Neither of us tested it, but hey, you have to do some of the work . You can see how this differs from the "pure" min-max code on Bruce''s site. Hope this helps.

Russell

Share this post


Link to post
Share on other sites
Looking at this code I don''t think I would ever have got it done because every AB piece of code I have been analysing for the last 2 weeks or so have something different, i can probaly resite most of them off the top of my head, so I immediately saw that both of the functions here return alpha. and when they prune they both return beta. I guess that where i was making my mistakes. The other ones I had seen had Min returning beta and the Min prune returning alpha and oppositely so for the Max.

Now this negamax thing I had tested and it works but I don''t understand it or why it should work, but my major problem with it is the evaluation function. It can''t just be the evaluation that you use with the regular MiniMax or AB but a modified one...for example .... I you to tell me if i am correct below...if i am then I would just use the negamax.

lets say a game evalutes position exclusive on points each person have at any stage in a game...so if A has more points and is the max player then a bigger positively difference in the scores is good for him zero differnce he is running even with Min player B and a negative distance in the points is bad for A. So an eval function could be like this...

function eval(state) {

eval = points_for_A - points_for_B

}

if eval is negative on a node then that is bad for A and good for B. and vice versa

NOW the importan part for the negamax would it be?

function eval(state) {

if (currentplayer = player_A) {
eval = points_for_A - points_for_B
else
eval = points_for_B - points_for_A
}

}

where when a node is evaled its evalde from the perspective of who ever turn it is??

so that a negative val is bad for the current player and a positive val is good for the currentplayer whether its A or B

and lastly this is my REAL question ... the utility function because at some point in the game the actual leaf nodes will be searched and a utility function as oppsed to an eval funtion will have to be applied to the true leaves (note that with this part i''m not sure if i am correct or not but...). a utility function could be

func util() {

if player_A = winner then
util = +INFINITY
elseif player_B = winner then
util = -INFINITY
else
util = 0

}

Now my problem is I don''t know how to update that to work with negamax. When you use the negamax_AB what do you do in that case.

Thanks. (whew...that was a lot of typing)



Share this post


Link to post
Share on other sites
Can someone tell me why negamax is a good idea?

The only disadvantage of minimax compared to negamax is that minimax is longer to write (twice as long)... I would say that negamax actually makes code harder to read, and thats a big deal for me when I go back to understand what Ive done six weeks later or whatever. I dont see how negamax is faster, theres still the same amount of parameter passing/function calling, just that it happens to be calling itself rather that minimise and maximise alternating.

Tim.

Share this post


Link to post
Share on other sites
I don''t think negamax is supposed to be faster. I think the point is that if you were a professional programmer and you had pure minmax in your program, you''d probably get laughed at, because a professional programmer would see almost instantly that the min and max functions are almost identical, so you cut down on the code you have to maintain, and the potential places where you can have bugs.

Maybe you guys aren''t really grasping what is going on in minmax. In minmax, all you''re doing is switching whether you call min or max. You''re switching the "point of view". In negamax, you''re doing that same switching back and forth, but instead of calling two different functions to accomplish that, you''re flipping the score from positive to negative, and back to positive, and so on (in the val = -NegaMax(depth - 1); line). You''re flipping the point of view by making the score negative instead of calling two seperate functions.

You just have to spend some time with it. I just played with the algorithm, drew lots of trees and performed the algorithm on it, and after a while I started to understand it. I never started with the pure minmax though. I started with negamax, so maybe that''s why it makes more sense to me.

Share this post


Link to post
Share on other sites
Cheers Russel,

My only problem with negamax was that my introduction to it was Jan Svarovsk''s Game Trees article in "Game Programming Gems". The style of writing seriously reflects his (her?!!) level of understanding. I thought it was weird that the only "advantage" of negamax was the less code thing. I sat there thinking "Am I missing something or is it really that trivial?!!!"

Anyway, this has been long winded so here''s something that really helped me understand minimax and hopefully makes this post worthwhile to someone...

Thanks Russel.

Tim.

Share this post


Link to post
Share on other sites