+-
QT5写Tetris之AI机器人玩游戏

背景

使用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