python |
您所在的位置：网站首页 › 博弈树的节点表示什么 › python |
python
|
博弈树解决井字棋游戏
问题内容算法流程相关设置具体程序运行结果完结
问题内容
【Game: tic-tac-toe (井字棋)】 两个玩家，一个max一个min，每次放X或O，交替走步，直到结束状态。 赢的定义：棋盘上有3个X或者3个O，在同一行或同一列或对角线上。 结束状态：max赢或min赢，或者棋盘被摆满平局。 使用minmax算法或alpha-beta剪枝策略实现井字棋的游戏。 alpha-beta剪枝策略 （1）搜索深度也就是往下推算的步数是9，叶子节点估价函数的定义为f(board)=-1为人玩家赢，f(board)=1为电脑赢，f(board)=0为平局； （2）棋盘的位置用数字0-8来表示，对应的使用列表来存储； （3）win元组中存储的是所有可能取胜的位置情况，位置组合也是用元组表示。 （4）为了输出棋盘，设置mark列表[‘·’，‘O’，‘X’]通过循环将使用的-1,1，0转换成标记符号。 具体程序本人来自江南大学，同校的小伙伴们记得修改修改，以免查重 # -*- coding: utf-8 -*- """ Created on Fri Apr 17 10:31:56 2020 @author: Administrator """ import random # 用0-8的9个数字来表示棋盘的位置:0,1,2,3,4,5,6,7,8, #WIN表示的是取胜的情况，即一行，一列，对角线相同时。 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)) row= ((0, 1, 2), (3, 4, 5), (6, 7, 8)) # -1表示玩家 0表示空位 1表示电脑. X_HUMAN= -1 EMPTY = 0 O_COMPUTER= 1 #棋盘上的值为0,1，-1，正好可以和mark中的标志相对应 #mark中的标志是为了输出棋盘 mark= ['·', 'O', 'X'] RESULT= ['平局', '电脑胜利', '玩家胜利'] HUMAN = 1 COMPUTER = 0 #输出当前的棋盘状态 def PRINT(board): for i in row: re= ' ' for j in i: re+= mark[board[j]] + ' ' print(re) #判断当前棋盘是否还有空位,true表示还有空位，false表示没有空位了 #判断当前棋盘board的每一个位置是否为空 def isEmpty(board): for item in range(0,9): if board[item] == EMPTY: return True return False #判断是否已经产生赢家 #-1表示玩家获胜，1表示电脑获胜，0为平局或者还未结束 #在主程序的while循环中返回为0则表示还未结束，while循环结束后返回的0表示平局 def winner(board): for i in WIN: #-1即为玩家，1为电脑 if board[i[0]]==board[i[1]]==board[i[2]]==-1: return -1 elif board[i[0]]==board[i[1]]==board[i[2]]==1: return 1 return 0 #alpha-bate剪枝策略的具体内容 '''这里的搜索深度是9，叶子节点的估价函数值为1电脑赢，-1玩家赢，0是平局''' def A_B(board, player, next_player, alpha, beta): board1=board win = winner(board1) #有玩家获胜时 if win!= EMPTY: return win elif not isEmpty(board1): # 没有空位,平局 return 0 # 检查当前玩家"player"的所有可落子点 for move in range(0,9): if board1[move] == EMPTY: board1[move] = player # 落子之后交换玩家，继续检验 val = A_B(board1, next_player, player, alpha, beta) board1[move] = EMPTY #对于一个MAX节点，估计出其倒推值的下确界Alpha， #若这个Alpha值不小于MAX的父节点(MIN节点)的估计倒推值的上确界Beta，即Alpha≥Beta， #则就不必再扩展该MAX节点的其余子节点了，为Beta剪枝。 if player == O_COMPUTER: # 当前玩家是Max玩家，是1 if val > alpha: alpha = val if alpha >= beta: return beta # 直接返回当前的最大可能取值beta, 进行剪枝 #对于一个MIN节点，估计出其倒推值的上确界Beta， #这个Beta值不大于MIN的父节点(MAX节点)的估计倒推值的下确界Alpha，即Alpha≥Beta， #则就不必再扩展该MIN节点的其余子节点了，为Alpha剪枝。 else: # 当前玩家是Min玩家，是-1 if val |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |