背景
使用Qt5.12.9的QGraphicsItem来实现俄罗斯方块,使用简单的评估函数,实现AI机器人玩俄罗斯方块游戏。这是AI机器人的第一步,这个算法很简单,但很有效,大多数情况能消5百层以上,最近的为数不多的测试中,最高纪录已经消了超过2500层。在这个基础上,可以方便的积累原始数据,我希望能抽取模式,进行模式识别及至机器学习。
思路
在手动游戏基础上进行改造,借鉴回放的经验,只需要加入一个评估算法,为每一个新方块找出一个放置的姿态(旋转次数)和最终位置坐标就可以了。我的算法设计也很简单,就是为每一个方块穷举其放置方法,使用一个紧密程度的评估算法进行评分,取出最高分的操作,若有相同得分的操作,用随机数二一添做五。
效果图
关键代码分析
流程控制
界面操作控制变量,做到随时可以在手动与自动两种模式之间进行切换。
if (isAutoRunning) { //自动模式
autoProcessCurBlock(); //处理当前方块,使用评估函数确定方块的最终姿态与位置
block->relocate(curPos); //放置
block->setBlockNotActive(); //固定方块
generateNextBlock(); //取下一个方块,游戏继续
}else //手动模式
this->moveBlockDown();
...
方块放置评分函数
我的设计思想很直观,俄罗斯方块就是要尽量紧密的堆积在一起,所以对每一个组成方块的block都检测一个它周围的四个位置,看是否有block(包括边界)存在,若有就加1分,没有不加分。这块的加分,并没有区别组成方块自身的block和外界的block,因为每个方块都是与自己进行比较,所以区分与不区分效果是一样的。起始分由深度确定,越深我认为效果越好。另个,block的垂直下方最好不要有空洞,若有会减分。
int Game::evaluate(Tetris* t)
{
QPoint pos = t->getPos();
int ct = pos.y(); //深度为基础分
int cct = t->cleanCount();
if (cct > 1) //能消层,加分
ct += 10 * (cct - 1);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (t->data[i][j]) {
ct += t->hasTetrisBlock(pos.x() + j + 1, pos.y() + i) ? 1 : 0; //检测block右边的位置
ct += t->hasTetrisBlock(pos.x() + j - 1, pos.y() + i) ? 1 : 0; //检测block左边的位置
ct += t->hasTetrisBlock(pos.x() + j, pos.y() + i + 1) ? 1 : 0; //检测block下方的位置
ct += t->hasTetrisBlock(pos.x() + j, pos.y() + i - 1) ? 1 : 0; //检测block上方的位置
if (i == 3 || t->data[i + 1][j] == 0) {
if (!t->hasTetrisBlock(pos.x() + j, pos.y() + i + 1)) { //block下方的紧临空洞
ct -= 4;
}
else {
int k = 2;
while (pos.y() + i + k <= 19) {
if (!t->hasTetrisBlock(pos.x(), pos.y() + i + k)) { //block下方的非紧临空洞
ct -= 1;
break;
}
k++;
}
}
}
}
}
}
return ct;
}
穷举方块的所有放置方式
一个方块最多只有四种姿态,把方块的每一种姿态都从左到右moveDownEnd一次,进行评分,取得分最高的方案。
void Game::autoProcessCurBlock()
{
int max = 0;
QPoint initPos = block->getPos();
Tetris* tmp = new Tetris(initPos, block->getShape(), -1); //构造当前方块的替身,blockType为-1,这种方块不会显示
int rotateCt = block->getRotateNum(); //同步替身初始姿态
for (int k = 0; k < rotateCt; k++)
tmp->rotate();
rotateCt = 0; //用于保存方块的最终姿态
for (int r = 0; r < 4; r++) { //四种姿态遍历,其实可以优化,有的方块不需要四次
if (r > 0) {
tmp->relocate(initPos); //注意,旋转要在方块进入游戏界面的地方旋转,不然可能旋转不成功
tmp->rotate();
}
while (tmp->moveLeft()); //从最左边开始
do {
tmp->moveDownEnd();
tmp->setBlockNotActive(); //固定方块,以便进行评分
int score = evaluate(tmp); //评分
if (score > max) { //找到当前最优方案
max = score;
curPos = tmp->getPos();
rotateCt = r;
}
else if (score == max) { //出现相等评分,随机取
if (qrand() % 2 == 1) {
curPos = tmp->getPos();
rotateCt = r;
}
}
//initPos.setX(tmp->getPos().x());
tmp->relocate(QPoint(tmp->getPos().x(), initPos.y())); //返回到游戏空间上方
tmp->setBlockTest(); //方块恢复到测试状态
} while (tmp->moveRight()); //方块右移,直到不能移动
}
delete tmp; //销毁测试方块,突然想到这块可以优化,只需要建七个方块就好,这样就不用不断的创建和销毁了
for (int k = 0; k < rotateCt; k++)
block->rotate();
}
下一步的设想
使用python重新实现所有功能,也不再用Qt,就用python自带的tkinter就好。把重点放在模式提取,让AI自动玩游戏,写个算法,提取优秀的操作模式。然后使用模式匹配或机器学习算法来优化AI。现在还没有具体的想法,只有这么个大概的设想。
源代码及运行方法
项目采用cmake组织,请安装cmake3.10以上版本。下面脚本是windows下基于MSVC的,其它操作系统上基本类似,或者使用qtcreator打开进行操作。
cmake -A win32 -Bbuild .
cd build
cmake --build . --config Release
注:本项目采用方案能跨平台运行,已经适配过windows,linux,mac。
源代码:
https://gitee.com/zhoutk/qtetris.git
或
https://gitee.com/zhoutk/qtdemo/tree/master/tetrisGraphicsItem
或
https://github.com/zhoutk/qtDemo/tree/master/tetrisGraphicsItem