More
GameRes游资网在以下平台有媒体号，欢迎关注收藏：

微信公众号

微博 

头条号

百家号

网易号

知乎号

H5版俄罗斯方块游戏开发：游戏的AI算法

作者：mumuxinfei 2016-03-28

GameRes游资网授权发布 算是"long long ago"的事了, 某著名互联网公司在我校举行了一次"lengend code"的比赛, 其中有一题就是"智能俄罗斯方块"。 本着一向甘做分母, 闪耀分子的绿叶精神, 着着实实地打了一份酱油。 这次借学习H5的机会, 再来重温下俄罗斯方块的AI编写。

演示&下载:

该版本依旧较为简陋, 效果如图所示:


其代码下载地址为: http://pan.baidu.com/s/1sjyY7FJ

下载解压目录结构如下所示:


点击tetris.html, 在浏览器上运行(由于HTML5程序, 最好在Chrome/Firefox上运行)。

算法分析:

核心算法参考了如下博文:

  • 传统规则俄罗斯方块AI技术介绍
  • 控制台彩色版带AI的『俄罗斯方块』


本程序也采用改进的Pierre Dellacherie算法(只考虑当前方块)。

其对局面的评估, 采用6项指标:

1)Landing Height(下落高度): The height where the piece is put (= the height of the column + (the height of the piece / 2))

2)Rows eliminated(消行数): The number of rows eliminated。

3)Row Transitions(行变换): The total number of row transitions.A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa.

4)Column Transitions(列变换): The total number of column transitions.A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa.

5)Number of Holes(空洞数): A hole is an empty cell that has at least one filled cell above it in the same column.

6)Well Sums(井数): A well is a succession of empty cells such that their left cells and right cells are both filled.

对各个指标进行加权求和, 权重系数取自经验值:

  1. -4.500158825082766
  2. 2 3.4181268101392694
  3. 3 -3.2178882868487753
  4. 4 -9.348695305445199
  5. 5 -7.899265427351652
  6. 6 -3.3855972247263626
复制代码

源码解读:

代码文件结构如图所示:


  • tetris_base.js: 公共的数据结构, 包括方块定义和方块池等
  • tetris_ai.js: 具体定义了AI的核心算法和数据结构。
  • tetris_game。js: 是整个程序的展示和驱动。


这边主要讲讲tetris_ai.js这个代码文件, 里面有三个重要的类, MoveGenerator, Evaluator, AIStrategy.

MoveGenerator用于生成各个可行落点以及对应的路径线路：

  1. /*
  2. * @brief    走法生成器
  3. */
  4. function MoveGenerator() {
  5. }

  7. MoveGenerator.prototype.generate = function(tetrisUnit, shape) {

  9.     var keymapFunc = function(x, y, idx) {
  10.         return "" + x + ":" + y + ":" + idx;
  11.     }

  13.     var moveMapFunc = function(step) {
  14.         return {x:step.x, y:step.y, idx:step.idx};
  15.     }

  17.     var results = [];

  19.     var boards = tetrisUnit.boards;
  20.     var rownum = tetrisUnit.row;
  21.     var colnum = tetrisUnit.col;
  22.     var shapeArrs = shape.shapes;

  24.     var occupy = {}

  26.     var actionQueues = [];
  27.     actionQueues.push({x:shape.x, y:shape.y, idx:shape.idx, prev:-1});
  28.     occupy[keymapFunc(shape.x, shape.y, shape.idx)] = true;

  30.     var head = 0;
  31.     while ( head < actionQueues.length )  {
  32.         var step = actionQueues[head];

  34.         // 1). 向左移动一步
  35.         var tx = step.x - 1;
  36.         var ty = step.y;
  37.         var tidx = step.idx;
  38.         if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
  39.             var key = keymapFunc(tx, ty, tidx);
  40.             if ( !occupy.hasOwnProperty(key) ) {
  41.                 actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
  42.                 occupy[key] = true;
  43.             }
  44.         }

  46.         // 2). 向右移动一步
  47.         tx = step.x + 1;
  48.         ty = step.y;
  49.         tidx = step.idx;
  50.         if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
  51.             var key = keymapFunc(tx, ty, tidx);
  52.             if ( !occupy.hasOwnProperty(key) ) {
  53.                 actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
  54.                 occupy[key] = true;
  55.             }
  56.         }

  58.         // 3). 旋转一步
  59.         tx = step.x;
  60.         ty = step.y;
  61.         tidx = (step.idx + 1) % 4;
  62.         if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
  63.             var key = keymapFunc(tx, ty, tidx);
  64.             if ( !occupy.hasOwnProperty(key) ) {
  65.                 actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
  66.                 occupy[key] = true;
  67.             }
  68.         }

  70.         // 4). 向下移动一步
  71.         tx = step.x;
  72.         ty = step.y + 1;
  73.         tidx = step.idx;
  74.         if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
  75.             var key = keymapFunc(tx, ty, tidx);
  76.             if ( !occupy.hasOwnProperty(key) ) {
  77.                 actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
  78.                 occupy[key] = true;
  79.             }
  80.         } else {

  82.             // *) 若不能向下了, 则为方块的一个终结节点.
  83.             var tmpMoves = [];
  84.             tmpMoves.push(moveMapFunc(step));
  85.             var tprev = step.prev;
  86.             while ( tprev != -1 ) {
  87.                 tmpMoves.push(moveMapFunc(actionQueues[tprev]));
  88.                 tprev = actionQueues[tprev].prev;
  89.             }
  90.             tmpMoves.reverse();

  92.             results.push({last:step, moves:tmpMoves});
  93.         }
  94.         head++;
  95.     }
  96.     return results;

  98. }
复制代码

Evaluator类, 则把之前的评估因素整合起来：

  1. function Evaluator() {
  2. }

  4. Evaluator.prototype.evaluate = function(boards) {
  5. }

  7. function PierreDellacherieEvaluator() {
  8. }

  10. PierreDellacherieEvaluator.prototype = new Evaluator();
  11. PierreDellacherieEvaluator.prototype.constructor = PierreDellacherieEvaluator;

  13. PierreDellacherieEvaluator.prototype.evaluate = function(boards, shape) {
  14.     return (-4.500158825082766) * landingHeight(boards, shape)          // 下落高度
  15.             + (3.4181268101392694) * rowsEliminated(boards, shape)      // 消行个数
  16.             + (-3.2178882868487753) * rowTransitions(boards)            // 行变换
  17.             + (-9.348695305445199) * colTransitions(boards)             // 列变化
  18.             + (-7.899265427351652) * emptyHoles(boards)                 // 空洞个数
  19.             + (-3.3855972247263626) * wellNums(boards);                 // 井数
  20. }
复制代码

AIStrategy整合了落地生成器和评估函数, 用于具体决策最优的那个落地点, 以及行动路线。

  1. function AIStrategy() {
  2. this.generator = new MoveGenerator();
  3. this.evalutor = new PierreDellacherieEvaluator();
  4. }

  6. /*
  7. * @brief 作出最优的策略
  8. * @return  {dest:{x:{x}, y:{y}, idx:{idx}}, [{action_list}]}
  9. */
  10. AIStrategy.prototype.makeBestDecision = function(tetrisUnit, shape) {

  12.     var bestMove = null;
  13.     var bestScore = -1000000;

  15.     // 1) 生成所有可行的落点, 以及对应的路径线路
  16.     var allMoves = this.generator.generate(tetrisUnit, shape);

  18.     // 2) 遍历每个可行的落点, 选取最优的局面落点
  19.     for ( var i = 0; i < allMoves.length; i++ ) {
  20.         var step = allMoves[i].last;

  22.         var shapeArrs = shape.shapes;
  23.         var bkBoards = tetrisUnit.applyAction2Data(step.x, step.y, shapeArrs[step.idx]);

  25.         // 2.1) 对每个潜在局面进行评估
  26.         var tscore = this.evalutor.evaluate(bkBoards, {x:step.x, y:step.y, shapeArr:shapeArrs[step.idx]});

  28.         // 2.2) 选取更新最好的落点和路径线路
  29.         if ( bestMove === null || tscore > bestScore ) {
  30.             bestScore = tscore;
  31.             bestMove = allMoves[i].moves;
  32.         }
  33.     }

  35.     // 3) 返回最优可行落点, 及其路径线路
  36.     return {score:bestScore, action_moves:bestMove};

  38. }
复制代码

注: 该代码注释, 诠释了决策函数的整个流程。

效果评估：

该AI算法的效果不错, 在演示模式下, 跑了一晚上, 依旧好好的活着。 这也满足了之前想要的需求和功能。

总结：

该算法的权重系数采用了经验值。 当然了, 也可以借助模拟退火算法来学习参数, 不过由于游戏本身的不确定性/偶然性影响, 收敛的效果并非如预期那么好。 有机会再讲讲。

无论怎么样, 该AI可以扮演一个合格的"麻烦制造者", 让游戏充满趣味和挑战性。 勿忘初心, let's go！！！

写在最后：

如果你觉得这篇文章对你有帮助, 请小小打赏下。 其实我想试试, 看看写博客能否给自己带来一点小小的收益。 无论多少, 都是对楼主一种由衷的肯定。

相关阅读：H5版俄罗斯方块游戏开发：需求分析和框架实现

最新评论
暂无评论
参与评论

推广
开测游戏 查看更多
胜利女神：新的希望 角色扮演
上线
发行 : 腾讯游戏   
荒原曙光 角色扮演
上线
研发 : Lingxi Games Inc.   
踏风行 角色扮演
上线
研发 : 祖龙游戏   
遮天世界 放置
限量删档测试
发行 : 腾讯游戏   
王于兴师 模拟
上线
研发 : 多益网络   
洛克人：时空裂隙 横版
上线
研发 : 云畅游戏   
商务合作 查看更多
蘑菇岛
降妖伏魔录
斗道世界
点点传说
编辑推荐 查看更多
三角洲行动 - 黑鹰坠落
开放空间
热血美职篮
The Midnight Walk
【爆款新游】【潜力佳作】分析系列
推广
推广

微信公众号

微博 

头条号

投稿邮箱：news@gameres.com
产品、开测信息邮箱：cp@gameres.com
© 2001-2025 GameRes游资网