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