アルファ・ベータの並列化 (Parallelization of Alpha-Beta Algorithm)

...に2週間程悩んでおりました。何をすれば良いのか解っていましたが(少なくともそのつもり)、それを達成するコードが全然見えませんでした。やっと見えてきたので忘れる前に記録しておこうとの次第です。

...I have been struggling with this problem for past two weeks. Although I fully understand what needs to be done (perhaps, I may be entirely misdirected), but materializing the code that accomplishes the task is a different matter. It appears that a feasible solution has been found and it's recorded here.

以前並列化について実験を行いましたが、

http://www.tokinclub.com/dp/node/566

この手法ではコア数が一定数以上だと演算時間の減少が頭打ちになり、大枚はたいて購入したマシンが生かされていません。

(問題点)

新マシン(i7 920)は8スレッド使用して(即ち、8分割)検索を高速化...の予定でしたが、そう簡単には収まりません。なぜかと言えば「各個の検索に必要とされる時間は均等では無い」からです。(怒)

従って、一つのスレッドに比較的長い検索時間が必要でも(枝刈りが起きないため...すなわち最善手)他のスレッドは助けられないためアイドル状態になっていることが発見されました。

since my previous attempt in parallelization,

http://www.tokinclub.com/dp/node/566

I realized this approach does not scale well beyond 2 threads. as a result, my new machine is severly under-utlized.

(Issues)

with i7 920, the original expectation was to split the search in 8 ways... however, the actual performance was unsatisfactory; amount of time consumed for each thread was not uniformly distributed. as a result, one thread remains executing while other threads completed their work and sit idle.

なぜ日本語と英語の二本立てなのか?並列化ですから...

投稿者: 紫外線 投稿日時: 月, 09/21/2009 - 21:24 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

根尽き果てました...

これ以上検索をスピードアップするのは(今の所)我には無理ダス。

初手から8手読みです。検索を8方に分けて行った結果です。

{SEARCHED: 3}{TIME: 1.872 sec.}
{SEARCHED: 3}{TIME: 1.919 sec.}
{SEARCHED: 5}{TIME: 1.95 sec.}
{SEARCHED: 3}{TIME: 1.966 sec.}
{SEARCHED: 4}{TIME: 1.966 sec.}
{SEARCHED: 5}{TIME: 1.95 sec.}
{SEARCHED: 5}{TIME: 1.965 sec.}
{SEARCHED: 1}{TIME: 3.401 sec.}

{TIME: 4.836000 sec.}{RATE: 8,620,382.340778 nodes/sec}
{NODES: 41,688,169}{CUT: 33,980,801}{HIT: 100,504}

各個の時間を総合すると16.994秒...理論的限界は8で割って2.12425秒ですか...道は遠いです。でも毎秒860万局面なら十分だと思う。

新アルゴリズムは理論的にはスバラシイかったのですが上手くいきませんでした。数ヵ月後に再トライです。

((やらなければならない事リスト))

①評価関数を実装・改良する(理論は完成(?)しました)
②枝切りの理論を練る
③Ponder(相手の手番中に考える)を実装する
④定跡ライブラリーを完成する

(追記)

ちなみに2コアのラップトップでは

{TIME: 8.455000 sec.}{RATE: 3,935,298.994678 nodes/sec}
{NODES: 33,272,953}{CUT: 27,445,843}{HIT: 69,841}

...となります。

まだ書き終わっていないのに...

...コメントは如何なものかと思われますが...

ここ数日新マシンでテストを繰り返していましたが、最大負荷で走らせているとランダムにマシンが凍結するという症状が出て我は立腹でございました。

あれこれ試して、ぐにょぐにょ調べた結果、RAMの電圧不足が原因と判定。BIOSから昇圧したら安定しました。ふぅ~。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。