第6-7课：Pierre Dellacherie 算法与俄罗斯方块游戏

编写一个俄罗斯方块游戏，涉及到键盘控制、定时器、UI 和复杂数据结构定义和使用，非常具有挑战性，很多编程爱好者自己也编写过俄罗斯方块游戏，该游戏有自己的 AI 算法，基本原理还是状态搜索和评估，这一课我们介绍著名的估值算法、Pierre Dellacherie 算法。当然，建立游戏的数据模型仍然是我们的重点。

俄罗斯方块游戏 AI 的原理

在游戏过程中，当一个板块下落的时候，旁边还会提示下一个将要落下的板块形状，熟练的玩家会利用下一个板块的形状评估现在要如何摆放当前的板块。玩家玩俄罗斯方块游戏的目的是得更高的分数和玩更长时间，但是一般俄罗斯方块游戏的程序设计都会随着游戏的进行慢慢提高难度，比如加快板块的下落速度，随机增加一些带空格的行等。

在探讨计算机的俄罗斯方块游戏智能算法之前，先研究一下人类玩家玩这个游戏的一些基本策略。玩家玩这个游戏，首先要能够玩尽量长的时间，这就要求要尽可能的消除行，避免累积高度太高；其次是尽量多得分，利用规则消除加分的特点，尽量一次消除多行。

在遇到板块形状很难处理的情况，要选择产生空格子少的摆放方法，尽量避免出现“空洞”。在很多情况下，当一个板块可以摆放在多个位置的时候，玩家需要根据自己的经验选择一个对下一步操作最有利的位置摆放这个板块，这就涉及到一个局面评估的问题。

对于此类问题通常的做法是设计一个局面评价函数，对各种可能的局面进行评估，根据评估结果选出最好的一个局面进行实施，那么要评估的局面是什么呢？如果我们把游戏区域这 10 × 20 个小格子视为“棋盘”的话，所谓的局面就是一个板块摆放在某个位置后这个“棋盘”的状态；如果一个板块有多个位置可以摆放࿰