コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。2:アルファベータ枝刈り」では、アルファベータ法の解説を行いました。ここでは、アルファベータ法の筆算方法について詳しく紹介します。手法の原理については上記の解説記事をご覧ください。基本的な事柄を整理しておきます。各局面には探索の下限値(α)と上限値(β)が与えられており、1つ先の局面(子ノード)の探索結果(評価値、もしくは評価値の存在範囲)を得るたびに、探索の範囲が狭められていきます。各局面における探索範囲の変化を追いかけていくことがアルファベータ法の肝となります。自分の手番においては、子ノードの評価値が下限値よりも大きければ、その評価値を新たな下限値として更新します。結果的に、全ての子ノードの探索が終了すると、最終更新値は子ノードの評価値の最大値となり、それがその局面の評価値となります。一度も更新されない場合には、全て下限値以下であったということですので、「α↓」というのが探索結果となります。上限値を超える更新があった場合には、その時点で探索を打ち切り、「β↑」を探索結果とします(※この時には、評価値は上限値以上である同時に、更新値以上でもあるので、さらに評価値の存在範囲を狭めることもできますが、今回の探索においては余分な情報になりますので切り捨てます)。相手の手番においては、逆に、子ノードの評価値が上限値よりも大きければ、その評価値を新たな上限値として更新します。その他も、自分の手番の場合の逆になります。実例で見ていきましょう。下図のゲーム木は上記の解説記事のものと同じものです。図中の各ノードには下限値と上限値が並べて書いてあり、確定値には下線を引きます。探索によって、下線のない数値を更新していくというのが基本的な作業になります。初期局面の探索範囲は負の無限から正の無限までの全ての範囲にしてあります(※図中の「INF」は無限の意味)。子ノードの初期の探索範囲は、その子ノードの探索開始時の親ノードの探索範囲を引き継ぎます。初期局面の最初の子ノードの初期探索範囲は、初期局面の探索範囲を引き継いで、全範囲となります。各局面を順番に展開していくと、右上の末端局面で「+500」の評価値が得られますので、その親ノード(自分の手番)の下限値が「+500」に更新されます。続いて、2番目の末端局面の評価値は「-200」であり、下限値の「+500」よりも小さいので、下限値は更新されません。この段階で子ノードの探索は終わりですので、最終下限値の「+500」が評価値として確定します。この確定した評価値により、さらに1つ前の親ノードの上限値が「+500」に更新されます。進めていくと、3番目の末端局面の評価値は「+700」であり、上限値以上ですので、探索は打ち切りで「+500↑」が親ノードの探索結果となります。この場合、さらに1つ前の親ノードの上限値は「+500」のままで変わりません。初期局面の最初の子ノードの評価値が「+500」で確定しましたので、初期局面の下限値が「+500」に更新されます。探索を進めると、6番目の末端局面は「+200」であり、下限以下ですので更新はされません。7番目の末端局面も「-100」と下限以下で更新されず、親ノードの下限値は更新されないままに子ノードの探索が終わりましたので、「+500↓」が探索結果となります。これにより、さらに1つ前の親ノードの上限値が「+500↓」で更新されますので、下限以下となり、探索は打ち切られて、初期局面の評価値が「+500」で確定します。これにて探索は終了です。以上、今回は、アルファベータ法の筆算方法について紹介しました。実際に手を動かしてやってみると、何となくアルファベータ法の感覚がつかめてくると思います。筆算というのは、技術としては必ずしも役に立つものではありません。人間のやることには必ずヒューマンエラーが伴いますので、計算はできる限り自動化される方向にあります。コンピュータの発展により、四則演算はもうとうに人間がやるべきことではなくなっていますし、複雑で高度な数式計算ですら、数式処理ソフトで計算するのが当たり前の時代になってきています。人間が概念を学習するためには手を動かす作業が有効であり(不思議なことですが)、代わりの学習方法が出てくるまでは、筆算の教育的な価値が失われることはないと思われます。1:コンピュータ将棋の基本戦略」では、ミニマックス法の戦略について解説しました。今回は、ミニマックス法における枝刈りについて解説します。枝刈りには大きく分けて2つの種類があります。「前向き枝刈り」と「後ろ向き枝刈り」です。「前向き枝刈り」とは、探索を行わずに何かしらの人為的な基準によって枝刈りを行うことです。探索に“先入観”を取り入れることになりますので、上手くいくかどうかはやり方に依ってきます。「後ろ向き枝刈り」とは、探索時の情報を活用することでミニマックス法の結果ができるだけ変わらないように行われる枝刈りのことです。副題の「アルファベータ枝刈り」(アルファベータ法とも言う)が代表例であり、これはミニマックス法の結果を確実に再現することができます。後ろ向き枝刈りは基本的にはやった方が得になります。今回の記事では、主として、後ろ向き枝刈りの最も基本的な手法であるアルファベータ法について解説します。この手法は、コンピュータ将棋の探索技術の基盤となるものです。前回のミニマックス法の探索例を再掲します。この例は、以下の図のように書き換え、「?」部分を任意の数字に置き換えても、初期局面の評価値や最善手の結果は変わりません。実際に色々と数字を入れて確認してみてください。探索途中の局面の評価値は変わりうるので、「+700↑」「+200↓」のように範囲で表現しています。ここで、数字末尾の「↑」は「以上」を、「↓」は「以下」を表しています。このことは、言い換えると、「?」部分は実は探索する必要がなかったということを意味しています。全局面を探索しなくても、正確な初期局面の評価値や最善手を得ることができるというわけです。それでは、実際にどのように探索をすれば無駄を減らすことができるのでしょうか?探索量を減らすという事は、その分だけ情報量を減らすということを意味していますので、上の例で途中の評価値を確定値から範囲値に変えたように、情報量削減の工夫が必要になってきます。探索の際に下限と上限の範囲を決めることで情報量を減らし、探索の無駄を省く手法のことをアルファベータ法と言います。名前は、下限値をα、上限値をβと書いたことに由来しており、現在でも探索の下限値と上限値は慣習的にαとβで書き表されます。実際にやってみましょう。上の図でそれぞれの局面の左下に書いてあるのが探索範囲です。初期局面の探索範囲は負の無限から正の無限までの全ての範囲にしてあります(※図中の「INF」は無限の意味)。初期局面からスタートして、局面を展開し、上から下へと順番に探索していきます。探索範囲は、探索で得られた情報を用いて、随時更新されていきます。上に位置している4つの局面は、まだ何も情報がありませんので、初期局面の探索範囲のままです。右上の末端で「+500」という値が得られます。この分岐では最大値を探しているので、2番目の末端局面の探索範囲の下限が「+500」に更新されます。2番目の末端局面の値は「-200」であり、下限以下ですので、これは無視されて、最終更新値である「+500」が一つ前の局面の評価値として返されます。一つ前の局面の分岐においては、最小値を探しているので、ここでは探索範囲の上限が更新されます。結果、探索の上限は「+500」となるのですが、3番目の末端局面の値は「+700」であるため、これで下限値を更新すると、それ以降の探索範囲は「+700」以上「+500」以下となって探索範囲が消失します。探索範囲が消失するということは、それ以降は探索しなくてもよいということです。以下同様の操作で、無駄な探索を省いて正確な結果を得ることができます。この手順はプログラムで書くと簡単なのですが、人間が理解しようとすると中々に大変です。アルファベータ法の筆算方法の詳細については「アルファベータ法の筆算:これであなたもコンピュータ!?」の記事にまとめました。ここで注意しなければならないのは、上記の手法に際して、「上から下へ」という探索の順序を指定していたことです。前の記事で全局面を探索していた時には探索順序は関係ありませんでした。実は、アルファベータ法の場合には探索順序が重要であり、探索順序によって省略できる探索量が変わってきます。上の例では末端の8局面の内の3局面の省略に成功していますが、記事冒頭の図に戻って、順序を「下から上へ」と逆にしてアルファベータ法をやってみると、ただの1局面も省略できないことが分かります。種を明かすと、上の例は「上から下へ」と探索した時に最も効率がよくなるような順序(各分岐で最善手を最初に探索)になっていたのです。それでは、実際に探索順序によって探索量はどれくらい変わってくるのでしょうか?分岐数を3に固定した時の探索局面数を以下に示します。横軸は探索の深さdです。青点が最善順序の時の結果(評価値は各分岐に対して等間隔)、赤点が最善順序の逆順の時の結果、黒点がランダムの時の結果(1000回の平均)になります。縦軸は常用対数ですので、10の何乗であるのかを表しています。全局面を探索する場合には、3のd乗ですので、赤線になります。最善順序の逆順の場合の結果(赤点)は、これに近くなります。2}\]の線(青線)によく一致しています。この式は、3を分岐数で置き換えると、固定分岐数におけるアルファベータ法の理想値として知られているものです。ランダムの場合の結果(黒点)は両者の中間くらいに位置しています。アルファベータ法は、順序が最善ならば、探索量を平方根で減らすことができます。平方根の違いは意外と大きく、例えば、上図で20手のところを見てみると、最善順序なら10万局面程度の探索で済むところが、ランダムならその100倍以上の計算量が必要になり、全局面なら1万倍以上の計算量が必要になります。最善順序なら1秒で済む思考時間が、2分とか、3時間とかになってきてしまうわけです。局面数が増えると、違いはより顕著になります。アルファベータ法が最もよく機能するのは、各分岐で最善手を最初に探索する場合であり、有望そうな手から順番に探索していくことが大切になります(指し手の順序付けの問題と言う)。move」と言う)を優先して探索したりというような工夫がなされています。上の例では、初期局面の探索範囲を負の無限から正の無限までの全範囲に設定していたわけですが、最初の段階から探索範囲に制限を加えてしまうことも可能です。設定範囲内に正解があるかどうかという賭けの要素が出てきます。下限値(α)と上限値(β)を利用して、さらに枝刈りを行う手法もあります。move枝刈り」や「futility枝刈り」等が有名です。move)によって相手に手番を渡した時に、それでも上限値以上なら、その局面は上限値以上と決め付けるという手法のことです。将棋の場合には、パスより酷い手しかないという局面(チェス由来のドイツ語でツークツワンクと言う)は滅多にありませんから、非常に高確率で有効な手法です。「futility枝刈り」というのは、末端まで残り1手の局面で評価値の簡易見積もりが下限値を大きく下回っている/上限値を大きく上回っているのならば、無駄(futility)になる可能性が高いので、その局面の探索を打ち切るという手法のことです。残り数手に拡張されることもあります。これらの手法は、アルファベータ法とは異なり、確実な結果を保証するものではありませんが、コンピュータ将棋においては有効な運用が可能であることが知られています。ちなみに、各々の枝刈り手法が「前向き」なのか、「後ろ向き」なのかについては文献によって記述に差があるようです。「futility枝刈り」は、評価値の簡易見積もりと人為的な基準によって探索を行わずに枝刈りをしているわけですから、厳密には「前向き」だと思われますが、一方で、アルファベータ法の近似手法の一つだと捉えると、「後ろ向き」であるとも解釈が可能です。「前向き」/「後ろ向き」の分類は、数学的な定義の問題というよりは、その手法をどういうものだと位置づけているかという解釈の問題なのかもしれません。「全幅探索」という言葉についても様々に解釈の余地があるようです。本来は「その深さの全ての局面の探索」を意味する言葉ですが、それと同じ結果が得られるアルファベータ法も「全幅探索」に含めることがあります。move枝刈り」や「futility枝刈り」等も、近似的に同じ結果を得ていると考えて、「全幅探索」に含めることがあります(例えば、Bonanza等)。この辺のことは定義に拘る人が見ると頭が痛くなるかもしれませんが、急速に発展する分野において言葉の整理が追いつかないというのは、とてもよくあることです。言葉を整理するのは、全てが終わった後に学問としてまとめる学者の仕事なのです。最後に、ハードウエアに関することを少し補足しておきます。上記の例では、1つのスレッド(一連の命令の流れ)で処理することが暗黙の前提になっていました。最近のCPUはマルチコアが基本になっています。i7-6700Kであれば、4つの物理コアを有しており、一度に4つのスレッドを処理することが可能です。ハイパースレッディング(HT)技術を用いると、4つの物理コアを8つの仮想コア(論理コアとも言う)に分けて利用することもでき、同時に8つのスレッドを処理することも可能になります。その場合には、1スレッドの性能は0.65倍程度に落ちてしまうようです(参照:「30分でBonanzaの評価関数の要点を話します!」)。1台のPCに限らず、多数のPCをつなげてクラスタとして使用する場合には、もっと大量のスレッドを同時に処理することになります。上述のアルファベータ法等の枝刈りは、探索時に得た情報を随時的に活用していました。これをマルチスレッドでどのように処理すればいいのかというのは技術的に簡単な話ではありません(並列化の問題と言う)。スレッド数が倍になっても自動的に探索速度が倍になるわけではないということです(※一説には、実効的な探索速度はスレッド数の平方根以上程度と言われています)。この問題については、ここではこれ以上は深入りしません。以上、今回はミニマックス法における枝刈りについて解説しました。ここで記したのは、本当に基礎的な部分ですが、コンピュータがどのように“考えている”のかを知るための一つのきっかけとなってくれれば幸いです。lfics81電王戦で一躍有名になったものの一つに「評価値」というものがあります。これはコンピュータが考える局面の形勢を数値化したものであり、歩一枚が100点程度になるように規格化されています。ちなみに、歩が100点というのは、コンピュータチェスのセンチポーン(1点=歩兵の100分の1)に由来しています。機械が計算する値なら、電卓のように、局面を入れればポンと決まった値が出てきそうな気がしますが、実際の評価値は時間が経つと共に数値が更新されていきます。これはコンピュータが“考えている”からなのですが、一体、何をどうやって“考えている”のでしょうか?実は、局面を入れればポンと出てくる値というのはちゃんと存在していて、「静的評価値」と言います。機械学習等で作るのは、この値を計算する関数(静的評価関数)です。コンピュータは、この静的評価値に基づいて、先の手を読んで(探索と言う)、評価値を更新していきます。いわゆる「評価値」というのは、読んだ先の局面の静的評価値のことであり、それ故に、探索が進むにつれて値が変わってくるわけです。この辺の手法というのは、意外と人間に近い感じがします。「静的評価値」が“一目の判断”に対応していると考えると、それに基づいて先の展開を読んで、形勢を判断したり、指し手を決めたりするということ自体は人間のやり方と同じです。それでは、実際にコンピュータはどのように探索を行っているのでしょうか?もちろん、技術の詳細は複雑であり、また、ソフトによっても違うわけですが、今回は最も基本となる仕組みである「ミニマックス法」について解説します。先の展開を読むためには、自分の指し手の方針を決め、また、相手の指し手を予測しなければなりません。いわゆる戦略が必要になります。自分の指し手については、最も評価値の高い局面(“最善手”と言う、本当に最善であるかは神のみぞ知る)を選択することにします。序盤では定跡ファイルの登録手を用いたり、対人ゲームでは擬似乱数によって手をばらけさせたりというようなこともありますが、ここでは最善手のみを考えます。相手の指し手については、相手が自分であると想定して、相手にとっての最善手(こちらの評価値を最も下げる手)を指し手として予測します。「なぜベストを尽くさないのか」というわけです。このように両者が最善手で応じると考えると、先の展開を読むことが可能になります。この戦略を「ミニマックス法」と言います。「ミニマックス」とは「最小(min)となる最大損害(max)」という意味であり、将棋は2人で指すものですから、こちらのミスをなくしてひたすら耐えていれば、その内に相手がミスをして有利を築けるだろうと考えていることになります(※ここでの「耐える」というのは将棋の攻め/受けとは別の概念であり、攻めでも受けでも、得をするためにやるのではなく、損をしないためにやっているということです)。ちなみに、将棋の場合には「自分の損害」=「相手の利益」ですので(零和と言う)、「最小となる相手の最大利益」と言い換えることもできます。ただの言い換えですが、受ける印象は変わります。「損害」と「利益」というのは、原点と符号だけの違いですので、「最大(max)となる最小利益(min)」と言い換えることもでき、この場合は「マクシミン」戦略と呼ばれます。この辺は様々な書き方ができるので混乱の元になるのですが、本質は同じことです。それでは、具体的にやってみましょう。簡単のために深さを3に固定して、以下の図のゲーム展開(ゲーム木と言う)における3手の読みを考えてみます。左が出発局面(根ノード)で自分の手番(青色)とします。そこから、指し手の候補が2つに分かれて、右側の相手の手番(赤色)の局面となり、さらに分岐して右へ右へと展開していきます。右端の末端局面(葉ノード)にある数字が、その局面の静的評価値です。静的評価値の数値は、こちらが優勢となる正の値が多いですが、中には負の値となってしまう変化も含まれています。両者最善の変化を探すには、以下の図のように、右端の末端局面から順番に遡っていきます。こちらの手番では最大値を選び、相手の手番では最小値を選びます。結果的に、一番上の変化が両者最善であったということが分かり(※後の説明のために、意図的にそういう順序にしています)、出発局面の評価値が+500点であるということも分かりました。ここで、「何で探索なんて行っているんだろう?」「探索なんてせずに静的評価値をそのまま使えばいいじゃないか」という疑問をもたれる方もいるかもしれません。確かに、探索を行っても最終的に使うのは末端局面の静的評価値なわけですから、静的評価値の確からしさが現局面においても末端局面においてもそんなに変わらないとすると、無駄に仮定をおいて現局面から離れていく分だけ、探索は評価値の精度を落としているだけという可能性もあるわけです。読み切りができる最終盤を除けば、探索をしない方がよいということも考えられます。実は、ここのところがミニマックス法が「戦略」である所以であり、仮に評価値の精度が向上していないとしても、少なくとも探索の範囲内においてミスをしないことが勝率に結び付くだろうという考え方なのです(※評価値の精度自体は変わらなくても、探索を行えば、探索範囲分の下限保証が付いた値になります)。ミニマックス法がどういう状況ならば「戦略」として正しいのかというのは非常に難しい問題なのですが、理論の話はさておき、現実のコンピュータ将棋においては探索の深さと勝率には強い正の相関があります。コンピュータ将棋におけるミニマックス法の有効性は実証的に示されていると言えます。ミニマックス法に基づくと、静的評価関数の良し悪しについても一つの指針が立てられます。それは「両者最善で指し手が進んだ時に静的評価値の変動が少ないものが良い」ということです。静的評価値の変動が少なければ、末端局面からさらに探索を進めたのと同様の結果をその分の探索をせずに得られることになりますし、また、次回に説明するように、探索自体もより効率的に行えるようになります。Bonanza式の機械学習においては、教師となる棋譜に基づいて、指し手がなるべく一致するように(かつ過剰に一致しすぎないように)静的評価関数を作成するわけですが、このやり方では、手に入る良質な教師棋譜の数に制限があるために、どうしても限界が出てきてしまいます。そこで、上記の方針を採用すれば、自らの探索結果を教師とすることで、Bonanza式の静的評価関数をさらに強化していく学習が可能になるわけです。この手法を確立したのは、筆者の理解では、NineDayFever(NDF)だと思います。上の例では深さを固定しているわけですが、これでは持ち時間のある対局には対応できません。最初は浅い深さで読んで、そこから徐々に深く読んでいくという反復深化の手法が採られます。末端局面で王手や駒取り等に手を絞った少量の探索(静止探索と言う)を行ったり、有望そうな局面について探索を延長したりというようなことも行われます。これらの技術についての説明は、ここでは省略します。上の例では、全ての局面を全幅的に探索して答えを出しているのですが、これは明らかに非効率的であり、平均分岐数が約80と言われる将棋においては、このやり方では深く読むことはできません。読む必要のない変化を切り捨てる「枝刈り」と呼ばれる手法が必須になってきます。次回は、この「枝刈り」について解説します。2:分岐の迷宮」の記事において、将棋の局面数について考察し、局面数が10の68~69乗程度であること、一手ごとの分岐に際して合流局面が非常に多いこと等を論じました。今回は、序盤の駒組みに限定すると局面数はどうなるのかということについて考えてみたいと思います。片方の駒組みの配置の数を考えてみましょう。簡単化のために、以下のような条件をつけます。持ち駒と成り駒は無し。手前から見て4段目まで、もしくは5段目までに配置を限定(それぞれ“4段駒組み”、“5段駒組み”と呼ぶことにします)。歩以外の駒は、手前から見て3段目までに配置を限定。配置は初期局面から移動可能な場所に限る。この条件では、歩や角の交換はありませんし、浮き飛車や腰掛銀もありませんので、かなり限定された駒組みということになります。いう計算だと思って見てください。10^{13}\]という結果になります。10^{27}\]という結果になります。5段駒組み同士の場合には、歩がぶつかっていたり、5段目で歩がかぶっていたりする局面も含まれてしまっていますが、これらの結果はそれぞれ下限と上限の見積もりに対応するものとお考えください。これらの局面数は、実感としては、どれくらいの大きさなのでしょうか?例えば、100万局面の定跡データベースは10の6乗ですので、それの10京(10の17乗)倍以上ということになります。これらの序盤の駒組みの局面についてデータベースを作ることを考えてみると、仮に10の25乗個の局面を収録し、1局面に1バイトの情報を保存するとしても、1TBのハードディスクが10兆台くらい必要になります。ちなみに、宇宙にある星の数は10の22乗個程度と言われていますので、それより少し大きいくらいとも言えます。ここで数えている局面のほとんどは、実際の対局には現れてこないものなのですが、それにしても「想像していたよりも大きい」と感じられる方が多いのではないかと思います。普段の対局ではお目にかかれない駒組みも、チェス960(フィッシャー・ランダム・チェス)のように初期配置をランダムに入れ換えた変則将棋を行うと出現するかもしれません。桂香以外の一段目の駒と飛車の初期筋をランダムにすると、普段の将棋からさほど離れない形で、様々な駒組みが見られそうな気がします。コンピュータ将棋で試してみても面白いかもしれません。それぞれの駒組みには初期局面からその配置を作るのに必要な最小手数が存在し、駒組みが局面内に現れるには、先手番と後手番がありますので、少なくともその手数の2倍の手数が必要になります。これを“最短手数”と呼ぶことにします。最短手数は、正確に計算しようとすると大変ですので、以下の近似で見積もります。駒ごとに初期局面から配置場所に移動する最小手数を算出して、全駒分を積算する(最短手数は最小手数の2倍)。駒の移動の際に他の駒の存在は考えない。移動の経路に利用できるマスは手前から見て4段目までに限る。この近似では、他の駒に邪魔されて余計な手数がかかる場合が考慮されていませんので、最短手数が少なめに出る傾向があります。駒組み数の最短手数分布を以下に図示します。青点が4段駒組みの場合、赤点が5段駒組みの場合の結果です。縦軸は駒組み数の常用対数ですので、10の何乗かを表しています。それぞれのグラフは、最初はほぼ線形で立ち上がり、4段駒組みは42手目、5段駒組みは52手目をピークとして減少に転じます。最短手数が多い方の局面は人間的に見て不自然な形がほとんどであると予想されますので、普通の将棋ではピーク付近までにそれぞれが駒組みを選択して開戦という流れになっているものと思われます。最後に、それぞれの駒組みを組み合わせた序盤の局面数の最短手数分布を示します。青点が4段駒組みの場合、赤点が5段駒組みの場合の結果です。局面数を計算する際には、必ずしも両者の駒組みの最短手数が一致しているとは限らず、片方が手損している局面も多く含まれてしまっています。そこで、両者手損がない局面に限定した場合の局面数も十字点で示しました(青が4段駒組み、赤が5段駒組み)。実際の将棋で現れうる局面数は、こちらの数字の方が近いと思われます。両者手損がない局面数(十字点)は、それぞれの駒組み数の2乗(対数では2倍)になっており、当然、ピーク位置なども同じです。これらの局面の中には人間的に見てありえないようなものが大量に含まれているわけですが、純粋な可能性としては、将棋の序盤の駒組みの局面にはこれだけの変化の余地がありうるということになります。グラフの最初の立ち上がりの部分に注目すると、10手で10の10乗程度になっておりますので、その付近の分岐数は10程度であることが読み取れます。全ての局面数ということでいうと、いきなり開戦という選択肢もありえますので、もっと大きくはなるのですが、この分岐数10程度という数字は、序盤で合流局面を除いた場合の平均分岐数の下限の見積もりを表すものと考えられます。以上、今回は序盤の駒組みにおける局面数を見積もりました。4段駒組み同士の場合は10の23乗程度、5段駒組み同士の場合は10の27乗程度という結果が得られ、また、10手目付近までの合流局面を除いた平均分岐数の下限値が10程度であるということも分かりました。最新コメント「最新トラックバック」は提供を終了しました。