H5版俄罗斯⽅块（3）---游戏的AI算法
前⾔:
算是"long long ago"的事了, 某著名互联⽹公司在我校举⾏了⼀次"lengend code"的⽐赛, 其中有⼀题就是"智能俄罗斯⽅块". 本着⼀向⽢做分母, 闪耀分⼦的绿叶精神, 着着实实地打了⼀份酱油. 这次借学习H5的机会, 再来重温下俄罗斯⽅块的AI编写.
本系列的⽂章链接如下:
1).
2).
这些博⽂和代码基本是同步的, 并不确定需求是否会改变, 进度是否搁置, 但期翼⾃⼰能坚持和实现.
演⽰&下载:
该版本依旧较为简陋, 效果如图所⽰:
其为: pan.baidu/s/1sjyY7FJ
下载解压⽬录结构如下所⽰:
h5平台源码下载 点击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.500158825082766
2 3.4181268101392694
3 -3.2178882868487753
4 -9.348695305445199
5 -7.899265427351652
6 -3.3855972247263626
源码解读:
代码⽂件结构如图所⽰:
• tetris_base.js: 公共的数据结构, 包括⽅块定义和⽅块池等
• tetris_ai.js: 具体定义了AI的核⼼算法和数据结构.
• tetris_game.js: 是整个程序的展⽰和驱动.
这边主要讲讲tetris_ai.js这个代码⽂件, ⾥⾯有三个重要的类, MoveGenerator, Evaluator, AIStrategy. MoveGenerator⽤于⽣成各个可⾏落点以及对应的路径线路:
/*
* @brief ⾛法⽣成器
*/
function MoveGenerator() {
}
ate = 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 = w;
var colnum = l;
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;
}
results.push({last:step, moves:tmpMoves});
}
head++;
}
return results;
}
Evaluator类, 则把之前的评估因素整合起来:
function Evaluator() {
}
Evaluator.prototype.evaluate = function(boards) {
}
function PierreDellacherieEvaluator() {
}
PierreDellacherieEvaluator.prototype = new Evaluator();
structor = 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() {
ator = 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 = ate(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
写在最后：
如果你觉得这篇⽂章对你有帮助, 请⼩⼩打赏下. 其实我想试试, 看看写博客能否给⾃⼰带来⼀点⼩⼩的收益. ⽆论多少, 都是对楼主⼀种由衷的肯定.
发表评论