  Herein, we investigate the randomized complexity, which is the least cost
against the worst input, of AND-OR tree computation by imposing various
restrictions on the algorithm to find the Boolean value of the root of that
tree and no restrictions on the tree shape. When a tree satisfies a certain
condition regarding its symmetry, directional algorithms proposed by Saks and
Wigderson (1986), special randomized algorithms, are known to achieve the
randomized complexity. Furthermore, there is a known example of a tree that is
so unbalanced that no directional algorithm achieves the randomized complexity
(Vereshchagin 1998). In this study, we aim to identify where deviations arise
between the general randomized Boolean decision tree and its special case,
directional algorithms. In this paper, we show that for any AND-OR tree,
randomized depth-first algorithms, which form a broader class compared with
directional algorithms, have the same equilibrium as that of the directional
algorithms. Thus, we get the collapse result on equilibria inequalities that
holds for an arbitrary AND-OR tree. This implies that there exists a case where
even depth-first algorithms cannot be the fastest, leading to the separation
result on equilibria inequality. Additionally, a new algorithm is introduced as
a key concept for proof of the separation result.
