词条 | 六贯棋 |
释义 | 简介六贯棋是在六边形格的棋盘上玩的图版游戏,亦是数学游戏,通常使用10乘10或11乘11的菱形棋盘(约翰·纳什则采用14×14的棋盘)。 在计算复杂性理论,六贯棋的复杂性已证明了是PSPACE完备的。(注意不少抽象策略游戏如国际跳棋、象棋和围棋都是EXPTIME完备。) 历史六贯棋最初在丹麦数学家海恩于1942年12月26日在丹麦报纸Politiken发表的一篇文章里出现,当时称为Polygon。1948年,约翰·福布斯·纳什(John Nash)重新独立发明了它。追随纳希的玩家最初称这个游戏为Nash。后来1952年Parker Brothers发行了一个版本,将它称为Hex,从此这个名字就定了下来。 规则六贯棋由两个人一起玩,有两种颜色,通常是红、蓝或黑、白。四个边平行填上两方的颜色。双方轮流下,每次占领一处空白格,在空白格放上自己颜色的棋子(或填上自己的颜色)。最先将棋盘属于自己的颜色的边连成一线的一方为胜。 由于先行的一方有极大的优势,所以有人发明了交换(Swap,或Pie rule)这个规矩。 获胜方法六贯棋不可能有和局。 六贯棋的棋盘通常是n×n,虽然两边不相等的棋盘是可行的,但两边之间距离较小的一方必胜。 棋盘大小为3至5的六贯棋都可以人手找到先行一方的必胜路线。棋盘大小为6的六贯棋由 Queenbee找到了必胜路线,棋盘大小为7的解答可在 杨靖的网站找到。 在n×n的棋盘,先行的一方有必胜路线。证明: 1.因为这个游戏是有限的,只有两个可能性(先走者胜或后走者胜),因为棋手移动时都在有限的选择里,根据博奕论的一个定理,其中一个棋手一定有必胜路线。 2.若果后走棋手有必胜路线,先走棋手只可以随便走一步,然后基于棋盘是对称的,跟随供后走棋手走的必胜路线。因为先走棋手的第一步不会损害他,他亦是必胜。于是,后走棋手有必胜路线的假设便引起矛盾。 相关游戏六贯棋是Y的子集 Shannon switching game与六贯棋不同,它并非PSPACE难。 六贯棋必胜的核心概念就是双活,而不同大小棋盘之间的关系就是堆栈,所以对任意大小的n层棋盘,皆可视为(n-1)层棋盘外再加一层,所以依照这个概念,我们只要有任意一种棋盘的必胜走法,就能利用六边形方格的特性向外扩张,立用这样的想法,省略中间的推导过程,那么设现在有一n×n的拿许棋盘,而我们有k×k拿许棋盘的必胜法,k≦n,现在在n×n的棋盘中任意下一点,则这一子所占有的“领域”,就是以这一子为一角,所画出来的k×k拿许棋盘,但是这一角需是k×k拿许棋盘的必是点之一,如此就能确保上下两端贯通,如果将这一块棋盘旋转,取刚好完全重叠的部份,能到一个六边形的方格,可想成以一个方格为基础所做出来的大方格,而这个方格,即是这一点所具有的”完整领域”,而先手接下来只要确保领域和领域了贯通,就能做出必胜策略,至于要如何贯通,就是要预测贯通点,只要预测出的贯通点或贯通方式有两种或两种以上,就能得到必胜策略。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。