Non-depth-first search against independent distributions on an AND-OR tree

Suzuki and Niida (2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Suppose that a positive real number r<1 is given, and let I(r) denote the class of all IDs such that the probability of the root having value 0 is r; if, among members of I(r), d is a maximizer of cost of the best algorithm then d is an independent and identical distribution (IID). (2) The same as above holds for the set of all IDs in place of I(r). In the case where non-depth-first algorithms are taken into consideration, the counterparts of (1) and (2) are left open in the above work. Peng et al. (2017) extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on ID d that the probability of the root having value 0 is neither 0 nor 1. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID d achieves the equilibrium among IDs then d has an optimal algorithm that is depth-first. In addition, we extend theorem 3 of Peng et al. to the case where non-depth-first algorithms are taken into consideration.