E500BASIC高速化のすべて
PART 5 アルゴリズムの見直し
PART4の(2)について考えていきましょう。
PART2で書いたように同じ割合で高速化可能な場合処理時間がかかる部分ほど高速化の効果は大きいのですがPART4のような省略化や簡略化ではかなりの数を改善しないと目に見える効果は得にくいです。複雑な処理をしていればかなりの処理時間がかかるためアルゴリズムの改善によって目に見えて高速化ができる場合があります。
アルゴリズムとは何かというと手順のことです。「三角形の面積を求めるには底辺に高さを掛けて2で割る」「テストの平均点を求めるにはテストの全員の点数を足して人数で割る」などの決められた手順が存在するというのが分かると思います。それらは三角形の面積を求めるアルゴリズムとテストの平均点を求めるアルゴリズムといえます。
では、次の計算式を見てください。
３６×７×２５
これを暗算で計算するというのは結構大変ですが、乗算は計算する順番を入れ替えても変わらないためにそれを入れ替えて計算すると次のようにできます。
２５×３６×７＝２５×４×９×７＝１００×６３＝６３００
プログラムではないのですが、単純な四則演算でさえ順番を入れ替えるだけでも高速に演算が可能になるというのが分かると思います。これがプログラムであれば同じ結果を得るためのアルゴリズムは多数存在するためその中から最適なものを選ぶことで高速化ができるのです。
例えば[1][3]のキーを交互に押すタイプのゲームがあった場合、その交互押しの部分だけを取り出すと下記のような感じになったとします。
10 F=1:X=0
20 K$=INKEY$
30 IF K$="1" AND F=3 THEN X=X+1:F=1
40 IF K$="3" AND F=1 THEN X=X+1:F=3
50 GOTO 20
|
30行・・・[1]を押し、前回[3]を押しているならば押した回数に1をプラスする
40行・・・[3]を押し、前回[1]を押しているならば押した回数に1をプラスする
|
このように前回押したキーを押したキーを記憶することで交互に押すという判定が行えるようになっています。ここで変数Fの数値において1と3を入れ替えた場合はどうなるでしょう。
10 F=1:X=0
20 K$=INKEY$
30 IF K$="1" AND F=1 THEN X=X+1:F=3
40 IF K$="3" AND F=3 THEN X=X+1:F=1
50 GOTO 20
|
これでも同じように交互押しの判定ができてしまいます。この場合のFの値は前回押したキーではなく今押さなくてはならないキーと考えれば分かりやすいでしょう。
ここで、30行は両者とも1、40行は両者とも3となっているために文字変数K$を数値化すればANDを等号にすることにより2つの行を1つの行にまとめられそうですね。あと問題はFの値が3と1で交互に入れ替わっているのですが、これはF=4-Fという式を使えば実現可能であるため次のようになります。
10 F=1:X=0
20 IF F=VAL INKEY$ LET X=X+1:F=4-F
30 GOTO 20
|
100m走のゲームで私が良く使っているキーの交互押しテクニックはこうやって生まれました。キーを交互に押すだけのごく単純なものでもそのアルゴリズムは1通りではないということが分かったと思います。
別の例を挙げるならば、じゃんけんの勝敗判定のアルゴリズムも相手の手と自分の手を見比べて勝ちか負けかを判断するという単純なものにも関わらずその方法は1つではありません。ごく単純に考えればIF文が9個必要になりますが、判定アルゴリズムを変更することで非常に簡単になりますからね。
上記のキーの交互押しやじゃんけんの勝敗判定のように汎用的に書かれている部分を専用化するということは高速化において有用になる場合が多いです。汎用性の高いアルゴリズムは他に使い回しが効くというメリットがありますが、速度面では不利になることが多いため汎用性が高く万能なものは高速化という観点から言うと無駄が多いとも言えるわけです。
少し複雑なものについて考えていくことにします。
例えばGPRINT形式の画像データの圧縮に関して過去に討議したこともありましたが、圧縮アルゴリズムというのは無数に存在します。ポケコンで行うのであれば処理速度や使用メモリも重要となるために選択肢が限られるのですが、それでも作る人によって大きく異なっているのが分かると思います。
ポケコンの場合は処理が遅いから速度を最優先するのがベストと言いたいところですが（というか、今回はBASICの高速化について書いているわけですし）、プログラムリストのサイズ、メモリ消費量などを考慮しなければならないこともあります。前述のデータ圧縮ではデータ圧縮によって必要なデータが圧縮されていても解凍ルーチンのサイズが大きければその意味は全くなくなってしまいますからね。私が考案したOGEはその辺のバランスを重視しています。
一般的にアルゴリズムの例としてとりあげられることが多いソート（並べ替え）ですが、ソートのアルゴリズムは多数あり、例えばクイックソートはバブルソートと比べ桁違いに速いと思っている人が多いでしょう。しかし、これも上記のGPINT形式の画像圧縮と同じく重視すべき点が何なのかを把握し最も適したものを選択することが重要になります。あるゲームにおいて5人の得点が高い順に並べ替えるという場合、データ数が5個程度ならばクイックソートは速くありません。さらに、プログラムリストが長くなるというデメリットもあります。
ポケコンBASICにおいて処理速度は重要となりますそれが場合によってはベストな選択とは限りません。また、速度においても一般的に速いというものではなく自分が必要としている用途において速いものを選択するべきです。上記のキーの交互押しのように速度が速くなり、プログラムリストも短くなるというものになるのがベストですが、そのようなものは簡単には出来ません。
さて、アルゴリズムが重要なゲームといえば思考型ゲーム（ここでは対戦型ゲームの敵の思考ルーチンも含める）ですが、思考型ゲームの場合はアルゴリズムを変えた時点で強さが変わってしまい「オリジナルの動作を完全再現した上での高速化」ではなくなってしまいます。もしも、オリジナルのゲーム内容を全く変えることなく高速化（オセロで言えば特定の盤面におけるコンピュータの石の置き方が変わらないようにした上で高速化）をしたければアルゴリズムを変えるのではなく別の方法で高速化を行う必要があります。
しかし、ポケコンBASICで作られた将棋やオセロなどのゲームはその処理速度の問題からコンピュータの思考ルーチンが速度面で問題となる場合が多くあります。ボトルネック部分を解消するためには多少の動作変更はやむを得ないかもしれません。
少しでも強くするならば数手先読みを取り入れたいところですが、その競技に合ったプレイパターン（定石っぽいもの）を導入しておかないと下手な思考ルーチンでは数手先を読ませたところで強さはあまり変わりません。しかも、α-β法を用いたとしてもポケコンBASICで数手読ますのはかなり無理があります。せっかくのお手軽なポケコンゲームなのに1手に数分かかるようではプレイする意欲もなくなってしまいますからね。
よって、コンピュータの思考時間が長くなりがちなゲームを作る場合は、少しでも強くなるようなものよりも8割の強さを2割の時間で実行できるようなアルゴリズム（多少弱くなっても圧倒的に速くなるもの）の方が望ましいと私は思います。私も昔ポケコンでオセロゲームをいくつか作りましたが2手先読みをしたものと評価関数のみで先読みしなかったもののとでは強さに差はほとんど無かったという経験もあり、複雑な処理（≒時間のかかる処理）を行えば必ずしも強くなるというわけではないことが分かりました。確かに強さ優先で作るのもありですが、「BASICの高速化」について書いているので今回は不適当と判断しました。
1手に数秒〜数10秒かけても問題ない思考型ゲームならば思考ルーチンは待てる範囲内で強くすることだけを考えても良いですが、対戦型のアクションゲームなどでは時間的なゆとりはありません。キー反応の悪さをあまり感じないアクションゲーム（5cps以上）を作る場合は、思考ルーチンは数10m秒で抑えておく必要があります。この場合は、いかに効率よく端折るということが重要になってきます。
ここで問題となるのはその端折り方ですが、前述のように同じく複雑な処理（複雑な場合分け）を行えば強くなるというわけではないので思考ルーチンを4つパターンに分けているならば3つのパターンに変えてみるなどの方法を取ると良いでしょう。そのためにもそのゲームにおける動作を完全に把握しておく必要があります。
アルゴリズムを変えることによる高速化は場合によってはかなり大きな効果が望めるということが分かったと思います。しかし、勝敗判定やソート（並べ替え）などのように結果が重要なものでは高速化する前のゲームの動作をそのままで高速化できますが、コンピュータの思考ルーチンのアルゴリズムのように過程が重要なものはアルゴリズムの変更をした時点で動作が変わってしまうため動作を全く変えずに高速化というのはできません。その動作の変更が認められない人や変更を許容した上でさらに高速化したい人は次からの内容を参考にすると良いでしょう。
PART6に続く
PART 1 なぜBASICを高速化するのか
PART 2 効率的な高速化を行うためには
PART 3 BASICの高速化とは
PART 4 どうやったらBASICが高速化できるのか
PART 5 アルゴリズムの見直し
PART 6 メインルーチンの軽量化
PART 7 表示を高速化
PART 8 IF文をうまく使う
PART 9 「BASICだから遅い」は言い訳の言葉
RETURN
