论文标题
三角形网格的制造商 - 破坏者划分游戏
Maker-Breaker-Crossing-Game on the Triangular Grid-graph
论文作者
论文摘要
我们研究$（P，Q）$ - 由Day推出的制造商Breaker Crossing Game和“ Maker-Breaker-Breaker Percolation Games I：Crossing Grids”中的Falgas Ravry。他们的论文中描述的游戏涉及两个玩家制造商和Breaker，他们轮流声称P和Q分别是该图的尚未获得的边缘。制造商的目标是从最左端的顶点到最右边的顶点，而断路器则旨在防止这种情况。该游戏是更通用的香农切换游戏的一个版本，并在方形网格图上播放。 我们考虑在三角形网格图上玩过的同一游戏$δ_ {（m，n）} $（横跨n个顶点高），旨在找到给定的$（P，Q，M，N）$，这是制造商或Breaker的获奖策略。我们建立了与Day和Falgas Ravry相似的策略，以表明： $ \ bullet $用于足够高的网格和$ p \ geq Q $制造商具有$（p，q）$ - $δ_ {（m，n）} $的$（p，q）$ - 交叉游戏的获胜策略。 $ \ bullet $用于足够宽的网格和$ 4P \ leq Q $，Breaker在$δ_{（M，N）} $上具有$（P，Q）$ - 交叉游戏的胜利策略。
We study the $(p,q)$-Maker Breaker Crossing game introduced by Day and Falgas Ravry in 'Maker-Breaker percolation games I: crossing grids'. The game described in their paper involves two players Maker and Breaker who take turns claiming p and q as yet unclaimed edges of the graph respectively. Maker aims to make a horizontal path from a leftmost vertex to a rightmost vertex and Breaker aims to prevent this. The game is a version of the more general Shannon switching game and is played on a square grid graph. We consider the same game played on the triangular grid graph $Δ_{(m,n)}$ (m vertices across, n vertices high) and aim to find, for given $(p,q,m,n)$, a winning strategy for Maker or Breaker. We establish using a similar strategy to that used by Day and Falgas Ravry to show that: $\bullet$ For sufficiently tall grids and $p\geq q$ Maker has a winning strategy for the $(p,q)$-crossing game on $Δ_{(m,n)}$ . $\bullet$ For sufficiently wide grids and $4p\leq q$, Breaker has a winning strategy for the $(p,q)$-crossing game on $Δ_{(m,n)}$.
