Alpha–Beta Pruning

Suppose you win a bet with your enemy [1], and he has to give you something as wager. However, he defines a strange rule:

There are several bags in front of you, each of which contains some stuffs of different value. But you can choose only one of them. Then he will choose one of the stuffs in that bag, and give it to you.

It’s obvious that you should choose the bag in which the least valuable thing is as valuable as possible. Because your enemy will of course choose the worst stuff in the bag for you.

So you open the bags one by one, and discard the bags in which the worst things are worse than your current choice. Clearly, the most valuable things in the bags count nothing to you.

Now suppose there are several smaller bags in these bags, and small bags contain the stuffs. The rule is a little different:

Firstly, you choose a bag. Secondly, your enemy chooses a smaller bag in that bag. Lastly, you choose a stuff.

According to this rule, you want to choose the best thing in the smaller bag, and your enemy wants to choose the bag in which the best thing is the worst among the best ones in all small bags. So at the first step, you have to choose the big bag in which the worst small bag is the best among those worst ones in all big bags.

Now you may use the Alpha-Beta Pruning technique. Assume that \alpha is the best value you have searched (the maximum among the minimuns). Any bag whose value is less than \alpha should be discarded. Assume that \beta is the worst value your enemy has searched (the minimun among the maximums). Any bag whose value is greater than \beta would be discarded by him.

The following pseudocode and animated pedagogical example are from Wiki [2].


Pseudocode

01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          for each child of node
06              α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
07              if β ≤ α
08                  break (* β cut-off *)
09          return α
10      else
11          for each child of node
12              β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
13              if β ≤ α
14                  break (* α cut-off *)
15          return β

 Example

Minimax_Example
Minimax with alpha-beta pruning

Minmaxab.gif(800 × 580 pixels, file size: 806 KB, MIME type: image/gif, looped, 117 frames, 15 min 45 s)


Reference

[1] Abramson, Bruce (June 1989). “Control Strategies for Two-Player Games”. ACM Computing Surveys 21 (2): 137.doi:10.1145/66443.66444. Retrieved 2008-08-20.

[2] Wikipedia: http://en.wikipedia.org/wiki/Alpha-beta_pruning

 

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.