こんにちは。
CG^2研のやけぬる(@jken_ull)です。

新刊展示ではこんな感じのゲームを展示していました。
無題2

↓ゲームの動画


ルールは
・同じ色を4つ並べると消える
・連鎖すると相手におじゃまブロックを送ることができる
・ウィルスを全部消すと勝ち
・ブロックが置けなくなると負け
という感じのゲームです。

制作期間は新歓展示まで半月でした。だらだらと短期間制作なのです。


今回はパズルのAIについて少しお話しようと思います。
先週のrogyゼミで話したことと似たようなお話です。


AI(人工知能)とは、人工的にコンピュータに人間のような知能を持たせようとすることを指します。
今回のゲームではパズルを解くAIを作りました。


では、どうやって解くのかを簡単にお話します。

AIにパズルを解かせるときには、出来る限りクリアできるようなやり方をさせたいと思いますよね。
比較
上の図の例でも、左の置き方よりも、右の置き方をさせたいですよね。

今回のゲームでは置く場所を決めていくわけですが、配置していくブロックは何個か分かっているだけで、それ以上はランダムに決定します。
そのため、事前に全探索してクリアできるように配置の仕方を決めよう、というわけにはいきません。
そこで、与えられたブロックの情報から、より良い配置の仕方を決定していくことになります。
今回は評価関数を使うことにします。

評価関数とは、ゲームの状態を評価して数値に変換する関数のことを言います。
その評価した値を見て、ゲームの状態をより良くするように進めていきます。

今回の場合は、
・できるだけ同じ色を並べていくようにする
・4つ並べると消すことができる
・連鎖したほうがよい
・ウィルスを優先的に消す
ということを意識して評価関数を考えることができます。

例えば、あるブロックを座標xに置いた時の評価関数を
g(x) = { (消せるブロックの数) + 10×(消せるウィルスの数) }×20×(連鎖する数) + (並んでいる同色ブロックの数)
という感じで定義します。
そして、すべての座標xでこの関数で評価してみて、g(x)を最大にする座標xに配置する、としておきます。
これでも、そこそこ良い感じのAIになります。

他にも、何個か先を見たり、乱択アルゴリズムなどいろんなアルゴリズムを使ったり、ゲームの状態によって評価関数を使い分けるなど、いろんなやり方があります。

評価関数はこうすれば必ず強いという定石はなく、プログラマの経験や理解の程度に影響します。
作り方によってAIの強さが変わるので、きちんと調整する必要があります。


最後に、AIを作るにあたって大切なことを書いておきます。

判定を時間内に終わるようにする
探索するAIでは、より多く探索していくと強いAIが作れるのですが、調べすぎて時間内に終わらないことがあります。
今回のゲームの場合、AIとして分かっている4個のブロックの配置状態をすべて探索するようにすると、その時の最適な置き方が分かり強いAIが作れるのですが、時間的に膨大な時間がかかります。 
この時、メインルーチンで処理している場合には、探索処理が時間内に間に合わないと次の処理に移れないため、ラグが発生してしまいます。
ラグはプレイヤーのゲームプレイのテンポを崩したり、誤操作してしまう原因になってしまうため、できるだけ避けたいものです。
また、別スレッドで処理している場合にも、探索処理が時間内に終わらない時でもブロックは動き続けるため、ゲームの状態によっては計算が終わる前に配置が決まってしまう可能性があります。
そのため、うまく枝刈りする(無駄な計算をしないようにする)などの処理を行い、探索の時間を減らす必要があります。
最悪の計算時間でも時間内で終わるようにAIを作るようにしましょう。

強すぎず、弱すぎず
AIは作り方によってはすごく強いAIができたり雑魚なAIができたりします。
強すぎるAIを作ってしまうとプレイヤーの心が折れてしまい、弱すぎるとプレイヤーにすぐ飽きられてしまいます。
これではゲームとしてあまり良くないものになります。
きちんと調整した、ほどほどの強さのAIがちょうど良いのです。


今回の話はここまでです。


次のゲームは何作るか決めてませんが、工大祭にはきっと何かできてると思うのでお楽しみに。
ではでは _(:3」∠)_