chess_engine_using_python
1.0.0
该存储库包含使用Minimax 、 Alpha-Beta 剪枝和静止搜索算法的国际象棋引擎实现。 Docker 容器内的 Jupyter Notebook 用于编码。所有 Jupyter Notebook 也都以 docker 镜像的形式提供。
查看项目论文以查看详细分析。
docker pull codewithnk/chess-engine-using-python:latestdocker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest国际象棋的核心是以minmax下棋。 Minmax通常将黑棋与MAX联系起来，将白棋与MIN联系起来，并且总是从白棋的角度进行评估。
Minmax算法是博弈论中的一种对抗搜索算法。它利用博弈树并包括两个玩家 MIN 和 MAX。两名玩家都试图抵消对方的行动。 Max 尝试最大化结果，而 MIN 尝试最小化结果。假设双方都处于最佳状态，两名玩家交替进行游戏。最佳游戏意味着两个玩家都按照规则进行游戏，即 MIN 使结果最小化，MAX 使结果最大化。
minmax 算法利用深度优先搜索方法来查找结果。此外，它还利用回溯和递归。算法将遍历直到终端节点，然后在比较所有子值的同时回溯。它将根据轮到谁来选择最小值或最大值。然后它将将该值传播回其父级。它使用静态评估函数来确定每个叶节点的值。它利用了零和博弈的优势。
使用 Minmax 的国际象棋引擎
Minmax 在博弈树上使用深度优先搜索（DFS），因此 minmax 算法的时间复杂度为O(b**m) ，其中 b 是博弈树的分支因子，m 是树的最大深度。
minmax算法的空间复杂度也与DFS类似，为O(bm) ，其中b是博弈树的分支因子，m是树的最大深度。
最小最大算法已完成。如果存在的话，它肯定会在有限搜索树中找到解决方案。
如果两个对手都处于最佳状态，则最小最大算法是最佳的。
最小最大算法可以通过修剪少量分支来优化。修剪的枝条是不会影响结果的枝条。它将提高时间复杂度。这个版本的 minmax 被称为带有 alpha-beta 剪枝的 minmax。它也称为 alpha-beta 算法。
在Alpha-Beta剪枝中，有两个值：Alpha和Beta。以下是关于 alpha 和 beta 需要考虑的几点：
回溯时，仅将节点值传递给父级，而不是 alpha 和 beta 值。
α-β剪枝的条件：
α >= β
alpha-beta 算法的有效性很大程度上取决于遍历的顺序。它在时间和空间复杂性中起着至关重要的作用。
在某些情况下，博弈树中不会删除任何节点或子树。在这种情况下，最佳移动发生在博弈树的右子树中。这将导致时间复杂度增加。
在这种情况下，节点和子树的最大数量被修剪。最佳移动发生在左子树中。它将降低时间和空间复杂度。
使用 Alpha-Beta 剪枝的国际象棋引擎
Alpha Beta 算法，也在博弈树上使用深度优先搜索（DFS）。
Alpha-Beta 算法已完成。如果存在的话，它肯定会在有限搜索树中找到解决方案。
如果两个对手都处于最佳状态，则 Alpha-Beta 算法是最佳的。
静止搜索是对最小-最大 α-β 剪枝的修改。静就是安静的意思。此搜索仅评估安静的动作。换句话说，在一定深度之后，它只使用捕获动作来计算下一步的动作。静止搜索可以避免地平线效应。
当我们只搜索到一定深度时，就会出现地平线效应，但如果我们再深入一层，那么移动得分可能会更少。静止搜索仅使用捕获移动来防止这种情况。静止搜索还减少了不同级别的分支因子，从而产生快速算法。
静止搜索算法，也在博弈树上使用深度优先搜索（DFS）。
静止搜索算法已完成。如果存在的话，它肯定会在有限搜索树中找到解决方案。
如果两个对手都处于最佳状态，则静止搜索算法是最佳的。
