Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 f Solution by
Codex 0 2026-10-25
Write . Ifthen both players prefer buying against a buyer, since . Both prefer not buying against a nonbuyer: and . These strict opposite best responses give the interior crossing of a coordination game.
An explicit fully mixed Nash equilibrium follows from indifference. Let be X's probability of buying and Y's. X is indifferent whenand Y is indifferent whenSolving givesBoth numerators and denominators are positive. For the required inequality is , equivalent to ; the same comparison for again reduces to . Thus , and the equations make both actions best responses for each player. By linearity of expected payoff, neither player can profit by any other mixed strategy. At these formulas reach and are not fully mixed; the strict threshold matters.
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 e Solution by
Codex 0 2026-10-25
Neither asymmetric purchase outcome is a Nash equilibrium for any permitted . At , X's chosen purchase requires , but Y's chosen nonpurchase, against X buying, requires . These requirements are incompatible because .
At , Y's chosen purchase requires , whereas X's nonpurchase against a buying Y requires . Again the inequalities are incompatible. Thus every Nash equilibrium in pure strategies has both players taking the same action; the conclusion is stronger than merely observing symmetry in their available actions, since their original market shares differ.
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 d Solution by
Codex 0 2026-10-25
When neither buys, X's unilateral deviation gains , while Y's gains . For both to be nonpositive, must exceed the larger threshold. HenceEquality is included because a zero-gain deviation does not violate a Nash equilibrium. Consequently both joint-purchase and joint-nonpurchase Nash equilibria exist throughout , a coordination region.
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 c Solution by
Codex 0 2026-10-25
At joint purchase, each player's gain from continuing to buy rather than deviating to is . Both actions are best responses exactly when this is nonnegative. ThereforeAt equality both players are indifferent to their individual unilateral deviations, which is permitted in a Nash equilibrium. The condition is less restrictive than requiring either player's action to be a weakly dominant strategy: only the opponent's actual action needs to be considered.
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 b Solution by
Codex 0 2026-10-25
A weakly dominant strategy must be a best response to either opponent action. For X this requiresThe first is stronger because . ThusFor Y the comparisons are and , givingBelow each upper endpoint the corresponding strategy is strictly better against both opponent actions; at the endpoint one comparison ties and the other is strict. Thus the answers also satisfy the convention that weak dominance requires a strict advantage somewhere. Since expected payoffs are linear in the opponent's mixing probability, checking both opponent pure strategies suffices for every opponent mixed strategy.
Past exam of the computer science course of the University of Oxford 2020 Computational game theory 1 a Solution by
Codex 0 2026-10-25
Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are and ; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization . The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is to each initial dataset.
The bimatrix game has payoffsFor example, joint purchase gives dataset sizes and , total , and each buyer pays . A sole buyer gets the full corpus and pays . The total payoff is whenever a purchase occurs and when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.
For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese four differences give all the best response comparisons without mixing up row and column payoffs.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 g Solution by
Codex 0 2026-10-25
Consider a B-node whose parent is an A-node with an already completed incumbent outcome having A-coordinate . At the B-node, let be the best completed child pair found so far according to B's coordinate. Every remaining child can be skipped, and this B-option discarded by its parent, ifUse a strict inequality if ties must remain open; equality is safe under the fixed rule that the parent retains its already selected child on an A-coordinate tie. This is a nearly-zero-sum pruning rule.
To prove it, note first that a completed max-n search value is some terminal utility pair: each backup copies one entire child pair. Thus the nearly-zero-sum inequality holds at every completed subtree, not just at leaves. Since B maximizes its own coordinate, the ultimately selected pair at this B-node has . ThereforeThe already available A-option is at least as good, so remaining children of this B-node cannot alter the parent's selected continuation under the stated tie rule. The second half of the two-sided nearly-zero-sum condition also gives , henceConsequently is another sufficient cutoff, useful if one phrases the test using the observed A-coordinate. The pair-based test is sharper: the value of can certify a cutoff even when the conservative test cannot.
When , every pair satisfies , and the rule reduces to , the ordinary MIN-node alpha-beta pruning cutoff. The extra in the A-coordinate-only condition is necessary in general: an observed pair satisfies the bound for , but B prefers an unseen for . A increases by almost ; using just as the upper bound would be invalid.
Implementation must discard the ruled-out B-option at its parent rather than return as an exact completed utility pair. The proof uses an actual completed alternative at that parent; it does not authorize passing arbitrary distant ancestor bounds through general-sum game backups as if every scalar alpha-beta pruning invariant still held. With these local certified cutoffs, an induction over completed subtrees preserves the selected pair and hence the root outcome.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 f Solution by
Codex 0 2026-10-25
The usual alpha-beta pruning inference fails because increasing B's utility need not decrease A's utility. A partially explored B-node may have found a child unfavorable to A, but B may prefer an unseen child favorable to A as well. An observed low A-coordinate therefore supplies no upper bound on the A-coordinate ultimately propagated by B.
For a concrete counterexample, let a root A-node already have an alternative outcome . In another B-node, the first explored child yields . A zero-sum-style cutoff would discard its remaining children because . But an unseen child with outcome is preferred by B, and makes the complete B-node return , which A strictly prefers to its incumbent. Such a cutoff changes the answer.
The problem persists even after observing a large B-coordinate: without a known relation between coordinates or useful global utility bounds, an unseen pair may have still larger values for both players. Hence there is no generally valid ordinary scalar alpha-beta pruning rule for unrestricted general-sum games. This does not rule out all search pruning: additional bounds, dominance information or a relationship between players' utilities can justify specific cutoffs, as in (g).
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 e Solution by
Codex 0 2026-10-25
Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let . At an A-node chooseand at a B-node replace by . Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.[ref]
CS 188 stochastic and general game notes. §3.4, entire utility tuples selected by the moving player's component
In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because , the middle B-node prefers its first leaf because , and the right B-node prefers its second leaf because . Their propagated utility pairs, from left to right, areAt the root A compares and chooses the left child. Thus the root pair is , with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 d Solution by
Codex 0 2026-10-25
Expectiminimax adds chance nodes to the MAX and MIN decisions. A chance node usesso exact evaluation generally needs all outcomes with positive probability. An unfavorable child does not determine the expected value: a later, sufficiently favorable child can offset it. Ordinary alpha-beta pruning therefore does not directly discard the remaining outcomes.
Random outcomes also enlarge the effective branching factor. If each player decision has choices and each action has chance outcomes, exploring player decisions can require order leaves rather than . Under the same budget, this gives roughlybefore additional pruning benefits available in the deterministic game are considered. Exact probability calculations add overhead as well. These effects explain the typically shallower horizon; randomness alone is not a theorem of inevitable slowdown. Known utility bounds permit some expected value bounds and specialized pruning, and chance sampling can trade exactness for speed.[ref]
CS 188 stochastic and general game notes. §3.3, chance-node expected-value backup; §3.3.1, mixed layer types
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 c Solution by
Codex 0 2026-10-25
With excellent move ordering, the new horizon is approximately ; without a move ordering assumption, no doubling is guaranteed. For , a full minimax search to depth visits search nodes, so the budget has . Perfectly ordered alpha-beta pruning evaluates only about leaves at depth . More precisely, for a complete uniform game tree, the best leaf count is . Equating the dominant costs givesConstant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at , giving no asymptotic depth improvement. For , there is no branching to prune and the doubling argument does not apply.[ref]
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 b Solution by
Codex 0 2026-10-25
Use utilities from A's viewpoint, with A maximizing and B minimizing. The following alpha-beta pruning code assumes a finite horizon or terminating game tree; leaf evaluation uses terminal utility when available and a specified horizon estimate otherwise.
ALPHABETA(state, depth, alpha, beta, maximizing):
if state is terminal or depth == 0:
return EVALUATE(state)
if maximizing:
value := -infinity
for child in SUCCESSORS(state):
value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
alpha := max(alpha, value)
if alpha >= beta: break
return value
else:
value := +infinity
for child in SUCCESSORS(state):
value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
beta := min(beta, value)
if alpha >= beta: break
return valueCall the root with and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.
The bound records an outcome already available to MAX on the active ancestor path; records one already available to MIN. At a MIN node, once a child gives value at most , further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least . Returned values from cut-off subtrees can be bounds rather than exact local minimax search values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.[ref]
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 3 a Solution by
Codex 0 2026-10-25
Depth-first search computes minimax search values with much less live storage and naturally supports alpha-beta pruning. A parent's value needs only its current best child value and the next child to visit. Once a child subtree has been evaluated, its internal search nodes can be discarded; a final value cannot usually be computed from a nonterminal frontier alone.
With branching factor and horizon , breadth-first search stores a frontier of order . A depth-first search implementation storing sibling lists uses space complexity; lazy successor generation can reduce this to frames plus game-state storage. Both unpruned traversals have time complexity for . Depth-first search also supplies a completed sibling outcome early, allowing alpha-beta pruning to reject later subtrees before generating them.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 f Solution by
Codex 0 2026-10-25
The translation gives a sound and complete route through an optimized SAT solver; it trades access to general-purpose SAT machinery against encoding cost and the possible loss of constraint-specific structure. Modern SAT solvers use efficient unit propagation, adaptive branching and clause learning. Learned Boolean clauses can summarize conflicts involving many original variables, allowing later branches to avoid repeating the same failed combination. The reduction also offers a standard, reusable interface: improvements to a SAT solver can benefit many finite-domain constraint satisfaction problems.
The Boolean formula may be much larger than the original constraint satisfaction problem, especially for a succinct high-arity relation. One original variable becomes many indicators, and general branching may lose the interpretation that the minimum remaining values and degree heuristic exploit directly. Native constraint propagation can exploit a relation without enumerating all its forbidden tuples. Even in the binary case, stronger propagation does not follow just from switching to SAT.
For example, take , , and let the only allowed pairs be . The forbidden-pair encoding contains and . If becomes false, arc consistency deletes because it has no support. Yet the direct encoding has no unit Boolean clause forcing : both remain possible individually, so plain unit propagation does not make that deletion. A SAT solver can eventually derive it through additional reasoning or search. Conversely, clause learning can combine information beyond the local consistency enforced by AC-3. Neither approach uniformly dominates: performance depends on representation, propagation strength and the instance's structure; both still face exponential worst-case search on general inputs.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 e Solution by
Codex 0 2026-10-25
Use an exactly-one constraint for each finite-domain variable and a Boolean clause forbidding each disallowed constraint tuple. Let the variables be , with explicitly listed finite constraint domains , and let constraint have distinct-variable scope and allowed relation . Introduce a Boolean variable for every , interpreted as . The direct SAT encoding of finite-domain constraints isIn the middle logical conjunction, each unordered distinct pair is included once. The first Boolean clause requires at least one value, the pairwise Boolean clauses permit at most one, and a final Boolean clause is false exactly when all coordinates of one forbidden tuple are selected. The formula is in conjunctive normal form. An empty constraint domain produces an empty Boolean clause, correctly making the instance unsatisfiable.
For soundness of the reduction, a solution of the constraint satisfaction problem gives the Boolean valuation exactly when . Every exactly-one constraint holds; a forbidden tuple differs from on at least one scoped coordinate, making its negative Boolean clause true. Thus supplies a satisfying assignment for .
Conversely, a satisfying assignment selects a unique value for every . If a constraint failed, the selected scoped tuple would belong to , and its entire negative Boolean clause would be false. That contradicts satisfiability. Hence is a solution. Decoding takes by scanning the value indicators. This proves has a solution if and only if is satisfiable.
For explicit size accounting, put , and . There are Boolean variables,Boolean clauses, andliteral occurrences. These formulas count nonempty scopes; a false zero-arity constraint contributes an empty Boolean clause, while a true one contributes none. Formula storage is literal-sized records; a bit-level encoding also stores indicator indices. With maximum constraint domain size , constraints and maximum arity , this is bounded by for nontrivial domains and scopes. In the common binary case it is .
The input representation matters: listing all forbidden tuples costs up to tests per constraint. This is polynomial for bounded arity and explicitly represented domains, but can be exponential in the description length of a succinct high-arity constraint. The translation is valid in that case without constituting a polynomial-size reduction. If a compact constraint is supplied as a polynomial-size Boolean circuit, one may instead encode that circuit using auxiliary Boolean variables and local conjunctive normal form equivalences, with size proportional to the circuit. No compact representation is silently assumed.
For the instance in (c), after unary filtering there are indicators. The five at-least-one Boolean clauses, pairwise at-most-one Boolean clauses and forbidden-equality Boolean clauses give Boolean clauses. Setting only true encodes the displayed solution.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 d Solution by
Codex 0 2026-10-25
Cutset conditioning selects a cycle cutset : deleting its vertices makes the binary constraint graph a forest. Enumerate assignments to , reject those violating internal constraints, and filter each remaining constraint domain against the chosen cutset values. Solve the residual components by tree-structured constraint satisfaction. Stop at a successful assignment, or report failure after all cutset assignments fail. Completeness follows by considering the restriction of any full solution to ; soundness follows by checking internal, crossing and residual constraints. With maximum constraint domain size and cutset variables, a typical bound is for the residual forest work, with cutset and crossing checks added explicitly.[ref]
Here take . The residual constraint graph has vertices and only edges , a tree rooted at . Choose the consistent cutset values . Filtering against these assignments givesThe upward support pass from deletes , because can only equal . The pass from retains , which has support or . Assign at the root and then supported child values . Together with , this gives the solution in (c).
No singleton cycle cutset exists: deleting or leaves, respectively, a triangle on or ; deleting leaves the cycle in a graph . Thus the two-element choice is also minimum, although the algorithm only requires a valid cutset.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 c Solution by
Codex 0 2026-10-25
One solution is . Use ascending value order; after minimum remaining values and the degree heuristic, break any remaining variable tie alphabetically. Apply the unary restrictions first:
Minimum remaining values selects , even though has greater initial vertex degree. Set . Forward checking removes from the three neighbors :Now is the unique minimum remaining values choice. Set . Forward checking removes from , givingSelect and set . Its remaining neighbors are , so forward checking givesThe two remaining variables tie on constraint domain size and each has one unassigned neighbor, so the degree heuristic also ties. Alphabetical order selects ; take . Since is already absent from , forward checking makes no further deletion. Finally choose . No empty constraint domain or violation occurs, so this branch needs no backtracking.
All eight binary constraints are checked explicitly by the unequal value pairsThe unary restrictions also hold. Equalities and are permitted because those pairs have no edges in the constraint graph.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 b Solution by
Codex 0 2026-10-25
Forward checking makes minimum remaining values respond to current restrictions rather than the original constraint domain sizes. After , its neighbors may have fewer choices, become forced or lose all choices. Minimum remaining values then selects the newly constrained variable early, while an empty constraint domain triggers immediate failure. The two mechanisms expose failure sooner and reduce wasted backtracking.
Forward checking only tests an unassigned neighbor against the newly assigned value. It need not check whether two still-unassigned variables have mutually supporting values. Arc consistency requires every value at either end of each binary constraint to have support in the other constraint domain, and AC-3 propagates deletions until this condition stabilizes or a constraint domain becomes empty.[ref]
For example, let initially have constraint domains with constraints and . Assigning makes forward checking reduce to , but leaves . Arc consistency also deletes from , leaving . Neither procedure alone decides every general constraint satisfaction problem: a triangle of two-valued inequalities satisfies arc consistency but is unsatisfiable.
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 a Solution by
Codex 0 2026-10-25
For a finite constraint satisfaction problem, remove values violating unary restrictions before starting. The following backtracking algorithm makes independent copies of constraint domains at each branch, so failed forward checking cannot contaminate a sibling branch.
SOLVE(P):
D := domains of P after unary filtering
if some D[X] is empty: return failure
return SEARCH({}, D)
SEARCH(assignment, D):
if every variable is assigned: return assignment
X := SELECT-UNASSIGNED-VARIABLE(assignment, D, P)
for v in ORDER-DOMAIN-VALUES(X, assignment, D, P):
if X=v is compatible with the current assignment:
next_assignment := assignment extended by X=v
next_domains := a deep copy of D
next_domains[X] := {v}
if INFERENCES(X, v, next_assignment, next_domains, P) succeeds:
result := SEARCH(next_assignment, next_domains)
if result is not failure: return result
return failureSELECT-UNASSIGNED-VARIABLE implements minimum remaining values: choose an unassigned variable with the smallest current constraint domain. Break ties by the degree heuristic, choosing the variable constrained to the greatest number of other unassigned variables; a fixed final tie rule makes execution reproducible. ORDER-DOMAIN-VALUES may use any complete ordering; ascending values suffice here.
INFERENCES implements forward checking: for each unassigned neighbor of , remove every value incompatible with , and fail if any constraint domain becomes empty. For higher-arity constraints, reject any completely instantiated violation and use a sound chosen filtering rule; the stated neighbor test is the usual binary case. Forward checking never removes a value used by a possible extension of the current assignment. Exhausting every surviving value therefore makes this finite backtracking procedure both sound and complete.[ref]
CS 188 constraint filtering notes. §2.3, opening paragraphs: filtering neighbors after assignment
[ref] Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 1 e Solution by
Codex 0 2026-10-25
The difficulty is representing dictionary membership and the one-letter relationship in positive conjunctive STRIPS preconditions; a finite dictionary nevertheless admits an exact encoding. Pure STRIPS does not provide string indexing, a “differs in one position” operator, arbitrary disjunctive tests or a procedure that calls a dictionary lookup. Those relationships must be represented by ground facts or compiled into ground actions.
One exact whole-word encoding uses a planning fluent and a static predicate containing exactly the permitted dictionary mutations. For the action schema , useInitialize and the static transition facts, and use goal . Only one fact is true initially. Each applicable ground action deletes it and adds exactly its permitted successor, so mathematical induction proves that exactly one current-word fact remains true and that every plan is a legal word ladder. Conversely, every legal word ladder directly supplies a plan. An isolated non-dictionary start is handled as in (c). A shortest plan has the fewest mutations.
This encoding moves the hard lexical relationship into preprocessing. For dictionary words, checking all ordered pairs takes character comparisons, although indexing can do better; the number of stored transitions is at most when all states are dictionary words. The STRIPS representation is finite, but its size and preprocessing cost matter.
A position-based representation instead uses planning fluents . Changing position must delete its old letter and add its new one; all other positions persist through the STRIPS update rule. Merely requiring each position to contain a letter admits non-dictionary strings. A disjunction over all dictionary words is not a positive conjunctive STRIPS precondition. It can be compiled into separate ground actions, each requiring every letter of a valid source word and changing one position to reach a valid destination. This again enumerates lexical cases and can be large. Arbitrary letter changes followed by an unconstrained “validate” action are unsound: several illegal intermediate strings could otherwise lead to a legal goal. Legality must hold after every mutation, not only at the endpoint.
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!
Intro to OurBigBook
. Source. We have two killer features:
- 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-calculusArticles 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/derivativeVideo 2. OurBigBook Web topics demo. Source. - 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.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.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. - Infinitely deep tables of contents:
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





