koba::blog

小林聡: プログラマです

麻雀の打牌選択アルゴリズム(5)

麻雀の打牌選択アルゴリズム(4) - koba::blog で説明したアルゴリズムを実装していく。

打点計算ルーチンを追加

Majiang.Player に打点計算するメソッドを追加した。打点の計算には汎用の和了点計算ルーチン Majiang.Util.hule() を使用している。

Majiang.Player.prototype.get_defen = function(shoupai) {

    var menqian = (shoupai._fulou.filter(
                        function(m){return m.match(/[\-\+\=]/)}).length == 0);
                                                        /* 門前か判定する */
    var param = {
        zhuangfeng: this._zhuangfeng,   /* 場風 */
        menfeng:    this._menfeng,      /* 自風 */
        hupai: {
            lizhi:      menqian,        /* 門前の場合はリーチする前提 */
            yifa:       0,
            qianggang:  false,
            lingshang:  false,
            haidi:      0,
            tianhu:     0
        },
        baopai:     this._baopai,       /* ドラ */
        fubaopai:   [],
        jicun:      { changbang: this._changbang, lizhibang: this._lizhibang }
    };
    
    var hule = Majiang.Util.hule(shoupai, null, param); /* ツモ和了として計算 */
    
    return hule.defen;
}

先読みで使用するため任意の手牌を入力値とする必要がある*1が、場風、自風、ドラ、供託*2は先読み中に不変なので「現在」のものを使用している。

打牌候補取得メソッドを共通化

Majiang.Player の打牌候補取得メソッド get_dapai() は「現在」の手牌を元にしているので、任意の手牌を入力とできるよう共通関数化した。*3

function get_dapai(shoupai) {

    /* Majiang.Player.prototype.get_dapai を元に、任意の手牌を入力とできるよう
       修正 */
}

Majiang.Player.prototype.get_dapai = function() {
 
    if (this._lizhi[this._menfeng]) return [ this._shoupai._zimo ];
 
    return get_dapai(this._shoupai);    /* 共通化した get_dapai() を呼出す */
}

現在の残り牌数を一括して連想配列に出力する機能を追加

Majiang.SuanPai のメソッド paishu() もやはり「現在」の残り牌数を返すので、これを連想配列で一括取得し、先読みの過程ではこれを元に残牌数を管理することにする。

Majiang.SuanPai.prototype.suan_paishu_all = function() {

    var paishu = {};
    for (var s of ['m','p','s','z']) {
        var nn = (s == 'z') ? [1,2,3,4,5,6,7] : [0,1,2,3,4,5,6,7,8,9];
        for (var n of nn) {
            if (s != 'z' && n == 5)
                    /* 五萬、五筒、五索は赤牌を含まない実数とする */
                    paishu[s+n] = this._paishu[s][n] - this._paishu[s][0];
            else    paishu[s+n] = this._paishu[s][n];
        }
    }
    return paishu;
}

将来的にはこの部分に「山読み」を実装したい。

牌姿の評価関数を追加

牌姿の評価関数を追加する。入力は手牌と、先ほど得た残牌数の一覧。

Majiang.Player.prototype.eval_shoupai = function(shoupai, paishu) {

    function add_hongpai(pai) {
        var new_pai = [];
        for (var p of pai) {
            if (p[0] != 'z' && p[1] == '5') new_pai.push(p.replace(/5/,'0'));
            new_pai.push(p);
        }
        return new_pai;
    }
    
    var n_xiangting = Majiang.Util.xiangting(shoupai);
    
    if (n_xiangting == -1) {
        /* 1. 牌姿が和了形(向聴数 = -1)の場合 (手牌が14枚)
              和了打点を評価値とする。 */
        return this.get_defen(shoupai);
    }
    
    if (shoupai._zimo) {
        /* 3. 牌姿が打牌可能な状態(ツモの後、副露の後)の場合 (手牌が14枚)
              向聴数が戻らない打牌を行った後の牌姿の評価値のうち最大のものを、
              その牌姿の評価値とする。 */
        var max = 0;
        for (var p of get_dapai(shoupai)) {
            var new_shoupai = shoupai.clone();
            new_shoupai.dapai(p);
            if (Majiang.Util.xiangting(new_shoupai) > n_xiangting) continue;
            
            var r = this.eval_shoupai(new_shoupai, paishu);
            if (r > max) max = r;
        }
        return max;
    }
    
    if (n_xiangting < 3) {
        /* 2. 牌姿が打牌後の場合 (手牌が13枚、テンパイもこの形)
              向聴数の進む牌をツモった場合の評価値 x その牌の枚数 の総和を
              その牌姿の評価値とする。 */    
        var r = 0;
        for (var p of add_hongpai(Majiang.Util.tingpai(shoupai))) {
            if (paishu[p] == 0) continue;
            
            var new_shoupai = shoupai.clone();
            new_shoupai.zimo(p);

            paishu[p]--;
            var ev = this.eval_shoupai(new_shoupai, paishu);
            paishu[p]++;
            
            r += ev * paishu[p];
        }
        return r;
    }
    else {
        /* 3向聴以前の場合は今までのアルゴリズムで評価 */
        var r = 0;
        for (var p of add_hongpai(this.tingpai(shoupai))) {
            if (paishu[p.substr(0,2)] == 0) continue;
            
            r += paishu[p.substr(0,2)] * (p[2] == '+' ? 4 :
                                          p[2] == '-' ? 2 : 1);
        }
        return r;
    }
}

打点の計算の際には赤牌を区別する必要があるが、従来の有効牌*4一覧取得ルーチンは赤牌を返さないため、赤牌を追加する関数 add_hongpai() を内部で使用している。*5

打牌の選択に牌姿の評価値を使うようにする

Majiang.Player のメソッド select_dapai() から牌姿の評価関数を呼出すようにする。

Majiang.Player.prototype.select_dapai = function() {

    /* ………… */

    /* 現在の向聴数を取得する */
    var n_xiangting = Majiang.Util.xiangting(this._shoupai);

    /* ………… */

    /* 現在の残り牌数を一括して取得する */
    var paishu = this._suanpai.suan_paishu_all();
 
    /* ………… */

    for (var p of this.get_dapai()) {
        var new_shoupai = this._shoupai.clone();
        new_shoupai.dapai(p);
        if (Majiang.Util.xiangting(new_shoupai) > n_xiangting) continue;

        /* 牌姿の評価値を得る */
        var x = 1 - this._suanpai.paijia(p)/100
              + this.eval_shoupai(new_shoupai, paishu);
        
        if (x >= max) {
            max = x;
            dapai = p;
        }
    }
 
    /* ………… */

    return dapai;
}

先読みを行うため 麻雀の副露判断アルゴリズム(2) - koba::blog で導入した鳴き考慮の向聴数計算ルーチンは使わず、汎用の向聴数計算ルーチン Majiang.Util.xiangting() に戻した。

評価値をキャッシュし計算速度を向上させる

ここまでの改良で「何切る問題」の正答率はかなり上がったが、2向聴から計算すると2秒以上かかる場合がある。ブラウザ上のJavaScriptとしては重すぎるので、牌姿の評価値をキャッシュし同じ牌姿を二度評価しないよう修正した。

Majiang.Player.prototype.select_dapai = function() {

    /* ………… */

    var dapai, max = 0;
    var paishu = this._suanpai.suan_paishu_all();
    this._eval_cache = {};      // キャッシュを初期化する

    /* ………… */
 
    return dapai;
}

Majiang.Player.prototype.eval_shoupai = function(shoupai, paishu) {

    /* ………… */

    /* キャッシュに評価値がある場合はそれを返す */
    var paistr = shoupai.toString();
    if (this._eval_cache[paistr]) return this._eval_cache[paistr];

    var rv;     // return を一ヶ所にまとめるために返り値を格納する変数

    if (n_xiangting == -1) {
        rv = this.get_defen(shoupai);   // return せず rv に評価値を格納
    }
    else if (shoupai._zimo) {
        /* ………… */
        rv = max;                       // return せず rv に評価値を格納
    }
    else if (n_xiangting < 3) {
        /* ………… */
        rv = r;                         // return せず rv に評価値を格納
    }
    else {
        /* ………… */
        rv = r;                         // return せず rv に評価値を格納
    }

    this._eval_cache[paistr] = rv;      // 評価値をキャッシュする
    return rv;
}

対戦結果

上記の修正を加えた思考ルーチン(打点考慮)と ver.0.8.8 の思考ルーチンを対戦させてみた。

ver.0.8.8打点考慮 ver.0.8.8打点考慮
対戦数 1,000 1,000 総局数 10,674 10,605
1位率 .244 .262 和了 .199 .193
2位率 .244 .274 放銃率 .118 .112
3位率 .249 .214 立直率 .248 .252
4位率 .263 .250 副露率 .269 .252
平均順位 2.53 2.45 平均打点 5,290 5,955

和了ver.0.8.8打点考慮 和了ver.0.8.8打点考慮
ドラ 49.13% 52.35% 断幺九 22.32% 18.81%
赤ドラ 45.07% 47.85% 一盃口 2.74% 3.97%
裏ドラ 23.22% 23.80% 三色同順 1.56% 3.62%
立直 52.52% 57.20% 一気通貫 0.24% 0.73%
一発 10.43% 11.75% 七対子 3.96% 4.06%
門前清自摸 26.52% 30.12% 対々和 0.14% 0.44%
翻牌 36.67% 36.14% 混一色 0.80% 1.03%
平和 13.50% 16.75% 清一色 0.00% 0.10%

和了役の出現率を見ると期待通りに手役指向の打ち筋にはなったが、その分門前指向も強くなり、和了率、副露率が下がっている。このため平均順位は思ったほど向上しなかった。

*1:和了可否判断では「現在の」手牌から判断するため手牌が入力値になっていない

*2:打点には反映していない

*3:get_dapai()、get_chi_mianzi()、get_peng_mianzi() は Majiang.Shoupai のメソッドに変更すべきかもしれないな

*4:ここでは向聴数を進める牌のこと

*5:JavaScriptredoがあればこんな関数は要らないんだけどな