收藏 分销(赏)

俄罗斯方块的AI设想.ppt

上传人:人****来 文档编号:14416042 上传时间:2026-09-11 格式:PPT 页数:38 大小:1.55MB 下载积分:8 金币
下载 相关
俄罗斯方块的AI设想.ppt_第1页
第1页 / 共38页
俄罗斯方块的AI设想.ppt_第2页
第2页 / 共38页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,俄罗斯方块的AI设想,俄罗斯方块的AI设想俄罗斯方块的AI设想 1.游戏介绍,2.算法分析,3.算法改进设想,1.,游戏介绍,2.,算法分析,3.,算法改进设想,游戏介绍,游戏名称:,俄罗斯方块,作者:,高炎,游戏特点:,在传统俄罗斯方块游戏的基础上加入了,AI,算法,实现了程序自动控制方块进行游戏。这款游戏包括单人模式和人机对战模式。,算法分析,算法解决的问题:,当前方块的最优路径规划问题,算法设计的前提,只考虑当前方块,不进行方块预测,规定方块的动作顺序为“旋转,移动,下落”,不考虑“插空”走法,算法实现,穷举法:找到方块所有的可能落点,通过两个,for,循环实现,任意方块的落点数不会超过,4,*,10=40,2.,评分函数:对所有可能落点进行评分,分数最高的落点即为方块的最佳放置点。,算法分析,评分函数(,Dellacherie,评分函数),1.LH,(,Landing height,),落点高度,方块落点的高度,图中为,2,。,FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,算法分析,评分函数(,Dellacherie,评分函数),2.RE,(,Eroded piece cells,),和消行数有关,等于消行数*方块贡献数,,图中为,1,*,3=3,。,特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),算法分析,评分函数(,Dellacherie,评分函数),3.RT,(,Row transitions,),行变换数,相邻单元格不一样则视为一次,变换,墙视为方块,图中,8,*,2+6+6=24,。,FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,算法分析,评分函数(,Dellacherie,评分函数),4.CT,(,Colum transitions,),列变换数。,FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,算法分析,评分函数(,Dellacherie,评分函数),5.,NH,(,Number of Holes,),空洞数,每列最顶上实方格下方的所有,空方块都为空洞,图中为,2,。,FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,算法分析,评分函数(,Dellacherie,评分函数),FS=a1*LH*,(,-1,),+a2*,RE*,(,+1,),+a3*RT,*,(,-1,)+,a4*,CT*,(,-1,),+a5*NH,*,(,-1,)+a6*,WS*,(,-1,),6.,WS,(,Well Sum,),井的个数,两边都有方块的列为井,,计算公式 ,,图中有三个井,,WS=1+(2+1)+1=5,特征,1.LH,(,Landing height,),2.RE,(,Eroded piece cells,),3.,RT,(,Row transitions,),4.,CT,(,Colum transitions,),5.,NH,(,Number of Holes,),6.,WS,(,Well Sum,),方块相关,状态相关,算法分析,评分函数(,Dellacherie,评分函数),FS=a1*LH*(-1,)+a2*,RE*(+1),+a3*RT,*(-1)+,a4*,CT*(-1),+a5*NH,*(-1,)+a6*,WS*(-1),权重,一位网友给出的权重经验值,a1:-4.500158825082766a2:3.4181268101392694a3:-3.2178882868487753a4:-9.348695305445199a5:-7.899265427351652a6:-3.3855972247263626,算法改进设想,考虑多个已知方块确定当前方块的最优放置点,优化评分函数,找到所有的落点,包括“插空”走法到落点,算法改进设想,找到所有的落点,包括“插空”走法到落点,分析直接走法(旋转,移动,下落)所能到达的落点情况,分析直接走法不能达到的落点情况,给出找到所有落点集的设想算法,算法改进设想,找到所有的落点,包括“插空”走法到落点,方块的坐标:方块的旋转中心。,算法改进设想,找到所有的落点,包括“插空”走法到落点,当前布局的情况:为,8,*,10,的网格,灰色格子表示有方块,,此时有一个,J,方块正准备下落,该方块的,4,个方向形状如左小,图所示,黑色表示旋转中心。,方块的坐标:方块的旋转中心。,1,2,3,4,算法改进设想,找到所有的落点,包括“插空”走法到落点,了解直接走法(旋转,移动,下落)所能到达的落点情况,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,1,2,3,4,方块所有落点情况,算法改进设想,找到所有的落点,包括“插空”走法到落点,分析直接走法不能达到的落点情况,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,1,2,3,4,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,3,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点(结合,A*,算法进行实现),2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点(结合,A*,算法进行实现),2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,2,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,2,2,1,2,3,4,分析直接走法不能达到的落点情况,插空走法,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,2,2,1,2,3,4,分析直接走法不能达到的落点情况,非插空走法,无遮挡的落点,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,2,2,1,2,3,4,分析直接走法不能达到的落点情况,非插空走法,无遮挡的落点,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,2,2,1,2,3,4,分析直接走法不能达到的落点情况,非插空走法,无遮挡的落点,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,3,1,34,2,2,2,1,2,3,4,分析直接走法不能达到的落点情况,非插空走法,无遮挡的落点,有遮挡的落点(插空走法),算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,直接,A*,算法,节点,S,i,:坐标,方向,上一节点,最短路径长度,动作:,T(,旋转,),,,L(,左移一格,),,,R(,右移一格,),,,D(,下移一格,),S0,S1,S2,S3,S4,L,R,D,T,S8,S6,S5,S7,S20,S18,S17,S19,S12,S10,S9,S11,S16,S14,S13,S15,T,L,R,D,T,T,L,L,R,R,D,D,优点,:一定可以找到所有可能落点,缺点,:计算量大,算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,第一步:找到所有可直达的落点。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,1,2,3,4,方块所有落点情况,算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,第二步:找到其他非直达的可能落点的位置。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,1,2,3,4,方块所有落点情况,逐列分析已知落点下方第二个方格起的所有空格,会否为可能落点。,算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,第二步:找到其他非直达的可能落点位置。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,2,3,1,1,2,3,4,方块所有落点情况,逐列分析已知落点下方第二个方格起的所有空格,会否可能为落点。,算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,第二步:找到其他非直达的可能落点位置。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,2,1,2,3,4,方块所有落点情况,逐列分析已知落点下方第二个方格起的所有空格,会否可能为落点。,算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,第二步:找到其他非直达的可能落点位置。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,3,2,1,2,3,4,方块所有落点情况,逐列分析已知落点下方第二个方格起的所有空格,会否可能为落点。,算法改进设想,找到所有的落点,包括“插空”走法到落点(结合,A*,算法进行实现),设想算法找到所有落点集,-,改进,A*,算法,第二步:找到其他非直达的可能落点位置。,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,1,2,3,4,方块所有落点情况,逐列分析已知落点下方第二个方格起的所有空格,会否可能为落点。,算法改进设想,找到所有的落点,包括“插空”走法到落点(结合,A*,算法进行实现),设想算法找到所有落点集,-,改进,A*,算法,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,1,2,3,4,方块所有落点情况,第三步:通过逆,A*,算法寻找目标可能落点到任意已知,可达节点的最短路径。,节点,S,i,:坐标,方向,上一节点,最短路径长度,,可达状态(,-1,0,1,),动作:,T(,旋转,),,,L(,左移一格,),,,R(,右移一格,),,,D(,上移一格,),算法改进设想,找到所有的落点,包括“插空”走法到落点,设想算法找到所有落点集,-,改进,A*,算法,2,24,24,13,1,4,13,1,24,24,2,24,234,1,3,3,3,1,34,2,1,2,3,4,方块所有落点情况,第三步:通过逆,A*,算法寻找目标落点到任意已知,可达节点的最短路径。,为了减少重复搜索,若不能找到可达路径,需要通过回溯标识所有经过的节点为不可达。,若找到最短路径,需要回溯标识所有最短路径上的节点为可达。,谢谢!,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服