麻雀ゲームが弱い理由（と羽生２冠が強い理由）～読みと見切り編～

先日の記事が割と評判が良かったようなので、続きを書いてみたいと思います。
前回は、局面の数に着目して麻雀の難しさについて書きましたが、今回は読みと見切り（探索と枝刈り）について紹介したいと思います。

将棋の場合：MIN-MAX法

将棋やオセロのようなゲームは、情報科学的には２人零和完全情報確定交互ゲームに分類されますが、このタイプのゲームではmin-max探索という先読みとαβ法という見切り（枝刈り）が有効であることが分かっています。

次の図のような感じです。

今、Ａという局面で先手の順番です。このとき先手にはＢ，Ｃという２つの手が考えられます。
先手がＢを指すと後手はＤとＥの２つの手が考えられ、先手がＣを指すと後手にはＦとＧという手が考えられます。

Ｄ～Ｇに書いてある数字はその局面で先手番からみた局面の有利さ（形勢判断）を数字化したものです。先手は出来るだけ数字が大きい局面に誘導したいですし、後手はできるだけ数字が小さい局面に誘導しようとします。

もし先手がＢを選ぶと、後手はまずＤの形勢判断をし(+3)次にＥの形勢判断をして(+5)小さい方を選びます。その結果Ｂの局面の形成判断は先手から見ると＋３点となります。

先手がＣを選ぶと、後手はＦの局面の形勢判断(-12)をし、次にＧの局面の形勢判断をします。(+10)点、その結果Ｃの形成判断は先手から見て-12点となります。

Ｂが+3点、Ｃは-12点ですから、先手はBを選んだ方が得ということになり、Ａの局面の形勢判断は先手から観て+3点ということになります。

いまの説明を式にすると
Aの評価値 = MAX(MIN(3,5), MIN(-12,10)) = MAX(3, -12) = 3
となります。

MIN(x,y)はxとyの小さい方の値を返す関数
MAX(x,y)はxとyの大きい方の値を返す関数

こういった方法をmin-max法と呼んでます。

将棋の場合：αβ法

実は上記の手順の中で省略できる箇所があります。
それはＧの形勢判断です。
Ｄ，Ｅの評価からＢが+3点だとわかりました。次にFの評価が-12点だとわかりました.
この時点でＣの局面の評価値は-12以下であることが確定しています。（もしＧの評価が-12より大きかったら後手はＧを選ばずにF選びます）先手はBとCの打ち評価が高い方を選びますから、この段階でCを選ばずBを選ぶことが確定しますのでもうGの形勢判断をする必要はないのです。

つまり、
Aの評価値 = MAX(MIN(3,5),MIN(-12,?))という式は？の値が分からなくても
MAX(MIN(3,5),MIN(-12,?)) = MAX(3, -12以下) = 3
と答えが計算できます。
?の箇所がいくつであってもA=3であることに変わりないので、?にどんな値が入るかかはどうでもいいのです。

こういった処理の省略をαβ法といいます。この例はパターンが少ないのでありがたみが感じられないかもしれませんが、実際の将棋では選択肢は２通りだけでなく８０通り近くありますので、そのうちの１つを読んだ段階でほかの79の局面を読まなくなるのは意味がありますし、２手先ではなくもっとずっと先まで読みますのでさらに効果が高まります。

なんか面倒くさいと感じされるかもしれませんが、プログラムにするとたったの数行の簡単な処理です。しかも、全く将棋の知識を必要とせず、処理を短縮してもそのことで誤差が生じるリスクが無く、処理時間短縮の効果が高いという、簡単安全高速な手法なのです。

αβ法の問題点とパスと羽生２冠

ただ、αβ法にも問題があります。図の左側から評価した場合はうまくいきましたが、この図を右側から評価してみるとうまくαβ法が働きません。
「ＧとＦを評価してＣが-12と判りました。次にEを評価して+5と判りました、Dの値がまだ判りません。」という時点では、BとCどちらを選べばいいか判断ができません。
式にするとこんな感じです。
A=MAX(MIN(10,-12), MIN(5, ?))
この式は?が-12より小さいかどうかで結果が変わってきます。

なのでαβ法はどの着手を先に読むかが大事なわけですが、理論上は、先手も後手も最善手を先に読むとαβ法の枝刈り効果が最も高いことが分かってます。

けれど、どの手が最善手かを調べようとしてるのに、「最善手を先に選択すれば処理が削減可能」といわれても困ります。それが分かるならそもそも調べる必要自体が無いわけです。

せめて、一番良い手が分からないとしてもそれなりに良い手が分かれば、αβ法は最善ではないにしろそれなりに効果を発揮するので、何とかして割といい手を探そうとするわけですが、そこで用いられる手法の一つが「パス」です。

認知科学の特別講演でプロ棋士の羽生２冠が面白いことを言っています。

「将棋というゲームの本質的な部分だとは思うのですが、可能性のある手はたくさんありますが、指したとしてもプラスになる手は限られています。というか、指さないほうが良いぐらいのマイナスになる手がたくさんあるんです。だから殆どの手は、消去法的に選ばないという感じです。」

将棋には一局面で８０手前後のルール上許される着手があるのですが、そのほとんどはパスをするより酷い手ばかりだということです。なのでルール上は許されないパスを便宜的に許して、先にパスした場合を探索するとそれが割といい手を先に選択したことと同じことになり、αβ法の効果を上げる事が出来るのです。

激指などで読み筋を表示させているとパスが表示されることが割と頻繁にありますが、それはそういった手法を用いているためのようです。

探索速度と羽生２冠
もう一つ、麻雀と比較する意味において、min-maxとαβ法を用いた手法で気にしてほしい点があります。それは、形勢判断が必要なのは(原理的には)終端の局面だけだということです。途中の局面BやCでは単にルール上打てる着手を列挙して片っ端から局面を進めていけば良く、玉の固さだとか駒得だとか、駒の連携だとかの形勢判断をする必要は一切ないのです。ですから、コンピュータ将棋は１秒間にものすごい数の局面が読めるわけです。

ちなみに羽生２冠はどうしているかというと、これもまた認知科学の特別講演ですごいことを言ってます。

司会「羽生さんは将棋の盤面は頭の中でどのように描いているのでしょう？」
羽生「実際は局面が将棋版として頭の中にあるとすると、そこから符号で局面が進んでいきます。読みが進んでいるときには盤面は浮かんでいない状態です。」

羽生さんは、途中の局面をイメージ化する作業を省いて、形勢判断するべき十数手先の局面のイメージ映像がいきなり脳内に見えるようなのです。

小学生が最初は５×３を5+5+5と一つずつ計算しているけれど、慣れると「さんごじゅうご」と一気に答えを出せるようなりますが、それと似たような感じのようです。

羽生さんの話は、聞いているとコンピュータのロジックにつながる点が色々とあってとても面白いです。講演を聞きに行く機会がある人はぜひ聞きに行かれるとよいでしょう。また、ぜひ質問を用意していくべきです。羽生さんの講演の真価はむしろ質疑応答にあるといってもいいくらいです。この人は１対１で対峙して相手のアクションにリアクションを返す時にこそ、とてつもない魅力を発揮する人だと感じることでしょう。

麻雀の場合、min-max法もαβも使えない

前置きが長くなりましたが、麻雀の場合について紹介します。

麻雀の場合、確率に左右されるゲームですし、４人でやるゲームですので対局相手は、必ずしも自分の評価値を下げる着手を選ぶわけではありません。よってmin-max法の探索手法は使えません。

理論的にどういった探索が良いかは不明ですが、「まったり麻雀」に関していえば、私が勝手にprob-max法と呼んでる方法で探索をしています。

(ちなみに、処理速度やゲーム内で表示される評価値、文献などを見る限り、市販の麻雀ゲームは全く先を読んでいないと思います）

イメージとしてはこんな感じです。

将棋と同様自分は、評価値が高い方を選ぶのですが、違いは、相手の着手は統計データから着手する確率を推測する点です。

式にするとこんな感じになります。
Aの評価値 = MAX((0.2 * 3)+(0.8 + 5), (0.7 * (-12)) + (0.3 * 10))

相手の着手の確率とその時の評価値を掛け算して期待値を出しそれを足していく感じになります。
式が上記のような形ですから、式のどこかに値が分からない個所があれば評価値が分からなくなってしまいますので、αβ法のようなゲームのノウハウがなくても実装できる安全簡単高速な処理削減方法(後方枝刈り)は原理上ありえません。

よって、厳格な先読みをしようとすると、指数関数的な計算量の爆発をもろに受けることになります。

また、終端の局面の評価だけでなく、途中の局面での確率の推定も非常に重要な意味があるため、将棋と違い読みの途中の局面でも形勢判断が求められる点も麻雀の難しさです。
（将棋にも実現確率探索というものがありますが、あれと麻雀のアルゴリズムでは求められる精度がまったく違います）

そもそも、「読み」という言葉が指すものが将棋と麻雀では違います。
将棋の読みは詰将棋などのように何手か先の局面をイメージすることであり、情報科学用語では「探索」に近いものですが、麻雀の読みは先の局面を読むというよりも、見えていない情報を推理するという意味合いで使いますので、どちらかというと情報科学用語としては、探索ではなくて「推定」に近い感じがあります。その言葉の違いだけでも、途中の局面の確率推移の必要性が重要であることが表れているといえるでしょう。

麻雀の場合先読みすれば強くなるわけではない

将棋の場合、先が読めることはそのまま強さに直結しますが、麻雀の場合はそうはいかないのも麻雀ゲームの難しさの一つです。
麻雀の局面の計算式は、一巡先を読むごとに、評価値に確率的予測の掛け算がかかってくるため、先を読むとそれだけ精度が下がってしまうのです。

つまり、例えば、１巡先を90%の精度で読めたとしても、2巡先は81%(0.9*0.9)、3順目は72.9%とドンドンと精度が落ちて行ってしまい５，６巡先には当たるかどうか五分五分まで精度が落ちてしまうのです。

なので麻雀の場合、どうしても評価値の誤差が大きくなってしまい、そのため強いコンピュータを作ることが困難になります。

参考文献

羽生２冠の思考について認知科学やＡＩの視点で語られた本に「先を読む頭脳」があります。
とても面白い書物です。値段の安くなった文庫版も出版されてますので、ぜひ読むことをお勧めします。

コンピュータ将棋について教養レベルで知りたければ以下の本がお勧めです。渡辺竜王とボナンザの対局、あからと清水女流との対局、8bit時代からのコンピュータ将棋の歴史をユーモアを交えて書かれています。将棋ソフト開発者や棋士へのリスペクトも強く感じます。

情報系の大学生かそれに近いレベルの人で実際に思考ゲームを作りたいならば以下の本がお勧めです。
この手の本としては、比較的最近出版されたもので結構新しいノウハウも書かれています。
各章の主題なテーマだけでなく、文章の中にもさらっとわりと重要なことが書かれていたりします。
この本に書かれているものの猿真似では、麻雀ゲームには使えませんが、なぜ使えないかを考える過程で、自分なりの答えを見つけていくことはできるだろうと思います。というか、頼りになる麻雀の文献はないので、そうするしかありません。

次回：評価関数と最適制御理論とモンテカルロ探索編につづくかもしれないし面倒くさいので書かないかもしれません。