mnk-bench

Fixing a game network's blind spots with a few oracle labels: PRISM-style targeted selection

A study run inside mnk-bench. Code: src/mnkbench/submodular.py, src/mnkbench/experiments/targeted.py. Data and plots: docs/results/targeted/. Reproduce with mnk-bench experiment targeted --out results (needs PyTorch; about 1 hour on 4 cores).

Abstract. We transfer PRISM's targeted learning to game-playing networks. A small AlphaZero-style network on mini Connect Four misses three tactical motifs (immediate wins, forced blocks, poisoned moves), each about 12–14% of positions. Given 20 examples of a motif, we choose k positions from an unlabelled pool for an exact solver to label, and fine-tune on them. Across 5 seeds × 3 motifs × 5 budgets (25–400 labels), the six PRISM measures do what they are designed to do: they select 2–3× more motif positions than random (FLVMI: 41% vs 14% at k = 25). That enrichment, however, mostly does not turn into accuracy on the motif. Only LogDetMI beats random selection reliably: +1.8 points over all budgets (46 of 70 non-tied paired comparisons; sign test p = 0.012, 0.12 after Bonferroni over 10 methods) and +4.3 ± 2.3 points at k = 400. The others are within ±1 point of random. Meanwhile an oracle that labels only true motif positions gains +13.3 points (+18.3 at k = 400). A dose-response analysis explains the gap. Every method's gain is predicted by the number of motif positions it got labelled, at about +4.7 points per doubling. PRISM-selected and randomly selected motif positions are worth the same, and with a 15–40% hit rate the non-motif labels dilute training. Targeting also costs overall accuracy (−1.0 to −1.3 points for GCMI, FLVMI and LogDetMI), where plain uncertainty sampling is best (+1.3 points). The bottleneck is precision, which depends on how well the network's own embeddings separate the motif, not on the choice of submodular objective.

1. Motivation

The rest of mnk-bench asks where each method breaks as the board grows. Exact search breaks first (minimax is refused from (5,5,4)), but an exact or very deep search is still the best teacher available: it can tell a learned agent the right move in any position it is shown. The catch is cost. Each label is a solver call, so in practice only a small budget of positions can be labelled.

That raises a practical question. Suppose you notice your network has a specific blind spot, such as missing immediate wins, and you can collect a handful of positions that show it. Which positions should you spend the labelling budget on? This is the targeted learning problem that PRISM (Kothawade, Kaushal, Ramakrishnan, Bilmes and Iyer, AAAI 2022) studies for image classifiers. A model underperforms on a rare class, a few examples of that class form a query set, and a submodular mutual-information function between candidate subsets and the query set chooses which unlabelled examples to label. This document transfers that setting to games.

2. Background: submodular information measures

A set function f over a ground set V is submodular if marginal gains diminish: f(A ∪ {j}) − f(A) ≥ f(B ∪ {j}) − f(B) for A ⊆ B. Greedy maximisation of a monotone submodular f under a cardinality budget is within (1 − 1/e) of optimal. All functions below use a non-negative similarity kernel S (here: cosine similarity of network embeddings).

PRISM builds information measures from a submodular f. Given a query set Q (what we want) and a private set P (what we want to avoid), it defines:

Instantiated with standard functions, they give the selection objectives compared here (formulas as in the authors' SUBMODLIB implementation):

name objective behaviour
FL (facility location) Σᵢ∈V maxⱼ∈A Sᵢⱼ representation/diversity, ignores Q
LogDet log det(S_A + λI) diversity (DPP-like), ignores Q
GCMI 2λ Σⱼ∈A Σ_q∈Q S_jq pure query relevance (modular)
FLMI Σᵢ∈V min(maxⱼ∈A Sᵢⱼ, η max_q∈Q Sᵢ_q) query coverage + diversity; saturates
FLVMI Σ_q∈Q maxⱼ∈A S_qj + η Σⱼ∈A max_q S_jq relevance + query coverage, no saturation
COM η Σⱼ∈A ψ(Σ_q S_jq) + Σ_q ψ(Σⱼ∈A S_jq), ψ = √ between GCMI and FLMI
LogDetMI log det(S_A) − log det(S_A − η² S_AQ S_Q⁻¹ S_AQᵀ) relevance + diversity
FLCMI Σᵢ max(min(maxⱼ∈A Sᵢⱼ, η max_q Sᵢ_q) − ν max_p Sᵢ_p, 0) like Q, unlike P

η trades query relevance against diversity, and ν sets how strongly P is avoided. The implementation (mnkbench.submodular) provides each function's direct definition, vectorised marginal gains, plain greedy and Minoux's lazy greedy (exact for submodular functions, and 25–70× faster here). Tests check incremental gains against the definitions, check diminishing returns and monotonicity on random instances, and check greedy against brute force for the (1 − 1/e) bound.

3. Setup

Game. Mini Connect Four: the (5,5,4) game with gravity. It is small enough that the exact solver labels a position in about 20 ms, and tactical enough to produce clear failure modes.

The network with blind spots. An AlphaZero-style policy/value network (the project's 39k-parameter residual CNN) trained by self-play for only 4 iterations × 30 games (about 20 s). Without search, its top policy move keeps the game-theoretic outcome in about 60% of the positions where the choice matters ("decision positions").

Target weaknesses (the "rare classes"). Positions are grouped by tactical motif, detected exactly from the rules:

motif definition share of positions base network's blunder rate there
win the side to move can win immediately 11.8% 39%
block the opponent threatens to win next move; it must be blocked 11.7% 31%
poison some legal move lets the opponent win at once (in gravity games: playing directly below the opponent's threat cell) 14.2% 28%

(Means over the 5 seeds' pools and test sets; blunder rate = share of held-out decision positions of that motif where the network's top move changes the outcome.)

Selection methods never see these motif labels for the pool. They only see network embeddings and the query examples. The motif labels are used solely for evaluation and for the oracle reference.

Data. For each seed, positions are sampled from games between a mix of agents (random, rule-based, MCTS-100 and alpha-beta depth 2, with 15% random moves), at most three per game, de-duplicated up to symmetry. They are split into an unlabelled pool (3,000), a development set (1,000) from which the query set Q (20 positions of the target motif) and the private set P (20 motif-free positions) are drawn, and a test set (2,000).

Oracle labels. For a selected position the exact solver returns every outcome-preserving move (a win stays a win, a draw stays a draw) and the solved value.

Selection. Embeddings are the residual tower's output (flattened, 800-d, non-negative ReLU features), with cosine similarity as the kernel. Methods:

Greedy selection is nested, so one greedy run at the largest budget gives every smaller budget as a prefix.

Fine-tuning. Each method's k selected positions, plus the 20 labelled query positions (the same for every method), fine-tune a copy of the network. The training budget is identical for every method: 300 Adam steps, batch 64, learning rate 1e-3, mirror augmentation. The policy target is uniform over the outcome-preserving moves and is applied only to decision positions: where every move keeps the outcome, the oracle says nothing about which to prefer. The value target is the solved outcome. A distillation term on unlabelled pool positions keeps the policy close to the original elsewhere.

Metrics. These are raw-policy accuracy (does the top move preserve the outcome?) on held-out decision positions of the target motif (target accuracy) and on all held-out decision positions (overall accuracy), plus the share of selected positions that belong to the motif (hit rate, PRISM's "how many rare-class examples were selected"). For k = 200 the fine-tuned networks also play 20 games each against perfect play and against depth-2 alpha-beta, without search, starting from 20 shared random 4-move openings.

Protocol. 5 seeds (fresh data, queries and training seeds; the base network is fixed) × 3 motifs × 12 methods × budgets k ∈ {25, 50, 100, 200, 400}. The ablations at k = 100 on the poison motif cover η ∈ {¼, ½, 1, 2, 4}, |Q| ∈ {5, 10, 20, 50, 100}, and raw-board features instead of network features. Means are reported with 95% confidence intervals over seeds, and paired comparisons against random use the same seed and data.

4. Results

All numbers are means over 5 seeds × 3 motifs unless stated otherwise. Raw per-run rows are in docs/results/targeted/targeted_runs.csv and the statistics in targeted_significance.csv.

4.1 Selection: PRISM finds the motif

Target accuracy and hit rate per motif and budget

Hit rate (share of selected positions in the target motif; random ≈ base rate ≈ 13%):

method k = 25 k = 100 k = 400
random 0.14 0.13 0.13
entropy / margin 0.10 / 0.12 0.09 / 0.10 0.09 / 0.11
FL / LogDet (diversity only) 0.07 / 0.13 0.08 / 0.14 0.10 / 0.13
GCMI 0.24 0.23 0.20
FLMI 0.17 0.22 0.15
FLVMI 0.41 0.31 0.22
COM 0.24 0.23 0.20
LogDetMI 0.37 0.30 0.23
FLCMI 0.23 0.23 0.15
oracle 1.00 1.00 0.92

Every query-guided measure enriches the selection, most at small budgets, as PRISM's theory predicts: once the most query-like positions are taken, the remaining ones are less similar. FLVMI and LogDetMI, which combine relevance with query coverage, enrich most. FLMI's saturation shows here: it stops valuing query-relevant points once the query is "covered". Pure diversity (FL) under-samples the motif, because motif positions are a small region of embedding space and a representative subset avoids over-covering it. Uncertainty sampling also under-samples it: the network is not especially uncertain in positions where it blunders.

4.2 Learning: little transfers, except for LogDetMI at larger budgets

Target accuracy, averaged over the three motifs (base network 0.672; base + the 20 labelled query positions 0.691):

method k = 25 k = 100 k = 400 vs random, all budgets (wins/losses, mean ± 95% CI)
random 0.684 0.673 0.707 —
entropy 0.681 0.683 0.679 36/35, −0.7 ± 1.2
margin 0.681 0.662 0.683 28/42, −1.1 ± 1.2
FL 0.687 0.658 0.677 31/41, −1.4 ± 1.5
LogDet 0.663 0.682 0.713 32/41, −0.1 ± 1.3
GCMI 0.696 0.682 0.712 39/30, +1.0 ± 1.2
FLMI 0.694 0.684 0.703 38/31, +0.5 ± 1.2
FLVMI 0.701 0.682 0.708 34/34, +0.5 ± 1.1
COM 0.693 0.686 0.709 34/32, +0.7 ± 1.0
LogDetMI 0.691 0.692 0.750 46/24, +1.8 ± 1.1 (p = 0.012; Bonferroni 0.12)
FLCMI 0.676 0.683 0.714 35/36, +0.1 ± 1.1
oracle 0.741 0.826 0.890 72/1, +13.3 ± 1.6

At k = 400, LogDetMI beats random in 11 of 13 non-tied comparisons (+4.3 ± 2.3 points, p = 0.022 uncorrected). It is also the only method whose curve clearly separates from random in all three motifs at the largest budget (win 0.731 vs 0.709, block 0.752 vs 0.678, poison 0.767 vs 0.735). We read this as a real but modest effect: consistent in direction, significant before multiple-comparison correction, not after.

Pooled curves

4.3 Why enrichment doesn't become accuracy: dose-response

Dose-response

For each run we plot the target-accuracy gain over the query-only network against the number of motif positions in its training set (hit rate × k + 20). The oracle's runs (pure motif data) lie on a clean log-linear curve: +4.7 points per doubling of labelled motif positions. Every other method, PRISM or baseline, sits about 5 points below that curve on average: random −5.0, GCMI −5.5, FLMI −5.3, LogDetMI −5.6, FLVMI −6.9. Two conclusions follow:

  1. A motif position selected by a PRISM measure is worth no more than a random motif position. The selection adds quantity, not quality. FLVMI is slightly below random. Its picks are the positions most similar to the query examples, which are partly redundant with the query positions already in the training set.
  2. The non-motif labels cost something. With a fixed training budget, gradient steps spent on the 60–85% of selected positions that are not in the motif dilute the targeted signal. This is why a 2–3× enrichment buys so little: going from 14% to 41% hits at k = 25 means about 10 instead of 3.5 extra motif positions on top of the 20 query positions, which is a fraction of one doubling.

4.4 Targeting costs overall accuracy

Overall accuracy over all decision positions, paired against random over all budgets:

method wins/losses mean ± 95% CI p (sign)
entropy 54/19 +1.3 ± 0.5 5e-5
FLMI 41/32 +0.3 ± 0.5 0.35
GCMI 25/50 −1.0 ± 0.6 0.005
FLVMI 26/49 −1.0 ± 0.6 0.011
LogDetMI 22/52 −1.3 ± 0.6 6e-4
oracle 19/54 −2.0 ± 0.6 5e-5

This is the expected trade-off: labels spent on one motif are not spent on the network's other mistakes. Uncertainty sampling, which does not target anything, is the best general-purpose strategy. FLMI, the most diversity-preserving MI measure, is the only targeted method that does not pay this cost.

4.5 Ablations (poison motif, k = 100)

eta

|Q|

4.6 Playing strength

Without search, the fine-tuned networks' non-loss rate against perfect play from 20 random openings is 0.05–0.22 for every method and motif, against 0.17 for the base network. Differences between methods are within game-to-game noise. None of the strategies made the network play worse, and 200 labels are too few to make a measurable difference in full games.

5. Discussion

What transferred from PRISM. The submodular information measures behave in games as they do on images. They reliably pull a rare, query-defined class out of an unlabelled pool, with the relevance-diversity behaviour the paper describes (GCMI pure relevance, FLMI saturating, FLVMI and LogDetMI balancing both, η controlling the trade-off). LogDetMI was the best measure overall here.

What did not. Enrichment from 13% to 30–40% was not enough to fix the weakness. The network's own embedding space, learned in 20 seconds of self-play, does not separate "a win is available" from look-alike positions where it isn't. Because selected motif positions are worth no more than random ones, the method's value comes entirely from its hit rate.

Implications for mnk-bench. This adds a new axis to "where does each method break": how cheaply can a learned agent's weakness be patched with an expensive teacher? With an exact solver as teacher, the answer on mini Connect Four is about +4.7 points of motif accuracy per doubling of motif labels. Selection precision is the lever. Whether a stronger network's embeddings (where motifs are more linearly separable) would make PRISM selection pay off is the natural next experiment, as is selecting in several rounds, with each round's newly labelled motif positions added to Q.

6. Limitations

7. Reproducing

pip install -e ".[dev,alphazero]"
mnk-bench experiment targeted --out results -v       # ~1 hour on 4 cores
mnk-bench experiment targeted --quick --out /tmp/t   # ~1 minute smoke test
pytest tests/test_submodular.py tests/test_targeted.py

The submodular functions can be used on their own:

from mnkbench.submodular import cosine_kernel, make_function, lazy_greedy
S, S_VQ = cosine_kernel(X), cosine_kernel(X, Q)          # X: pool features, Q: query features
picked = lazy_greedy(make_function("FLVMI", S, S_VQ, eta=1.0), k=100)

References

Source: docs/research/targeted-selection.md