リバーシのアルゴリズム

本書では、多くの人のなじみの深いリバーシを題材に、思考ゲームを解くプログラムの作り方を解説します。本書を一通り読めば、思考ゲームが極めて単純な原理、すなわち Minimax アルゴリズムに基づいて手を選んでいるということが分かるはずです。

思考ゲームのプログラムは、盤面を読んで次の一手を選ぶという単純な原理で動いています。『リバーシのアルゴリズム』 (Seal Software 著、工学社 (I/O books)、2003 年 6 月 18 日発売) は、リバーシを題材に、その原理をボードの表現、探索アルゴリズム、評価関数の 3 つに分けて設計と実装まで解説する書籍です。副題は『「探索アルゴリズム」「評価関数」の設計と実装』で、ソースリストは C++ と Java の併記、CD-ROM が付属します。版元はコードに詳細なコメントを付けたことを挙げ、入門者や中級者にも参考になると案内しています。

ボード実装から定石まで、全 6 章の構成

本文は全 6 章です。1 章「イントロダクション」でリバーシとプログラミング言語の選択を整理し、2 章「ボードの設計と実装」で石とボードの表現、石を打てるかの判定、着手と取り消し、ゲーム終了とパスの判定を Board クラスとして組み上げます。3 章「探索アルゴリズム」は最善手決定の概要から Minimax アルゴリズム、alpha-beta 法、negamax 法、NegaScout 法へ進み、先読み手数と AI クラスで締めます。4 章「評価関数」は終盤の単純な評価に始まり、得点テーブル、着手可能手数、開放度、確定石、辺、パターンを用いたテクニック、パラメーターの最適化までを扱います。5 章「定石」では座標の変換と定石探索の実装を、6 章「ゲームの実装」ではコマンドライン版と GUI に向けた指針を取り上げます。動く対戦プログラムを最後まで組み立てる流れの本です。

Minimax から NegaScout へ、探索を速くする理由

ゲーム木探索の出発点である Minimax は、自分の手番では評価値が最大の手を、相手の手番では最小の手を選ぶと仮定して木を読み下す方法で、実装は 再帰 で自然に書けます。ただし素朴に全部の枝を読むと、読む手数を 1 手増やすごとに局面数が分岐の数だけ掛け算で増えます。alpha-beta 法は、すでに見つかった手より悪いと確定した枝を読まずに打ち切ることで、同じ答えをずっと少ない局面数で得る方法です。negamax 法は、相手の評価を符号反転で表して最大化と最小化の 2 つの処理を 1 つにまとめる書き方で、NegaScout 法は最初に読んだ手が最善だと仮定して残りの手を狭い窓で確かめ、仮定が外れた時だけ読み直す工夫です。どれも手を読む順序がよいほど効果が大きい手法です。3 章はこれらを Minimax から順に並べ、その後に「その他の技法」と「先読み手数」の節を置いています。

評価関数の作り込みと、2003 年刊という前提

探索をどれだけ速くしても、読み切れない局面では評価関数の質が強さを決めます。4 章に並ぶ着手可能手数、開放度、確定石、辺は、リバーシの評価で古くから使われる特徴量で、目先の石数よりも、相手の打てる手を減らし、ひっくり返されない石を確保する方向へ指し手を導きます。ボードを オブジェクト指向 のクラスとして設計しておくことは、評価関数や探索の部品を差し替えて強さを比べる時に効いてきます。一方で、本書は 2003 年刊で、目次に並ぶのは Minimax から NegaScout までの古典的なゲーム木探索と、特徴量を組み合わせる評価関数です。モンテカルロ木探索やニューラルネットワークによる評価は目次に現れないため、それらを学びたい場合は別の本が必要です。アルゴリズム本全体の選び方は アルゴリズム本ガイド が参考になります。

自分で対戦プログラムを作りたい人に向く一冊

この本が向くのは、C++ か Java でクラスと関数を書いた経験があり、教科書で見た探索アルゴリズムを動く形で確かめたい人です。石を打てるかの判定という足回りから、探索、評価関数、定石、対戦プログラムの完成までを 1 つの題材で通して追えるため、各手法がどこに効くのかを実装の差として確かめられます。ゲーム木探索と評価関数の考え方は 2 人で交互に指す完全情報ゲームに共通するため、リバーシ以外の思考ゲームを作る前の足場としても、古典的な手法を一通り自分の手で組んでおく価値があります。