Results 1 to 19 of 19
Like Tree1Likes
  • 1 Post By KevinWorkman

Thread: Alpha-beta pruning

  1. #1
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Exclamation Alpha-beta pruning

    I found this pseudocode on Wikipedia.

    Java Code:
    function alphabeta(node, depth, α, β, maximizingPlayer)
        if depth = 0 or node is a terminal node
            return the heuristic value of node
        if maximizingPlayer
            for each child of node
                α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
                if β ≤ α
                    break (* β cut-off *)
            return α
        else
            for each child of node
                β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
                if β ≤ α
                    break (* α cut-off *)
            return β
    (* Initial call *)
    alphabeta(origin, depth, -∞, +∞, TRUE)
    What do they mean exactly with min(β, alphabeta(child, depth - 1, α, β, TRUE))? Is it a function that returns the lowest value of all the nodes? Or does it return the smallest value of alpha and beta, like this:

    Java Code:
    static int min(int SCORE1, int SCORE2){
    	if(SCORE1 < SCORE2)
    		return SCORE1;
    	else if(SCORE2 < SCORE1)
    		return SCORE2;
    	else
    		return SCORE1;
    }
    What do you think? I don't think that would make sense at all, it's got to be something else. And where are the best positions for alpha and beta saved? I am having trouble understanding this, so I would be really glad if you helped me :)

    Thanks!
    Last edited by Zelaine; 01-06-2014 at 12:53 AM.

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    It's a recursive call to the alphabeta() function. What does the alphabeta() function return?
    Zelaine likes this.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    It returns an int value. If it is a recursive call, why create two separate functions for that (max and min)? Why not just type β := alphabeta(child, depth - 1, α, β, TRUE) then?
    Last edited by Zelaine; 01-06-2014 at 05:18 PM.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    Quote Originally Posted by Zelaine View Post
    It returns an int value. If it is a recursive call, why create two separate functions for that (max and min)? Why not just type β := alphabeta(child, depth - 1, α, β, TRUE) then?
    What happened when you wrote a little test program that did exactly that? What happened when you traced through your modified algorithm with a piece of paper and a pencil?

    The min() and max() functions are simply utility functions used by the alphabeta() function to keep things clean. In Java, you might use the Math.min() and Math.max() functions.

    The algorithm takes whatever is returned from the alphabeta() function (at the child level) and compares it to the alpha or beta (at the parent level) using the min() and max() functions.

    The how and why are the meat and potatoes of the algorithm, which I assume is your assignment to understand.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    What happened when you wrote a little test program that did exactly that?
    It did not work out at all, the computer chose seemingly random positions.

    What happened when you traced through your modified algorithm with a piece of paper and a pencil?
    I did trace through it, however not with a piece of paper and a pencil, but just by putting print statements everywhere. It did not give me a better understanding though, probably because it was all too messy.

    In Java, you might use the Math.min() and Math.max() functions.
    Thanks, I'll try that! :)

    The algorithm takes whatever is returned from the alphabeta() function (at the child level) and compares it to the alpha or beta (at the parent level) using the min() and max() functions.
    And returns the greatest or smallest value (depending on what function we're using)?

    The how and why are the meat and potatoes of the algorithm, which I assume is your assignment to understand.
    Yes, it is. I'll return when I have it figured out. Thanks for the feedback!

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,520
    Blog Entries
    7
    Rep Power
    20

    Default Re: Alpha-beta pruning

    The minmax algorithm assumes that your best/worst move is worst/best for your opponent and your opponent's best/worst move is worst/best for you; and vice versa from your opponent's perspective. That pseudo code is just translation of that observation.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    Thanks, I got that, and this is what I came up with:

    Java Code:
    Initial call: alphaBeta(0, 9, -1000, 1000);
    
    ...
    
    static int alphaBeta(int node, int depth, int ALPHA, int BETA){
    	if(depth == 0 || foundTerminalState()){
    		int winner = chooseWinner();
    		if(winner >= -1 && winner <= 1)
    			return winner;
    	}
    		
    	if(TURN == 1){
    		for(int tile = 0; tile < BOARD.length; tile++)
    			if(isLegal(tile)){
    				makeMove(tile, 'X');
    				changeTurn();
    				BETA = Math.min(BETA, alphaBeta(tile, depth-1, ALPHA, BETA));
    				undoMove(tile);
    				if(ALPHA >= BETA)
    					break;
    			}
    		return BETA;
    	}
    		
    	else{
    		for(int tile = 0; tile < BOARD.length; tile++)
    			if(isLegal(tile)){
    				makeMove(tile, 'O');
    				changeTurn();
    				ALPHA = Math.max(ALPHA, alphaBeta(tile, depth-1, ALPHA, BETA));
    				undoMove(tile);
    				if(ALPHA >= BETA){
                        BEST_COMPUTER_MOVE = tile;
    					break;
    				}
    			}
    		return ALPHA;		
    	}
    }
    I have tried to replicate the pseudocode, but my opponent (the computer) does the most stupid moves all the time so apparently I did not succeed. Do you have any feedback? What should I change?
    Last edited by Zelaine; 01-06-2014 at 07:55 PM.

  8. #8
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    You shouldn't replicate pseudocode. You need to understand the ideas behind it and what it's trying to accomplish instead of trying to "translate" it into Java directly.

    Just glancing at it though, how does the alphabeta function know which turn it is? Note that the current player's turn in the game might be different from the "virtual turn" the alphabeta function is looking at on any given recursive call.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  9. #9
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    You shouldn't replicate pseudocode. You need to understand the ideas behind it and what it's trying to accomplish instead of trying to "translate" it into Java directly.
    I know I shouldn't replicate pseudocode, but if the pseudocode is correct shouldn't that result in a correctly working program? I have tried understanding it for days before posting this post and the post before this one, but I still apparently don't understand it, because whenever I try to write it I just get the same code. I was just so tired of that and wanted to get it working.

    Just glancing at it though, how does the alphabeta function know which turn it is?
    I have a global variable called TURN, which value I change with the changeTurn() function.

    Note that the current player's turn in the game might be different from the "virtual turn" the alphabeta function is looking at on any given recursive call.
    I tried what you said. The result changes, but it is still not correct so there must obviously be something else that's wrong.

  10. #10
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    Quote Originally Posted by Zelaine View Post
    I know I shouldn't replicate pseudocode, but if the pseudocode is correct shouldn't that result in a correctly working program? I have tried understanding it for days before posting this post and the post before this one, but I still apparently don't understand it, because whenever I try to write it I just get the same code. I was just so tired of that and wanted to get it working.
    The pseudocode is correct, but your understanding of it is incomplete, so implementing it is going to be a series of huge headaches, which I think you're experiencing now. I recommend taking a step back and spending the time really understanding the alphabeta algorithm before trying to write code. You might have to go back and read your textbook and class notes.


    Quote Originally Posted by Zelaine View Post
    I have a global variable called TURN, which value I change with the changeTurn() function.
    I tried what you said. The result changes, but it is still not correct so there must obviously be something else that's wrong.
    Like I said, the actual TURN might not be the "virtual" turn inside the function. Think about it this way:

    You and I are playing checkers. It is currently my turn. To decide where to go, I look at every possible move I could make. To evaluate which one of those moves I should make, I *pretend* I made each move and then *pretend* that it's your turn. What would you do with the board that results if I made that particular move?

    To figure out which move you would make, I pretend I'm you and do the same thing: for each possible move you could make, you take the resulting board and *pretend* that you're me! So I have to think ahead, switching between whose turn I'm *pretending* it is.

    Eventually I reach my limit of how many turns I can look ahead and I have to assign the resulting board a *heuristic value*, which I then use to figure out which move would be made by the pretend versions of you and me.

    It sounds really complicated, but it's pretty trivial for a computer to do.

    So in your code, you're not *pretending* it's the other person's turn, which is a pretty important part of the algorithm, which is why I think you should take a step back before writing another line of code.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  11. #11
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    You and I are playing checkers. It is currently my turn. To decide where to go, I look at every possible move I could make. To evaluate which one of those moves I should make, I *pretend* I made each move and then *pretend* that it's your turn. What would you do with the board that results if I made that particular move?
    Yeah, I understand that, it's just that I'm having trouble implementing it :P
    You might have to go back and read your textbook and class notes.
    I don't take classes, I just wanted to create an unbeatable Tic-Tac-Toe game :)
    ... which is why I think you should take a step back before writing another line of code.
    I'll try it :) Thanks for the feedback, it's been really helpful!
    Last edited by Zelaine; 01-06-2014 at 09:17 PM.

  12. #12
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    After a few hours of going through the program with a pencil and a piece of paper, I know what I am missing. When the algorithm is "pretending", as you elegantly expressed it, to be the player, it must not only return the BETA value, but also the ALPHA value. Because changing the value of ALPHA lower in the stacks of recursion that is the algorithm, doesn't change the value in the upper levels IF the value is not returned. Same thing goes for when the algorithm is "pretending" to be the computer, it must not only return the ALPHA value, but also the BETA value. When I've got this figured out, it's just implementing it into the program left. I am thinking about using objects, but then I would have to redo the whole algorithm, so firstly I will look for a different approach.
    Last edited by Zelaine; 01-07-2014 at 03:00 AM.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,520
    Blog Entries
    7
    Rep Power
    20

    Default Re: Alpha-beta pruning

    Don't use a global variable 'TURN'; the algorithm might prune and return while the TURN variable might not have been reset to the correct value (i.e. do as the pseudo code does and pass it as a parameter).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    I need to return two variables in my algorithm, but I can't use objects because if I change the value of the object's variables, those will change everywhere. How could I do that? An object that is passed on like a variable maybe, but can contain several variables? Or anything else that works, really.

    Java Code:
    static int alphaBeta(int node, int depth, int ALPHA, int BETA){
        if(depth == 0 || foundTerminalState()){
            int winner = chooseWinner();
            if(winner >= -1 && winner <= 1)
                return winner;
        }
             
        if(TURN == 1){
            for(int tile = 0; tile < BOARD.length; tile++)
                if(isLegal(tile)){
                    makeMove(tile, 'X');
                    changeTurn();
                    BETA = Math.min(BETA, alphaBeta(tile, depth-1, ALPHA, BETA));
                    undoMove(tile);
                    if(ALPHA >= BETA)
                        break;
                }
            return ALPHA, BETA;
        }
             
        else{
            for(int tile = 0; tile < BOARD.length; tile++)
                if(isLegal(tile)){
                    makeMove(tile, 'O');
                    changeTurn();
                    ALPHA = Math.max(ALPHA, alphaBeta(tile, depth-1, ALPHA, BETA));
                    undoMove(tile);
                    if(ALPHA >= BETA){
                        BEST_COMPUTER_MOVE = tile;
                        break;
                    }
                }
            return ALPHA, BETA;       
        }
    }

  15. #15
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    You don't have to return two values from this function. You need to return the value of the move that this "virtual turn" would choose, which is based off the move that the next "virtual turn" would choose, which is what the recursion is for.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  16. #16
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    Sorry, but I don't understand what you mean :o

  17. #17
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    Quote Originally Posted by Zelaine View Post
    Sorry, but I don't understand what you mean :o
    I know, and that's why I think you need to spend some more time really understanding the algorithm. You might have to read more, even if it's not from class notes.

    Take a look at your pseudocode. It only ever returns a single value. Why do you think you need to return two? In other words, say you're in the middle of a recursive call to the function. Your function has somehow just returned two values. What are you going to do with them?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  18. #18
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    157
    Rep Power
    2

    Default Re: Alpha-beta pruning

    Take a look at your pseudocode.
    It's Wikipedia's pseudocode, not mine :)
    It only ever returns a single value. Why do you think you need to return two?
    This is hard to explain, but when, for example, the BETA value is returned the BETA value in the "upper" recursion isn't assigned that value, however the ALPHA variable is assigned the biggest value of its own and the value returned from the alphaBeta() function. So when we come to the comparison of ALPHA and BETA, BETA will still have its old value and not the value that was returned.
    What are you going to do with them?
    You just compare them as usual, the ALPHA and BETA values.

  19. #19
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,960
    Rep Power
    8

    Default Re: Alpha-beta pruning

    Quote Originally Posted by Zelaine View Post
    It's Wikipedia's pseudocode, not mine :)
    That might be the problem. It's more important to understand the algorithm than it is to convert the pseudocode, and the fact that you think you need to return two values suggests that you don't have a full grasp of the ideas behind the algorithm. You need to do that before you can start writing code.

    Quote Originally Posted by Zelaine View Post
    This is hard to explain, but when, for example, the BETA value is returned the BETA value in the "upper" recursion isn't assigned that value, however the ALPHA variable is assigned the biggest value of its own and the value returned from the alphaBeta() function. So when we come to the comparison of ALPHA and BETA, BETA will still have its old value and not the value that was returned.
    Again, I don't think your description matches how alphabeta works. Have you implemented a minimax algorithm? You might want to focus on that before worrying about alphabeta pruning.

    Quote Originally Posted by Zelaine View Post
    You just compare them as usual, the ALPHA and BETA values.
    Why do you compare them?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Hypersocket 0.0.1 Alpha
    By java software in forum Java Software
    Replies: 0
    Last Post: 06-23-2013, 11:01 PM
  2. Alpha Beta pruning help!
    By shahrukh1 in forum New To Java
    Replies: 1
    Last Post: 04-23-2012, 12:04 PM
  3. Pruning?? (N-Queens problem)
    By n00neimp0rtant in forum New To Java
    Replies: 1
    Last Post: 02-14-2010, 06:41 AM
  4. minmax with Alpha - Beta Pruning
    By Zosden in forum Advanced Java
    Replies: 6
    Last Post: 05-02-2008, 08:40 AM
  5. Alpha-beta algorithm, game tree
    By ljaf_1985 in forum New To Java
    Replies: 0
    Last Post: 03-28-2008, 04:21 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •