wood burning stoves 2.0*
The moose likes Java in General and the fly likes Alpha beta pruning with negamax Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Alpha beta pruning with negamax" Watch "Alpha beta pruning with negamax" New topic
Author

Alpha beta pruning with negamax

Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
The code below is written for connect four (plot four).This is not my home work. My hobby is programming so I am doing it.It works perfectly fine when ab pruning is not used,but has one draw back that is it takes lot of time to execute move.

This is the entire code for connectfour using negamax+ab pruning. But it is not working. I think I have made mistake in
the if else if loop of minmax().


The code executes perfectly but then it doesn't even see win for the player,nor forces a quick win (even if it is possible) for it self


please forgive me for grammatical mistake as English is my second language.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
I didn't try to figure out your code, but I'm in the middle of implementing a recursive negamax algorithm with my chess program. Here is the pseudocode for the negamax part of things. If we can see eye to eye on this, then I'll add in the alphabeta pruning, and hopefully this might help you with your program.
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125

Thanks for the code mate.



Here is my only negamax + ab pruning code, it contains many bugs which i am not able to debug. I have tried it many a time but still failed, so I am posting it here
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
You say that things work just fine without the abp code, just slowly, which is to be expected. It is worth noting that abp should not change your final choice of a move, just speed up the process.

The following page is a good resource for negamax and alpha-beta pruning. It's a chess page, but the algorithms are the same.

http://www.frayn.net/beowulf/theory.html

Also, give some thought to implementing some kind of a trace which will print to the console the various tree paths and their evals, and also which tree branches were pruned and why.

I am very interested in the topic, but I don't find it easy. If you can help me out by specifying exactly which lines of your code are responsible for the abp pruning, and a word or two about how you expect it to work, then I will give it my best shot to understand the problems.

Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@fred
I am very thankful to you for your replies.
I have implemented this code for connect four AI. it plays decently(beat few online bots and lost to few online bots.. thts pretty good when novice programmer like me has programmed it) The only thing is that,it takes lots of time to execute the move(at depth of 8 its 10 secs approx).and hence I want ab along with negamax,so that i can speed up the process and raise the depth to a higher value than 8 to make it play stronger.

So to describe my program I will write few word for the methods which are there.
I have two variables value and prevalue, value stores the current value while prevalue stores the previous value. Now they are compared, if value>prevalue, then prevalue stores the value (i.e its current score) and for column having the highest prevalue, checker is put in to it.(I have not written the score function yet.. I will do it , but i guess it has nothing to do with ab pruning)

Here is the code:





where moves is a vector

Now come the method of minmax(same as negamax+ab in this program).
it has 4 parameters.
1.playe whose turn it is to move
2.column which is to be iterated
3.alpha (variable a) which is initialized as -MAX_RECURDEPTH.
4.beta (variable b) which is intializes as MAX_RECURDEPTH .

According to me I have made mistake in if's .
More over if write return a then it plays 3-4 moves and not allowing the user to play.
if I don't write it (i replace with break) then it does not even see the victory for itself or the player(even if there are 3 in format,horizontal,vertical,diagonal).
Here is code for if's










I want the ab pruning to behave in same way as that of negamax but eliminating the useless nodes.
here is the code for negamax+ab pruning.


I would definitely like to help you in chess(I am chess player my self),But as of now ,I am not on that level of programming chess, so step by step i would like to learn
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
ok bud, you are welcome. Like I said I am interested in the topic, so I will learn something useful here too. I should be able to reply by this time tomorrow. In the mean time I'll keep an eye on the thread in case someone else solves it.

And sure, we can talk about the chess later too., I'm not a guru, the negamax/abp algorithm is pretty much the same from game to game.
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
Thanks once again, I will wait for your reply which will hopefully solve my problem.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
I don't think we are on the same page as to what some of this stuff actually means.

OK we agree on the purpose of alphabeta pruning does. It eliminates nodes and subsequent tree creation and evaluation based on the findings of negamax, negamax tells us the nodes won't influence the final evaluation, alhabeta pruning actually does something about that.

What do you mean about not having written a score function yet. What do you mean by a score function. I don't see how you can even have negamax without a way to evaluate the end points of the tree.


... Now come the method of minmax(same as negamax+ab in this program).


I'm not sure why you are talking about it. I see minmax as a different way of traversing the game tree, as is negamax, so I don't see minmax and negamax as co-existing in the same algorithm. Furthermore. I see ab pruning as being something that can be added to negamax and minmax to speed things up. Do you agree?


I want the ab pruning to behave in same way as that of negamax


OK, are you saying that you want abp to work with minmax the same way it works with negamax? That would make sense. Except I still don't know why you are talking about minmax. Like I said, to me it's one or the other
. Either you have minmax or negamax. agreed?

Please have a look at my pseudocode. Do you understand it, do you condider it to be correct, and does it conform to your understanding of negamax, without the abp?
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
I think there is confusion here the name of function is minmax,but it is written in negamax fuction.. so to refer it by name, i I think the pseudo code that you wrote helped me but that is not the way in which I have written my negamax function. If you look at my code then you will find the variable preValue which stores the highest score. If it has connect in four then it straight away displays the (MAX_RECURDEPTH-prevalue) as score to win,for all rest till it does not find win it displays score as zero. By writing a score function, I mean it evaluates each position and then shows up like for example if computer has a slightly better position then it shows 0.24 or something like that, this is what I have not written as of now. As my code is working without the score function.(just now I tried to explain you what score function means in my program.)implementing the only negamax code, it should work with negamax+abp as well.
The reason I think that it does not work is in either the if's or in the return a rest I think there is no problem(as I have not modified my original negamax code which is fully working so trying to work there, please help me if you find the correct code or correct sequence of coding)
I think the confusion is being cleared of minmax and negamax. so to end with confusion I will give an short example:
even if you call rose as lily, it will still remain rose. In same way I have named negamax as minmax, but still it will be negamax.
Need your help.
Thank you.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Gurudas Bhandarkar wrote:I think there is confusion here the name of function is minmax,but it is written in negamax fuction.. so to refer it by name, i I think the pseudo code that you wrote helped me but that is not the way in which I have written my negamax function. If you look at my code then you will find the variable preValue which stores the highest score. If it has connect in four then it straight away displays the (MAX_RECURDEPTH-prevalue) as score to win,for all rest till it does not find win it displays score as zero. By writing a score function, I mean it evaluates each position and then shows up like for example if computer has a slightly better position then it shows 0.24 or something like that, this is what I have not written as of now. As my code is working without the score function.(just now I tried to explain you what score function means in my program.)implementing the only negamax code, it should work with negamax+abp as well.
The reason I think that it does not work is in either the if's or in the return a rest I think there is no problem(as I have not modified my original negamax code which is fully working so trying to work there, please help me if you find the correct code or correct sequence of coding)
I think the confusion is being cleared of minmax and negamax. so to end with confusion I will give an short example:
even if you call rose as lily, it will still remain rose. In same way I have named negamax as minmax, but still it will be negamax.
Need your help.
Thank you.


my algorithm does pretty much the same thing, in that it stores the highest value in max. For now it only does that to so I won't have to find the maximum when it comes time to actually select the move. When I add in my abp, it will be comparing the max to the evals of the replies of the opponent As I see it what your code does when it finds a connect4 is technically not a part of negamax. It's almost like a simplified abp, you see what I mean?

Anyways, you have cleared up my misunderstanding about terminology, so now I will look closely at your code and try to reply by the end of the day
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@Fred.
I will be very thankful to you.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
ok bud, I figure before I tried to tell you how to do yours, I should get mine working, so here is my recursive negamax with alpha - beta pruning. You can test drive it at the link in my signature. My head is spinning, so I will probably take the rest of the night off before I tackle your code. I'll be happy to answer any questions you have on my code. You will notice this is incomplete code, but the methods themselves are complete. p.s. it is worth noting that alpha-beta pruning reduced my search time by about 50%

Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@Fred

I understood your code. (Your comments made it easier!)
But only one problem between your code and mine: I have not created a copy of the board.as you can see in my code, I have declared everything as static variables. more over, I tried to make copy of it and tried to fit in your code, it played worse and made moves for human player as well.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Gurudas Bhandarkar wrote:@Fred

I understood your code. (Your comments made it easier!)
But only one problem between your code and mine: I have not created a copy of the board.as you can see in my code, I have declared everything as static variables. more over, I tried to make copy of it and tried to fit in your code, it played worse and made moves for human player as well.


So you are saying that you tried to use my algorithm with your code, and it played worse? But you understand my code and agree with its correctness? or not?
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@fred
When I looked at your code, it seemed pretty fine. But I guess certain things have been missed out.
You did not undo the moves (When I tried to implement it without undoing the moves it gave me array out-of-bound exception)
secondly,When I tried to implement it in my game it did not look for win,neither for itself nor for the opponent. Here is the code which I modified.Please take a careful look at it. (I don't have much time to program now as my college will start and then I must begin with my studies(electronics). So I am trying to fix this bug as soon as possible.Please Help)



here is the entire code,
try executing it:
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Yeah, I have realized that mine has some issues. It's ok as far as it goes, but it needs a little work. I will be giving this stuff my attention, but It's going to take more time than I thought, so don't hold your breath. Anyways, I shall return hopefully soon with some answers.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Gurudas Bhandarkar wrote:@fred
When I looked at your code, it seemed pretty fine. But I guess certain things have been missed out.
You did not undo the moves (When I tried to implement it without undoing the moves it gave me array out-of-bound exception) secondly,When I tried to implement it in my game it did not look for win,neither for itself nor for the opponent. Here is the code which I modified.Please take a careful look at it. (I don't have much time to program now as my college will start and then I must begin with my studies(electronics). So I am trying to fix this bug as soon as possible.Please Help)


I don't know what you mean when you say "You did not undo the moves". As far as not looking for a win goes, I don't see it that way. For example in my program, at ply = 2 it will solve mate in one, at ply = 4 it will solve mate in two, etc. It does this by virtue of starting with a very low initial maxValue. At ply = 4 it will find no possible moves and return the -ve of that low max value, which will lead to the move that forces checkmate being played.
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@fred
By undoing the moves, I mean In my code.(If I donot write this,It gives me array out o bounds exception.)
(I have modified the code so many times, that by this time, I have almost forgotten what my original code was!)
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
More over, it should be noted as my current search max depth is 8, and still the computer does not look win in 1 also.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Ok, By undoing moves are you talking about undoing the analysis so that the change in the game position only reflects the move actually played? If so, then I suggest that your array index out of bounds exception is not because of something correct that you aren't doing, it's because of something incorrect that you are doing. I don't concern myself with undoing moves because the analysis creates copies of the position as needed, and these copies are discarded once a particular subtree is evaluated. Only when the final move is chosen is the game position updated.

As for not looking for a win, as I see it that is not really a function of negamax itself , that is a function of the evaluation of the end points of the tree. A particular move leads to a forced win in all variations if all the endpoints of the subtree, after correct ab pruning, are winning positions, if your evaluation routine correctly identifies the endpoints as winning, then the algorithm I provided will indeed choose the winning move. If yor program is not finding a win in one move then you haven't implemented the algorithm properly.

Anyways, i still intend to examine your code, i will begin doing so today, and hopefully will find specific sections of yur code that is causing the problem.
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@fred
I don't think it is possible for me to go for alpha beta pruning (I tried for 3 weeks and failed).I just have one more week to go and then my college will start.If in one week, we are not able to rectify this,then i request you (i can only request you as you may also have lot of work) to rectify my code completely.Its a favour that I can only ask for(not hoping that you will do it). But still I am quiet positive about the job being successfully done in time.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
heh heh I will try soon, if I can't rectify your connect-4, Then I'll write my own. Hang tough, sorry to keep you waiting after all the work you have put in to this thread so far.
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
@fred

Actually I must Thank you for replying me constantly with new ideas and taking pain to find flaws. I must also say that you helped me in this debugging(though its not completely debugged.. and that is of course my fault as the way I have programmed).
Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
A good news,(at least for me) My vacation is extended.. and now it will be take one more week to start .
- hope you reply soon regarding the code
 
Consider Paul's rocket mass heater.
 
subject: Alpha beta pruning with negamax
 
Similar Threads
Converting a two dimensional int array into a byte array
Array Testing Output Confusion
Help in connect four
array out of bounds
How to add gutter space after each column in JTextpane?