以前の記事「ミニマックス法とは何か? 2:アルファベータ枝刈り」では、アルファベータ法の解説を行いました。ここでは、アルファベータ法の筆算方法について詳しく紹介します。手法の原理については上記の解説記事をご覧ください。

まずは基本的な事柄を整理しておきます。

各局面には探索の下限値(α)と上限値(β)が与えられており、1つ先の局面(子ノード)の探索結果(評価値、もしくは評価値の存在範囲)を得るたびに、探索の範囲が狭められていきます。各局面における探索範囲の変化を追いかけていくことがアルファベータ法の肝となります。

自分の手番においては、子ノードの評価値が下限値よりも大きければ、その評価値を新たな下限値として更新します。結果的に、全ての子ノードの探索が終了すると、最終更新値は子ノードの評価値の最大値となり、それがその局面の評価値となります。ただし、一度も更新されない場合には、全て下限値以下であったということですので、「α↓」というのが探索結果となります。また、上限値を超える更新があった場合には、その時点で探索を打ち切り、「β↑」を探索結果とします(※この時には、評価値は上限値以上である同時に、更新値以上でもあるので、さらに評価値の存在範囲を狭めることもできますが、今回の探索においては余分な情報になりますので切り捨てます)。

相手の手番においては、逆に、子ノードの評価値が上限値よりも大きければ、その評価値を新たな上限値として更新します。その他も、自分の手番の場合の逆になります。

実例で見ていきましょう。下図のゲーム木は上記の解説記事のものと同じものです。

abh_00

図中の各ノードには下限値と上限値が並べて書いてあり、確定値には下線を引きます。探索によって、下線のない数値を更新していくというのが基本的な作業になります。

初期局面の探索範囲は負の無限から正の無限までの全ての範囲にしてあります(※図中の「INF」は無限の意味)。子ノードの初期の探索範囲は、その子ノードの探索開始時の親ノードの探索範囲を引き継ぎます。例えば、初期局面の最初の子ノードの初期探索範囲は、初期局面の探索範囲を引き継いで、全範囲となります。

各局面を順番に展開していくと、右上の末端局面で「+500」の評価値が得られますので、その親ノード(自分の手番)の下限値が「+500」に更新されます。

abh_01

続いて、2番目の末端局面の評価値は「-200」であり、下限値の「+500」よりも小さいので、下限値は更新されません。この段階で子ノードの探索は終わりですので、最終下限値の「+500」が評価値として確定します。この確定した評価値により、さらに1つ前の親ノードの上限値が「+500」に更新されます。

abh_02

さらに進めていくと、3番目の末端局面の評価値は「+700」であり、上限値以上ですので、探索は打ち切りで「+500↑」が親ノードの探索結果となります。この場合、さらに1つ前の親ノードの上限値は「+500」のままで変わりません。

abh_03

初期局面の最初の子ノードの評価値が「+500」で確定しましたので、初期局面の下限値が「+500」に更新されます。さらに探索を進めると、6番目の末端局面は「+200」であり、下限以下ですので更新はされません。

abh_04

7番目の末端局面も「-100」と下限以下で更新されず、親ノードの下限値は更新されないままに子ノードの探索が終わりましたので、「+500↓」が探索結果となります。これにより、さらに1つ前の親ノードの上限値が「+500↓」で更新されますので、下限以下となり、探索は打ち切られて、初期局面の評価値が「+500」で確定します。これにて探索は終了です。

以上、今回は、アルファベータ法の筆算方法について紹介しました。実際に手を動かしてやってみると、何となくアルファベータ法の感覚がつかめてくると思います。

筆算というのは、技術としては必ずしも役に立つものではありません。人間のやることには必ずヒューマンエラーが伴いますので、計算はできる限り自動化される方向にあります。コンピュータの発展により、四則演算はもうとうに人間がやるべきことではなくなっていますし、複雑で高度な数式計算ですら、数式処理ソフトで計算するのが当たり前の時代になってきています。しかしながら、人間が概念を学習するためには手を動かす作業が有効であり(不思議なことですが)、代わりの学習方法が出てくるまでは、筆算の教育的な価値が失われることはないと思われます。