GIPF

by 大原雄馬

情報提供者N.H.K.さんに感謝。

GIPFは2人用の対戦型パズルゲームです。運の要素は全くありません。京大シミュ研にあるゲームとしてはめずらしく、理論上は先手必勝か後手必勝かのどちらかというゲームです。「詰めもの」と呼ばれています。

プレイヤーは自分のコマを交互に盤面に置いていきます。コマの数には限りがあります。コマを置けなくなると負けです。盤面に同じ色のコマが一直線上に4個以上ならぶと、そのコマが手元に戻ります。このとき、そのコマと同じ直線上にあって、かつそのコマとつながっているコマも戻ってきます --- 4個以上ならんだコマと同じ色ならば。色が異なると、そのコマはゲームから除去されてしまいます。わかりやすく言えば、自分の色のコマを盤面に4個以上うまくならべれば、相手のコマを減らすことができるのです。こうやって相手を手づまりに追いこむのです。

このゲームのコンピューター版がここにあります。
http://gf1.sourceforge.net/

このプログラムのソースコードは C++で書かれているようです。むしろJavaに近いという印象を受けました。

コンピューターの思考ルーチンは伝統的なminimaxのようです。これは次のようなものです。

これから先のN手でルール上可能な手をすべて書きだす。
そのうちのひとつをとりあえずやってみる。
その結果、盤面がどうなったかを見て盤面を評価する。この評価がこの手に対する評価となる。
この手がいままで読んだ手よりもよければ、この手を仮採用する。

"だれにとって"なのかをきちんと説明するには再帰を使わないといけません。ここでは例でごまかします。

たとえばN=3で、いま白の番のときには次のようになります。可能な手(一般には 42通りあります)に1から42までの番号をつけておきます。まず

白黒白
1, 1, 1
1, 1, 2
...
1, 1, 42

をやってみます。このうち、白にとって最も有利な手を仮採用します。それを

1, 1, C1

と書きましょう。次に

白黒白
1, 2, 1
1, 2, 2
...
1, 2, 42

をやってみます。このうち、白にとって最も有利な手を仮採用します。それを

1, 1, C2

と書きましょう。以下同様にして

白黒白
1, 1, C1
1, 2, C2
...
1, 42,C42

を調べます。このうち黒にとって最も有利な手を仮採用します。それを

1, B1, C*

と書きましょう。このようにして

白黒白
1, B1, C*
2, B2, C*
...
42,B42, C*

がわかったら、このうち白にとって最も有利な手を選べばいいのです。相手が最善をつくしたとき(つまり、自分の点数がminimumのとき)の自分の点数を最大(maximum)にするというのがminimaxの語源です。

この原理は私が書いたマンカラのプログラムでも使われています。GIPFのほうはもうひと工夫あります。「制限時間いっぱい」まで読むらしいのです。("CPUがはやいほど強い"と説明文にあります。何手先まで読むかを固定していたらこうはなりません。)

問題なのは評価関数をどう書くか、つまり盤面をどう評価するかです。ソースコードのコメントを以下引用します。
BEGIN QUOTE

/* capturing a piece from your opponent is worth 20 points */
/* 1 point for each piece in use on the board */
/* 2 pieces or less left is getting dangerous */
/* one gipf left can be dangerous, subtract 5 points */
/* pieces closer to the center have a higher value */
/* normalize the result, should be between 1000 and -1000 */

END QUOTE
詰んだ盤面の点数は1000点(白の勝ち) または-1000点(黒の勝ち)のようです。 GIPFコマの点数は一般コマの1.5倍のようです。コマの位置による点数は

どまん中 5点
そのまわりの6マス 2点
その他 1点

のようです。