亞馬遜棋（Game of the Amazons），由阿根廷人WalteZamkauska在1988年推出的兩人棋類，是奧林匹亞電腦遊戲程式競賽的比賽指定棋類，由於局面過於複雜，僅第一步就有2176種走法，故該棋類多不用於人類之間比賽，而是用於計算機博弈相關方面的比賽與研究 。
亞馬遜棋的研究，實現包括了程式語言，算法思想，博弈思想等；常用的算法有蒙特卡洛算法，退火算法，遺傳算法的等；隨著機器學習的開展，亞馬遜棋作為計算機博弈的一個項目正逐漸的被更廣泛的熟知。
亞馬遜棋是全國大學生計算機博弈大賽和國際計算機博弈錦標賽的比賽項目之一。2017年全國大學生計算機博弈大賽亞馬遜棋組冠軍為來自北京科技大學的“夏洛克的博弈犬 ”代表隊(Sherlock's game dog)。
基本介紹
- 中文名：亞馬遜棋
- 外文名：Game of the Amazons
- 類型：兩人對弈棋類
- 推出人：Walter Zamkauska（阿根廷）
棋具簡介,規則,走法產生,局面評估,步法搜尋,相關術語,箭,空地,收益,
棋具簡介
亞馬遜棋-棋盤界面1、棋盤制式為10*10方格棋盤（如右圖）；
2、每方各4枚棋子，以黑白兩色區分敵我，雙方棋子的初始位置如圖；
規則
- 在10*10的棋盤上，每方有四個棋子（四個Amazons）；
- 每個棋子都相當於西洋棋中的皇后，它們的行棋方法與皇后相同，可以在八個方向上任意行走，但不能穿過阻礙；
- 當輪到一方行棋時，此方只能而且必須移動四個Amazons中的一個，並在移動完成後，由當前移動的棋子釋放一個障礙，障礙的釋放方法與棋子的移動方法相同（皇后的走法，不能穿過障礙），同樣障礙的放置也是必須的；
- 當某方完成某次移動後，對方四個棋子均不能再移動時，對方將輸掉比賽；
- 每次開局位於棋盤下方的玩家先手；
- 整個比賽中雙方均不能吃掉對方或己方的棋子或障礙。
走法產生
- 亞馬遜棋的走法分為兩步，首先要移動一個棋子，然後由當前被移動的棋子放置一個障礙，棋子的移動和障礙的放置都遵循皇后的走法，所以在生成一步的所有可行走法時，走法的結構中應該至少包括3個數據：起點，終點，障礙放置點；
- 由於亞馬遜棋走法存在上述的特點，導致每一步的可行走法數量十分龐大，平均在1000多種左右，第一步有2176種可行走法。
局面評估
- 由上面的介紹可知，亞馬遜棋的行棋目的是用障礙或自身棋子將對方棋子堵死，使其不能移動，而另一種思路則是圈地思想，用障礙或己方棋子為自己圈出足夠大的地盤（對方棋子不能進入的區域），因為對方的地盤沒有己方的多，這樣迫使對方自己最後無路可走，將自己堵死；
- 現在用的主要是後一種控制區域（地盤）的思想，當評估一個局面的好壞時，主要看對方棋子控制的區域和己方棋子控制區域的多少，至於什麼樣的區域算是己方的控制區域，現在多數用QueenMove的方法，詳細的可以參考論文An evaluation function for the game of amazons
步法搜尋
- 傳統的負極大方法：用負極大方法為搜尋的主體時，由於亞馬遜棋每步的可行走法數量十分龐大，所以可以向下展開的層數很少，兩層就會有數百萬個葉子節點。因此需要大量運用剪枝算法配合提前排序。
- MC方法，即蒙特卡洛方法：以蒙特卡洛方法為主體的搜尋方法也在亞馬遜棋中大量運用，但與圍棋中的MC方法不同的是，亞馬遜棋中的MC模擬並不模擬到局面的終了，而是只模擬到一定的層數，詳細的MC/UCT方法參見Amazons Discover Monte−Carlo和The Monte-Carlo Approach in Amazons
相關術語
箭
亞馬遜棋行棋過程中，一方移動一枚棋子之後，在該棋子所能直達的範圍內設定的“障礙”；
箭不可移動，箭所占據的位置棋子不可再次占據。
作用：起到阻擋、包圍對方棋子，圍占擴張己方“占領”區域的作用
箭不可移動，箭所占據的位置棋子不可再次占據。
作用：起到阻擋、包圍對方棋子，圍占擴張己方“占領”區域的作用
空地
沒有被棋子和行棋者設定的箭所占領的區域成為空地，亞馬遜棋棋盤初始共有92塊空地，對弈雙方可以 在空地上移動棋子設定箭。空地也作為終局判斷對弈雙方輸贏的依據；哪一方占領的空地數目多，哪一方便 獲勝。
收益
亞馬遜棋中的收益，也成為占領區域，雙方通過移子和設定箭來將空地劃歸自己管控範圍之內，最有效的方法就是限制對方區域的擴展，限制對方棋子的移動。收益是對空地的計算。
