學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
9 results
Search Results
Item 八層三角殺棋的勝負問題之研究(2009) 白聖群電腦棋類遊戲在人工智慧領域中是很重要的。而三角殺棋部份，自從許舜欽教授在1985年研究出七層三角殺棋結果後。三角殺棋更多層數的結果，就沒有任何相關文獻了。 在本論文中，我們使用CPU為AMD Athlon64 X2 4000+ 2.1GHz，記憶體為8G Byte的個人電腦，花費約十四個小時半的時間，證明了兩種規則的八層三角殺棋皆為先手勝。 我們除了找到八層三角殺棋的結果，也提出了一些解三角殺棋勝負時，可以加快搜尋勝負速度的方法。雖然研究過程中花費許多時間在倒推法上，但我們也研究出來所有先前求出的盤面是可以運用到之後要求解的三角殺棋。並且提出了一個管理記憶體的方式，使得在求解三角殺棋的過程中，盤面資訊狀態可以儲存，這樣就可以利用較少量記憶體來解八層三角殺棋，而不必動用到虛擬記憶體。Item 六子棋中一個結合迫著搜尋的防禦性策略(2009) 劉雲青; Yun-Ching Liu摘要 k 子棋相關的研究一直有許多有趣的研究成果被發表出來，而其中於2005年所提出的六子棋則格外受到注目。從2006年開始，六子棋一直被列為ICGA電腦奧林匹亞中重要的比賽之一，投入六子棋的研究和參與比賽的團隊逐年增加。 這篇論文裡，從簡介現今應用在六子棋的相關技術和研究成果開始，接著提出六子棋上的一個防禦性策略以及一個策略性的審局方案。迫著搜尋演算法在電腦六子棋中有相當重要的地位，論文裡亦提出提升其實作上效能和精確度的技術。防禦性策略和迫著搜尋的結合也會被探討。 防禦性策略和迫著搜尋的結合的表現足以跟現今的一些頂尖的六子棋軟體分庭抗禮 ，可見其為一個相當有效的方法。我們整合這些技術所實作出的程式Kagami，於第十四屆ICGA 電腦奧林匹亞中獲得第四名。Item 電腦暗棋之設計及實作(2008) 謝曜安電腦棋類一直是人工智慧發展的重要領域之一，而電腦暗棋至今尚未有人對其做較深入的研究。暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、象棋是屬於完全資訊的棋類遊戲，所以如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情況下，會因分枝度過大無法做深入的搜尋，因此難以做出較佳的決策。 本論文首度對電腦暗棋做深入的研究，並提出一些演算法來解決電腦暗棋所面臨的相關問題。經實戰測試，我們所寫出來的暗棋程式可以擊敗市面上我們蒐集到的所有暗棋程式，棋力已接近人類玩家的一般水平。Item 電腦象棋開局庫之改進研究(2008) 張修正電腦棋類遊戲在人工智慧領域中是很重要的。而開局庫的部份，一直較缺乏深入的研究。開局庫的建造方法有從棋書輸入、對戰結果統計或是使用中局程式來自動展開。對於這麼龐大的開局庫，其中也可能包含了一些不好的走法。傳統的作法，可能需要聘請高段的棋手，來幫我們檢視及修正，但對於許多電腦棋類的作者來說，可能無法負擔這樣的花費。 在本論文中，我們首度提出一個新的建造開局庫的構想：以市面上可以取得的棋軟為師，我們可採集他們在開局時的走步，因而建造一個更完整的開局庫。再藉由目前棋軟所擁有的搜尋引擎，配合電腦可長時間運作的特性，來調整我們的開局庫，修正其中可能隱藏的錯誤。 經由實驗，我們發現這樣的作法可提高開局庫的正確性，並且可自動化地逐步更新開局庫。Item DTS演算法效能改良之研究(2007) 白聖秋電腦西洋棋在近年來已經大量使用平行搜尋演算法，目前表現最好的是使用DTS（Dynamic Tree Splitting）搜尋演算法，該演算法的作者Robert M. Hyatt所設計出來的電腦西洋棋程式Crafty也在2004年第12屆World Computer Speed Chess Championship比賽獲得第二名。 本篇論文主要研究DTS（Dynamic Tree Splitting）搜尋演算法，發現使用一些改良技巧，如改良方法一的控制CPU分配量與改良方法二的控制允許使用DTS搜尋演算法的最低層數，能將DTS（Dynamic Tree Splitting）搜尋演算法在電腦西洋棋程式中獲得更好的效能。我們也使用開放程式碼的Crafty20.14版做實驗，目前研究結果發現改良方法一能提升20％左右的效能，而改良方法二能提升35％左右的效能。Item 電腦象棋擴大空步剪裁演算法的設計及實作(2007) 郭哲宇目前大多數頂尖的象棋軟體都採用空步搜尋法，以增進搜尋效率，但這個方法有時會有水平效應的策略盲點。在本論文中我們設計一種改良的空步搜尋方法，可以增進搜尋速度且不會降低搜尋的正確性。且透過實驗分析結果，我們發現擴大空步搜尋的新方法，在平均狀態下可以展開較小的搜尋樹，且比單純使用標準空步搜尋有更佳的棋力。經對戰實戰，改良版和未改良版對戰之下，勝率逼近七成。Item 電腦象棋深象中局程式的設計與實作(2006) 黃文樟電腦博奕在人工智慧領域中，一直是引人關注的，在深藍打敗西洋棋棋王Karsparov之後，象棋由於複雜度與西洋棋接近，在資料結構與搜尋演算法方面與西洋棋有許多相似或共通之處，成為下一個最有可能打敗人類棋王的棋類遊戲，近年來也吸引了許多人投入研究。 本論文介紹電腦象棋程式“深象”(取得了在義大利杜林舉辦之第十一屆Computer Olympiad象棋比賽銅牌)的基本資料結構、搜尋演算法與審局函數的設計，以及對所使用的資料結構與搜尋演算法進行測試與分析，並針對提高棋力的核心－審局函數，提出我們的改進方案。 關鍵字:電腦象棋、搜尋演算法、審局函數、人工智慧。Item 電腦象棋知識庫的切捨技術(2006) 李任軒; Jen-Hsuan Li對儲存設備來說，資料的切捨非常重要，因為比起沒切捨而言，它能讓系統儲存更多的資料，如此一來，所用的磁帶量就比較少，在傳送及備份時也會比較快速。切捨也減少了網際網路上檔案的傳送時間和通訊頻寬。 本文介紹電腦象棋知識庫的切捨方法及實作經驗，以使龐大且完整的知識庫得以被切捨、精簡化卻不更改其走步的手順。如此一來，原本龐大、繁瑣、動輒上百萬譜的知識庫，可被切捨為便於攜帶，或網路上方便且快速傳輸的檔案，供棋友互相交流或研究使用。我們並且跟據原本的後代節點數及勝負和等資訊，提出一套精確的棋步與走子價值，作為探討開局走法的研究基礎及使用策略，以避免因審局的不準而造成MiniMax的分數差異，使得電腦在開局的階段下出緩著或劣著，導致輸棋的關鍵。 本論文之部份研究成果已實作在「師大深象」電腦象棋軟體中，在2006年5月底參加在義大利舉行之第11屆國際電腦象棋奧林匹亞競賽中，榮獲銅牌。未來希望能有更好的成績表現。Item UCT算法的適用性及改進策略研究－以黑白棋為例(2008) 方裕欽電腦棋類在人工智慧領域中，一直是引人關注的，而電腦黑白棋在1997年時，由Logistello打敗當時的人類冠軍Takeshi Murakami，可以說是電腦黑白棋的一個里程碑。而在2007年，MoGo圍棋程式以UCT演算法在9路圍棋的比賽中取得良好的成績，使人們開始注意到UCT演算法。而目前相關文獻中，尚未有任何文獻提出應用UCT演算法於黑白棋上的研究。 本論文首度將UCT演算法實作於黑白棋中，除了探討UCT演算法在黑白棋中的適用性外，並根據黑白棋的特性，提出部分改進策略。