スポンサード リンク

T.Ishii's Software Library

HTML5 レトロ風ゲーム館

無料ブログはココログ

« Bookにも仕上げが必要 | トップページ | AVX2版は共通化 »

結局は評価データ

ここの所、EdaxとMasterReversiとのエンジン対局を行いつつ、MasterReversiのFFO性能を向上させてきたのだが、既に纏め作業に入った。今回のバージョンアップでは、評価データと評価関数の微変更も入るのだが、FFO性能に関しては、評価データだより、という所もある。

MasterReversiのFFO性能は、結構、高速な筈だ。

何故なら、開発終了時点、つまり、2005年くらいには高速と言われていたWZebraの完全/勝敗読み性能を、少なくとも今時のPC上で比較すれば、何倍も上回っているからだ。

MasterReversiの完全/勝敗読み性能がWZebraのソレを何倍も上回っている理由は、大きく分けて三つある。

その一つは、WZebraの評価関数はシングススレッド動作であるのに対し、MasterReversiのソレはマルチスレッド動作を行っていて、マルチコアCPU環境では、コア数の増加に伴って処理性能が向上する、という事にある。

その二つ目としては、2005年というのは、まだ、64BitOSの時代ではなかったので、WZebraは32Bitアプリとして構築されているのだが、MasterReversiには、64BitOSに最適化された64Bit版が存在している、という事になる。

その三つ目としては、2005年には、既にSSE2命令が使えるCPUが存在はしていたものの、MMXレジスタを使う命令の2倍のクロック周期が必要だったりしたために遅かったので、WZebraではSSE2命令は積極的には使われていなかったのだが、MasterReversiでは、SSE2命令ばかりではなく、AVX2命令まで使う格好になっているので、その分、高速処理が可能になっている訳だ。

と、いう事で、MasterReversiのFFO性能はWZebraのソレよりも今時のPC環境では何倍も高速になっているのだが、リバーシ用の完全読みプログラムなんてモノは、それほど難しいモノではない。

具体的には、このブログでも何回か書いてきた筈なのだが、作者が最初に購入したPCはNECのPC-6001になるのだが、作者的には、それ以前に、ツクダオリジナルのコンピュータオセロ機で遊んだりもしていた訳だ。

なので、PC-6001を購入すると、理系の大学生よろしく、サインカーブなんかの数式のグラフ表示を行ってみたりしていたのだが、同じくらいの感覚で、自前のオセロプログラムを作って遊んでみたりもしていた訳だ。

で、普通に鑑みれば、オセロプログラムで難しいのは、コンピュータの思考ルーチンになる訳なのだが、終盤の完全読みに関しては、全ての組み合わせを試して最高の結果が得られた着手を選択すれば良いだけな訳だ。

つまり、通常時の思考ルーチンよりも、終盤の完全読みの方が簡単にコーディングできた訳なので、作者製の最初のオセロプログラムでも、完全読みをしていた訳だ。

もっとも、作者的には、PC-6001用ソフトの開発時には、そのCPUである所のZ80用のアセンブラも使えたのだが、前述のオセロプログラムについては、Basicで記述していた。

そして、使えるメモリも少なかったので、あまり深い読みも出来なかったので、完全読みといっても、残り3箇所か4箇所程度が限界だった様に記憶している。

いずれにしても、上記の完全読みルーチンは遅かったのだが、その理由は、今時の人なら当たり前のモノと考えている筈のαβ検索すらしていなかったので、完全読みでは、文字通り、全ての着手進行を完全に読み切って答えをだしていたからだ。

と、いう事で、MasterReversiの完全読みが高速なのは、その前提として、当然の事ながら、αβ検索を使っているから、というのもあるのだが、この辺のテクニックについては、WZebraも同様だ。

更に言えば、MasterReversiの完全読みでは、最初から完全読みを行っている訳ではなく、まずは、枝刈りを行いつつ、正しそうな着手進行に目星をつけている。

何故、そんな事をしているのか、というと、αβ検索時には、そのウインドウ幅は狭い方が高速に処理できるので、最初から、ウインドウ幅は1で正解を探す格好にしておいた方が、より高速に結果が得られるからだ。

もっとも、こういった検索のやり方についても、WZebraも同様の手法を取っている。と、いうか、WZebraがそんな感じのやり方をしていたので、後発のMasterReversiとしては、そのやり方を何となく見習った、みたいな所もあった訳だ。

そして、実際の所、上記の様な方法を採用していると、並列演算時に複数のスレッドに同時に検索を行わせても、普通にαβ検索を行わせる場合と比べると、損害は軽微になる。

何故なら、αβの検索窓のサイズは最初から1なので、無駄な検索は殆ど行われないからだ。

もっとも、αβ検索で最も効率が良いのはヌルウインドウサーチになる訳なので、上記の様な方式を採っている場合にも、最善値が早期に見つかった方が有利ではある。

何故なら、最善値が見つかれば、その時点で、検索窓のサイズを0に出来るからなのだが、実際の所、目論見通りに事が運ぶのであれば、最善手以外の検索窓のサイズは最初から0にしておく事も可能だ。

それでも、全てが目論見通りであれば、何ら問題のない完全/勝敗読み結果が得られるのだが、実際には、目論見通りに行かない事も多い。

具体的には、意外と、準備検索で得られた最善値は正しかったものの、最善手は間違っていた、なんて事も多いので、こういったケースでは、最善手以外のウインドウも開いておくと、検索リトライが発生しないので、より高速に処理が終わったりする訳だ。

と、いう事で、今時の完全/勝敗読みというのは、闇雲に全ての着手進行を網羅的に検索している訳ではないので、実際の所、処理性能に大きく影響するのは、各着手を行った場合の評価値の精度、という事になる。

なので、結局は、評価データの良し悪しが処理性能を大きく左右する事になるので、今回、評価データについても変更を入れている訳だ。

« Bookにも仕上げが必要 | トップページ | AVX2版は共通化 »

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/534482/66814472

この記事へのトラックバック一覧です: 結局は評価データ:

« Bookにも仕上げが必要 | トップページ | AVX2版は共通化 »

2018年10月
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

広告

プライバシーポリシー

  • 当サイトでは、第三者配信による広告(Google Adsense)サービスを利用しています。

    Google を含む第三者配信事業者は、Cookie を使用して、ユーザーのウェブサイトでの閲覧履歴に基づく広告を配信します。 Google 広告 Cookie を使用することにより、Google や Google のパートナーは当サイトや他のサイトへのアクセス情報に基づく広告をユーザーに表示できます。

    収集された情報がGoogleによってどの様に使用されるか、収集される情報をユーザーが管理する方法については、以下のリンクを参照下さい。

    ポリシーと規約 - Google