博弈树解决一字棋问题
实验内容
用博弈树求解一字棋博弈问题，定义估 价函数，并站在某一方立场，给出当前最佳走步（α- β剪枝搜索）
实验原理
要想讲讲 ALPHA-BETA 剪枝算法，得先讲讲其他点别的。
博弈树
博弈树$（game\ tree）$是指组合博弈理论中用来表达一个博弈中各种后续可能性的树，一个完整的博弈树$（complete\ game\ tree）$会有一个起始节点，代表博弈中某一个情形，接着下一层的子节点是原来父节点博弈下一步的各种可能性，依照这规则扩展直到博弈结束。博弈树相同于扩展形式的博弈理论中的树。博弈树中形成的叶节点代表各种游戏结束的可能情形，例如井字游戏会有 $26,830$ 个叶节点。
一个井字游戏的博弈树示例
博弈树在人工智能的应用相当重要，若要查找某博弈中最佳的步法的一个方式，是利用极大极小算法在博弈树中搜索最佳解，例如在井字游戏中电脑可以很快速地找到最佳解并做出决策，但是对于象棋、围棋这一类大型的博弈游戏，列出完整博弈树可能使电脑计算能力难以应付，因此对这类游戏通常会采用部分的博弈树$（partial\ game\ tree）$来进行搜索，典型的部分博弈树通常是限制博弈树的层数，并剔除不佳的步法（例如自杀），一般而言搜索的层数越多，能走出较佳步法的机会也越高。
若是两人游戏，除了可以用博弈树表达之外，也可以用 $And–or tree$ 表示。
最小最大函数
伪代码如下：
int MinMax(int depth) {
if (SideToMove() == WHITE) { // 白方是“最大”者
return Max(depth);
} else { // 黑方是“最小”者
return Min(depth);
}
}
int Max(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Min(depth - 1);
UnmakeMove();
if (val > best) {
best = val;
}
}
return best;
}
int Min(int depth) {
int best = INFINITY; // 注意这里不同于“最大”算法
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1);
UnmakeMove();
if (val < best) { // 注意这里不同于“最大”算法
best = val;
}
}
return best;
}
上面的代码可以这样调用：
$val = MinMax(5);$
这样可以返回当前局面的评价，它是向前看5步的结果。
这里的“评价”函数用的是我上面所说第一种定义，它总是返回对于白方来说的局面。
我简要描述一下这个函数是如何运作的。假设根局面(棋盘上当前局面)是白方走，那么调用的是 $“Max”$ 函数，它产生白方所有合理着法。在每个后续局面中，调用的是 $“Min”$ 函数，它对局面作出评价并返回。由于现在是白走，因此白方需要让评价尽可能地大，能得到最大值的那个着法被认为是最好的，因此返回这个着法的评价。
$“Min”$ 函数正好相反，当黑方走时调用 $“Min”$ 函数，而黑方需要尽可能地小，因此选择能得到最小值的那个着法。
这两个函数是互相递归的，即它们互相调用，直到达到所需要的深度为止。当函数到达最底层时，它们就返回 $“Evaluate”$ 函数的值。
如果在深度为 $1$ 时调用 $“MinMax”$ 函数，那么“Evaluate”函数在走完每个合理着法之后就调用，选择一个能达到最佳值的那个着法导致的局面。如果层数大于1，那么另一方有权选择局面，并找一个最好的。
以上内容应该不难理解，但是代码很长，下面有个更好的办法。
负值最大函数
负值最大只是对最小-最大的优化，“评价”函数返回我所说的第二种定义，对于当前结点上要走的一方，占优的情况返回正值，其他结点也是对于要走的一方而言的。这个值返回后要加上负号，因为返回以后就是对另一方而言了。代码如下：
int NegaMax(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -NegaMax(depth - 1); // 注意这里有个负号。
UnmakeMove();
if (val > best) {
best = val;
}
}
return best;
}
ALPHA-BETA搜索
$Alpha-Beta$ 同”最小-最大”非常相似，事实上只多了一条额外的语句。最小最大运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。
这个思想是在搜索中传递两个值，第一个值是 $Alph$a，即搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道Alpha的值，任何小于或等于 $Alpha$ 的值都不会有所提高。
第二个值是 $Beta$，即对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为我们知道在对手看来，他总是会找到一个对策不比Beta更坏的。如果搜索过程中返回 $Beta$ 或比 $Beta$ 更好的值，那就够好的了，走棋的一方就没有机会使用这种策略了。
在搜索着法时，每个搜索过的着法都返回跟 $Alpha$ 和 $Beta$ 有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。
如果某个着法的结果小于或等于 $Alpha$，那么它就是很差的着法，因此可以抛弃。因为我前面说过，在这个策略中，局面对走棋的一方来说是以 $Alpha$ 为评价的。
如果某个着法的结果大于或等于 $Beta$，那么整个结点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于 $Beta$，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。
如果某个着法的结果大于 $Alpha$ 但小于 $Beta$，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此 $Alpha$ 会不断增加以反映新的情况。有时候可能一个合理着法也不超过 $Alpha$，这在实战中是经常发生的，此时这种局面是不予考虑的，因此为了避免这样的局面，我们必须在博弈树的上一个层局面选择另外一个着法。
算法如下，醒目的部分是在最小-最大算法上改过的：
伪代码如下：
int AlphaBeta(int depth, int alpha, int beta) {
if (depth == 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta) {
return beta;
}
if (val > alpha) {
alpha = val;
}
}
return alpha;
}
可以看出现在的算法没有太多的改变。 这个函数需要传递的参数有：需要搜索的深度，负无穷大即Alpha，以及正无穷大即Beta： \(val = AlphaBeta(5, -INFINITY, INFINITY);\) 这样就完成了 $5$ 层的搜索。我在写最小-最大函数时，用了一个诀窍来避免用了 $“Min”$ 还用 $“Max”$ 函数。在那个算法中，我从递归中返回时简单地对返回值取了负数。这样就使函数值在每一次递归中改变评价的角度，以反映双方棋手的交替着子，并且它们的目标是对立的。 在 $Alpha-Beta$ 函数中我们做了同样的处理。唯一使算法感到复杂的是，$Alpha$ 和 $Beta$ 是不断互换的。当函数递归时，$Alpha$ 和 $Beta$ 不但取负数而且位置交换了，这就使得情况比口袋的例子复杂，但是可以证明它只是比最小-最大算法更好而已。 最终出现的情况是，在搜索树的很多地方，Beta是很容易超过的，因此很多工作都免去了。
可能的弱点
这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法，那么 $Beta$ 截断就不会发生，因此该算法就如同最小-最大一样，效率非常低。该算法最终会找遍整个博弈树，就像最小-最大算法一样。
如果程序总是能挑最好的着法来首先搜索，那么数学上有效分枝因子就接近于实际分枝因子的平方根。这是 $Alpha-Beta$ 算法可能达到的最好的情况。
由于国际象棋的分枝因子在 $35$ 左右，这就意味着Alpha-Beta算法能使国际象棋搜索树的分枝因子变成 $6$。
这是很大的改进，在搜索结点数一样的情况下，可以使你的搜索深度达到原来的两倍。这就是为什么使用 $Alpha-Beta$ 搜索时，着法顺序至关重要的原因。
当然，也可以通过以下方法使你的代码更加完善，棋力更加强大。
（不仅限于在此题目上的应用，因层数较小可能并不是很适合）
迭代加深
如果你准备开始搜索一个局面了，你要搜索多深呢？事先预测搜索将进行多少时间，这有些困难，因为完成 $D$ 层搜索所需要的时间取决于很多不确定的因素。在复杂的中局局面里，你可能不会搜索得很深，而在残局中你可能会搜索得非常深，在某些比如象棋的王兵残局里你可能会搜索100多层（并没有非常夸张噢）。
有一个思想，就是一开始只搜索一层，如果搜索的时间比分配的时间少，那么搜索两层，然后再搜索三层，等等，直到你用完时间为止。
这足以保证很好地运用时间了。如果你可以很快搜索到一个深度，那么你在接下来的时间可以搜索得更深，或许你可以完成。如果局面比你想象的复杂，那么你不必搜索得太深，但是至少有合理的着法可以走了，因为你不太可能连1层搜索也完不成。
这个思想称为“迭代加深”$(Iterative\ Deepening)$，因为你在迭代搜索，每次都比一次前一次加深 $1$ 层(多 $1$ 层没有什么奥妙的，当然你可以试试多两层，但是 $1$ 层比较好)。
代码如下：
for (depth = 1; ; depth ++) {
val = AlphaBeta(depth, -INFINITY, INFINITY);
if (TimedOut()) {
break;
}
}
这是一个非常有效的搜索方法，你可能会感到吃惊。如果你能增强 $Alpha-Beta$ 使得它返回一条”主要变例”，你可以用主要变例中的着法来做下一次迭代搜索。
例如，一层的搜索显示 $“1. e4”$ 是最好的着法，那么在做两层的搜索时你先搜索 $“1. e4”$。如果返回 $“1. e4 e5”$，那么你在做三层的搜索时仍旧先搜索这条路线。
这样做之所以有好的效果，是因为第一次搜索的线路通常是好的，而 $Alpha-Beta$ 对着法的顺序特别敏感。如果着法顺序很坏，那么在国际象棋中你的“分枝因子”将接近 $35$。如果你的着法很好，那么分枝因子将接近于 $6 $。前一次迭代的搜索函数得到的主要变例通常是非常好的着法。
迭代加深的思想给了你一个简单的方法，它可以在时间用完时中断搜索，并且会提高你的搜索效率。
(有可能的话，你可以把检测超时的程序做到 $“AlphaBeta”$ 函数里去，而 $“TimeOut”$ 只是由 $“AlphaBeta”$ 函数返回的超时检测结果(如果超时的话，就直接跳出函数体了)。很多情况下，程序没有必要搜索整个一层才给出最佳着法。由于迭代加深的原因，新的一层搜索的第一个着法总是上一层搜索得到的最佳着法，如果新的一层可以搜索出另一个更好的着法，就已经很满意了，有时没有必要找到最好的着法。换句话说，即使你没有足够的时间把这一层搜索完，得到的着法至少不会比上一层最好着法要坏。
静态搜索
举个例子，在国际象棋中，会有很多强制的应对。如果有人用马吃掉你的象，那么你最好吃还他的马。
$Alpha-Beta$ 搜索不是特别针对这种情况的。你把深度参数传递给函数，当深度到达零就做完了，即使一方的后被捉。
一个应对的方法称为“静态搜索”$(Quiescent Search)$。当 $Alpha-Beta$ 用尽深度后，通过调用静态搜索来代替调用 $“Evaluate()”$。这个函数也对局面作评价，只是避免了在明显有对策的情况下看错局势。
简而言之，静态搜索就是应对可能的动态局面的搜索。
典型的静态搜索只搜索吃子着法。这会引发一个问题，因为在国际象棋中吃子通常不是强制的。如果局势很平静，而且你面对的吃子只有 $QxP$ (后吃兵，导致丢后)，你不会强迫后去吃兵的，所以静态搜索不应该强迫吃子。
因此，走子一方可以选择是吃子还是不吃子。这就好比打扑克牌时可以只用手中的牌而不去抓牌。
伪代码如下：
int Quies(int alpha, int beta) {
val = Evaluate();
if (val >= beta) {
return beta;
}
if (val > alpha) {
alpha = val;
}
GenerateGoodCaptures();
while (CapturesLeft()) {
MakeNextCapture();
val = -Quies(-beta, -alpha);
UnmakeMove();
if (val >= beta) {
return beta;
}
if (val > alpha) {
alpha = val;
}
}
return alpha;
}
这看上去和 $ALPHA-BETA$ 非常相似，但是区别是很明显的。这个函数调用静态评价，如果评价好得足以截断而不需要试图吃子时，就马上截断(返回 $Beta$)。如果评价不足以产生截断，但是比 $Alpha$ 好，那么就更新 $Alpha$ 来反映静态评价。
然后尝试吃子着法，如果其中任何一个产生截断，搜索就中止。可能它们没有一个是好的，这也没问题。
这个函数有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通过 $Beta$ 截断马上返回；也可能某个吃子产生 $Beta$ 截断；可能静态评价比较坏，而任何吃子着法也不会更好；或者可能任何吃子都不好，但是静态评价只比 $Alpha$ 高一点点。
注意这里静态搜索中没有传递“深度”这个参数。正因为如此，如果找到好的吃子，或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。
MVV/LVA
$MVV/LVA $ 意思是“最有价值的受害者/最没价值的攻击者” $(Most\ Valuable Victim/Least\ Valuable\ Attacker)$。这是一个应用上非常简单的着法排序技巧，从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。
$MVV/LVA $ 可以解决静态搜索膨胀的问题，但是它仍然留给你比较庞大的静态搜索树。
$MVV/LVA$ 的优势在于它实现起来非常方便，而且可以达到很高的 $NPS$ 值(每秒搜索的结点数)。它的缺点是搜索效率低——你花大量的时间来评估吃亏的吃子，所以你的搜索不会很深。
SEE
$SEE$ 意思是“静态交换评价”(Static Exchange Evaluation)。它比 $MVV/LVA$ 更复杂，但是着法排序更准确，从而很多吃子都不必考虑。
在 $MVV/LVA$ 中你无法去掉 $QxP$ 的着法，因为很可能兵是没保护的，这就意味着 $QxP$ 是好的着法。当然，如果兵是保护的，我不相信你还能在搜索这步时有什么好的发现。用了 $SEE$ 后，如果 $QxP$ 是吃亏的着法，你就可以把它挑出来，然后在吃子的顺序里把它排在最后，或简单地把它裁剪掉。
现在我还没有 $SEE$ 的示范代码，你可以设计一个处理吃子的过程，然后根据它看上去能得到的价值进行排序。【当考虑吃子着法时，需要考虑能吃到的该子的所有攻击子，也要保护该子的所有防守子，因此处理吃子的过程是相当复杂的。】
$SEE$ 能让你非常有效地裁剪掉坏的着法，很多重要的吃子不会被错误地裁剪，并且能改进着法的顺序。你能做的另一件事是，如果着法看起来还不算充分好，那么你可以裁剪掉这些好的着法。如果你领先一个车，那么得一个兵的吃子或许不值得在静态搜索中尝试。
我很怀疑用 $SEE$ 的程序能比相同的但用了 $MVV/LVA$ 的程序强。问题在于代码的编写上，需要很好地设计数据结构，才能让 $SEE$ 变得有效。
静态搜索不是完美的
静态搜索极有可能会犯错误。这是一个不幸的现实，但是它更多地在搜索看上去非常愚蠢(例如一层的搜索，它根本不会是非常好的)的情况下会犯错误，因此这不是一个严重的问题。
如果可能用更准确的静态搜索而不降低速度，那么我肯定这个程序会比以前更强。但是我们必须明白的是，你在耗费时间的前提下试图让静态搜索更准确，需要找到平衡点。如果为了让静态搜索更聪明，你花费了几层完全搜索的时间，那么这就不值得让它更聪明了。
实验代码
很明显，在解决此类问题时，将棋盘定义为一个类。
class ChessBoard:
根据函数判断当前棋盘是否为空。
def is_empty(self):
#判断棋盘是否为空
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] != 0:
return False
return True
做出行动，即对数组中的数据进行修改。
def make_move(self, i, j, flag):
#flag == 1, 着1 flag == 2 ,着2
if self.space[i][j] == 0:
self.space[i][j] = flag
return True
else:
print(i, j ,"is not a legal movement")
return False
pass
根据当前棋盘的情况，生成可以走的地方。
def generate_steps(self):
#生成着法， 便于在ALPHA-BETA处进行搜索
result = []
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
result.append([i, j])
if result is not None:
return result
else:
return False
在 $ALPHA-BETA$ 搜索时，模拟过后需要将模拟的走法给撤回掉。
def withdraw_move(self, i, j, flag):
#撤回某次着法
if self.space[i][j] != 0:
self.space[i][j] = 0
return True
else:
print("not a legal movement")
return False
评估函数，当存在取胜的情况下，返回极大值或极小值。
def evaluation(self, flag):
# 评估函数 根据FLAG 的棋方 对当前棋盘进行评估（优劣势）
scores = 0
if flag == 1:
opposite_flag = 2
else:
opposite_flag = 1
if self.counts_row(flag) != 0:
return 999999999
elif self.counts_column(flag) != 0:
return 999999999
elif self.counts_diagonal(flag) != 0:
return 999999999
if self.counts_row(opposite_flag) != 0:
return -100000
elif self.counts_column(opposite_flag) != 0:
return -100000
elif self.counts_diagonal(opposite_flag) != 0:
return -100000
#temp_list = self.space.deepcopy() #用临时列表来计算得分
temp_list = copy.deepcopy(self.space)
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
self.space[i][j] = flag
scores += self.counts_diagonal(flag) + self.counts_column(flag) + self.counts_row(flag)
self.space = copy.deepcopy(temp_list) #还原
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
self.space[i][j] = opposite_flag
scores -= self.counts_diagonal(opposite_flag) + self.counts_column(opposite_flag) + self.counts_row(opposite_flag)
self.space = copy.deepcopy(temp_list)
return scores
$ALPHA-BETA$ 搜索：结合极大极小搜索并且采用一个在递归前加上一个巧妙的负号来完成。
def alphaBetaSearch(self, flag, depth, alpha, beta):
if depth == 0:
return self.evaluation(flag)
List_steps = self.generate_steps()
while len(List_steps) != 0:
each_step = List_steps.pop(0)
self.make_move(each_step[0], each_step[1], flag)
if flag == 1:
oppisite_flag = 2
else:
oppisite_flag = 1
if depth == 3 and (self.counts_row(flag) != 0 or self.counts_column(flag) != 0) :
self.temp_i = each_step[0]
self.temp_j = each_step[1]
return 99999999999999999999
val = - self.alphaBetaSearch(oppisite_flag, depth - 1, alpha = -beta, beta = -alpha)
self.withdraw_move(each_step[0], each_step[1], flag)
if val >= beta:
return beta
if val > alpha:
alpha = val
#暂存
self.temp_i = each_step[0]
self.temp_j = each_step[1]
return alpha
完整代码如下：
#-*- coding:UTF-8 -*-
import copy
import time
class ChessBoard:
space = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
temp_i = -1
temp_j = -1
def __init__(self):
pass
def is_empty(self):
#判断棋盘是否为空
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] != 0:
return False
return True
def make_move(self, i, j, flag):
#flag == 1, 着1 flag == 2 ,着2
if self.space[i][j] == 0:
self.space[i][j] = flag
return True
else:
print(i, j ,"is not a legal movement")
return False
pass
def one_step_win(self, flag):
pass
def generate_steps(self):
#生成着法， 便于在ALPHA-BETA处进行搜索
result = []
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
result.append([i, j])
if result is not None:
return result
else:
return False
def withdraw_move(self, i, j, flag):
#撤回某次着法
if self.space[i][j] != 0:
self.space[i][j] = 0
return True
else:
print("not a legal movement")
return False
def evaluation(self, flag):
# 评估函数 根据FLAG 的棋方 对当前棋盘进行评估（优劣势）
scores = 0
if flag == 1:
opposite_flag = 2
else:
opposite_flag = 1
if self.counts_row(flag) != 0:
return 999999999
elif self.counts_column(flag) != 0:
return 999999999
elif self.counts_diagonal(flag) != 0:
return 999999999
if self.counts_row(opposite_flag) != 0:
return -100000
elif self.counts_column(opposite_flag) != 0:
return -100000
elif self.counts_diagonal(opposite_flag) != 0:
return -100000
#temp_list = self.space.deepcopy() #用临时列表来计算得分
temp_list = copy.deepcopy(self.space)
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
self.space[i][j] = flag
scores += self.counts_diagonal(flag) + self.counts_column(flag) + self.counts_row(flag)
self.space = copy.deepcopy(temp_list) #还原
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
self.space[i][j] = opposite_flag
scores -= self.counts_diagonal(opposite_flag) + self.counts_column(opposite_flag) + self.counts_row(opposite_flag)
self.space = copy.deepcopy(temp_list)
return scores
def counts_row(self, flag):
# 统计横着 3子的情况 因此功能可能被多次使用故用函数包装
scores = 0
for i in range(0, 3, 1):
if self.space[0][i] == flag and self.space[1][i] == flag and self.space[2][i] == flag:
scores += 1
return scores
def counts_column(self, flag):
# 统计竖着3子的情况
scores = 0
for j in range(0, 3, 1):
if self.space[j][0] == flag and self.space[j][1] == flag and self.space[j][2] == flag:
scores += 1
return scores
def counts_diagonal(self, flag):
#统计对角线3子的情况
scores = 0
if self.space[0][0] == flag and self.space[1][1] == flag and self.space[2][2] == flag:
scores += 1
if self.space[0][2] == flag and self.space[1][1] == flag and self.space[2][0] == flag:
scores += 1
return scores
def alphaBetaSearch(self, flag, depth, alpha, beta):
if depth == 0:
return self.evaluation(flag)
#temp_list = self.generate_steps()
List_steps = self.generate_steps()
print(List_steps)
#List_steps = temp_list
while len(List_steps) != 0:
#for each_step in List_steps:
#print(each_step)
each_step = List_steps.pop(0)
# if self.make_move(each_step[0], each_step[1], flag):
# pass
# else:
# continue
print("将要走出",each_step)
self.make_move(each_step[0], each_step[1], flag)
if flag == 1:
oppisite_flag = 2
else:
oppisite_flag = 1
#print(each_step)
print("深度为:", depth)
print(self.space[each_step[0]][each_step[1]])
if depth == 3 and (self.counts_row(flag) != 0 or self.counts_column(flag) != 0) :
self.temp_i = each_step[0]
self.temp_j = each_step[1]
return 99999999999999999999
val = - self.alphaBetaSearch(oppisite_flag, depth - 1, alpha = -beta, beta = -alpha)
#val = - self.alphaBetaSearch(oppisite_flag, depth-1, -beta, -alpha)
self.withdraw_move(each_step[0], each_step[1], flag)
if val >= beta:
return beta
if val > alpha:
alpha = val
#暂存
self.temp_i = each_step[0]
self.temp_j = each_step[1]
#self.temp_i = -1
#self.temp_j = -1
return alpha
# 博弈树ALPHA-BETA剪枝搜索（并基于MAX-MIN进行改进）
pass
def print_state(self):
for arr in self.space:
print(arr)
return
def space_is_empty(self):
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] != 0:
return False
return True
def space_is_full(self):
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if self.space[i][j] == 0:
return False
return True
def make_random_move(self, flag):
for i in range(0, 3, 1):
for j in range(0 ,3 ,1):
if self.space[i][j] == 0:
self.make_move(i, j, flag)
if flag == 1:
print("黑方走出：", end = "")
else:
print("白方走出", end = "")
print(i, j )
return
# 评估函数存在着一定的问题！在一定的情况下无法阻止对方的胜利 #
if __name__ == "__main__":
#
# chess_board = [[0, 0, 0],
# [0, 0, 0],
# [0, 0, 0]]
alpha = -100000
beta = 100000
chessboard = ChessBoard()
chessboard.print_state()
while True: #待修改
if chessboard.space_is_full():
break
val = chessboard.alphaBetaSearch(flag=1, depth=3, alpha=alpha, beta=beta)
temp_i = chessboard.temp_i
temp_j = chessboard.temp_j
if chessboard.space_is_empty(): #开局走中间
temp_i = 1
temp_j = 1
if chessboard.make_move(temp_i, temp_j, flag = 1): #存在僵持住的局面~
print("黑方走出：", temp_i, temp_j)
pass
else:
print("随机走一步")
chessboard.make_random_move(1)
print("棋盘的状态为:", end = " ")
print("值是：",val)
chessboard.print_state()
time.sleep(1.5)
val = chessboard.alphaBetaSearch(flag=2, depth=3, alpha=alpha, beta=beta)
temp_i = chessboard.temp_i
temp_j = chessboard.temp_j
if chessboard.make_move(temp_i, temp_j, flag=2):
print("白方走出：", temp_i, temp_j)
pass
else:
chessboard.make_random_move(2)
print("棋盘的状态为:", end=" ")
print("值是：", val)
chessboard.print_state()
time.sleep(1.5)
print()
chessboard.print_state()
#alphaBetaSearch()
pass
实验结果
图中所演示的是计算机与计算机的对弈。由于两个计算机均采用的是相同的算法进行博弈，因此走的位置看起来比较笨（不是）。
总结
通过这次实验，我学会如何运用博弈树和 ALPHA-BETA 剪枝算法 对棋类的博弈问题进行解决，并且对 最小最大函数、 负值最大函数等有了一个更加深入的了解，收获颇丰。