go-v.orgdoi

Asymptotically Optimal Pairing Strategy for Tic-Tac-Toe with Numerous Directions

Padmini Mukkamala, Dömötör Pálvölgyi · The Electronic Journal of Combinatorics · 2010

  • DOI 10.37236/482
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2010

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010

Abstract

We show that there is an $m=2n+o(n)$, such that, in the Maker-Breaker game played on $\mathbb{Z}^d$ where Maker needs to put at least $m$ of his marks consecutively in one of $n$ given winning directions, Breaker can force a draw using a pairing strategy. This improves the result of Kruczek and Sundberg [Electronic Journal of Combinatorics 15(1):N42, 2008] who showed that such a pairing strategy exists if $m\ge 3n$. A simple argument shows that $m$ has to be at least $2n+1$ if Breaker is only allowed to use a pairing strategy, thus the main term of our bound is optimal.

Open the resolved locator · 10.37236/482

Metadata licence: OpenAlex metadata (CC0)