対戦相手を作ろう!

※コミュニケーション能力的な話ではない

この記事はSYSKEN Advent Calendar 2017 21日目の記事です。

はじめに

卒研で死にそうな手羽先です。~~記事のネタがなくて死にそうでした。~~
記事についてですが、コミュニケーション的な話でもないですし物理的に人間を作るとかいう話でもありません。ゲームにCPUを実装しようというお話です。私は毎年のようにボードゲームのようなものを作ってますが、毎度対戦相手がいないとプレイできないという不親切設計だったので試しに簡単なものを実装してみることにしました。

ゲームについて

対戦相手を作るゲームはこちら、弥生祭に出したゲーム「Reberslide」です。

ルールは基本的にオセロと共通ですが違う点として

盤面の端から石を投げ入れていく
石がぶつかると石の場所が一つずれる
石の置き方が相手の石を返せる場所のみにおけるオセロと違い返せない場所でもおける

となります。
パスが起こることがありませんし、別に角に置かれても返せます。

どのように考えさせるか

適当なところに打たせても一応ゲームはできますが、それではあまりにもお粗末です。
そこである程度考えた手を打つようにします。ただこのゲームはどのような考えで手を打つのが正しいのか僕自身よくわかってないので今回はひとまず最も多くの石を返せるところに打つようにしました。

この考えだけで動かしたものが上の動画になります(後手がCPU)。

時間がなくてここまでの実装で力尽きてしまいましたが、本来なら相手がどのように動くかも予測させるべきです。
ひとまず1手のみ予測させるとすれば「その位置に打った時に自身が返せる駒の数」と「その後の盤面で相手が返せる最大の数」の差分を求めて判断させたいところです。そのために探索を行うのがベストです。

探索について

探索とは現在の盤面をはじめとし、自身と相手の打つ手によって変化する盤面から最適解を見つけることです。
探索の様子を図であらわすために、「ゲーム木」（下図）を考えます。
ゲーム木では、局面を節点（図の丸）であらわし、手を枝（節点を結ぶ線）であらわします。
図では、青い丸が自分の手番のときの局面を、赤い丸は相手の手番のときの局面を表します。
一番下の節点を葉と呼び、葉に書かれている数字はその局面での評価値をあらわします。

図1. ゲーム木