石取りゲームで遺伝的アルゴリズムの実験 その1

著者：北本 敦

公開日：2021/03/10

最終更新日：2021/04/10

カテゴリー：技術情報

タグ：石取りゲームで遺伝的アルゴリズムの実験／遺伝的アルゴリズム

北本です。

遺伝的アルゴリズムが最近話題になっていたので、自分でも試してみようと、簡単なゲームを学習させて勝率を上げていく実験をしてみました。

ゲームの概要

ルールがシンプルかつ評価方法が明確ということで、以下のようなルールの石取りゲームをやらせてみることに決めました。

・石が21個ある。
・2人のプレイヤーに交互にターンが回る。ターンが回ってきたら1～3個の石を取らなければならない。
・最後(21個目)の石を取った方が負けとなる。

実はこのゲーム、残りの石の数が(4の倍数 + 1)以外の時に自分にターンが回ってくれば必勝することができます。残りの石の数が1個の状態で相手にターンを回せば勝ちなので、まず、自分のターンで残りの石が2個の時に1個、3個の時に2個、4個の時に3個取れば勝ちが確定します。また、残りの石の数が5個で相手にターンが回った場合は、相手が1個取れば残り4個、2個取れば残り3個、3個取れば残り4個で自分のターンが回ってくるので、どの取り方をしても前述の必勝パターンに持ち込めます。すなわち、残りの石の数が(4の倍数 + 1)の状態で相手にターンを回すような取り方をすれば必勝できるわけです。よって、このゲームは石が(4×5+1)個なので後手が必勝できます。

手法

今回の遺伝的アルゴリズムの実験では、各個体に現在取り終わった石の数がｎ個の状態で自分のターンになった場合に石を何個取るかの情報を遺伝子として持たせます。要素数21の配列を用意し、(n + 1)番目の要素に取り終わった石の数がｎ個の場合に自分が取る石の数を1～3の整数値で入れる感じです。ただし、存在する石の数を超えて取らないよう、20番目の要素は1か2のみ、21番目の要素は1のみが入ります。21番目の要素は値が固定なのでなくても問題なかったですが、あった方が実装がしやすくなるかなと敢えて用意してみた次第です。

1世代あたり、前述のような遺伝子を持った個体が100個存在するものとし、大まかには、以下のようなアルゴリズムを実行していきます。

①まず、第1世代の100個体をランダムな遺伝子情報で生成する。

②現世代の各個体に、ランダムな方法で石を取ってくる対戦相手と100試合(先手50試合/後手50試合)ずつ石取りゲームさせ勝ち数を記録する。

③計10,000試合が完了したら、勝率の高い個体を選択(そのまま次世代に残す)したり、勝率の高い個体が高確率で抽選されるような形で2個体を親に選択して交叉して子を生成したりして、次世代の個体を100個用意する。ここの詳しい方法については後に取り上げることとします。

④現世代を③で生成した次世代に置き換えて②へ。

②～④の繰り返し実行することで、勝率の低い個体が淘汰され、勝率の高い個体の遺伝子が生き残っていくことになります。

予想

上記②～④の操作を繰り返していくことで、前述した必勝法を踏まえ、遺伝子のパターンが下表のような形で収束していくのではないかと予想しました。

取る石数を「?」と記した残り石数が(4の倍数+ 1)の箇所は、必勝パターンがないのでどのような値に収束するのかわかりません。

また、残り石数が少ない箇所ほど早い段階で収束していくだろうと予想しました。特に、残り石数2個の時に2個取ったり、残り石数3個の時に3個取ったりするような自滅パターンはかなり早期に淘汰されるだろうと思いました。

プログラムについて

C++でプログラムを書きます。
コンソールで動くだけのプログラムでも実験は可能ですが、UIがあった方がわかりやすいですし、何よりも自分自身の達成感が大きいと思うので、現在業務でも触っておりますMFCを使って画面も作成することにしました。先に完成品を提示することになりますが、以下画像のようなものをつくります。

画面には最後に実行した試合の結果が表示されます。

• 「1試合実行」ボタンを押すと、試合が1回だけ実行されます。
• 「1個体分実行」ボタンを押すと、現在の個体の第100試合までが実行されます。例えば、第11試合まで完了していれば、残りの89試合が一気に実行されます。
• 「1世代分実行」ボタンを押すと、現在の世代の100個体目の第100試合までが一気に実行されます。
• 「リセット」ボタンを押すと今までの記録を破棄し、第1世代の生成からやり直します。

「記録閲覧」ボタンを押すと別ダイアログが開き、
一つの世代において、ある遺伝子にあるパラメータを持つ個体がどれぐらいの割合を占めているかをグラフ化した「全個体統計」

各世代各個体の遺伝子のパラメータと試合の勝利数を表にした「遺伝子情報」

を閲覧することができます。

結構凝ってしまい、遺伝的アルゴリズムの処理そのものの実装より時間を掛けてしまったかもしれませんが、UIについては本題ではないので、ここではあまり詳しく解説しないことにします。

では、次回からは、具体的なコードの内容などを紹介していきたいと思います。