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代。该人群中的最高基因将被选为代理商将使用的启发式特征的最佳权重。