aki.の月記

■[将棋] 疑似乱数を利用したdf-pn探索の簡易分散並列計算

GPWで見た保木さんの発表がお手軽で面白そうだったのでやってみました。

https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=78266&item_no=1&page_id=13&block_id=8

要はdf-pnにちょろっと乱数を加えた複数のクライアントがそれぞれ探索してみて、一番早く結果が返ってきたのを採用、という感じです。

C#版のBlunderでの実装は、↓こんな感じになりました。

とりあえずテーブルを用意しまして、、

[Blunder/SearchMate/AndOrTree.cs]

        public struct RandEntry { public int P, D; }
        /// <summary>
        /// 乱数テーブル
        /// </summary>
        /// <remarks>
        /// 疑似乱数を利用したdf-pn探索の簡易分散並列計算
        /// https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&amp;active_action=repository_view_main_item_detail&amp;item_id=78266&amp;item_no=1&amp;page_id=13&amp;block_id=8
        /// </remarks>
        public RandEntry[] RandTable = new RandEntry[1024];

新規節点で固定深さ探索をした結果のp, dに対して、ハッシュ値で表を引いてpかdを1bitシフトする感じに。

[Blunder/SearchMate/AndOrTree.FDS.cs]

            // 乱数を加算
            if (minD < Infinity) {
                var t = RandTable[context.HistoricalHashValue & 1023];
                p <<= t.P;
                d <<= t.D;
            }

乱数テーブルを埋めるところは↓こんな感じです。

    for (int j = 0; j < randTable.Length; j++) {
        uint rand1024 = rand.NextUInt() & 1023;
        if (rand1024 <= 50) { // 5%くらいの確率でP=1, D=0
            randTable[j].P = 1;
        } else if (rand1024 <= 100) { // もう5%くらいの確率でP=0, D=1
            randTable[j].D = 1;
        } else {
            // P=0, D=0 (乱数無し)
        }
    }

そしてコレをコア数分だけスレッド作って実行する処理をUSIEngine.csのgo mateのところに実装して、将棋所の「詰」ボタンで動くようにしてみました。

そして6コアで6並列で、そのうち1個は乱数無しにしていて、それ(オリジナル)と、6並列のうち1番早く答えが出たもの(最小)について、節点数と実時間を出力するようにしてみまして、試しに将棋図巧の1〜20番を解かせてみたところ、こんな感じに。

1,4,6,8は解けそうになかったので諦めました。_no

そして14番が凄い事になってますが、乱数の種を固定していなかったので再現性のないデータになってしまいました。(まぁ、オリジナルが回り道しすぎているだけの気もしますが)

最後に、無駄にフルセットな実行ファイル・ソース一式はこちらに。

http://tqzh.tk:24497/site/blunder/Blunder-EasyDistrDFPN.zip