1
$\begingroup$

I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to determine next best move in combat scenarios in StarCraft game play. Section 3.2 (which probably is necessary to understand my question) is the part I am having trouble with, where he talks about approximating a combat (where simultaneous moves occur) with a version where alternating move occur. This allows him to use minmax trees and alpha-beta search.

The part I don't understand is when he describes how building the minmax tree gives an advantage to one player, while a maxmin tree gives an advantage to the other player. For one, his diagram labels the tree where "max" goes first as "maxmin", but his text (and wikipedia :P) describe the tree where max goes first as "minmax". Perhaps that is just a mislabelling.

The main part I am confused about is when he goes on to say:

Proposition 1: For stacked matrix games G, we have $$mini(G) \leq Nash(G) \leq maxi(G)$$

My understanding of this is that $Nash(G)$ is the real final game state taking into account simultaneous moves. Then $mini(G)$ is the final game state if we approximate with MAX moving first, and $maxi(G)$ is the final game state if we approximate with MIN moving first. Besides the Nash equilibrium stuff, which is a bit beyond my education so far, I don't understand how the inequality $$mini(G) \leq maxi(G)$$ can be true. Below are 4 examples. The leaf node values come, I believe, from an evaluation function of that game state's value to MAX:

enter image description here

The two on the left are maxmin, meaning MIN goes first. The two on the right are minmax, with MAX going first. The top pair contains one set of leaf node values that lead to $$5=maxi(G) \lt mini(G)=8$$ This goes against the proposition above. However, the bottom pair contain a different set of leaf node values that lead to $$4=maxi(G) \gt mini(G)=3$$ Here the proposition seems to hold. I believe I could also construct a scenario where $mini(G) = maxi(G)$.

What am I missing here? Is there really a hard relation between $mini(G)$ and $maxi(G)$ or doesn't it just depend on the leaf node values?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function.

That said, the source of your problem is a confusion about which choices are available to each player when it is their turn. Consider the left-hand side of your first example: writing this in matrix form, each player gets to choose between (say) $0$ and $1$, with payoffs $p(\text{minchoice},\text{maxchoice})$ given by

$p(0,0)=3, p(0,1)=5, p(1,0)=9, p(1,1)=8.$

The tree then represents the fact that if min plays $0$, max gets to choose between $p(\mathbf{0},0)=3$ and $p(\mathbf{0},1)=5$, and if min plays $1$, max gets to choose between $p(\mathbf{1},0)=9$ and $p(\mathbf{1},1)=8$.

However, if max plays first, the situation is changed: If max plays $0$, the choices for min are $p(0,\mathbf{0})=3$ and $p(1,\mathbf{0})=9$; if max plays $1$, the choices for min are $p(0,\mathbf{1})=5$ and $p(1,\mathbf{1})=8$.

This means that the right tree should be $((3,9),(5,8))$ instead of $((3,5),(9,8))$, for a maxmin of $5$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, so this means the grouping of the leaf node values is not arbitrary? It depends on the ordering of the players? $\endgroup$
    – xdhmoore
    May 1, 2016 at 22:30
  • 1
    $\begingroup$ @xdhmoore exactly, for example the $5$ is reached by going first left, then right if min plays first, but going first right, then left if max does. $\endgroup$
    – Klaus Draeger
    May 2, 2016 at 7:25
  • 2
    $\begingroup$ @xdhmoore, one way to help see this is to label the strategies. Say the max player is picking between $A$ and $B$, while the min player picks between $C$ and $D$. Now label each leaf node by which strategies reach it. $\endgroup$
    – usul
    May 2, 2016 at 20:41
  • 1
    $\begingroup$ @usul, thanks, that gave me the last push I needed. So, my trees are valid, but they are the expression of 4 different problems instead of 2. The two in the top row are not the same problem because the top right is not a mere player order shift. It also switches what choices are given to the players. Klaus Draeger's (3, 9, 5, 8) would be the correct ordering for the top right leaf nodes that is equivalent to the top left tree. $\endgroup$
    – xdhmoore
    May 3, 2016 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.