最快连接4赢检查方法

2024-03-28 18:09:06 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试按照tic-tac-toe的alpha-beta pruning方法制作一个ai。我需要让检查一个胜利尽可能快,因为人工智能将通过许多不同的可能的游戏状态。现在我想到了两种方法,都不是很有效。在

  1. 创建一个大元组,在连续获胜的条件下对每4个可能的得分进行循环。在
  2. 使用for循环,检查“水平”、“垂直”、“diag facing left”和“diag facing right”。这似乎要慢得多#1。在

有人会建议你怎么做?在


Tags: 方法alpha游戏状态tic条件人工智能ai
1条回答
网友
1楼 · 发布于 2024-03-28 18:09:06

从你的问题来看,你的方法将如何实施有点不清楚。但是从alpha-beta剪枝来看,似乎你想看很多不同的游戏状态,并且在递归中为每个状态确定一个“分数”。在

一个非常重要的观察是,一旦发现一个4连一行的递归就结束了。这意味着在递归步骤开始时,游戏板没有任何连续4个实例。在

使用这个,我们可以直观地看到,在所述递归步骤中放置的新块必须是递归步骤期间创建的任何4行实例的一部分。这将极大地减少搜索空间,从总共69个(21个垂直、24个水平、12+12个对角线)4个连续位置减少到最多13个(3个垂直、4个水平、3+3个对角线)。在

这应该是第二种方法的基准。对于一个简单的实现,它最多需要52(13*4)个检查,对于一个更快的算法,它需要25个(6+7+6+6)检查。在

现在很难击败25个布尔检查,我想说,但是我猜您的#1方法需要一些额外的内存使用来减少每个递归步骤的计算量。最简单的方法是存储8个整数(对于这个应用来说,单字节是很好的),它们表示在8个方向上可以找到的相同色卡的最长链。在

使用这个方法,一个win的检查可以减少到8个布尔检查和4个加法。只需在新放置的芯片的对侧获得链的长度,检查它们是否与芯片的颜色相同,如果是,则添加它们的长度并加1(对于新放置的芯片)。在

根据这个计算,你的方法似乎是最有效的。但是,它维护数据结构的开销要大得多,并且使用更多的内存,除非可以通过引用传递,否则应该避免这种情况。另外(假设布尔检查和加法在速度上是相似的),即使忽略开销,更困难的方法也只能以2倍的优势获胜。在

我做了一些简单化的解释,有些解释可能不太清楚,但是如果你还有其他问题要问。在

相关问题 更多 >