5五將棋程式Wonders的設計與實作

Abstract

利用人工智慧與人對弈的這個概念，可以追溯自1769年。但直到了1950年，人工智慧這個領域出現了一位Shannon教授致力於如何發展能夠與人對弈的西洋棋程式，這領域的研究才逐漸有穩定發展的方向。許多後來從事電腦對局領域的相關研究人員，也都跟隨Shannon教授的觀念發展而來。直至現今，無論是西方的跳棋、西洋棋、五子棋、撲克牌，抑或是東方的象棋、暗棋、孔明棋、將棋等等，許多的對弈遊戲皆成為電腦對局領域裡面研究的項目。 其中日本的mini-shogi(5五將棋)，為日本將棋於1970年左右發展的其一分支。並於2007年開始，發展國際電腦對局的相關賽事。由日本的電氣通信大學所舉辦的UEC Cup到ICGA的Computer Olympiad，5五將棋已經成為在國際賽事中被熱烈參與的項目之一。在台灣近幾年也被TCGA(Taiwan Computer Games Association)和TAAI(Technologies and Applications of Artificial Intelligence)列為固定的競賽項目之一了。 本研究論文中實作之程式Wonders，利用alpha-beta搜尋來幫助我們找到最佳走步。並且利用嶄新的審局函數快速的減少搜尋分支，以減少執行時間。另外我們也使用暫存表以及Zobrist hashing 和 bitboard的技術來提升程式的計算效能。從2011年研發至今，Wonders於2013年的TAAI 電腦對局競賽當中獲得5五將棋的金牌，期望在未來能夠有更穩定且具有突破性的研究發展。Since 1769, people already started the research about artificial intelligence ( AI ) . Until 1950, Professor Shannon devoted in developing the program, which can play Chess against human. This field became more stable with his research. Till now, many games such as Chess, Checkers, Connect Five, Pokers etc. have already been included in computer games research. Among these games, mini-shogi came from a branch of shogi around 1970. The competition of computer mini-shogi had become one of the international events since 2007. From the UEC Cup in Japan to the Computer Olympiad from ICGA (International Computer Games Association), mini-shogi has become one of the important game items. In Taiwan, there are more and more competitions, for example, TCGA (Taiwan Computer Games Association) and TAAI (Technologies and Applications of Artificial Intelligence), that also included mini-shogi. In this paper, the author implemented the mini-shogi engine which is called “Wonders” with alpha-beta search algorithm for AI to search the best move. Cut-off and a novel evaluation function were applied to reduce the execution time. The transposition table, Zobrist hashing and bitboard techniques were used in the program. From 2011 till now, “Wonders” has already attended a lot of events. This program also won the champion of TAAI 2013 computer game tournament of mini-shogi. Hope we can have more stable and more promotions in this research in the future.