Sign in to follow this  

Code is good but theory is even better

This topic is 4750 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

Hi i'll try to explain to you the game logic of my first game which happens to be a simple chess game.For now i'm having troubles changing the Min-Max strategy to Alpha-Beta strategy and i need your oppinion regarding this since i don't know if i understood it. int AlphaBeta(int depth,int alpha,int beta,int turn) { if(depth==0) return Evaluate(); GenerateLegalMoves(); if(turn==GENIUS) { alpha=-INFINITY;//this will be cut away at the final alpha-beta(hopefully) while(MovesLeft()) { MakeNextMove(); val=AlphaBeta(depth-1,alpha,beta,(turn+1)%2); UndoMove(); if(alpha<val) { alpha=val; if(depth==MAX_LEVEL)WriteAgainThisMOvesInTheGlobalBitboards(); } } return alpha }else {//THIS IS THE MIN LEVEL alpha=INFINITY;//this will be cut away while(MovesLeft()) { MakeNextMove(); val=AlphaBeta(depth-1,alpha,beta,(turn+1)%2); UndoMove(); if(alpha>val) { alpha=val; } } return alpha } } This is how i think alpha-beta should be made (although i'm not very sure) Let's take a simple case :
                                              
             |7|         (Genius(computer)level)
       /                
     |7|            |1|    (Minime(human player)level)
  /  |  \      /     |   \     
|9| |8| |7|    |6|  |5|  |1| (Genius)             


1.at first alpha=-infinty and beta=+infinity 2.alpha should keep the best move and beta the worst move 3.At first Minime will take 9 as the worst move so alpha=-infinity and beta=9 then alpha=-infinity and beta=8 then alpha=-infinity and beta=7 4.Now i go to the second branch and the Evaluation() returns 6 .My algorithm sould stop searching this branch(is that right???????)because i know this is worse than the worst thing from the first branch (7) so i don't go the 5 and 1 anymore.

Now the question is how should i change my game function

I was thinking of changing it like : val=AlphaBeta(depth-1,beta,alpha,(turn+1)%2); ( alpha is the worst thing and beta is the best thing ) if(val<beta)return beta; if(val>alpha)alpha=val; GOD THIS WINTER AND ICE............. . Guys give me a hand will you ThankX! [Edited by - Hermes on December 16, 2004 9:51:06 AM]

Share this post


Link to post
Share on other sites
The first trick is using scores that are always from the perspective of the player to move, so you don't have to duplicate code. Then, you got the treatment of the bounds all wrong. This is what it should look like:
int AlphaBeta(int depth, int alpha, int beta, bool wtm){
if(depth<=0)
return wtm?Evaluate():-Evaluate();

GenerateLegalMoves();

while(MovesLeft()){
MakeNextMove();
val=-AlphaBeta(depth-1,-beta,-alpha,!wtm);
UndoMove();

if(alpha<val){
alpha=val;
if(beta<alpha)
break; // This is a beta cut, which is what makes the whole thing work
}
}

return alpha;
}



Share this post


Link to post
Share on other sites
Well,is this what you mean???


|7| (Genius(computer)level)
/
|7| |1| (Minime(human player)level)
/ | \ / | \
|9| |8| |7| |6| |5| |1| (Genius)



1.I am at the root (alpha,beta)=(-infinity,+infinity)
2.I go on the left branch (alpha,beta)=(-infinity,+infinity)
3.I reach the first node ,this is evaluated to 9 then Minime gets -9
alpha<-9 so (alpha,beta)=(-9,infinity)
alpha<-8 so(alpha,beta)=(-8,infinity)
alpha<-7 so (alpha,beta)=(-7,infinity)
4.I am at the top (apha,beta)=(-infinity,infinity)and i get 7 then
(alpha,beta)=(7,infinity)
5.I go on the right branch (alpha,beta)=(-infinity,-7)
6.I get to the first leaf which is evaluated to 6
7.Minime gets value -6 but (alpha,beta)=(-infinity,-7) so the received value is bigger than -7 so i skip the other leafs.

*Lets say i am at the genius layer and i get a value x,which is better than all the moves i've seen so far so alpha=x;But if x>beta this means that this move is too good to be true so noway that my enemy will let me make this move since i know for sure he has a much worse move prepared for me.
*Now i am at the minime layer and i get a value of y (negative value) and i see this move is better(|y|<|all_the_other_scores|) so alpha=y but at the same time y>beta which means there is a better move out there whic i searched before so i know this is a bad option.




Conclusion:

1.alpha keeps the current best move that it gets from the previous player
2.|beta|(absolut value) is the best score of the previous player
3.I always skip the check if alpha>beta since this move is less valuable.





Well ,does this make any sense to you.....?

[Edited by - Hermes on December 16, 2004 9:26:36 AM]

Share this post


Link to post
Share on other sites
Hermes,
googling would give you hundreds of them ... take a look at this one (just a good one, there are plenty).

Debugging is painfull, so code first a simple minimax, build a test of say 100 or 1000 games, store them in a file with its solutions and then add features one at a time checking against your known solutions. Don't get into a level unless you're fairly confortable with the one you are. Specifically hard to debug when hashing tables will come up.

Dramatic speed improvements with move ordering and hash tables.

Hope it helps.

Share this post


Link to post
Share on other sites

This topic is 4750 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.

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