acceptodds
Desk rejected at ICLR 2027

Learning Pursuit Policies with Belief-Weighted Information-Consistent Search in the Scotland Yard Board Game

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Pursuit-evasion games in which the pursuers cannot see the evader are a natural testbed for search under imperfect information, and the board game Scotland Yard is their best-known large instance. CFR-based equilibrium solvers are costly over a long horizon with combinatorial joint actions. Search over sampled evader locations avoids this cost but fails in two opposite ways: the pursuers' search lets them act differently in worlds they cannot tell apart, and the evader's search lets the pursuers it imagines see it. We observe that in one-sided games both failures disappear if every pursuer decision, in either role's search, depends only on the public history. On this principle we build a self-play learning framework. Its pursuer nodes are keyed by the public history and shared by all possible evader locations, and the evader expands a root for every location the pursuers cannot rule out. A learned location prior reweights the simulation backups in the pursuer search, and an autoregressive policy represents the pursuers' joint action. Through self-play, two role-specific networks learn to match search policies and predict game outcomes. On an adapted version of Scotland Yard, our pursuers win at least 98% of games against every evader we test, even without search. The best baseline wins 86% of games against learned evaders on average.

Primary area:
reinforcement learning
Keywords:
Partial Observability, Pursuit-Evasion Games, Reinforcement Learning, Monte Carlo Tree Search, Scotland Yard

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_EEEBOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies pursuit policies for Scotland Yard as a two-player zero-sum one-sided partially observable stochastic game, where the five pursuers share observations and only the evader has private location information. The authors propose SWIFT, a self-play framework that trains role-specific graph networks on a single public-history search graph shared by both roles. The construction combines information-consistent search, a learned location prior that reweights sampled worlds during backup, an autoregressive joint-action policy, and self-play distillation of search targets. On an adapted 199-station, 22-round version of the game, the authors report that the trained pursuers win at least 98% of games against six self-trained evaders, even without test-time search.

Critical strengths
  1. The paper identifies a clean structural property of one-sided public-observation POSGs: because the pursuers have no private information, every public history corresponds to exactly one pursuer information set, so the per-information-set trees required by ISMCTS and self-determinization collapse into a single public-history graph.

  2. The empirical results are strong within the paper's protocol: SWIFT wins at least 98% against all six self-trained evaders without test-time search, and the belief-weighting and encoder ablations are consistent with the claimed mechanism.

  3. The efficiency contrast is potentially significant: SWIFT is trained on a single RTX 5090 for five hours.

Critical weaknesses
  1. The presentation method of the paper needs improvement. The paper should not aim at Scotland Yard as the solution, but rather at the pursuit game where "only one side is partially observable". Scotland Yard is too narrow in game domain.

  2. No external anchor for the central claim. All six evaders are trained by the authors, and no published agent participates; PimBot, the standard strong agent in this game, is never included in the comparison, even though the paper builds on its single-tree determinization and location categorization. The Introduction describes SoG only through an 11-node map, although SoG was trained on the full 199-station game and won 55% head-to-head against PimBot with 10M simulations. This omits the most natural external comparison and understates a competitor's contribution.

  3. The headline claim is broader than the evidence. "At least 98% against every evader we test" is not supported for the human evader. The 98% figure is also specific to the five-pursuer game; with three pursuers the same method wins about 23% against its final evader.

  4. The baseline comparisons confound algorithm and training opponent. The PPO-type baselines are trained only against Greedy, which is nearly solved from the first checkpoint, while P2SRO is a 12-hour self-play baseline and SWIFT gets five hours. There is no no-learning ISMCTS and no search-vs-search comparison at equal simulation budget.

  5. No exploitability or best-response measure is reported. Every learned opponent is produced by the authors' own training runs, and every strength comparison is a win rate against fixed opponents or a rating from cross-play within one pool, so none of them bounds how much a stronger evader could gain against the trained pursuers; even the P2SRO evader, the closest to a best-response opponent, is trained against its own population.

Questions for authors
  1. Can you evaluate SWIFT head-to-head against PimBot with roles swapped, under the classic rules or an adaptation to your 22-round rules, and report the result of SoG vs PimBot?

  2. Can you isolate the AlphaZe** gap with a 2×2 ablation (per-world vs. public-history search × with/without KataGo refinements) within a single rating pool, and report the L1 distance or a reliability diagram between qP and the exact belief b?

  3. Can you restrict "every evader we test" to the six agent evaders, state the five-pursuer condition in the abstract and conclusion, and describe the human evaluation as a single-participant exploratory study?

  4. Can you add a MAPPO self-play baseline trained for five hours, compare P2SRO at equal wall-clock time, and report search-vs-search at equal simulation budget?

  5. Can you report exploitability on the 11-node map used by SoG, or the gain of a best-response evader trained against the final pursuers?

5 comments
AuthorsOpenReview ↗

Response to Reviewer EEEB (1/3)

Thank you for the review. We added the experiments that bear most directly on the main claim (PimBot in both roles, best-response evaders, the 2×2 ablation and the calibration of the location prior) and narrowed the claims as you suggested. All new results support the paper's central claim.

Weakness 1: framing beyond Scotland Yard

Weakness 1. The presentation method of the paper needs improvement. The paper should not aim at Scotland Yard as the solution, but rather at the pursuit game where "only one side is partially observable". Scotland Yard is too narrow in game domain.

We agree and now frame the paper around this class of games. The Introduction now starts from pursuit-evasion games with one-sided partial observability, in which the pursuers share public information and the evader observes the full state. Adapted Scotland Yard is presented as the testbed (§1, paragraph 1), and §3 introduces it as our instance of this class. The search construction itself relies only on this information structure: the shared public-history pursuer nodes, the evader roots for every possible location and Proposition 1 need only that the pursuers hold no private information and that the evader knows the true state.

Weakness 2 and Question 1: PimBot as an external anchor, and Student of Games

Weakness 2. No external anchor for the central claim. All six evaders are trained by the authors, and no published agent participates; PimBot, the standard strong agent in this game, is never included in the comparison, even though the paper builds on its single-tree determinization and location categorization. The Introduction describes SoG only through an 11-node map, although SoG was trained on the full 199-station game and won 55% head-to-head against PimBot with 10M simulations. This omits the most natural external comparison and understates a competitor's contribution.

Question 1. Can you evaluate SWIFT head-to-head against PimBot with roles swapped, under the classic rules or an adaptation to your 22-rounds rules, and report the result of SoG vs PimBot?

We evaluated SWIFT against PimBot with roles swapped, under an adaptation to our 22-round rules. Averaged over the two roles, SWIFT without search wins more than half of the games at every PimBot budget from 10 to 10⁶ simulations per decision. This average falls from 100% at the smallest budget to 54% at the largest (table in the General Response, item 3; new App. D.9, Figure 15). As pursuer, SWIFT wins at least 98% at every budget. As evader, it wins 28% against PimBot with 10⁴ simulations and 10% with 10⁶, in line with the pursuers' structural advantage in this game. In Table 1 (10⁴ simulations per decision, 512 games per pairing), PimBot is the strongest baseline pursuer, with an average win rate of 85.7% against the learned evaders (SWIFT: 98.5%), and the SWIFT evader is its hardest opponent.

We reimplemented PimBot following Nijssen & Winands (2012) with all components of the original (General Response, item 3). Since it plays our rules, its handling of double moves is not needed, and we re-estimated the location-category weights from 1000 self-play games under our rules. As you requested, §1 and §2 now report the result of Student of Games: it beats PimBot with 10⁷ simulations per search in 55% of 2000 games, half of them with roles swapped (Schmid et al., 2023).

AuthorsOpenReview ↗

Response to Reviewer EEEB (2/3)

Weakness 3 and Question 3: the scope of the claims

Weakness 3. The headline claim is broader than the evidence. "At least 98% against every evader we test" is not supported for the human evader. The 98% figure is also specific to the five-pursuer game; with three pursuers the same method wins about 23% against its final evader.

Question 3. Can you restrict "every evader we test" to the six agent evaders, state the five-pursuer condition in the abstract and conclusion, and describe the human evaluation as a single-participant exploratory study?

We made all three changes. (i) "Every evader we test" now refers to the learned, rule-based and search-based evader agents we evaluate, that is, the six of the submission and PimBot (Abstract, §1, §6). (ii) The abstract, §1 and the conclusion state the result for the five-pursuer game. In the three-pursuer game (App. D.5), SWIFT wins about 29% against its final evader in a new run; the 23% of the submission came from an earlier run. P2SRO, now also trained in this game for about 14 hours, wins about 28% against the same evader and less often than SWIFT against every heuristic evader. (iii) The human evaluation is described as a single-participant exploratory study (App. D.1), and the main text draws no conclusion from it.

Question 2: the 2×2 ablation and the calibration of q_P

Question 2. Can you isolate the AlphaZe** gap with a 2×2 ablation (per-world vs. public-history search × with/without KataGo refinements) within a single rating pool, and report the L1 distance or a reliability diagram between qP and the exact belief b?

2×2 ablation. We ran the 2×2 within one rating pool. Public-history search beats per-world search whether the KataGo tricks are switched on or off. The tricks, in turn, help only when combined with public-history search. Pursuer ratings after 5 h, in the pool formed by the four runs (this response only):

Pursuer searchKataGo tricks onKataGo tricks off
Public-history (shared pursuer nodes)20221639
Per-world (separate pursuer trees)14381461

Public-history search is worth 584 points when the tricks are on and 178 when they are off. The tricks add 383 points with shared nodes and change little (−23) with per-world trees. In the public-history runs, the evader searches from a single root; in the per-world runs, it keeps one root per possible location. Since a single root weakens the pursuer (General Response, item 1a), this choice does not favor public-history search. For AlphaZe** itself, we rated the final networks of SWIFT, its ablations and both AlphaZe** variants in another pool. AlphaZe** is 784 points below SWIFT (1255 vs. 2039) and loses another 255 points when the tricks are added (1000). Without the tricks on either side, SWIFT still leads by about 400 points (1653 vs. 1255), so the tricks do not explain the gap. One possible explanation is that the KataGo tricks strengthen AlphaZe**'s search within individual sampled worlds, making it favor actions that rely more heavily on world-specific perfect information. This may exacerbate the effects of strategy fusion, resulting in a worse averaged root policy.

Calibration of q_P. We report both (new part of App. D.4, Figure 9). The location prior is much closer to the exact belief than uniform weighting. Over 1,024 games between the final networks, we compute the exact belief b of the evader network by Bayesian filtering of the public history (5,344 states, 147,765 state–location pairs). The mean L1 distance between q_P and b grows from about 0.23 one hidden move after a reveal to about 0.61 after four, whereas uniform weighting stays at 0.71–0.86. The mixture used in the search lies in between. q_P is well calibrated up to about 0.35 and overconfident above that: when it predicts about 0.95, the evader is there in about 83% of cases. The mixture keeps every possible location at no less than half its uniform weight, which limits the effect of this overconfidence on the search.

AuthorsOpenReview ↗

Response to Reviewer EEEB (3/3)

Weakness 4 and Question 4: training opponents, equal training time and search baselines

Weakness 4. The baseline comparisons confound algorithm and training opponent. The PPO-type baselines are trained only against Greedy, which is nearly solved from the first checkpoint, while P2SRO is a 12-hour self-play baseline and SWIFT gets five hours. There is no no-learning ISMCTS and no search-vs-search comparison at equal simulation budget.

Question 4. Can you add a MAPPO self-play baseline trained for five hours, compare P2SRO at equal wall-clock time, and report search-vs-search at equal simulation budget?

A learning opponent alone does not explain SWIFT's advantage. We agree that the PPO-type baselines confound the learner with the Greedy training opponent, and §5 now states which baselines train against learning evaders and which against Greedy. A MAPPO self-play baseline would test whether a learning opponent alone produces strong pursuers, and three comparisons in the paper already answer this. P2SRO trains the same PPO-GNN learner against a population of learning evaders: against the SWIFT evader, it wins about 61% after five hours and 85.7% after twelve, compared with 66.2% for PPO-GNN and 98.2% for SWIFT (Table 1; App. D.2). AlphaZe** uses SWIFT's networks, training pipeline and training time against its own learning evader and wins only 30.5% against the SWIFT evader. Every SWIFT ablation is also trained by self-play, yet separate pursuer trees alone cost 590 rating points (General Response, item 1). The information-consistent search, rather than the learning opponent, makes the difference.

At equal wall-clock time, P2SRO stays far behind SWIFT. At five hours, the P2SRO pursuer wins about 61% of games against the final SWIFT evader, compared with 98.2% for SWIFT (App. D.2, Figure 6).

The search budget does not explain SWIFT's strength. As a search baseline without learning, we added PimBot. It is the published single-tree determinization MCTS for Scotland Yard, and its shared pursuer tree follows the same principle as ISMCTS. With 10⁴ simulations per decision, it wins 85.7% on average against the learned evaders, compared with 98.5% for SWIFT without search. We did not run search against search at equal budget, because the paper's claim concerns the networks that training produces, which play without search. Three further results show that the budget does not explain the pursuers' strength. First, the SWIFT pursuer without search wins at least 98% of games against PimBot with up to 10⁶ simulations per decision. Second, AlphaZe**'s pursuers spend up to 500 simulations per move (100 in each of up to five worlds), compared with about 300 for SWIFT, and end far weaker. Third, the 2×2 above compares the two search structures at the same budget.

Weakness 5 and Question 5: exploitability

Weakness 5. No exploitability or best-response measure is reported. Every learned opponent is produced by the authors' own training runs, and every strength comparison is a win rate against fixed opponents or a rating from cross-play within one pool, so none of them bounds how much a stronger evader could gain against the trained pursuers; even the P2SRO evader, the closest to a best-response opponent, is trained against its own population.

Question 5. Can you report exploitability on the 11-node map used by SoG, or the gain of a best-response evader trained against the final pursuers?

We report the gain of a best-response evader, and the SWIFT pursuer is much harder to exploit than every learned baseline. A PPO evader trained from scratch against the frozen final SWIFT pursuer, on the full 199-station map, wins 7% of games after half an hour, 12% after one hour and 17% after two. Against the learned baseline pursuers, the same learner wins 53.3–99.6% after half an hour and 68.4–99.6% after two hours (General Response, item 2; revised §5.1, Figure 2; App. D.8). The fixed evaders of Table 1 win at most 1.8% against SWIFT, so adaptation helps the evader, but it still wins far less against SWIFT than against any learned baseline pursuer. We chose this option because it evaluates the very pursuer reported in the paper, in the game it was trained for. Exploitability on the small map of Student of Games would describe a different policy trained for a different game.

We hope these results address your concerns, and we are glad to discuss any remaining point.

Reviewer_vUZeOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper learns pursuer policies for an adapted version of the board game Scotland Yard. Five pursuers chase one evader on the 199-station map of London, and see its location only in four reveal rounds. Treating the pursuers as one player gives a two-player zero-sum game in which only the pursuers lack information. Search over sampled evader locations fails in two ways: the pursuers' search can choose different actions for locations they cannot tell apart (strategy fusion), and in the evader's search, the pursuers it imagines can act as if they see it. SWIFT keys every pursuer node, in both searches, by the public history, so all sampled locations share these nodes. The evader's search expands one root per location the pursuers cannot rule out, and reads only the root of its true location. A learned location prior reweights the pursuers' backups, and an autoregressive policy represents their joint action. Two networks, one per role, are trained by self-play. Proposition 1 states that both searches are information-consistent, and Proposition 2 decomposes the error of a root value in the pursuers' search. Without search at test time, SWIFT's pursuers win 98.2% to 100% of games against six evaders: three learned, two heuristic and one random. The best baseline, MAPPO-GNN, averages 85.6% against the learned evaders. Ablations remove the location prior entirely, train it only as an auxiliary loss, or, without the prior, replace the graph encoder with an MLP.

Critical strengths
  1. The search design follows from a clear analysis of why search over sampled locations fails on each side. For one-sided games, the paper argues that one graph keyed by the public history rules out both failures, with the evader's search entering it through one root per possible location (Section 4.3 and Proposition 1). The design builds on single-tree determinization, information-set MCTS and self-determinization, and credits them (lines 251–253 and 294). It adds a graph shared by both roles, a learned location prior, a joint-action policy, and self-play learning. This makes the method simple to state and to reason about.

  2. Against the learned evaders, SWIFT's pursuers are clearly stronger than every baseline. Without search, they win 98.2–99.2% of games against them, while no baseline exceeds 94.1% against any learned evader (Table 1). AlphaZe**, which uses SWIFT's network architecture, training pipeline and training time, wins only 26.2–32.4% against them. The location-prior ablation includes a useful control that trains the prior as an auxiliary loss without using it in the search (Figure 3). This is clear evidence that SWIFT works well against the evaders tested.

Critical weaknesses
  1. The paper does not isolate the effect of its two search components: shared public-history pursuer nodes, and one evader root per possible location.

The paper's central claim is that information-consistent search removes both failures and yields strong pursuers (lines 081–095). But I found no experiment that changes either component with everything else fixed. The ablations in Figure 3 vary the location prior and the encoder. The paper cites earlier evidence that shared pursuer nodes beat separate trees (lines 120–122). The main empirical evidence for these two components is the comparison with AlphaZe** (Section 5.1). But AlphaZe** also has no location prior and "none of the KataGo refinements that SWIFT uses", and its pursuers search up to five sampled locations with 100 simulations each (Appendix C). So the attribution of the gap to the two failures (line 405) is not tested directly. Lines 408–409 argue that the prior explains little of this gap, because removing it costs about 200 rating points in Figure 3. But ratings "are comparable only within one figure" (line 942), and AlphaZe** is rated only in Figure 2. Figures 2 and 3 also show one curve per method, without bands, and I found no mention of repeated training runs, so the ablation gaps at five hours (about 2150 vs. 1950 and 1910, lines 427–428) may partly reflect run-to-run variation. This matters because both search components follow earlier methods, so much of the contribution rests on showing that combining them in one graph, with learning, makes the pursuers strong.

  1. The evaluation does not directly test how exploitable the pursuers are.

The win rates in Table 1 are against six fixed evaders: Random, two heuristics, and three learned evaders, of which the paper notes AlphaZe**'s is the weakest (lines 407–408). SWIFT's own evader is the hardest opponent for every pursuer except P2SRO (lines 398–399), but it may still be far from a best response. Its search gives its true location only about 1/K of the simulations, for K possible locations (lines 296 and 308–310), and test-time search barely changes its win rate (about 46–48% for a three-hour checkpoint, Appendix D.3). In Table 1 and the ratings, each network plays its most probable legal action without search, so the pursuers' play is deterministic (lines 921–922). No evader is trained as a best response to the final, frozen SWIFT pursuer. The human evaluation comes closest, since the human adapts, but it has one participant (an author), who lost all four games against checkpoint 118 despite unlimited undo (Appendix D.1). The paper does not claim convergence to an equilibrium (lines 351–352), but it asks whether the method produces "strong pursuers" (lines 081–082), and win rates against fixed opponents can overstate strength against an opponent that adapts.

  1. Prior Scotland Yard agents are not compared, and Student of Games is described incompletely.

The paper says that Student of Games covers "a tiny map of Scotland Yard with only 11 nodes" (line 051). But Schmid et al. (2023) also evaluate Student of Games on full Scotland Yard, where it beats PimBot, the MCTS agent of Nijssen & Winands (2012). The paper omits this, although it motivates SWIFT by calling CFR-based methods "expensive for Scotland Yard" (line 052) and re-solving "costly at every decision" (line 117). Schmid et al. note that Student of Games uses "substantial computational resources", so this motivation may hold, but the paper reports no cost comparison with CFR-based methods. The paper compares with neither PimBot nor Student of Games, and its rule changes (Table 2), such as removing double-move tickets, prevent a direct comparison with their results. It says that removing double moves, giving the evader unlimited regular tickets and ending after 22 rounds "marginally simplify the game, but keep its core features" (lines 149–151), but I found no evidence that the simplification is marginal. This makes it hard to judge how strong SWIFT is relative to prior agents for this game.

I would raise my score if the authors ablate the two search components with everything else fixed, evaluate the final pursuer against a best-response evader, complete the description of Student of Games, and support the claim about the rule changes.

Minor point:

The RQ2 heading says that SWIFT "keeps improving after every baseline levels off" (line 410), but the paragraph says that AlphaZe** "improves throughout" and that P2SRO "improves steadily over the first five of its twelve hours" (lines 415–416).

Questions for authors
  1. Can you train SWIFT with one pursuer tree per sampled location, and SWIFT with an evader that searches only from its true location, keeping everything else fixed? Can you also train AlphaZe** with SWIFT's KataGo refinements?

  2. What is the final SWIFT pursuer's win rate against an evader trained against it while it is frozen, e.g., with PPO or with SWIFT's evader search?

  3. How much do the final win rates and ratings vary across training seeds, for SWIFT and its ablations?

  4. What is the distribution of K during self-play, and how many simulations does the root of the evader's true location receive on average?

My suggestion for future work (not part of my assessment):

  1. Run SWIFT under the classic rules, so that it can be compared with prior Scotland Yard agents.
3 comments
AuthorsOpenReview ↗

Response to Reviewer vUZe (1/3)

Thank you for the detailed review and for naming the evidence that would change your assessment.

I would raise my score if the authors ablate the two search components with everything else fixed, evaluate the final pursuer against a best-response evader, complete the description of Student of Games, and support the claim about the rule changes.

We did all four, and the results support the paper's claims. Both search components make the pursuer stronger, and per-world pursuer search alone costs SWIFT 590 rating points (Weakness 1). An evader trained against the frozen final SWIFT pursuer wins only 17% of games, compared with at least 68% against every learned baseline (Weakness 2). We corrected the description of Student of Games, replaced the claim about the rule changes, and added PimBot as an external baseline under our rules (Weakness 3).

Weakness 1 and Questions 1 and 3: isolating the search components

Weakness 1. The paper does not isolate the effect of its two search components: shared public-history pursuer nodes, and one evader root per possible location.

Question 1. Can you train SWIFT with one pursuer tree per sampled location, and SWIFT with an evader that searches only from its true location, keeping everything else fixed? Can you also train AlphaZe** with SWIFT's KataGo refinements?

Question 3. How much do the final win rates and ratings vary across training seeds, for SWIFT and its ablations?

Each component with everything else fixed. We trained both variants, and both components make the pursuer stronger. SWIFT w/ separate pursuer trees keeps one pursuer tree per sampled location in both searches, and in SWIFT w/ single evader root the evader searches only from its true location. Each keeps the networks, the location prior, the KataGo tricks, N = 300 simulations per decision and five hours of training. In one pool with the other ablations (revised Figure 4, Figure 3 in the submission), separate pursuer trees cost 590 pursuer rating points after 5 h, the largest drop of any ablation. A single evader root costs 80 points at 5 h and up to 170 during training. This tests the attribution at line 405 directly: per-world pursuer search alone accounts for the largest loss, and RQ1 now cites this comparison (revised §5.1, §5.2; App. D.7). The single-root evader is rated about 100 points higher, because its true root receives all 300 simulations instead of about 300/K (Question 4 below).

The gap to AlphaZe** within one pool. We agree that the "about 200 rating points" argument compared ratings across figures, and we removed it (lines 408–409). To compare within one pool, we rated the final networks of SWIFT, its ablations and both AlphaZe** variants together (this response only). Pursuer ratings after 5 h:

PursuerRatingvs. SWIFT
SWIFT2039
SWIFT w/ single evader root1999−40
SWIFT w/o belief weighting (MLP)1882−157
SWIFT w/o belief weighting1839−200
SWIFT w/ auxiliary belief loss1813−226
SWIFT w/o KataGo tricks1653−386
SWIFT w/ separate pursuer trees1450−589
AlphaZe** (as in Table 1)1255−784
AlphaZe** with KataGo tricks1000−1039

AlphaZe** is 784 points below SWIFT. Per-world pursuer search alone accounts for 589 of these points, whereas removing belief weighting costs 200. The search structure thus accounts for most of the gap, as stated at line 405.

AuthorsOpenReview ↗

Response to Reviewer vUZe (2/3)

Seed variation (Question 3). We trained SWIFT and SWIFT w/ single evader root with three seeds each, since this is the only ablation whose gap is close to the variation between runs. Pursuer ratings after 5 h, in a separate pool of the final networks (new Table 6, App. D.7):

PursuerSeed 1Seed 2Seed 3Mean ± std
SWIFT1813179017111771 ± 53
SWIFT w/ single evader root1763173516971732 ± 33

The SWIFT pursuer is rated higher in every seed, by 14 to 55 points, so multiple evader roots consistently produce a stronger pursuer. The same holds throughout training in Figure 4: after the first hour, the single-root pursuer stays below SWIFT, by up to 170 points. Multiple roots keep the evader's model of the pursuers information-consistent, and the pursuer trained against this evader benefits from it.

AlphaZe** with the KataGo tricks (Question 1, second part). We trained AlphaZe** with the KataGo tricks, and they do not close the gap. They lower AlphaZe** by 255 points (1000 vs. 1255 in the pool above), and SWIFT without the tricks still leads AlphaZe** by about 400 points (1653 vs. 1255). The 2×2 of search structure and tricks (General Response, item 1c) shows the same pattern: the tricks add 383 points with shared pursuer nodes but change little (−23) with separate pursuer trees. One possible explanation is that the KataGo tricks strengthen AlphaZe**'s search within individual sampled worlds, making it favor actions that rely more heavily on world-specific perfect information. This may exacerbate the effects of strategy fusion, resulting in a worse averaged root policy.

Weakness 2 and Question 2: a best-response evader against the frozen pursuer

Weakness 2. The evaluation does not directly test how exploitable the pursuers are.

Question 2. What is the final SWIFT pursuer's win rate against an evader trained against it while it is frozen, e.g., with PPO or with SWIFT's evader search?

The frozen final SWIFT pursuer wins 83% of games against a PPO evader trained against it for two hours, and it is much harder to exploit than every learned baseline pursuer. Against SWIFT, the learner wins 7% after half an hour, 12% after one hour and 17% after two. Against the learned baselines, it wins 53.3–99.6% after half an hour and 68.4–99.6% after two hours (table in the General Response, item 2). Each frozen pursuer plays exactly as in Table 1, deterministically and without search, and P2SRO plays its meta-strategy. Against each, we trained a PPO evader from scratch with the same configuration and initial weights, and validated its greedy policy on 512 games every 15 minutes (revised §5.1, Figure 2; App. D.8, Table 7). As you expected, an adaptive evader wins more often than the fixed evaders of Table 1, which win at most 1.8% against SWIFT. At every point of training, however, it wins far less against SWIFT than against any learned baseline. The abstract, §1 and §6 now report this result.

Question 4: the distribution of K and the budget of the true root

Question 4. What is the distribution of K during self-play, and how many simulations does the root of the evader's true location receive on average?

K is 1 right after each reveal and grows until the next reveal (new App. D.10, Figure 16). For the final networks, its mean is about 70 in round 3, before the first reveal, and about 27, 17 and 11 before the reveals of rounds 8, 13 and 18. K also shrinks during training, for example from about 43 to 27 in round 8, as the pursuers learn to rule out more locations. Each root receives ⌈300/K⌉ simulations. Since this budget changes by more than an order of magnitude within a game, we report it per round rather than as one average: the true root receives all 300 simulations right after a reveal, and about 5, 12, 18 and 28 at the mean K before the reveals of rounds 3, 8, 13 and 18. It thus receives few simulations exactly when the evader is hardest to locate. This is the price, stated in §4.3, of keeping the imagined pursuers as uncertain as the real ones. The single-root ablation shows what the price buys: with all 300 simulations at the true root, the evader is rated about 100 points higher, but the pursuer trained against it is weaker in every seed (Weakness 1 above).

AuthorsOpenReview ↗

Response to Reviewer vUZe (3/3)

Weakness 3 and Question 5: Student of Games, prior agents and the rule changes

Weakness 3. Prior Scotland Yard agents are not compared, and Student of Games is described incompletely.

My suggestion for future work (not part of my assessment):

  1. Run SWIFT under the classic rules, so that it can be compared with prior Scotland Yard agents.

Student of Games. We corrected the description. §1 and §2 now state that Student of Games beats PimBot on the full map, winning 55% of games against PimBot with 10⁷ simulations per search, and computes exploitability on a small custom map. The cost motivation now rests on the report of Schmid et al. that strong play required substantial computational resources, and §2 names the source of this cost: re-solving enumerates the information states of every public state (line 117). §2 also states how our goal differs: instead of approximating an equilibrium, we distill information-consistent search into pursuer networks that play without search.

Prior agents. We added PimBot in both roles, reimplemented for our rules with all components of the original program (General Response, item 3). Averaged over the two roles, SWIFT without search wins more than half of the games against PimBot at every budget up to 10⁶ simulations per decision, and in the ratings both its pursuer and its evader pass PimBot within three hours of training. PimBot is the strongest baseline pursuer, with an average win rate of 85.7% against the learned evaders (SWIFT: 98.5%), and the SWIFT evader is its hardest opponent.

Rule changes. We agree and replaced the sentence (lines 149–151). §3 now states what the adapted game keeps: the map, the pursuers' tickets and the information structure, in which the evader knows the full state and the pursuers must infer its location from its tickets and periodic reveals. Table 2 lists the other kept rules (five pursuers, five black tickets, the 18 start stations) and every change: no double moves; unlimited regular evader tickets (refilled from the pursuers' tickets in the classic edition); 22 instead of 24 rounds, which drops the reveal of round 24; a move order chosen each round; and an early evader win when no pursuer can move. The revised text no longer judges how much these changes affect the difficulty. Instead, PimBot under the same rules relates SWIFT to a prior agent. Running SWIFT under the classic rules (Question 5) is a natural next step.

Minor point: the RQ2 heading

Minor point. The RQ2 heading says that SWIFT "keeps improving after every baseline levels off" (line 410), but the paragraph says that AlphaZe** "improves throughout" and that P2SRO "improves steadily over the first five of its twelve hours" (lines 415–416).

We corrected the heading, which now reads "SWIFT is still improving after five hours and ends with both the strongest pursuer and the strongest evader".

We hope these results address the four points you named, and we are glad to discuss further.

Reviewer_esjROpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SWIFT (hardly an acronym), a self-play framework for learning pursuit policies in a modified version of the Scotland Yard game.

The proposed approahc tackles two problems with searching over possible hidden states:

  1. pursuers planning differently in situations they cannot distinguish, and
  2. an evader incorrectly modeling pursuers as knowing its location.

The framework shares pursuer search nodes across worlds with the same public history and conducts evader search from every possible location, reading the true-location root afterward. SWIFT combines this construction with a learned location prior that weights search backups, an autoregressive joint-action policy, and role-specific graph networks.

Critical strengths
  1. The theory seems to be sound. The treatment of assymetric information is coherent.

  2. The empirical results look really impressive.

  3. The belief-weighting ablation is well designed.

  4. The paper is tranparent about implementation and its iimitations.

Critical weaknesses
  1. I looks like the main conceptual contribution of the proposdd approach is sharing pursuer nodes and using multiple roots in the evader’s search. However, the ablations primarily examine belief weighting and the network encoder. There is no controlled experiment that separately removes either of these two search mechanisms while preserving the rest of SWIFT.
Questions for authors

Regarding the ablation mentioned in Critical Weaknesses 1.

  1. Could you turn off public-history node sharing and the evader’s multiple-root search one at a time, keeping the rest of the system and the compute budget the same? Runinng each version with a few different training seeds and showing how much each component contributes should strenthen the experimental evaluation.

Mostly out of curiostiy: 2. If you freeze the final SWIFT pursuer and train a new evader specifically to beat it, how well does the pursuer perform? I’d also be interested to see whether SWIFT still outperforms the strongest baselines in the three-pursuer version of the game.

3 comments
AuthorsOpenReview ↗

Response to Reviewer esjR

Thank you for the positive review. We ran all the experiments you suggested, and they support the paper's central claim.

Weakness 1 and Question 1: ablating the two search mechanisms

Weakness 1. I looks like the main conceptual contribution of the proposd approach is sharing pursuer nodes and using multiple roots in the evader’s search. However, the ablations primarily examine belief weighting and the network encoder. There is no controlled experiment that separately removes either of these two search mechanisms while preserving the rest of SWIFT.

Questions For Authors. Regarding the ablation mentioned in Critical Weaknesses 1.

  1. Could you turn off public-history node sharing and the evader’s multiple-root search one at a time, keeping the rest of the system and the compute budget the same? Running each version with a few different training seeds and showing how much each component contributes should strengthen the experimental evaluation.

We switched off each mechanism on its own, and both make the pursuer stronger. Node sharing contributes more than any other component of SWIFT. The rest of SWIFT and the compute budget stayed fixed: the networks, the location prior, the KataGo tricks, N = 300 simulations per decision and five hours of training. Pursuer rating relative to SWIFT after 5 h (revised Figure 4, one pool):

VariantPursuer rating vs. SWIFT
SWIFT w/ separate pursuer trees (no node sharing)−590
SWIFT w/ single evader root (no multiple roots)−80 (up to −170 during training)

Removing node sharing costs the pursuer more than any other ablation, including removing the KataGo tricks (−400) or belief weighting (−215). Without multiple roots, the pursuer falls behind SWIFT after the first hour and stays behind. For the seeds, we trained SWIFT and the single-root variant with three seeds each, since this is the only ablation whose gap is close to the variation between runs. The SWIFT pursuer is rated higher in every seed, by 14 to 55 points (new Table 6), so multiple evader roots consistently produce a stronger pursuer across training runs. The single-root evader is rated about 100 points higher, mainly because its true root receives all 300 simulations instead of about 300/K. Multiple roots pay off in the pursuer trained against this evader. The full tables, including a 2×2 of search structure and KataGo tricks, are in the General Response, item 1 (revised §5.2; App. D.7).

Question 2: an evader trained against the frozen pursuer, and three pursuers

Mostly out of curiosity: 2. If you freeze the final SWIFT pursuer and train a new evader specifically to beat it, how well does the pursuer perform? I’d also be interested to see whether SWIFT still outperforms the strongest baselines in the three-pursuer version of the game.

The final SWIFT pursuer still wins 83% of games against an evader trained for two hours to beat it, and it is much harder to exploit than every learned baseline pursuer. A PPO evader trained from scratch against the frozen SWIFT pursuer wins 7% of games after half an hour, 12% after one hour and 17% after two. The same learner, trained the same way, wins 68.4–99.6% against the frozen learned baseline pursuers after two hours (General Response, item 2; revised §5.1, Figure 2; App. D.8).

In the three-pursuer game, SWIFT still outperforms the strongest baseline. We trained P2SRO there, the baseline that beats the SWIFT evader most often in Table 1. With less training time, SWIFT wins more often against every heuristic evader and as often against the learned evader. Pursuer win rate (%) (App. D.5, Figure 10):

PursuerRandomGreedyTerritorySWIFT evader of this game
SWIFT (8 h)100978229
P2SRO (about 14 h)94866528

We are glad to discuss any further questions.

Thank you for your detailed responce.

I assume all the exepriments discusses in this thread will go into the appendices of the paper.

Given the drawback discussed here, I am not improving my score to Clear accept, and still maintaining the Weak accpet score.

This is still recommendation of acceptance, obviously.

Good luck!

AuthorsOpenReview ↗

Response to Reviewer esjR

Yes, the experiments discussed in this thread are part of the revised PDF.

Thank you again for providing the detailed review and helping us further improve this paper!

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response (1/3)

We thank the reviewers for their careful and constructive feedback. Changes in the revised PDF are marked in blue.

The reviews converge on three questions: does each search component of SWIFT matter, how easily can the trained pursuers be exploited, and how does SWIFT compare with an established Scotland Yard program? We ran new experiments for all three, and the answers support the paper's claims:

  • Each search component of SWIFT strengthens the pursuer (esjR, vUZe, EEEB). Using a separate pursuer tree for each sampled evader location costs 590 rating points, the largest drop of any ablation. Letting the evader search only from its true location also weakens the pursuer, in all three training seeds.
  • The SWIFT pursuer is much harder to exploit than every learned baseline (esjR, vUZe, EEEB). A PPO evader trained against the frozen final SWIFT pursuer wins 17% of games after two hours, compared with at least 68% against every learned baseline pursuer.
  • SWIFT is stronger than PimBot, an established MCTS program for Scotland Yard (vUZe, EEEB). We reimplemented PimBot for our rules with all components of the original program, adapting only what the rule changes require. In the ratings, both the pursuer and the evader of SWIFT pass PimBot within three hours of training. In direct play, SWIFT without search wins more than half of the games averaged over the two roles, even when PimBot searches with 10⁶ simulations per decision.

1. Ablation of the search components (esjR, vUZe, EEEB)

We switched off each search component on its own and kept everything else as in SWIFT: the networks, the location prior, the KataGo tricks, N = 300 simulations per decision and five hours of training.

  • SWIFT w/ separate pursuer trees switches off node sharing. Each sampled evader location (world) keeps its own pursuer nodes in both searches, as in per-world search.
  • SWIFT w/ single evader root switches off the multiple evader roots. The evader searches only from its true location, so the pursuers it imagines can act on that location.

(a) One component at a time. Both components make the pursuer stronger, and sharing pursuer nodes contributes most. Pursuer rating relative to SWIFT after 5 h, from revised Figure 4, which rates SWIFT and all its ablations in one pool:

VariantPursuer rating vs. SWIFT
SWIFT w/ separate pursuer trees (new)−590
SWIFT w/o KataGo tricks (new)−400
SWIFT w/o belief weighting−215
SWIFT w/ single evader root (new)−80 (up to −170 during training)

Separate pursuer trees cause the largest drop of any ablation, so information-consistent pursuer search is the core of SWIFT's strength. Without multiple evader roots, the pursuer falls behind SWIFT after the first hour and stays behind. On the evader side, separate trees cost 240 points, while the single-root evader is rated about 100 points higher. This ablation changes two things at once. The imagined pursuers can again act on the true location, although their network inputs remain public, and the true root receives all 300 simulations instead of about 300/K. Since the evader sees the full state, the larger budget at its true root outweighs the bias of its opponent model at N = 300. Multiple roots keep the evader's opponent model information-consistent, and this pays off in the pursuer trained against this evader, which is the focus of the paper. They need not maximize the evader's own strength at a fixed budget.

(b) Training seeds. We trained SWIFT and SWIFT w/ single evader root with three seeds each, because this is the only ablation whose gap is close to the variation between runs. Pursuer ratings after 5 h, in a separate pool of the final networks (new Table 6, App. D.7):

PursuerSeed 1Seed 2Seed 3Mean ± std
SWIFT1813179017111771 ± 53
SWIFT w/ single evader root1763173516971732 ± 33

The SWIFT pursuer is rated higher in every seed, by 14 to 55 points. Across three independent training runs, multiple evader roots thus consistently produce a stronger pursuer than a single root.

AuthorsOpenReview ↗

General Response (2/3)

(c) Search structure × KataGo tricks. Shared pursuer nodes beat separate pursuer trees whether the KataGo tricks (forced playouts, policy-target pruning, LCB policy targets and side positions) are switched on or off. The tricks, in turn, help only when pursuer nodes are shared. Pursuer ratings after 5 h, in one pool formed by these four runs (this response only):

Pursuer searchKataGo tricks onKataGo tricks offEffect of tricks
Shared pursuer nodes20221639+383
Separate pursuer trees14381461−23
Effect of sharing+584+178

The tricks amplify information-consistent search but cannot repair per-world search, so the advantage of SWIFT's search structure does not come from the tricks. In the shared-node runs, the evader searches from a single root; in the separate-tree runs, it keeps one root per possible location. Since a single root weakens the pursuer (a), this choice does not favor the shared-node rows. Our responses to vUZe and EEEB add AlphaZe** with the KataGo tricks.

2. Best-response evaders against the final pursuers (esjR, vUZe, EEEB)

An evader trained against the frozen final SWIFT pursuer wins only 17% of games after two hours, whereas the same learner wins 68.4–99.6% against the learned baseline pursuers. The SWIFT pursuer is thus much harder to exploit than any learned baseline: at every point of training, an evader adapting to it wins far less often than one adapting to a baseline. Evader win rate (%) on the validation positions (revised §5.1, Figure 2; new App. D.8, Table 7):

Frozen pursuer0.5 h1 h2 h
SWIFT7.212.117.4
P2SRO53.362.368.4
PPO-GNN72.781.484.6
MAPPO-GNN78.983.888.5
AlphaZe**93.096.196.1
PPO-MLP99.6100.099.6

Each frozen pursuer plays exactly as in Table 1, choosing the most probable legal action without search (P2SRO plays its meta-strategy). Against each of them, we trained a PPO evader from scratch with the same configuration and initial weights. Every 15 minutes, the learner's greedy policy plays 512 validation games.

Within half an hour, the learner already wins more than half of the games against every learned baseline pursuer, but only 7% against SWIFT. During the second hour, its win rate against SWIFT rises by only 5 points (12% → 17%). The fixed evaders of Table 1 win at most 1.8% against SWIFT, so adaptation helps the evader. Even so, the SWIFT pursuer wins 83% of games against an evader trained specifically to beat it.

3. Comparison with PimBot (vUZe, EEEB)

Averaged over the two roles, SWIFT without search wins more than half of the games against PimBot at every PimBot budget from 10 to 10⁶ simulations per decision. Win rate (%) of SWIFT, 100 games per role and budget (new App. D.9, Figure 15):

PimBot simulations per decision1010²10³10⁴10⁵10⁶
SWIFT as pursuer100100100999998
SWIFT as evader1009765281710
Mean of both roles10098.582.563.55854

As evader, SWIFT loses more often to stronger PimBot pursuers, in line with the pursuers' structural advantage in this game. In Table 1, where PimBot searches with 10⁴ simulations per decision, PimBot is the strongest baseline pursuer, with an average win rate of 85.7% against the learned evaders (SWIFT: 98.5%), and the SWIFT evader is its hardest opponent. In the ratings, SWIFT's evader passes PimBot after about two hours of training and its pursuer after about three (Figure 3).

PimBot (Nijssen & Winands, 2012) is a published MCTS program for Scotland Yard that uses no learning. We reimplemented it on our game engine with all components of the original: one pursuer tree shared by all determinizations, UCT with progressive history, ε-greedy playouts with the original heuristics, black-ticket filtering, coalition reduction and location categorization. We adapted only what depends on the rules: PimBot plays our rules, so its handling of double moves is not needed, and the location-category weights are re-estimated from 1000 self-play games under our rules. As vUZe and EEEB requested, we also corrected the description of Student of Games in §1 and §2.

AuthorsOpenReview ↗

General Response (3/3)

The main revisions, all marked in blue in the PDF:

  • Abstract and §1 Introduction
    • The paper is framed around pursuit-evasion games with one-sided partial observability, with adapted Scotland Yard as the testbed (EEEB).
    • The description of Student of Games is corrected (vUZe, EEEB).
  • §2 Related Work: Student of Games (its full-map evaluation and the source of its cost) and PimBot (single-tree determinization with location categories) (vUZe, EEEB).
  • §3 Problem Formulation: the differences from the classic rules are described in more detail and more clearly (vUZe).
  • §5 Experiments
    • New baseline: PimBot in both roles (Table 1, Figure 3) (vUZe, EEEB).
    • New best-response evaluation (Figure 2) (esjR, vUZe, EEEB).
    • RQ1 explains the gap to AlphaZe** with the ablation of separate pursuer trees, rated in the same pool as SWIFT, instead of comparing ratings across figures (vUZe).
    • RQ2 heading corrected (vUZe).
    • RQ3 adds the ablations of both search components and of the KataGo tricks (Figure 4) (esjR, vUZe, EEEB).
    • The setup states which baselines train against learning evaders and which against Greedy (EEEB).
  • §6 Conclusion: revised in line with the new results.
  • Appendix
    • D.4 (new part): calibration of the location prior against the exact belief (Figure 9) (EEEB).
    • D.5 (updated): three pursuers, with P2SRO trained in the same game (esjR, EEEB).
    • D.7 (new): controlled search ablation and three training seeds (Table 6) (esjR, vUZe, EEEB).
    • D.8 (new): best-response setup (Table 7) (esjR, vUZe, EEEB).
    • D.9 (new): PimBot reimplementation and budget sweep (Figure 15) (vUZe, EEEB).
    • D.10 (new): distribution of K and the budget of the true root (Figure 16) (vUZe).
AuthorsOpenReview ↗

Response to Reviewer vUZe

Thank you for checking the revision so carefully and for raising your rating. We agree with every point and have uploaded a revised PDF with the changes below.

1. Changes to Table 1. Yes, AlphaZe** was retrained. Appendix C states that AlphaZe**, like the original method, uses none of SWIFT's KataGo tricks. However, the submitted version of AlphaZe** still used two of them: shaped Dirichlet noise at the root and first-play urgency reduction. We retrained AlphaZe** with both switched off, so that it matches this description; the networks, training pipeline, training time and evaluation protocol are unchanged. All cells in its row and column, its curves in Figure 6 and the related numbers in the text come from this run. No other agent was retrained, so the other cells are unchanged. As you note, the correction slightly favors AlphaZe** and leaves the conclusions of Section 5.1 unchanged. Since this correction was not directly related to the issues raised in the first review reports, we did not discuss it in our responses or highlight the updated numbers in the revised PDF.

2. Evidence for the attribution at line 466. We added the joint rating pool to Appendix D.7 (new Table 7), with SWIFT, its ablations and both AlphaZe** variants rated together. In this pool, SWIFT w/ separate pursuer trees is 589 points below SWIFT, and AlphaZe** is 784 points below. The discussion in Section 5.1 now points to this table, so the attribution rests on ratings from the same pool. With this new table, the best-response table is now Table 8.

3. Two claims in the conclusion. The conclusion now states the 98% result for "each fixed evader agent we test in Scotland Yard with five pursuers". It also states that an approximate best response trained for two hours wins only 17% of games against the SWIFT pursuers, compared with at least 68% against every learned baseline.

Minor.

  • The two eight-hour sentences were left over from the submitted Figure 3, whose insets showed longer runs of three variants. Since Figure 4 ends at five hours, we removed them.
  • The sentence on SWIFT w/ single evader root now separates the two results: its pursuer falls behind SWIFT after the first hour in Figure 4, and its final pursuer is rated below that of SWIFT in all three seeds of Table 6.
  • Sections 1 and 2 now state the budget: Student of Games wins 55% of games against PimBot with 10710^7 simulations per search.

We also rechecked the details throughout the paper. Thank you again for your careful reading and constructive suggestions, which have made the paper more accurate.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.