前言:
算是"long long ago"的事了, 某著名互联网公司在我校举行了一次"lengend code"的比赛, 其中有一题就是"智能俄罗斯方块". 本着一向甘做分母, 闪耀分子的绿叶精神, 着着实实地打了一份酱油. 这次借学习H5的机会, 再来重温下俄罗斯方块的AI编写. 本系列的文章链接如下: 1). 2). 这些博文和代码基本是同步的, 并不确定需求是否会改变, 进度是否搁置, 但期翼自己能坚持和实现.演示&下载:
该版本依旧较为简陋, 效果如图所示:
其为: http://pan.baidu.com/s/1sjyY7FJ 下载解压目录结构如下所示: 
点击tetris.html, 在浏览器上运行(由于HTML5程序, 最好在Chrome/Firefox上运行). 算法分析:
核心算法参考了如下博文: • • 本程序也采用改进的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.5001588250827662 3.41812681013926943 -3.21788828684877534 -9.3486953054451995 -7.8992654273516526 -3.3855972247263626
源码解读:
代码文件结构如图所示:
• tetris_base.js: 公共的数据结构, 包括方块定义和方块池等 • tetris_ai.js: 具体定义了AI的核心算法和数据结构. • tetris_game.js: 是整个程序的展示和驱动. 这边主要讲讲tetris_ai.js这个代码文件, 里面有三个重要的类, MoveGenerator, Evaluator, AIStrategy. MoveGenerator用于生成各个可行落点以及对应的路径线路: /* * @brief 走法生成器 */function MoveGenerator() {} MoveGenerator.prototype.generate = function(tetrisUnit, shape) { var keymapFunc = function(x, y, idx) { return "" + x + ":" + y + ":" + idx; } var moveMapFunc = function(step) { return {x:step.x, y:step.y, idx:step.idx}; } var results = []; var boards = tetrisUnit.boards; var rownum = tetrisUnit.row; var colnum = tetrisUnit.col; var shapeArrs = shape.shapes; var occupy = {} var actionQueues = []; actionQueues.push({x:shape.x, y:shape.y, idx:shape.idx, prev:-1}); occupy[keymapFunc(shape.x, shape.y, shape.idx)] = true; var head = 0; while ( head < actionQueues.length ) { var step = actionQueues[head]; // 1). 向左移动一步 var tx = step.x - 1; var ty = step.y; var tidx = step.idx; if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) { var key = keymapFunc(tx, ty, tidx); if ( !occupy.hasOwnProperty(key) ) { actionQueues.push({x:tx, y:ty, idx:tidx, prev:head}); occupy[key] = true; } } // 2). 向右移动一步 tx = step.x + 1; ty = step.y; tidx = step.idx; if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) { var key = keymapFunc(tx, ty, tidx); if ( !occupy.hasOwnProperty(key) ) { actionQueues.push({x:tx, y:ty, idx:tidx, prev:head}); occupy[key] = true; } } // 3). 旋转一步 tx = step.x; ty = step.y; tidx = (step.idx + 1) % 4; if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) { var key = keymapFunc(tx, ty, tidx); if ( !occupy.hasOwnProperty(key) ) { actionQueues.push({x:tx, y:ty, idx:tidx, prev:head}); occupy[key] = true; } } // 4). 向下移动一步 tx = step.x; ty = step.y + 1; tidx = step.idx; if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) { var key = keymapFunc(tx, ty, tidx); if ( !occupy.hasOwnProperty(key) ) { actionQueues.push({x:tx, y:ty, idx:tidx, prev:head}); occupy[key] = true; } } else { // *) 若不能向下了, 则为方块的一个终结节点. var tmpMoves = []; tmpMoves.push(moveMapFunc(step)); var tprev = step.prev; while ( tprev != -1 ) { tmpMoves.push(moveMapFunc(actionQueues[tprev])); tprev = actionQueues[tprev].prev; } tmpMoves.reverse(); results.push({last:step, moves:tmpMoves}); } head++; } return results; } Evaluator类, 则把之前的评估因素整合起来:
function Evaluator() {} Evaluator.prototype.evaluate = function(boards) {} function PierreDellacherieEvaluator() {} PierreDellacherieEvaluator.prototype = new Evaluator();PierreDellacherieEvaluator.prototype.constructor = PierreDellacherieEvaluator; PierreDellacherieEvaluator.prototype.evaluate = function(boards, shape) { return (-4.500158825082766) * landingHeight(boards, shape) // 下落高度 + (3.4181268101392694) * rowsEliminated(boards, shape) // 消行个数 + (-3.2178882868487753) * rowTransitions(boards) // 行变换 + (-9.348695305445199) * colTransitions(boards) // 列变化 + (-7.899265427351652) * emptyHoles(boards) // 空洞个数 + (-3.3855972247263626) * wellNums(boards); // 井数} AIStrategy整合了落地生成器和评估函数, 用于具体决策最优的那个落地点, 以及行动路线.
function AIStrategy() { this.generator = new MoveGenerator(); this.evalutor = new PierreDellacherieEvaluator();} /* * @brief 作出最优的策略 * @return {dest:{x:{x}, y:{y}, idx:{idx}}, [{action_list}]} */ AIStrategy.prototype.makeBestDecision = function(tetrisUnit, shape) { var bestMove = null; var bestScore = -1000000; // 1) 生成所有可行的落点, 以及对应的路径线路 var allMoves = this.generator.generate(tetrisUnit, shape); // 2) 遍历每个可行的落点, 选取最优的局面落点 for ( var i = 0; i < allMoves.length; i++ ) { var step = allMoves[i].last; var shapeArrs = shape.shapes; var bkBoards = tetrisUnit.applyAction2Data(step.x, step.y, shapeArrs[step.idx]); // 2.1) 对每个潜在局面进行评估 var tscore = this.evalutor.evaluate(bkBoards, {x:step.x, y:step.y, shapeArr:shapeArrs[step.idx]}); // 2.2) 选取更新最好的落点和路径线路 if ( bestMove === null || tscore > bestScore ) { bestScore = tscore; bestMove = allMoves[i].moves; } } // 3) 返回最优可行落点, 及其路径线路 return {score:bestScore, action_moves:bestMove}; } 注: 该代码注释, 诠释了决策函数的整个流程.
效果评估:
该AI算法的效果不错, 在演示模式下, 跑了一晚上, 依旧好好的活着. 这也满足了之前想要的需求和功能.总结:
该算法的权重系数采用了经验值. 当然了, 也可以借助模拟退火算法来学习参数, 不过由于游戏本身的不确定性/偶然性影响, 收敛的效果并非如预期那么好. 有机会再讲讲. 无论怎么样, 该AI可以扮演一个合格的"麻烦制造者", 让游戏充满趣味和挑战性. 勿忘初心, let's go!!!