纯代码告诉你：我的原弈非常（Yanj Future）是怎么下棋的

// 为了便于计算, 将局面固定为红下黑上, 评价以红方为基准
#define INFINITY		10000

int Max(int depth)
{
	if (depth <= 0)
	{
		// 到达指定的搜索深度, 返回局面的评价值
		// 局面评价与搜索无关, 不必绝对精确, 只需要保证返回的值能正确区分: 胜负平优劣
		return Position::Evaluate();
	}
	// 生成所有合法的着法
	int c = Position::GetLegalMoves();
	// 假定评价最低(黑胜)
	int best = -INFINITY;
	// 遍历每个着法
	for (int i = 0; i < c; i++)
	{
		// 执行着法
		Position::MakeMove(i);
		// 下一步为黑方行棋, 必定选择最评价最低的着法
		int val = Min(depth - 1);
		// 撤销着法
		Position::UndoMove();
		// 检查评价
		if (val > best)
		{
			// 保存当前最高的评价
			best = val;
		}
	}
	// 向上返回: 如果执行到当前局面, 对红方最有利的就是这样
	return best;
}

int Min(int depth)
{
	if (depth <= 0)
	{
		// 同 ::Max()
		return Position::Evaluate();
	}
	// 生成所有合法的着法
	int c = Position::GetLegalMoves();
	// 假定评价最高(红胜)
	int worst = INFINITY;
	// 遍历每个着法
	for (int i = 0; i < c; i++)
	{
		// 执行着法
		Position::MakeMove(i);
		// 下一步为红方行棋, 必定选择最评价最高的着法
		int val = Max(depth - 1);
		// 撤销着法
		Position::UndoMove();
		// 检查评价
		if (val < worst)
		{
			// 保存当前最低的评价
			worst = val;
		}
	}
	// 向上返回: 如果执行到当前局面, 对红方最不利的就是这样
	return worst;
}

int MinMax(int depth)
{
	if (Position::Force == ForceEnum::White)
	{
		// 红方要寻找的是评价最高的着法: 即希望红胜
		return Max(depth);
	}
	else
	{
		// 黑方要寻找的是评价最低的着法: 即希望红负
		return Min(depth);
	}
}

// 三个函数逻辑上可以合并为一个函数: 即所谓的降低算法复杂度(其实在程序员的思维中复杂度是提升的, 需要数学能力或逻辑能力)

int NegMax(int depth)
{
	if (depth <= 0)
	{
		// 到达指定的搜索深度, 同 ::Max()
		return Position::Evaluate();
	}
	// 生成所有合法的着法
	int c = Position::GetLegalMoves();
	// 假定评价最低(黑胜)
	int best = -INFINITY;
	// 遍历每个着法
	for (int i = 0; i < c; i++)
	{
		// 执行着法
		Position::MakeMove(i);
		// 下一步为黑方行棋, 必定选择最评价最低的着法(直接对评价取反)
		// 对于黑方也是一样, 假设二层且每层二种着法, 依次行棋及对应的评价:
		// 红 黑 评价
		//  1  1  100
		//  1  2   50
		//  2  1  -99
		//  2  2    1
		// 使用 MinMax() 时:
		// 红方使用 Max() 搜索 1 时, 黑方使用 Min() 搜索, 选择 1 着法, 调用 Max() 评价为 100, 选择 2 着法, 调用 Max() 评价为 50, Min() 选择 50 即 2 着法, 路径为 1 2
		// 红方使用 Max() 搜索 2 时, 黑方使用 Min() 搜索, 选择 1 着法, 调用 Max() 评价为 -99, 选择 2 着法, 调用 Max() 评价为 1, Min() 选择 -99 即 1 着法, 路径为 2 1
		// 红方使用 Max() 搜索完成, 选择 50 > -99 即 1 着法, 路为 1 2
		// 使用 NegMax() 时:
		// 红方使用 NegMax() 搜索 1 时, 黑方使用 NegMax() 搜索, 选择 1 着法, 调用 NegMax() 评价为 100, 选择 2 着法, 调用 NegMax() 评价为 50, 黑方 NegMax() 取反选择 -50 > -100 即 2 着法, 路径为 1 2
		// 红方使用 NegMax() 搜索 2 时, 黑方使用 NegMax() 搜索, 选择 1 着法, 调用 NegMax() 评价为 -99, 选择 2 着法, 调用 NegMax() 评价为 1, Min() 选择 99 > -1 即 1 着法, 路径为 2 1
		// 红方使用 NegMax() 搜索完成, 选择 -(-50)=50 > -(99)=-99 即 1 着法, 路为 1 2
		// 两种方式完全等价
		int val = -NegMax(depth - 1);
		// 撤销着法
		Position::UndoMove();
		// 检查评价
		if (val > best)
		{
			// 保存当前最高的评价
			best = val;
		}
	}
	// 向上返回: 如果执行到当前局面, 最好的评价就是这样(对于任何一方)
	return best;
}

// 极大极小值搜索一种严密的搜索, 它会尝试给定深度内的所有可能性
// 如果评价函数精确, 则是无敌的, 实际上评价函数不可能精确, 如果评价函数精确, 搜索就不必要了, 直接对根局面每一种着法评价即可
// 因此, 评价函数只需要保证返回的值能正确区分: 胜负平优劣
// 然而, 评价函数也影响程序的效果, 如果评价函数过于粗糙, 虽然代码少, 执行快, 但可能程序搜索 10 层, 还不如评价程序好的搜索 6 层
// 一种有效的方法是使用人工神经网络(深度学习)作为评价函数, 人工神经网络是无敌的黑箱, 可以拟合一切规律, 而不管这个规律多么复杂
// 当然, 神经网络的能力与构成它的神经元数量有关, 因此计算量又是制约神经网络的重要一个原因
// 但是: 对于极大极小值搜索, 有一个致命的弱点, 那就是局面数量, 中国象棋每个局面做多有个 119 种着法(确切着法), 以 100 种算
// 搜索 10 层的局面数量是: 100 的 10 次方, 即 10 个 100 相乘, 那就是 100000000000000000000, 即 1 后面 20 个零, 一万亿亿种局面
// 是局面, 不是运算次数, 一种局面的评价按一万次运算(一万条指令, 3000条左右的 C++ 语句, 1000 行代码)来算, 那就是: 一亿亿亿次运算
// 中国曾为世界上最强(2017)的天河二峰值也只有: 5亿亿次每秒, 需要 231.5 天, 每天 24 小时不停的算, 个人计算机要算到天荒地老, 海枯石烂了...

// 那么有没有办法减少这个计算量呢, 有! 那就是有利无害的, 只减少运算量, 不带来任何负面影响的 alpha-beta 算法:
// 接着上例, 在 NegMax() 中, 红方搜索 2 然后黑方 搜索 1 时, 即路径为 2 1 时, 黑方得到的评价为 -99
// 然而此时, 红方之前得到的最高评价为 50, 即黑方在怎么为难, 选择对红方最低的着法, 评价也有 50
// 这时候, 整个红方的 2 着法其实可以不用继续搜索了, 原因如下:
// 1. 如果走这一步, 那么黑方至少会走出 -99 这一步, 甚至后面可能还有更低的, 但至少是 -99, 即黑方总是选择对红方最不利的那种着法
// 2. 先前得到的评价为 50, 这是黑方能给出的最低的对抗, 甚至如果黑方失误, 还会选择 100 那一步
// 这里的 50 就是所谓的 beta 值, 即下界(最低评价边界), 任何大于此值的着法都不用再考虑, 即假定对方一样是顶级高手, 不会傻到走这一步棋, 因此这一局面直接丢弃, 不必迟疑
// 用代码实现如下:

int AlphaBeta(int depth, int alpha, int beta)
{
	if (depth <= 0)
	{
		// 到达指定的搜索深度, 同 ::Max()
		return Position::Evaluate();
	}
	// 生成所有合法的着法
	int c = Position::GetLegalMoves();
	// 假定评价最低(黑胜)
	int best = -INFINITY;
	// 遍历每个着法
	for (int i = 0; i < c; i++)
	{
		// 执行着法
		Position::MakeMove(i);
		// 获取对方评价, 同 ::Max()
		// 关键:
		// 对方最好的结果就是当前对于对方最糟糕的结果取反
		// 自己(对方的对方)最糟糕的结果就是当前对于自己最好的结果取反
		// 取反的原理同 ::NegMax()
		int val = -AlphaBeta(depth - 1, -beta, -alpha);
		// 撤销着法
		Position::UndoMove();
		// 检查评价
		if (val >= beta)
		{
			// 找到一个比现在对于对方来说最不利的结果还要糟糕的评价
			// 不用想了, 对方不会让你得逞的(最多是现在对于对方来说最糟糕的这个了)
			return beta;
		}
		if (val > alpha)
		{
			// 找到了一个比现在更好的评价, 这个评价是这种着法下去
			// 对方能给我的最低的评价, 但仍然比之前的高, 我当前最好的选择就是它
			alpha = val;
		}
	}
	// 向上返回: 如果执行到当前局面, 最好的评价就是这样(对于任何一方)
	return alpha;
}

// 例子, 加入搜索出对于对方最糟糕的着法评价是 -INFINITY, 任何比这个评价更高的都不管了, 其实就是都不用管了
// 如果第一次搜索出来, 就是最低的 beta 和 最高的 alpha 值, 那么相当于整个博弈树分枝会全部截断, 那就爽歪歪了, 瞬间飙到几十层
// 而如果每次搜索出来都是最高的 beta 和最低的 alpha 值, 那就呜呼哀哉了, 整个博弈树跟 ::NegMax() 一模一样, 天河二, ...
// 意思就是:
// 这种 alpha-beta 算法严重依赖于搜索顺序, 你最好能一眼猜中最好的着法, 这就要别的帮助啦, 代码也要复杂得多

// 实际上, 原弈非常(Yanj Future)使用多种方式来选择着法顺序:
// 1. 历史启发
// 2. 杀手启发
// 3. 空着
// 4. 哈希表
// 5. 棋力
// 6. 人工神经网络
// 人总是喜欢自己擅长的事情, 原弈非常的特点就是满满的人工神经网络, 又是黑箱模型
// 不过这其实是个笑话, 小时候下棋都是别人教的(我老爸下棋厉害, 但是他反对我玩象棋), 小伙伴教会我一种棋, 一个下午之后他就再也玩不过我了
// 自从调试玩原弈非常, 让它学会下棋之后, 至今再也没赢过它, ...

// 总体上表现出来的是, 电脑下棋不会走险棋, 但是也不会被险棋得逞, 即跟程序员一个德行: 严密的思维
// 实际上, 受限于评价函数的水平, 以及搜索深度, 电脑的棋力在当今还是有限的
// 什么? AlphaGo? AlphaZero 我只能说呵呵, 几十亿元成本, 每天 3000 美元的电费, 那也叫电脑?!
// 天河二啊, 我只能说 ... 每天吞掉人民币约 50万, 你的电脑多少钱啊?!
// 当然了, 像 AlphaZero 这样的人工神经网络, 训练结束后的产品, 只需几万人民币的电脑, 就可以运行的, 只是产品背后的投入, ...
// 喂, 物业吗? 这个月的电费, 能不能五分钱一度??? 多买多送嘛, 嘿嘿