1

我想知道如何处理在 c 中问题的许多不同“级别”中使用的过程的问题，最好以“惯用”方式。我知道我解释得不够好，所以让我举个例子：

考虑制作一个游戏求解器的一般问题，它应该打印最好的下一步动作。我认为它应该在一个for循环中检查所有可能的动作，看看它是否是一个获胜的动作（在这一轮中）如果是，则返回移动，否则检查对手可以针对您的移动（for循环）进行的所有可能移动并调用该函数以再次找到最佳移动。

但是，我发现这种方法有一些限制，例如性能（程序将花费时间运行调用函数所需的样板代码等）和有限的灵活性，因为函数必须找到一种方法来与调用者沟通如何找到了一个很好的举动。也就是说，如果它可以做到的话。

bestmove()
{
  for (;i<maxmove;i++)
   {
    if(checkifwinning(moves[i])) return;
    for (;n<maxopponentmove;n++)
     {
      bestmove();
     }
   }

我已经和haskell 搞混了一段时间，所以我担心我的想法是寻求递归解决方案。我希望你能告诉我一种以'c native'方式编写这个函数的方法。

4

3 回答 3

3

C 语言允许递归函数。但是，它没有尾递归调用的概念（但在某些情况下，最近的 GCC 编译器能够将一些尾递归调用优化为纯迭代的机器代码）。

在编写递归函数时，您应该避免太深的递归和太大的本地调用帧（所以使用堆内存）。

于 2012-04-25T11:16:25.993 回答
0

我认为你真正需要的是一个类似分支定界的算法：保留一个“开放”移动列表（即尚未考虑）和一个“封闭”移动列表（即，已经考虑）。在 C 中，最好用两个队列（打开和关闭）来实现。然后你会有一个如下的算法：

while (open is not empty)
{
   pop gameState from open
   if (gameState in closed)
      continue;
   push gameState to closed
   for (eachMove)
   {
       computeNewState();
       addStateToOpen();
   }
}

与递归方法相比，这样做有几个优点：

  • 你确定每个游戏状态只考虑一次
  • 你不会“压倒”堆栈
于 2012-04-25T11:23:29.433 回答
0

您正在谈论搜索游戏树以找到最佳移动；你可以使用像minimax这样的标准算法。您的方法似乎是对树的深度优先搜索，该树在找到的第一个获胜动作处终止；请注意，这不会找到通往获胜动作的最短路径，也不会防止对手获胜。

有一些方法可以加快游戏树的搜索速度，例如alpha-beta pruning。这样的标准算法是要走的路——比担心在 C 中调用函数等的开销要好得多。C 函数调用并不昂贵。在编写 C 代码时要小心这种“优化”——无论如何，优化器可能更擅长这些事情。至少，首先以最直接的方式编写一个版本，这样你就有了可以作为基准的东西。你的工作是找到一个好的算法。

于 2012-04-25T12:48:25.113 回答