電腦科學與資訊工程科Computer Science & Information Engineering190032
The GoClub-梅花棋演算法效率及適用性分析 Taiwan
本研究旨在研究一款自創棋類遊戲「梅花棋」,找出效率最佳的演算法及分析AI的適用性。遊戲規則如下:雙方玩家輪流在19階的棋盤上下棋,先手執黑子,後手執白子,任一方形成梅花即獲勝。隨著棋子的增加,肉眼判斷勝負愈發困難,因此希望借助電腦的力量完成它。我們透過C++編寫程式,不斷修改演算法,提升電腦的精確度與流暢度。過程中依序提出了平均演算法、畢氏定理演算法、向量演算法、以及網狀編碼演算法。在最新版本中,我們使用含有螺旋編碼表的網狀編碼演算法,這可使電腦快速正確地判斷勝負。得到最佳的演算法後,我們運用撰寫Minimax演算法編寫AI,並且利用Victory notion的概念分析兩者間的相似度,判斷其對於梅花棋的適用性。透過不斷與Minimax演算法測試遊戲,將梅花棋規則中,先後手的優勢差距逐漸縮小。目前本研究已可進行複雜的雙人對戰與簡易的人機對戰。