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

Min-Max
Alpha-Beta

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.

So you want to know how to convert this into alpha-beta?

Yes thats correct.

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...


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

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)

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.

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.

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.