---
id: "20260821-0225-verify-nashs-hex-strategy"
title: "Verify Nash's Hex strategy-stealing proof (non-constructive; PSPACE-hard to construct) against a math-history primary or scholarly secondary"
type: "capture"
status: "promoted"
origin: "batch"
writer_model: "claude-sonnet-5"
date_created: "2026-08-21T00:00:00.000Z"
provenance: "this batch run, 2026-08-21"
derived_from: ["claim-nash-hex-first-player-win-proof-is-non-constructive","question-verify-nash-hex-strategy-stealing-non-constructive-primary"]
tags: ["hex","game-theory","john-nash","strategy-stealing","non-constructive-proof","pspace-complete","history-of-mathematics","quote-verification"]
promoted_to: ["30-notes/claim-nash-1952-rand-report-confirms-hex-proof-non-constructive.md","30-notes/claim-hex-winner-determination-is-pspace-complete.md","30-notes/claim-nash-hex-first-player-win-proof-is-non-constructive.md (existing note updated in place, not a new file: primary+secondary sourcing added, flag partially resolved)","40-entities/entity-piet-hein.md (new hub)","40-entities/entity-stefan-reisch.md (new hub)","40-entities/entity-ryan-hayward.md (new hub)","40-entities/entity-philip-henderson.md (new hub)","40-entities/entity-john-nash.md (existing hub updated: dated Updates line)","50-questions/question-verify-nash-hex-strategy-stealing-non-constructive-primary.md (marked answered)"]
not_promoted: ["Claim 2 as a standalone note (Henderson's dissertation independently tracing the strategy-stealing argument's naming/origin to Nash) — folded into claim-nash-1952-rand-report-confirms-hex-proof-non-constructive.md as a dual-sourced corroboration (source_url_2/source_quote_3) rather than a separate atomic note, since it restates the same historical fact as Nash's own primary rather than adding a genuinely distinct claim.","The Reisch-translation-mirror quote (Tier 3, [unverified-provenance — mirror]) as its own note — kept as non-load-bearing supporting texture inside claim-hex-winner-determination-is-pspace-complete.md instead; the Henderson Tier-2 citation alone clears that claim's sourcing floor.","Entity candidates Shimon Even and Robert Endre Tarjan — real and load-bearing to the PSPACE result, but their paper was not read directly this session (paywalled, only cited via Henderson), and a joint or thin biographical page for two unread-primary authors risked exactly the flood the entity spec warns against. Left as plain-text mentions in claim-hex-winner-determination-is-pspace-complete.md; promotable later if their 1976 paper is ever read directly.","Entity candidate Jack van Rijswijck — real, co-participant in the 1999 Nash interview and author of a separate Hex PhD thesis, but this capture's engagement with him is secondary to Hayward's and Henderson's (mentioned, not sourced from directly); left as a mention inside entity-ryan-hayward.md rather than promoted to his own hub.","Entity candidate Sylvia Nasar — flagged in the capture itself as an unread further lead ('A Beautiful Mind'), not yet consulted this session; per the entity spec, when unsure, don't promote."]
seek_code_commit: "17d9798"
---


Direct follow-up to [[question-verify-nash-hex-strategy-stealing-non-constructive-primary]],
raised against [[claim-nash-hex-first-player-win-proof-is-non-constructive]], which rested
solely on Tier-4 Wikipedia for its load-bearing point. This session located and directly
fetched (via `extract_pdf`, never a search summary) three sources that together clear the
sourcing floor: Nash's own 1952 RAND report (Tier 1 primary), a 2010 University of Alberta
PhD dissertation on Hex supervised by a leading Hex researcher (Tier 2 scholarly secondary),
and a translated mirror of Stefan Reisch's 1981 PSPACE-completeness paper (Tier 3, used only
as corroborating texture). **Result: confirmed on both halves of the question.** Nash's own
words describe the proof as a non-constructive contradiction argument that leaves the winning
strategy unknown; the PSPACE-completeness of determining a Hex position's winner (the modern
technical grounding for "the strategy is hard to construct") is independently attested by a
scholarly secondary citing the two primaries (Even & Tarjan 1976; Reisch 1981) directly.

## Claim: Nash's own 1952 RAND report states that the first-player win was proved by a non-constructive contradiction argument, and that the explicit winning strategy remained unknown

**Claim type**: historical / technical-mechanism (this is the exact load-bearing point the
existing vault note flagged as under-sourced) — Tier 1–2 required, met at Tier 1.

John Nash's own report to RAND, written after "a very interesting conversation with Claude
Shannon," states the result as a two-line summary: the first player has a winning strategy,
and that strategy is not known. In the body he gives the argument's shape directly: because
Hex cannot end in a draw and an extra stone is never a disadvantage, "one can give a simple
contradiction argument showing that the player who moves second cannot have a winning
strategy and thus that the first player can always win if he plays properly." He then states
plainly that no explicit strategy was in hand: "the first player does not seem to have a
simple winning strategy on a large board game." This is Nash's own account of the argument
later named the strategy-stealing argument (see next claim) — existence proved by
contradiction, construction left open.

source_quote: "one can give a simple contradiction argument showing that the player who moves second cannot have a winning strategy and thus that the first player can always win if he plays properly"
source_quote_2: "The winning strategy is, as yet, unknown."
source_url: "https://web.archive.org/web/2017id_/https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf"
source_sha: "f0f295b18ef3a3fc2e543507b63df920d26abbe82a43066fe0ca87c20045c9da"
source_title: "Some Games and Machines for Playing Them"
source_author: "John Nash"
source_venue: "RAND Corporation (Project RAND), Document D-1164"
source_date: "1952-02-02"
source_tier: 1
source_delight: "Nash's own two-sentence summary states in the same breath that a winning strategy is proven to exist and is 'as yet, unknown' — the non-constructive result in the discoverer's own words, seven years before anyone called it strategy-stealing."

Note on provenance: the live document lives at RAND's own site
(`https://www.rand.org/pubs/documents/D1164.html`, confirmed to exist via search, PDF at
`https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf`), but both `extract_pdf`
and `archive_page` returned HTTP 403 Forbidden against the live PDF this session — the
document is not gone, but is currently blocked to automated fetch tools. The text above comes
from the Internet Archive's Wayback Machine capture of that same PDF (captured 2017,
`tls: verified`), read via `extract_pdf` (method: OCR — text is clean and legible; a few OCR
artifacts like "aweakest link" for "a weakest link" appear in unquoted passages, none in the
quotes above). Worth a note alongside `sources.md`'s existing known-blocked-route entries if
rand.org direct-PDF 403s recur on a future session.

## Claim: A scholarly secondary — Philip Henderson's 2010 University of Alberta PhD dissertation on Hex, supervised by Hex researcher Ryan Hayward — independently traces the "strategy-stealing argument" directly to Nash's reasoning about Hex

**Claim type**: historical (naming/attribution) — Tier 3–4 acceptable per the floor for
uncontested history, but this clears Tier 2, strengthening the existing vault note beyond
the minimum.

Henderson's dissertation, *Playing and Solving the Game of Hex*, opens its literature review
by describing Nash's motivation and the origin of the argument:

> "By contrast, Nash was looking for a game whose value (assuming optimal play) could be
> deduced, yet where the method for attaining this outcome was completely unknown. Nash came
> to realize that if no draw was possible, and if having an extra move was never
> disadvantageous, then the existence of a first player winning strategy was guaranteed. This
> was the inspiration for the now well-known strategy-stealing argument."

The dissertation's own bibliography sources this directly to Nash's 1952 RAND report (above)
and, distinctly, to a December 1999 telephone conversation the thesis's supervisor Ryan
Hayward and colleague Jack van Rijswijck held with Nash himself — a second, later primary
this capture did not chase down (see Further leads). This is independent corroboration, from
a named researcher in an academic dissertation at a university with a standing Hex research
group, of the same non-constructive-existence-proof shape found in Nash's own 1952 words.

source_quote: "Nash was looking for a game whose value (assuming optimal play) could be deduced, yet where the method for attaining this outcome was completely unknown. Nash came to realize that if no draw was possible, and if having an extra move was never disadvantageous, then the existence of a first player winning strategy was guaranteed. This was the inspiration for the now well-known strategy-stealing argument."
source_url: "https://webdocs.cs.ualberta.ca/~hayward/theses/ph.pdf"
source_sha: "ca144da90581a063b9985fbc0f8c93178977d059351e4662945eb42ef7cfb0ea"
source_title: "Playing and Solving the Game of Hex"
source_author: "Philip Thomas Henderson"
source_venue: "PhD dissertation, Department of Computing Science, University of Alberta (examining committee chaired by supervisor Ryan Hayward), Fall 2010"
source_date: "2010"
source_tier: 2

## Claim: Determining the winner of a Hex position — the modern grounding for "the winning strategy is hard to construct" — is PSPACE-complete, per Even & Tarjan's 1976 result on generalized Hex and Stefan Reisch's 1981 extension to Hex itself

**Claim type**: quantitative/technical-mechanism (a specific complexity-class result) — Tier
1–2 required.

Henderson's dissertation states the complexity result directly, citing both primaries by
number in its bibliography (Even & Tarjan 1976; Reisch 1981):

> "Determining the winner of a Hex (or Generalized Hex) position is a PSPACE-complete
> problem. Thus, developing an efficient (i.e., polynomial-time) algorithm to solve arbitrary
> Hex positions is equivalent to proving that P equals PSPACE and, as a consequence, proving
> that P equals NP."

The two primaries behind that citation: Shimon Even and R. Endre Tarjan, "A Combinatorial
Problem Which Is Complete in Polynomial Space" (*Journal of the Association for Computing
Machinery* 23(4):710–719, 1976), proved PSPACE-completeness for *generalized* Hex played on
arbitrary graphs; Stefan Reisch, "Hex ist PSPACE-vollständig" (*Acta Informatica* 15:167–191,
1981), extended this to Hex itself, played on the standard board. An (unattributed,
undated) English-language translation of Reisch's paper states the same result in its own
words: "the problem to determine the player having a winning strategy in a given situation on
an n×n board of one of these games is as hard to solve as any problem computable in
polynomial space," concluding "Since it is easy to see that the decision problem for Hex is
in PSPACE, the decision problem for Hex is PSPACE-complete."

**Caveat on framing** — all three sources state PSPACE-completeness of the *decision*
problem (who wins from a given position), not literally "constructing the winning move is
PSPACE-hard." The equivalence between the two framings is standard in combinatorial game
complexity (an algorithm that outputs a winning move can decide the winner in polynomial
time by recursion, so hardness of one is generally taken to transfer to the other), but none
of the three sources read this session states the move-construction framing in those exact
words. The existing vault note's phrasing ("computing an explicit winning strategy... is
PSPACE-hard") should be read as this standard extension of the sourced decision-problem
result, not as a separate directly-quoted claim.

source_quote: "Determining the winner of a Hex (or Generalized Hex) position is a PSPACE-complete problem."
source_url: "https://webdocs.cs.ualberta.ca/~hayward/theses/ph.pdf"
source_sha: "ca144da90581a063b9985fbc0f8c93178977d059351e4662945eb42ef7cfb0ea"
source_title: "Playing and Solving the Game of Hex"
source_author: "Philip Thomas Henderson"
source_venue: "PhD dissertation, Department of Computing Science, University of Alberta, Fall 2010"
source_date: "2010"
source_tier: 2

Supporting (not load-bearing) quote, corroborating texture only:

source_quote: "the problem to determine the player having a winning strategy in a given situation on an n×n board of one of these games is as hard to solve as any problem computable in polynomial space"
source_quote_2: "Since it is easy to see that the decision problem for Hex is in PSPACE, the decision problem for Hex is PSPACE-complete."
source_url: "https://academic.timwylie.com/17CSCI4341/hex_acta.pdf"
source_sha: "601f8b89d89a4a7705151f45b07fda11731a38392fce004bc664a18deaf6c124"
source_title: "Hex is PSPACE-complete"
source_author: "Stefan Reisch (original, in German); English rendering as hosted, translator not credited"
source_venue: "English-language mirror/translation of \"Hex ist PSPACE-vollständig\" (Acta Informatica 15:167–191, 1981, Springer, paywalled), hosted on Tim Wylie's course site (academic.timwylie.com), not the original venue"
source_date: "1981 (original); translation date not stated"
source_tier: 3
flags:
  - "[unverified-provenance — mirror] This is a translation of unclear authorship/date hosted on a third-party course site, not Reisch's own venue or the original publisher (Springer/Acta Informatica, paywalled and not read this session). Used only as corroborating texture; the Tier 2 Henderson-dissertation citation is what clears the sourcing floor for this claim."

## Further leads

- John Nash, December 1999 — telephone conversation with Ryan Hayward and Jack van Rijswijck, cited in Henderson's dissertation bibliography (entry [129]) as a direct source on Nash's own account of Hex; no transcript located or read this session — a second primary, later in Nash's life, worth chasing if one exists.
- Sylvia Nasar, *A Beautiful Mind: A Biography of John Forbes Nash, Jr.* (Simon and Schuster, 1998) — cited in the same bibliography [127] as a further account of Nash's Hex work; not read this session.
- Shimon Even and R. Endre Tarjan, "A Combinatorial Problem Which Is Complete in Polynomial Space," *Journal of the ACM* 23(4):710–719 (1976) — the original generalized-Hex PSPACE-completeness primary; paywalled at the ACM Digital Library (dl.acm.org/doi/10.1145/321978.321989), not directly read this session.
- Stefan Reisch, "Hex ist PSPACE-vollständig," *Acta Informatica* 15:167–191 (1981) — the original German-language publication; paywalled at Springer (link.springer.com/article/10.1007/BF00288964); this capture used an unattributed English mirror instead (see Claim 3 flag).
- Ryan B. Hayward and Jack van Rijswijck, "Hex and Combinatorics," *Discrete Mathematics* 306(19–20):2515–2528 (2006) — cited repeatedly throughout Henderson's dissertation as the standard survey of Hex's mathematical history; not fetched this session, likely the single best next source for further corroboration or a cleaner primary-adjacent account.
- The live rand.org PDF for D-1164 (`https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf`) 403'd on both `extract_pdf` and `archive_page` this session; only the Wayback Machine's 2017 capture was fetchable. Worth logging as a possible known-blocked route in `sources.md` if this recurs on a future session.
- John Milnor, "A Nobel Prize for John Nash," *Mathematical Intelligencer* 17(3):11–17 (1995) — cited in Henderson's bibliography [124] as another historical secondary on Nash's mathematical work; not read this session.

## Safety flags

None. All three directly-fetched sources this session (Nash's 1952 RAND report via the
Wayback Machine, Henderson's 2010 PhD dissertation, and the Reisch translation mirror) were
ordinary third-person technical/historical prose — no addressed-to-AI language, override
language, claimed authority, tier self-assignment, file-system instructions, credential
requests, or urgency framing encountered. All three `extract_pdf` calls used for the quotes
above recorded `tls: verified`, not the unverified/elevated-suspicion case.

## Entity candidates

- Piet Hein — person — independently invented Hex in Denmark in 1942, before Nash's separate 1948 rediscovery at Princeton; per Nash's own memo, "It seems that it was originally discovered in Denmark, and rediscovered by the author at Princeton." Flagged first, per the known blind spot: the founding figure the game's own origin story (and thus every later account, including Nash's) measures itself against.
- Shimon Even and Robert Endre Tarjan — people — authors of the 1976 result proving *generalized* Hex PSPACE-complete, the foundational complexity result Reisch's 1981 Hex-specific proof explicitly positions itself against ("our proof is quite different from the proof provided by Even and Tarjan").
- Stefan Reisch — person — Universität Bielefeld mathematician who proved Hex itself (not merely its graph generalization) is PSPACE-complete, 1981.
- Ryan Hayward — person — University of Alberta computing scientist, leading Hex researcher, supervised Henderson's dissertation, and personally interviewed Nash by telephone in December 1999.
- Philip Henderson — person — author of the 2010 PhD dissertation used here as the scholarly secondary tracing Nash's proof and the PSPACE-completeness result; also built the strongest computer Hex solvers/players of his time (Wolve, MoHex).
- Jack van Rijswijck — person — co-participant in the 1999 Nash telephone interview; author of a separate Hex-focused PhD thesis (*Set Colouring Games*, 2006) cited throughout Henderson's dissertation.
- Sylvia Nasar — person — Nash's biographer (*A Beautiful Mind*, 1998); flagged as an unread further lead, not yet consulted this session.

> [!note] Seek's commentary:
> The find this session actually wanted was Nash's own memo, and it came through the back
> door — the live RAND page blocked every automated tool, and the only route in was a nine-year-old
> Wayback Machine snapshot of the same PDF. That's a strange kind of fragility for a
> foundational document: the primary source exists, is not paywalled, is hosted by a serious
> institution, and is still functionally unreachable to anything but a human with a browser or
> a lucky archive capture. The document itself rewarded the trip — Nash's own two-line summary
> is more direct than any later retelling, including the vault's own prior note, which had to
> rest on Wikipedia's paraphrase of a paraphrase. — Seek