俄羅斯方塊游戲自動機

《用electron製作俄羅斯方塊游戲》 後續文章，智能程式玩俄羅斯方塊游戲。

背景

前不久用ES6完成了基本的俄羅斯方塊游戲，今天已經完成了一個初步的智能演算法，可以自動玩俄羅斯方塊了，讓自己的想法朝實現更近了一步。

效果圖

第一次運行，消除了1398行，竊喜！

程式結構

主要關註智能演算法，結構簡單化，全部放在了index.js中。

用定時器驅動游戲

function autoPlayClick(){
    isAutoPlay = document.getElementById('autoPlay').checked;
    if(isAutoPlay){
        clearInterval(interval)
        interval = setInterval( autoTick, 1 );        //自動演算法入口
    }else{
        clearInterval(interval)
        interval = setInterval( tick, TICKVAL );      //自動下落入口
    }
    document.getElementById('speedShow').focus();
}

變數定義

模擬手動操作，一個方塊分三步走：旋轉、左或右移、下落到底。

const MOVEOPS = ['moveLeft','moveRight']                //左、右移動定義
var opList = [], bestEva;                               //待操作隊列

class Opration{                                         //操作細節
    constructor(op,num){                    
        this.op = op;                                   //操作方法
        this.num = num;                                 //操作次數
    }
}

class Evaluation{                                      //局面評估函數結果定義
    constructor(r,x,eva){
        this.r = r;                                    //旋轉次數
        this.x = x;                                    //方塊水平位置
        this.eva = eva;                                //評估結果
    }
}

智能演算法調度

function autoTick(){
    if(opList.length == 0){                            //上個方塊已經處理完畢
        getStrategy();                                 //策略演算法，生成下一個方塊的操作方法策略序列
    }else{
        let op = opList.shift();                       //取操作方法
        for(let i=0; i<op.num; i++){                   //執行既定策略
            tetris[op.op]();
            if(op.op == 'moveDown')                    //是下落操作，取下一塊方塊
                generateNext();
        }
    }
}

策略演算法

這是演算法核心，確定每一塊方塊的操作方法。

function getStrategy(){
    let max = 0;                                        //存最優評估值
    tetris.erase();
    let tmp = new Tetris(tetris.shape,tetris.ctx,tetris.x,tetris.y,'rgb(1,1,1,1)','rgb(111,111,111)')                                                //生成用於測試的方塊
    for(let i = 0; i < 4; i++){                        //讓測試方塊與真實方塊保持一致，因為我的每一個方塊生成時都進行了隨機次數的旋轉
        for(let j = 0; j < 4; j++){
            tmp.data[i][j] = tetris.data[i][j];  
        }
    }
    for(let r = 0; r < 4; r++){                    //每個方塊，旋轉四次，分別進行局面評估
        tmp.erase();
        tmp.x = tetris.x;
        tmp.y = tetris.y;
        if(r > 0)
            tmp.rotate();
        while(tmp.moveLeft());                                //從最左測試到右
        while(tmp.moveDown());                                //下落到底
        while(rightOver(tmp)){                                //到右結束這一形態的評估
            let score = evaluate(tmp);                        //局面評估
            if(score > max){                                  //保存最優結果
                max = score;
                bestEva = new Evaluation(r,tmp.x,max)
            }
            if(!tmp.moveRight()){                            //右移失敗
                if(!tmp.moveUp()){                           //上移，繞過障礙
                    max = 1000;                              //上移失敗，說明填補了空洞，方塊就放這
                    bestEva = new Evaluation(r,tmp.x,max)
                    break;
                }
            }else{
                while(tmp.moveDown());                      //右移成功後下落到底
            }
        }
        let score = evaluate(tmp);                          //最後一個位置
        if(score > max){
            max = score;
            bestEva = new Evaluation(r,tmp.x,max)
        }
    }
    tmp.erase();
    // console.log(max)

    opList.push(new Opration('rotate',bestEva.r));        //旋轉操作
    let moveAct = bestEva.x - tetris.x > 0 ? 1 : 0;       //水平位置差轉化成左或右移操作
    let actNum = Math.abs(bestEva.x - tetris.x)
    opList.push(new Opration(MOVEOPS[moveAct],actNum));   //左或右移操作
    opList.push(new Opration('moveDown',1));              //下落操作

}

評估函數

現在只做了幾個基本參數評估，有待優化。更深入的做法是加入機器學習演算法，進行自主反饋學習。

function evaluate(t){
    let ct = t.y;                                                            //調試越大越好
    for(let i = 0; i < 4; i++){                                              //查看每個小方塊的四個鄰居的情況
        for(let j = 0; j < 4; j++){
            if(t.data[i][j]){
                if(t.canSee(t.x +i, t.y + j + 1))                            //下方是空洞
                    ct -= 5;
                for(let k=0; k<4; k++){
                    switch(k){
                        case 0: ct += t.canSee(t.x + i + 1, t.y + j) ? 0 : 1;   //右
                        break;
                        case 1: ct += t.canSee(t.x + i - 1, t.y + j) ? 0 : 1;   //左
                        break;
                        case 2: ct += t.canSee(t.x + i, t.y + j + 1) ? 0 : 1;   //下
                        break;
                        case 3: ct += t.canSee(t.x + i, t.y + j - 1) ? 0 : 1;   //上
                        break;
                    }
                }
            }
        }
    }
    return ct;
}

源代碼：

git clone https://git.oschina.net/zhoutk/Tetris.git
或者：
git clone https://github.com/zhoutk/Tetris

小結

開啟了我的智能演算法學習之路，這還只是一個最簡單的自動程式，都談不上任何智能，但對我來說是一個新方向的開始，加油！