Python Deep Learning

Learning a value function

Let's get a bit more details on exactly how much computation the min max algorithm has to do. If we have a game of breadth b and depth d, then evaluating a complete game with min-max would require the construction of a tree with eventual d ^b leaves. If we use a max depth of n with an evaluation function, it would reduce our tree size to n ^b. But this is an exponential equation, and even though n is as small as 4 and b as 20, you still have 1,099,511,627,776 possibilities to evaluate. The tradeoff here is that as n gets lower, our evaluation function is called at a shallower level, where it may be a lot less good than the estimated quality of the position. Again, think of chess where our evaluation function is simply counting ...