网络知识 娱乐 【参赛经验分享】无需关心算法的渐进式解题思路

【参赛经验分享】无需关心算法的渐进式解题思路

发布: 2023年2月14日 10:17:50

背景介绍

这是一篇 腾讯极客挑战赛第四期：鹅罗斯方块 的参赛经验分享。这个参赛的主要内容大致是玩俄罗斯方块，最后比较得分。和正常俄罗斯方块不太一样的是这个比赛随机种子被固定了，方块落下的顺序是固定的（方块数量也固定了 10000 的上限），而且得分和你消行时场地上存在的方块数量有关。

当方块被消除时，玩家得分。所获得的分数与玩家一次性消除的行数，以及屏幕中已有的格子数有关。“富贵险中求”，在游戏中堆的方块越满，消除得分越高

我从 SJoshua 口中得知这个挑战赛时比赛已经进行到了一半，而且工作日忙于其他事务原本并不打算参加这个比赛。不过在周六傍晚的时候外面突然下起了雨，打乱了我出门逛街的计划，因此我在吃完晚饭后临时起意，参加了这个挑战。而此时距离比赛结束仅剩一天。

本文涉及的完整代码可在这个 GitHub 仓库找到。代码的最后得分为470544分（非比赛得分）。

资料收集准备

使用开发者工具查看源码后发现出题人贴心地给了注释完整的源码，尝试直接修改请求后提交成绩也可以注意到后台是有验证步骤的，因此基本可以断定这不是 CTF 题，是实打实的算法题。

所以这时的目标就变为寻找一个可用俄罗斯方块的算法了，在网上搜索之后可以注意到俄罗斯方块的算法主要有两种，一种是经典的 Pierre Dellacherie 算法，一种基于基于深度搜索的算法。在时间紧迫的情况下各种人工智障算法直接被排除了，只剩下算法更加清晰，复杂度更低的 Pierre Dellacherie 算法。

进一步搜索之后一篇文章 An Improvement on Pierre Dellacherie’s Algorithm 映入了我的眼帘。这篇文章配套的仓库 ielashi/eltetris: Tetris AI 代码清晰，有完整的注释和使用用例，而且游戏的实现和这次的题目及其相似，最重要的是它也是使用 JS 实现的，这意味着我只需要实现鹅罗斯方块和这个 eltetris 之间的接口转换就能完成挑战，无需关心算法，无需关心鹅罗斯方块！

eltetris 的表现

开始实现

我使用的方案是同时运行两个游戏，从鹅罗斯方块中获取新块，转换格式，喂给 eltetris 决策，然后获取这次的决策行动，转换为移动操作，再喂给鹅罗斯方块，循环直达游戏结束。

游戏的主流程如下

// 运行鹅罗斯方块
const game = new Game(canvas, {});
const tetris = game.tetris;
tetris.setStatus("running"); // 设定 tetris 为 running 状态
tetris.initGrids(); // 初始格子

// 运行 eltetris 游戏
const eltetris = new ElTetris(config.gridConfig.col, config.gridConfig.row - 1);

while (true) {
  // 鹅罗斯方块生成新方块
  tetris.initBrick();
  // 把鹅罗斯方块转换为 eltetris 的方块
  const piece = getEltetrisPiece(tetris);
  // 由 eltetris 决策下一步该如何行动
  const { move } = playElTetris(eltetris, piece);
  // 把 eltetris 的行动同步给鹅罗斯方块，保证两个游戏进度一致
  const { topTouched, isRoundLimited } = syncOperate(tetris, move);

  // 判断游戏是否继续
  // 触顶或者超过游戏的最大方块数量后，结束游戏
  if (topTouched || isRoundLimited) {
    const { maxBrickCount, brickCount } = tetris;
    console.error(
      `方块是否触顶：${topTouched}（当前为第 ${brickCount} 个方块），方块数是否超过限制：${isRoundLimited}（最大方块数：${maxBrickCount}）`
    );
    break;
  }
}
// 打印成绩
const { opRecord, score, brickCount } = tetris;
console.log("运行方块数：", brickCount);
console.log("最终得分", score);
game.gameOver();

整个流程就这么简单，只要实现两个游戏中间的亿点点转换细节，就能得到一个自动帮你打比赛的 AI。

不过此时的得分仅有 78130分

玄学调参

到这一步我们查看一下回放，就能发现由于没有调整参数，我们始终在用一种存活的策略玩游戏，方块高度一直在较低的位置，导致每次消行时得到的分数不会太高。因此第一个可以优化的地方就是方块的行高 landing_height 这个参数，在高度较低的时候降低这个参数的权重，然后在高度足够的时候恢复这个参数。由于这个比赛的方块难度加大了，在部分轮次还需要微调参数才能通过，调整完成后代码能够已经能够跑到283970分。

调整前

// eltetris 的默认权重计算函数
ElTetris.prototype.evaluateBoard = function(last_move, board) {
  return GetLandingHeight(last_move, board) * -4.500158825082766 + // <- 需要修改这里
      last_move.rows_removed * 3.4181268101392694 +
      GetRowTransitions(board, this.number_of_columns) * -3.2178882868487753 +
      GetColumnTransitions(board, this.number_of_columns) * -9.348695305445199 +
      GetNumberOfHoles(board, this.number_of_columns) * -7.899265427351652 +
      GetWellSums(board, this.number_of_columns) * -3.3855972247263626;
};

调整后

const clamp = (min = -Infinity, max = Infinity) =>
  getCount() > min && getCount() < max;

let LandingHeightFactor = -4.500158825082766; // 默认参数

ElTetris.prototype.evaluateBoard = function (last_move, board) {
  // 高度低时降低权重
  if (last_move.landing_height < 10) {
    LandingHeightFactor = -4;
  }
  // 在部分轮次需要手动微调参数 防止死亡
  if (clamp(3000, 3500)) {
    LandingHeightFactor = -6;
  }
  if (clamp(4900, 5000)) {
    LandingHeightFactor = -7;
  }
  // ...

  return (
    GetLandingHeight(last_move, board) * LandingHeightFactor +
    last_move.rows_removed * 3.4181268101392694 +
    GetRowTransitions(board, this.number_of_columns) * -3.2178882868487753 +
    GetColumnTransitions(board, this.number_of_columns) * -9.348695305445199 +
    GetNumberOfHoles(board, this.number_of_columns) * -7.899265427351652 +
    GetWellSums(board, this.number_of_columns) * -3.3855972247263626
  );
};

进一步，更进一步

注意：以下优化为比赛结束后进行的优化

在进行玄学调参后发现通过调整参数的方式无法针对性地控制堆叠的高度和消行的时间，而且调参费时费力难以找到最优解。

因此接下来改变思路对 eltetris 的决策函数开刀。原本逻辑为遍历方块落下的全部可能，计算权重，挑选权重最高的一种方式作为目标决策，但是很明显这种决策方式不适合富贵险中求的规则，因此调整策略，在行数较低时优先选用权重高的几种决策中不消行的那个，等把行数堆上去了，再进行消行。使用了这个决策之后，分数提高到了470540分。

不过此时仍有少部分位置需要手动调整行数临界值以免提前死亡，因此后续的优化思路就很明确了。编写存档和读档两个函数，用于保存鹅罗斯方块的状态，设置每隔一百个方块（或更短的间隔）做一次存档，同时把开始消行的临界值提高到满，这样算法就只会进行叠加方块，不会消行，等死亡之后，重新读取最近的一个档，同时降低消行临界值，直到通过这个区域后再提高消行临界值，循环直到通关，分数：??????。

更进一步还可以利用存档读档搜索权重没那么高的决策位置的后续，探索更高的分数。。。

赛后感想

虽然没有拿到名次是时间的缘故，一定是 ，但这场比赛还是玩得很开心，久违地让我的脑子满载运转了一天，也见识到了各路神仙（Nano 等人）的精彩操作，希望以后能来多几场比赛。

相关文章