Constraints & Slackness Reasoning Exercises

post by johnswentworth · 2019-05-21T22:53:11.048Z · LW · GW · 3 comments

Contents

  Game Exercises
    Exercise 1: Deck-Building Game
    Exercise 2: 4X Game
    Exercise 3: Engine-Building Game
None
3 comments

Epistemic status: no idea if this will work at all for learning the relevant thought-skills. Please post feedback if you try any exercises, especially if you hadn’t internalized these skills already.

The goal of this post is to briefly explain and practice a very general thought-tool. If you've ever tried to hold off on proposing solutions [LW · GW], then sat there without any idea where to start, then this is the sort of tool which you may find useful. We'll start with a short example and explanation, then dive right into the exercises.

Here’s a reaction you may have used in high school or undergrad chem lab to synthesize aspirin:

(source)

Each mole of aspirin requires one mole each of salicyclic acid and acetic anhydride to produce.

Warm-up question: we start with one mole of salicyclic acid and two moles of acetic anhydride. Assuming the reaction runs to completion (i.e. as much of the reactants as possible are converted to aspirin), which will result in more total aspirin production: one extra mole of salicyclic acid, or one extra mole of acetic anhydride?

In the language of optimization/economics, we have two constraints:

1. the amount of aspirin produced is less than or equal to the amount of salicyclic acid available (in moles)
2. the amount of aspirin produced is less than or equal to the amount of acetic anhydride available (in moles)

In the case of our warm-up question, we would say that constraint 1 is “taut” and constraint 2 is “slack”. Once 1 mole of aspirin is produced, we cannot produce any more, because there is no “room left” in constraint 1 - just like a taut rope cannot be pulled further, a taut constraint can go no further. Conversely, just like a slack rope can be pulled further, constraint 2 has extra room - extra acetic anhydride left, which could produce more aspirin if only we had more salicyclic acid.

Key point: the slack constraint is completely and totally irrelevant to the amount of aspirin produced, so long as it remains slack: adding one additional mole of acetic anhydride will produce exactly zero extra moles of aspirin. If we want to maximize the amount of aspirin produced, then we should ignore the slack constraint (acetic anhydride) and focus on the taut constraint (salicyclic acid).

This idea generalizes: whenever we want to optimize something, we can ignore slack constraints. Only the taut constraints matter.

In more realistic situations, “constraints” usually aren’t perfectly binding. For instance, a real aspirin-producing reaction might not run all the way to completion - it might reach some equilibrium where there’s a little bit of both salicyclic acid and acetic anhydride in the solution, and adding either one will produce at least some extra aspirin. But even then, constraint 1 will be “more taut” than constraint 2 - one extra mole of salicyclic acid will produce a lot more extra aspirin than one extra mole of acetic anhydride. We can quantify this via marginal production (a.k.a. the gradient), but that’s not really the goal here.

The goal here is to build some intuition for recognizing which constraints in a problem are probably more taut or more slack, and using that intuition to make tradeoffs. In the real world, this usually requires a bunch of domain-specific knowledge, so we'll be using some made-up games to keep it simple.

Game Exercises

In these exercises, the rules of a game are laid out up-front. Identifying potential constraints/resources should be relatively easy; the focus is on predicting which constraints will be taut. The main question will be: what do you expect to be the main bottleneck?

Side notes: these exercises are intended for people not already familiar with the specific subject matter, so if you've never played Magic: The Gathering or Civilization V or whatever then don't worry. Feel free to post clarifying questions in the comments. If you post solutions or major hints in the comments, please rot13 them.

Exercise 1: Deck-Building Game

Consider a simplified deck-building combat game, along the lines of Magic or Hearthstone. You start each turn with five random cards from your deck, and three mana. Each card costs one mana to play, and does useful things: summons or boosts allies, damages your opponent or their allies, etc. On your turn, you can play as many cards as you like, until you run out of either cards or mana. At the end of your turn, any leftover cards get shuffled back into your draw pile, along with any cards you played.

Start each turn with 5 random cards and 3 mana. Each card costs 1 mana to play. At the end of your turn, all cards (both played and in hand) are shuffled back into your draw pile.

You have a choice between two cards to add to your deck:

• Energy card: gain 2 mana immediately (Note that it costs 1 mana to play)
• Draw card: draw 2 cards immediately

These are the only cards in the game which gain mana or draw cards, respectively.

All else equal, which of the two cards above would you choose? For each scenario below, identify relevant constraints, predict which constraints are taut/slack, and use this knowledge to pick your card. If your answer depends on something, say what (and quantify it if possible!).

1. The entire rest of the deck is copies of the Attack card
2. Full deck has size 25 cards, you have 2 Energy cards already, rest of the deck is Attack (Hint: you draw 5 random cards each turn. What constraint has the highest probability of being taut?)
3. Full deck has size 25 cards, you have 8 Energy cards already, rest of the deck is Attack
4. The rest of the deck is 50% Attack and 50% Defend. Depending on the turn, you want to either only attack or only defend - the other card is useless.
5. As previous, except 30% Attack and 70% Defend.
6. One card in your deck wins the game instantly. (If your answer depends on something, quantify it.)
7. There are roughly 4 different card types in your deck, with differing numbers of each, each suited to different situations.
8. As previous, except full deck size is 25 cards and you have 5 Draw and 2 Energy cards already.

Exercise 2: 4X Game

Next, let’s consider a simplified 4X game, along the lines of Civ (4X = explore, expand, exploit, exterminate). You start the game with your home base (fixed position) and one unit (mobile), located somewhere on a large and mostly-unrevealed map. The unit always starts at your home base, and comes in one of four types:

• Scout: fast, long sight range (good for exploration)
• Settler: can establish new bases (good for territorial expansion)
• Worker: builds improvements on your bases/territory (good for exploiting resources)
• Warrior: can fight other players and take their stuff (good for either offense or defense)

You can obtain more units by paying for them with resources. Resources are produced by the territory around your bases: in general, more bases => more territory => more resources => buy more units. However, different locations may produce more/different resources. Improvements (built by workers) will generally increase resource yield, but have diminishing returns: second or third improvements have less percentage impact than first improvements.

The base collects resources from its territory - five lightning and two heart resources. Different locations produce more/different resources, and the hex to the north produces no resources at all. Most of the map is unexplored, as indicated by “?”. The unit north-east of the base can move around, e.g. to explore the map.

Unless otherwise stated, you may assume that:

• Your home base produces whatever resources are needed to create any additional units, but not very quickly.
• There are no units except those belonging to the players (i.e. no “barbarian” units).
• Players usually start far apart.
• Win condition is to exterminate the other players, but the game is long enough that extermination usually isn’t directly relevant in the early game.

For each scenario below, you get to pick exactly one unit to start the game with. For each one, identify relevant constraints, predict which are taut (all else equal), and then pick a unit type. If your answer depends on something, say what (and quantify it if possible!), and at least try to eliminate some of the unit types.

1. Map is uniform (no location different from any other).
2. Sparse resources: most locations produce no resources.
3. Your starting location has unusually good resources.
4. You start right next to another player.
5. The map starts with one-time resource caches, picked up by the first unit to find them.
6. You do not know how close you start to other players.
7. The entire map, including other players’ bases, is revealed at the start.
8. The entire map, including other players’ bases and units, is visible throughout the game.
9. Improvements have increasing rather than decreasing returns.
10. There are hostile “barbarian” units scattered around the map which attack the players’ units.

Exercise 3: Engine-Building Game

Finally, we’ll look at a simplified engine-building game. Each player has some resources and some cards. On your turn, you draw four cards from the deck, and can purchase as many of them as you want (and can afford) using whatever resources you’ve accumulated. Each card does different things - some give an immediate one-time benefit (e.g. trading one resource for another), others give long-term benefits (e.g. producing resources every turn or every time something specific happens), and some give the player new capabilities (e.g. the ability to trade one resource for another indefinitely).

To keep it simple, we’ll assume that:

• You’re usually not directly competing with other players for particular cards.
• The first player to amass a certain amount of resources wins.

In each scenario below, pick which cards to buy (or decide not to buy any). For each one, identify relevant constraints, predict which are taut (all else equal), and then pick cards. If your answer depends on something, say what (and quantify it if possible!), and at least try to eliminate some of the cards.

1. On your first turn, you have a choice between two types of cards: Machines, which produce one resource per turn, and Machine Shops, which produce one Machine per turn. You can spend all your resources to buy either three Machines or one Machine Shop. Which do you pick? If your answer depends on something, quantify it.
2. Same as previous question, but it’s late in the game rather than your first turn.
3. There are two different resources in the game: diamonds and rubies. You have a choice between a Machine which produces two diamonds per turn, or a Machine which produces one resource of your choice per turn. All resource-producing Machines are quite common in the game.
4. Same as (3), except ruby-producing Machines are rare.
5. Same as (3), except diamond-producing Machines are rare.
6. Same as (3), except there are six resources in the game rather than two.
7. Same as (3), except you can trade with other players.
8. Same as (3), except you can trade with other players and the other players already have lots of diamond production.
9. Same as (3), except you can trade with other players and the other players already have lots of ruby production.

3 comments

Comments sorted by top scores.