将棋脳

まーくん様のリクエストりよりスレ立てです...

『掲示板の主催者さんが将棋ソフトの開発者とのことですので,開発者からのご見解もお聞かせいただけたらと思います.
将棋ソフトに関することで,主に分散処理の効率と評価関数,機械学習の効率等に関してです.』

投稿者: webMaster 投稿日時: 木, 06/24/2010 - 03:34 categories [ ]

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

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

読みと強さ (2)

>「同じソフト同士を対戦するならば深く読むほうが強くなります。一般に1手深く読めるなら(同ソフト同士の対戦で)2割勝率が上がると言われています。」

将棋ソフトの番付けが A > B > C とすれば、Bの深読みバージョンは当然 B深 > B となりますね… では B深 > A は可能か???

我の認識としては「可能であるが、どの程度深読みすればそれを達成出来るかは簡単には解らない」…と成ります。

ごく基本の「駒割り」だけでの評価関数でも十分深く読めれば「無敵」の領域に達することも不可能ではありません…ですが、検索に時間が掛かり過ぎてしまうので実際には無理な話です…よって評価関数を工夫することにより有限時間内での検索を実用的なものにしています。

私がぼけていました

webmasterさん

前回の投稿内容ですが,私がいつものようにぼけていました.

一番の関心事,つまり,私の直面している問題と言っても良いのですが,駒音掲示板にて,

秋に行われるソフトと清水さんとの対戦は,ソフト側の圧勝との論調が多かったと思います.その主な理由として挙げられていたのが
ハードの格段の進歩だったと思います.

私は,はたしてそうだろうかと感じました.ご説明で,分散処理の効率面は少しですが理解しました.

もちろん1回の対戦で優劣を決めることはできないと思います.ただ,人間側からすれば,時間切れを狙うゲリラ作戦をとれば(まあ,面子上プロができるかどうかは別にして)どうなるか?

強いソフトを作るという気は全くないのですが,何とか動く将棋ソフトを作ってみたいと思うようになりました.

様々な手法の解説を楽しみにしています.お時間が許せば,継続してお教えください.お願いします.

読みと強さ

> 要は,読めば読んだだけ,将棋ソフトは強くなのか?

以前書きましたが、

同じソフト同士を対戦するならば深く読むほうが強くなります。一般に1手深く読めるなら(同ソフト同士の対戦で)2割勝率が上がると言われています。」

...ここで重要なのは「同じソフト同士を対戦」の部分ですね。

将棋の「強さ」は相対的な順番付けです...対戦の結果を基に A > B > C... と決定します。これは絶対的な基準で優劣を決める競技(100M競走、重量挙げ、高跳び、etc.)とは「強さ」の種類が違います。

(続)

((追記))あと... 並列アルファ・ベータ法はまだ書くことがあるので機を見て再開ので...

さらなる疑問ですが

ありがとうございます.記載内容を調べながら読んでいるので,お返事が遅くなります.すいません.

まーくんが現実に直面している問題ではありません.純粋に興味からの質問です.お気に障ったらお許しください.

さて,次が一番の疑問点です.webmasterさんは,将棋ソフトを開発しているとのこと.そこで開発者としてのご見解をお願いいたしたいのですが,

要は,読めば読んだだけ,将棋ソフトは強くなのか?

と言うことです.この場合,読めば読んだだけというのは,局面を数値化すると理解してください.たとえば,50手先まで読んで指し手を決める
PCと10手先まで読んで指し手を決めるPCとどちらが強いのかということです.

50手先まで読んで指す方が強いように思うのですが,何か違うような気がします.

確かwebmasterさんの記述で,時間scaleを同じとして,数手先を読めれば勝率は上がるとの内容を読んだように記憶しています.

これはPC同士の対戦ですよね.素人のバカな意見でしょうが,たとえば,PC対人間の場合,この場合の人間は,基準は不明確ですが
一応,プロとします.そのプロが,敢えて,極端に不利にならない程度のまるっきり攻めないというような将棋の常識にない手を去る程度
指し続ければ,これをソフトは的確に評価して,自らが有利になる手を選択できるのでしょうか?

並列処理 (3)

まーくん様へ...お褒めの言葉、ありがとうございます。どの程度役に立つかは解りませぬが出来る限り尽力させて頂きます。あと、まーくん様の「現実の問題」を差し障りの無い程度で説明して頂ければ我なりの考察をここに記してみます。

>「各合法手に1コアを使用した並列検索...仕事を80分割するから検索時間は80分の1...最悪でも50倍くらい速くなる!!!」

上記の手法は

「1コアが80手各手を検索する時、80個分のの仕事があり、マルチ・コアなら分業(各分業がほぼ同じ時間を消費すると仮定する)すればあっという間に出来上がり」的観測による予想なのですが仮定に致命的欠陥があります。

問題は以下の部分です...

「各分業がほぼ同じ時間を消費すると仮定する」

力任せの検索
http://f.hatena.ne.jp/issei_y/20090117163830

...1コアのCPUで(「力任せの検索」のテクを使用して)アルファ・ベータ検索をした場合、実際の消費時間は

①最初の数個のノード 70~80%
②残り 20~30%

...程度におさまります。

アルファ・ベータが普通のミニ・マックスより格段に速い理由は

「検索しないでよい部分は切り捨てる」

...に拠ります。1コアによるアルファ・ベータ検索は...

(A) 最初のノードを検索...これにより「基準値」を確立
(B) 残りのノードの検索は「基準値」を使用して検索の切捨てを行いながらの検索(もっと良い手が見つかったら「基準値」の更新もあります)

...となります。

上記のマルチ・コアによる「80分割法」では(A)の恩恵が起きないので各コアが一手進めた所から独自に最大のレンジで検索します。これは言い換えると、「80分割法」では各コアが(一手進めた状態から検索するので) N-1 の深度で検索するのと同等です。

すなわち、 「1コアで10手読む」 仕事を 「80コアで一手進めた状態から検索するので各コアで9手読む」 に置き換えた事になります。

「力任せの検索」によれば...検索の深度が一つ増える度に3倍の時間が掛かります。逆に言えば検索の深度が一つ減る度に3倍の1の時間に短縮します...ですね。

((結論)) 「80分割法」は分業により検索深度が一つ減るため検索時間が3分の1に減ります(つまり、3倍速になります)。

おもしろいです

スレッドに関しては,webmasterさんの前提で結構です.

必要に迫られて新しい概念をソフトウェア化していました.コードを書くのに必要な知識は,ほぼ書籍で独習(力業)したので,正規の知識などはありません.

>結果から述べると「せいぜい3倍」が関の山ですね。

コア数が増えてもそれに応じて(数に応じて)増えるわけではないと,経験上,感じていました.論理的に説明できないのが残念ですが.

たとえば,80個のコアを想定し,そのうち1個を管理用,残りで指し手を計算させたとします.その際に79個の指し手を計算するコアがほぼ同時に
計算を終えれば,非常に,効率的な期がします.ただ,実際にそうなるかですね.そのには,ソフトウェア的に計算時間が各コア均等になるように,処理の割り振りが必要ではないかと感じていました.私にはどうして良いか,見当が付かず,これが,マルチコア(CPUでも何でも良いですが)対応のアプリケーションは簡単に書けるのか?とい疑問です.

私の疑問の前提がおかしいですかね?

並列処理 (2)

>OSから見れば「マルチ CPU」、「マルチ・コア」は同様に「複数のCPUがある環境」と認識されその扱いに違いはありません。

...さて、並列処理バージョンのアルファ・ベータ法を実装するわけですが、今回は以下の仮定をします。

①局面における合法手の数は80とする。
②使用するマシンは(有り得ないけど)ものすごくゴージャスな「80コア(!!)」マシンです。

この設定で一番最初に頭に浮かぶ方法は

「各合法手に1コアを使用した並列検索...仕事を80分割するから検索時間は80分の1...最悪でも50倍くらい速くなる!!!」

...なのですが、そうはいきません。

結果から述べると「せいぜい3倍」が関の山ですね。(今回は80コアを同時稼動する際に起きうる弊害を無視します...それを加味するともっと落ちるでしょう。)

(続)

並列処理

>...さて「将棋ソフトの検索」ではどの程度「分割・分散」が可能なのか?

http://f.hatena.ne.jp/issei_y/20090117163830

現在将棋ソフトの検索に使用されるアルゴリズムの基本中の基本は「アルファ・ベータ(Alpha-Beta)法」であり、並列処理無しでも(評価関数が優秀ならば)ある程度の強さは達成できます。

並列処理の考察としてまず最初に(一番取り組みやすい)「マルチ CPU」、「マルチ・コア」から始めます...

「マルチ CPU」...は文字通り複数のCPUを一台のマシンに搭載します。高い処理能力が要求されるサーバー用です。
「マルチ・コア」...は複数のコア(CPU)を一つのCPUのチップに押し込みます。個体でのCPUの速度増加が頭打ちとなった現在流行のパッケージですね。

...両方あわせて、「マルチ マルチ・コア」も当然あります。当然値段もお高くなります。

OSから見れば「マルチ CPU」、「マルチ・コア」は同様に「複数のCPUがある環境」と認識されその扱いに違いはありません。

(続)

それでは...

一応我はコード書いて飯食っていますので、出来る範囲でお答えいたします。その過程で質問もありますのでその時はお願い致します。

>マルチCPUがWinNT上で何とか動いていました.そのマルチCPUを効率よく使おうと,様々なコード上の工夫及びコンパイラーの変更
>(開発環境を変えた)の変更などを行いましたが,実行速度は,なかなか向上しませんでした.

この場合の「工夫」は「マルチ・スレッド*を使用」を含む...と仮定してよろしいですか?

*「マルチ・スレッド」の意味・解説は以下より
http://e-words.jp/w/E3839EE383ABE38381E382B9E383ACE38383E38389.html
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%AC%E3%83%83%E3%83%89_%28%E3...

------

「分散処理」を行うには...当然のことですがその仕事が分割出来なければ意味がありません。これはアルゴリズムの領域となります。

さて、どのような仕事が「分散処理」に向くでしょうか?

①部屋のお掃除...これは仕事を分割しやすいので人数分に比例して速度を上げることが出来ます(限度はありますが)。

②生卵を茹でる...これはどう頑張っても10分程度かかります。鍋を10コ用意しても調理の速度は不変ですね。

...さて「将棋ソフトの検索」ではどの程度「分割・分散」が可能なのか?

(まだ勤務中なので...続)

ありがとうございます.それでは,

管理人さん,ありがとうございます.

将棋のソフトを題材にして,ソフトウェア処理技術に関していろいろご教示をいただけたらと思います.

まず,分散処理に関して.

私は,必要に迫られてWindows上のソフトウェアをWinNTぐらいからVB,VCで力任せに書いています.始めた当時は,マルチCPUがWinNT上で何とか動いていました.そのマルチCPUを効率よく使おうと,様々なコード上の工夫及びコンパイラーの変更(開発環境を変えた)の変更などを行いましたが,実行速度は,なかなか向上しませんでした.

清水女流との対戦に使用される機械のOSはUNIXですね,マルチCPU(ノード)で動かすとして,最適化せずに期待する処理速度が出るものなのでしょうか?まず,これが疑問.

最適化は行うのでしょうが,そんなに簡単(短期間)にできるのでしょうか?

UNIXでは,アプリケーション側で最適化を行わなくても,OSで処理してくれるのでしょうか?その際のチューニングは必要なのでしょうか?

なぜ処理速度にこだわるかというと,その局面局面を何らかの形で数値化して,指す手を決めているのでしょうが,これ処理を,評価せずに指し手を選ぶアプローチは無いのでしょうか?

漠然とした質問で申し訳ありませんし,用語の間違いがあればお許しください.

将棋ソフトの見解

...もう少し的を絞っていただけますか?

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

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