2
$\begingroup$

I have been working on a problem to which I've applied alpha-beta pruning. While I got most of the answers right, there is one part I'm not quite getting:

enter image description here

Note that I've only provided a part of the tree I'm working on. Node $B$ starts with the following values:

$B$

  • $v = \infty$
  • $\alpha = - \infty$
  • $\beta = \infty$

Now, we push the alpha and beta values down to node $D$ from parent node $B$, and calculate its value:

$D$

  • $v = -\infty$
  • $\alpha = -\infty$
  • $\beta = \infty$

As leaf node $J$ has a value of $-7$, we push that back up to parent node $D$, changing node $D$'s value to $-7$ (as it is better than the old value of $-\infty$), and we also change the $\alpha$ value of node $D$ (as it is also better than the old value of $-\infty$).

New $D$

  • $v = -7$
  • $\alpha = -7$
  • $\beta = \infty$

We now push the value of $-7$ back up to parent node $B$, changing node $B$'s value to $-7$ (as it is better than the old value of $\infty$), and we also change the $\beta$ value of node $B$ (as it is also better than the old value of $\infty$).

New $B$

  • $v = -7$
  • $\alpha = -\infty$
  • $\beta = -7$

We now traverse down to node $E$ (and we don't prune it because node $B$'s value is NOT <= its $\alpha$ value), and we push the alpha and beta values down from node $B$, and calculate its value:

$E$

  • $v = -\infty$
  • $\alpha = -\infty$
  • $\beta = -7$

As leaf node $K$ has a value of $0$, we push that back up to parent node $E$, changing node $E$'s value to $0$ (as it is better than the old value of $-\infty$). Now, this is the point where my confusion lies. According to my understanding, at this point we would also set the $\alpha$ value of node $E$ to $0$ (as it is better than the old value of $-\infty$). However, the answer I received to this question specifies that we do NOT change the $\alpha$ value of node $E$, and rather leave it as $-\infty$.

Can someone please explain to me why this is the case?

UPDATE

I did not originally include the full subtree - this is it:

enter image description here

In this instance, only node M should be pruned. However, my question still stands as to why the answer did not update the alpha value of node E, as no pruning happened in that part of the tree.

$\endgroup$
0
3
+25
$\begingroup$

First, allow me to draw it for better visualization:

1. (α=-∞,β=∞) from B ➡ D

             B (α=-∞,β=∞)
          ↙ / \
(α=-∞,β=∞) D   E
           |   |
        -7=J   K=0
--------------------------
2. (v=-7) J ➡ D α=max(-7,-∞)=-7

             B (α=-∞,β=∞)
α=max(-7,-∞)/ \
(α=-7,β=∞) D   E
      ↖    |   |
        -7=J   K=0
--------------------------
3. (α=-7) D ➡ B β=min(∞,-7)=-7

               β=min(∞,-7)
             B (α=-∞,β=-7)
         ↗  / \
(α=-7,β=∞) D   E
           |   |
        -7=J   K=0
--------------------------
4. (α=-∞,β=-7) from B ➡ E

             B (α=-∞,β=-7)
            / \       ↓
(α=-7,β=∞) D   E (α=-∞,β=-7)
           |   |
        -7=J   K=0
--------------------------
5. (v=0) K ➡ E β=min(0,-7)=-7

             B
            / \ β=min(0,-7)
(α=-7,β=∞) D   E (α=-∞,β=-7)
           |   |    ⬈?
        -7=J   K=0
--------------------------


Update: I found this simulator. It behaves exactly like you describe:

http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html

  • Enter Tree Structure: 2 3 1 1 1 1 1
  • Enter Values -7 0 -4 -10

I noticed that it tries to update β on node K->E. As β=min(0,-7), it won't change.

It's possible to check their internal code by inspecting the page, to debug even further.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for the explanation Andre! I have taken note in my textbook that if a node will be cut, you don't have to update the alpha and beta values, but in this case, E is not being pruned. I will edit the post with some more information - apologies for not clarifying $\endgroup$ Aug 29 '21 at 11:57
  • $\begingroup$ OK, I'll check your updates later. $\endgroup$ Aug 29 '21 at 12:00
  • $\begingroup$ Updated with an interactive live example with the exact behavior as you stated. $\endgroup$ Aug 29 '21 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.