koba::blog

小林聡: プログラマです

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

麻雀の打牌選択アルゴリズム(6) - koba::blog でシャンテン戻しを仮実装したが、問題が残っている。

m4m5m6m6p5p8p8p9p9p9s4s0s6 m3
のテンパイから m6 を切って1向聴に戻してしまう。また
m1m2p1p9s1s9z1z2z3z4z5z6z7 m1
国士無双テンパイからも m1 をツモ切りしてしまう。今回はこの問題を修正する。

状況分析

m4m5m6m6p5p8p8p9p9p9s4s0s6 m3

からテンパイを維持する打牌とその評価値は以下の通り。

No打牌 聴牌待ち枚数打点 評価値
1p5m3m4m5m6m6p8p8p9p9p9s4s0s6m6 2 52001,733.33
p8 2 5200

一方 m6 を切って1向聴戻しとした場合の聴牌形とその評価値は以下となる。

Noツモ 枚数打牌 聴牌待ち枚数打点 評価値
1m1 4 p5m1m3m4m5m6p8p8p9p9p9s4s0s6m2 4 52001,733.33
2m2 4 p5m2m3m4m5m6p8p8p9p9p9s4s0s6m1 4 40003,666.67
m4 3 4000
m7 4 4000
3m3 3 p5m3m3m4m5m6p8p8p9p9p9s4s0s6m3 2 52001,733.33
p8 2 5200
4m4 3 p5m3m4m4m5m6p8p8p9p9p9s4s0s6m2 4 40002,866.67
m0 1 8000
m5 2 5200
5m0 1 p5m3m4m0m5m6p8p8p9p9p9s4s0s6m4 3 80004,633.33
m7 4 7900
m5 2 p5m3m4m5m5m6p8p8p9p9p9s4s0s6m4 3 52002,633.33
m7 4 4000
6m6 2 p5m3m4m5m6m6p8p8p9p9p9s4s0s6m6 1 52001,300.00
p8 2 5200
7m7 4 p5m3m4m5m6m7p8p8p9p9p9s4s0s6m2 4 40003,991.67
m0 1 7900
m5 2 4000
m8 4 4000
8m8 4 p5m3m4m5m6m8p8p8p9p9p9s4s0s6m7 4 52001,733.33
9p3 4 m3m4m5m6p3p5p8p8p9p9p9s4s0s6p4 4 52001,733.33
10p4 4 m3m4m5m6p4p5p8p8p9p9p9s4s0s6p3 4 40004,000.00
p6 4 8000
11p0 1 m3m4m5m6p0p5p8p8p9p9p9s4s0s6p5 2 80002,666.67
p8 2 8000
p5 2 m3m4m5m6p5p5p8p8p9p9p9s4s0s6p0 1 80001,966.67
p5 1 5200
p8 2 5200
12p6 4 m3m4m5m6p5p6p8p8p9p9p9s4s0s6p4 4 80004,000.00
p7 4 4000
13p7 4 m3m4m5m6p5p7p8p8p9p9p9s4s0s6p6 4 52001,733.33
14p8 2 p5m3m4m5m6p8p8p8p9p9p9s4s0s6m3 3 52002,166.67
m6 2 5200

14種48枚で再度テンパイするが、素直にテンパイをとった場合の評価値を超えるケースは、No.2、4、5、7、10、11、12、14の8種27枚だけであり、評価値が2倍以上になるケースに限るとNo.2、5*1、7、10、12の5種17枚まで減ってしまう。

m1m2p1p9s1s9z1z2z3z4z5z6z7 m1
の場合、打 m2 とすると13種(全ての幺九牌)38枚で再度テンパイするが、素直にテンパイをとった場合の評価値を超えるパターンは m9 ツモの1種4枚*2だけであり、m1 引き戻し以外の全てのケースにおいてフリテンとなってしまう。

上記から、シャンテン戻しに関して以下のようにプログラム修正すればよいと思われる。

  • 評価値が2倍以上とならないケースは評価しない
  • フリテンとなったケースは評価しない

あわせて以下の修正も行う。

  • シャンテン戻しの打牌を引き戻したケースも評価しない

改善プログラム

シャンテン戻しを評価するメソッドを eval_backtrack() として独立させる。

var width = [12, 12*6, 12*6*3];     // 評価値正規化の係数を共通化する

/* 有効牌に赤牌を加える関数も共通化する */
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;
}

/* ………… */

/*
 *  シャンテン戻し専用の評価値計算ルーチン
 */
Majiang.Player.prototype.eval_backtrack = function(shoupai, paishu, min, dapai) {

    var n_xiangting = Majiang.Util.xiangting(shoupai);
    
    var r = 0;
    for (var p of add_hongpai(Majiang.Util.tingpai(shoupai))) {
        if (p == dapai)     continue;   // シャンテン戻しの打牌を引き戻した
                                        // ケースは評価しない
        if (paishu[p] == 0) continue;
            
        var new_shoupai = shoupai.clone();
        new_shoupai.zimo(p);

        paishu[p]--;
        var ev = this.eval_shoupai(new_shoupai, paishu, dapai);
        paishu[p]++;
        
        if (ev < min * 2) continue;     // 評価値が2倍以上とならないケースは
                                        // 評価しない
        r += ev * paishu[p];
    }
    return r / width[n_xiangting];
}

評価値計算メソッド eval_shoupai() のパラメータにシャンテン戻しの際に行った打牌を加える。

Majiang.Player.prototype.eval_shoupai = function(shoupai, paishu, dapai) {
                                                // パラメータ dapai を追加
    /* ………… */

    if (n_xiangting == -1) {
        rv = this.get_defen(shoupai);
    }
    else if (shoupai._zimo) {

        /* ………… */

            var r = this.eval_shoupai(new_shoupai, paishu, dapai);
                                                // パラメータ dapai を追加
        /* ………… */
    }
    else if (n_xiangting < 3) {
    
        var r = 0;
        for (var p of add_hongpai(Majiang.Util.tingpai(shoupai))) {
            if (p == dapai)     return 0;   // フリテンとなったケースは評価
                                            // しない
            if (paishu[p] == 0) continue;
            
            var new_shoupai = shoupai.clone();
            new_shoupai.zimo(p);

            paishu[p]--;
            var ev = this.eval_shoupai(new_shoupai, paishu, dapai);
                                                // パラメータ dapai を追加
            paishu[p]++;
            
            r += ev * paishu[p];
        }
        rv = r / width[n_xiangting];
    }
    else {

        /* ………… */
    }

    /* ………… */
}

打牌を選択するメソッド select_dapai() では、まず向聴数を戻さない打牌について検討し、その後シャンテン戻しを検討するよう修正する。

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

    /* ………… */

    var dapai, max = 0, backtrack = [];     // シャンテン戻しの打牌を保存する
                                            // 変数 backtrack を追加
    var paishu = this._suanpai.suan_paishu_all();
    this._eval_cache = {};

    /* まず向聴数を戻さない打牌について検討する */
    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) {
            if (n_xiangting < 2) backtrack.push(p); // シャンテン戻しとなる打牌
                                                    // を保存する
            continue;
        }

        var x = 1 - this._suanpai.paijia(p)/100
              + this.eval_shoupai(new_shoupai, paishu);

        if (x >= max) {
            max = x;
            dapai = p;
        }
    }

    var tmp_max = max;  // 向聴数を戻さない最良の評価値を tmp_max とする

    /* その後シャンテン戻しを検討する */
    for (var p of backtrack) {
        var new_shoupai = this._shoupai.clone();
        new_shoupai.dapai(p);

        var x = 1 - this._suanpai.paijia(p)/100
              + this.eval_backtrack(new_shoupai, paishu, tmp_max, p);
                        // シャンテン戻し専用の評価値計算ルーチンを呼び出す
        if (x >= max) {
            max = x;
            dapai = p;
        }
    }
 
    /* ………… */

    return dapai;
}

枝刈りによる計算速度向上

今回の修正でシャンテン戻しについても妥当と思われる打牌が選択できるようになったが、打牌に1秒以上かかるケースが出てきた。原因は向聴数が戻る打牌についても計算する分の計算量が増えたためであるが、向聴数を戻す打牌はたいていは悪手であり、すべてについて計算するのは時間の無駄である。

そこで、以下の条件で「枝刈り」を行うことにした。

  • 各々の打牌について、向聴数を進める「有効牌」の枚数を算出する
  • 向聴数を戻さない打牌を検討したときに最良の評価値となった打牌について、その打牌を行った場合の「有効牌」の枚数を「最良ケースの待ちの広さ」とする
  • シャンテン戻しを検討する際に、各々の打牌の「有効牌」の枚数が、「最良ケースの待ちの広さ」x 6 以下の場合は、打牌候補とせず、評価値も計算しない。

具体的な変更は以下の通り

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

    /* ………… */

    var dapai, max = 0, max_tingpai = 0, backtrack = [];
    var paishu = this._suanpai.suan_paishu_all();
    this._eval_cache = {};
 
    /* まず向聴数を戻さない打牌について検討する */
    for (var p of this.get_dapai()) {

        /* ………… */
        
        /* 向聴数を進める「有効牌」の枚数を算出する */
        var n_tingpai = 0;
        for (var tp of Majiang.Util.tingpai(new_shoupai)) {
            n_tingpai += paishu[tp];
        }
 
        if (x >= max) {
            max = x;
            dapai = p;
            max_tingpai = n_tingpai;    // 最良ケースの待ちの広さ
        }
    }

    var tmp_max = max;
 
    /* その後シャンテン戻しを検討する */
    for (var p of backtrack) {

        /* ………… */

        /* 向聴数を進める「有効牌」の枚数を算出する */
        var n_tingpai = 0;
        for (var tp of Majiang.Util.tingpai(new_shoupai)) {
            n_tingpai += paishu[tp];
        }
        /*「最良ケースの待ちの広さ」x 6 以下の場合は、打牌候補とせず、
           評価値も計算しない */
        if (n_tingpai < max_tingpai * 6) continue;

        /* ………… */
    }
 
    /* ………… */
}

対戦結果

シャンテン戻しを考慮した思考ルーチン(向聴戻し)と ver.0.8.8 の思考ルーチンを対戦させた結果は以下の通り。

ver.0.8.8打点考慮 向聴戻し ver.0.8.8打点考慮 向聴戻し
対戦数 1,000 1,000 1,000 総局数 10,674 10,605 10,609
1位率 .244 .262 .232 和了 .199 .193 .190
2位率 .244 .274 .272 放銃率 .118 .112 .118
3位率 .249 .214 .256 立直率 .248 .252 .246
4位率 .263 .250 .240 副露率 .269 .252 .253
平均順位 2.53 2.45 2.50 平均打点 5,290 5,955 5,764

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

残念ながら成績は逆に下降してしまった。門前指向が強くなっていることが原因と思われるので、次回改善を考える。

*1:m0 ツモの場合

*2:この場合国士無双13面待ちとなり、電脳麻将ではダブル役満としている