[組み合わせゲーム理論] 組み合わせゲームとゲーム木について

組み合わせゲームとは

組み合わせゲームとは、2人の対局者が盤面に対して交互に手を打ち、一方の手番の時に局面に対して打ち手がなくなった場合を終局とするゲームのことを言います。

組み合わせゲームは特徴として、以下のような性質を持ちます。

• 完全情報 : ゲームの局面(状態)が全て公開されている
• 確定 : (サイコロなど)偶然に左右される要素がない
• 有限 : 有限の手数によって必ずゲームが終了する

つまり、サイコロなどのランダムな要素を持たず、相手に対して隠されているような手札を持たず、有限回手を進めることで必ず終了する様なゲームの事を、組み合わせゲームと呼びます。

組み合わせゲームの単純な例として、ドミナリングがあります。

ドミナリングとは、1×2の長さのドミノを盤面に交互に配置するという組み合わせゲームで、先手(左)は縦向き、後手(右)は横向きにしか置けないという規則があります。

ドミナリングにおける対局の流れを以下の図に示します。

図の例では、左が最後の手を置いた後、盤面に右が置ける手がなくなったため、最終的に左の勝ちとなります。このように、終局となった際に最後に手を置いた対局者を勝ちとするゲームを正規形と呼び、逆に最後に手を置いた対局者を負けとするゲームを逆形と呼びます。

また、ドミナリングでは左と右で置けるドミノの向きが異なるため、ある盤面に対して打ち手の選択肢が異なります。このように選択肢が対局者によって異なるゲームを非不偏ゲームとよび、逆に選択肢が左と右で同じゲームを不偏ゲームと呼びます。ドミナリングの亜種にドミノの向きを対局者が自由に選べるクラムがあり、これは不偏ゲームの一種となります。

局面と選択肢、ゲーム木

組み合わせゲームの進行は、対局者の打ち手とその結果生まれる新たな局面の繰り返しによって表現されます。

例えば、以下の様な局面があった場合、

左、右それぞれの次手の選択肢は以下の通りとなり、それぞれの選択肢の結果として新たな局面が生まれます。

このように、ある局面に対して選択肢を羅列したものをゲームの局面の木(ゲーム木)と呼びます。木で表現されることから予想される通り、枝となる局面に対して更に選択肢を羅列することで、ゲーム木は更に延ばしていくことができます。

ゲーム木を延ばす時、それぞれの局面について、どちらが次の手番であるかということは考慮されません。例えば、ある局面から右が連続で2手打つ場合の選択肢やその局面もゲーム木には含まれます。これは、ゲームの局面がいくつかの部分局面の和として表れた場合を想定しているためです。

以下の例では、部分局面の和として局面が現れた場合の、部分局面のゲーム木について考えています。進行によっては、ある部分局面に対して同じ対局者が2手連続で打つパターンがあることがわかります。

不偏ゲームでは、左右の選択肢は同じであるため、ゲーム木で左右の選択肢を区別しません。

ある局面に対して、末端がすべて終局となるように完全にゲーム木を延ばした場合、その局面で起こりうる局面を全て網羅することになります。

参考

• 組合せゲーム理論入門―勝利の方程式― (P.3 - 9)