AIのアルゴリズム

アルゴリズムとは

近年、将棋の電王戦のように、コンピュータと人間が対決するというニュースをよく耳にするようになりました。この時、コンピュータはいったいどのようにして戦っているのでしょうか？（次の一手を導いているのでしょうか？）

将棋やオセロのように、二人のプレーヤーが交互に一手ずつ行動するゲームを考えてみましょう。このとき、コンピュータに対戦相手をさせるとすると、コンピュータには強いものから弱いものまでさまざまな強さのレベルが存在します。このコンピュータの強さを決定するものは何でしょうか。コンピュータの行動を決定させるためには、「どのように行動するか」を示したプログラムが必要となります。このプログラムの中の「どのように」を決めるものがアルゴリズムです。つまり、アルゴリズムはある状態では「１」の行動を選択し、別の状態では「２」の行動を選択するというような、次の行動を決定するまでの手順のことを示します。

すなわち、アルゴリズムの良し悪しによってコンピュータは強くなったり弱くなったりするのです。

アルゴリズムの重要性

将棋などのゲームの単純なアルゴリズムとして自分と対戦相手が取り得るありとあらゆる手順をすべて挙げて、最も勝つ可能性の高い一手を選択するというものが考えられます。ですが、このアルゴリズムでは莫大な計算時間がかかってしまい、ゲームが進みません。

具体的には、将棋ですべての手を考えるとすると10の226乗の手を考える必要があります。これは、1秒間に1京（10の16乗）手考えられるスーパーコンピュータを用いても、10の202乗年以上かかってしまいます。宇宙の寿命が約137億（10の10乗）年と考えられているので、この計算は、宇宙が滅びても終了しません。
このように、全通りの手を考えることはできないので、いかに限られた時間の中で最善の一手を導かせるかが課題となっています。その中で、コンピュータに学習させ、局面がどれだけ自分に有利かを判断させる方法や、数手先の手を読み、次の手を考える方法などが考えられ、さまざまな工夫を凝らしたアルゴリズムについて長年研究が行われてきました。

アルゴリズムの例

では、実際の将棋などのゲームで使われているアルゴリズムの例を少し挙げます。皆さんが実際にゲームでコンピュータと対戦するとき、どのようなアルゴリズムが使われているか考えてみると面白いかもしれませんよ！

ランダム

この方法は、自分が選択できる手の中からランダムに1つ選ぶアルゴリズムです。

貪欲法

貪欲法とは、定められたある基準に基づいてその場その場で最善となるように次の1手を選択するというアルゴリズムです。

min-max法

min-max法とは、想定される最大の損害が最小になるように次の一手を決定するアルゴリズムです。一手を決定するために、数手先までのすべての局面を考え、局面がどの程度自分に有利かを点数づけます。そして、最も点数の高い手を選択します。

例えば、上の図のような差し手が常にAかBの2通りである仮想のゲームにおいて、3手先までのすべての手を読むアルゴリズムを考えてみましょう。一番下の数字は、考えられるすべての盤面についての点数を表しており、点数が高いほど自分に有利であることを示します。まず、3手先の点数に着目します。その前の手(2手先)は自分の手番なので、自分が有利となるようにそれぞれの盤面で、AとBを比べ大きい方の点数を引き継ぎます。次に、さらに1手前(1手先)に着目すると、相手の手番であるので、相手は自分に最も不利となる手を選択すると想定し、小さい方の点数を引き継ぎます。そして、最終的に自分の次の手として、大きい方の点数の手を選択します。図では、赤線で示すように次の手を決定します。

モンテカルロ法

モンテカルロ法とは、乱数を用いて計算やシミュレーションを行う方法です。原始的なモンテカルロ法は、ある局面で、コンピュータが乱数に従い、2人の仮想プレイヤーを演じて終局まで対戦します(プレイアウト)。プレイアウトを複数回実行することで勝率を計算することができ、一番高い勝率となる手を選択するという方法です。この原始的なモンテカルロ法と他の方法を組合せることで、さまざまな強さのコンピュータを作ることができます。