我需要实现一个智能代理来玩鲍鱼游戏,对于这种游戏来说,最好的方法是使用alpha beta修剪的min-max策略 .
我已经实现了一个使用min-max修剪的天真搜索算法,
my problem is...
如何生成执行搜索的树的节点?
我不知道正确的方法,以及如何为每个节点分配权重 .
用于生成树节点:您需要实现一个方法,该方法返回给定当前板位置和轮到它的玩家的所有可能合法移动的集合 . 所有这些移动将成为表示当前板位置的节点的子节点 . 重复直到内存耗尽以生成游戏树;)或者更确切地说,直到达到合理的树深度 .
对于alpha-beta搜索,您还需要一个评估函数,用于计算每个电路板位置/节点的权重 . 您可以自己做一些研究或考虑这样的功能,也许考虑一下仍在板上的石头数量 . 然而,糟糕的评估功能会严重影响您的结果,因此请注意并进行大量测试 .
如果您在提出合理的评估功能时遇到问题,我建议您先了解一下蒙特卡罗技术,例如 UCT .
http://en.wikipedia.org/wiki/Monte_Carlo_tree_search
这些使用概率方法解决了这个问题,并且比alpha-beta有一些很好的优势 . 此外,它们不需要评估功能,因此您可以跳过此步骤 .
祝好运!
1 回答
用于生成树节点:您需要实现一个方法,该方法返回给定当前板位置和轮到它的玩家的所有可能合法移动的集合 . 所有这些移动将成为表示当前板位置的节点的子节点 . 重复直到内存耗尽以生成游戏树;)或者更确切地说,直到达到合理的树深度 .
对于alpha-beta搜索,您还需要一个评估函数,用于计算每个电路板位置/节点的权重 . 您可以自己做一些研究或考虑这样的功能,也许考虑一下仍在板上的石头数量 . 然而,糟糕的评估功能会严重影响您的结果,因此请注意并进行大量测试 .
如果您在提出合理的评估功能时遇到问题,我建议您先了解一下蒙特卡罗技术,例如 UCT .
http://en.wikipedia.org/wiki/Monte_Carlo_tree_search
这些使用概率方法解决了这个问题,并且比alpha-beta有一些很好的优势 . 此外,它们不需要评估功能,因此您可以跳过此步骤 .
祝好运!