搜索算法 - 版本历史

2024年10月2日 (三) 07:48 New

2024-10-02T07:48:04Z

@@ 第181行： / 第181行： @@
 基于空步的分数≤最优走法的分数这个假设，如果返回的评估≤beta-1，说明后续该节点的alpha值有可能达不到beta，不进行剪枝；如果返回的评估≥beta，说明最优走法的分数也一定≥beta，也就是说后续alpha在更新的时候也会≥beta，可以直接进行剪枝。
-然而一些局面并不满足之前我们提到过的假设，如国际象棋的迫移局面（Zguzwang），若使用空步裁剪，则会使引擎判断错误，于是我们需要使用“isNullMoveAllowed”函数判断是否满足空步裁剪的条件，尽量规避这种现象。
+然而一些局面并不满足之前我们提到过的假设，如国际象棋的迫移局面（Zguzwang），若使用空步裁剪，则会使引擎判断错误，于是我们可以设计一个“isNullMoveAllowed”函数判断是否满足空步裁剪的条件，尽量规避这种现象。
 伪代码如下：
@@ 第258行： / 第258行： @@
+     }
      return maxEval;
+}
 </syntaxhighlight>

New：/* PVS（主要变例搜索） */

2024-10-02T07:30:36Z

PVS（主要变例搜索）

←上一版本		2024年10月2日 (三) 15:30的版本
第219行：		第219行：

	== PVS（主要变例搜索） ==		== PVS（主要变例搜索） ==
	PVS是对Alpha-Beta剪枝的增强，可以提高Alpha-Beta剪枝的效率。简单来说，PVS先对第一个子节点进行[alpha, beta]的全窗口搜索，再对剩余子节点使用[alpha, alpha+1]的零窗口搜索。零窗口搜索结束后，如果该节点搜索返回的评估在(alpha, beta)~~之间，说明该节点有希望，于是继续进行一次全窗口搜索。~~		PVS是对Alpha-Beta剪枝的增强，可以提高Alpha-Beta剪枝的效率。简单来说，PVS先对第一个子节点进行[alpha, beta]的全窗口搜索，再对剩余子节点使用[alpha, alpha+1]的零窗口搜索。零窗口搜索结束后，如果该节点搜索返回的评估在(alpha, beta)之间，说明该节点有希望，于是继续进行一次全窗口搜索。如果返回的评估超出了(alpha, beta)，说明这个节点必然会被剪枝。

	伪代码如下：		伪代码如下：
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">

2024年10月2日 (三) 07:28 New

2024-10-02T07:28:22Z

←上一版本		2024年10月2日 (三) 15:28的版本
第219行：		第219行：

	== PVS（主要变例搜索） ==		== PVS（主要变例搜索） ==
	PVS是对Alpha-~~Beta剪枝的增强，可以显著提高Alpha~~-Beta剪枝的效率。简单来说，PVS先对第一个子节点进行[alpha, beta]的全窗口搜索，再对剩余子节点使用[alpha, alpha+1]的零窗口搜索。零窗口搜索结束后，如果该节点搜索返回的评估在(alpha, beta)之间，说明该节点有希望，于是继续进行一次全窗口搜索。		PVS是对Alpha-Beta剪枝的增强，可以提高Alpha-Beta剪枝的效率。简单来说，PVS先对第一个子节点进行[alpha, beta]的全窗口搜索，再对剩余子节点使用[alpha, alpha+1]的零窗口搜索。零窗口搜索结束后，如果该节点搜索返回的评估在(alpha, beta)之间，说明该节点有希望，于是继续进行一次全窗口搜索。
			伪代码如下：
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	int alphaBeta(int depth, int alpha, int beta) {		int alphaBeta(int depth, int alpha, int beta) {

2024年10月2日 (三) 07:13 New

2024-10-02T07:13:06Z

@@ 第215行： / 第215行： @@
+     }
      return value;
+}
 </syntaxhighlight>

New：/* 空步裁剪（Null Move Pruning） */

2024-03-27T16:01:55Z

空步裁剪（Null Move Pruning）

←上一版本		2024年3月28日 (四) 00:01的版本
第175行：		第175行：
	我们可以利用这一点编写一个剪枝策略——空步裁剪。空步裁剪是一种冒险策略，就是基于上面假设进行的，把比“空步”分数低的招法剪掉。		我们可以利用这一点编写一个剪枝策略——空步裁剪。空步裁剪是一种冒险策略，就是基于上面假设进行的，把比“空步”分数低的招法剪掉。

	为了加快搜索，我们可以对“空步”搜索的层数额外减少R（一般是2-~~3）层。由于我们只关心“空步”的分数和beta相比是大还是小，应该用零窗口搜索（~~[beta - 1, beta]），使Alpha-Beta剪枝在搜索空步时发挥的作用最大。		为了加快搜索，我们可以对“空步”搜索的层数额外减少R（一般是2-3）层。由于我们只关心“空步”的分数和beta相比是大还是小，所以应该用零窗口搜索（[beta - 1, beta]），使Alpha-Beta剪枝在搜索空步时发挥的作用最大。

	由于走子方互换，传递给子节点的alpha值和beta值也要按照之前的方法进行转换，也就是-beta和-beta + 1。		由于走子方互换，传递给子节点的alpha值和beta值也要按照之前的方法进行转换，也就是-beta和-beta + 1。
第181行：		第181行：
	基于空步的分数≤最优走法的分数这个假设，如果返回的评估≤beta-1，说明后续该节点的alpha值有可能达不到beta，不进行剪枝；如果返回的评估≥beta，说明最优走法的分数也一定≥beta，也就是说后续alpha在更新的时候也会≥beta，可以直接进行剪枝。		基于空步的分数≤最优走法的分数这个假设，如果返回的评估≤beta-1，说明后续该节点的alpha值有可能达不到beta，不进行剪枝；如果返回的评估≥beta，说明最优走法的分数也一定≥beta，也就是说后续alpha在更新的时候也会≥beta，可以直接进行剪枝。

	然而一些局面并不满足之前我们提到过的假设，如国际象棋的迫移局面（Zguzwang），若使用空步裁剪，则会使引擎判断错误，于是我们需要使用“isNullMoveAllowed”函数判断是否满足空步裁剪的条件，努力规避这种现象。		然而一些局面并不满足之前我们提到过的假设，如国际象棋的迫移局面（Zguzwang），若使用空步裁剪，则会使引擎判断错误，于是我们需要使用“isNullMoveAllowed”函数判断是否满足空步裁剪的条件，尽量规避这种现象。

	伪代码如下：		伪代码如下：

New：/* 空步裁剪（Null Move Pruning） */

2024-02-23T11:59:28Z

空步裁剪（Null Move Pruning）

←上一版本		2024年2月23日 (五) 19:59的版本
第171行：		第171行：

	== 空步裁剪（Null Move Pruning）==		== 空步裁剪（Null Move Pruning）==
	~~解释待更新...~~		一般来说，一个局面我方什么都不走（或者说走了一个“空步”），而是把走子权让给对方，我方是吃亏的。即最优走法的分数一般来说不会比走“空步”的分数低。

			我们可以利用这一点编写一个剪枝策略——空步裁剪。空步裁剪是一种冒险策略，就是基于上面假设进行的，把比“空步”分数低的招法剪掉。

			为了加快搜索，我们可以对“空步”搜索的层数额外减少R（一般是2-3）层。由于我们只关心“空步”的分数和beta相比是大还是小，应该用零窗口搜索（[beta - 1, beta]），使Alpha-Beta剪枝在搜索空步时发挥的作用最大。

			由于走子方互换，传递给子节点的alpha值和beta值也要按照之前的方法进行转换，也就是-beta和-beta + 1。

			基于空步的分数≤最优走法的分数这个假设，如果返回的评估≤beta-1，说明后续该节点的alpha值有可能达不到beta，不进行剪枝；如果返回的评估≥beta，说明最优走法的分数也一定≥beta，也就是说后续alpha在更新的时候也会≥beta，可以直接进行剪枝。

			然而一些局面并不满足之前我们提到过的假设，如国际象棋的迫移局面（Zguzwang），若使用空步裁剪，则会使引擎判断错误，于是我们需要使用“isNullMoveAllowed”函数判断是否满足空步裁剪的条件，努力规避这种现象。

	伪代码如下：		伪代码如下：

2024年2月23日 (五) 11:25 New

2024-02-23T11:25:07Z

←上一版本		2024年2月23日 (五) 19:25的版本
第169行：		第169行：

	其实这两者是等价的，正常情况下，alpha<beta，所以alpha≥beta的情况只能是分数更新，导致alpha变大，发生Beta剪枝，所以直接和val进行比较也是一样的。		其实这两者是等价的，正常情况下，alpha<beta，所以alpha≥beta的情况只能是分数更新，导致alpha变大，发生Beta剪枝，所以直接和val进行比较也是一样的。

			== 空步裁剪（Null Move Pruning）==
			解释待更新...

			伪代码如下：
			<syntaxhighlight lang="cpp">
			// R是空步裁剪搜索中额外减去的层数
			const int R = 3;

			int alphaBeta(int depth, int alpha, int beta) {
			if (depth == 0 \|\| isGameOver()) {
			return evaluate();
			}

			// Null Move Pruning
			if (depth >= R + 1 && isNullMoveAllowed()) {
			makeNullMove(); // 走一步“空步”
			int nullMoveEval = -alphaBeta(depth - R - 1, -beta, -beta + 1); // 用[beta - 1, beta]进行搜索
			undoNullMove(); // 恢复

			if (nullMoveEval >= beta) {
			return beta; // 如果beta的值还不如走“空步”的分数高，就直接剪掉
			}
			}

			int value = INT_MIN;
			for (Move move : getPossibleMoves()) { // 走法生成
			makeMove(move); // 走棋
			value = std::max(value, -alphaBeta(depth - 1, -beta, -alpha));
			undoMove(move); // 恢复
			alpha = std::max(alpha, value);
			if (alpha >= beta) {
			break; // Beta剪枝
			}
			}
			return value;
			}
			</syntaxhighlight>

2024年2月23日 (五) 11:11 New

2024-02-23T11:11:10Z

←上一版本		2024年2月23日 (五) 19:11的版本
第106行：		第106行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			== 继续简化，引入Negamax ==
			前面我们的分数一直是相对于红方视角的，需要将红方和黑方分类讨论，这显然使代码复杂化了。为了解决这个问题，我们需要引入Negamax。

			引入Negamax后，我们对双方可以使用同样的处理策略，省去了编写MIN方代码的必要性，但是评估函数需要改成相对于走子方的分数。

			如果当前走子方是红方，需要返回相对于红方的分数；如果当前走子方是黑方，需要返回相对于黑方的分数。

			由于我们把两种情况合并成了一种情况，判断红黑方的参数可以删去。

			在搜索子节点的时候，我们需要从MAX层切换到MIN层，或者从MIN层切换到MAX层，应该如何做呢？

			在这里，我们继续举一个例子来说明。假设当前节点从父节点传下来的alpha值为5，beta值为8，说明最优走法的分数一定在5和8之间，接下来我们把分数视角切换到对手，最优走法的分数一定在-8和-5之间，-8和-5就分别是传递给子节点的alpha值和beta值。

			所以，传给子节点的alpha和beta值应该是-beta和-alpha。

			下面是引入Negamax后的伪代码：

			<syntaxhighlight lang="cpp">
			int alphaBeta(int depth, int alpha, int beta) {
			if (depth == 0 \|\| isGameOver()) {
			return evaluate();
			}

			int maxEval = INT_MIN; // 初始化为负无穷，方便程序找出所有走法中分数的最大值
			for (Move move : getPossibleMoves()) { // 走法生成
			makeMove(move); // 走子
			int eval = -alphaBeta(depth - 1, -beta, -alpha); // 向下一层搜索，获得该走法对应的子节点的分数
			undoMove(move); // 恢复到走子前的局面
			maxEval = std::max(maxEval, eval);
			alpha = std::max(alpha, eval);
			if (alpha >= beta)
			break; // Beta剪枝
			}
			return maxEval;
			}
			</syntaxhighlight>

			有些资料上的代码可能是这样的：

			<syntaxhighlight lang="cpp">
			int alphaBeta(int depth, int alpha, int beta) {
			if (depth == 0 \|\| isGameOver()) {
			return evaluate();
			}

			for (Move move : getPossibleMoves()) {
			makeMove(move);
			int val = -alphaBeta(depth - 1, -beta, -alpha);
			undoMove(move);

			if (val >= beta) {
			return beta; // Beta剪枝
			}
			if (val > alpha) {
			alpha = val; // 更新Alpha的值
			}
			}
			return alpha;
			}
			</syntaxhighlight>

			其实这两者是等价的，正常情况下，alpha<beta，所以alpha≥beta的情况只能是分数更新，导致alpha变大，发生Beta剪枝，所以直接和val进行比较也是一样的。

New：/* Alpha-Beta剪枝的代码实现 */

2024-02-23T04:27:17Z

Alpha-Beta剪枝的代码实现

←上一版本		2024年2月23日 (五) 12:27的版本
第68行：		第68行：
	因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。若当前节点的分数超过了beta，必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳；若当前节点的分数等于beta，必然不会比其父节点之前搜过的某个子节点更优。我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。		因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。若当前节点的分数超过了beta，必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳；若当前节点的分数等于beta，必然不会比其父节点之前搜过的某个子节点更优。我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。

	~~判断当前节点的分数是否≥beta，可以等同于判断alpha≥beta，因为alpha就是按照子节点的分数进行更新的。~~		判断当前节点的分数是否≥beta，可以等同于判断alpha≥beta，因为alpha就是按照子节点的分数通过取最大值进行更新的。

	MIN层同理，这里不再赘述。		MIN层同理，这里不再赘述。

2024年2月23日 (五) 04:25 New

2024-02-23T04:25:30Z

←上一版本		2024年2月23日 (五) 12:25的版本
第58行：		第58行：

	== Alpha-Beta剪枝的代码实现 ==		== Alpha-Beta剪枝的代码实现 ==
	为了用代码实现Alpha-Beta剪枝，我们需要引入alpha和beta两个量，alpha是红方能保证至少获得的分数，beta是黑方能保证至多获得的分数（这里的分数都是从红方视角看的）。也就是说，最优走法的分数必然≥alpha而≤beta。		为了用代码实现Alpha-Beta剪枝，我们需要引入alpha和beta两个量，alpha是红方能保证至少获得的分数，beta是黑方能保证至多获得的分数（这里的分数都是从红方视角看的）。也就是说，最优走法的分数必然≥alpha而且≤beta。

	在最开始调用“alphaBeta”函数的时候，我们应该把alpha设为负无穷，把beta设为正无穷。		在最开始调用“alphaBeta”函数的时候，我们应该把alpha设为负无穷，把beta设为正无穷。
第64行：		第64行：
	当我们搜索一个节点的时候，我们需要接受从父节点传来的alpha和beta值，接着判断该节点处于MAX层还是MIN层。		当我们搜索一个节点的时候，我们需要接受从父节点传来的alpha和beta值，接着判断该节点处于MAX层还是MIN层。

	这里还是举一个例子方便读者理解，假设我们处于MAX层（即红方），父节点传递的alpha值是5，beta值是8。因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。当前节点的分数超过了beta（可以等同于判断alpha≥beta），必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳，我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。		这里还是举一个例子方便读者理解，假设我们处于MAX层（即红方），父节点传递的alpha值是5，beta值是8。

			因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。若当前节点的分数超过了beta，必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳；若当前节点的分数等于beta，必然不会比其父节点之前搜过的某个子节点更优。我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。

			判断当前节点的分数是否≥beta，可以等同于判断alpha≥beta，因为alpha就是按照子节点的分数进行更新的。

			MIN层同理，这里不再赘述。

	伪代码如下：		伪代码如下：

搜索算法 - 版本历史

2024年10月2日 (三) 07:48 New

New：​/* PVS（主要变例搜索） */

2024年10月2日 (三) 07:28 New

2024年10月2日 (三) 07:13 New

New：​/* 空步裁剪（Null Move Pruning） */

New：​/* 空步裁剪（Null Move Pruning） */

2024年2月23日 (五) 11:25 New

2024年2月23日 (五) 11:11 New

New：​/* Alpha-Beta剪枝的代码实现 */

2024年2月23日 (五) 04:25 New

New：/* PVS（主要变例搜索） */

New：/* 空步裁剪（Null Move Pruning） */

New：/* 空步裁剪（Null Move Pruning） */

New：/* Alpha-Beta剪枝的代码实现 */