risk game ai agent

實施風險遊戲和人工智能代理人

1。摘要

1.1。遊戲描述

風險是兩到六名球員的外交，衝突和征服的戰略棋盤遊戲。在控制比賽的軍隊的球員之間旋轉，他們試圖從其他玩家那裡捕獲領土，並由骰子卷確定結果。遊戲的目的是佔據董事會上的每個領域，然後消除其他玩家。每個回合由兩個動作組成：

1. 草案：球員必須在自己擁有的任何領土上添加一定數量的陸軍部隊。
2. 攻擊：玩家可以選擇攻擊鄰國敵方領土，以征服土地，他們喜歡的軍隊數量。

1.2。項目目標

該項目的目的是通過規則中的一些更改來實施風險遊戲，並設計了能夠正確玩遊戲的人工智能代理，並且在面對其他對手（包括實際人類）的其他對手時有很大的勝利機會玩家或其他代理人。

2。遊戲實現

遊戲是使用Java編程語言實施的。控制轉彎，執行播放器請求的操作，更新遊戲地圖，檢查一切是否根據規則等發生，是代碼的此部分所做的事情。遊戲UI還通過.fxml文件設計，該文件繪製地圖，是將玩家連接到遊戲邏輯的平台。

3。AI播放器實施

本節重點介紹了啟發式方法的實施和評估，這導致了對遊戲風險的強大AI。

3.1算法

實施基於最小α-beta修剪算法。播放器根據DFS算法構建了預測樹。

3.1.1預測樹

每當輪到代理商玩遊戲時，就會製造一棵樹。樹節點是遊戲的狀態（該狀態下的遊戲地圖），每個邊緣都是當前狀態對攻擊結果狀態的攻擊。攻擊行動包括起步和針對領土的坐標以及被選為進攻部隊的單位數量。根節點是播放器必須選擇其移動的地圖的當前狀態。雖然，由於玩家在每個狀態下可能不允許的情況下，因此，由於玩家在每個狀態中可能擁有的可能動作，因此無法預測該遊戲的結束狀態。因此，玩家只能將樹構造到我們在代碼中定義的一定深度。在代理遊戲策略的特定部分中也有一些簡化，這些部分將在以下各節中進行解釋。為了使最佳決策能力的啟發法定義為最深的節點（樹葉），以評估達到該狀態的數量對玩家有益。該報告將在報告中進一步解釋啟發式方法。當確定葉子的值時，樹將被傳遞到minimax alpha-beta修剪，這種眾所周知的算法將發現玩家可以採取的最佳動作。

3.2。啟發式和簡化

3.2.1。起草階段

向領土提供單位可能是一項棘手的任務；從某種意義上說，我們希望提高攻擊力，同時確保在有攻擊危險的領土上具有足夠的防禦能力。在與敵方領土附近的國家中部署單位可能是保持這兩個目標之間平衡的明智方式。

簡化草案：
預測並在預測樹中預測所有可能的草稿方案將導致一棵複雜的樹，該樹將面臨前面提到的問題；因此，簡化的之一是，我們使用起草的啟發式方法，該啟發式被證明始終具有最佳的結果，並預測對手在起草中也採取了這種方法。換句話說，我們將起草結果刪除為預測樹的可能性，並將其更改為確定的草稿場景。

為了這樣做，我們採取以下步驟：
草稿heuristic：
步驟1：
將與X國相鄰的敵方國家的所有單位的總和彙編為我們稱之為邊境安全威脅（BST）的措施。

步驟2：
將此BST除以X中的單位提供了邊境安全比率（BSR），可以在所有邊境國家中進行比較。

BSR高的國家更有可能被敵方參與者征服，因為相鄰敵方國家的敵方單位數量相對較高，遠高於該國本身的單位數量。選擇具有較高BSR的國家可以通過降低BSR來提高其防禦力量。向BSR較低的國家提供單位，這意味著他們已經具有更好的防禦立場，將增加其進攻力量，從而增加了這些國家成功攻擊的機會。

步驟3：
通過將BSR除以球員擁有的所有BSR的總和，將其歸一化，將進行直接測量，有人可以安排單位。歸一化邊界安全比率（NBSR）由以下方式計算

它給出瞭如何在國家之間分配單位的直接比率。在這一點上，我們可以看到該比率會有問題，因為某些數據是無關緊要的，並且我們不想在所有領土上添加單位，因此我們通過對BSRX數據進行排序，將閾值設置在第二和第三步之間。下降的順序（我們更多地關注使防禦能力更強大），將數據與中間分開，並將數字設置為下半部分。

步驟4：

步驟4將繼續進行，直到沒有更多可用的單元可添加為止。

3.2.2。進攻階段

在攻擊階段進行了一些簡化，以使樹不那麼複雜，因此我們可以預測其更深層次的水平。這可以通過檢查哪些攻擊場景有更高的機會贏得戰鬥，而只將它們包括在樹上。

1. 攻擊性透露術，遠離衛星部隊比衛冕部隊更重要。
2. 所有攻擊者和防御者領土部隊的數字funittheattackingarmycanbeonlyequallyquallyqualtopheage
3. Intheeriginalgametheresultofattackisbasedondices和...但是，我們假設攻擊者是否會與帶有D單位的單位和防守者一起參加戰鬥，並且絕對比D大，攻擊者將贏得比賽，並且將留下廣告單位。這意味著我們將許多可能的節點刪除到一個確定的節點。
4. 每個回合中的球員都可以在零到最多三個攻擊之間，並假設對手也這樣做。

3.2.3。預測樹啟發式方法

為了評估樹葉對特定玩家的有益程度；我們已經定義了四個啟發式特徵，在學習啟發式過程中可以找到最好的權重，這將在以後進行解釋。所有功能都將結果返回到一個之間，因為當特徵相互近距離價值時，學習和分配權重將更加準確。

功能是：

1. 地圖所具有的近葉植物甲狀腺菌Aplayerownstoallowerownstoall。
2. 地圖中的近甲蟲甲蟲Allunitsthatare。
3. foreachterritoryxtheplayerowns，我們計算的eachenemyterritoryAdjacent：
   
   之後，我們計算所有Z的平均值，結果是我們使用的第三個功能。它顯示了我們的防守能力，並且越接近它表明我們具有更高的防守力量。
4. foreachterritoryXtheplayerowns，ifyisnumberofneighborenemymemy領土，Z是玩家擁有的鄰居領土的數量，P將計算出來：
   
   之後，我們計算所有P = AVGP的平均值。 （1 - AVGP）指出我們的領土多麼茂密和封閉，因為該遊戲的獲勝策略越高，例如當有大陸時，要專注於一個大陸並征服它，然後轉移到其他大陸。

3.3。學習和遺傳

在上一部分中，對每種啟發式方法的重量都有助於評估每個人贏得比賽的重要性和影響力。尋找這些權重的過程是通過遺傳和學習的。每個基因都是這四個功能的四個權重。我們首先在範圍內生成100組隨機權重[0,10]。之後，將發生10場比賽。對於每個錦標賽，將隨機選擇來自初級人口的10個基因。每對可能的基因將相互對抗，每場比賽中每場比賽的結果都將記錄在案。健身功能定義為每個基因的勝利數 /遊戲數量）。每個錦標賽中的三個頂部基因（基於健身功能）將被選擇，因此現在我們有30個最佳基因。其中，我們選擇了12對隨機對，每對進行分頻器，該對通過計算一對基因的平均重量來創建新基因。因此，我們現在有12個新基因。另一方面，3個基因是在我們擁有的30個基因中隨機選擇的，並通過將每個基因的一個隨機重量更改為範圍的另一個隨機重量來突變[0,10]。畢竟，我們現在有15個全新的基因，這些基因占主要人群，取代了我們已經擁有的15個最不好的基因。在這一點上，第二代基因生成。這個過程將繼續重複，直到生成基因的第4代。該人群中的最高基因將被選為代理商將使用的啟發式特徵的最佳權重。