搜索与算法

xhz

搜索算法
考虑电脑游戏也采用与上述相同的策略。 请注意，搜索算法是计算电脑游戏策略的算法。

怎么运行的
搜索算法的目标是找到最优的一组移动，以便他们可以到达最终目的地并获胜。 这些算法使用胜出的一组条件，每场比赛都有所不同，以找到最佳的移动方式。
将电脑游戏形象化为树。 我们都知道树有节点。 从根开始，可以进入最终的获胜节点，但是具有最佳的移动路径。 这是搜索算法的工作。 这种树中的每个节点代表未来的状态。 搜索算法搜索这棵树，在游戏的每个步骤或节点做出决定。

组合搜索
使用搜索算法的主要缺点是它们本质上是穷尽的，这就是为什么他们探索整个搜索空间以找到导致资源浪费的解决方案。如果这些算法需要搜索整个搜索空间以找到最终解决方案，那将更加麻烦。
要消除这样的问题，可以使用组合搜索，它使用启发式来探索搜索空间，并通过消除可能的错误动作来减小其大小。 因此，这样的算法可以节省资源。 这里讨论了一些使用启发式搜索空间并节省资源的算法 -

Minimax算法
这是组合搜索使用启发式策略加快搜索策略的策略。 Minimax策略的概念可以通过两个玩家游戏的例子来理解，其中每个玩家都试图预测对手的下一步行动并尝试最小化该功能。 而且，为了获胜，玩家总是会根据当前的情况尝试最大化自己的功能。
启发式在像Minimax这样的策略中扮演着重要的角色。 树的每个节点都会有一个与之相关的启发式函数。 基于这种启发式方法，它将决定向最有利于他们的节点迈进。

Alpha-Beta修剪
Minimax算法的一个主要问题是它可以探索那些无关的树的部分，导致资源的浪费。 因此，必须有一个策略来决定树的哪一部分是相关的，哪一个是无关紧要的，并且将不相关的部分留给未开发的部分。 Alpha-Beta修剪就是这样一种策略。
Alpha-Beta修剪算法的主要目标是避免搜索树中没有任何解决方案的那些部分。 Alpha-Beta修剪的主要概念是使用名为Alpha的两个边界(最大下界)和Beta，即最小上界。 这两个参数是限制可能解决方案集合的值。 它将当前节点的值与alpha和beta参数的值进行比较，以便它可以移动到具有解决方案的树部分并丢弃其余部分。

Negamax算法
这个算法与Minimax算法没有区别，但它具有更优雅的实现。 使用Minimax算法的主要缺点是需要定义两个不同的启发式函数。 这些启发式之间的联系是，对于一个玩家来说游戏的状态越好，对另一个玩家来说就越糟糕。 在Negamax算法中，两个启发函数的相同工作是在单个启发式函数的帮助下完成的。

//更多请阅读：https://www.yiibai.com/ai_with_python/ai_with_python_gaming.html