1. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## 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. ## Re: Alpha-beta pruning

It's a recursive call to the alphabeta() function. What does the alphabeta() function return?

3. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## 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. ## Re: Alpha-beta pruning

Originally Posted by Zelaine
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.

5. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

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

7. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

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

9. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## 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. ## Re: Alpha-beta pruning

Originally Posted by Zelaine
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.

Originally Posted by Zelaine
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.

11. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## 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. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

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

14. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

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

16. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## Re: Alpha-beta pruning

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

17. ## Re: Alpha-beta pruning

Originally Posted by Zelaine
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?

18. Senior Member
Join Date
Aug 2013
Location
Sweden
Posts
148
Rep Power
0

## 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. ## Re: Alpha-beta pruning

Originally Posted by Zelaine
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.

Originally Posted by Zelaine
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.

Originally Posted by Zelaine
You just compare them as usual, the ALPHA and BETA values.
Why do you compare them?

#### Posting Permissions

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