Coalition wins in multiplayer k-in-a-row
In cyclic k-in-a-row on Z2 with p ≥ 3 players, a player has a winning strategy against all the others exactly when it moves first and either k = 1, or k = 2 and p ≤ 8. Against every other player, the target, the others force a win of one of them. When 2p > k they win in round k, the earliest possible, except that against a target in neither the first nor the last seat with 2p = k + 1 the earliest round they can force is k + 1; at (p,k) = (3,5) these rounds are computer-assisted against the first two seats. When 2p ≤ k they win before the target's k · 6k-1th turn, but only after round k + ⌊(k-2p)/2⌋ and after the target has made (p/(p-1))k-1/(4k(p-1))-1 turns: exponential time in k for fixed p, at a rate tending to 1 as p grows. With three players, k = 3 is the smallest length at which the opponents can stop the first player, and only by counterattacking: they win by move 9, whereas blocking alone loses by move 10. Their wins at k = 5,6,7 contrast with two-player k-in-a-row on the infinite board, which is open for these lengths. 2020 Mathematics Subject Classification: Primary 91A46; Secondary 05C57, 91A06. Files: the paper (PDF) and a reproduction archive with the LaTeX source of the paper, the two programs printed in Sections 12 and 13, the 67 strategy tables of Propositions 11.2 and 11.3 with their solver, two independent verifiers, the census of the distance bounds and two walks of the tables, and the exhaustive searches of the box game behind the optimal numbers of stages printed in Section 7.1; see README.md in the archive. Assisted by AI.
Authors
- Sungsoo Na (ORCID: https://orcid.org/0009-0005-5257-3374)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-03
- DOI
- https://doi.org/10.5281/zenodo.22930495
- Primary Topic
- Artificial Intelligence in Games
- Type
- preprint