【ゲーム木探索】コンピュータにボードゲームをプレイさせる方法。

チェス・将棋・囲碁までもがコンピュータ（人工知能）が人間を超えてしまいました。

では、コンピュータはボードゲームをどのようにプレイしているのか、基本的な概要を調べてみました。

二人完全情報確定的ゼロ和ゲーム

将棋などのボードゲームは、「二人完全情報確定的ゼロ和ゲーム」というゲームに分類されます。
なにやら長くて難しい名称ですね（笑）
ちなみに、オセロ・チェス・囲碁も同じ仲間に分類されます。

それでは、「二人完全情報確定的ゼロ和ゲーム」に当てはまる条件は何なのでしょうか？
単語を分割して1つずつ説明していきます。

「二人」は、二人で対戦するゲームであるということです。

「完全情報」は、相手の情報も全て見えるということです。
例えば、トランプは相手のカードが見えないのでこの条件には当てはまりません。

「確定的」は、偶然性が一切入らないということです。
例えば、サイコロを振るゲームだと、偶然性が入ってしまいこの条件に当てはまりません。

「ゼロ和」は、足してゼロになるゲームであるということです。
自分が勝てば、相手が負け、
相手が勝てば、自分が負けとなるゲームです。

で、以下の手法は、この「二人完全情報確定的ゼロ和ゲーム」にしか適応することができない手法です。

ゲーム木探索

ゲーム木とは、以下のような樹形図のことです。

初手がルートとすると、
1手指すごとにどんどん枝分かれしていきます。
そして、ずっと伸ばしていくと、必ず最後のノードにいきつきます。
それを葉といいます。

コンピュータは、このゲーム木を探索していき、指し手を決めていきます。

最終局面まで読みきることができれば、そのボードゲームの必勝法を求めることができますが、
その局面まで着手可能な指しては、

• オセロの場合は、１０の６０乗
• チェスの場合は、１０の１２０乗（将棋と違って持ち駒が使えないため少ない）
• 将棋の場合は、１０の２２０乗
• 囲碁の場合は、１０の３６０乗（将棋より升目が多い１９×１９路ある）

あるため、読み切るのは不可能で、スーパーコンピュータを使っても宇宙の歴史より長い時間がかかってしまうそうです。

Minimax 法

よほど単純なゲームでない限り、最終局面までの読み切りは不可能なので、コンピュータに「ある程度の局面まで読んで、その時点での最善手を指す。」ということをさせます。

その際に指し手を決めるルールが Minimax 法です。

もう少し詳しくいうと、ゲーム木において、「あるところまで探索してその局面に点数を付け、自分の手番で評価値を最大化し、相手の手番で自分の評価値を最小化するような手順を選択していく。」ということになります。

局面に点数を付けるときに使われるのが、局面評価関数と呼ばれるもので、将棋の大局観に相当します。

この Minimax の考え方を考案したのが、「CLAUDE E. SHANNON」や「Von Neumann」です。

それぞれの論文です。

・「Programming a Computer for Playing Chess」

https://link.springer.com/chapter/10.1007/978-1-4757-1968-0_1

・「Game Theory and Von Neumann’s Minimax Theorem」

http://cdm16120.contentdm.oclc.org/cdm/ref/collection/p16120coll7/id/5

αβアルゴリズム

単純にMinimax法を使って探索していくと膨大な数の局面になってしまいます。

ある局面の平均着手可能手は、チェスだと35、将棋だと80、囲碁だと250程度だといわれており、数手先の探索でさえ膨大な探索空間になってしまいます。

そこで、Minimax法 で不要な探索を減らして、効率的に探索を行うために、D. E. Knuthらにより考案された手法が αβアルゴリズムです。探索を減らすというのは、具体的には「不要な葉ノードの局面評価関数の呼び出しを減らす。」ということです。

ちなみに、αβアルゴリズムを使って効率的に探索を行うとMinimax法と比較して探索数がその平方根くらい少なくできることが知られています。

論文です。

・「An analysis of alpha-beta pruning」

https://www.sciencedirect.com/science/article/pii/0004370275900193