Victor M
Victor M

Reputation: 759

Minimax question regarding alpha-beta pruning?

Can someone explain to me why it is possible to eliminate the rest of the middle branch in this image for alpha-beta pruning? I am confused because it seems the only information you know is that Helen would pick at least a 2 at the top (considering if we iterate from left to right in DFS), and Stavros would absolutely not pick anything above 7. This leaves 5 possible numbers that the rest of the branch could take on that Helen could potentially end up picking, but can't because we've eliminated those possibilities via pruning.

enter image description here

Upvotes: 1

Views: 2837

Answers (2)

manlio
manlio

Reputation: 18962

Only:

  1. B → B ⇸ B
  2. C → C ⇸ C

are legal cuts.

Original tree

Changing the order of root moves (swapping B and C) would allow the cut in your picture:

Swapped moves

So... you're rightly confused!

For further experiments take a look at some online alpha-beta pruning simulator, e.g. http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html

Upvotes: 1

eligolf
eligolf

Reputation: 1878

Alpha-beta pruning is based on the assumption that both players play perfectly and always make the best possible move. I don't know the rules of the game in your example so I can't answer you specifically on this case, but I think this link gives you a good exmplanation of how it works generally: https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/.

Upvotes: 0

Related Questions