The row player's unique best response to is and to is . The column player's unique best response to is and to is . Thus the pure Nash equilibria are and .
For a fully mixed equilibrium, let and . Row-player indifference requires
Column-player indifference requires
Both probabilities lie strictly between zero and one, so these indifference conditions make both supported actions best responses. Hence the remaining equilibrium is
Its expected payoffs are . There are no other partly mixed equilibria: if either player is pure, the other's best response is unique, forcing both to be pure. If both mix, the displayed linear indifference equations uniquely determine their probabilities. The row player's equilibrium mixture differs from its maxmin mixture in part (a); these are different optimization criteria in this non-zero-sum game.
Let be the row player's probability of . Its expected payoffs against and are and . The security level payoff is therefore
The first line decreases and the second increases, so their intersection is optimal: gives . Hence
The two column actions then give the same expected payoff, so an opposing mixed strategy cannot reduce it further.
Write , where . For three distinct sites , the left, middle and right firms receive respectively
These follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy , the final entrant compares at , at , and at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.
First suppose opens at the central site . If chooses , the final entrant's best possible payoffs on the left, right and interior are at most , exactly , and at most , respectively. Hence 's unique best response is . The resulting payoff to is , uniquely maximized on that side at . Reflection gives the other optimal choice , followed by . Under either choice, receives only . Any mixture of the tied optimal second-mover choices has the same consequence.
Now let deviate to . If chooses , the unique final best response is , yielding at most . If chooses , the unique final best response is , yielding only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:
  • If , can choose . The final entrant compares , and , so uniquely chooses . This gives exactly .
  • If , can choose site four after chooses two. All three remaining sites are final-mover best responses; they give payoffs five, four and three. Thus guarantees at least three, exceeding the excluded choices' payoff two.
Accordingly, in every subgame perfect equilibrium continuation after , the second mover must choose a site . This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.
For any such , every legal final site gives at least three. If lies left of , then is the middle firm and receives . If lies right of , then is the left firm and receives . Thus the deviation gives at least , against every subgame-perfect continuation, whereas the central opening gives it .
Figure 1.
Final-mover ties and the second mover's guarantee after the first firm deviates on a nine-building street
. Details.
In this original example, a final-mover tie produces the line segment for : its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing , so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.
A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.
There is no pure Nash equilibrium. If the firms choose different sites, serves at least its own building, so receives less than . By moving onto 's site, makes every customer equidistant from the two shops and wins every tie, obtaining . Thus any separated profile has a profitable unilateral deviation by .
At any co-located profile, receives zero. It can move to a different site and capture at least that site's customers, obtaining at least two. Thus every co-located profile also has a profitable unilateral deviation. These cases exhaust all pure strategy profiles.
Both players can guarantee by part (d), so at any Nash equilibrium each must receive at least . Their payoffs sum to , forcing both equilibrium payoffs to equal .
Moreover, an equilibrium action must itself have the maxmin guarantee . If a player's chosen action allowed an opposing response that reduced its payoff below , that response would give the opponent more than , a profitable unilateral deviation. Thus both equilibrium sites belong to the central set identified in part (d).
Conversely, if both choose from that central set, each chosen action guarantees . Neither can improve above , because the other player's fixed central action still guarantees the other player . Consequently, all pure Nash equilibria are
For even , this includes both co-located central profiles and both orders of the two distinct central sites.
If a player chooses site , the opponent can co-locate and hold its payoff to . Among opposing sites to its right, the lowest payoff is obtained against , giving . Among opposing sites to its left, the lowest is against , giving . Thus the pure-action security level payoff is
The expression remains valid at an endpoint, where the missing-side term is redundant. It reaches its largest possible value exactly when . Hence the pure maxmin strategies are
Reflection gives the same answer for the other player.
Yes to both questions, for both players. Site one is strictly dominated by site two. Against opposing site , the payoff difference is
Every difference is positive for . By reflection, site is strictly dominated by site . These endpoint actions are therefore also weakly dominated strategies, since strict dominance is stronger than the requirement of being no worse everywhere and better somewhere.
Neither player has a weakly dominant strategy among its pure strategies. Against an opponent at site one, the unique best response is site two, yielding . Co-location yields only , and moving further right reduces one's payoff. Against an opponent at site , the unique best response is , by reflection. For , these two sites differ. No single pure strategy can therefore be a best response to both opposing actions, as a weakly dominant strategy would require.
The players are the two chains, each with the set of pure strategies . A strategy profile gives the sites of and . For later use, write the first player's payoff for a general street size as
When , count customers to the left of , assigning value one rather than two to any midpoint customer. This gives whether the midpoint is an occupied building or lies between buildings. The other player receives . At co-location, every customer's value is split, giving each.
For , the payoff matrix for is
Rows and columns are indexed by sites ; the full ordered payoff pair in cell is . This discrete location game is a constant-sum game.
Read the satisfying assignment in increasing time order. In layer , output the unique ground action whose occurrence Boolean variable is true, or output nothing if all are false. Discard idle layers. The result is a sequence of at most actions.
For correctness, the layer-zero planning fluents are exactly the actual initial state. The action precondition axioms make the selected action applicable, while the successor-state axioms give precisely its add/delete update; the action exclusion axioms prevent simultaneous competing actions. By induction, every following time layer is the real state reached by the decoded prefix. The final goal formula therefore proves that the extracted plan reaches both required goals.
Conversely, execute any valid plan of length at most , assign each layer its actual fluent values and pad with idle layers. These values satisfy every component of . In this instance, decoding the three-action trajectory in part (d) gives a model at and at every larger horizon after padding; direct state-space and propositional checks find no model for .
Use a sequential SATPlan encoding with times . The fluent universe is
There are nine support Boolean variables and three clearance Boolean variables per time layer. Static block types, parameter inequalities and permanent table availability are handled during action grounding. For each well-typed ground action from parts (b)–(c), introduce an occurrence Boolean variable for . Allow at most one action per layer, including no action, so that a horizon of encodes at most physical actions.
The complete initial-state formula is
Every well-typed fluent not initially true is explicitly false. The final goal formula is simply . Leaving unrelated final facts unconstrained is appropriate; leaving unrelated initial facts unconstrained would introduce imaginary starting states.
For each , include all action precondition axioms , after removing static true conditions. For example,
The precondition axiom for similarly requires .
For every fluent , let be the logical disjunction of actions at adding , and the logical disjunction deleting it. Include the successor-state axiom
It combines action effects with the frame axiom, preventing unsupported changes. A fully grounded example is
Apply the same construction to every support and clearance fluent, using the exact add/delete lists. If no action occurs, both effect logical disjunctions are false, so all fluents persist.
The sequential action exclusion axioms are for every pair of distinct grounded actions . For example,
forbids selecting those two occurrences together. Do not add a requirement that some action occur in every layer: that would remove idle padding and change “at most ” into an exact-length requirement. One may additionally include true planning state invariants, such as a block having at most one support and a block support carrying at most one block; the unlimited table must be exempt from the latter restriction.
Finally, conjoin , , and all precondition, successor and exclusion formulas over the layers to obtain . It is a propositional formula; if a solver requires conjunctive normal form, use a satisfiability-preserving Tseitin transformation with auxiliary Boolean variables. The equivalence between this encoding and real action sequences follows from sequential SATPlan correctness: a satisfying assignment induces exactly the stated STRIPS trajectory, and every sufficiently short valid plan supplies such an assignment.
Let and . The familiar obstruction is the Sussman anomaly for restricted goal-by-goal planning.
If one first constructs the obvious isolated plan for , it moves off and then puts on . Now is not clear, so achieving requires taking off , undoing . If one first achieves the isolated directly, it puts on while is still on . To free , it must move , which first requires moving off , undoing . Therefore neither ordering of those independent subplans works while protecting the first achieved goal.
The literal concatenation-only definition in the question is too weak to imply the requested impossibility. A valid plan is
The first two actions constitute a plan for from the original state, and the last action is a plan for from the resulting state, preserving . Thus this is itself a concatenation of the stated kind. Its crucial first action prepares for the later subgoal before completing .
Figure 1.
Support relations along the derived three-action blocks world plan
. Details.
The green-outlined cells mark achieved goal facts. This original solution timeline makes the distinction explicit: independent goal-directed subplanning fails, but unrestricted concatenation does not. To obtain the intended impossibility claim, “non-interleaved” must also forbid anticipatory preparation or require the isolated subplans described above. No source input is missing; the issue is the breadth of the printed definition.
Ground as distinct blocks. For , take
Thus a clear block leaves its block support, makes that support clear, and joins the unlimited table. persists, and table availability is never deleted. Requiring to be a block excludes a redundant table-to-table action. The static predicates need not be stored as time-varying planning fluents.
Use direct-transfer STRIPS actions: one action includes picking up a block and putting it down again. There is no separate holding state. Ground as distinct blocks and as a support, either a block or the table, with and .
For , take
The preconditions ensure that can be picked up and that the destination has room. Moving it frees a block source and occupies the destination, while persists. When , table availability remains true; its redundant addition is simply omitted. Since is fixed in each ground action, this case distinction constructs ordinary add lists rather than introducing conditional action effects. The search transition model is .
Write for the table. The positive initial planning fluents read from the original figure are
The static type facts are , and ; the table is not a block. With an explicit table-availability predicate, take to be permanently true. Under the closed-world assumption, all other well-typed initial planning fluents are false; in particular, is not clear.
The goal is the partial-state conjunction
It need not redundantly prescribe every final fact. With only these three blocks and a valid blocks world state, the completed stack also places on the table and leaves clear.
The depth assertion is false. Each move occupies one new square, so the general bound is , not . On a board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length , since knight moves always change colour.
The opponent-independent “best possible move” assertion is false. Minimax search maximizes the guaranteed utility against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning strategy is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax strategy guarantees its minimax value, not that its root choice is best for every possible opponent behavior.[ref]
The storage assertion is false for the usual minimax implementation. Here the maximum branching factor is and maximum depth is . A conventional depth-first search retaining pending successors uses the usual search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to stack frames plus board storage; neither accounting should confuse the board side length with its squares.
The winning-strategy assertion is true. The game is finite, has perfect information, alternates two players, and has no draw under the normal-play convention. A terminal position is losing for the player to move. By backward induction, a nonterminal position is winning exactly when at least one legal move reaches a losing position; otherwise it is losing. This labels every position, including the initial board, so exactly one of the two players has a winning strategy.
A useful local search state is any occupied-square subset , allowing temporary attacks. Let count unordered attacking pairs and . Maximize
ACTIONS can offer insertion at an empty square, deletion of an occupied square, and relocation of one knight to an empty square. RESULT is respectively , , and . Insertions and deletions alone connect the whole state space; relocation is a useful additional proposal.
Every conflicting state has , whereas the empty board has score zero. Every conflict-free state has score exactly its knight count. Hence every global maximizer is a maximum-size nonattacking placement. If a knight participates in conflicts, deleting it changes the score by , so a positive-conflict local stopping point cannot persist when improving deletions are considered.
From a random board, choose score-improving moves, with random restarts or occasional non-improving proposals to escape poor conflict-free local optima. A maximal placement is not necessarily a maximum placement: accepting only legal insertions can get stuck too early. This objective function defines the intended optimization precisely; a finite heuristic run still gives no general global-optimality certificate.
Backtracking assigns one variable at a time and abandons a partial assignment as soon as it cannot extend to a solution. With forward checking, placing a knight deletes its occupied and attacked squares from every remaining knight's constraint domain. An empty constraint domain rejects the branch immediately; stronger constraint propagation, such as arc consistency, can detect additional incompatibilities among future choices.
This combines early rejection with depth-first storage. It retains the current assignment and domain changes rather than the entire breadth-first layer of partial placements. A direct knight-variable implementation uses space for explicit domains, plus its assignment and restoration trail, instead of an exponentially large breadth-first search search frontier. Propagation has a computational cost and does not guarantee improvement on every input, but often prevents exploration of vast inconsistent subtrees.
The minimum remaining values heuristic selects an unassigned variable with the fewest currently legal values, exposing the likeliest failure first. The degree heuristic selects a variable constrained to the largest number of other unassigned variables, often breaking minimum remaining values heuristic ties. Degree is measured in the remaining constraint graph, not by counting assigned neighbors. In the symmetric knight-variable encoding the remaining degrees can all tie, so the heuristic need not discriminate there.[ref]
Use the knight-variable representation and build a placement one knight at a time. The initial state is the empty placement. An action places the next knight on an empty square attacking no previously placed knight; the search transition model appends that square. The goal test is that knights have been placed. Each action adds exactly one, so any solution has depth .
Put . At depth , there are at most choices, hence branching factor at most . A coarse search tree size bound is . Keeping the shrinking choice count gives the sharper bound
where is a falling factorial. This counts ordered placements before attack pruning.
For a full expansion down to depth , the number of depth- leaves is at most , or approximately when is small relative to . If denotes the number of legal unlabelled -knight placements, the exact number of legal depth- leaves is . There can also be earlier dead-end leaves: a legal placement may leave no further nonattacking square. Writing for the number of inclusion-maximal legal -knight placements, the fully explored pruned tree has
leaves. Its leaf count is still at most the unpruned , since each early leaf replaces a disjoint nonempty subtree of the unpruned tree. Breadth-first search that stops at its first goal can construct less of the last layer; if no solution exists, it exhausts the reachable partial placements.
Identifying different insertion orders changes the representation. With a state that is an unlabelled set of occupied squares and repeated-state elimination, the corresponding depth- state bound is , with legal goal states. The factorial and binomial bounds refer to these different representations, not competing counts of the same tree.
Let be the board squares and let mean that the absolute coordinate differences are or .
One variable per knight. Use , with each constraint domain equal to . For every pair , require
Every satisfying assignment places distinct nonattacking knights, and any such placement gives an assignment after labelling its knights. This has only variables and binary constraints, but domains of size . Relabelling the knights gives assignments for the same unlabelled board, so the representation contains considerable redundancy.
One Boolean variable per square. Use for every . Impose the cardinality constraint
and for every knight-attack pair impose . There are variables, each with a two-element constraint domain, and only local attack restrictions, because each square attacks at most eight others. The single counting constraint is a global constraint, not a binary constraint.
The square encoding avoids knight-label redundancy and has sparse local attack relations; the knight encoding uses fewer variables when is small and makes single-knight moves natural. Both are exact representations of the nonattacking knights problem. Neither may impose one knight per row: several knights can legally share a row.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact