Game of Death

You are given a complete binary tree with \(4^n\) leaves.

Each leaf node is colored black or white.

There is a token at the root of the tree.

The game

You and Death take turns moving the token from the current node to one of its child nodes.

The game ends after 2n moves, when the token lands on a leaf node.

You move first, so Death gets the last turn.

Winning conditions

If final leaf is black -> you die.

If final leaf is white -> live forever.

Playing

We can game is deciding if we want to play.

Nodes at even levels are OR gates (root is level 0). Since you can choose any one of the gates, you need at least one move to a node where the traversal path is such that Death can only move to a white leaf node.

Nodes at odd levels are AND, Death can choose any path, if all his paths leaf to white leaf nodes, you will live forever.

Constraints

We have to use a randomized algorithm that determines if you can win in \(O(3^{3})\) time.

Definitions

We use \(T_{n}\) to denote the game tree of depth 2n.

We use \(v(T_{n})\) to denote the boolean value at the root of the tree \({T_{n}}\).

Notice that a tree Tn consists of 4 trees of depth \(T_{n-1}\).

Then,

$$ v(T_{n}) = (v(T^{0, 0}_{n-1}) \land v(T^{0, 1}_{n-1})) \lor (v(T^{1, 0}_{n-1}) \land v(T^{1, 1}_{n-1})) $$

Algorithm

Natural recursive algorithm, \(EvaluateTree(T_{n})\):

Randomly pick one side of the tree.

Randomly pick one subtree and evaluate its value.

If it is TRUE, we evaluate the other subtree on the same side.

If the other subtree is also TRUE, then we don’t care about the other subtree in OR.

If any of the subtrees are false, we turn to the other side of the tree.

If any of the subtrees on the other side are FALSE, we safely return FALSE.

Runtime analysis

n = 0 -> only leaf node, just takes 1.

TRUE tree: In this case, for the first subtree chosen, we choose the ‘correct’ side with probability 1/2. We then make 2 calls of \(EvaluateTree(T_{n-1})\).

On the other hand, the ‘bad’ side has at least 1 FALSE subtree.

We choose it with probability of at most 1/4. We have to make 4 calls.

Overall expected calls = 1/2 x 2 + 1/4 x 3 + 1/4 x 4 = 2.75 calls.

FALSE tree:

1/2 x 2 + 1/2 x 1 + 1/2 x 2 + 1/2 x 1 = 3

Overall calls is less than 3.

Hence \(E(T(n)) \leq E(T(n-1)) + O(1)\).