ボードゲームの思考アルゴリズムの入門
社内の技術系Adventカレンダー向けに何か書けと言われ、とりあえずボードゲームの思考ルーチンについて書いてみたり。
せっかくなので、存在を忘れかけていたBlogメンテの意味も込めてこちらで公開。
ボードゲームをプレーする=知能?
ボードゲーム、その中でもチェスをプレーするということは、非常に人間的な行為であると思われてきました。チェスをプレーするということは知的であり、創造性を要する、極めて複雑な問題であり、人間にしかできないと思われていたわけです。
そんな知的な作業をコンピュータが行うことが出来れば、これは人工的に知能を実現したということだ、ということで、ある種の目標となり、歴史的なコンピュータサイエンスや人工知能の研究ではチェスは度々登場します。
チェスのアルゴリズムの振り返り
ご存じの通り、1996年にはチェス世界チャンピオンであるカスパロフと、IBM製のDeepBlueが対戦をし、コンピュータが勝ちました。(ここら辺はチェスファンからすると異論もありますが、ある種の節目ではありました。)
Wikipediaにもあるように、1840年バベッジ*1の頃から構想はあり、どれが初めてのチェスアルゴリズムと言って良いか分かりませんが、1951年にチューリングが手計算でチェスアルゴリズムと人間の対戦を行ったところを初のチェスアルゴリズム登場と見なすならば、かれこれ45年の歳月がかかったわけです。
人工知能としてのボードゲームの思考ルーチン
「人工知能研究は、常に未解決問題」と言われることがあります。
これは、問題を定式化し、計算というタスクに落とし込むと、結局は特定の問題に帰着し別分野として確立をしてしまうからです。
例えば最近の例で言えばGoogleの自動運転であったり、今日では実用的となっている機械学習など、様々な分野が元々は人工知能研究のテーマでしたが、今では別分野として確立をしています*2。
同様にチェスなどのボードゲームも、コンセプトを重視するなら「思考」と擬人化した表現をしたくなるものの、アルゴリズムは今日ではゲーム理論と計算機科学における単純な探索問題となります。
オセロのアルゴリズムのざっくり説明
ボードゲームの中でも、ルールが単純な、オセロについて簡単に。
ゲーム木探索
ボードゲーム探索の基本的な考え方は、「可能性のあるパターンを先読みして、最終的に最も良くなる状態の手を選択」するという方法です。この基本は、オセロのみならず、将棋、チェスと全て変わらずに同じです。
先手を四角(□)、後手を丸(○)とすると、図1のように可能性のあるパターンを全て羅列します。この例では、2手先まで先読みを行っています。
そして、「先手、後手共に、常に最善の手を打つ」という前提のもと、先読みをした範囲から「最も良い結果」となりうる最善手を目指して手を打ちます。
- Fig ゲーム木のイメージ
評価関数
盤の状態がどちら側にとって、どの程度有利なのかということを定量的に比較するために、評価関数を用いて点数化をして判断します。先手に有利であれば有利な分だけ正の点数、後手に有利であれば負の点数、そして完全に互角であれば0を返す関数です。
この評価関数の「出来の良さ」というのは、プレーをしたときの強さに最も直接的に影響します。オセロの場合は、2手先の先読みだけであっても、評価関数さえ良ければ一般的なオセロをちょっと指したことある人が勝てないレベルにはなる、と言われています。
今回は、オセロで単純な例として、置いている場所から点数化をする例を紹介します。
例えば8×8の盤に対して、以下のような点数を振ります。 (この点数の付け方は経験的なものであり、必ずしもこれが強いわけではありません。)
- Table オセロの評価関数用の点数の例
それぞれ石が置いてある場所の点数の合計(後手は有利なほどマイナスなので、× -1をして評価)によって、点数化します。
評価値 = Σ(白の石が置かれている箇所の点数) ＋ -1 × Σ(黒の石が置かれている箇所の点数)
人間の判断だけで、精度の高い評価関数を作成するのには限界があります。
応用として、この評価関数自体を機械学習(具体的には強化学習)の枠組みで、学習器によって「学習」する仕組みが可能です。
つまり、自らプレーを通じて試行錯誤しながら強くなっていくという、実に人間らしい仕組みです。
MinMax法
全ての可能性のある指してのゲーム木と、評価関数を用いて、これらをもとに最適な次の指し手を決定します。
完全情報ゼロ和ゲームと呼ばれる種類のゲームに対しての最適戦略を求めるゲーム理論の方法の1つです。
手順は以下となります。
- まず、ゲーム木を探索し(この場合は2手先まで)、その結果を「1.評価関数で点数化」を行います。 次に、この評価値をもとに探索を行います。
- 先手を四角(□)、後手を丸(○)とすると、先手にとってはよりプラスの評価値ほど良い、後手にとってはよりマイナスが良いわけです。 一番底の評価値から、以下のルールに従い探索を行います。
- 「四角(□)のノードでは、取りうる選択肢から最大値を選択」
- 「丸(○)のノードでは、取りうる選択肢から最小値を選択」
この手順に従い探索を行うと、図の赤い矢印のように-3へ続く手筋が選択されるわけです。
この手順を繰り返すことで、先読みの深さにかかわらず、最適解を導くことができます。
ここで「先手にとって最も良い点数は、左下の+25だ。なので先手は、一番左を選択するべきでは？」という疑問が出てくるかもしれません。
仮に先手が一番左を選択したとすると、次の後手は{+25, -5, -9}という選択肢が与えられます。後手の選択では最も有利となる-9を選択することになるため、+25は選択されません。
つまりこのアルゴリズムは、お互いに「合理的」な意思決定をした場合にたどり着くことが可能な範囲から、最も良い手を選択するアルゴリズムとなります。
ちなみに、、この探索ですが、ちょっと考えると、実は無駄な探索をしているということに気がつかれた方もいるかもしれません。
実は、必ずしも全てのノードを探索せずとも、同じ解を得ることが可能です。 このMinMax法を枝刈りして計算量を減らした方法としてαβ法という手法もあります。
現在の第一線のチェス、将棋ソフトでもαβ法を基本として探索をしています。
オセロ、チェス、将棋、囲碁の探索問題としての「難しさ」
オセロは、90年代の後半に、日本人チャンピオンの中島さんとPCが対決をし、6対0で人間が完敗してしまいました。
しかも、ただのPentium Pro×2のSMPというちょっと早い程度のPCでした。( 人間側チャンピオンの中島さんの「一度くらい、いい試合をしたかった」というコメントが印象的で、そこからも強さが伝わってくるかと思います。)
チェスもまた、1996年にDeepBlueという計算機クラスタにより、人間に一応勝ちました。
将棋も、2013年になり、人間に勝つ兆し(事実上勝っている?)が出てきました。
この順番というのは、コンピュータが探索をしなくてはならない局面数の大きさによっておおよそが決まっています。
各ボードゲームの局面数をざっくり推定をすると、以下のようになります。 (10の360乗というのは、0が360個ということです、念のため。)
オセロ : 10の56乗
チェス : 10の120乗
将棋 : 10の220乗
囲碁 : 10の360乗
非常に膨大な探索空間です。 探索をするという観点では、仮にコンピュータが10倍速になったとしても、せいぜいさらに数手先まで深読みが出来る程度の違いしか無かったりします。
そういう意味では、コンピュータの「早さ」の進歩も大事ながらも、適切な評価関数であったり、棋譜のデータを取り入れたりといった試みの方が大事だったりもします。
ちなみに、現在、最もホットな領域の1つが「囲碁」です。 上記の局面数を比較すると、囲碁だけが桁違いです。
これは、19×19と盤が広く、好きなところに置けるので局面数も広いことが理由で、また探索をする上でも、評価関数が非常に難しい(たった一手によって形成が逆転をしたりと安定せず、また形成の判定に地というパターン認識が求められるためスコア化が極めて行いにくい)ということが主な理由です。
そのため、ちょっと前までは、今までのゲーム木探索というアプローチとノイマン型計算機である限り、囲碁プログラムは人間には勝てないと言う研究者もいました。
しかし最近になり、確率的なアプローチでプレーをする「モンテカルロ囲碁」という方法が出現し、突如、囲碁のレベルが上がりました。
これは簡単に言ってしまうと、ランダムに手を指して、確率論的に勝つ確率が高いところに打つ、というような方法論です。
ある意味、成熟したと思われていた分野で、この様なイノベーションが起きるというのも面白いですし、今後の動向から目が離せないのでした。
作ってみた(実装編)
というわけで、上記のアルゴリズムに従って、とりあえず作ってみたものをご紹介します。
とはいえ、幾つかを単純化をしています。
ボードゲームでは、途中までの打ち手の順番は異なっても、最終的には同じ盤面になることが多々発生します。 であれば、ゲーム木をlink listで表現し、一度探索した盤面の状態をhashから辿れるようにすることで、次回以降は同じ盤面が出てきても計算と探索を省けるわけです。また探索も幅優先探索をしながら、許されている持ち時間の中で深く掘り下げると言う方が効率的です。 しかし、ここでは実装の単純化のため再帰関数による深さ優先探索とします。
