單色k子棋

Abstract

本篇論文將探討一種k子棋的變體（即單色k子棋）：兩位玩家輪流在給定的棋盤上下棋，其中雙方玩家所使用的棋子沒有顏色差異。遊戲會在棋盤上產生了一條k子連線時結束，由下最後一子的玩家獲勝。和一般的k子棋不同，玩家不再需要佔領一整條k子連線；僅需佔領某條k子連線的最後一個空位即可。

本篇聚焦在此類遊戲的總步數估計。嚴格來說，是對最終棋盤上棋子（之於棋盤格數）的密度做估計。作為原始遊戲棋盤的延伸，平面網格（Z^2）和超立方體（[k]^d）是本篇主要探討的兩種棋盤類型。

就最小密度而言，對於平面網格棋盤上的單色3子棋，我們有確切值：1/17。對於其他更大的k，其介在1-16/k-o(k^(-1))和1-8/k+o(k^(-1))之間。對於超立方體棋盤，最小密度大致為1-2d/k+2d(d-1)/(k^2)±O(k^(-3))。

就最大密度而言，我們仍有平面棋盤上單色3子棋的確切值：1/5。對於不是3的倍數的k，其等於1-2/k。對於剩餘的k，上下界非常相近，其值介於1-2/(k-1)和1-2/k之間。超立方體的則是1-2/k-O(k^(-2))。

We introduce a variant of k in a row: On a given board, each of players claims a position in turns until there is a k in a row among all claimed positions. The difference to the original k in a row is that, in this variant, a player no longer needs to claim a full k in a row by themself to win the game; instead, claiming the last remaining position of a k in a row is sufficient.

We are curious about how long a game can last, or, equivalently, how dense a final board configuration can be. Likewise, we concern how sparse a configuration can be. We ask the same questions for various boards, say the infinite plane board and the hypercubes [k]^d for every d∈N. To answer it, we give bounds on the maximum and minimum densities configurations.

Speaking minimum density, on the infinite plane board, we have the exact answer, 1/17, when k=3. For other k, the minimum density is between 1-16/k-o(k^(-1)) and 1-8/k+o(k^(-1)). On the hypercube [k]^d, it is around 1-2d/k+2d(d-1)/(k^2)±O(k^(-3)).

Speaking maximum density, we still have the exact answer for the plane board when k=3, which is 1/5. For other k with 3∤k, it is exactly 1-2/k. For other multiple of 3, it is between 1-2/(k-1) and 1-2/k. On the hypercube, it is around 1-2/k-O(k^(-2)).