1
$\begingroup$

I'm taking a course 'Introduction to AI' and, in one of the tutorials, it was written that when pruning the game tree using $\alpha$-$\beta$ boundaries, the number of nodes that will be developed, when using random sort function for the children (i.e., in the average case) will be $$ O(b^{3d/4})$$.

Since the proof is not in the scope of the course we weren't given one at the tutorial, so I tried looking for the proof online, but couldn't find anything, and I didn't think of anything myself. I wondered whether someone could give me a lead or refer me to some reading material that shows the full proof?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I also found this claim in section 5.3.1 (p. 169) in Norvig and Russell's book (3rd edition), but there's also no proof. They just say that this holds for "moderate $b$". $\endgroup$
    – nbro
    May 13, 2021 at 12:04

0

Reset to default

You must log in to answer this question.