Correctness

To indicate that the evaluation algorithm is correct, but without a rigorous proof, an outline of a correctness proof will be given. Consider that since the evaluation algorithm is recursive, a induction proof on the size of the game tree is suitable. For the base case, where there is one chance node, evaluation proceeds by evaluation of the complete plans that terminate the game tree. The one with the maximum expected utility is returned as the minimax choice. Since this is just a matter of comparing a set of alternatives, it is clear that it is correct. For the induction step, suppose that every game tree of $n$ levels is evaluated correctly. If this is the case, then for a tree of $n+1$ levels, all of the recursive calls to minimax that are made in choosing edges for the play tree must choose the maximum utility alternative. Since the play tree is correct, and since the evaluation of the play tree is only a matter of taking a weighted sum over belief state outcomes, the algorithm is a correct one.