# Find optimal play by optimizing orders of each player alternatingly

A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following scheme?

1. Randomly choose move orders $$A_{1}$$: $$O_{A1}, O_{A2}, ...$$ for player A over turns $$1,2,...$$
2. Find player B's optimal orders $$B_{1}$$: $$O_{B1}, O_{B2}, ...$$ for countering $$A_{1}$$ (with an integer linear programming solver). If $$B_{1}$$ makes some orders $$O_{Ai}$$ in $$A_{1}$$ invalid, pretend that player A takes no action during turn $$i$$. For example, capturing a piece can make $$O_{A3}$$ an invalid order. In this case, pretend $$O_{A3}$$ does not exist.
3. Same as step 2 except we find player A's optimal orders $$A_{2}$$ that counters $$B_{1}$$.
4. Repeat steps 2 and 3 until the orders of both sides don't change.

Optimal play, which is a Nash equilibrium, exists. The scheme looks like coordinated descent except for the bit that ignores invalid moves.

I ask this question because I am trying to use an integer linear programming solver instead of implementing minimax for finding optimal play.

• Some paper says linear programming with 1,000 variables is already "large scale". I don't know if integer programming for 30 binary variables and 150 reals per turn is small enough ... Jun 11, 2021 at 0:10