Beyond win-loss game trees

The game tree evaluation algorithms we saw in class were focused exclusively on win-loss games: the outcome is always one of two possibilities.

Most real games are not this way; the outcome is any value among a spectrum of possibilities. Certainly "tie" is a third possibility in most of the kind of games we think of (chess, tic-tac-toe, Othello, checkers, ...). But game trees can also be used in games that involve betting and have monetary values for each possible outcome (leaf node). In such cases, the question becomes what is the largest sum (or best outcome) that can be guaranteed by a winning strategy, and how can we find it?

Use the randomized game tree evaluation algorithm we saw in class to come up with an algorithm to find the best-guaranteed-outcome strategy for a game with multiple output possibilities. You may assume that the branching factor is 2. Analyze the cost of your algorithm in terms of \(n\), which is the number of nodes in the graph, and incidentally is also a bound on the number of different outcomes from the game.

Hint: Use the idea of binary search

Hint: This kind of a game tree is called a minimax tree.