ニップのCPUアルゴリズム

ニップのCPUのアルゴリズムだが、考えても考えても妥当な評価値マップがわからない。
もうしょうがないからとりあえず作ってみて後で調整することにした。
一応作ってみたのは下のような感じ。
なるべく最外周の石を取りに行くようにする。



ゲーム序盤、中盤は、上の評価値マップによる評価と、相手が指すことが可能な選択肢の数を、重み１：１でミックスすることにした。
探索の深さは１。マシンスペックに依存したものにしたくないから。

ゲーム終盤（45手以降～）は、単純に石の数を評価値とする。探索の深さは３か４。選択肢は十分少ないから。

とりあえずこれで実装してみる。

ニップの評価関数

OpenNipというソフトウェアのCPU対戦機能として、現在のバージョンでは次の２つのアルゴリズムが実装されている。
１．ランダムアルゴリズム・・・指せる全ての手の中で、ランダムに選択する。
２．最大手アルゴリズム・・・指せる全ての手の中で、もっともひっくり返せる数の多い手を選択する。

上記２つはアルゴリズムとして単純で、実に簡単に実装できる。

が、お世辞にも強いとは言えないので、ミニマックス法により手を決定するアルゴリズムを実装してみた。
ミニマックス法とは簡単に言うと、考えられる最も大きな損害を最も小さくするような手を打つ、というもの。
ちなみに評価関数は単純に自分の石の数とした。

で実際に実装してみて、探索する深さを４つにしてみたら、OutOfMemoryErrorが発生した。
深さを３にしてみたらエラーは出ないものの、弱い。上の２のアルゴリズムにも負ける。
自分の実装が下手糞なのかもしれないが、これ以上効率よくするのも大変なので、違う方法を思案中。

ここでリバーシの評価関数を参考にしよう。

１．盤面上の各マスに評価値を与え、その総和を取る。
２．相手の打てる手の選択肢の少なさを評価する。
３．確定石の数を評価する。

ニップの最大の特徴は角がなく、外周は円形でありその周上もひっくり返すことが可能であることである。
そのことを考慮すると、

１の方法は、角がないため各マスの評価値はリバーシと大きく異なるだろう。ただし妥当な評価値マップを作れれば有効と思われる。
２の方法は、リバーシでもニップでも変わらないと思われる。これは有効。
３の方法は、ニップでは確定石がリバーシに比べて極端に少ない。あまり有効ではないように思える。

ということで、１と２をミックスした評価関数を作成することを目標に、妥当な評価値マップを考えていくことにしよう。