組込み屋でもアプリがしたい！ 第4局

プログラミング

「オメーの読みは『浅い』んだよ。手当たり次第に読んでくからムダ読みが多い。読みの量は多いが、そのほとんどがゴミだ」
（『りゅうおうのおしごと！５』）

アルファ・ベータ法

これまで、読みの探索アリゴリズムはミニマックス法を採用してきました。ミニマックス法はn手先までのすべての手を読んで最善手を選びますが、その大部分がムダ読みです。今回はアルファ・ベータ法を実装しました。アルファ・ベータ法は、それ以上読む必要のないムダ筋を途中で切り飛ばします。読みの深さが同じなら計算結果はミニマックス法とまったく同じですが、計算時間を桁違いに短縮できるので、そのぶん読みを深くすることができます。


ミニマックス法では6手先読みが僕のPCでは時間的に限界(思考時間が最大1分以内)でしたが、アルファ・ベータ法では8手先読みまでできるようになりました。また、時間を測定するためにチェスクロックの機能も実装しました。
図

スマホアプリと勝負

恥ずかしながら、もはや僕では太刀打ちできないので、スマホアプリと勝負させて強さを測ることにします。（自動で勝負できれば良いのですが、僕がPCとスマホを人力で操作しての勝負です。）
スマホアプリはAndroidのUltima Reversiを使用しました。かなりダウンロード数の多いアプリで、レベル1からレベル10まで強さを設定できます。何度か対局してみたところ、結果は次のようになりました。

  • 読みの深さ=6：Ultima Reversiのレベル4以上、レベル5未満
  • 読みの深さ=7：Ultima Reversiのレベル5以上、レベル6未満
  • 読みの深さ=8：Ultima Reversiのレベル6以上、レベル7未満

読みを深くすることで確実に強くなっているようです。

今回のソースのスナップショット

今回のTIPS

Stopwatchクラスの経過時間を取得するElapsedプロパティはTimeSpan構造体です。
TimeSpan構造体は、DateTime構造体と同様に、書式つきでToStringすることができます。
ただし、どういうわけか書式指定文字列の仕様がDateTime構造体とは異なるので要注意です。

    DateTime dateTime = new DateTime();
    TimeSpan timeSpan = new TimeSpan();

    Console.WriteLine(dateTime.ToString("hh:mm:ss.ff"));
    Console.WriteLine(timeSpan.ToString(@"hh\:mm\:ss\.ff"));