押し引きアルゴリズムの改善(1)

先制リーチを受けた場合、電脳麻将ベタオリのアルゴリズム - koba::blog で「仮実装」したアルゴリズムにしたがい打牌を選択しているが、今回これを改善したい。

まず最初に改善目標を明確にするために、2019年の天鳳鳳凰卓の牌譜から先制リーチを受けた局の最終結果と局収支を集計してみた。

結果 割合 局収支
和了 10.8% +7055
放銃 11.1% -6228
被ツモ 33.6% -2800
横移動 27.1% -27
流局 17.4% -715
平均 -1003

「結果」の意味はそれぞれ以下の通り。

和了
先制リーチを受けたときにすでにダマテン、あるいは回し打ちしてテンパイし、逆転和了した。収支はプラスになる。
放銃
先制リーチ者あるいはその他の者に放銃した。収支はマイナスになる。
被ツモ
先制リーチ者あるいはその他のものがツモ和了した。収支はマイナスになる。
横移動
先制リーチ者とその他の者で横移動した(その他の者の和了もあり)。収支は通常 ±0 だが、追いかけリーチをした場合はマイナスになる。
流局
流局した。収支はノーテン罰符と追いかけリーチの状況による。

現状分析

電脳麻将同士で1000戦の対局を行い、同様の集計を行った結果は以下の通り。対戦方法は デュプリケート麻雀の実装 - koba::blog で実装したデュプリケート方式とした。

結果 割合 局収支
和了 10.2% +6441
放銃 10.5% -6209
被ツモ 32.6% -2690
横移動 26.3% -57
流局 20.4% -827
平均 -1057

これを見ると、天鳳鳳凰卓よりは「引き気味」と言えると思う。局収支は天鳳鳳凰卓平均より若干悪い。

改善内容

現在のアルゴリズムは、

  1. オリる場合に最善となる牌を選ぶ
  2. 押す場合に最善となる牌を選ぶ
  3. 2シャンテン以前なら 1 の牌を切ってオリる
  4. テンパイなら 2 の牌を切って押す
  5. 1シャンテンで 2 の牌が現物かスジか字牌なら押す
  6. 1シャンテンで 2 の牌が無スジなら 1 の牌を切ってオリる

となっているが、これだと「次善の牌を切って回る」ことができない。具体的には以下の手牌で p5 が現物の場合、スジの p8 を切って回る選択をせず、いきなり p0 を切ってベタオリしてしまう。

f:id:xlc:20201220104943j:plain

また序盤のリーチなどで安全牌が1枚もない場合は押すしかないと思うが、この場合でもおよそ安全とは言えない牌を切ってオリてしまう。例えば以下の手牌からは端牌の m1 を切ってオリるが m1 が安全な保証はない。

f:id:xlc:20201220105923p:plain

シャンテン戻しについても考慮が必要である。リーチを受けた局面でシャンテン戻しをする余裕はないと思うので、押す場合でもシャンテン戻しは選択しない方が良さそうだ。

プログラム修正

まず手始めに、

  • 安全牌が1枚もないときは押す
  • 最善手が押せない場合でも次善の手が押せるのならば押す
  • シャンテン戻しを選択しない

から実装することにする。

牌の危険度を調査する

「次善の手」を選択するためには全ての手の危険度を把握する必要がある*1。今までは危険度最低の牌のみ把握していたので、打牌可能な牌*2全てについて危険度を調査し、ハッシュに格納する。

    let anquan, min = Infinity;     // anquan: 危険度最低の牌、min: 最低の危険度
    let weixian;                    // weixian: 各牌の危険度を納めるハッシュ
    if (this._suanpai._lizhi.find(l=>l)) {  // リーチを受けた場合
        weixian = {};
        for (let p of this.get_dapai()) {   // 全ての可能な打牌について以下を行う
            weixian[p] = suan_weixian(p);   // 危険度を調査する
            if (weixian[p] < min) {         // 危険度最低の場合
                min = weixian[p];           // min を更新
                anquan = p;                 // anquan を更新
            }
        }
    }

条件に合わない牌を打牌候補としない

打牌を選ぶループ内で、条件に合わない場合は continue し以降の処理を行わないことで打牌候補から外している。全ての牌が条件に合わない場合は、先に調査済みの「危険度最低の牌」を打牌することになる。

    let dapai = anquan, max = 0, max_tingpai = 0, backtrack = [];
                                    // dapai: 打牌する牌(初期値は危険度最低の牌)
                                    // max: 打牌する牌の評価値
    let paishu = this._suanpai.paishu_all();
    let n_xiangting = Majiang.Util.xiangting(this._shoupai);
                                                    // 手牌のシャンテン数を取得
    for (let p of this.get_dapai()) {   // 全ての可能な打牌について以下を行う
        if (! dapai) dapai = p;
        let shoupai = this._shoupai.clone().dapai(p);   // 打牌後の牌姿を作成
        if (Majiang.Util.xiangting(shoupai) > n_xiangting) {
                                                        // シャンテン戻しの場合
            if (anquan) continue;   // リーチを受けている場合は打牌候補としない
            if (n_xiangting < 2) backtrack.push(p);
            continue;
        }

        let ev = this.eval_shoupai(shoupai, paishu);    // 評価値を計算
        let x  = 1 - paijia(p)/100 + ev;                // 評価値同点の補正

        /* ……… */

        if (min < 6) {          // 打牌可能な牌が全て無スジ以上の危険度なら押す
            if (n_xiangting >  1 && weixian[p] > min) continue;
                                // 2シャンテン以前は最低の危険度の牌でオリる
            if (n_xiangting == 1 && weixian[p] >   5) continue;
                                // 1シャンテンの場合は無スジは押さない
        }

        if (x >= max) {         // 評価値最大の場合
            max = x;            // max を更新する
            dapai = p;          // dapai を更新する
            max_tingpai = n_tingpai;
        }
    }

評価

修正後のプログラムと修正前のプログラム3者で1000戦の対局を行った結果は以下の通り。デュプリケート方式での対戦なのでアルゴリズムの変更だけが結果に影響を及ぼしているはず。

結果 改善前 改善(1)
結果 割合 局収支 割合 局収支
和了 10.2% +6441 11.6% +6468
放銃 10.5% -6209 13.0% -6200
被ツモ 32.6% -2690 31.5% -2703
横移動 26.3% -57 25.6% -68
流局 20.4% -827 18.2% -615
平均 -1057 -1036

押し気味になり放銃するケースが増えているが、和了するケースも増えているため平均の局収支としてはやや改善された。

先制リーチを受けた局面以外も含めた全体の成績は以下の通り。

改善前 改善(1) 改善前 改善(1)
対戦数 1,000 1,000 総局数 10,505 10,465
1位率 .241 .249 和了率 .209 .218
2位率 .251 .244 放銃率 .128 .141
3位率 .254 .255 立直率 .221 .237
4位率 .254 .252 副露率 .346 .349
平均順位 2.52 2.51 平均打点 5,492 5,499

押し気味になったことで和了率、放銃率、立直率がともに増えているが、平均順位はほぼ変動がなかった。この改善をベースに 押し引き表の牌姿は評価値何点? - koba::blog で計算した評価値を考慮して押し引き条件を詳細化していく。

追記 (2020-12-22)

先制リーチを受けた局の局収支の集計に誤りがあったので数値を訂正しました。

*1:危険度は ベタオリのアルゴリズム - koba::blog で定義した値を使用

*2:喰い替えとなる牌は打牌できないし、リーチ後はツモ切りしかできないので手牌が全て打牌可能ではないことに注意