为回合制棋盘游戏编写AI

Question

我正在编写一个棋盘游戏(8x8),我需要开发一个AI.

我在电路板游戏中看过很多关于AI的文章,有或没有字母修剪的minmax,但我真的不知道如何实现这个,我不知道从哪里开始......

关于我的游戏,这是一个回合制游戏,每个玩家都有棋子,他们必须选择一个并选择移动这个棋子(最多1或2个单元格)或克隆棋子(最多1个单元格).

目前,我有一个非常愚蠢的人工智能选择一个随机的片然后选择随机移动玩...

请问关于如何实现此功能的一些线索？

最好的祝福

Answer 1

(编辑:2013年8月8日) - 我写了一些示例代码:Ultimate Tic-Tac-Toe,我有一个最小/最大游戏搜索的通用实现.代码是用C++的愚蠢变体编写的,称为prepp.

您最好的资源将是人工智能的大学课程.经典教科书是Russel和Norvig的"人工智能:现代方法"

我将尝试给出关键概念的细分.

游戏状态 - 这是一组可用于确定的变量:

• 当前状态的估计"价值"
• 游戏结束了吗？

值 - 特定状态的"值"是当前玩家评估的状态的函数,我们称之为f(x).该函数的另一个名称是"启发式"函数.在给定板状态x的情况下,它确定当前玩家可以实现的最佳可能值.你如何建模x取决于你,但x应该涵盖游戏自然流程中使用的所有东西.因此,在您的情况下,x可能是映射到电路板上各个部分的8x8值矩阵.并且,f将是一个函数,为Red播放器(或某些此类播放器)提供该电路板配置的"值".

在2人回合制游戏中考虑的一种可能的简化是将"当前玩家"编码为状态的一部分.这会将状态添加到启发式函数的输入中.所以,我们有f(x,player)而不是f(x ).但是,通过将玩家滚动到x可以简化这一点.无论哪种方式,f将始终返回同一玩家的"价值",但根据轮到谁接下来.

通过(简化)示例来澄清,如果白色可以杀死黑人的女王,国际象棋中的f几乎总是会返回非常高的分数.但是如果黑色有可能在下一步中杀死白人女王,那么f应该返回一个非常低的数字.

请注意,到目前为止还没有提到minmax的树搜索部分. f总是根据当前状态定义.因此,当我说"黑色将有可能......"时,我的意思是你的启发式函数可以确定,例如,给定x,在a之间存在视线(对角线,水平或垂直).黑人主教,或车,白人的女王.国际象棋的启发式方法应该足够复杂,以便知道这就产生了威胁,因此在计算f的总值时应该对其进行相应的评分.

在我到达minmax之前,请注意A*是用于搜索可能的x值的空间的优化.但是,在完全理解并实施minmax之前,您不必担心优化.

因此,minmax算法是组织AI决策过程的一种方式.为了实现minmax,您需要做的事情:

• 从现有游戏状态x生成有效的游戏状态.
• 在达到特定深度后停止循环或递归.
• 记住每个级别递归的"值",将其传递回调用者.

基本流程从理解开始,轮到谁了？正如我之前提到的,f将始终返回高值以指示玩家1的成功,而低值则表示玩家2的成功.在每个更深层次的递归中,玩家将允许您了解是否选择最小值或最大值.通过递归发现的潜在价值.

让我说另一种方式.实际评估f(x)有两个原因.

1. 你想知道游戏是否在状态x结束.
2. 你已经达到了最深层次的递归,你想评估如果游戏进展到这么远的分数.

所以,你的代码会做这样的事情:

function minmax(x,player)返回值

• 我当前的状态是x,下一个要移动的玩家是已知的.我知道这是因为
  • 功能选择 - 移动告诉我.(见下文)
  • 我被自己递归地叫了起来.(见下文)
• 游戏结束了吗？问f(x).如果它返回正无穷大,则白色赢了.如果它返回负无穷大,则黑色赢了.如果你的游戏有僵局选项,或者有最终得分(可能是较大游戏的一部分),那么你只需要用一种方法来表示获胜+得分作为f的返回值.或者,如果你想将它分开,只需创建一个新函数g(x)即可.如果游戏结束,请将该值返回给您的来电者.如果游戏尚未结束,请继续.
• 从x我将枚举所有可能的x'.在8x8游戏中,可能存在来自任何单个游戏状态的几个,几十个或几百个可能的有效移动.这取决于你的游戏规则.
• 如果达到了最深层次的期望递归,
  • 对于每个x',调用f(x',播放器).对于每个调用,我们将其返回值与我们传入的特定x'相关联.
• 其他
  • 对于每个x',递归调用minmax(x',其他玩家).(注意,此时其他玩家与玩家相反.)对于每次调用,我们将其返回值与我们传入的特定x'相关联.

此时,所有可能的下一步移动应该具有与它们相关联的"值".

• 如果玩家是玩家1,则从与所有x'相关联的所有值中选择最大值,并返回该值.这是玩家1能够从这个游戏状态中做到的最好的.
• 如果玩家是玩家2,请从与所有x'相关联的所有值中选择最小值,并返回该值.这是玩家2在这个游戏状态下能够做到的最好的.

结束函数minmax

function choose-move(x,player) return*next_state*

• 我目前的状态是x,我们试图弄清楚玩家的下一步应该是什么.
• 检查游戏是否结束,如上所述.
• 从x我将枚举所有可能的x'.(您应该能够在minmax中重复使用您必须执行此操作的任何代码.
  • 对于每个x',调用minmax(x',播放器).对于每个调用,我们将其返回值与我们传入的特定x'相关联.
• 如果玩家是玩家1,则从与所有x'相关联的所有值中选择最大值,并返回该值.这是玩家1能够从这个游戏状态中做到的最好的.
• 如果玩家是玩家2,请从与所有x'相关联的所有值中选择最小值,并返回该值.这是玩家2在这个游戏状态下能够做到的最好的.

结束功能选择 - 移动

你的驱动程序代码只需要调用choose-move,它应该返回下一个游戏板.显然,对于不同的表示,您还可以将返回值编码为"移动"而不是状态.

希望这可以帮助.对不起啰嗦的解释,我刚喝了一些咖啡.