Almost optimal pairing strategy for Tic-Tac-Toe with numerous directions

2010/05/29 by Padmini Mukkamala, Mukkamala, Padmini, Dömötör Pálvölgyi +1
Computer Science · Engineering · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems #math.CO #math.NT

paper · pdf · doi:10.48550/arxiv.1005.5469

arxiv created 2010/05/29 · openalex publication_date 2010/05/29 · arxiv updated 2010/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that there is an m=2n+o(n), such that, in the Maker-Breaker game played on \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 who showed that such a pairing strategy exits if m≥ 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.

Related

• Cubic tic-tac-toe: A matching-based approach
• Tic-Tac-Toe on Designs
• At Most 43 Moves, At Least 29: Optimal Strategies and Bounds for Ultimate Tic-Tac-Toe
• Pairing strategies for the Maker-Breaker game on the hypercube with subcubes as winning sets
• An n-in-a-row type game