簡易檢索 / 詳目顯示

研究生: 陳昌裕
論文名稱: 五子棋新棋規與五~七路五子棋勝負問題之研究
指導教授: 林順喜
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2013
畢業學年度: 101
語文別: 中文
論文頁數: 51
中文關鍵詞: 五子棋人工智慧
論文種類: 學術論文
相關次數: 點閱:306下載:28
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 五子棋(Gomoku)這個歷史悠久的遊戲,盤面大小和圍棋不相上下,其搜尋的空間複雜度是十分龐大的,但因為對先下的黑方有利,因此很早就被看出是很不公平的遊戲。隨著電腦演算法的進步,1994 年Allis利用“迫著搜尋”(Threat Space Search)證明出黑先必勝,而2001年,Wagner及Virag更證明出有禁著的連珠棋(Renju)規則依舊是個黑先必勝的遊戲。因此也有非常多新的棋規陸陸續續被提出來,可惜治絲益棼,這些新棋規一旦發現黑方仍佔優勢時,就越改越繁複,使得玩家也越來越無法記住所有的棋規了,這在其它的遊戲,是少有這個演變的現象。
    本論文就五子棋的困境,首度提出一個簡易的「林氏新棋規」,其中有三個目標:「維持連五」、「規則簡單」及「雙方公平」,試圖挽救五子棋的命運。這棋規規定第一手黑方只能下在棋盤的外環區域,第二手起雙方就全部都自由了。經由初步利用五子棋軟體做實驗及探討,驗證出其確實可行,希望再賦與五子棋一個新生的機會,後續利用depth first proof number search演算法技術求出五~七路五子棋盤面各點先手的勝負結果。將來使用這個簡單的新棋規,我們就可有一個對黑白雙方都較為公平的遊戲,期望可再開啟這一個益智遊戲的新紀元。

    附表目錄 v 附圖目錄 vi 第一章 緒論 1 第一節 前言 1 第二節 研究動機 4 第三節 論文架構 4 第二章 文獻探討 5 第一節 各式五子棋棋規介紹 5 第二節 目前五子棋的困境 11 第三章 如何挽救五子棋的命運? 13 第一節 六子棋 13 第二節 林氏新棋規 14 第三節 尋找公平邊界 15 第四節 迫著搜尋 19 第四章 資料結構與演算法 21 第一節 Proof Number Search演算法 21 第二節 Depth First Proof Number Search演算法 24 第三節 Bitboard介紹 26 第五章 程式改良與實驗數據 28 第一節 走步產生改良 28 第二節 連五判別改良 30 第三節 Deadpoint加速法 33 第六章 實驗結果與分析 36 第一節 前言 36 第二節 實驗一 36 第三節 實驗二 38 第七章 結論與未來研究方向 42 參考文獻 43 附錄A 測試盤面 46 附錄B Magic Number(一) 48 附錄C Magic Number(二) 50

    [1] 六子棋首頁,http://www.connect6.org/。
    [2] 向祚雲,介紹五子棋的一種新規定——優連五子棋棋規,http://www.wuzi8.com/Article/HTML/ 2256.html。
    [3] 李睿凡,關於五子棋的常見誤解,http://122.225.62.170:8080/viewthread.php?tid=16&from=indexheats。
    [4] 技術深研 http://chessprograming.wikispaces.com。
    [5] 林氏五子棋新棋規首頁,http://www.csie.ntnu.edu.tw/~linss/Lin-Rule-For-Five-in-a-row.htm。
    [6] 黃德彥,五子棋相關棋類人工智慧之研究,國立交通大學碩士論文,2005年。
    [7] 劉雲靑,六子棋中一個結合迫著搜尋的防禦性策略。國立臺灣師範大學碩士論文,2009年。
    [8] 詹宜智,適用於六子棋之 PNS 研究,國立交通大學碩士論文,2009。
    [9] L. V. Allis, “Searching for Solutions in Games and Artificial Intelligence,” Ph.D. Thesis, University of Limburg, Maastricht, 1994.
    [10] L. V. Allis, “A Knowledge-Based Approach of Connect-Four: The game is over, White to move wins,” M.Sc. thesis, Vrije Universiteit, Amsterdam, 1988.
    [11] L. V. Allis, H. J. van den Herik, and M. P. H. Huntjens, “Go-Moku Solved by New Search Techniques,” Computational Intelligence, Vol. 12, 1996, pp. 7–23.
    [12] L. V. Allis, M. van der Meulen, H. J. van den Herik, “Proof-number search,” Artificial Intelligence, Vol. 66 (1), 1994, pp. 91–124.
    [13] L. V. Allis and P. N. A. Schoo, “Qubic Solved Again,” In H. J. van den Herik and L.V. Allis (eds.), Heuristic Programming in Artificial Intelligence 3: The Third Computer Olympiad, Ellis Horwood, Chichester, 1992, pp. 192–204.
    [14] A. Nagai, "Df-pn algorithm for searching AND/OR trees and its applications", Ph.D. Thesis, Gunma University, 2002.
    [15] D. M. Breuker, J. W. H. M. Uiterwijk, and H. J. van den Herik, “Solving 8×8 Domineering,” Theoret. Comp. Sci., Vol. 230, 2000, pp. 196–206.
    [16] H. J. van den Herik, J.W.H.M. Uiterwijk, and J.V. Rijswijck, “Games solved: Now and in the future,” Artificial Intelligence, Vol. 134, 2002, pp. 277–311.
    [17] P. Kannan, “Magic Move-Bitboard Generation in Computer Chess,” April 30, 2007.
    [18] A. Kishimoto, “Correct and Efficient Search Algorithms in the Presence of Repetitions”, Department of Computer Science, Univerity of Alberta, 2005.
    [19] Ogemust http://code.google.com/p/ogemust/source/browse/src/?r=30485314b5f7b532faa1a63c7b98808371286edb.
    [20] P. S. Segundo, R. Galán, F. Matía, D. R.-Losada, A. Jiménez, "EFFICIENT SEARCH USING BITBOARD MODELS", Intelligent Control Group, Universidad Politécnica de Madrid, 2006.
    [21] Renju International Federation, The International Rules of Renju, http://www.renju.nu/ rifrules.htm.
    [22] G. Sakata and W. Ikawa, Five-In-A-Row. Renju. The Ishi Press, Inc., Tokyo, Japan.
    [23] M. P. D. Schadd, M. H. M. Winands, M. H. J. Bergsma, J. W. H. M. Uiterwijk, and H. J. van den Herik, “Fanorona is a Draw,” ICGA Journal, Vol. 30(1), 2007, pp. 43–44.
    [24] J. Wágner and I. Virág, “Solving Renju,” ICGA Journal, Vol. 24(1), 2001, pp. 30–34.
    [25] I-C. Wu and D.-Y. Huang, “A New Family of k-in-a-row Games, ” ACG11, September 2005.

    下載圖示
    QR CODE