c# – 如何使用negamax算法

这是关于探索树中可能移动的每个节点.如果使用alpha-beta修剪,可以通过“修剪”(不评估)树的某些分支来提高算法的效率.我假设你没有使用修剪,而是要查看完整的树.

如果Mancala是一个非常简单的游戏,比如Tic-Tac-Toe,你可以在不需要“评估功能”的情况下实现算法.通过井字游戏,如果你发挥所有可能的动作,你将获得胜利,失败或平局.你可以在那里实现一个negamax算法而不考虑游戏的中间状态(即,在最后一个之前的任何移动),因为可能的移动数量非常有限,并且AI引擎很容易计算出所有的可能性一直到最后.

另一方面,在国际象棋中,“评估功能”(以下简称EF)是必不可少的,因为这个星球上没有任何硬件可以计算每一个可能的国际象棋移动顺序一直到游戏结束.因此,大多数国际象棋AI将深入12-14级,然后评估结果位置,为女王分配8分,为车辆分配5分,为主教或骑士分配3分,为棋子分配1分,然后为其分配额外分数像方块控制的东西(控制中心方块的点数更多),国王安全等等

对于Mancala来说,据我所知,可能需要评估函数,但评估函数可能很简单,例如仍然拥有的种子数量,也可能为种子添加点数.先进的职位. (我查找了Wiki Mancala,看起来有很多可能的变种 – 我不确定你正在使用哪一种.)

因此,negamax算法需要实现一定的深度(即,直到游戏结束时才使用所有可能的游戏),并且需要简单的EF.让我们假设你将实现AI看起来5个深度.关于negamax的好处是它是完全对称的和零和的;换句话说,如果AI的位置评估为5,则对于人类玩家评估为-5.如果对于人类玩家评估为13,则对于AI评估为-13.这是讨论的“单一号码”.考虑到这一切,AI算法看起来像这样(再次,没有修剪)：

1)检查每个可能的AI移动

2)对于每个动作,检查每个可能的对手响应

3)对于每个可能的响应,检查每个可能的AI移动

4)对于每个可能的AI移动,检查每个可能的对手响应

5)最后,对于每个可能的对手响应,检查每个可能的AI移动

现在我们已达到深度5,你已经构建了一个有5个级别的树,可能还有数千或数百万个树的叶子(底层节点).您可以对每个节点引用其父节点以及对其所有子节点的引用进行编码,以便您可以轻松遍历树,从父节点到子节点再返回.

一旦你正确设置了树,现在是时候实现negamax算法,如下(让我们假设AI玩家的分数越高越好)：

6)对于每个4级对手的反应,找到所有AI儿童动作中的最高评价,并修剪所有其他孩子.你正在确定你的AI将从哪个第五位移动以响应每个可能的第4对现在的对手响应.所以现在每个第4级响应都有一个假定的第5级响应.现在,您将第5级孩子的评估分数分配给第4级父母.这表示如果你达到第4级对手的移动,AI将会进行这个特定的第5级移动,并且棋盘将评估该分数.

7)接下来,你评估每个第3级AI动作,并且对于每个动作,在所有第4对现在的对手动作中找到最低评价,修剪所有其他孩子,并指定第4级分数(来自最高的第5级)级别节点)到第3级.除了使用最低儿童分数(b / c这是AI移动而不是对手移动)之外,您的操作与步骤6相同.

8)对于第2级执行与第6步相同的操作,在所有从现在开始的第3次移动中找到最高评价,并将第2级节点分配给那些最高评价.

9)对第1级执行与步骤7相同的操作,在所有从现在开始的第2次移动中找到最低评价,并为第1级节点分配那些最低评价.

10)查看所有第一级节点,您的AI应该播放具有最高分数的节点.

显然,你会将深度不是硬编码为5,而是一个参数,你将使用递归(如在Wiki中)来实现这一点.要选择深度,请查看运行所需的时间,并将n设置为最高深度,这仍然允许快速的AI响应.一旦你在这里构建了基础知识,你可以在以后添加修剪策略,通过不评估树的整个分支来实现更大的深度,这显然不是正确的移动,但这是我为你布置的完整的,基本的negamax.

祝你好运,它应该是一个有趣的编程！