将棋と麻雀の組み合わせの話、あとAIがやっていること
表題通りのことが話したいんですが。この手の話の前提として、数のスケールの目線をちゃんと持っておく必要がある
数(すう)の中には無限に存在するものとしないものがある(そして数の種類そのものもおそらく無限に存在する、というか作り出すことができる)んだけど、その中でも身近な数というと自然数になると思う。この後の話は自然数の問題として扱っても良いのでそのようにします
で、無限に存在すると言っても、大きさにはランクをつけたい。AとBを比べたときに、(大小だけでなく)その違いがドングリの背比べなのか、蟻と巨人なのか、わかっていた方がいいのだから
ひとまず、ロバート・ムナフォが1996年(？)に発表した定義によると
クラス0の数：-
まで
(まあ自然数って言っちゃったから本当は0は入らないけど)これは、一瞬で認識できる数。まあ、6つくらいなら一瞬で何個かわかるよね？
クラス1の数：-
まで
クラス0の数が一瞬で認識できるということは、クラス1の数(0の数が6個まで)は一瞬で"大きさが"認識できるはず。まあ、日常的に扱う数の上限もこのあたりではないかと思う
クラス2の数：-
まで
クラス1の上限が100万なので、クラス2の上限はそれを指数の肩に乗せた100万桁までの数になる。実は、自然数という定義に厳密に拘るとこの辺りが上限になるかもしれない。宇宙に存在する陽子の総数が-
と言われているからだ
※ちなみに、いわゆる無量大数が、Googleの由来になったGoogolは
なので、クラス2の数は実用表記上もほぼ上限と考えてよい
より上位のクラス(クラス自体も無限に存在するわけだが)の数については別の機会にするとして、表題の内容に関してはこの程度の大きさまでわかっていれば充分なので本題に戻ることにする
将棋の局面数
将棋の局面の組み合わせはどの程度だろうか？多めに見積もると、81マスに置ける駒の種類が歩、と、香、成香、桂、成桂、銀、成銀、金、角、馬、飛車、龍、玉の14通り。先後の向きを考えて28通り、置かれていない時もあるので29通りだとすると、組み合わせ数"L"としては
L :
ということで、いきなりクラス1の上限を超えているんだけど、これはそもそも駒の枚数条件を考慮していないので多めにも程がある。実際にはL : 程度と考えられるようだ。無量大数と同じ程度だというのはやや面白い
(参考：https://www.nara-wu.ac.jp/math/personal/shinoda/legal.pdf)
さて、この組み合わせ数なんだけど、これが現状のコンピュータでは取り扱いできないオーダーであることを理解したい。一局面に仮に何がしかの評価をしたとして、その結果を1バイトで保存(その局面がどちらの勝ちかだけ書き込まれているイメージ)できたとする。1テラバイトは バイトなので、Lの評価結果の保存に必要な容量は
TBとかのオーダーになる。これがどの程度かと言うと、地球に存在する全ての原子が1TBのストレージに化けたとしてもまだ足りないので、そもそも計算時間を考えるまでもないレベルであることが明白だ
あらかじめ全局面のリストを作っておき、ある"勝ち局面"を設定して、そこに変化可能かどうかを評価することで全ての局面の勝ち負けを評価するような、将棋の神様のようなことは不可能なことがわかる
将棋AIがやっていること
では今の将棋AIは何をしているかと言うと、終盤のどちらかが勝ちか計算できる場面を除けば、結局は局面の期待値(評価値)を計算している。プロ棋士の形勢判断は
・駒割
・(実質的な)手番
・玉形
・駒の働き
あたりがよく語られているけど、これがBonanzaになると
・駒割
・王と他の駒２つの位置(KPP)
・王と玉と他の駒の位置(KKP)
・王と王に隣接した味方の駒とその他の味方の駒３つの位置
・隣接しあった駒２つの位置関係
・竜馬飛角桂香の利き上にいる駒の種類
・竜馬飛角香が動ける枡の数
・ピンされている(動くと玉が取られる)駒の種類、方向、王との距離
・角と同じ色の枡にいる味方の歩の数
・歩桂銀が前進できるか
・竜飛香の前、後の歩
・王の周囲25枡の利きの配置
などなどをパラメータにして学習しているようだ
(保木さん本人による説明：https://www.ipsj.or.jp/10jigyo/forum/software-j2008/hoki-print.pdf)
ただ、これは2006年のBonanzaメソッドの話なので、今はもっとあると思われるのと、最近の強いソフトは勝ちがありそうな局面では専用のアルゴリズムで必勝の変化を読んでいるらしい。確か数年前のコンピュータ将棋選手権の決勝でelmoが勝ちを宣言した時の読み筋は"mate64"つまり部分的とはいえ64手先までの変化を読み切った事になる。藤井聡太、斎藤慎太郎あたりの終盤力とその強さを考えれば、elmoが実戦的にもどれだけ強いかは推して知るべし
ここまでまとめると、
・将棋の局面を網羅することはおそらく人類の歴史の中では不可能
・期待値計算であれば評価のパラメータを増やすことで精度が向上する
と、言ってしまって良いだろう
ちなみに、将棋よりはるかに局面数の少ないオセロの場合でも、局面数は64マスに白、黒、なしの3通りで
程度はあり、局面を網羅するのはやはり不可能に近い。指数の発散というのは恐ろしいものなのだ(もっともオセロは指し手の制約が多いので、実現可能局面はこれよりもさらに少ないが)
麻雀の局面数
さて、麻雀の局面数"M"はどの程度だろうか？これの良い計算方法はまだわかっていないけど、とりあえず牌山の組み合わせは比較的容易に求められる。136枚の牌の並べかたは136!で、実際には4枚ずつ34種類の同じもののある順列なので
M :
将棋の局面数を余裕で超えている。ここにさらに、"毎巡14通り程度の選択が最大20回程度繰り返される組み合わせ"を掛け合わせれば答えに近づきそうではあるんだけど、意味がなさそうだ
ゲーム性の性質を勘案して、"一人から見えている組み合わせ"のみ数え上げてはどうだろうか。最初は15枚(手牌＋ドラ表)から始まり、終局時には最大で80枚ほど見えている。それぞれ34通りあるので、多めに見積もって
M' :
うーんだめか、まあ、将棋に比べて牌の種類が多く、81マスが80枚に変わっているだけなのでわかっていたことではある
※ちなみに、本当はさらに15枚〜80枚の間の組み合わせも全て掛け合わせるんだけど、発散が速すぎて誤差の範囲なので割愛する
麻雀AIは何をするべきか
実は、これを書いている時点で僕はSuperPhoenixがやっていることをほとんど調べていない。なので書けることがないんだけど、とりあえずよくある誤解として"将棋と違って麻雀は完全情報ゲームじゃないので実用アルゴリズムの考え方も流用できない"というもの。前述の通り、将棋AIも結局は期待値計算しているので実はあまり変わらない(もちろん、目的関数と損失関数は全く違うものになるが、長くなるので割愛)。むしろ次元を下げる工夫や計算リソースをケチるための局面の同一視のやり方などは大いに参考になる|されるべきだろう
尻切れトンボになっているんだけど、誰かが麻雀AIに興味を持ってくれることを大いに期待しています
