对抗搜索也称为博弈搜索，在一个竞争的环境中，智能体之间通过竞争实现相反的利益，一方最大化这个利益，另外一方最小化这个利益。
最小最大搜索(Minimax Search)是对抗搜索中最为基本的方法，给定一个游戏搜索树，Minimax算法通过每个节点的Minimax值来决定最优策略，当然，MAX希望最大化Minimax值，而MIN则相反。Minimax是一种简单有效的对抗搜索手段 ，但是如果搜索树极大，则无法在有效时间内返回结果。
Alpha-Beta剪枝搜索(Pruning Search)是一种对Minimax进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果。
α
{alpha}
α：玩家MAX目前得到的最高收益；假设
n
{n}
n 是MIN节点，如果
n
{n}
n 的一个后续节点可提供的收益小于훼，则
n
{n}
n 及其后续节点可被剪枝。
β
{beta}
β：玩家MIN目前给对手的最小收益；假设
n
{n}
n 是MAX节点，如果
n
{n}
n 的一个后续节点可获得收益大于훽，则
n
{n}
n 及其后续节点可被剪枝。
α
{alpha}
α 和
β
{beta}
β 的值初始化分别设置为
−
∞
{-infty}
−∞和
+
∞
{+infty}
+∞。
搜索过程即为：每个节点有两个值，分别是
α
{alpha}
α 和
β
{beta}
β 。节点的
α
{alpha}
α 和
β
{beta}
β 值在搜索过程中不断变化。其中，
α
{alpha}
α 从负无穷大(
−
∞
{-infty}
−∞)逐渐增加、
β
{beta}
β 从正无穷大(
+
∞
{+infty}
+∞)逐渐减少。如果一个节点中
α
{alpha}
α >
β
{beta}
β ，则该节点的后续节点可剪枝。
上面的规则可能有点抽象，下面我将从人机井字棋对战来图解Alpha-Beta剪枝搜索；
首先我们需要进行一些设置：
(1)电脑：Max玩家，其落子符号表示为“O”，落子数值表示为“1”；
(2)人类：Min玩家，其落子符号表示为“X”，落子数值表示为“-1”；
(3)棋盘最终为电脑赢，则得分为1，若为人类赢，则得分为-1，若为平局，得分为0；
(4)由于棋盘最终得分只有三种情况-1、0、1，那么
α
{alpha}
α 初始值可设为-2，
β
{beta}
β 初始值可设为2；
假设我们的棋局到了图中蓝色九宫格的情况，现在还剩三个空位置：3、5、6号位可以落子，下一步该Max玩家(电脑)落子，此时，电脑就要思考了，我下哪一个位置更有利呢？
如果电脑落子为3，交换玩家后，人类落子为5，那么电脑最后落子为6，那么电脑将会胜利，如此电脑将会计算之后所有的落子情况。如下图所示，我们可以看到，当电脑这一步落子为6时，最后的结果是电脑胜利或者平局，相比于其他两种存在人类胜利的情况来说，落子为6当是最佳选择，但是怎么样让电脑知道6是最佳选择呢？
图中方框代表Max节点，圆圈代表Min节点，绿色数字代表此时选择落子的位置，蓝色数字代表最终棋盘得分，-1代表Min玩家胜利，1代表Max玩家胜利，0代表平局。
此时我们的
α
{alpha}
α 和
β
{beta}
β 就派上用场了！
每个节点设置有
α
{alpha}
α 和
β
{beta}
β 值，在搜索中不断更新。
更新规则为：
(1)Max节点，只更新
α
{alpha}
α 值，更新为Max(当前
α
{alpha}
α ，下一节点
α
{alpha}
α，下一节点
β
{beta}
β )；
(2)Min节点，只更新
β
{beta}
β 值，更新为Min(当前
β
{beta}
β ，下一节点
α
{alpha}
α，下一节点
β
{beta}
β )；
(3)更新顺序为先左支向下传递，后左支向上更新，再右支向下传递，后右支向上更新；
如图，展示的是左边第一棵树的更新，紫色虚线表示逐步的更新流程。
[1]、[2]步表示左支向下传递，直接将
α
{alpha}
α 和
β
{beta}
β 值向下传递到最后一个节点；
[3]、[4]步表示左支向上更新：
Max节点只更新
α
{alpha}
α，Max(当前
α
{alpha}
α=-2，下一层只有1) = 1 ——>
α
{alpha}
α =1 ，
β
{beta}
β =2
Min节点只更新
β
{beta}
β，Min(当前
β
{beta}
β=2，下一层
α
{alpha}
α=1，下一层
β
{beta}
β=2) = 1 ——>
α
{alpha}
α =-2 ，
β
{beta}
β =1
[5]、[6]步表示右支向下传递，直接父节点
α
{alpha}
α 和
β
{beta}
β 更新后的值向下传递到最后一个节点；
[7]、[8]步表示右支向上更新：
Max节点只更新
α
{alpha}
α，Max(当前
α
{alpha}
α=-2，下一层只有-1) = -1 ——>
α
{alpha}
α =-1 ，
β
{beta}
β =1
Min节点只更新
β
{beta}
β，Min(当前
β
{beta}
β=1，下一层
α
{alpha}
α=-1，下一层
β
{beta}
β=1) = -1 ——>
α
{alpha}
α =-2 ，
β
{beta}
β =-1
图中，红色框为第一次更新结果，黄色框中为节点第二次更新结果。
同理，我们可以按照上面的流程得到所有节点的更新值，最后得到Min层，三个节点的黄色更新框。
对于最顶层的Max节点来说，它需要选择Min层中
β
{beta}
β最大的那个节点对应的选项，这样可以给对手造成最小的收益。
(1)选择3号位：
β
{beta}
β= -1
(2)选择5号位：
β
{beta}
β= -1
(3)选择6号位：
β
{beta}
β= 0
由于对手是Min玩家，需要
β
{beta}
β 值越小越好，那么Max玩家要使Min玩家收益最小，就应当选择
β
{beta}
β 最大的节点，即电脑此时应当选择6号位。
图中的青色方框显示的是
α
{alpha}
α ≥
β
{beta}
β 的情况，如果该节点下面还有节点，就可以进行剪枝，即，其下面的节点不必再进行搜索了。
按照上述的搜索流程，我们就可以进行人机井字棋对战了。实际搜索树会更复杂一些，上面的图解是简化到只剩3步的情况，方便大家理解 α {alpha} α 和 β {beta} β更新的过程。
import random
import numpy as np
# 棋盘显示函数,每次落子后显示棋盘
def show(chessboard):
for i in range(len(chessboard)):
mark = ' '
row = chessboard[i]
for j in row:
mark = mark + tag[j + 1] + ' '
print(mark)
# 判断是否产生赢家
def terminal(chessboard, win, position):
for line in win:
m1,n1 = position[line[0]][0],position[line[0]][1]
m2,n2 = position[line[1]][0],position[line[1]][1]
m3,n3 = position[line[2]][0],position[line[2]][1]
if chessboard[m1][n1] == chessboard[m2][n2] == chessboard[m3][n3] == -1:
return -1
elif chessboard[m1][n1] == chessboard[m2][n2] == chessboard[m3][n3] == 1:
return 1
return 0
# 判断棋盘是否还有空位
def empty(chessboard, position):
for point in position:
if chessboard[point[0]][point[1]] == 0:
return True
return False
# 电脑走位之后,交换玩家,直到棋盘出现赢家或者没有空位
def alpha_beta(chessboard, win, position, now_player, next_player, alpha, beta):
winner = terminal(chessboard, win, position)
if winner != 0:
return winner
elif empty(chessboard, position) == False:
return 0
for i in range(len(position)):
temp = position[i]
if chessboard[temp[0]][temp[1]] == 0:
chessboard[temp[0]][temp[1]] = now_player
test = alpha_beta(chessboard, win, position, next_player, now_player, alpha, beta)
chessboard[temp[0]][temp[1]] = 0
# 如果现在是电脑,Max玩家,修改alpha值
if now_player == 1:
if test > alpha:
alpha = test
if alpha >= beta:
return alpha
# 如果现在是玩家,Min玩家,修改beta值
else:
if test < beta:
beta = test
if alpha >= beta:
return alpha
# 修改上一个节点的值
if now_player == 1:
node = alpha
else:
node = beta
return node
# 电脑计算目前最优的位置
def computer_move(chessboard, win, position):
val = -2
move_ = []
for i in range(len(position)):
temp = position[i]
# 检查所有可走的位置
if chessboard[temp[0]][temp[1]] == 0:
chessboard[temp[0]][temp[1]] = 1 # 假设电脑走该位置
if terminal(chessboard, win, position) == 1:
return temp, i
test = alpha_beta(chessboard, win, position, -1, 1, -2, 2)
chessboard[temp[0]][temp[1]] = 0 # 将该位置清0
if test > val:
val = test
move_ = [temp]
elif test == val:
move_.append(temp)
cmove = random.choice(move_)
for j in range(len(position)):
if cmove == position[j]:
return cmove, j
if __name__ == '__main__':
chessboard = [[0,0,0],[0,0,0],[0,0,0]]
position = [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
win = ((0, 1, 2), (3, 4, 5), (6, 7, 8),
(0, 3, 6), (1, 4, 7), (2, 5, 8),
(0, 4, 8), (2, 4, 6))
tag = ['x', '.', 'o']
result = ['玩家胜利!', '平局!', '电脑胜利!']
player = -1 # 玩家为Min玩家
computer = 1 # 电脑为Max玩家
first = input("请选择哪一方先下,输入x表示玩家先下,输入o表示电脑先下:")
if first == "x":
next_move = player
elif first == "o":
next_move = computer
else:
next_move = player
print("输入有误,默认玩家先下")
show(chessboard)
print('=========================')
print('游戏开始!')
while empty(chessboard, position) and terminal(chessboard, win, position) == 0:
if next_move == player and empty(chessboard, position):
try:
hmove = int(input("请选择你的落子位置(0-8):"))
if chessboard[position[hmove][0]][position[hmove][1]] != 0:
print('该位置已有棋子,请重新选择')
continue
chessboard[position[hmove][0]][position[hmove][1]] = player
next_move = computer
except:
print("输入为0~8,请重试")
continue
if next_move == computer and empty(chessboard, position):
cmove, po = computer_move(chessboard, win, position)
chessboard[cmove[0]][cmove[1]] = computer
print("电脑落子为:", po)
next_move = player
show(chessboard)
print('=========================')
print('最终棋局:')
show(chessboard)
s = terminal(chessboard, win, position)
print('游戏结束:',result[s+1])
print('=========================')
运行一盘试试：
请选择哪一方先下,输入x表示玩家先下,输入o表示电脑先下:x . . . . . . . . . ========================= 游戏开始! 请选择你的落子位置(0-8):8 电脑落子为: 4 . . . . o . . . x 请选择你的落子位置(0-8):5 电脑落子为: 2 . . o . o x . . x 请选择你的落子位置(0-8):6 电脑落子为: 7 . . o . o x x o x 请选择你的落子位置(0-8):1 电脑落子为: 3 . x o o o x x o x 请选择你的落子位置(0-8):0 x x o o o x x o x ========================= 最终棋局: x x o o o x x o x 游戏结束: 平局! =========================
让电脑赢一局：
请选择哪一方先下,输入x表示玩家先下,输入o表示电脑先下:o . . . . . . . . . ========================= 游戏开始! 电脑落子为: 6 . . . . . . o . . 请选择你的落子位置(0-8):1 电脑落子为: 0 o x . . . . o . . 请选择你的落子位置(0-8):4 电脑落子为: 3 o x . o x . o . . ========================= 最终棋局: o x . o x . o . . 游戏结束: 电脑胜利! =========================
参考资料
浙江大学吴飞老师：《人工智能：模型与算法》
Alpha-Beta剪枝算法（人工智能）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）