- 1 名前：デフォルトの名無しさん mailto:sage [2007/04/06(金) 15:33:11 ]
- できたらよろこんでやる。
前スレ
おまいら最強の将棋プログラムしてみろよ part5
pc11.2ch.net/test/read.cgi/tech/1109307327/
- 593 名前：デフォルトの名無しさん [2008/02/11(月) 16:07:36 ]
- 512や1024ならスワップ起こるよ
OS、ほかのプログラムが動いているとハッシュテーブルがメモリ外に出ることがある
するととても弱くなる
たとえばボナンザで実験するとわかる
- 594 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 18:13:57 ]
- >>580
rootでA,B,Cと候補手があるとして
BやCの評価値の評価値を並列に探索して求める場合はrootでsplit。
Bの評価値が確定してからCを探索する場合はrootではsplitしていない。
- 595 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 20:56:25 ]
- >592
デマというか、ハードウェアとかコンパイラに依存するので時代によって……
- 596 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 22:41:19 ]
- >>594
ありがとうございます
>BやCの評価値の評価値を並列に探索して求める場合はrootでsplit。
というのは直観的に理解できそうです
rootでとりあえず指し手を列挙してみて
おらこれとこれとこれがあるから行ってこいやぁ、みたいなw
でも
>Bの評価値が確定してからCを探索する場合はrootではsplitしていない。
というのがよくわかりません
この場合、どこで並列処理（並列化）をしているのでしょうか？
- 597 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 23:35:35 ]
- Bにも子供たちが…
- 598 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 23:46:07 ]
- てことは……
深さ0（？ 現局面のこと）で指し手を列挙して
おのおのの指し手について並列するのがrootでsplit
深さ0で指し手を列挙したあとその指し手の1つをまず取り出して
そこからの指し手（深さ1以下の指し手）について並列するのがrootでないsplit
ってことですか？
実際の方法論としては
たとえば候補手が50個並んでいて
CPU1が候補手aを、CPU2が候補手bを読んでいって
先に終わったほうが候補手cを読む……という「仕組み」自体はいっしょで
それをrootでやるかそうでないかだけが違う（というかYSS議論では違ってた）
ということでしょうか？
- 599 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 02:48:08 ]
- >>598
深さ0で指し手がA0、B0、C0と3つあるとすると、今のプログラムは
A0の手を調べるのに全体の50%の時間を使ってしまいます。
そこで、A0の探索が終わった後に、B0、C0の2つの手を並列に探索します。
その方がA0の探索の結果を使えるので効率がいいためです。
A0の手の下にはA01、A02、A03の3つの手があるとすると、
A01の手を調べるのにこれまた50%の時間がかかります。
そこで、A01の探索が終わった後にA02、A03の探索を並列に行います。
こうやって延々続いていきます。
深さ0でも並列に探索するのが「rootでsplit」で
深さ0でのみ並列に探索しないのが「rootでsplitしない」です。
「rootでsplitしない」場合でも深さ1、深さ2、、、、ではsplitします。
- 600 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 10:33:34 ]
- 並列化ド素人の自分だが
Aspiration searchの真ん中の値で二分すれば
単純に二倍速くなりそうという感じは受ける。
ちょっと試せないので分からないけど。
ボナンザも歩の交換値２つぶんでAspiration searchをやってるらしいので。。
やっぱり問題はその次からの一回の探索を分ける方法だねえ。
- 601 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 11:08:15 ]
- >>599
なるほど・・・
ありがとうございました
- 602 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 12:38:42 ]
- >>600
お前コンピュータ将棋もど素人だろ。
ウィンドウを２分割すれば探索ノードもキレイに２分割できると思ってる？
- 603 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 14:47:26 ]
- 逆に他の手法はきれいに二分割できるの？やろうとしてるの？
- 604 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 16:43:40 ]
- ただのPVS使ってるが少なくとも600のやり方よりは効率がいい。
ついでに書くと、MTD(f)の探索木みれば600がいかに効率悪いかわかる。
まぁ、俺は選手権の対局より強化学習の方を高速化したいから、並列探索は手抜きだがな。
- 605 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 18:49:22 ]
- 書き忘れてた。>>604のPVSはPV Splittingの方。
- 606 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 19:30:13 ]
- あーなるほど、2つほど勘違いしてた。
600をやって他もできると思ってたら、できないねえ。
ノード数が二分できないのではなく、ノードが二分できないのか。
同じ局面を二回作ってるから二で割って一と。
- 607 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 19:44:07 ]
- そーゆー事だ。
- 608 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 19:48:54 ]
- >>599に補足すると、「rootでsplitする」場合だと、B0とC0を並列に探索するのでB0,C0の評価値が求まるまでの時間は長くなる。
「rootでsplitしない」場合だと、B0の子ノードOR孫ノードORもっと先のノードで並列化するので、B0の評価値は「rootでsplitする」場合より速くも止まる。
んで、仮にA0の評価値＜B0の評価値だと、B0の探索終了時に「B0は（最善手ではないかもしれないが）少なくともA0よりは良い」と分かる。
なんで、「rootでsplitしない」場合は、「仮の最善手」が速く決まる可能性が高い（YSSの掲示板だと「見切り発車」とか表現してた）から、思考時間に制限がある場合にちょっとお得、と。
- 609 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 19:49:53 ]
- すまん、二行目の「も止まる」は「求まる」だった。
死んできます。
- 610 名前：デフォルトの名無しさん mailto:sage [2008/02/12(火) 19:58:06 ]
- まあ、そんなに簡単なら話にも出てこないか。
でも並列化ってイメージしにくいような気がする。
頭を両手で同時に洗うのは並列化？
- 611 名前：デフォルトの名無しさん mailto:sage [2008/02/13(水) 00:31:48 ]
- もちろんそうだが，タスクの分割が自明な例だな
- 612 名前：デフォルトの名無しさん mailto:sage [2008/02/13(水) 19:04:11 ]
- 例えばフライを揚げる時、衣付ける人と揚げる人の二人でやる事あるだろ？
そういうのが並列処理。
- 613 名前：デフォルトの名無しさん mailto:sage [2008/02/13(水) 19:19:45 ]
- その例えは誤解の元
- 614 名前：デフォルトの名無しさん mailto:sage [2008/02/13(水) 19:52:42 ]
- >>612
それはCPUのパイプラインだ。
並列処理なら、フライパンを二つ用意しなきゃ。
もっとも、将棋の場合は揚げなくてもいいものがあるから、
二つ用意しても倍は速くならないのだ。
- 615 名前：デフォルトの名無しさん mailto:sage [2008/02/13(水) 19:54:02 ]
- >613
どういう点が…と聞いてみようと考えたら分かった。
>612の例えは「並列処理」と言うより「パイプライン処理」だ。
- 616 名前：615 mailto:sage [2008/02/13(水) 19:54:54 ]
- あ、先に言われてしまったｗ。
- 617 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 02:06:09 ]
- パイプライン処理も並列処理みたいなもんでしょ。
依存関係があっても適用できるわけだし
そういう細粒度の並列処理を
ソフトウェアでうまく書く方法ってある？
手の生成→並べ替え→手を打つ
手の生成→並べ替え→手を打つ
手の生成→並べ替え→手を打つ
手を打たないと、次の手の生成ができないから無理か orz
- 618 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 02:22:52 ]
- >パイプライン処理も並列処理みたいなもんでしょ。
ぷぎゃー
- 619 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 02:41:25 ]
- いや、言いたいことはわかるよ
- 620 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 16:51:24 ]
- >617
普通のPCハードウェア（CPU）じゃ無理だね。
パイプライン処理（それも将棋専用の）が可能なCPUじゃないと。
だから「A級リーグ指し手1号」と言う名前で専用プロセッサを
FPGA使って開発してる人が居るわけで。
- 621 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 18:28:27 ]
- パイプラインによるオーバーラップさせた処理は並列処理の一種
- 622 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 18:31:21 ]
- マルチコア環境ではハードでなきゃ無理ということはないと思う
例えばPS3/Cellにはそういう形（パイプライン）の並列処理の枠組みが用意されてる
もちろんアルゴリズムは自分で考えるのだが
- 623 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 19:07:21 ]
- >622
へー、CellB.E.(SPU?)にそんな仕組みがあるの？
単なるSIMD演算器がさらに8個並列で存在するだけかと思ってた。
個々のSPU内の演算器を自分好みのパイプラインに仕立てられるのか？
- 624 名前：623 mailto:sage [2008/02/14(木) 19:37:44 ]
- >622
もしそういう機能が本当にあれば非常に興味深い（使ってみたい）ので
どのドキュメントに載っていてどんな名前で呼ばれている機能か教えてくれ。
「Cell Broadband Engine アーキテクチャ」Ver1.01 (by ソニー）
をざっと眺めてみたが見つけられなかった。
- 625 名前：623 mailto:sage [2008/02/14(木) 20:06:15 ]
- >622
もしかしてSIMD演算機能あるいはSPUを仮想化してマルチスレッド
ソフトウェアを走らせる機能を（ハードウェア）パイプライン機能と
混同してない？
普通の（IntelやAMDのx86)CPUもある種のパイプライン（スーパースカラー）
機能はあるけどプログラマが意識的（明示的）に操れるわけじゃないし。
- 626 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 21:11:56 ]
- 622じゃないけど、
PS3のCellで囲碁をパイプラインってこんなの？
www.geocities.jp/hideki_katoh/publications/gpw2007/gpw07-private.pdf
αβ探索じゃなくて、モンテカルロならパイプライン可能かもな
要はスレッド間の同期をとるだけじゃん
- 627 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 21:20:01 ]
- >>625 スーパースカラーはパイプラインじゃないよ
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
こういうのがパイプライン。
スーパースカラは複数の命令を同時に実行できる機能
- 628 名前：623 mailto:sage [2008/02/14(木) 21:20:17 ]
- スレッド間同期とパイプライン処理は違うでしょ？
- 629 名前：623 mailto:sage [2008/02/14(木) 21:27:37 ]
- >627
スーパースカラー＝パイプラインじゃないけど、現在主流のCPUで言う
「スーパースカラー」はパイプライン処理が前提なんだけど。
すなわち複数命令を（同時実行できるものは）同時発行しておいて
さらにそれらをパイプライン化された処理装置に叩き込む。
詳細はWiki等を参照してくれ。
- 630 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 21:30:02 ]
- どの命令が並列処理できないかコンパイル時点で分かるよね？
- 631 名前：623 mailto:sage [2008/02/14(木) 21:34:30 ]
- >630
??? 何が言いたいの？
コンパイラに並列化を任せて明示的に(機械語レベルで）複数命令を
並列実行するならVLIWアーキテクチャだね。Itaniumみたいな。
- 632 名前：デフォルトの名無しさん mailto:sage [2008/02/14(木) 23:59:56 ]
- ちなみに普通の（VLIWでない）CPUはコンパイラが並列処理可能な
命令を見つけたとしてもそれをマシン(CPU)に伝える手段が無い。
- 633 名前：デフォルトの名無しさん mailto:sage [2008/02/15(金) 00:37:59 ]
- さらにちなみにベクタープロセッサ(ベクター型CPU）はひとつの
演算処理（たいていは積和算）そのものを複数のステージに細切れに
分けてパイプライン処理する。したがって同じタイプの演算命令が
次々と間を空けずに来る事が前提。
なのでベクター（行列）の処理に向くと言うか、それにしか向かない。
- 634 名前：622 mailto:sage [2008/02/15(金) 02:16:07 ]
- およよ，思いっきり勘違いされた
>マルチコア環境ではハードでなきゃ無理ということはないと思う
と書いた時点でソフトの枠組みの話をしてることが分かると思ったのだが
分かり難くてスマソ
- 635 名前：デフォルトの名無しさん mailto:sage [2008/02/15(金) 15:11:57 ]
- >634
いいたいことは分かった。
スレッド同士のバケツリレー的なことを API でサポートしてるってことね。きっとイベントキューとかメッセージボックスとか使うんでしょ。
って >622の文脈であの書き方じゃわかるわけねーよ！
- 636 名前：デフォルトの名無しさん mailto:sage [2008/02/15(金) 19:54:51 ]
- 俺は使ったことがないが，API より上のレベル，
フレームワークが提供されていると聞いている
>じゃわかるわけねーよ！
読み直してみると確かに分かり難い．改めてすまんかった
- 637 名前：623 mailto:sage [2008/02/15(金) 22:45:43 ]
- やっぱりソフトウェア（開発ツール）レベルでパイプライン（的）
処理をサポートする枠組みがあると言う事だったのか。
>634を読んでしばらく考えてようやく意味が分かったよ。
確かにCellのSPUならマルチスレッド（マルチコア処理）で
パイプライン（的）処理をする仕組みを作りやすいかも知れないな。
キャッシュなしのローカルストレージのみで動くから
インストラクションの実行時間を確実に見積もれる。
そういう話を聞くと>617が書いてるようなパイプライン処理を
Cell(PS3)上で実現できないか、ちょっと考えてみたくなるな。
タスクをそれぞれ均等な実行時間を持つステージに分割できるか、
通信オーバーヘッドがどれくらいあるかが問題だけど。
- 638 名前：デフォルトの名無しさん mailto:sage [2008/02/16(土) 02:00:36 ]
- 概要レベルだが
ttp://research.cesa.or.jp/pdf/shiryo6-2-2.pdf
にCellの並列化のPipelineモデルとかStreamingモデル等の話が載ってる
（日本IBMの東京基礎研の人の講演）
- 639 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 21:43:39 ]
- >>638 THX 勉強になった
>>626 のPDFを見ても、cellってMBOXでSPUが通信できる仕組みみたいだねえ
ハードのパイプラインはクロック同期と思うが、
ソフトでも負荷の無い同期方法ってないもんか？
Stramingモデルってのが面白かった
- 640 名前：デフォルトの名無しさん mailto:sage [2008/02/20(水) 00:16:34 ]
- >負荷の無い
ってどういう意味？
libspe2 には mbox と signal しか用意されてないけど
自分で作るのもあり
- 641 名前：デフォルトの名無しさん mailto:sage [2008/02/20(水) 11:30:35 ]
- >>639
ハードウェアのクロック同期だって負荷があるだろ。
1クロックよりずっと短い処理だってクロック同期を待たなければならないんだから。
それでもCISCの頃よりは計算資源のアクティブ率は上がった。
ソフト側も同様にプロセッサの稼働率を上げていけばよい。
- 642 名前：デフォルトの名無しさん [2008/03/18(火) 10:22:07 ]
- 保守
- 643 名前：デフォルトの名無しさん mailto:sage [2008/03/19(水) 00:05:55 ]
- 4/6(日)開催予定のオープン戦案内メールをもらった。
しかしソフトはまだ全然出来ていない。
将棋を指す骨組みと通信部分だけくらいは何とかその日までに
完成させて一回は通信対戦テストをしておきたいのだが。
このままじゃ、ぶっつけ本番になってしまいそうだ。
- 644 名前：デフォルトの名無しさん mailto:sage [2008/03/22(土) 01:46:00 ]
- オープン戦に間に合わなければ、
wdoorでテストしておけば？
CSAの対局サーバーとは細かい違いはあるようだが……
がんばれ
- 645 名前：デフォルトの名無しさん mailto:sage [2008/03/23(日) 13:05:20 ]
- あげ
- 646 名前：デフォルトの名無しさん [2008/03/23(日) 13:05:40 ]
- てなかった
- 647 名前：デフォルトの名無しさん [2008/03/23(日) 15:10:42 ]
- ボナンザについて解説してるサイトがあったら教えてください＞＜
- 648 名前：デフォルトの名無しさん mailto:sage [2008/03/23(日) 15:55:11 ]
- >>647
作者のサイトの GPW 2006 発表資料 には目を通した？
あの説明で何かわからないことある？
- 649 名前：647 mailto:sage [2008/03/23(日) 17:44:26 ]
- >>648
見てなかったです．
読んでみます．
サンクスです．
- 650 名前：デフォルトの名無しさん mailto:sage [2008/04/10(木) 23:56:08 ]
- >648
あれ読んでも具体的に何と何を入力パラメータとして
選んだのか今一良く分からないんだよね。
各駒種に対してその位置（升目）ごとに重み付けしていって、
それを2個以上の駒の位置関係にまで広げていったら、
あっと言う間にパラメータは1万個どころか百万個以上に
なりそうだし、学習を進めると結局、棋譜に現れたもしくは
探索済みの特定の局面に評価値を与えるだけになりそうな気が。
つまり一般化能力なんか全く無さそうな気がするんだが、
私が何か勘違いしてるのかね？
コンピュータ将棋に詳しくないために。
- 651 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 00:38:13 ]
- >>650
その論文読んでないけど、テレビでやってたやつ見た限りだと
その発想そのままだと思う。
ボナンザの初期バージョンでは数手先まで読むように拡張してみたところ
うまく読み取れない局面があることがわかった。
そこで、ある程度（？）評価の悪い枝についても読むようにしたところ
かなりよくなった。
完全に総当りじゃなくて、ある程度評価がいい手の中でも
多少悪いぐらいでは枝狩をしない
また、相手の手版のときに、多少悪いぐらいの手をさしてくることを
考慮して読んでおくことで、時間を有効に使う
一般的にどうこうするっていうのではなくて
特定の場合に愚直な実装して、枝狩りの閾値さげたら
割とうまくいきました っていう感じだと思う。
他の検索系のやつもそうだけど
この手の総当りが必要そうなものについて、愚直に実装して
動かしてみたら案外うまくったってのが、最近の傾向じゃないかな
人間があーだこーだ考えるよりPCに考えさせたほうが
早いっていう。
だから一般化というより、ある特定のルールのときに
CPU時間を有効に使えるように変えてみたら
アルゴリズムは今までとほとんど同じだけど
勝率があがりました って思ってるけどこれも違うかな？
あくまで素人の意見なんですが。
- 652 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 01:16:23 ]
- >>650
> それを2個以上の駒の位置関係にまで広げていったら、
広げない。
将棋は、自玉、敵玉に対する位置関係は重要だが、それ以外の2駒の相対的な位置関係は
あまり重要なゲームではないからだ。
例えば以下の記事が参考になるだろう。
d.hatena.ne.jp/yaneurao/20080406
ただし、銀の退路が歩で遮られていないかだとか、歩越しになっていないかだとかは重要なので、
Bonanzaでもそこは考慮に入れていたはず。
- 653 名前：650 mailto:sage [2008/04/11(金) 01:30:39 ]
- あり？ 良く考えてみると二駒の絶対位置関係の
全ての組み合わせにそれぞれ点数を付与して
行ったとしても、二駒のペアは自由に選べるわけだから
特定の局面に対して点数を付けて行くのとは違うな。
汎化能力はあるか、俺が勘違いしてたわ。
それにしてもパラメータ数が膨れ上がると言う謎は残るな。
愚直にやると駒のペア×位置（マス目）×位置（マス目）で
40×39÷2×83×83で500万以上にもなるか？
- 654 名前：デフォルトの名無しさん mailto:650 [2008/04/11(金) 01:38:22 ]
- >652
なるほど、サンクス！
もうちょっと考えてみよう。
- 655 名前：デフォルトの名無しさん [2008/04/11(金) 01:39:58 ]
- >>654教授か研究者の方？
- 656 名前：654 mailto:sage [2008/04/11(金) 01:52:32 ]
- >655
いえ、違います。
ただ単にコンピュータ将棋に関心があって
（できれば自分でも作りたいと思ってる）
ボナンザメソッドに興味を持った
一介のアマチュアです。
- 657 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 05:57:50 ]
- 最善手を求めるときって、引き分けがある場合はちょっと工夫が必要なのかな？
反復進化で求めると思うんだけど、その時未知の局面が現れた場合、引き分けの値との関係が難しい。
負け＜引き分け＜未知＜勝ちという図式になると思うんだけど、未知の局面の値は相手から見ても引き分けより
大きくなければならないので、単純に符号を変えるという普通の方法が使えないわけですが
何か一般的な手法があるのかなと思って聞いて見た次第です。
- 658 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 06:05:36 ]
- >>657
未知の局面て何よ？
未探索で評価値がわからないなら探索して決めればいいじゃん。
終端ノードなら、静止評価すればいいじゃん。
そんなの反復深化とも引き分けともなんも関係ないよ。
- 659 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 06:26:40 ]
- えっと、負け＜引き分け＜未知＜勝ちから分かる通り
未探索の局面を全て調べる必要がないわけですが、深さを制限しないで調べるのが一般的でしょうかね。
- 660 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 07:03:41 ]
- >>659
> えっと、負け＜引き分け＜未知＜勝ちから分かる通り
何が言いたいのかさっぱりわからんよ。
基本的なことを確認するが、あんたは普通のαβや反復深化は理解していて
自分でそのプログラムぐらいはすぐに書けるんだろな？
あんたの言う「未知」って何よ？置換表に登録されていないの意味か？
そしてその「引き分け」っていうのは、なによ？
評価したい局面で引き分けにする指し手が見つかっているのか、
それとも「引き分け」というのが存在する将棋みたいなゲームでの
一般的な探索メソッドについて話しているのかどっちなのよ。
- 661 名前：デフォルトの名無しさん mailto:sage [2008/04/11(金) 12:48:08 ]
- >>653
例えば相対位置を使ったり
- 662 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 01:16:32 ]
- 上の方にあった千日手関係の話？
- 663 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 10:38:11 ]
- で将棋に関するGHI問題の話の結論はどうなったの？
- 664 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 11:23:06 ]
- >>663
このスレでは >>234 の論文以上の進展はないと俺は理解している。
- 665 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 13:18:03 ]
- >663-64
結論は既に出てると思うが？
GHI問題と言うのは証明アルゴリズムの不完全性などに起因するのではなくて、
千日手などのそこまでの指し手に依存して勝ち負け（引き分け含む）が決まる
タイプのルールを持つゲーム（将棋、チェスなど）には必然的に生じる問題。
即ち、ある局面からの勝ち、負け、引き分けを厳密に判定するにはその局面に
至るまでの経路（指し手の履歴）も考慮する必要があると言う良く考えれば
ごく当たり前の話に過ぎない。
- 666 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 13:19:36 ]
- 上のアンカーは >663-664 の書き間違い。
- 667 名前：デフォルトの名無しさん mailto:sage [2008/04/12(土) 14:33:23 ]
- >657の言う「未知」と言うのは千日手になるかも知れないが初手からの
完全な履歴は残してないので厳密に考えると「千日手になるかどうか不明」
になると言う話なのかな？
しかし「相手から見ても引き分けより大きくなければならない」と言うのが
良く分からんな。不明な局面の場合「悪くても引分け（千日手）」に持ち込める
と言う保証なんか無いわけだから。不利な状況から千日手に持ち込もうとしても
出来ないかも知れない。
- 668 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 13:27:01 ]
- うさ将棋本に局面で乱数xorを用いるhash(zobrist hashのことだろう)を、乱数ではなく
もう少しいい方法があるらしいことが書いてあるのだが、誰か情報求む。
与えられた数列集合の要素同士のxorを何回かとるときに
なるべく衝突しないような数列を数学的に決定する方法があるのか、
それとも衝突しにくい組み合わせを事前にrandomで選んだ数列集合のうち
良いものを探してみましょう、程度の話なのかどちらなのだ？
- 669 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 15:46:14 ]
- その本のは知らないけど、以前読んだ何かのプログラムのソースでは
個々の乱数を生成したら立ってるビットの数はチェックしていたな。
うろ覚えだけど16±5くらいの範囲に収まってるかってのだったかなぁ。
この範囲に無ければ再生成。
- 670 名前：デフォルトの名無しさん [2008/04/13(日) 16:32:31 ]
- ボナンザでいくつか質問があるんだけど，
・静的評価関数はminimax探索で利用されるんだよな？
・最適化の数値的手法１のスライドの関数f(p,ν）って何？
人工知能は学部で多少勉強した程度で将棋プログラムの経験もないんでとんちんかんなこと
聞いてるかもしれないけど，教えてください
- 671 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 17:52:30 ]
- >>669
ああ、なるほど。1のビットの数はチェックしたほうが良さそうだね。
- 672 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 12:13:14 ]
- 他の乱数とのハミング距離が小さいのは捨てる
というのもあった（時間掛かるけど最初だけだからOK）
- 673 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 12:42:55 ]
- >>672
ああ、それもいいね。
- 674 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 23:07:55 ]
- >670
良く嫁。同じスライドの下に式があるだろう＞f()
- 675 名前：デフォルトの名無しさん [2008/04/17(木) 20:19:52 ]
- 序盤、中盤、終盤はどのように判定したらいいんですか?
50手で終盤の事もあるし、200手で中盤の事もあるので手数とは関係ないと思います
考えられるのは、玉の危険度で測るのがいいと思いますが定番のやり方ってありますか?
- 676 名前：デフォルトの名無しさん [2008/04/17(木) 20:23:10 ]
- >>668
数学的な方法って無いと思いますよ
自分でやってみた方法は、プロの 棋譜を読み込んで衝突が起こりにくい乱数を決めておくって方法です
実際に起こりえない局面で衝突が起こらなくても意味がないので
- 677 名前：675 [2008/04/17(木) 20:27:40 ]
- 読み無しで、玉が詰みそうかどうかを判定する方法がわかれば良いのですが
- 678 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 21:04:04 ]
- >>677
> 玉が詰みそうかどうかを判定
これを読みって定義するんじゃないか？
- 679 名前：675 [2008/04/17(木) 21:31:52 ]
- 危険度を数値化(危険度の評価関数)するって事ですよ
詰みそうならば詰め将棋を読んで、詰まないことが局面だけから判断できるなら詰め将棋をしなくて済みます
玉の逃げ道の多さが危険度に関係ありそうですけど、穴熊だとうごける所は0なのに堅いです
どのように危険度を判定するといいですか
- 680 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 22:10:47 ]
- それこそ開発者各々の know-how の部分だろ．
まずは定番の「コンピュータ将棋の進歩」シリーズを読む．
続いてゲームプログラミングワークショップの予稿集を読む．
CSA に入ってトーナメントに参加し，他の開発者から色々教わる．
本格的な議論は将棋板のコンピュータ将棋関係のスレッドで
- 681 名前：デフォルトの名無しさん [2008/04/17(木) 22:19:20 ]
- 将棋板には人いません
- 682 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 22:40:25 ]
- >>675
成駒の数とか敵陣にいる駒の数、あとは王将と攻め駒の距離とかかな。
適当に考えただけだから、実装して上手くいくかどうかはわからんが。
- 683 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 22:42:44 ]
- >679
この辺で聞くと役に立つアドバイスがもらえるかも知れないよ。
GA将!!!さん運営の「コンピュータ将棋等の掲示板＠入門編」
www4.rocketbbs.com/741/comsyogi.html
あるいは超有名なYSSの山下さんところの
「コンピュータ将棋や囲碁の掲示板」
524.teacup.com/yss/bbs
最近、掲示板@入門偏は話題が無くて止まってるからちょうど良いかも。
ちなみにダブルポストすると注意されるから気を付けてね。
- 684 名前：デフォルトの名無しさん [2008/04/17(木) 23:05:52 ]
- サンクス
- 685 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 23:22:10 ]
- >679
ちなみに「うさぴょん本」にちょっとだけ書いてあるのを紹介すると
・玉の危険度
「玉の周囲に敵の利きがどの程度あるか、敵の駒がどの程度の距離に迫っているか」
結局、自陣(自玉周囲）にどの程度敵方の駒が利いているかが判定のキモだと思うな。
自陣に利いていても、玉ではない味方の駒で敵の駒の利きを受け止めているんなら
まだ固いと判断できるし、何にも無い空間にバシバシ利いているんなら（裸玉）、
もう詰められる寸前だろうし。
固さと玉の逃げ道の広さは当然、矛盾するところがあるので難しいところだけど。
- 686 名前：デフォルトの名無しさん [2008/04/18(金) 00:04:17 ]
- しかし、玉の危険度と、通常の評価関数の二つがあると、どちらを優先したらいいのか混乱しますね
統合した評価関数が出来れば一番良いのですが
- 687 名前：デフォルトの名無しさん [2008/04/18(金) 00:49:07 ]
- プロの棋譜で、2回以上現れる局面で必然手のない局面は、互角であると思います。
これを基準にして評価関数を調整するといいと思うのですが…
しかし、問題があり、2手以上出てくる中盤までしか調整が出来ません。
プロが指した手が最も得点が高くなるように調整すれば全局面に対応出来ますが
例えば、10手読みを入れた結果だとすると、評価値の値を間違えることになります。
しかし、何手読んだのか知ることは出来ず、常に一手読みとして学習したら駄目でしょうか?
- 688 名前：デフォルトの名無しさん mailto:sage [2008/04/18(金) 00:53:31 ]
- >686
？？？ そりゃ、両方をひとつの評価関数として統合しないと。
と言うか、玉の危険度も通常は評価関数の一部だよ。
いろんなパラメータを重み付けして足して行くわけだ。
だから手動で調整するとバランスを取るのに四苦八苦するわけだが。
- 689 名前：デフォルトの名無しさん [2008/04/18(金) 01:06:48 ]
- >>688
序盤か、終盤か、は通常の評価関数では知ることは出来ないと思います。
互角であっても終盤である事があります。
終盤であることを知るにはどちらかの玉が危険であると知ることが必要と思います。
そのため、玉の危険度と通常の評価関数がないと終盤がわかりません。
- 690 名前：689 [2008/04/18(金) 01:20:20 ]
- 先手の得点A、後手の得点Bに対して、評価関数をA/(A+B)とするならば
MAX(A,B)の値によって終盤判定が行えると思います。
- 691 名前：デフォルトの名無しさん mailto:sage [2008/04/18(金) 01:45:16 ]
- >689
（通常の評価関数の一部としての）玉の危険度と
局面の進行度（終盤度）を計るための玉の危険度の話が
ゴッチャになっているね。（私が誤解したのかも知れない）
後者は例えば
序盤度×パラメータA＋中盤度×パラメータB＋終盤度×パラメータC
と言うような重み付け係数として組み込む事になると思う。
玉の危険度は終盤度（進行度）と通常の（有利不利を見る）
評価関数の一部としての両方に表れて良いと思うけど、
進行度の方はあまり凝った評価はしなくて良いんじゃ無いかな？
お互いの陣地に成り込んだ駒の数とか持ち駒の数くらいで。
飽くまで私見ですが。
- 692 名前：デフォルトの名無しさん [2008/04/18(金) 01:51:46 ]
- 5対5でも、8対2でも、最善手を指せば駒交換などの後、数手以内なら状勢は変わらないはずですね。
ボナンザはその前後で評価値が変わらないとして学習しているって事ですか。
何手先の局面と評価が一致するのかが重要ですが。
- 693 名前：デフォルトの名無しさん [2008/04/18(金) 02:15:05 ]
- >>691
玉の危険度を正確に評価することは重要と思います。
正確に判定できれば、終盤用の指し手がさせますし、詰め将棋を調べず高速に危険度が求まります。
>>692の続きですが、評価値が保たれている局面を把握する方法は、既に知られているんですか?
ネットで見る限りでは、駒交換だけ進める様な感じと思いますが…
しかし、それでは飛車・角・香の利きが良く利いているなどの情報は失われます。
|
 |
