俄罗斯方块的AI设想.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 俄罗斯方块 AI 设想
- 资源描述:
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,俄罗斯方块的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*,算法寻找目标落点到任意已知,可达节点的最短路径。,为了减少重复搜索,若不能找到可达路径,需要通过回溯标识所有经过的节点为不可达。,若找到最短路径,需要回溯标识所有最短路径上的节点为可达。,谢谢!,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


俄罗斯方块的AI设想.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14416042.html