麻雀アルゴリズムの課題

自分のためにまとめ。

麻雀では、「新しい牌をツモって、不要な牌を切る」を繰り返して和了り（上がり）の形を目指します。
牌は34種類あって手牌は14枚あるので、単純に考えると、n巡の先読みをする場合はゲーム木のノード数が(34*14)^n=476^nも必要になります。この枝を刈るために、普通は「シャンテン数」の増減に着目します。

シャンテン数は、現在の手牌で和了りに不足している牌の枚数から1を引いた数です。シャンテン数が-1なら和了りで、0ならテンパイです。シャンテン数を減らすことが麻雀の目的とも言えます。

新しい牌をツモったとき、シャンテン数は1減るか、変わらないかのどちらかです。牌を切ったとき、シャンテン数は変わらないか、1増えるかのどちらかです。

ゲーム木を構成するとき、「シャンテン数の変わらないツモ」と「シャンテン数の増える切り」の一方または両方を無視すれば、枝を大幅にカットできます。でもこの枝刈りをすると、麻雀において非常に重要とされる「手替わり」と「シャンテン戻し」を考慮できなくなってしまいます。

手替わりは、ツモと切りの後にシャンテン数が変化しないけれど、和了期待値が高まる打牌です。シャンテン戻しは、ツモと切りの後にシャンテン数が増えてしまうものの最終的な和了期待値が高まる打牌で、局所解を抜け出して大域解を目指すような打牌です。

表にまとめると次のようになります。

-	ツモ(シャンテン数減)	ツモ(シャンテン数不変)
切り(シャンテン数不変)	棒テン (A)	手替わり or 無駄ヅモ (B)
切り(シャンテン数増)	手替わり or 悪手 (C)	シャンテン戻し or 悪手 (D)

優秀な麻雀アルゴリズムを作るためには、(B)(C)(D)の領域をきちんと考慮に入れて、かつ組み合わせ爆発を抑える何らかのアイデアが必要です。