使用最大-最小树搜索算法和alpha-beta剪枝算法设计有效围棋走法
使用最大-最小树搜索算法和alpha-beta剪枝算法设计有效围棋走法
我们的世界纷繁复杂，看起来完全不可捉摸。但在很多场景下，它运行的本质其实是通过付出最小的代价获得最大化收益。例如在自然界里的自然选择，光的运行路径。对于人的世界更是如此，由于我们做任何事情，任何选择都要付出相应的成本，因此选择一种决策方式让我们以最小的代价获得最大化的回报无疑是我们行动思考的核心。
围棋，以及一切棋类它的本质就是寻求一种最优化策略，但不同之处在于，它不是寻求即时回报，而是寻求最终回报，我所采取的一系列行动，很可能再当下某个时刻没有回报，乃至要付出代价，但只要我最终获得的收获能达到我的目标即可。
实现该目标的一种可行策略是，你在脑子里考虑一系列行动组合的可能性，然后评估这一系列行动获得的收益，从中选择收益最大化的那一中行动组合。这种策略落实到计算机上就叫树搜索。对于棋类而言，棋手会思考如果我下位置1，对方最有可能会下位置2，然后我会下位置3，对方最有可能接着下位置4…如此推演下去，然后他脑子里评估那种下法序列能让自己获得最佳回报，你能推演的层次越深，这意味着你的功力越高深。
显然人脑能思考的层次深度非常有限，但对于计算机而言，它可以仿造这种方法进行类似的运算，这种算法就叫最大最下树搜索。一个难题在于，如果每一步骤可选的落子方式很多，那样的话走法序列的可能性会随着层次深度的增加而呈现爆炸性增长，对于计算机而言它同样吃不消。
因此除了使用树搜索外，我们还需要好的方法尽可能的减少不必要的搜索，把搜索范围限定在可行性之内，同时还要确保限定范围内的走法序列能够得到好的回报，也就是选定的走法序列能最终战胜对手。每次走到分叉口处，你有n种选择，你有好的办法选出其中3种最佳选择，抛弃n-3种其他选择，这个抛弃过程就叫剪枝。
问题在于很多时候，你根本没有足够的信息作出选择。例如面对10条路，每条路看起来都没有区别，你如何确定走哪几条路距离目的地最近？在这种情况下，我们引入蒙特卡罗树搜索算法，它通过引入随机性的方式，帮我们以概率最大化的方式的走上正确的道路。只要基于这里提到的两种方法，我们可以设计出打败很多棋手的围棋算法，但是你要想打败像柯洁，李世石这样的绝顶高手，我们后面还得引入深度学习技术。
树搜索算法只能应用在特定的游戏规则，那就是游戏以循环方式依次进行，每次轮到你时，你总能有若干种选择。如果游戏不以这种方式进行，例如球类游戏像篮球足球，树搜索就完全用不上。
我们看看树搜索的基本流程：
上图中棋盘首先落子的是X，它有三种方式可选择，它选择其中一种后，对手O也有三种方式可选择，于是X要考虑O落子后自己又该如何选择，如此依次进行，直到棋盘都占据满后，再回溯到第一步，选择走到最后一步时能取得最大收益的那种走法。
在进行树搜索时，我们要遵守几个原则： 1，当前是否有致胜走法，有的话走那一步。 2，当前是否有对方的致胜走法，有的话我要赌住那一步。 3，判断当前能否有两步赢法，例如下图：
假设我们当前下的是三子棋，当三个同样的棋子在行，列，对角线上连在一起时能获胜，那么对于X而言，走中间位置就是两步赢法，因为它可以在对角线相连，也可以中中间那一列相连。 4，判断对方是否有两步赢法，有的话堵住那一步 5，如果上面条件都不成立，你选择经过给定层次后能够取得最大好处的那一步。
上面原则还有很多细节待考虑和待落实，我们将使用代码的方式，一步一步将上面的原则细化，落实，首先我们先定义三种状态：
class GameResult(enum.Enum):
loss = 1
#平局
draw = 2
win = 3假设你现在有一个函数best_result，你从当前所有走法中选择一种后，调用该函数你就能得到最终结果，也就是它会返回上面三种值之一。假设你当前有3中走法，你选择走法1，调用best_result后返回loss，这意味着你选择走法1你会失败；你选择走法2，调用best_result后返回2，着意味着你选择走法2最终会获得平局；你选择走法3后，调用best_result返回3，着意味着你选择走法3或获得最终的胜利，由此必然要在当下选择走法3.
由此我们得到一个走法框架。首先你遍历当前所有可能的走法，对每一种走法，你调用best_result对每种走法进行筛选，显然返回loss的走法是必须去除，如果有返回win的走法，你就必须选择，如果所有走法都返回draw，那么你就随机选取其中一种,由此我们得到相应代码：
class MiniMaxAgent(Agent):
def select_move(self, game_state):
'''
遍历所有可行走法，根据best_result返回结果挑选最合适的走法
'''
winning_moves = []
draw_moves = []
losing_moves = []
for possible_move in game_state.legal_moves():
next_state = game.state.apply_move(possible_move)
#尝试一种可行走法后，看对手可以得到什么好处
opponent_best_outcome = best_result(next_state)
'''
根据对手结果评估我们选取走法的结果,如果opponent_best_outcome等于loss,
our_best_outcome就是win,如果如果opponent_best_outcome等于draw,
our_best_outcome就是draw,如果opponent_best_outcome等于loss,
our_best_outcome就是win
'''
our_best_outcome = reverse_game_result(opponent_best_outcome)
if our_best_outcome == GameResult.win:
winning_moves.append(possible_move)
elif out_best_outcome == GameResult.draw:
draw_moves.append(possible_move)
else:
losing_moves.append(possible_move)
if winning_moves:
return random.choice(winning_moves)
if draw_moves:
return random.choice(draw_moves)
return random.choice(losing_moves)接下来问题是，如何实现函数best_result。我们先从最简单的状况处理，如果当前棋局结束，那么函数只要判断当前谁赢谁输即可：
def best_result(game_state):
if game_state.is_over():
if game_state.winner() == game.state.next_player:
return GameResult.win
elif game_state.winner() is None:
return GameResult.draw
else:
return GameResult.loss如果当前棋局还未结束，那么我们得对各种可能下法进行搜索，我们当前搜索采取全遍历的方式，也就是查找双方直到棋局结束时的所有落子次序，然后通过结束时的输赢来决定当前走法好坏：
def best_result(game_state):
if game_state.is_over():
if game_state.winner() == game.state.next_player:
return GameResult.win
elif game_state.winner() is None:
return GameResult.draw
else:
return GameResult.loss
best_result_so_far = GameResult.loss
for candidate_move in game_state.legal_move():
#查询所有走法
next_state = game_state.apply_move(candidate_move)
#递归执行去判断当前走法的好坏
opponent_best_result = best_result(next_state)
our_result = reverse_game_result(opponent_best_result)
if out_result.value > best_result_sor_far.value:
best_result_so_far
return best_result_so_far上面算法思路很简单，就是比你的对手所思考一层，然后封堵住一切有利于对手的走法。这种算法能让你战无不胜，而且这种算法能应用到所有棋类游戏中。理论上可行但是实践上不可行，因为你要遍历全部走法，从中选出最好的。但对于围棋而言，它所有可能性是50010亿10亿，也就是5后面跟20个0，全宇宙的原子数都没有那么多，因此无论多强大的超级计算机都不可能把所有情况遍历一便！
因此我们必须过滤掉足够多的情况，把要搜索的数量控制在计算机可运算范围内，这种过滤过程就叫剪枝。上面我们看到的搜索树有两个数量需要考虑，一个是宽度W，也就是当前有多少走法；一个是深度d，也就是从当前局势一直到结束需要多少步。由此树的大小我们用W^d来表示。对围棋而言W=250, d=150,于是围棋的搜索树大小有250^150 = 10^359.世上没有任何计算机能处理得了这个量级的数据。
公式W^d也表示出，只要我们能稍微减少W或d的值，数量级会迅速缩小。假设W=10,d=10，W^d=10亿。如果我们能把W减少到8，d减少到9，8^9=1千万，于是我们一下子就能减少98%以上的计算量！
对围棋而言，有两种剪枝方式，一种叫位置评估函数，它用于减少树的深度，一种叫alpha-beta剪枝，它用于减少树的宽度，后面我们引入AI技术时，就是要作用到这两种剪枝算法上。
所谓位置评估函数，其实就是计算当前局面的好坏。对围棋而言，一种最简单的评估就是计算你在棋盘上的棋子数量和对方在棋盘上的棋子数量，你的棋子越多就越好，很显然这种评估方式并不符合围棋精髓，但基本可用，在后面我们需要用人工智能技术才能做出准确评估。
由此我们不用遍历所有可能情况，例如当前我们还需要走100步才能结束对弈。但我们的搜索树只要走10步，然后用评估函数预测一下10步之后的好坏如何即可。
我们看看评估函数的实现：
def capture_diff(game_state):
'''
计算双方在棋盘上的棋子数量，进而评估当前局面好坏，己方的棋子数比对方多意味着局面好
'''
black_stones = 0
white_stones = 0
for r in range(1, game_state.board.num_rows + 1):
for c in range(1, game_state.board.num_cols + 1):
#遍历棋盘每个位置，统计两种颜色棋子数量
p = Point(r, c)
color = game_state.board.get(p)
if color == Player.black:
black_stones += 1
elif color == Player.white::
white_stones += 1
diff = black_stones - white_stones
if game_state.next_player == Player.black:
return diff
return -1 * diff我们看使用位置评估，和深度限制后的情景：
我们看上图，搜索树的高度限定为4，走到第四步后我们进行评估，计算不同棋子的数量，上图是以X为计算方，因此1表示X的数量比O多一个，于是我们从最后一行可以得知那种下面最好，那就是沿着最底部为1的地方倒推回去,由此我们就从深度上对搜索树进行剪裁，由此我们修改前面best_result函数，限定它递归搜索的层次：
MAX_SCORE = 999999
MIN_SCORE = -999999
#改进版best_resut,控制递归搜索的深度
def best_result(game_state, max_depth, eval_fn):
if game_state.is_over():
if game_state.winner() == game_state.next_player:
return MAX_SCORE
else:
return MIN_SCORE
#max_depth变量控制遍历深度
if max_depth == 0:
#抵达允许的最大层次后评估局面好坏
return eval_fn(game_state)
best_so_far = MIN_SCORE
for candidate_move in game_state.legal_moves():
next_state = game_state.apply_move(candidate_move)
opponet_best_result = best_result(next_state, max_depth - 1, eval_fn)
our_result = -1 * opponent_best_result
if our_result > best_so_far:
best_so_far = our_result
return best_so_far上面代码限定了搜索的深度，接下来我们要限定搜索的宽度。假设当前走法有100种，我们并非把全部走法都尝试一遍，通过一些规则的判断，我们可以过滤掉90种，只尝试剩下的10种走法。
问题是通过怎样的规则去过滤当前其他不必要走法呢。其做法是记录双方当前最好得分，对于落子一方，它可能有很多种选择，但它只要寻找到一种方法使得它能尽可能的减少对方当前最好得分即可。
在横向上减少搜索范围的算法叫alpha-beta剪枝,我们看一个具体实例：
假设黑白两方当前最佳得分为0，限定搜索深度为3，当前轮到黑棋落子，它会遍历所有可行落子点，假设它落在B点，那么在后面的深度搜索中，它发现在3步以内，对方最好的落子点是最左上角，这样就能至少吃掉3个黑棋，于是对方最佳得分是3，如果黑子落在B点，对方落在最左上角，白棋就可以吃掉4个黑棋，因此落在B点会使得在3步内，对方最佳得分增加为4，让对方得分变高的方法当前绝对不可行。
如果落子在A点，黑棋至少能吃掉2个白棋，而在接下来的搜索中黑棋知道白棋在2步（由于搜索深度是3，黑棋已经走了一步，只剩下2步）内，最好的收获是走最左上角至少吃掉3个黑棋，于是落在A点能将对手的最佳得分从3分变成1分，于是黑棋搜索到A点时停止不再考虑其他情况，因为在这里落子已经能够减少对方的最好得分。
我们通过代码实现能够得到更清楚的理解：
'''
进一步改进best_result，在控制搜索深度的同时，控制搜索宽度。我在当前选定一步后，往后推2步，
2步后如果得分能减少对方的最好得分，那么我就在这一步停止，不再考虑其他可能性
'''
def alpha_beta_result(game_state, max_depth, best_black, best_white, eval_fn):
if game_state.is_over():
if game_state.winner() == game_state.next_player:
return MAX_SCORE
else:
return MIN_SCORE
if max_depth == 0:
return eval_fn(game_state)
best_so_far = MIN_SCORE
for candidate_move in game_state.legal_moves():
next_state = game_state.apply_move(candidate_move)
opponent_best_result = alpha_beta_result(next_state, max_depth - 1,
best_black, best_white,
eval_fn)
our_result = -1 * opponent_best_result
if our_result > best_so_far:
best_so_far = our_result
if game_state.next_player == Player.white:
if best_so_far > best_white:
best_white = best_so_far
outcome_for_black = -1 * best_so_far
if outcome_for_black < best_black:
#如果白棋落子，选择能够减少黑棋当前最好得分的步骤
return best_so_far
elif game_state.next_player == Player.black:
#如果是黑棋落子，那么选择能够减少白棋当前最好得分的步骤
if best_so_far > best_black:
best_black = best_so_far
outcome_for_white = -1 * best_so_far
if outcome_for_white < best_white:
return best_so_far
return best_so_far在上面代码实现中，落子时搜索棋盘每一个可行位置，当找到第一个可行位置能使得对方的得分减少时，我就终止搜索。这会带来一个问题，如果当前能够让对方减分的位置有多个，不同的位置能够给对方带来减分的数量不一样，上面算法很可能会选出让对方减分最少的那个位置。
按逻辑我们应该选择让对方减分最多的位置才对。但如此会大大增加运算量，因此综合考虑，我们只要找到第一个让对方减分的位置即可，不管这个位置能给对方减多少分，这种想法其实与贪婪算法如出一辙，我只要获得好处就收手，不管后面是不是还有更大的好处。
完成上面代码后，运行人机对弈流程：
def main():
board_size = 9
game = GameState.new_game(board_size)
#change here
bot = AlphaBetaAgent(2, capture_diff)
while not game.is_over():
print_board(game.board)
if game.next_player == Player.black:
human_move = input('--')
point = point_from_coords(human_move.strip())
move = Move.play(point)
else:
print('before bot select move')
move = bot.select_move(game)
print('after bot select move')
print_move(game.next_player, move)
game = game.apply_move(move)
main()运行上面代码，同时我把搜索深度为2时的运行时间打印出来如下：
从上面打印可以看出，一开始机器搜索时耗时很长，达到3秒多，后来一下子加快到不到1秒，这是因为alpha-beta剪枝产生作用，它不用循环棋盘所有位置，只要找到第一个能够减少对手得分的位置即可。
虽然我们使用了剪枝技术去降低机器落子时的搜索数量级，但目前我们使用的剪枝技术在最好情况下，只能讲运行时间由原来的W^d减少为W^(d/2)，这是在最好情况下，最坏情况下就是没有任何改进，在完成上面代码后，机器落子需要时间依然超出合理范围，从我运行的情况看，机器在十分钟以内依然没有执行完上面的代码！
在后面章节中，我们会运用新的方法处理我们当下遇到的问题。
腾讯云开发者
