學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
1 results
Search Results
Item 暗棋殘局庫的壓縮與實做(2020) 唐豪; Tang, Hao暗棋是由中國象棋衍生的一種具有隱藏訊息的遊戲。相較於圍棋、西洋棋等高複雜度遊戲，其複雜度主要來自於隨機性。近年來因AlphaGo的出現，電腦在高複雜度的完全資訊遊戲處理上有了極大的進步。但面對不完全資訊遊戲的處理還不是那麼成熟，反而是傳統的極小化極大演算法、alpha-beta剪枝法對於不完全資訊遊戲有較高的適應性。此類演算法要找到最佳解將需要大量的思考時間，如何減少程式的思考時間是一個重要的課題。在面對殘局時，暗棋常常出現剩下少許子數卻需執行大量走步才能使遊戲結束的情況。殘局庫的製作及使用將能大大增強暗棋程式的棋力。 本研究針對暗棋製作殘局庫，運用回溯分析法生成殘局庫，以位元棋盤(bitboard)加快合法走步的搜索和遊戲勝負的判斷。最後以一個無衝突的對射函數(bijective function)對棋子位置進行索引，並記錄遊戲結果及到達該結果所需步數。