JavaScript (29) 囲碁プログラムの本質

今日はちょっと JavaScript からはちょっと離れますが、囲碁プログラムとは数学的にどういうものかを考えてみたので、書いてみたいと思います。これは今月行われたゲームプログラミングワークショップ2013に参加してインスパイアされたものです。
一言でいうと囲碁のプログラムとは全局面の集合から次の一手の集合への写像、関数、あるいは演算です。
まず頭の準備体操としてビット演算を例に考えてみます。ビット同士の演算として　AND, OR, XOR などがありますが、全部で16通りあります。これは2つのビットの組み合わせが00から11まで4通りあって、その4通りに対する演算(の結果)はたとえば0000のように4ビットで表せます。したがってすべての演算の組み合わせは0000から1111までの16通りになります。

【図26 ビット演算の組み合わせ】
さて囲碁の次の一手を求める演算ですが、演算のパラメータとなる局面の組み合わせは、各交点に黒石があるか白石があるか空点かの3通りの状態が交点の数だけ組み合わされるので、たとえば9路盤の場合は交点が81なので、3⁸¹通り（ありえない局面も含む）となります。これに対し81交点のどの点に打つかというのが次の一手を求める演算なので、交点に0から80までの番号を振ったとすると、3⁸¹通りの局面に対する演算は0,0,0,…,0(全部で3⁸¹個の0)から80,80,80,…,80(全部で3⁸¹個の８0)まで組み合わせで81³⁸¹通りあります。

【図27 全ての局面に対して次の一手を決める演算の組み合わせ】
この演算のうちの1つ(白、黒それぞれ)が神の手と呼ばれる最善手のはずです。ただしこれをプログラムにすると初手は必ず同じ交点に打つことになります。
囲碁のプログラムを作るということは本質的にはこの81³⁸¹通りの作戦のうちのどれかを選ぶことと同じになります。
なお、この数字はいろいろはしょってます。石を置く以外にパスと投了を加えると83³⁸¹通りになりますし、白黒のアゲハマの個数の差たとえば-81から+81までによって手を変える場合はさらに、83^(381x163)通りになります。