Tic-Tac-Toe算法笔记(一)：Minimax算法
Feb 9th, 2009 – 8:41 am | Algorithm
这几天在用Python写Tic-Tac-Toe小游戏，顺便接触了一些简单的人机博弈算法，其实在算法方面我完全算是个新手，所以这也算是一个反复折腾学习的过程。而Tic-Tac-Toe应该算是人机博弈里最简单的应用了，最经典的算法是miniMax算法，也叫极大极小值算法，主要方法就是通过考虑双方博弈N步后，从所有可能的走法中选一步最佳的走法来走。
先简单说说算法的基本思想：
1. 设博弈双方中一方为MAX，另一方为MIN。然后为其中的一方(计算机)找一个最佳走法。
2. 为了找到当前棋局的最优走法，需要对各个可能的走法所产生的后续棋局进行比较，同时也要考虑对方可能的走法，并对后续棋局赋予一定的权值（或者称之为分数）。也就是说，以当前棋局为根节点生成一棵博弈树，N步后的棋局作为树的叶子节点。同时从树根开始轮流给每层结点赋予Max和Min的称号
3. 用一个评估函数来分析计算各个后续棋局（即叶子节点）的权值，估算出来的分数为静态估值
4. 当端节点的估值计算出来后，再推算出父节点的得分。推算的方法是：对于处于MAX层的节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对处于MIN层的节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况，这样计算出的父节点的得分为倒推值。
5.如此反推至根节点下的第一层孩子，如果其中某个孩子能获得较大的倒推值，则它就是当前棋局最好的走法。
昨天在网上搜资料的时候也发现一个用Python写的Tic-Tac-Toe，也是基于Minimax算法，看了源码发现它是通过递归将当前棋局之后的所有后续棋局全部遍历出来直到棋局结束，这样倒推上来的得分确实是最优的，而且这个算法也能保证理论上无法被击败。但问题是每走一步都要生成一颗庞大的树，特别是第一步就递归94977次，耗时3000多毫秒，几乎到了无法忍受的地步，最后决定在按照上面的思想自己写个算法，并加到这个源码里和这个大家伙对战，如果一直平局则说明算法有效。
昨天折腾了一个晚上，把主要的算法写出来了，分为两个函数，一个为估值函数，即计算各个后续棋局（即叶子节点）的权值；另一个为遍历函数，生成指定遍历深度的博弈树。
先贴估值函数代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | 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[i]=board.pieces[i] # 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[i] for i in row]): count+=1 #========================================== clone_pieces2=[Empty]*9 for i in range(9): clone_pieces2[i]=board.pieces[i] for pos in range(9): if clone_pieces2[pos] == Empty: clone_pieces2[pos]=opponent[player] for row in winning_rows: if allEqual([clone_pieces2[i] for i in row]): count-=1 return count |
代码里的board.pieces是存储当前棋局位置的变量，这个函数首先复制指定的棋局，然后在复制的棋局将棋盘中的空格填满自己的棋子，然后统计此时自己的棋子在每行每列加上斜线有多少三联通的，每个联通count值加1；接着同样的方法统计在空格填满对方棋子的棋局里，对手的棋子有多少三联通的，每个联通count值减1，这样所得的count值作为估值返回
核心是遍历函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | 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点起来，突然想到叶节点上两联通棋子的数量也可能是一个重要的因素，自己又尝试着把估价函数优化了一下，基本思想是：在叶子节点填补空白估值前，先看看此时棋局中的每行列斜线里，对方棋子两联通加上一空白的情形有多少，若有这种情形，则扣去比较重的权值以说明此步比较危险，具体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | 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[i]=board.pieces[i] 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[i]==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[i]=board.pieces[i] 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[i]==opponent[player]): flag+=1 if (flag==3): count-=1 return count |
用这种优化的估值函数和大家伙下了50局，全部平手，同时自己人工测试了N遍也无获胜的机会，所以理论上说这个算法所产生的棋步是无法战胜了。这个改进的算法平均耗时差不多是20ms，第一步耗时是原来那个大家伙的1%，可以说效率提高了很多。
由此可以看出估值函数在算法中的重要程度，直接决定了棋力大小。当然觉得这个算法可能还有完善的地方，感觉它选择棋步的时候比较注重于防御，即侵略性不够强，有一次走出（也有可能是我眼花了）根本不可能取胜的棋步来，可能加强自己棋子的二联通权值可以改善。
这个笔记里所引用的代码和自己写的Minimax算法都被我写进这个py文件里，包括那个大家伙算法，加以修改后可以让两种算法的计算机去对抗，或者人机对抗
