“人生如棋，走一步看一步是庸者，走一步算三步是常者，走一步定十步是智者。”不管是在生活中，还是在游戏中，我们很多时候都需要对下一步做出决策，如果能够充分地考虑未来可能发生的情况而早做打算，在未来成功的可能性就会提高。在对抗类的游戏中，例如五子棋、象棋等，一般由两个游戏者轮流进行，每次执行一个步骤。我们或计算机在走每一步的时候，通常会对这一步做出评估，比如，令对方当前的优势最小化，或令自己当前的优势最大化，或者多考虑三步、五步，比如对方可能如何走下一步，这一步对未来几步有什么影响。
极大极小值算法和负极大值算法的基本思想
下棋就是一个博弈的过程，如果我们要赋予机器智能，需要给它设计一种博弈的算法。这里介绍一种常用的极大极小值算法（又名MiniMax算法）以及与之相关的负极大值算法。
MiniMax算法是一种找出失败的最大可能性中的最小值的算法，是基于搜索的博弈算法。该算法是一种零总和算法，即一方要在可选的选项中选择将其优势最大化的方法，而另一方则选择令对手优势最小化的方法。该算法的策略本质上使用的是深度搜索策略，所以一般可以使用递归的方法来实现。在搜索过程中，在对本方有利的搜索点上应该取极大值，而在对本方不利的搜索点上应该取极小值（主要是指计算机方）。极小值和极大值都是相对而言的。在搜索过程中需要合理地控制搜索深度，搜索的深度越深，效率越低，但是一般来说，走法越好。
我们知道，常用的博弈算法都是基于搜索的博弈算法，所有可能的下棋步骤构成一棵树的结构，根据树的结构可以对局面进行价值评估。极大极小值算法是这样做的（假设现在要为红方选择最佳走法）：如果当前局面是红方的局面，那么就选择最大值(Value=RedValue-BlackValue)，如果当前是黑方走后形成的局面，那么就选择最小值(Value=BlackValue-RedValue)，也就是最小化红方的利益，其实就是最大化黑方的利益。
负极大值（Negamax）算法是根据MiniMax算法得来的。在负极大值形式的搜索中，一个局面对红方的优势为X，那么对于黑方的优势就是-X；一个局面对红方的优势为-X，那么对黑方的优势就是X。在负极大值算法中，没有极小点，只有极大点。需要注意的是，局面对一方的优势转化为对另一方的优势时，需要加负号。局面估计区间是一个关于0点对称的区间:[-MaxValue,MaxValue]。需要注意的是，为了能使负极大值算法得到正确的评价，必须修改局面并评估函数的返回值，在极大极小值算法中返回的始终是红方的优势，现在要改为当前走棋方的优势。
下面以Tic-Tac-Toe（中文称为井字棋，即两人轮流在井字棋盘的方格内画
或
，谁先将画过的3个方格连成一条直线或对角线，谁就胜利）游戏为例，简单说明搜索策略的使用。
井字棋
下图表示了Tic-Tac-Toe游戏的前两步所有可能的步骤。
井字棋的策略
上图中第0层为空棋盘，第1层是
方所有可能的步骤，第2层是
方所有可能的步骤。在第1层，
方需要选择使其优势最大的步骤，而在第2层，
方则需要选择使
方优势最小（即己方优势最大）的步骤。
MiniMax算法的含义就是极小化对手的最大利益，在上图中，在第2层
方一定会选择使自己优势最大的步骤，而对于
方，需要做的就是选择
方优势最大步骤中的极小值。负极大值算法始终是对本方优势最大化，使对方负优势最大化，这样在搜索时代码更加简洁。
基于负极大值算法的Tic-Tac-Toe游戏的实现
我们基于常用的Python游戏库easyAI来实现一个简单的井字棋游戏。easyAI是一个纯Python人工智能框架，用于两人抽象游戏，如Tic-Tac-Toe、Connect 4、Reversi等。它使定义游戏机制、与计算机对抗或给出游戏解法变得容易。在easyAI中主要采用带剪枝和换位表的Negamax算法。本程序参考https://www.tutorialspoint.com/artificial_intelligence_with_python/artificial_intelligence_with_python_gaming.htm的相关内容。根据该游戏的特点，设计的游戏程序应包括的内容见下图。
井字棋Python程序设计流程
#从easyAI中导入相关类
from easyAI import TwoPlayersGame,AI_Player,Negamax
from easyAI.Player import Human_Player
#创建TicTacToe_game类，它继承于TwoPlayersGame类
class TicTacToe_game(TwoPlayersGame):
#定义初始化函数，定义游戏玩家players，定义棋盘board
def_init_(self,players):
self.players=players
self.nplayer=1
#定义棋盘board为一个9×9的方阵，初始化为0
self.board=[0]＊ 9
#定义可能的移动
def possible_moves(self):
return[x+1 for x,y in enumerate(self.board)if y==0]
#定义玩家的移动
def make_move(self,move):
self.board[int(move)-1]=self.nplayer
#启动AI,定义玩家何时移动
def umake_move(self,move):
self.board[int(move)-1]=0
#定义失败条件，即对手有3个棋子在一条直线上
def condition_for_lose(self):
possible_combinations=[[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
return any([all([(self.board[z-1]==self.nopponent)for z in combination])for combination in possible_combinations])
#定义函数，检查是否完成游戏
def is_over(self):
return(self.possible_moves()==[])or self.condition_for_lose()
#显示当前游戏状态
def show(self):
print('\n'+'\n'.join([''.join([['.','O','X'][self.board[3＊j+i]]for i in range(3)])for j in range(3)]))(www.xing528.com)
#计算分值
def scoring(self):
return-100 if self.condition_for_lose()else 0
#主程序，设置算法为Negamax以及搜索深度
if_name_=="_main_":
algo=Negamax(7)
TicTacToe_game([Human_Player(),AI_Player(algo)]).play()
可以看到运行结果为：
...
...
...
Player 1 what do you play ?1
Move #1:player 1 plays 1:
O..
...
...
Move #2:player 2 plays 5:
O..
.X.
...
Player 1 what do you play ?3
Move #3:player 1 plays 3:
O.O
.X.
...
Move #4:player 2 plays 2:
O X O
.X.
...
Player 1 what do you play ?4
Move #5:player 1 plays 4:
O X O
O X.
...
Move #6:player 2 plays 8:
O X O
O X.
.X.
本章小结
本章介绍了如何利用人工智能解决优化与决策问题，例如求函数的最优值、旅行商路径规划问题、下棋等。在这些人工智能算法中，重要的是如何将一个问题转换为算法可以表达的方式。在编写Python程序时，可以调用相关软件包来完成。
本章习题
请选择一个函数，求取它的最大值或者最小值。
生成若干城市，推销员从一个城市出发，经过所有城市后回到原地，看看怎样走最近。
运行井字棋的程序，和计算机进行对弈。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
