论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-02-21 20:00 |只看该作者 |倒序浏览

这几天在用Python写Tic-Tac-Toe小游戏，顺便接触了一些简单的人机博弈算法，其实在算法方面我完全算是个新手，所以这也算是一个反复折腾学习的过程。而Tic-Tac-Toe应该算是人机博弈里最简单的应用了，最经典的算法是miniMax算法，也叫极大极小值算法，主要方法就是通过考虑双方博弈N步后，从所有可能的走法中选一步最佳的走法来走。

因为初学python，而且算法也是新学的，所以代码仍然有所瑕疵，希望和各位多多交流

先简单说说算法的基本思想：
1. 设博弈双方中一方为MAX，另一方为MIN。然后为其中的一方(计算机)找一个最佳走法。

2. 为了找到当前棋局的最优走法，需要对各个可能的走法所产生的后续棋局进行比较，同时也要考虑对方可能的走法，并对后续棋局赋予一定的权值（或者称之为分数）。也就是说，以当前棋局为根节点生成一棵博弈树，N步后的棋局作为树的叶子节点。同时从树根开始轮流给每层结点赋予Max和Min的称号

3. 用一个评估函数来分析计算各个后续棋局（即叶子节点）的权值，估算出来的分数为静态估值

4. 当端节点的估值计算出来后，再推算出父节点的得分。推算的方法是：对于处于MAX层的节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对处于MIN层的节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况，这样计算出的父节点的得分为倒推值。

5.如此反推至根节点下的第一层孩子，如果其中某个孩子能获得较大的倒推值，则它就是当前棋局最好的走法。

把主要的算法写出来了，分为两个函数，一个为估值函数，即计算各个后续棋局（即叶子节点）的权值；另一个为遍历函数，生成指定遍历深度的博弈树。

先贴估值函数代码：

def miniMaxEvalauate(board,player):
opponent = { Player_O : Player_X, Player_X : Player_O }
winning_rows = [[0,1,2],[3,4,5],[6,7,8], # vertical
[0,3,6],[1,4,7],[2,5,8], # horizontal
[0,4,8],[2,4,6]] # diagonal
count=0
clone_pieces=[Empty]*9 # Initialize an empty chessboard
# Copy the current chessboard
for i in range(9):
clone_pieces=board.pieces
# fill it into the clone chessboard
for pos in range(9):
if clone_pieces[pos] == Empty:
clone_pieces[pos]=player
# analyse ur point value
for row in winning_rows:
if allEqual([clone_pieces for i in row]):
count+=1
#==========================================
clone_pieces2=[Empty]*9
for i in range(9):
clone_pieces2=board.pieces
for pos in range(9):
if clone_pieces2[pos] == Empty:
clone_pieces2[pos]=opponent[player]
for row in winning_rows:
if allEqual([clone_pieces2 for i in row]):
count-=1
return count

复制代码

代码里的board.pieces是存储当前棋局位置的变量，这个函数首先复制指定的棋局，然后在复制的棋局将棋盘中的空格填满自己的棋子，然后统计此时自己的棋子在每行每列加上斜线有多少三联通的，每个联通count值加1；接着同样的方法统计在空格填满对方棋子的棋局里，对手的棋子有多少三联通的，每个联通count值减1，这样所得的count值作为估值返回

核心是遍历函数：

def comp2(board,player):
t0 = time.time()
board.output() # print the chessboard
def miniMax(board, depth, p=player):
opponent = { Player_O : Player_X, Player_X : Player_O }
moves=[]
outcomes=[]
# return if game over
if board.gameOver():
if board.gameOver()== player:
return +100
if board.gameOver()== opponent[player]:
return -100
return 0
if depth!=0:
depth-=1
for move in board.getValidMoves():
board.makeMove(move, p)
point=miniMax(board,depth,opponent[p])
outcomes+=[point]
moves+=[move]
board.undoMove(move)
else:
return miniMaxEvalauate2(board,player)
if p != player:
#return min(outcomes)
min_element = 100
n=0
for o in outcomes:
if o == -100:
board.bestmove=moves[n]
return o
min_element = min(o,min_element)
if o==min_element:
board.bestmove=moves[n]
n+=1
return min_element
else:
#return max(outcomes)
max_element = -100
n=0
for o in outcomes:
if o == +100:
board.bestmove=moves[n]
return o
max_element = max(o,max_element)
if o==max_element:
board.bestmove=moves[n]
n+=1
return max_element
miniMax(board, 3)
board.makeMove(board.bestmove, player)
print "computer move: %0.3f ms" % ((time.time()-t0)*1000)

复制代码

depth参数是遍历深度，数值越高估值越准确因而AI也越高，这里通过递归miniMax函数三次来取得三层后的棋局，再进行估值反推，并保存最佳走步的位置，最后选择那步最佳方案走。

写完调试成功后以为大功告成了，结果在对抗中败下阵来，自己的miniMax估值算法导致了以下无语的走法(自己的算法下”X”)：

可以看出自己的下法仿佛在把自己逼入死路，其实这是有限遍历造成权值相同导致的。

在有限遍历很容易出现几种权值相同的情况，即有几个最佳走法，但其中一些可能是陷阱，有时候得遍历多一步可能才能判断出来，可是这样又会耗用过多的资源和时间，这样也完全不是在优化算法。网上的资源也很少有顾及到这个问题，所以只能自己解决，昨晚折腾3点多种仍然无果，才很不痛快地睡了，早上8点起来，突然想到叶节点上两联通棋子的数量也可能是一个重要的因素，自己又尝试着把估价函数优化了一下，基本思想是：估值时看看此时棋局中的每行列斜线里，对方棋子两联通加上一空白的情形有多少，若有这种情形，则扣去比较重的权值以说明此步比较危险，具体代码如下：

def miniMaxEvalauate2(board,player):
opponent = { Player_O : Player_X, Player_X : Player_O }
winning_rows = [[0,1,2],[3,4,5],[6,7,8], # vertical
[0,3,6],[1,4,7],[2,5,8], # horizontal
[0,4,8],[2,4,6]] # diagonal
count=0
clone_pieces=[Empty]*9
for i in range(9):
clone_pieces=board.pieces
for pos in range(9):
if clone_pieces[pos] == Empty:
clone_pieces[pos]=player
for row in winning_rows:
flag=0
for i in row:
if(clone_pieces==opponent[player]):
flag+=1
if (flag==0):
count+=1
if (flag==2):
count-=4
clone_pieces2=[Empty]*9
for i in range(9):
clone_pieces2=board.pieces
for pos in range(9):
if clone_pieces2[pos] == Empty:
clone_pieces2[pos]=opponent[player]
for row in winning_rows:
flag=0
for i in row:
if(clone_pieces2==opponent[player]):
flag+=1
if (flag==3):
count-=1
return count

复制代码

经过测试，用这种优化的估值函数所产生的棋步是无法战胜了。由此可以看出估值函数在算法中的重要程度，直接决定了棋力大小。当然觉得这个算法可能还有完善的地方，感觉它选择棋步的时候比较注重于防御，即侵略性不够强，有一次走出（也有可能是我眼花了）根本不可能取胜的棋步来，可能加强自己棋子的二联通权值可以改善。

[ 本帖最后由 kavingray 于 2009-2-21 20:11 编辑 ]