Results 1 to 19 of 19
Thread: Alphabeta pruning
 01062014, 12:36 AM #1Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Alphabeta 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 (* β cutoff *) return α else for each child of node β := min(β, alphabeta(child, depth  1, α, β, TRUE)) if β ≤ α break (* α cutoff *) return β (* Initial call *) alphabeta(origin, depth, ∞, +∞, TRUE)
Java Code:static int min(int SCORE1, int SCORE2){ if(SCORE1 < SCORE2) return SCORE1; else if(SCORE2 < SCORE1) return SCORE2; else return SCORE1; }
Thanks!Last edited by Zelaine; 01062014 at 12:53 AM.
 01062014, 04:59 PM #2
Re: Alphabeta pruning
It's a recursive call to the alphabeta() function. What does the alphabeta() function return?
How to Ask Questions the Smart Way
Static Void Games  Play indie games, learn from game tutorials and source code, upload your own games!
 01062014, 05:16 PM #3Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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; 01062014 at 05:18 PM.
 01062014, 05:23 PM #4
Re: Alphabeta pruning
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!
 01062014, 05:51 PM #5Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta pruning
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?
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.
 01062014, 06:51 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,457
 Blog Entries
 7
 Rep Power
 20
Re: Alphabeta 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,
Joscenosillicaphobia: the fear for an empty beer glass
 01062014, 07:53 PM #7Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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, depth1, 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, depth1, ALPHA, BETA)); undoMove(tile); if(ALPHA >= BETA){ BEST_COMPUTER_MOVE = tile; break; } } return ALPHA; } }
Last edited by Zelaine; 01062014 at 07:55 PM.
 01062014, 07:59 PM #8
Re: Alphabeta 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!
 01062014, 08:13 PM #9Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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.
 01062014, 08:23 PM #10
Re: Alphabeta pruning
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.
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!
 01062014, 09:13 PM #11Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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?
You might have to go back and read your textbook and class notes.
... which is why I think you should take a step back before writing another line of code.Last edited by Zelaine; 01062014 at 09:17 PM.
 01072014, 02:57 AM #12Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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; 01072014 at 03:00 AM.
 01072014, 10:52 AM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,457
 Blog Entries
 7
 Rep Power
 20
Re: Alphabeta 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,
Joscenosillicaphobia: the fear for an empty beer glass
 01072014, 12:50 PM #14Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta 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, depth1, 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, depth1, ALPHA, BETA)); undoMove(tile); if(ALPHA >= BETA){ BEST_COMPUTER_MOVE = tile; break; } } return ALPHA, BETA; } }
 01072014, 03:19 PM #15
Re: Alphabeta 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!
 01072014, 03:23 PM #16Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta pruning
Sorry, but I don't understand what you mean :o
 01072014, 03:32 PM #17
Re: Alphabeta pruning
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!
 01072014, 05:07 PM #18Senior Member
 Join Date
 Aug 2013
 Location
 Sweden
 Posts
 152
 Rep Power
 2
Re: Alphabeta pruning
Take a look at your pseudocode.
It only ever returns a single value. Why do you think you need to return two?
What are you going to do with them?
 01072014, 05:22 PM #19
Re: Alphabeta pruning
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.
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.
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

Hypersocket 0.0.1 Alpha
By java software in forum Java SoftwareReplies: 0Last Post: 06232013, 11:01 PM 
Alpha Beta pruning help!
By shahrukh1 in forum New To JavaReplies: 1Last Post: 04232012, 12:04 PM 
Pruning?? (NQueens problem)
By n00neimp0rtant in forum New To JavaReplies: 1Last Post: 02142010, 06:41 AM 
minmax with Alpha  Beta Pruning
By Zosden in forum Advanced JavaReplies: 6Last Post: 05022008, 08:40 AM 
Alphabeta algorithm, game tree
By ljaf_1985 in forum New To JavaReplies: 0Last Post: 03282008, 04:21 PM
Bookmarks