« 被先制リーチ時収支 | トップページ | 根本が間違ってるのかも »

2008/02/17

ゲームの木と、鳴きへの変化を考慮した評価関数

まほ公さんの指摘のとおりで、現行のメインで利用している期待値型評価関数は評価点を算出するときに、鳴きへの移行を考慮していない。これを修正する方法については、実はすでに、プランがあることはあります。
どういう風な仕組みなのか、ゲームの木で将棋の場合も交えて紹介します。


将棋の場合
まず、将棋のような決定完全情報2人零和交互ゲームの場合のゲームの木ですが、以下の図のようになります。
Gt_shogi
ゲームAIの初歩の初歩、いわゆるMin-Max法ってやつです。
これだと、後手番は評価値が一番低い値、先手番は評価値が一番高い値をバックトラックで選択していくわけで、
選択したけっか、現在の局面の評価値を算出するためのノードのパスは終端まで1つのパスでつながり枝分かれがなくなりますし、局面の評価値は終端ノードの評価がそのまま使えることになります。

これだと、αβ法などのよく知られている方法で枝狩りがしやすいのですし、局面評価値も割りと雑でもなんとかなるのです。


麻雀の場合
ところが、不確定要素の入る麻雀の場合そういった手はつかえません。
以下は一人麻雀の評価値を出すためのゲームの木です。
Gt_nakinasi
Min-Max法ではなく、Max-Prob法(そんな呼び名無いと思いますが、今私が勝手に命名した)になるわけです。

つまり、「打牌」については最大値を選択することなるけれど、「ツモ」については、イメージてきには、Σ(各ノードの評価値x実現確率)になるわけです。(あくまでイメージです。実際は順目の概念が加わるのでもっと複雑です。)ですので、現在の局面から終端ノードまでは1つのパスにはならず枝分かれが生じることになり、枝狩りがやりにくいのです。さらに、現在の局面の評価値は終端ノードの評価値とはことなることになります。さらに終端ノード以外は評価値に掛け算が加わるので厄介なのです、たとえば精度90%の読みでも、4回程度、先読みするとほぼ、当てずっぽうになってしまうのと同じなのでどうしても精度が低くなります。

以前「うしうし掲示版」で最適制御理論と機械学習の手法で麻雀の局面評価関数を作成する論文について、疑問を提示したとき、評価値は、先読みするとき確率と親和性のある値でないとまずい。という意図の記述をしたのは、麻雀はこういったゲームの木になるためです。


まったり麻雀の4人ゲームも実は基本はこれの一人麻雀のゲームの木をベースにしています。4人ゲーム化の補正をするために、評価値x実現確率の部分に、牌譜からとった情報を元に、補正値を入れています。
つまりこんな感じの計算になります。Σ(評価値x実現確率+他家和了時評価点x他家和了確率)

ただ、この4人化のための補正が現在かなり大雑把なために、新アルゴリズムが四人ゲームにしたときに弱くなってしまってます。


さらに、まほ公さんから指摘のあったとおりで、これには、鳴きの考慮が入っていない。
現在は、評価値はツモ前提の評価で、鳴ける牌は別のアルゴリズムを使って、鳴いた牌が出たときに、評価をしているのが現状です。

麻雀に強い人ならば、ご存知のように、ポンチーするパイというのは、鳴いた牌が場に出てから考えているのでは遅いのです。もたもたしている間に次の人につもられてしまうし、ネットだと鳴きラグでばれてしまう。
打牌する前に鳴くことも考慮して打牌を決定するわけです。

まったり麻雀は鳴く牌が出てから考えているため、鳴きラグでCOMが鳴くかどうか迷ってる(?)とばれてしまわないように、鳴き判断の処理速度は極端に気をつかってプログラムをしています。そのため、結果的にあまり深く考えずに鳴いているというのが現状です。


鳴きの考慮は結構難しいので後回しにしていましたが、まったく考えていなかったわけではないのです。プランとしてはだいぶまえから暖めていて、いろいろな作業と絡めなければいけないのでブログで紹介していなかっただけ。先にプランだけ紹介すると、自分が作業する前にほかの人に作られちゃうから、隠したいという気持ちがあったのです。

鳴き考慮の場合

要するに意思を持って変化する局面と確率で変化する局面が交互にくるのが、麻雀の特徴。これでも厄介なのですが、何とかゲームの木にすることが、できますし、実際プログラムとしてまったり麻雀のメインアルゴリズムにつかっています。鳴きが入るとさらに厄介です。鳴き判断は、確率による推移と意思による推移が同時にやってきます。しかし、鳴きのイベントを意思による局面変化と確率による局面変化にわけて、ゲームの木にすることは可能です。

どういったゲームの木になるかというと、以下のようになります。

Gt_nakiari

このようにノードを分ければ、鳴き考慮を打牌の前に判断しておく評価関数が作成可能です。


(麻雀の他家挙動を含めたすべての事象をこのようなゲームの木で確率によって局面が推移するノードと意思によって局面が推移するノードにわけてゲームの木にすることが、麻雀の理想のアルゴリズム実現になるのではないかと思っています。)

* * * * *

ただし、実際これをゲームに組み込んで遊べる形で、実現するためには、どの程度の確率で鳴けるのかとか、手牌が短いときの放銃の確率だとかいろいろデータを取る必要があり、すっごく作業が面倒です。
そういった泥臭い部分を除いても、順目の概念と評価値を組み合わせるのも複雑になり、手順前後による同一局面を枝狩りすることも困難にあります。さらに、一向聴手替なしでさえ、6手先までの深さを読まなければいけないので速度の問題もまた出来る可能性はあります。
* * * * *
実は、前回の手替わり考慮版評価関数はあくまで「布石」にすぎません。それほど落胆しているわけでも、失敗したわけでもありません。ここで紹介した鳴きありの探索や、点数状況判断の考慮のためのベースアルゴリズムとして活用可能なので原理が確立でき、処理速度のめどが立てばそれでOKなのです。

可能であれば、点数状況判断や手替わりの判断の修正をいれるまえに、新アルゴリズムをメイン評価関数にすえて一度、ージョンアップして公開したかったのですが、それができなかったというだけです。布石として着手したことが根本的に失敗だったとは思っていません。

|

« 被先制リーチ時収支 | トップページ | 根本が間違ってるのかも »

コメント

こんにちは、はじめまして、かどうか忘れましたが、うしうしで私の名はご存知でしょうか。まったり麻雀、楽しませてもらってます。(キレそうになるほど負けることの方が多いかもしれませんが)

機能・仕様に関する要望がある場合、どのような形でお伝えすればよろしいでしょうか。ここで構いませんか? メールの方がいいですか?

投稿: 我打麻将 | 2008/02/17 21:14

可能であれば、こちらのブログにお願いします。
個人的な話など、こちらでは話しにくい内容を含んでいる場合や、
画像などの添付が必要ならメールで連絡お願いします。

ただ、要望に必ずしもこたえられるわけではないのでその点はご了承願います。

投稿: kmo2 | 2008/02/18 02:34

ありがとうございます、ではこちらで。

1. 乱数のseed値について
うしうし掲示板にて少し前に、短期間で実力評価を行う方法についての話題がありました。
そこで私が「デュプリケート麻雀」を提案したのですが、もしご興味があれば、対局開始時に「乱数の種を指定」するモードの追加を希望いたします。
( /2006/05/post_fc8e.html でも同様の希望を見ました)

2. 打牌速度について
コンピュータの打牌速度に、あらかじめ指定したウェイトをかけることはできますでしょうか。
思考が深くなるかどうかも設定できるとベターですね。

3. ショートカットキーについて
「採譜対局開始」だけでも、F2とかで始められると嬉しいです。

たぶん簡単な順は 3>1>2 だと思います。有用な順は人によりますね。

投稿: 我打麻将 | 2008/02/19 21:09

3については、次回の版数アップのときに入れます。
2については、手替りアルゴリズムなどアルゴリズムが重くなったときに考えます。いま、単に遅くするだけだとあまり面白くないので。

さて、1ですが……
単にシードを指定するだけではあまりデュプリケートとして意味がないのではないかと思ってます。
これは本文に書きます。

投稿: kmo2 | 2008/02/21 01:30

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/61182/40155781

この記事へのトラックバック一覧です: ゲームの木と、鳴きへの変化を考慮した評価関数:

« 被先制リーチ時収支 | トップページ | 根本が間違ってるのかも »