暗棋是由中國象棋衍生的一種具有隱藏訊息的遊戲。相較於圍棋、西洋棋等高複雜度遊戲，其複雜度主要來自於隨機性。近年來因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.

[1]施宣丞，暗棋程式Darkcraft 的設計與實作，2016，國立臺灣師範大學資工所碩士論文。
[2]Ken Thompson, “Retrograde Analysis of Certain Endgames,” ICCA Journal, vol. 9, no. 3, pp. 131-139, September 1986.
[3]J. Chen, T. Lin, B. Chen and T. Hsu, "Equivalence Classes in Chinese Dark Chess Endgames," in IEEE Transactions on Computational Intelligence and AI in Games, vol. 7, no. 2, pp. 109-122, June 2015.
[4]Yen-Chi Chen, Jia-Fong Yeh and Shun-Shii Lin, “Design and Implementation Aspects of a Surakarta Program,” ICGA Journal, vol. 40, no. 4, pp. 438-449, March 2019.
[5]C. Chen, G. Fan, S. Tsai, T. Lin and T. Hsu, "Compressing Chinese dark chess endgame databases," 2015 IEEE Conference on Computational Intelligence and Games (CIG), pp. 254-259, November 2015.
[6]徐大開，電腦暗棋程式Observer的設計與實作，2014，國立臺灣師範大學資工所碩士論文。
[7]S. Yen, C. Chou, J. Chen, I. Wu and K. Kao, "Design and Implementation of Chinese Dark Chess Pro-grams," in IEEE Transactions on Computational Intelligence and AI in Games, vol. 7, no. 1, pp. 66-74, March 2015.
[8]J. Chen, G. Fan, H. Chang and T. Hsu, "Compressing Chinese Dark Chess Endgame Databases by Deep Learning," in IEEE Transactions on Games, vol. 10, no. 4, pp. 413-422, December 2018.
[9]林品儒，增強學習架構與期望最小最大算法之愛因斯坦棋實作比較，2019，國立台灣師範大學資工所碩士論文。
[10]吳天宇，基於 AlphaZero General Framework 實現 Breakthrough 遊戲，2019，國立台灣師範大學資工所碩士論文。
[11]C. Hsueh, I. Wu, J. Chen and T. Hsu, "AlphaZero for a Non-Deterministic Game," 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI), pp. 116-121, December 2018.
[12]Jouandeau N., Cazenave T. “Small and Large MCTS Playouts Applied to Chinese Dark Chess Stochas-tic Game,” in: Cazenave T., Winands M.H.M., Björnsson Y. (eds) Computer Games. CGW 2014. Communications in Computer and Information Science, vol. 504, pp. 78-89, August 2014.
[13]Chang HJ., Hsu T. “A Quantitative Study of 2×4 Chinese Dark Chess,” in: van den Herik H., Iida H., Plaat A. (eds) Computers and Games. CG 2013. Lecture Notes in Computer Science, vol. 8427, pp. 151-162, July 2014.
[14]陳志昌，顏士淨，電腦暗棋多暗子殘局庫之設計與製作，2015，科技部計畫，中原大學應用數學系。
[15]桌上遊戲，維基百科。https://zh.wikipedia.org/wiki/%E6%A1%8C%E4%B8%8A%E9%81%8A%E6%88%B2
[16]陳志昌，TCGA 2015 暗棋比賽規則。
https://web.ntpu.edu.tw/~jcchen/clients/ver3/chinesedarkchess_Rule.txt