Search code examples
pythonartificial-intelligenceminimaxalpha-beta-pruninggame-theory

Tied root for Alpha Beta Pruning Algorithm

I am having trouble understanding why the alpha-beta pruning algorithm should not prune C here?

Here is my terminal output:

eval A
min 2 min1 -9223372036854775807 10.0
eval B
min 2 min2 10.0 10.0
*** FAIL: test_cases/q3/6-tied-root.test
***     Incorrect generated nodes for depth=3
***         Student generated nodes: A B max min1 min2
***         Correct generated nodes: A B C max min1 min2
***     Tree:
***         max
***        /   \
***     min1    min2
***      |      /  \
***      A      B   C
***     10     10   0

My understanding was that once B is evaluated, min2 will see that max will not pick anything lower than 10, therefore, even if a smaller value is found (x<=10) it would not make a difference. In this case, min2 would only be incentivized to look at C if B was greater than 10.

Thanks in advance

Solution

  • My understanding was that once B is evaluated, min2 will see that max will not pick anything lower than 10, therefore, even if a smaller value is found (x<=10) it would not make a difference.

    It's correct and can be verified with an online simulator (e.g. http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html or https://raphsilva.github.io/utilities/minimax_simulator/):

    tree_height=2;tree_number_nodes=6;Tree>0,0,2,1,-1000,393.75,30,-1000,1000,-1,-1,undefined,1,1,1,3,1000,225,295,undefined,undefined,0,-1,undefined,2,1,2,4,1000,562.5,295,undefined,undefined,0,-1,undefined,3,2,0,-1,10,225,560,undefined,undefined,1,undefined,undefined,4,2,0,-1,10,450,560,undefined,undefined,2,undefined,undefined,5,2,0,-1,0,675,560,undefined,undefined,2,undefined,undefined,<

    min2 would only be incentivized to look at C if B was greater than 10.

    Equally correct:

    tree_height=2;tree_number_nodes=6;Tree>0,0,2,1,-1000,393.75,30,-1000,1000,-1,-1,undefined,1,1,1,3,1000,225,295,undefined,undefined,0,-1,undefined,2,1,2,4,1000,562.5,295,undefined,undefined,0,-1,undefined,3,2,0,-1,10,225,560,undefined,undefined,1,undefined,undefined,4,2,0,-1,12,450,560,undefined,undefined,2,undefined,undefined,5,2,0,-1,0,675,560,undefined,undefined,2,undefined,undefined,<

    min2 must check C also if A is less than 10.

    Could it be a wrong test case?