暗棋殘局庫的壓縮與實做
Abstract
暗棋是由中國象棋衍生的一種具有隱藏訊息的遊戲。相較於圍棋、西洋棋等高複雜度遊戲，其複雜度主要來自於隨機性。近年來因AlphaGo的出現，電腦在高複雜度的完全資訊遊戲處理上有了極大的進步。但面對不完全資訊遊戲的處理還不是那麼成熟，反而是傳統的極小化極大演算法、alpha-beta剪枝法對於不完全資訊遊戲有較高的適應性。此類演算法要找到最佳解將需要大量的思考時間，如何減少程式的思考時間是一個重要的課題。在面對殘局時，暗棋常常出現剩下少許子數卻需執行大量走步才能使遊戲結束的情況。殘局庫的製作及使用將能大大增強暗棋程式的棋力。
本研究針對暗棋製作殘局庫，運用回溯分析法生成殘局庫，以位元棋盤(bitboard)加快合法走步的搜索和遊戲勝負的判斷。最後以一個無衝突的對射函數(bijective function)對棋子位置進行索引，並記錄遊戲結果及到達該結果所需步數。
Chinese Dark Chess is a derivative game based on Chinese Chess with hidden information. Chess and Go are games that have extremely high complexity. Unlike Chess and Go, the complexity of Chinese Dark Chess is mainly caused by its randomness. In recent years, the emergence of AlphaGo made the computer have great progress in the processing of high-complexity games. However, the traditional algorithms such as minimax and alpha-beta pruning are more adaptable while facing the processing of incomplete information games. These algorithms require a large amount of time to seek for the best solution. How to reduce the thinking time of the program is an important issue. When facing an endgame, there are often situations where a few pieces are left on the board but a lot of moves are needed to make the game end. The production and use of the endgame database will greatly enhance the strength of the Chinese Dark Chess program. This research aims at creating an endgame database for Chinese Dark Chess, generating the database through retrograde analysis, and using bitboard to speed up the search of legal moves and the judgment of game outcomes. Furthermore, a collision-free bijective function is used to index the position of the chess pieces. Finally, the result of the game and the number of steps required are recorded in the endgame database.
Chinese Dark Chess is a derivative game based on Chinese Chess with hidden information. Chess and Go are games that have extremely high complexity. Unlike Chess and Go, the complexity of Chinese Dark Chess is mainly caused by its randomness. In recent years, the emergence of AlphaGo made the computer have great progress in the processing of high-complexity games. However, the traditional algorithms such as minimax and alpha-beta pruning are more adaptable while facing the processing of incomplete information games. These algorithms require a large amount of time to seek for the best solution. How to reduce the thinking time of the program is an important issue. When facing an endgame, there are often situations where a few pieces are left on the board but a lot of moves are needed to make the game end. The production and use of the endgame database will greatly enhance the strength of the Chinese Dark Chess program. This research aims at creating an endgame database for Chinese Dark Chess, generating the database through retrograde analysis, and using bitboard to speed up the search of legal moves and the judgment of game outcomes. Furthermore, a collision-free bijective function is used to index the position of the chess pieces. Finally, the result of the game and the number of steps required are recorded in the endgame database.
Description
Keywords
暗棋, 殘局庫, 位元棋盤, 殘局庫壓縮, Chinese Dark Chess, endgame database, bitboard, endgame database compression