Darkside(リンクエラー修正しました)

2014年1月12日(日) 18:49

スクリプトで探索

 虱潰し探索をスクリプトで記述する場合、再帰呼び出しの使用がほぼ必須となる。だから、プログラミングの初心者にはluaを書くのは難しいと思われる。
 自分も lua では初めてなので言語仕様の理解不足から思わぬ罠にハマるかと危惧していたが、大筋ではすんなり動作した。C言語仕様の痛恨と言われる「セミコロン必須」が無いとか、関数の帰り値を複数持てるとか、かゆい所に手が届いている新し目の言語だけあって、再帰記述でトラブルを起こすような仕様にはなっていないようで一安心。

 キー入力の探索木を記述する際には、途中経過をステートセーブせねばならない。探索木を戻るときにステートロードしないと、兄弟木を伸ばせない。
 幸いにして BizHawk のluaではファイル名を指定してのステートセーブが可能なので、保存数の制限に引っ掛かることはない。ただし、ノードごとにロードするため動作速度が上がらない。この問題がなくてもエミュレーターを動作させて探索するため、コンピューター将棋みたいに毎秒何万回なんて探索はできない。
 せいぜい毎秒数回というレベル。

 ここで問題となるのは、1人ゲームだという点。
 オセロや将棋のような2人対戦ゲームの先読みを行う場合、プログラムは複雑になる。しかし、相手の手番では探索量を減らすテクニックがあれこれ存在する。これに対し1人ゲームにはそのようなテクニックがないため、探索量が多くなる。これで探索速度は遅いのだから、虱潰しと言いながらそれほど虱潰しできない。あれこれ制約を設けないと、現実的な時間で探索が終了しない。
 例えばアクセルとブレーキと何も押さないという3通りが可能であっても、ブレーキは押さないことにして探索から除外。押すパターンにも制約を設ける。 

 本来CPUによる力ずく探索は、人間なら考えないような常識外れの最適解を発見できるのが魅力である。ところが、常識的に普通はやらないキー入力は除外しておかないと、探索に時間が掛かり過ぎる。ちょっと放漫にスクリプトを組むと、探索終了まで何日?なんて話になってしまう。
 10フレームでもキー入力が3通りなら、3の10乗で6万通り近いパターンになる。キー入力を2択にしても、20フレームなら100万通りを超える。1秒あたり数通りしか探索できないのに!
 先日、内部速度を特定の値に一致させようとして奇数偶数の罠にハマったが、現実の
SFC F-ZERO ではキー入力の前後が入れ替わっても速度は変わらないことが大半である。

 僅かな例外を拾うための全パターン網羅は、効率が悪過ぎる。

written by higashino [ゲーム] [この記事のURL] [コメントを書く] [コメント(0)] [TB(0)]

この記事へのトラックバックPingURL

Comments

TrackBacks

Darkside(リンクエラー修正しました)

Generated by MySketch GE 1.4.1

Remodelling origin is MySketch 2.7.4