プログラミング講座(32) モンテカルロの高速化

高速化に取り組んでひと月が経ちました。ちょっと行き詰っているので、いままでの経過をお伝えします。プログラムIDはGCS192で発行しました。例によって2000行を超えたため、コメント等を削除した他、棋譜ファイルの入出力部分を別のID DWG627で発行しました。棋譜の入出力を行う場合は、DWG627もインポートして組み込み、さらに、ファイルの入出力がコメント化されているので、[Ctrl]+Fキーで “commented” を検索しコメントの'(シングルクォーテーション)を削除してください。
高速化として行ったのはプレイアウトする際に、まず、盤上の着手可能な手をすべて求めてからランダムに着手していたのですが、着手までに時間がかかるので、次のように改めました。着手前は盤上の空点からランダムに並べた乱空点列を作り、その乱空点列に対して着手可能かどうかを調べて打つようにしました。次に、例えばプレイアウト数が4回のとき、すでに3勝1敗した着手可能手があった場合、他の着手のプレイアウトでは2敗した時点で勝率を上回ることができないので、プレイアウトを断念するようにしました。最後に、例えばプレイアウト数で全勝する着手可能手が見つかった時点で残りのプレイアウトを放棄してそこに打つようにしました。
その結果、2倍の高速化ができ、5路盤でも耐えられるようになってきました。下記のコンピュータ同士の対局が5分で終わります。

【図28 Random (乱数) vs CPU (モンテカルロ) 5路盤での対局再生結果】
今回も、デバッグ画面に現在プレイアウトしている着手可能手を表示し、さらに、その結果が勝ち(W)か負け(L)かも表示するようにしました。

【図29 デバッグ画面】
まだ、高速化の案としては、一手打つ中で着手禁止の判定と、着手後の囲われた石を取り除く処理の両方で四方の石が取れるかどうか判定しているので、まとめられそうだ、といったアイディアがあるにはあるのですが、画期的に速くなる確信がないので、ここで一段落することにしました。
Small Basicは配列が特殊な構造をしているため、処理がかなり遅いのではないかという疑念も湧いてきているところです。いろいろ考えた結果、この囲碁プログラムはSmall Basic向けとしては大きくなり過ぎてしまったこともあるので、「昇格する」という機能でVisual Basic言語の環境に切り替えて、性能を比較してみようと思います。もしかしたら、それが最も自然なアプローチなのかもしれないと思えてきたからです。
（つづく）