俄罗斯方块的AI设想

1、俄罗斯方块的AI设想 1. 游戏介绍 2. 算法分析 3. 算法改进设想游戏介绍游戏名称：俄罗斯方块 作者：高炎游戏特点：在传统俄罗斯方块游戏的基础上加入了AI算法，实现了程序自动控制方块进行游戏。这款游戏包括单人模式和人机对战模式。算法分析算法解决的问题：当前方块的最优路径规划问题算法设计的前提1. 只考虑当前方块，不进行方块预测2. 规定方块的动作顺序为“旋转，移动，下落”，不考虑“插空”走法算法实现1. 穷举法：找到方块所有的可能落点，通过两个for循环实现，任意方块的落点数不会超过4*10=402. 评分函数：对所有可能落点进行评分，分数最高的落点即为方块的最佳放置点。算法分析评分函数

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 ）方块相关状态相关算法分

3、析评分函数（ 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 * (

4、-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、）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

6、. 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（

7、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=5wells)(depth21 (ww特征1.LH（Landing height）2.RE（ Eroded

8、 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.500158825082766 a2: 3.4181268101392694 a3 : -3

9、.2178882868487753 a4 : -9.348695305445199 a5 : -7.899265427351652 a6 : -3.3855972247263626 算法改进设想1. 考虑多个已知方块确定当前方块的最优放置点2. 优化评分函数3. 找到所有的落点，包括“插空”走法到落点算法改进设想3. 找到所有的落点，包括“插空”走法到落点A. 分析直接走法（旋转，移动，下落）所能到达的落点情况B. 分析直接走法不能达到的落点情况C. 给出找到所有落点集的设想算法算法改进设想3. 找到所有的落点，包括“插空”走法到落点l方块的坐标：方块的旋转中心。算法改进设想3. 找到所有的落

10、点，包括“插空”走法到落点l当前布局的情况：为8*10的网格，灰色格子表示有方块，此时有一个J方块正准备下落，该方块的4个方向形状如左小图所示，黑色表示旋转中心。l方块的坐标：方块的旋转中心。1234算法改进设想3. 找到所有的落点，包括“插空”走法到落点A. 了解直接走法（旋转，移动，下落）所能到达的落点情况2242413141312424224234133311234方块所有落点情况算法改进设想3. 找到所有的落点，包括“插空”走法到落点B. 分析直接走法不能达到的落点情况2242413141312424224234133311234插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找

11、到所有的落点，包括“插空”走法到落点22424131413124242242341333131234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331341234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331341234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“

12、插空”走法到落点（结合A*算法进行实现）224241314131242422423413331341234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点（结合A*算法进行实现）2242413141312424224234133313421234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点22424131413124242242341333134221234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法

13、改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331342221234B. 分析直接走法不能达到的落点情况插空走法l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331342221234B. 分析直接走法不能达到的落点情况非插空走法l 无遮挡的落点l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331342221234B. 分析直接走法不能达到的落点情况非插空走法l 无遮挡的

14、落点l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点224241314131242422423413331342221234B. 分析直接走法不能达到的落点情况非插空走法l 无遮挡的落点l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点2242413141312424224234133331342221234B. 分析直接走法不能达到的落点情况非插空走法l 无遮挡的落点l 有遮挡的落点（插空走法）算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-直接A*算法l节点Si：坐标，方向，上一节点

15、，最短路径长度l动作：T(旋转)，L(左移一格)， R(右移一格)，D(下移一格)S0S1S2S3S4L RDTS8S6S5S7S20S18S17S19S12S10S9S11S16S14S13S15TLR DTTLLRRDD优点：一定可以找到所有可能落点缺点：计算量大算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-改进A*算法第一步：找到所有可直达的落点。2242413141312424224234133311234方块所有落点情况算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-改进A*算法第二步：找到其他非直达的可能

16、落点的位置。2242413141312424224234133311234方块所有落点情况逐列分析已知落点下方第二个方格起的所有空格会否为可能落点。算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-改进A*算法第二步：找到其他非直达的可能落点位置。22424131413124242242341332311234方块所有落点情况逐列分析已知落点下方第二个方格起的所有空格会否可能为落点。算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-改进A*算法第二步：找到其他非直达的可能落点位置。224241314131242422423

17、41333121234方块所有落点情况逐列分析已知落点下方第二个方格起的所有空格会否可能为落点。算法改进设想3. 找到所有的落点，包括“插空”走法到落点C. 设想算法找到所有落点集-改进A*算法第二步：找到其他非直达的可能落点位置。224241314131242422423413331321234方块所有落点情况逐列分析已知落点下方第二个方格起的所有空格会否可能为落点。算法改进设想3. 找到所有的落点，包括“插空”走法到落点（结合A*算法进行实现）C. 设想算法找到所有落点集-改进A*算法第二步：找到其他非直达的可能落点位置。2242413141312424224234133313421234方块所有落点情况逐列分析已知落点下方第二个方格起的所有空格会否可能为落点。算法改进设想3. 找到所有的落点，包括“插空”走法到落点（结合A*算法进行实现）C. 设想算法找到所有落点集-改进A*算法2242413141312424224234133313421234方块所有落点情况第三步：通过逆A*算法寻找目标可能落点到任意已