コンピュータ将棋の理論：アルゴリズム編
コンピュータ将棋って、どんなアルゴリズムを使っているの？
前回の記事では、コンピュータ将棋の基礎知識について書きました。
コンピュータ将棋の理論はディープラーニングの登場で大きく変化していますが、どんな分野にも言えることですが、まずは基礎をしっかりと理解するところから入りたいと思います。 ということで、コンピュータ将棋のアルゴリズムとしてどんなものがあるかを見ていきましょう。 先の記事で書きましたようにBonanzaの登場以降、コンピュータ将棋は、学習学習の本質は、如何にして上手な分け方を見つけていくか、ということであると説きました。 そうなんです、コンピュータ将棋のアルゴリズムも、分ける、というアルゴリズムで構成されています。 では、分ける、というアルゴリズムを見てみましょう。
まずは、探索アルゴリズムから
１）ゲーム木
将棋で自分の手番になったとき、指すことができる場所は複数存在しますよね。
その複数の場所の中から実際に駒を置くところを選びますよね。
これを繰り返してゲームが進んでいくわけですが、終わってみると選択肢はまるで
木のようになっていますよね。
コンピュータ将棋のアルゴリズムは、この木を調べてどのルートを通るかという
ことを決めるためのもので、この木のことをゲーム木と呼び、調べることを
探索と呼んでいます。
ゲーム木のサンプル
これがコンピュータ将棋のアルゴリズムの基本になります。
上の図の〇や▢の中には、局面の良さを数値で入れます。
この数値を決める関数を評価関数と言います。
評価関数は昔はプログラマが将棋の知識をもとに決めていましたが、
今は機械学習で決めています。
２）ミニマックス法
この方法は、一言でいえば、自分の手番は最良の手を選び、相手の手番では
最悪の手を選ぶためには、ゲーム木のどのルートを通れば良いかを探索する、
方法です。 これが名前の由来になっています。
決まった深さまでのところから上方向にそれを行っていきます。
これによりゲーム木における通るべきルートが見つかります。
でも、これはプロ並みに百手先まで考えるとなると時間がかかりそうですよね。
３）αβ法
ミニマックス法でやってみて時間がかかりすぎることに誰かが嫌になったので
しょうね。 αβ法とは、無駄な探索をやめるためのアルゴリズムで、自分の
子の値が自分の値を変えないと判った段階で子の探索をやめるというものです。
αβ法が現在の探索アルゴリズムの基本になっています。
次は評価関数
１）プログラマの将棋の知識
上で書きましたようにBonanza以前はプログラマがその人の将棋の知識を基にして
評価関数を決めていました。 人間ぽくって何だか好感が持てますね。
２）機械学習
機械学習を使って評価関数を決める手法はBonanzaで初めて使われました。
Bonanzaは、プロ棋士の棋譜を使って評価関数のパラメータを決めています。
プロ棋士の棋譜を使うという所から教師あり学習ということになります。
３）強化学習
最近のコンピュータ将棋では、プロ棋士の棋譜を用いて評価関数のパラメータを
決めるのではなく、コンピュータ将棋同士の自己対局の結果を用いて評価関数の
パラメータを決めています。 これを強化学習と言います。
凄いですね、想像もつかないです。
ざっとコンピュータ将棋のアルゴリズムの歴史を見てきました。 このことをベースに次にはディープラーニングについて見ていきたいと思います。
では、また。
（参考図書）
リンク
リンク
