五子棋新棋規與五~七路五子棋勝負問題之研究

Abstract

五子棋(Gomoku)這個歷史悠久的遊戲，盤面大小和圍棋不相上下，其搜尋的空間複雜度是十分龐大的，但因為對先下的黑方有利，因此很早就被看出是很不公平的遊戲。隨著電腦演算法的進步，1994 年Allis利用“迫著搜尋”(Threat Space Search)證明出黑先必勝，而2001年，Wagner及Virag更證明出有禁著的連珠棋(Renju)規則依舊是個黑先必勝的遊戲。因此也有非常多新的棋規陸陸續續被提出來，可惜治絲益棼，這些新棋規一旦發現黑方仍佔優勢時，就越改越繁複，使得玩家也越來越無法記住所有的棋規了，這在其它的遊戲，是少有這個演變的現象。 本論文就五子棋的困境，首度提出一個簡易的「林氏新棋規」，其中有三個目標：「維持連五」、「規則簡單」及「雙方公平」，試圖挽救五子棋的命運。這棋規規定第一手黑方只能下在棋盤的外環區域，第二手起雙方就全部都自由了。經由初步利用五子棋軟體做實驗及探討，驗證出其確實可行，希望再賦與五子棋一個新生的機會，後續利用depth first proof number search演算法技術求出五~七路五子棋盤面各點先手的勝負結果。將來使用這個簡單的新棋規，我們就可有一個對黑白雙方都較為公平的遊戲，期望可再開啟這一個益智遊戲的新紀元。