コンピュータ将棋や囲碁の掲示板　過去ログ2008年版

荒木と申します。UEC杯にはGNU_arkで出ておりましたが、大会の結果が悪かったのと、鶴岡さん(激指、元同じ研究室)に「その方針で強くすることは難しい」という内容のことを言われたのとが理由で、急遽(12/10くらいに)修士論文の方針をモンテカルロ法に変えることにしました(playoutに使うMovePredictionの精度とモンテカルロ碁の強さの関係を調べる)。ただ、Remiさんの論文のようにパターンを使ったplayoutによるモンテカルロの簡易版(UCTも使っていない)を実装したのですが、遅すぎて困っています(Remiさんの1/40〜1/50くらい)。gprofで見ても一番時間を食っている関数の消費時間の割合が10%くらいと、アルゴリズムを変えない高速化で40倍も速く出来るようには思えません。加藤英樹さんのソースのモンテカルロ部分もざっと眺めたのですが、CrazyStoneではなくMoGoベースのせいか、どうしてこんなに速度差が出るのか良く分かりませんでした(少なくとも画期的なアルゴリズムを使っているようには見えなかったのです)。モンテカルロ用の高速なplayoutの実装のためには、何かコツがあるのでしょうか?それとも、みなさんアルゴリズム以外の高速化をひたすら頑張ることで速くしているのでしょうか?    

速度で一番影響が出るのはデータ構造ではないかと思います。
彩のデータ構造は下のような感じです。
・ダメの情報（位置、数）を常に正確に保持する。
・石の数
・連同士が融合したとき、小さい方の連は大きい連番号を参照するようにする

特徴としては連構造体の中に「仮の連番号」というのを持っていて
たとえば下図で、★に黒が打った場合に、

  ＡＢＣＤＥＦ  1番の連 (C3) 仮の連番号 1
１┌┬┬┬┬┬  2番の連 (E4) 仮の連番号 2
２├○○○┼┼
３├○●●★┼  これが★に打った場合、
４├┼┼┼●○
５├┼┼●●○  1番の連 (C3) 仮の連番号 2
６├┼○○○○  2番の連 (E4) 仮の連番号 2

というようにしてC3にある石の連番号を求める時に、仮連番号を
たどっていく、という構造にしています。

ただ、ダメの位置、を正確に持つために大きな石同士が融合するときは
かなり重いです。

後は彩も3x3のパターンを使って、1手ごとに白と黒の確率分布を
更新しているのですが、これもかなり重いです。
後はplayoutでは石を戻さずに、最後まで打ったら次回にはコピーしなおしています。

Core Duo1.83GHzで初手で打つ速さは
　 9路盤  40000po/秒  平均 77.5手 パターンなし。データ構造のみ
　19路盤   9300po/秒  平均354.4手 パターンなし。データ構造のみ
　 9路盤   7890po/秒  平均 99.8手 playoutのみ。6270po/秒 UCTあり
　19路盤   1830po/秒  平均422.4手 playoutのみ。1660po/秒 UCTあり

囲碁のデータ構造はかなり面白い部分の一つではないかと思います。    

山下さん、返信ありがとうございます。
>・ダメの情報（位置、数）を常に正確に保持する。
>・石の数
>・連同士が融合したとき、小さい方の連は大きい連番号を参照するようにする
同じようなデータ構造を使っています。加藤英樹さんのソースを眺めたときにもそのような方針らしいと分かったので、石を打つたびに周囲の石が取れるか再帰的に調べる方針から変更しました。ただ、それでも劇的には速くならなかったです…。違う点と言えば、石の数だけでなく座標もデータ構造に入れている点でしょうか。うーん。
>後は彩も3x3のパターンを使って、1手ごとに白と黒の確率分布を更新しているのですが、これもかなり重いです。
今は3x3のパターンより少しだけ大きなパターンを使っています。だから、速度が1/2位になるなら納得できるのですが…。
>後はplayoutでは石を戻さずに、最後まで打ったら次回にはコピーしなおしています。
同じですね。
現在の速度は、Core2Quad2.4GHz(1コアのみで並列化はしていません)で
79.38po/秒 UCT無し
です。時間はboostのtimerで計っています。    

あれから少し高速化し、またパターンを3x3に縮小してみたのですが、それでも
  150.6po/秒
です。山下さんの1/10以下ですね。    

データのコピーに時間がかかっている、ということはないですか？
彩の連構造体は1MB近くあって巨大なので、
最初クラスを丸ごとコピーしていたらかなり遅くなった記憶があります。
データがある部分だけを最小限コピーしたらほとんど気にならなくなりました。

乱数で9路で石を50回打って戻すだけ、というような処理でも
遅いのでしょうか？

> 石の数だけでなく座標もデータ構造に入れている点でしょうか。

彩では int ishi_list[BOARD_SIZE] という配列を一つ持って、
C3の黒石の隣、C4に黒を打った場合、ishi_list[C3] = C4, ishi_list[C4] = NULL
というようなリスト構造にして連の構造体には最初の座標だけを持つようにしています。
石をたどるときは、このリストをたどっています。    

返信ありがとうございます。どうもすいません。
9路盤50手までパターン無しで速度測定してみたのですが、
  4554po/秒
という結果になってしまいました。山下さんの約1/10ですね。どうやらパターン以前に盤の実装も重かったようです。STLのコピーが遅いのでしょうか。これからさらに調査してみます。
いろいろありがとうございました。    

とうとう2008年ですねー (なんのこっちゃー(^^;

私は、過去(6年前)の2002年 8月 3日(土)に、ここの掲示板において「将棋プログラム強化法　（100倍強くなる法 ) 」と題して、
好き勝手な妄想を書かせていただいた者です。そのあまりの誇大妄想に大笑いもされました。(^^

当時、私は、「2008年はコンピュータ将棋のターニングポイントの年であります! (私がかってに決めた　(^^; 」
と書き(過去ログを参照)、「私の妄想する「プログラムC」?の実現、完成なくしてプロからの一勝は夢のまた夢であろう」と書きました。
ちなみに、ターニングポイントとは、［turning point］転換点，転換期，転機，変わりめの意味です。
そして、「このプログラムC　の完成まで天才、山下さんでも6年を要する」、
「2008年、完成をめどに今からプログラムC の制作にとりかかっていただきたいですね。(ほんと 言うのは簡単やなー(^^A 」
と書きました。が、果たして2008年を迎えた今日、その「プログラムC」は実現されたのでありましょうか?

私は、また好き勝手な予想をしたいと思います。(あきんなぁー(^^;
今年の選手権において優勝するプログラムこそが、私の妄想する「プログラムC」に最も近く、
コンピュータ将棋界に新たな、転換点，転換期，転機をもたらす事を断言したいですね……(責任は取れんけどねー(^^A
つまり、ここ数年の著しいコンピュータ将棋の進化(実際、目を瞠るものがあります)は、
このターニングポイント実現への到達点に過ぎません。

そして、その快進撃するプログラムは……learning programと称されるでしょう――。(ほんとかいなー(^^A    

色々お騒がせしました。あれからランダムシミュレーション部の改良をしたり、__gnu_cxx::__pool_allocを使ったり、bitsetを使ったりして、何とか
  20000po/秒 9路盤50手までパターン無し
まで速度が出ました。まだ山下さんの1/3ですが、もうあまり修士論文提出まで時間が無いので、これで実験しようかと思います。どうもありがとうございました。    

この度、「彩」をダウンロードさせて頂きました
私は、だいぶ前から９路盤を研究しており、まとめとして使えるコンピュータを作れないかと思っているのですが、この「彩」をベースのソフトとして棋譜を入力していき、それを再現させる、ということはできませんでしょうか？　ソフトの知識は全くないのですが、ご回答お待ちしております    

明けましておめでとうございます，完全に出遅れた加藤です．
私のプログラムのボトルネックは，乱数で手を一様に選ぶ部分の合法手の数え上げと，一手打たれたときに連のダメを更新する部分でした（各々全体の 30% 程度）．
なお，profiler ですが，Sylvain は valgrind に付属している callgrind を使っているそうで，私も使ってみましたが中々良くできていて，アセンブリとの対応まで表示してくれます．但し，中でエミュレートしているので細かく分かる代わりにかなり遅くなります．
本題が後になりましたが，荒木さんの場合ボトルネックは STL の中を含めて new 等のメモリ管理関連ではないかと思います．
速度を求める人は LibEgo を参考にするのがいいでしょう．もっとも，最高速を求めるなら（Penryn なら SSE4.1 の ptest もあるし）bitboard を使うのがベストでしょう．連のダメを動的に計算してもそれほど掛かりませんし．
私も（Cell の SPU には 128bit register が 128 本あって盤面を常駐できることもあって）現在順次移行中です．    

加藤さん、返信ありがとうございます。荒木です。
たしかにメモリ関連で相当な割合を食っているらしいです。同じ研究室の人にもcallgrindを勧められて、その結果を見てもやっぱりnew関係がかなり食っていました。なので、候補手をスコアでソートして持っておくsetを自前のheapに変えたりしたのですが、まだあまり速くなっていません。ちなみに先ほど山下さんの1/3と書きましたが、パターンを入れるとまだ山下さんの1/10です。うーん。
僕の修士論文の目的は、RemiさんのようにMovepredictionをモンテカルロに入れた場合の、Movepredictionの精度とモンテカルロの強さの関係を調べることです。なので、最高速を求めているわけではないのですが、それでもある程度のplayoutを行って強さを調べないと「その結果はplayoutが少ないせいでは?」と言われてしまうので高速化している次第です。10000playoutくらいしないと収束しないのかなと(何となくですが)思っているので…。現在10000playoutに1分かかるので、せめて10〜20秒にしたいのですが…。    

僕はC++は使わないのでよく知りませんが，開発者はあまりlibraryの類は使ってないように思います．中の挙動が分かりませんし．LibEgoでもUCTの実装にBoostを使ってましたが「とりあえず」と言っていたように思います．なんでも自前の必要は全くありませんが，性能に効く部分は自分で書いた方がいいでしょう．
MITのDon Dalleyも言ってましたが，何らかの評価するためには速度は重要です．なんせ大体千試合かそれ以上やらないといけませんから，一試合10秒でも3時間ほど掛かります．時間があまり無い時こそ「急がば回れ」で，最短時間で論文が完成する計画をきちんと考えて研究を進めて下さい．慌てても良いことは何もありません．
あと，playoutの評価ですが，S.Gelly & D.Silverは，手でスコアを与えた複数の局面に対する予測スコアの平均二乗誤差を用い，結果としての強さと良く対応すると書いてます．現時点ではほぼ唯一の直接的な評価方法かも知れません．
理想的なpolicyは（当然）最善手を選ぶことですが，それは無意味．実際に有効なのは「強い人たちが打ちそうな手順（複数）」を再現するpolicyだと思われますが，これを実現するのは非常に難しい．何か面白い結果が出ることを期待してます．    

加藤さん、どうもありがとうございます。
callgrindで解析しながら高速化して、11/9倍くらい速くなりました。ただ、これ以上の高速化は修士論文としては無理かなと思っています。callgrindによると、一番食っている関数でも7%ちょっとの割合なので…。あと数倍速くするためには、全体を削るしかないのですが…。プログラム全体からSTLを取り除いていくしかないのかもしれません。
とりあえず、現状でUCTを組み込んでみて、GNUGoと対戦させてみようと思います。少ないplayoutでも(速度的に1000playoutくらい?)ある程度の勝率が得られるなら(得られないならGNU Goのレベルを下げて)、それで評価しようと思います。1000対戦は無理そうですが、100対戦くらいならなんとかなりそうなので…。
どうもいろいろすいませんでした。    

まず，callgrindを使う時は inline 系のオプションは外してますよね？
それから，Remiの手法で時間が掛かるのは確率分布に対応させて手を選ぶ処理です．彼はこれを縦と横に分けて，各々インクリメンタルに更新することで高速化していると聞いています(この辺りは山下さんの方が詳しい)．
また，私のプログラムの GNUGo 3.7.10 level 0 との対戦成績は 3kpo/move で65%位です．仮に同程度の強さ(Remiの手法がちゃんと動けば少なくともこの程度は期待できるはず)とすると，1kpoでの勝率は50%位になる(ELOで100位下がる)でしょう．
しかし，この位の勝率だと100試行での標準偏差は10%位で，分解能もこの程度になります(これは68%; 95%信頼区間は±20%位)．論文の目的が分かりませんが，例えば各特徴の寄与を求めるにはちょっと厳しいかな，と思えます．参考まで．    

たびたびすいません。荒木です。
あれからバグを取って、19路盤で終局まで打たせるplayoutで毎秒306くらいまで速度向上しました。まだ山下さんの1/6くらいですが…。
inline系のオプションを外しても、そんなに状況は変わりませんでした。一番食っている関数でも10%未満です。
確かに一番時間がかかっているのは、確立分布に対応させて手を選ぶ処理です。僕の場合は、ヒープに合法手をスコアと一緒に入れておき、上位n個を取ってきてその中からランダムで選ぶという方針にしています(他にいい方法が浮かばなかったので)。一手打つ度に打った手と取られた石の周囲のパターン(のインデックスを)更新し、ヒープも更新しています。
現在の速度からすると、2000po/moveくらいでやることになりますかね…。1000po/moveの100試行で標準偏差10%位ですか…。統計はあまり詳しくないですが…。パターンを少し大きくしたときや、直前の手との相対座標の素性を入れたときの、Movepredictionの精度(これは当然向上する、特に相対座標の素性は効く)と強さ(向上する?)の関係を調べようと思っているのですが…。まあ、1000対戦は無理なので、大きな差が出ない限りは「有意な差は出なかった」という論文になりそうですね。    

お返事が遅くなってすみません。
棋譜の入力、という点では彩はまったく向いてないです。
フリーソフトでは下のPocket Gobanがお勧めです。
http://www.vector.co.jp/soft/win95/game/se178901.html    

MoGoやCrazyStoneは彩の1.5倍から2倍以上速いですから、
まだまだ（私も含めて）改良の余地はありそうですね。
ただ、データ構造に何を持たせるか（持たせないか）で
その後のMCの精度も変わってきそうで難しいです。
Crazy Stoneはダメの数だけ保持する構造（位置は持たない）という話を
聞いた記憶があります。

今、KGSでMC版の彩を動かしているのですが、
10000poで9k、16万poで6k程度になるようです。(旧彩は8kです)

　 10000 playout 9k http://www.gokgs.com/gameArchives.jsp?user=AyaMC2
　160000 playout 6k http://www.gokgs.com/gameArchives.jsp?user=AyaMC
(10000po ... 5000po x2 CPU, 160000po ... 20000po x8 CPU)

16倍高速になって3k上がる、というのはなかなかのような気がします。
(将棋だとこうはいかないですから)    

　 9路盤  40000po/秒  平均 77.5手 パターンなし。データ構造のみ
　19路盤   9300po/秒  平均354.4手 パターンなし。データ構造のみ

補足ですけど、この2つのデータは眼には埋めない、などの条件は一切持たず、
9路だと最初に81箇所に打つ順番を乱数で決めて、その通りに打っていく、というだけの
データです。自殺手やコウの場合は無視してます。石が取られた跡には打ってません。
そのため最長でも81手で終わる（終局してない）データです。    

僕は性能測定は9路でやってます．19路だと時間が掛かり過ぎますから．これまでの数値は全て9路のものです．19路での正確な勝率の値が必要ならいざ知らず，効果を測るなら9路で十分でしょう．
後，確率分布に従って手を選ぶ部分はスコアに忠実に選ばないと何を測っているのか分からなくなると思いますが．．．上位ｎ個というのは意味が分かりません．
Remiの様に縦と横に累積して二度で済ませれば無茶な処理時間にはならないと思います．    

ほんとうにたびたびすいません。
>補足ですけど、この2つのデータは眼には埋めない、などの条件は一切持たず、
>9路だと最初に81箇所に打つ順番を乱数で決めて、その通りに打っていく、というだけの
>データです。自殺手やコウの場合は無視してます。石が取られた跡には打ってません。
>そのため最長でも81手で終わる（終局してない）データです。
あれ、そうだったんですか。

>後，確率分布に従って手を選ぶ部分はスコアに忠実に選ばないと何を測っているのか分からなくなると思いますが．．．上位ｎ個というのは意味が分かりません．
>Remiの様に縦と横に累積して二度で済ませれば無茶な処理時間にはならないと思います．
そうですか…。縦と横に累積してをやってみます。    

ちなみに山下さんと同じ条件(眼を埋めても良い、取った跡には打たない)でランダム打ちの速度を計ってみたのですが、
  19路盤 4180po/秒、平均351手
   9路盤 16600po/秒、平均78.2手
という結果です。やはり遅いですね。    

試しに私のUEC杯版（公開版）を測ってみましたが，100kpo/54.8s @4x3GHz ≒ 456po/s @3GHz でした．もう，できるだけ heap を使わないようにする（静的に確保する）位しか手が残ってないようですが，手間と残り時間との塩梅でしょうか．
これまでベンチマークは散々取ってきましたが，経験上500試合位までの勝率はかなりばらつきますから，論文にするならぎりぎり600試合(これで標準偏差＝信頼度68%の区間が±2%，95%区間は±4%，99%区間は±5%)でしょうか．私のプログラムの場合，GNU Go level 0 相手の19路だと一試合20秒ほど掛かるので，600試合で3~4時間です．level 10 だと3~40秒．9路だとこれが6~8秒xlevel0，20秒xlevel 10になります．どちらにしても level 10 の GNU はけっこう遅いので MoGo の公開版を使った方がいいかも知れません．こちらの方が強さも細かく制御できますし．
#4コアのPC買っちゃうのが一番手っ取り早いかも．Time is money.    

http://computer-go.org/pipermail/computer-go/2007-September/011156.html
から始まるスレッドです．最初の投稿が：
>I was not able to tell from the CrazyStone paper how the patterns are
>used in the playouts.  Can anyone enlighten me?  Does it simply select
>the move with the highest score?

これに対する答えが，
>I only keep light-weight local features in the random simulations. So,
>it is not expensive. A table of move urgencies can be updated
>incrementally after each move: only a few change. In fact, my program
>became faster when I introduced 3x3 patterns for the random simulations.
>I can pre-compute a lot of information indexed by pattern shape, that
>are useful to detect eyes and move legality. From memory, Crazy Stone
>does about 5k playouts / second from the empty position on 19x19, on one
>3 GHz CPU, which is "only" about 5 times slower than libego, if I
>remember correctly.

とこれ．
>Remi keeps a number that is the sum of all the probabilities (I'll
>call them that, although they are not normalized so they add up to 1)
>and also one number per row that is the sum of the probabilities of
>the points in that row. Now you pick from the distribution of rows,
>and inside the row from the distribution of points, and it can be done
>fast.    

色々ありがとうございます。
>100kpo/54.8s @4x3GHz ≒ 456po/s @3GHz でした．
あれ、そんなものですか?ダウンロードして実行してみたときはもっと速い感じがしたのですが(デフォルトは1000po/一手ですか?)
>経験上500試合位までの勝率はかなりばらつきますから，論文にするならぎりぎり600試合(これで標準偏差＝信頼度68%の区間が±2%，95%区間は±4%，99%区間は±5%)でしょうか．
修士論文一回目の提出は100試合くらいで、最終提出までに1000試合のデータを用意しようかなと思っています。一回目の提出までに600試合は出来るかどうか…。
>#4コアのPC買っちゃうのが一番手っ取り早いかも．Time is money.
一応研究室で使っている自作マシンは4コアですし、研究室の共用マシンとして4コアマシン*8と8コアマシン*2があります。他の人も締切り前なのであまり使うと怒られますが…。8コアマシン一台占有して600試合が出来ればいいのですが…。ただ、GNU_arkの学習にGNU Goを使っていた時の経験上、GNU Goは一マシン上で何個も走らせると挙動が変になる気がするのですが(GNU Goを使った素性抽出が不定期に止まった)。並列に走らせたことが本当に原因なのか分かりませんが。とりあえずやってみます。

(現在山下さんのソースを参考にUCTを組み込んでみたのですが、変な手ばかり打ちます。UCTの実装が間違っているのか、3x3のパターンの素性しか使っていないのが悪いのか、playoutが足りないのか調査中です。)    

なるほど、ありがとうございます。パターンのインクリメンタルな更新はやっているのですが、このようにして手を選んでいたんですね。    

失礼しました。456po/s @3GHzですが、僕がggmcをダウンロードして実行したマシンが4コアだったからもっと速く感じたんですね。失礼しました。    

彩では3x3のパターンに直前に相手がどの場所に打ったか（8箇所）という情報も
持たせています。
そのため、3x3のパターンの更新は、
・自分が打った位置の8箇所（近傍で高い）
・相手が直前に打った場所を戻す（高いのを戻す）
と最大16箇所更新しています。（他にも連が取れる場所などを高得点に）

> (現在山下さんのソースを参考にUCTを組み込んでみたのですが
> 、変な手ばかり打ちます。

あのソースは私もあまり自信がありません。
MoGoなどは2手ですぐノードを作ってUCTでかなり深く読むようですし。

私も最初は81箇所全部を候補にして読ませていたら、なかなか強くなりませんでした。
（初手は中央付近に打ってくれない）
3x3のパターンで高得点なものをかなり絞って読むようにしたら強くなっていった
記憶があります。    

山下さんもどうもありがとうございます。
>・自分が打った位置の8箇所（近傍で高い）
>・相手が直前に打った場所を戻す（高いのを戻す）
>と最大16箇所更新しています。（他にも連が取れる場所などを高得点に）
石を取った場合は取られた石の周囲のパターンも変わりますが、そこは更新していないんですか?

>あのソースは私もあまり自信がありません。
まあおそらく僕のミスだと思います。

>MoGoなどは2手ですぐノードを作ってUCTでかなり深く読むようですし。
どうするのが良いのかは確かに難しいですね。

>3x3のパターンで高得点なものをかなり絞って読むようにしたら強くなっていった
>記憶があります。
うーむなるほど。パターンを使ったProgressive Wideningが重要なわけですね。

ちなみに現在は、Remiさんと同様の、確率分布に基づいた着手決定を書いた所です。速度は19路盤で286po/秒くらいです。Remiさんの1/20くらいですか…。    

> 石を取った場合は取られた石の周囲のパターンも変わりますが、

あ、やっています。
MCで一番厄介だったのは私は3x3の確率更新でした。


9路で2500点とトップに近い強さを持つgreenpeepでは
3x3のパターンに上下左右4箇所の石のダメの数の情報も持たせているそうです。
これらのパターンは自己対戦から収集したとのこと。
http://www.mail-archive.com/computer-goxcomputer-go.org/msg04944.html

ただ、ダメの数は連が長い場合、かなりの範囲を更新しないと
いけないので重そうですけど。
（・・・斜めの場合を含まなければダメ3ぐらいまでに限定してれば
少ない個数で済みそうですね）

彩でもダメ2の石が取れるかどうか（相手が自分のダメに打ってダメ数が増えるかどうか）、
打った石が自爆しないか、という判定を入れたら150点ほどレーティングが上がったので
この手の簡易シチョウみたいは方法はかなり効果がありそうです。
（探索せずにシチョウっぽいのを調べます）    

暮れの親父を亡くし、ショックだったのか、それ以降１ステップもなおしてないですが、ちょっと訳あって船でアルゼンチンまで行ってきます。
水平線効果の正体をさぐるには、水平線の彼方まで行ってそこで何が起こっているか見るしかないと言う考えも少しはありますが、３食昼寝付きでデバッグ出来るという考えです。
生きていれば、ゴールデンウィーク前には帰ってきます。
ほな、さいなら。

　　from CSA将棋の作者    

>MoGoなどは2手ですぐノードを作ってUCTでかなり深く読むようですし。
MoGo は基本的に 1 po で 1 node 作ってるはずです．UCT 木を深くすることが大切なので．UCT の実装は MoGo の最初のレポート通りで特に難しくないはずです．ただ，レポートで省略されてる部分，UCT 木の中で終局する場合の処理を間違えないように（辿ったら終局してた場合と展開したら終局してる場合の 2種類あります)．あと注意するのは，各局面の色（誰の手番か）と（最終的な）スコアを誰の立場で計算しているかを合わせる位．最初は UCB1-TUNED の式を使うのが無難でしょう．あ，僕は MC が長くなり過ぎて打ち切った時はスコアを0.5（引き分け）にしてます．±1でやってるなら0ですね．セキは無視（パスは合法手に入れない）で十分でしょう．
>パターンを使ったProgressive Wideningが重要
これは確かに効きます．MoGo も fpu を修正することで（結果的に）同じことをしてますし．が，今回は絶対的な強さは不要なので後回しでいいのでは？

とにかくバグがあると採ったデータが丸々無駄になりますから，バグがないことの確認を最優先でプログラムはできるだけシンプルに．データを採る時は局面（打着）のチェックと同時に（Excel などで）グラフを描いて異常がないことを確認しながら進める．できるだけ詳しい情報を log file に出力しておく ← これ大事です．    

色々ありがとうございます。
>>パターンを使ったProgressive Wideningが重要
>これは確かに効きます．MoGo も fpu を修正することで（結果的に）同じことをしてますし．が，今回は絶対的な強さは不要なので後回しでいいのでは？
たしかに後回しで良さそうですね。

>とにかくバグがあると採ったデータが丸々無駄になりますから，バグがないことの確認を最優先でプログラムはできるだけシンプルに．データを採る時は局面（打着）のチェックと同時に（Excel などで）グラフを描いて異常がないことを確認しながら進める．できるだけ詳しい情報を log file に出力しておく ← これ大事です．
なるほど。そうですね。ありがとうございます。

現在は、なぜかUCTを組み込んだものよりUCTを組み込まないもののほうがまともな手を打つという状況(序盤を見ただけで、最後まで打たせたわけでは無いのですが)で、どこかUCTの実装がおかしいのかなと思っています。たしかにバグがないことが最も重要なので、慎重にデバッグします。    

UCTの実装で勘違いしていたところがあり、それを直すとようやく、UCT無しのモンテカルロと同程度の強さくらいにはなってきました。まだ弱いのは、playoutが弱すぎる(3x3のパターンのみを使っているから)せいかなと思っています。これからさらに調査していきます。    

はじめまして、私、IKENと申します。

実は、私は今まで将棋とはまったく縁が無かったのですが、
去年、NHKでコンピュータ将棋の番組を見て以来、コンピュータ将棋に興味を
持つようになりました。
特に、ソフトが自己対戦する事によって、強化学習をする方法に
強い関心を持っています。

そこでどうしても知りたい事があり、質問してもよろしいでしょうか？

もし、仮に、ボナンザを0.003秒間に40手先まで読む事が可能な
スーパーコンピューター上で自己対戦させ、出来た棋譜を元に、
ボナンザが強化学習する事を繰り返した場合、ボナンザは強くなりますか？

それと、ボナンザが0.003秒間に40手先まで読む事が可能な
スーパーコンピューターを将棋ソフト開発に使えたとしたら、
皆様はどのような方法で将棋ソフト開発に活用したいですか？

お忙しいかもしれませんが、よろしくお願いいたします。    

的がはずれた質問はこの掲示板でしないで自分で勉強してほしいものです。自己対戦は学習
するものではない。自己対戦の目的はソフトの改造により本当に強くなったかどうかをテストするために行うものです。改造前のソフトと改造後のソフトとの繰り返し対戦で勝率が向上すれば効果があったとみなす。学習についてはボナンザさんのHPにくわしく記されている。いそがしいがよろしく頼むというのはいただけないね。。    

まあまあ。確かにボナンザの学習方法は自己対戦ではありませんが、自己対戦による学習という手法は存在します。例えばTDギャモンなど。あと、強化学習ではないですが、オセロプログラムをやっている友人によると、似たレベルのプログラム何個かの対戦の棋譜を大量にあつめて学習すれば、読みの部分が評価関数に反映されて強くなるそうです。つまりそういうのを将棋に適用できないかと言いたいのでしょう。まあ、自己対戦による学習には詳しく無いのでBonanzaが今より強くなるかどうかは分かりませんが…。

それと、報告ですが、Remiさんの真似をして、取る手、逃げる手、自己当たりなどを素性として入れてみたのですが、遅くなった上まだ9路盤でGNU Goレベル0に勝てないという惨状です…。    

一昨日のCSA例会で、柿木さんが55将棋で自己対戦の棋譜から
Bonanza方式の学習で評価関数を学習させ、非常に強いプログラムを作った、
という報告がありました。
（大会は55Tacosが優勝だったのですが、決勝戦では頭金の状態で55柿木将棋が
クラッシュして負けたそうです）
どういう特徴を学習させるか、にもよると思うのですが
本将棋でも結構な強さのものが出来そうな気がしました。
（本格的にやった、という話はまだ知りません）

> まだ9路盤でGNU Goレベル0に勝てないという

最後、最善手を選ぶ時に、最大勝率の手ではなくて
一番多く調べた手を返すようにすると彩で少し強くなりました。    

前回の報告からバグを取り、playout数を10倍(10000po/一回の着手決定)にしたら、9路盤でGNU Go 3.6のlevel0に勝ちました(終局判定がちゃんと出来ていないので、僕が目で見て判断した結果ですが。)。しかし"1000po/一回の着手決定"だとやはり相当変な手を打ちます。加藤英樹さんの1000poで勝率50%くらいという状態からは遥か遠い気がします。うーん。

>最後、最善手を選ぶ時に、最大勝率の手ではなくて
>一番多く調べた手を返すようにすると彩で少し強くなりました。
なるほど、ちょっと試してみます。    

回答者A様、ご回答ありがとうございます。
御忠告、感謝いたします。精進をいたします。

荒木(ark)様、ご回答ありがとうございます。
なるほど、オセロである一定の効果が認められたのなら、
将棋も強くなる可能性は少なくないですね。

山下様、ご回答ありがとうございます。
そうですか〜既に55将棋で実践されている方がおられるのですね。
今後ともよろしくお願いいたします。

ところで、あつかましいとは知りつつも、皆様に追加の質問をしてよろしいでしょうか？

Bonanzaは、評価関数を学習させる時に、
1手+静止探索で学習をしていますが、
10手+静止探索で学習した方が強くなりますか？

よろしくお願いいたします。    

あ、書き方が悪かったですね。たしかオセロの友人は、「強くなるはず」と言って棋譜を作る所まではやったのですが、その後実際にそこから学習させてみるのは(確か)まだやってなかったと思います。誤解を招く書き方して申し訳ありませんでした。

追伸:その友人のオセロプログラム仲間によると、適当に学習させてみたところ、significant improvementは無かったそうです。すいません。    

荒木(ark)様
ご回答ありがとうございます。

いえいえ、お気を使わないで下さい。

普通のPCで作成した棋譜で強化学習をしても、あまり効果が無い事は、
私にも感覚的に理解ができるような気がします。

しかし、もし、仮に、
普通のPCの数百万倍の計算能力があるスーパーコンピュータ上で、
自己対戦し、ソフトの実力以上の棋譜を作成して、その棋譜で強化学習をした場合は、
かなりの改善が見込めませんでしょうか？

これは実際に実験をしてみないと分からない事かもしれませんが･･･    

もう話が終わってしまった感じなのですが、簡単に書かせてもらいます。
私が今やっている感じだと、一から書いたプログラムで強化学習をするのは、ある程度は成功しています（まだまだ弱いですが）。
ただ、Bonanzaの探索ルーチン・評価関数はBonanza Method用に書かれたものでしょうから、そのまま強化学習に使っても上手く行かないのではないか、というのが私の予想です。    

今の MoGo が使っている RLGo の特徴は自己対戦による学習で得たものです．ですから（それほど強くないレベルでの）有効性には疑問はないと思います．
問題は今の将棋のレベルで有効かどうかでしょうが，これは流石にやって見ないと分からないでしょうねぇ．．．自己対戦の場合，良くも悪くも癖が強く出て現れる手も限られたものになりますから，学習の素材としては強い人の棋譜より不利になるのはほぼ確実でしょうし．    

>加藤英樹さんの1000poで勝率50%くらいという状態からは遥か遠い
これには MoGo 流の playout policy と RAVE が入ってますから．RAVE で 300ELO 位（po 数に換算して20倍強？）強くなってます．
>一番多く調べた手を返すようにすると
私も試しましたが，こちらの方が安定してます．両者を組み合わせてもみましたが大差なしでした．ま，こういう小手先の改良で稼げるのは 2〜30 ELO 程度で，やはりアルゴリズムが大切．    

>これには MoGo 流の playout policy と RAVE が入ってますから．RAVE で 300ELO 位（po 数に換算して20倍強？）強くなってます．
なるほど。しかしpo数に換算して20倍強にもなるんですか…。しかしRAVEを入れた加藤英樹さんのほうが僕のよりだいぶ速いですね。Remiさんの真似をして素性を追加したらさらに遅くなって、今19路盤で60po/秒くらいだと思います。うーん、情けない。

ちなみに、poを40000まで増やして9路盤でGNU Go level10と1回対戦させたところ勝ちました。が、棋譜を見る限りこれはGNU Goがたまたまひどかったように思います。まあ、一回の対戦にかなり時間がかかってしまいましたが…。

まあ、GNU Goのレベルとpo数をうまく調整して、マシンを何台か使えば実験は出来ると思います。(今研究室の共用サーバーが混んでてちょっとやりづらいですが。)

いろいろありがとうございます。    

何はともあれおめでとう．僕が岐阜チャレンジで使ったプログラムは，多分 GNU Go には level 0 でも勝てないでしょう（level を 0 にしてもそれほど弱くなりません．-150ELO 程度？)．それを考えると大変なことです．

>RAVEを入れた加藤英樹さんのほうが僕のよりだいぶ速いですね。
RAVE は UCT 側のアルゴリズムですから po 速度にはそれほど影響しません．並列度の上限は下がりますが．

>実験は出来ると思います
くれぐれもバグには注意して下さい．ログファイルを一回じっくりチェックしておくことをお勧めします．    

彩だと2000poでほぼ5割の勝率です。（GnuGo 3.7.10の9路、Level 10）
CrazyStoneは500poで5割、とのこと。
加藤さんの1000poは性能いいですね。
greenpeepは10000poで GnuGo 3.6 level 8 に84%、なので1000poで50%は
行っていそうです。    

>彩だと2000poでほぼ5割の勝率です。（GnuGo 3.7.10の9路、Level 10）
>CrazyStoneは500poで5割、とのこと。
>加藤さんの1000poは性能いいですね。
>greenpeepは10000poで GnuGo 3.6 level 8 に84%、なので1000poで50%は
行っていそうです。
え、皆さんそんなにすごいんですか。うーむ。ちなみに僕のプログラムは10000poで80局GNUGo3.6のlevel0と9路盤で打たせてみたら勝率20%ほどでした。うーん。こんな状態で実験やって意味があるのでしょうか。    

厳密には，実測値が 3000po で勝率 65% = +110ELO，po数 2倍で +70ELO を外挿すると 3倍で +110ELO，差し引き 0ELO = 50%ということです．
なお，greenpeep の 84%は +290ELO，po数 10倍は +230ELO，差し引き +60ELO = 60%弱になりますが，相手が 3.6 level 8 なので微妙．．．
>こんな状態で実験やって意味があるのでしょうか
実験の目的次第です．パターンの効果を測るのに基準を何にするのが良いか，あるいは妥当か？
候補の一つは最小限のヒューリスティクスという意味で random playout でしょうか．これは再現性が高いので誰もが納得するでしょう．ヒューリスティクスを多用したものを使った場合，再現性も無いし測定される効果もかなり打ち消されるでしょう．
勘違いしている人が多いのですが，研究の目的は決して強いプログラムを作ることではありません．それがどれだけ他の研究者の役に立つかが最も重要なのです．こういう基礎的なデータを測定する場合は特に．例えば複数のヒューリスティクスの効果を比較するのに引用されるとか．当然，前提/環境を明確にすることは必須で，ソースも公開するべきなのです．    

加藤さんの統計計算についてですが、二項分布として計算しているのでしょうか。一回の対局の勝率pとしたときの二項分布の期待値はnp、分散はnp(1-p)、標準偏差はsqrt(np(1-p))です。n=100,np=50という結果が得られたとすると、標準偏差はsqrt(100*0.5*0.5)=5.0なので、二回実験をしたときの68%信頼区間(標準偏差の分余裕を持たせた区間ということですね)は10すなわち10/100で10%ということでしょうか。

だとすると、np=20のときは、標準偏差sqrt(100*0.2*0.8)=4.0で8%ということでしょうか。    

書き込みのタイミングが悪かったですね。
>>こんな状態で実験やって意味があるのでしょうか
>実験の目的次第です．パターンの効果を測るのに基準を何にするのが良いか，あるいは妥当か？
>候補の一つは最小限のヒューリスティクスという意味で random playout でしょうか．これは再現性が高いので誰もが納得するでしょう．ヒューリスティクスを多用したものを使った場合，再現性も無いし測定される効果もかなり打ち消されるでしょう．
確かにランダムプレイアウトは基準のひとつにしようと思っています。今の心配は、いくつかの実験の勝率が低いところで固まってしまって有意な差が出ないことです。言葉足らずですいません。おそらくランダムプレイアウトは勝率0%でしょうから、0〜20%の間で有意な差を論じることになるのでしょうか。

>勘違いしている人が多いのですが，研究の目的は決して強いプログラムを作ることではありません．それがどれだけ他の研究者の役に立つかが最も重要なのです．こういう基礎的なデータを測定する場合は特に．例えば複数のヒューリスティクスの効果を比較するのに引用されるとか．当然，前提/環境を明確にすることは必須で，ソースも公開するべきなのです．
その通りだと思います。僕も実験の意味がある最低限の強さが得られればいいと思っています。(もちろん、修士論文が終わった後は大会に向けて強くしますが)。ソースの公開も、反面教師になるだろうから、やっていいかなとは思っています。    

各対局が独立と仮定して正規分布の標準偏差 = sqrt(p(1-p)/n), p=勝率，n=試合数
で計算してます．ちょっと式が違ってますが，50/100 だと 5%です（n が 100 なので偶々一致してる．n が分子にあるのは変でしょ)．
確かに勝率ゼロではどうしようもありません．GoGui の作者からも勝率が低過ぎる時は使えないよと教えて貰いました（私は統計が苦手)．公開版 MoGo の playout 数を減らしてみるのも一法かと．    

お忙しいところ何度も質問してすいません。UCTの末端ノードでのモンテカルロは、皆さん何poくらいやっているんでしょうか?(UCTの探索回数×末端ノードでのpo=全体のpoと理解しているのですが)    

彩はUCTの末端で1回だけplayoutを実行しています。
uctの関数を呼んだ回数（再帰を含む）だと、10000poで

　 9路 playout 10000回 uct関数呼び出し 19370回 node作成 45回
　19路 playout 10000回 uct関数呼び出し 13937回 node作成 16回

こんな感じです。    

なるほど。ありがとうございます。

(先ほどまたバグを潰しました。それでもまだ、UCTが返す勝率がどう考えてもおかしい時があるので、慎重にデバッグ中です。他の人のプログラムよりはるかに弱いのはバグのせいなのかなと思いまして。)    

第３回コンピュータ将棋最強決定戦の日が近づいてまいりました。
２００８年１月２３日(水）２４日(木) 午前9時半から２３日は午後４時頃まで、
２４日は正午頃までです。
北陸先端科学技術大学院大学で行います。こちらは現在雪が積もっています。
今年も昨年同様動画中継を行うことになりました。
参加プログラムはYSS, 激指, Bonanza, TACOSです。
平日の昼間ではありますが、ぜひご覧ください。 
http://www.jaist.ac.jp/rccg/saikyo/
   

私は 1 po = 1 node 作成で simulation も 1回．
>uctの関数を呼んだ回数（再帰を含む）だと、10000poで
UCT で再帰するところありましたっけ？　木を降った経路を明示的に保存せずに再帰でやってる？
>　 9路 playout 10000回 uct関数呼び出し 19370回 node作成 45回
node作成が凄く少ない様に思えるのですが．これでは余り深く読めないのでは？    

細かい補足ですが、

> 二項分布の期待値はnp、分散はnp(1-p)

これは合計した場合ですね。平均を取ると、期待値はその1/n, 分散は1/n^2になるかと思います。    

>これは合計した場合ですね。平均を取ると、期待値はその1/n, 分散は1/n^2になるかと思います。
あ、その通りですね。ご指摘ありがとうございます。

(先ほどRemiさんの論文で勘違いしていたところを直したところ、
  9路盤2000po 対GNU Go 3.6 level 0 で 20勝76敗
と、少しはましになったようです。)    

> node作成が凄く少ない様に思えるのですが．これでは余り深く読めないのでは？

読めないです。
19路だと序盤で深さ2手、終盤でも深さ5手ぐらいしか読めていません。
ただ、彩は手の枝刈をやっているせいか、ノードをたくさん作ってUCTでの木を
深くするようにしても強くなりません（逆に弱くなります）
あまり調べていないので何ともいえないのですが。

10000playout行った場合、彩ではrootで9路でも19路でも全部で18手の候補手しか
調べません。最善手が抜けていた場合はかなり致命的です。
最後の愚形のダメを埋めるところなんかで、時々見落として半目負けたりします。

19路で最近効果があった方法は、playoutに行く直前に連の死活を調べて
完全に死んでいる連の味方のダメに打つ手を1/10000にする（ほとんど打たなくする）
という方法でした。GnuGo相手だと勝率0.17から0.33ぐらいまで上がります。
9路だとほとんど効果がないのですが。    

UCT をとことんしゃぶる意味で，一度 1 node/1 po を試してみては？
枝刈りしちゃうとそちらで性能が頭打ちになってしまい，
po が良くなってもそれが表に出なくなっちゃうというリスクがあるのが怖い．    

おっと，言葉が足りませんでした．
Remi の progressive widening のパラメタは 19路用だと思われ，9路ではもっと鈍くした方が良い可能性があります．これと 1 node/1 po を併用するという意味です．    

皆さんいろいろありがとうございます。
>19路で最近効果があった方法は、playoutに行く直前に連の死活を調べて完全に死んでいる連の味方のダメに打つ手を1/10000にする（ほとんど打たなくする）という方法でした。GnuGo相手だと勝率0.17から0.33ぐらいまで上がります。
>9路だとほとんど効果がないのですが。
うーむ9路だと効果が無いのですか。残念です。今回の修士論文は9路で書く予定(というか19路はまだ無理)なので…。今後19路を目指すときに参考にします。
>Remi の progressive widening のパラメタは 19路用だと思われ，9路ではもっと鈍くした方が良い可能性があります．これと 1 node/1 po を併用するという意味です．
なるほど。ちょっと試してみます。
ちなみにさきほど、演算が途中でオーバーフローしていたバグを取り除き、
  9路盤2000po 対GNU Go3.6 level10 18勝82敗
と言う結果が出ました。ましになってきましたが、まだ山下さんには遠く及ばないですね。ちなみに2000poでも100局の実験に3並列化して3〜4時間かかります…。    

> 一度 1 node/1 po を

試してみましたが、GnuGo3.7.10 L10の9路で
候補手の枝刈なし。 2000po 0勝111敗 勝率 0.000  初手で深さ3手ぐらい読みます。
候補手の枝刈あり。 2000po 1勝 71敗 勝率 0.013  初手で深さ9手ぐらい読みます。
と惨憺たる結果でした。

枝刈をもう少しゆるくすれば少しはましになるとは思いますけど。
加藤さんは、9路だと枝刈はまったくされてないのですか？


9路で最近効果があった方法としてはUCTで次にどの手を展開するか選ぶ時のパラメータで、

double factor = sqrt(2.0);
double uct = factor * sqrt( log(この局面を探索した全回数) / 子局面を探索した回数 );
uct_value = 子局面の勝率 + uct;

このfactor を sqrt(2.0) から sqrt(0.9) に変更したら 2000poの1000局で
勝率が0.55から0.60に上がりました。
彩だと、あまり探索回数の少ない子局面を積極的に調べていかない方が強いみたいです。

余談ですけど、英語だと、少ない回数の子局面を調べることを exploration(探査?)、
すでにたくさん調べている手をさらに深く読むために選ぶことを exploitation(開拓?)、
と言ういみたいですけど、日本語に訳する時はどういう単語がいいのでしょうかね？
どうもピンとくる単語がないです。

他には候補手の枝刈をする際に、連の死活探索を行って、死んでいる連のダメに打つ手の
価値を下げて、次の殺せる手、生きられる手の価値を上げると、ちょっと強くなりました。


それと今、19路のCGOSサーバってみなさん見れます？
http://www.lri.fr/~teytaud/cgosStandings.html
私の環境だと一昨日いくらいから、
Forbidden
You don't have permission to access /~teytaud/cgosStandings.html on this server.
と出て、ほとんどアクセスできなくなりました。
対局サーバ自体は動いているのですが。    

深く読んで弱くなるというのは不思議ですねぇ．．．Po のパターンが 9路と合ってないのかな？

そう言えば，Valkyria の Magnus が po の終局時の盤の状態（の平均）を表示する様にしたら，po のバグ取りや問題点のチェックに非常に役立ったと書いてました．これはいい手でしょう．

>加藤さんは、9路だと枝刈はまったくされてないのですか？
GPW の時は MoGo のレポートの fpu の初期値=1.15 以外はやってなかったと思います．今は，これも同レポートの，直前とその前の手とからコスト 2で届く範囲に絞ってますが，あまり大きな差なかったように思います．実際問題として9路ではほとんど全盤面になりますから．あ，序盤は中央と四隅の近傍に絞ってたか．これも大差なかったはず．やはり RAVE が一番効いてます．

>double factor = sqrt(2.0);
これは UCB1 の係数ですよね？　僕は色々試して 0.45 が最善でした．GNU Go 3.7.10 level 0 相手の勝率（千〜二千局，標準偏差は 0.1〜0.2%）は:
0.2->10.2%, 0.4->20.1%, 0.45 -> 20.7%, 0.5 -> 20.3%, 0.7 -> 17.4% でした．
しかし sqrt の中に移すと 0.2 になりますねぇ．．．スコアは±1ですか？　僕は0〜1ですが．．．UCB1-TUNED なら（多少計算コストは増えますが）無調整で最善値に近い結果が得られますから，一度試すのもいいかも．

EvE の翻訳ですが，僕は exploration を探検，exploitation を収穫と訳していたと思います（MoGo のレポートの拙訳をご覧下さい)．

>19路のCGOSサーバってみなさん見れます？
僕も見られなかったので管理者の Olivier にメールしときました．    

> Po のパターンが 9路と合ってないのかな？

playoutのパターンは19路から収集したので9路では少し甘いような気はします（特に盤端周辺では）。
ただ、それよりはUCTでの探索のさせ方がどこかまずいような気もします。
（そもそも何が正しい方法かはまだ確立してませんけど）
ちなみに彩のUCT部分は下のような感じです。
http://www32.ocn.ne.jp/~yss/uct_aya.cpp

> po の終局時の盤の状態（の平均）を表示する様にしたら

これは私もやってます。
最後に石が存在した場所＋地になった場所、を合計して黒のエリア+100%、白のエリア-100%で
表示させてます。
攻め合いで死んでいる石なのに中途半端に生きると思ってる、とかが分かって便利です。

9路では枝刈なしなのですか・・・。
RAVEは少しやって、あきらめてしまったのでもう少し試してみます。

> スコアは±1ですか？

はい。

> UCB1-TUNED なら（多少計算コストは増えますが）無調整で最善値に近い結果が

そうなのですか。もう一度MoGoの論文見直してみます。

> 僕も見られなかったので管理者の Olivier にメールしときました．

ありがとうございます。見れました。
ただ更新されていないようなので私も催促メールを送ってみます。    

>playoutのパターンは19路から収集したので9路では少し甘いような
これはありそうですね．いずれにせよ一度ちゃんと作るに越したことはありませんが．．．
>ちなみに彩のUCT部分は下のような感じです
読んでみます（C++ は好きではありませんがｗ)．
>攻め合いで死んでいる石なのに中途半端に生きると思ってる
うむ，これは私もやらねば．でも GoGui 使ってるから別途作るのも面倒なんですよね．
>> スコアは±1ですか？
>はい。
ふむ，ならいいのかな．分散だから4倍にsqrtで結局2倍．
0.45x2=0.9，sqrt(0.9)≒0.95でほぼ同じですか．
>ただ更新されていないようなので私も催促メールを送ってみます
ML の方に
>the 19x19 CGOS ranking page is back (but might be still unstable)
>and Leela seemingly performs quite well.
>The crosstables will come back soon also.
という投稿があったから，もう少し待った方がいいかも．    

貴重な情報交換中、腰を折るようですが、

>余談ですけど、英語だと、少ない回数の子局面を調べることを exploration(探査?)、
>すでにたくさん調べている手をさらに深く読むために選ぶことを exploitation(開拓?)、
>と言ういみたいですけど、日本語に訳する時はどういう単語がいいのでしょうかね？
>どうもピンとくる単語がないです。

と、山下さんがどういう単語がいいか、悩まれているようなので、
私が日頃、好き勝手に呼んでいる造語を書いてみます。参考になれば幸いです。(なるんかいなー)(^^

私は、「少ない回数の子局面を調べること」を【少考探査】と呼んでいます。
意味合いとしてプロ棋士が難しい局面に「長考」すると言うので、少ない局面(簡単)に対し「少考」とし、
調べるだけで求めてないので、「探査」で【少考探査】、
逆に「多い回数の大局面を調べること」を【長考探査】です。(^^\

そして、「すでにたくさん調べている手をさらに深く読むために選ぶこと」を【探索深度】と呼んでいます。
意味は「すでにたくさん調べている」と求め得ているので「探索」、
「さらに深く読むために選ぶこと」と深く読むために選び求めるで【探索深度】です。
また、
Aより広く調べる、求めるを【拡張探査】【拡張探索】、
Aより狭く調べる、求めるを【縮小探査】【縮小探索】と勝手に呼んでいます。(^^;

そのままの直訳が良いのか、ピンとくる造語が良いのか、はよくわかりませんが、
「コンピュータ将棋の進化」を執筆された方々が提案して単語を統一された方が、
ひとつの事に各人が造語を当てるのは混乱の元かもしれません。

ちなみに私の造語が仮に採用されたとしても「造語使用料」は請求しませんのでご安心を…(なんのこっちゃー)(^^A    

>読んでみます（C++ は好きではありませんがｗ)．
このリストには評価値は [0..1] の様に書いてありますが，はて？

一つ気になったのが，uct_tree を再帰的に呼ぶ前後で木のロックを解除している事．一番下に行く迄解除してはいけないと思います．どう影響するかは分かりませんが．これが深く読んでも強くならない原因かも？

このハッシュ表だと劫がうまく扱えないのではないかと．Remi は劫の有無で別のハッシュ値になる様にしてると書いてました．僕は未だ実装してないので分かりませんが．

僕は天元から渦巻順になってる空点のリストを持っていて，これと ucb (uct_value) の初期値（fpu）を 1.15 にすることで，progressive widening 的な効果を得ています．今の MoGo は，この初期値をパターンを使って計算しているようですが．山下さんのは初期値乱数＋progressive widening なので，かなり妙なことになりそうな気がします．やはりここにもパターンを使うべきでしょう（progressive widening を使うなら)．あるいは未展開の手に与える初期値を 1+ε にするのも簡単な手法でしょう．

しかしノード作成，そんなに重いですか？　一度ちゃんと profile を取ることをお勧めします．私の場合（連の構造なども保存して）確か 9路でも 20%程度だったと思うので．    

>どう影響するかは分かりませんが．
一例として，負けになった po による更新と勝ちになった po による更新が入り混じったら無茶苦茶になるでしょう．    

加藤さん重複書き込みになってますね。
>そう言えば，Valkyria の Magnus が po の終局時の盤の状態（の平均）を表示する様にしたら，po のバグ取りや問題点のチェックに非常に役立ったと書いてました．これはいい手でしょう．
なるほど、盤の状態の平均ですか。今まではpoの終局時の盤の状態を適当にサンプルして見ていたのですが、確かに平均を取ったほうが分かりやすいですね。

訓練時にパターンの対称性を考慮するのを忘れていたのを直して、先ほどGNU Go 3.6のlevel10とlevel0と、9路盤2000poで100局ずつ打たせてみたのですが、
  level0…こちらの17勝83敗、level10…こちらの23勝77敗
という結果になってしまいました。level0ってそんなに弱くないんですね。それと、100局だとやはりかなりばらつくんですね。
加藤さんが最低600局とおっしゃってましたが、600局なら何とか間に合いそうなので(一回の実験に3,4並列で24時間くらい、マシンを3台くらい使えば十数通りは試せる)、600局でやってみようと思います。600局なら、勝率が0〜23%くらいで固まっても有意な差を論じやすいと思いますし。MoGoを使うことも考えたのですが、やはり論文での強さの評価はGNU Goで行うことが一般的な気がするので…。    

>加藤さん重複書き込みになってますね。
あらら，投稿直後に確認した時は問題なかったのに．通信エラーかな？　できれば削除して下さい＞管理人さん
>level0ってそんなに弱くないんですね
そうですね．手元のデータから推定すると -150ELO 位かな．でもスピードはかなり違う．
〆切は今週末？　ならもうデータ採り始めるしかないか．必要ならうちのマシンパワーも貸しますからメール下さい（現在4+2コア空いてます)．では，致命的なバグが無い事を祈って．    

重複書き込み消えてますね。
加藤さんどうもありがとうございます。提出は来週の火曜日です。英語で書くのが大変ですが…。現在7000words。実験はおそらく自作マシンと研究室の共用サーバーで大丈夫だと思います。
ひとまず今夜バグが無いことを確認するために30000po(Progressive Widening無し)で何局か打たせてみます。Remiさんの論文によるとこれくらいのpoで68.2%の勝率らしいので、それに近い勝率が出れば安心して実験が出来るかなと思います。まあ、そうでなくてももう実験するしかないかもしれませんが。    

重複は消しておきました。

> 一つ気になったのが，uct_tree を再帰的に呼ぶ前後で木のロックを解除

実験はほとんど1スレッドでやっているのであまり関係がないと思いますけど

> 負けになった po による更新と勝ちになった po による更新が入り混じったら

うーん、ちょっとよく分かりません。

> このハッシュ表だと劫がうまく扱えないのではないかと

彩では
uint64 hashboard64[BOARD_SIZE][3];
として、[1]...黒の石 [2]...白の石、[0]...コウが発生した場合
で扱っています。コウが発生した場合は盤面が完全に同じでも別局面扱いしています。
(KGSとかCGOSでは盤面だけの同一局面を作ると負けになるので、別に処理をしてます）

> しかしノード作成，そんなに重いですか？

ノードを作るときに手をソートしてるのですが、その時、全部の石の死活探索を
やってるのでかなり重いです。
今後はここに眼の認識、群の認識、も入れようと思ってます。


factorの調整ですが、さらに sqrt(0.1) (= 0.32) にして
19路で10000poでGnuGoと対戦させると
勝率が 0.10(660局) から 0.22(140局) まで上がりました。
こんな小さなパラメータの変更だけでこれだけ変わる、というのが
意外というかなんだこりゃ？という感じです。    

荒木君 >加藤さんが最低600局
この数字を鵜呑みにせずに，勝率と局数から標準偏差をちゃんと計算しましょう（この計算式も論文に明記)．標準偏差の値は信頼区間 68%（いわゆる1σ)，言い換えると3回に1回間違える幅なので，できれば2σ（信頼区間 95%）でやりたいところです．

山下さん >重複は消しておきました
お手数掛けました (_ _)．
>ほとんど1スレッドでやっているので
そうですか，これが原因じゃないのか．．．とすると 10000+rand_mc_max(100) の方かな？　いずれにせよここで乱数を使うメリットは無いと思いますが．．．
>>負けになった po による更新と勝ちになった po による更新
要するに木の状態が一貫しなくなる可能性があるということです．ある状態であるレベルまで降ってきた時に他のスレッドがそのノードの値を更新したとしましょう．それに対応して降ったけど，その時また別のスレッドがそのノードを更新してたら，一体何を計算してるのか分からなくなります（UCB1 アルゴリズムの前提が壊れます)．
なので，少なくとも後半の更新パートだけはロックを掛けたまま（他のスレッドが割り込まない様にして）実行すべきである，と．また，前半の木を降る部分も一気にやった方が良いはずです．無茶苦茶な探索はしないと思いますが，木の状態が変わった時は root から再スタートした方が better なので（po が最も expensive として)．

劫の件了解．ちゃんと処理されてるんですね．私も早く実装せねば（汗．

>こんな小さなパラメータの変更だけで
これは UCB アルゴリズムの肝になる係数で，本来対象の確率分布に合わせて調整すべきものです．これを対象に合わせて動的に適応させるアルゴリズムに関する賞金付きのコンテストが開かれた位重要なものです．＃従って最適値は po の policy にも依存するはずです．
最適化問題の枠組みで考えると，これで EvE のバランスが変わるので，1 po の効率が大幅に変わります．逆に po 数固定で考えると，強さが大きく変わることになります．
＃この現象は山下さんの実装が間違ってないことの状況証拠になっているとも言えます．    

>この数字を鵜呑みにせずに，勝率と局数から標準偏差をちゃんと計算しましょう（この計算式も論文に明記)．標準偏差の値は信頼区間 68%（いわゆる1σ)，言い換えると3回に1回間違える幅なので，できれば2σ（信頼区間 95%）でやりたいところです．
わかりました。ありがとうございます。

一晩30000poで打たせてみた(9路盤GNU Go 3.6 level10)ところ、こちらの7勝22敗という散々な結果になりました。poを15倍にしているのに勝率があまり変わらないというのはバグの可能性が高い気がします。もうちょっとだけバグチェックしてみます。    

>poを15倍にしているのに勝率があまり変わらないというのは
間違いなくバグです．po 数 2倍で 70乃至 100 ELO 強くなるはずです．恐らく UCT の実装にミスがあるんでしょう．木を降りる時と値を繰り上げる時に手番をちゃんと入れ替えてるか＆値を反転してるか，UCT 内で終局していた時/した時の処理，辺りでしょうか，バグり易いのは．

ログファイルをじっくり調べましょう．くれぐれも焦らないように．    

23,24日と、石川県のJAISTで世界最強決定戦が行われて
総当りの結果、2勝1敗で激指とYSSが同率優勝しました。
選手権のようなスイス式で順位を決めるのではないので、
優勝は2つ、準優勝がTacosとBonanza、となっています。

　　　　激 YS Ta Bo  勝敗 順位
激指       ○ × ○  2-1   1
YSS     ×    ○ ○  2-1   1
Tacos   ○ ×    ×  1-2   2
Bona    × × ○     1-2   2

第3回 コンピュータ将棋 世界最強決定戦 2008
http://www.jaist.ac.jp/rccg/saikyo/

地方紙では4,5社ほど取り上げられていました。
北陸中日新聞ではWebの記事も見れます。

“電脳棋士”が熱戦　先端大　『世界最強決定戦』が開幕
http://www.chunichi.co.jp/article/ishikawa/20080124/CK2008012402081985.html

中日新聞の記事は詰将棋メモさん経由で知りました。
http://toybox.tea-nifty.com/memo/2008/01/post_5e7e.html    

お久しぶりです。何とかバグ取れました。
あれから、UCTやモンテカルロシミュレーション部の細かなバグをいろいろ取り除いていたのですが、なかなか改善しませんでした。その後、盤のコピーコンストラクタのバグを直し、ようやく、9路盤対GNUGo3.6のlevel10で
  2000po こちらの35勝65敗
  4000po こちらの41勝59敗
  8000po こちらの48勝52敗
という結果がでました。もう600局対戦で実験する時間は無いので、100局対戦の実験をしようと思います。
いろいろありがとうございました。加藤さんと山下さんの名前をAcknowledgementに入れさせていただきます。また、加藤さんと山下さんのモンテカルロのソースをReferenceに入れさせていただきます。    

>  2000po こちらの35勝65敗
>  4000po こちらの41勝59敗
>  8000po こちらの48勝52敗
勝率 35%は -107.5, 41%は -63.2, 48%は -13.9 ELO になるので po 2倍で 50 ELO ほど
強くなってます．4000 po で level 10 相手に勝率 41% はかなりのレベルですが，
ちょっと po 数に対する強さの伸びが小さい感じなので，まだ改善の余地があるように
思えます．    

そうですか…。Ratingと勝率の関係式は知らないのですが…。
確かにttp://computer-go.org/pipermail/computer-go/2006-July/005737.htmlを見ると、po二倍にしたらもうちょっと勝率上がってもいい気がしますね…。ただ、もうデバッグしている時間は無いので、「大きなバグは無いだろう」ということで実験してしまおうと思います。    

あ，そういう意図ではなかったのですが．．．
いくつかありますが，通常 rating = 400 log10(p/(1-p)), p = 勝率，が使われてます．
Po との関係は丁度今かなりの規模の実験の最中で，↓をご覧下さい．
http://cgos.boardspace.net/study/index.html
ただ，このレベルだとバグとは限らない様に思います．春休みにでももう少しデータを増やして調べて頂ければ幸いです．    

ratingと勝率の関係の式、ありがとうございます。
なるほど。こんな実験があったんですね。
卒業後も趣味で研究は続ける予定なので、暇を見つけてデータを増やして調べてみます(他にも試してみたいアイディアがあるのでそっちが先になるかもしれませんが)。
先ほど訓練時のちょっとしたバグを取り除いたところ、2000poで42%の勝率が出ました。まあこの程度の値ならたまたま良かったと言うことかもしれませんが。4000poと8000poは時間が無いので試していません。また今度ということで。    

私も忘れていたので先ほど申し込みました。
http://www.computer-shogi.org/wcsc18/

FPGAのA級リーグ指し手１号さんも申し込まれていました。
楽しみです。    

皆さんのおかげで無事修士論文の一回目の提出を乗り切ることが出来ました。どうもありがとうございました。まだまだやるべきことはありますが…。
実験結果ですが、「Move Predictionの精度(テストデータにおける人間の手との一致率)は、それを組み込んだモンテカルロ碁の強さの指標にはならない」という感じです。まあ、自明な結果かもしれませんが。詳しいことが知りたい方がもしいたら、ここで質問して下さってもかまいませんし、ttp://ark.qp.land.to/main.pdf(修士論文本体)とttp://ark.qp.land.to/backup.tar.gz(ソースコード)を見てくださってもかまいません。    

拝見させていただきました。
Acknowledgementに載せていただいてうれしいです。

一致率(accuracy)、とは一番確率の高い手が人間の手と一致する確率、ということで
いいのでしょうか？
3x3(＋上下左右で12箇所)のパターンとアタリや近傍だけで29%もあるのはかなり高いですね。
もっと大きいパターンもいれた状態で34%、とのことですので、小さなパターンだけでも
それほど確率は落ちないのですね。

私は3x3のパターンにアタリや近傍を入れても22%しかプロの棋譜とは一致しませんでした。
大きなパターン(菱形で距離5まで)を追加しても23%でした。
単純な出現頻度だけの確率しか使っていないのですが、最大エントロピー法や
Remiのレーティングを付ける方法の方がはっきり優秀なのでしょうか。

アタリ、にしたがるようにすると、一致率は変わらないのに弱くなる、
というのは面白いですね。私も弱くなったので外した記憶があります。
(ダメが2にされた石の、周囲のダメ2の敵のダメを埋めるようにしたら少し強くなりました)

石の配置だけのパターンが一致率のほとんどを占めていそうなので
3x3の8箇所だけや、上下左右の4箇所だけのパターンだけだとどのくらい弱くなるか、
も気になりました。（もっと大きなパターンだとどうなるかも）


将棋ではYSSに1手20秒考えさせて試したところ
プロの棋譜3つで合計323手で

一致率       166/323=51%
このうち
定跡手だと    34/ 55=62% （一番頻度の高い手を最善手として数えています）
定跡以外だと 132/268=49%

将棋だとアマ5段程度で一致率は50%程度になるようです。    

>一致率(accuracy)、とは一番確率の高い手が人間の手と一致する確率、ということでいいのでしょうか？
その通りです。ただ、モンテカルロにおいては一番確率の高い手だけを使っているわけではないので、上位n個の一致率と比較したほうが良かったかもしれません。

>3x3(＋上下左右で12箇所)のパターンとアタリや近傍だけで29%もあるのはかなり高いですね。
>もっと大きいパターンもいれた状態で34%、とのことですので、小さなパターンだけでも
>それほど確率は落ちないのですね。
そうですね。大きいパターンを入れると序盤の一致率が急激に上がるのですが、序盤が終わるともう大きいパターンは出現しないので、全体としてはそれほど一致率は上がりません。

>私は3x3のパターンにアタリや近傍を入れても22%しかプロの棋譜とは一致しませんでした。
>大きなパターン(菱形で距離5まで)を追加しても23%でした。
>単純な出現頻度だけの確率しか使っていないのですが、最大エントロピー法や
Remiのレーティングを付ける方法の方がはっきり優秀なのでしょうか。
そうですね。おそらく最大エントロピー法やRemiのレーティングをつける方法(これらは数値計算のアルゴリズムは違うものを使っているが、モデルとしては実は同じ)のほうが、複数の素性を使う場合は、優れていると思います。修士論文のMove Predictionの章(僕の論文:Move Prediction in Go with the Maximum Entropy Methodがベース)で、最大エントロピー法によるRerankingありと無しの比較をしているのですが、上位10個くらいまでは最大エントロピー法を使ったほうが優れていました。ただし、修士論文にも書いたのですが、最大エントロピー法はメモリを食うので(今回のモンテカルロの実験では6Gちょっと食った)、メモリを大量に積んだマシンが無いとつらいですが。一応Amisというライブラリには、メモリが足りないときにファイル上で計算すると言うオプションがあるのですが当然かなり遅くなります…。

>アタリ、にしたがるようにすると、一致率は変わらないのに弱くなる、
というのは面白いですね。私も弱くなったので外した記憶があります。
あ、いえ違います。あの表は、取り除いた素性と、一致率と強さの関係を表しているので、「アタリを取り除くと」弱くなるということです。山下さんの経験と逆ですか…。バグで無ければいいのですが。ただ、僕はアタリを入れたほうが強くなるのが自然だと思います。なぜかと言うと、人間が囲碁を打つとき「やたらとアタリを打つな」とは言われますが、読むときはアタリも読むことが多いからです。モンテカルロにおいては、人間が実際に打つ手だけだなく、頭の中で読む手もシミュレーションすることが大事だと思っています。(これについては研究のアイディアがあって、修士論文の直しがひと段落したら試す予定です。)

>石の配置だけのパターンが一致率のほとんどを占めていそうなので
3x3の8箇所だけや、上下左右の4箇所だけのパターンだけだとどのくらい弱くなるか、も気になりました。（もっと大きなパターンだとどうなるかも）
そうですね。それも実験するべきでした。今回は時間が無かったのですが、修士論文の最終提出までには実験します。

>将棋ではYSSに1手20秒考えさせて試したところ
>プロの棋譜3つで合計323手で
>一致率       166/323=51%
>このうち
>定跡手だと    34/ 55=62% （一番頻度の高い手を最善手として数えています）
>定跡以外だと 132/268=49%
>将棋だとアマ5段程度で一致率は50%程度になるようです。
アマ5段程度で一致率50%ですか。かなり高い気がしますね。囲碁と将棋とでゲームの性質が違うと言うのもあるのでしょうけど。まあ、僕は将棋は弱いのでよく分かりませんが。うろ覚えなのですが、GPW2006でBonanzaが発表したときは35%とかだった気がするのですが。YSSとBonanzaでこんなに違うのは気になります。    

書き忘れていましたが、「最大エントロピー法がメモリを食う」というのは訓練時の話です。実行時は相対頻度を使うのと変わりません。    

横から失礼します、荒木の共同研究者の吉田と申します。
以下でRemi Coulomさんの仕事として言及するのは、"Computing Elo Ratings of Move Patterns in the Game of Go"です。

＞これらは数値計算のアルゴリズムは違うものを使っているが、モデルとしては実は同じ

"Move Prediction in Go with the Maximum Entropy Method"で使っているモデルは、各候補手に対して、それが打たれるかどうかの二値分類をしているので、Move Predictionの手法としてはRemiさんのモデルとは少し違うものになっている、ということでいいですよね？修士論文のうしろの方で、モンテカルロ法を使っている部分では、Remiさんと同じモデルを使っている、と。統計的なモデルとしてはどちらにしても同じものなのだと思いますが。（ガウス分布などで正則化している分、我々の方がやや有利になっているかもしれません）

数値最適化の部分は、きちんと調べたわけではありませんが、おそらく最大エントロピー法（ME）で普通に使われている手法の方が、Remiさんのものよりだいぶ高速なのではないかと思います。少し古いですが、
http://bulba.sdsu.edu/malouf/papers/conll02.pdf
で比較されている手法の中では遅い方のGISなどでも、Remiさんの手法より良いのではないかと想像しています。（実装も簡単です。ガウス分布による正則化を入れると、少し面倒になりますが）この件についてはRemiさんに直接メールしてみたのですが、（許可を取っていないので具体的なことは書きませんが）Remiさんの方でも論文の時点から進展があったそうです。


＞最大エントロピー法はメモリを食う

そうですよね。あと時間も。
個人的には、一致率を稼ぐだけならMEのようなモデルでまじめに計算する必要はなくて、Averaged Perceptronのような高速な手法で、訓練データを増やす方が良いのではないかと思うのですが（Move Predictionのような問題では、正解つきデータが割と大量に使えるので）、Perceptronではまともな確率分布は計算できないので、モンテカルロ法に使った時どれ位うまくいくかは分らないですね。（自分で試せればよいのですが…）
MEの方でも、上の論文以降で、より高速な推定手法が提案されているようですが、扱いづらいものが多そうな印象をもっています。

強い碁のプログラムを作る上で、こういうことがどれくらい役に立つかというようなことも考えるとまた難しそうですね。


＞「アタリを取り除くと」弱くなるということです
MEでは、例えばパターンとは別にアタリに関する素性を入れても（あるいは、さらに両方の組み合わせを入れたりしても）、訓練データに合わせてうまく重みを調節してくれるので、その辺が効いていそうな気もします。相対頻度で似たようなことをするのはかなり面倒なのではないでしょうか。    

すっかりお返事が遅くなりましたが、

> あの表は、取り除いた素性と、一致率と強さの関係を表しているので、
> 「アタリを取り除くと」弱くなるということです。

あ、そうですよね。すみません。自分の経験と合っていそうだったので
誤読してました。アタリにする確率、は統計を取らずに適当に試しただけなので
再度試してみます。

> GPW2006でBonanzaが発表したときは35%とかだった

でしったけ？
ただ、将棋では相当強いプログラムでも50%程度なのに
探索も何もしていない周囲の形程度の知識だけで34%も一致する、
というのはかなりすごいのではないかと思います。
分岐因子は将棋の80に対して囲碁は220程度と3倍近いのに。

逆に言うと、囲碁でこれだけモンテカルロ法が成功している理由の一つに
小さなパターンとの関連性が極端に高い、というのがありそうな気がします。

補足ありがとうございました。＞吉田さん    

現在の彩を銀星囲碁7と対戦させてみましたら、28勝5敗と
予想外に彩が勝ち越しました。

彩はXeon 2.66GHz Quad Core x2 (合計8コア)で走らせており、
1手に240000 playout を行います(30000 x8)。
この条件だと1局で25分ほど使います。

銀星囲碁7も同じマシン上で、ほぼ同じ思考時間です（こちらは1コアしか
使いませんが）レベルは「最上級」思考時間は「無制限」棋風は「一般型」
コミは6目半、を利用しています。アップデートはあて忘れました。

・コミは双方6目半。
・彩は中国ルールで打っています（終局判定も中国ルールを採用してます）
・相手がPASSしたら無条件でPASSしてます。

棋譜はこちらです。
http://www.yss-aya.com/gin7_ayamc.zip
ほとんど中央をどかんと取って勝つ、というパターンばかりです。

GnuGoに対しては
10000 playout 勝率 0.23
40000 playout 勝率 0.32
程度の勝率なので銀星7に対しては少し彩の相性が良いようです。

今までの彩は140回対戦させても1回も勝てなかったのですが・・・。
モンテカルロ法の威力は本当にすごいです。

余談ですが、Windows Vista、の Aeroだと画面を読み取るGetPixel()という関数が
極端に遅い(1回で0.1秒程度)ので、最初傀儡師がまともに動きませんでした。
画面のテーマをクラシックにすればOKでした。    

>誤読してました。
僕の論文がひどいせいでしょう。加藤英樹さんにメールで厳しい指摘を頂きましたし。
ちなみに、600対局での実験が終わったのですが、以下のようになりました。精度は19路盤、勝率は9路盤GNUGo3.6 level10相手のもの。playout数は一手あたり2000。±は標準偏差です。
�@訓練データ量を25%,50%,75%,100%と変えたとき
量  |Top1精度(%)|Top10精度(%)|勝率(%)
----------------------------------------
25% |28.5±0.133|61.3±0.143 |34.2±1.94
50% |29.2±0.134|61.7±0.143 |32.3±1.91
75% |29.4±0.134|61.9±0.143 |33.7±1.93
100%|29.3±0.134|62.0±0.143 |38.0±1.98
----------------------------------------
こちらの実験は標準偏差が大きいので強いことは言えませんが、もう少し細かくデータ量を変えてみたり、データ量を増やしてみたりすると面白いかなと思っています。

�A素性を一つ取り除いて作った複数のシステムの比較
取り除いた素性  |Top1精度(%)|Top10精度(%)|勝率(%)
----------------------------------------------------
無し            |29.3±0.134|62.0±0.143 |38.0±1.98
石を取る1       |28.2±0.132|61.6±0.143 |25.8±1.79
石を取る2       |29.4±0.134|62.0±0.143 |36.7±1.97
石を取る3       |29.3±0.134|62.0±0.143 |33.0±1.92
石を取る4       |29.3±0.134|62.0±0.143 |37.2±1.97
アタリから逃げる|28.1±0.132|61.5±0.143 |40.7±2.01
自己アタリ      |29.2±0.134|61.7±0.143 |35.7±1.96
アタリ          |29.5±0.134|62.3±0.142 |24.0±1.74
直前の手との隣接|24.2±0.126|58.7±0.145 |11.2±1.29
二手前との隣接  |28.9±0.133|59.9±0.144 |30.7±1.88
----------------------------------------------------
修士論文の最初のバージョンに載せた数値に比べて標準偏差がだいぶ小さくなったので、いろいろ言えると思います。特に「アタリから逃げる」と「アタリ」を比較すると、やはりMovePredictionの精度はモンテカルロの強さの指標としては微妙なのかもしれないと言えるのではないでしょうか。実際、山下さんのほうがMovePredictionの精度は低いのにモンテカルロとしては強いわけですし。
そして、computer-goのメーリングリストにも書いたのですが、精度すなわち人間の手との一致率が強さの指標にならないなら、そもそも人間の手を正解データとした学習が間違っている可能性も高いのではないかと思っています。これについては試してみたいことがあるので、空き時間を見つけて実験したいと思っています。

>ただ、将棋では相当強いプログラムでも50%程度なのに
>探索も何もしていない周囲の形程度の知識だけで34%も一致する、
>というのはかなりすごいのではないかと思います。
>分岐因子は将棋の80に対して囲碁は220程度と3倍近いのに。
うーん、どうなんでしょう。一度人間の有段者をたくさんあつめて、人間のMove Predictionの精度測定をやってみたいですね。将棋も囲碁も。昔そんな実験を見た気がするのですが、記憶があいまいです。

>逆に言うと、囲碁でこれだけモンテカルロ法が成功している理由の一つに
>小さなパターンとの関連性が極端に高い、というのがありそうな気がします。
モンテカルロ将棋を卒論でやっている人がいると聞いたことがあります。将棋でどうなるか、その結果が楽しみです。

あと、銀星囲碁に大幅勝ち越しとはすごいですね…。僕も早くそのレベルまで達した上で実験したいものです。    

> 75% |29.4±0.134|61.9±0.143 |33.7±1.93
> 100%|29.3±0.134|62.0±0.143 |38.0±1.98

75から100で急にポンと上がってますね。なんとなく誤差っぽいですけど。
Remiは652局程度のデータでかなり成績が良かったですから、学習の棋譜は
それほど必要ないのでしょうか。

> 直前の手との隣接|24.2±0.126|58.7±0.145 |11.2±1.29

これがめちゃくちゃ強力だったんですね。

> やはりMovePredictionの精度はモンテカルロの強さの指標としては微妙

今のプログラムの棋力と比較して、プロの棋譜との一致度を見るのは
少しレベルが高すぎるのかもしれません。

Remiのデータでも思ったのですが、コウが発生したときにアタリを打つ確率、
というのがKGSの棋譜では高かったのですけど、プロの棋譜ではそうでも
ありませんでした。
相手が悪手を打った時に正しく応じるパターン、とかが収集されないのかも
しれませんね。    

>相手が悪手を打った時に正しく応じるパターン、とかが収集されないのかも
>しれませんね。
それについては、弱い人の棋譜に対してGNUGoで正解データをつけて学習すればある程度解決するかなと思っています。    

論文の英語に関しては，Remi の exotic が言いえて妙です．ま，公の場ですし，彼は優しいからこういう言い方をしているのでしょう．ただ彼も言ってるように，native が誤読する可能性は低いのが幸いでしょうか．厳しい物言いは期待しているからこそですよん（はぁと．

人間の棋譜からの学習が云々は全くその通りで，強い人同士の棋譜の場合，お互いに潰し合ってる手は棋譜には表れないので明らかに不十分です．弱い人と強い人の対局の棋譜も必要だとずっと前から思ってました．

最初の表は一致率が 19路，勝率は 9路のものなんですよね？　9路の一致率じゃないと意味がないような．．．これでは勘違いされるだけでしょう．    

英語はすいません…。
二つの表は、一致率19路、勝率9路です。9路での一致率も計りたいのですが、棋譜が大量に手に入らなくて…。ずうずうしいかもしれませんが、以前この掲示板で話題になった9路盤の棋譜を頂けませんか?
勝率と一致率で盤のサイズが異なるのは気になっていたのですが、1回目の提出までに19路で打てるほど強くならなかったことと、小さな素性しか使っていないから9路で計ってもも大丈夫だろうと思ったことが理由で無視していました。製本提出までには19路で打てるようになればいいのですが…。そのためにはまず50倍の高速化をしないと…。    

これは岡崎さんに連絡してみます．が，岡崎さんの話によると色々ミスがあるとか．
それでも良ければ喜んで．    

今月送られてきたICGAジャーナル(2007年12月号)に
昨年の10月に中国で開催された
The 2nd Chinese Computer-Games Championship(第2回中国コンピュータゲーム大会)
の記事が出ていました。

シャンチー、19路、9路、Connect 6の4つの大会が開催されたそうで、
シャンチーは16チームが参加して上位10チームが決勝に残り CYCLONE が優勝。

19路盤は9ソフトが参加して Handtalk が全勝優勝。
9路は6ソフトが参加して Beiyou 2 が全勝優勝しています。
Beiyou というのは北京郵電大学(Beijing University of Posts and Telecommunications)
のコンピュータ囲碁研究部門が作成しているそうです。
3人のリーダーがいて、うち二人は中国のプロ棋士である Bin Yu 9段と Ping Yu 6段とのことです。
2年以内に人間の世界チャンピオンに勝つ！のが目標とのことです。

特記すべきは、今年の9月に北京で開催されるComputer Olympiadに
KCC囲碁とHandtalkがそれぞれ出場する予定、とのことです。

19路盤   2007年10月3-8日、中国 重慶、重慶工科大学

                 HT B2 GS B3 OC BS B1 BR NH  Wins
1 HandTalk           1  1  1  1  1  1  1  1   8
2 Beiyou 2        0     1  1  1  1  1  1  1   7
3 GoStar          0  0     1  1  1  1  1  1   6
4 Beiyou 3        0  0  0     1  1  1  1  1   5
5 Ocean           0  0  0  0     1  1  1  1   4
6 BitStronger     0  0  0  0  0     1  1  1   3
7 Beiyu 1         0  0  0  0  0  0     1  1   2
8 Break           0  0  0  0  0  0  0     1   1
9 NineHeadBird    0  0  0  0  0  0  0  0      0

9路盤
                 B2 HT GS B3 BR BS   Wins
1 Beiyou 2           1  1  1  1  1    5
2 HandTalk        0     1  1  0  1    3
3 GoStar          0  0     1  1  0    2
4 Beiyou 3        0  0  0     1  1    2
5 Break           0  1  0  0     1    2
6 BitStronger     0  0  1  0  0       1

写真(左からBin Yu 9段、Handtalkの陳先生、Xinhe Xuさん)
http://picasaweb.google.com/yoenix/2/photo#5119156078609551778    

貴重な情報ありがとうございます．まだ陳先生頑張ってるんですねぇ．棋譜はありませんか？
>2年以内に人間の世界チャンピオンに勝つ！のが目標とのことです
うわ，しかし人間の世界チャンピオンって誰？
>KCC囲碁とHandtalkがそれぞれ出場する予定
お〜，クラスタ版 MoGo，Crazy Stone との対決が見ものですねぇ．山下さんも行きますよね？　食べ物と空気は心配だけど．．．    

>>2年以内に人間の世界チャンピオンに勝つ！のが目標とのことです
>うわ，しかし人間の世界チャンピオンって誰？
9路だと誰なんでしょう…。2年以内に勝つと言っているからさすがに9路の話なんでしょうけど。19路なら韓国のイーチャンホやイーセドルあたりですか。
>KCC囲碁とHandtalkがそれぞれ出場する予定
うーん見ものですね。行ってみたいですが会社の休みがとれないですね…。学会発表のために休み取るのも難しいらしいので。

先ほど、ふと碁盤のコードのローカル変数に関してconstをつけたら、速度が1.5倍速くなったり4倍遅くなったりして戸惑っています。1.5倍速くなるのは分るのですが(今までconstをしっかりつけていなかったのは怠慢)4倍遅くなるのはちょっと…。みなさんは囲碁プログラム開発中にそんな現象ありましたか?    

>>うわ，しかし人間の世界チャンピオンって誰？
>9路だと誰なんでしょう…。2年以内に勝つと言っているからさすがに9路の話なんでしょう>けど。19路なら韓国のイーチャンホやイーセドルあたりですか。
多分19路のチャンプに9路で打って貰うつもりなんでしょう．
>>KCC囲碁とHandtalkがそれぞれ出場する予定
>うーん見ものですね。行ってみたいですが会社の休みがとれないですね…。
有給は？　一年目は無いのなら親戚に死んで貰いましょう（爆．    

私も可能なら行くつもりです。

> constをつけたら、速度が1.5倍速くなったり4倍遅くなったりして

const程度でそれだけ変わるとうのはかなり極端ですね・・・。
私はinline関数にしたら1.2倍、とかぐらいが最大でした。
playoutの部分は非常に小さくてそこだけ100万回とか呼ばれるので
劇的に変わることもありそうですけど。    

あ，忘れてた．
> constをつけたら、速度が1.5倍速くなったり4倍遅くなったりして
まず profile で当たりを付けてから .s を見比べるしかないでしょう．Case by case ですから．
何に const を付けたかすら書いてないんじゃ何も分かりませんが，多分ポインタでしょうか．ただ，付けたら遅くなるというのはちょっと考え難い．．．g++ の最適化のバグ（に近いもの）ではないでしょうか．
ついでに書いておくと，一般にポインタより添字の方が最適化され易い．    

山下さん、加藤さん

あ、すいません。簡潔にうまく状況を説明する方法が分からなくて…。とりあえず、.sを見比べてみます。x86のアセンブリは全然わかりませんががんばります。
あと、最適化のバグの可能性は他の人にも指摘されました。    

CGOSの将棋版？ともいえるfloodgateモードxwdoorが動いています。
作者の金子さんには感謝！です。
YSSも近いうちに走らせてみます。

連続対局場所
http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html
レーティング
http://wdoor.c.u-tokyo.ac.jp/shogi/logs/LATEST/players-floodgate.html
対戦成績
http://wdoor.c.u-tokyo.ac.jp/shogi/tools/view/latest-table.cgi?event=LATEST&filter=floodgate&show_self_play=1
金子さんのブログ
http://www.sgtpepper.net/kaneko/diary/    

山下さん、ご紹介ありがとうございます。
将棋プログラマのみなさまのご参加をお待ちしています。15分切れ負けで対局を沢山行おうという企画です。お気軽にお試しください。

(サーバの機能を実装したのはGPSで一緒にやっている森脇でした。)    

「と金倶楽部」なる掲示板サイトを立ち上げました。お暇な時にお越し下さい。

http://www.tokinclub.com 
http://www.tokinclub.com
   

>有給は？　一年目は無いのなら親戚に死んで貰いましょう（爆．
ComputerOlympiadのページを見たのですが、全部で一週間ですか…。全部行くのは無理そうですね(連続して有給をとれるのは2日くらいらしい)。碁のcompetitionが一週間のうちのいつあるかはまだ公表されていないのでしょうか?    

細かいスケジュールはまだだと思います．
去年 MoGo 組（Sylvain & Wang）は木曜の夜来て日曜に帰りました（9路は代打ち)．
こういうのもありでしょう．    

今、KGSでCrazy Stoneが走っているのですが、
どうも1dくらいで安定しそうな気配です。
KGSの1dだと日本の3段以上はありそうですから、囲碁も高段者の
世界に入ってきた、と言えると思います。
http://www.gokgs.com/gameArchives.jsp?user=CrazyStone

下の1dの人に逆転で勝った棋譜は印象的でした。
http://files.gokgs.com/games/2008/2/19/klauknue-CrazyStone.sgf

作者のRemiさんによると8コアで動かしていて、UECに参加した時より
パラメータを調整してレーティングで100点は上がっているだろう、とのこと。

ちなみにGnuGo(Level 10)には 5000 playoutで57%勝つそうです。いやはや・・・。    

ふむー確かに強いですね。僕も大体3段くらいなので、今度暇ができたら互先で打ってみようと思います。まあ、棋譜を見る限りまだ勝てそうな気がしますが、それでも何局か打てば負けることもあるかもしれません。最近自分では囲碁を打たないので相当弱くなっている気もしますし。
ただ、高段者の世界というのはまだちょっと遠い気もします。日本の3段というのは相当甘い判定での3段だと思うので。ネット碁での5段以上を高段者とするならば、まだ先は長い気がします。    

KGS 3k の加藤です．私も一局対戦したんですが，3子で負けました．1d で安定するか
どうかは私には判断できませんが，まず確実に私より強いと思われます．
>ネット碁での5段以上を高段者とするならば
これは辛すぎでしょう．KGS 3d か 4d で十分だと思います．
ま，最近の KGS の段位はちょっと甘くなってる気もしますが．    

と、思っていたのですが、その後2kまで転落していました。
もう少し対局数をこなさいと何とも言えなさそうです。    

５月に行われる将棋大会ではオープン戦のように
ドメイン名+4081ポートで対戦するのでしょうか？
それともローカルのIPを指定するのでしょうか？
ＬＡＮの環境が知りたいです。    

会場では、有線のLANを使い、ローカルのIPを使用します。
（少なくとも、昨年の大会はそうでした。）
IPアドレスなどは、その場で割り当てられます。    

将棋ソフトのページを開設しました
http://www.geocities.jp/shogi_depot/
内容は
1. ssj(Java対局ソフト)
2. マイボナ(Bonanza用GUI)
3. プチ将棋(USI対応GUI)
4. JS将棋盤(JavaScript将棋盤)
です。 
http://www.geocities.jp/shogi_depot/
   

3D のshotestが近日中に Xbox Live Arcade で使えるようになるようです。昨日辺りからいろいろなところで英語で情報が流れていますが、以下のスクリーンショット32枚を載せたign.comのページが面白いと思います。どんな画面が用意されているか一目瞭然です。
http://xbox360.ign.com/dor/xbox360/14241424/images/shotest-shogi-20080317002226940.html    

Computer-GoのMLによると、MoGoとCatalin Taranu プロ5段が
22日と23日に9路と19路で対戦するそうです。

MoGoはINRIA(フランス国立情報学自動制御研究所)にあるスーパーコンピュータを
数百台使う！そうです。

9路が30分切れ負けで3局、19路は1局、とのことです。
対局はKGSで中継される予定です。

3/22/08 3:00 PM (GMT)（日本時間 22日(土) 24:00開始、22日深夜)
Game I (9x9) 30分切れ負け、次の対局は90分後に開始。
Game II 9x9
Game III 9x9

3/23/08 3:00 PM (GMT)（日本時間 23日(日) 24:00開始)
Exhibition game (19x19)

タラヌ　カタリン(Catalin Taranu) 5段（ルーマニア出身、日本棋院中部総本部）
http://www.nihonkiin.or.jp/player/htm/ki000347.htm
MoGo/professional challenge
http://computer-go.org/pipermail/computer-go/2008-March/014517.html
http://paris2008.jeudego.org/ (フランス語)    

１局目はMoGoが黒番で負け、２局目はMoGoが白番で勝ち！
になり１勝１敗となっています。
次は３局目です。

棋譜はこちら
http://www.gokgs.com/gameArchives.jsp?user=IaGoChall    

今棋譜を見ると、9路はMoGoの1勝2敗のようですね。9路ならプロレベルということでしょうか。
しかしさすがに19路ではまだ勝負にならないでしょうね。それでも早く棋譜がみたいですが。    

棋譜拝見しました。ｓｇｆ形式で英語のコメントがごちゃごちゃ入ってますね。

１局目　白番カタリン５段の圧勝
２局目　白番ＭｏＧｏがカタリン５段の３子を呑み込んで５目半も大差勝ち
３局目　打ちきってない？よくわかりませんでした。Ｍｙソフトの不備か？
＜注＞こみは中国ルールなので７目半のようです

２局目は白番でプロに勝利ということでビックリしました。
スーパーコンピュータの威力なのかパソコンでもこれくらい強いのか？
よくわかりませんがコンピュータ囲碁も進化してますね。

３局目はＭｙソフトの不備なのか？よくわかりませんでした。
別の市販ソフトで読み込んでみても１，２局目は読み込めるけど３局目は
蹴られてしまいました。ｋｇｓのソフトで見ないといけないのかも！？
RE[　]で結果が入ってないようですがｓｇｆのバージョンが違うのか？    

> ３局目はＭｙソフトの不備なのか？よくわかりませんでした。

彩でも41手目までしか読めないです。
3局目の42手目、白E1が中継ミス(実際はF3)で分岐棋譜になっているせいだと思います。
48手目の白E1でMoGoが投了しています。

3局目のSGFを作ってみました。

(;
GM[1]SZ[9]
PB[Mogo]
PW[Catalin Taranu]
DT[2008-03-22]
RE[W+R]
KM[7.5]TM[1800]RU[Chinese]GN[Ia-Go Challenge]
;B[ee];W[gd];B[ge];W[he];B[gf];W[fd];B[dd];W[cg];B[hf];W[dc]
;B[ce];W[cc];B[bf];W[eg];B[ec];W[ed];B[fe];W[hd];B[gb];W[fc]
;B[eb];W[fb];B[fa];W[db];B[ea];W[da];B[bd];W[gh];B[hh];W[bg]
;B[eh];W[fh];B[ga];W[hb];B[dh];W[dg];B[ag];W[ah];B[bh];W[af]
;B[ch];W[fg];B[hi];W[ae];B[cd];W[bc];B[ad];W[ei])    

>9路ならプロレベルということでしょうか。
二局目ですが，黒が捨て石にするべく？伸びた手が敗着と思われます．
これを伸びなければ（私の棋力では）黒の勝ちになりました．
ハードから考えても高々1,000コア，4コアの250倍≒2^8で8子強くなっているとすると
4コアが3段相当として高々11段ということになりましょう．
実際にはもっと弱いでしょうから，まぁプロの入り口辺りがせいぜい？
三局目の方が面白く，上辺の桂馬が良く分からない．
素直に下辺を取っていたのでは（半目？）足りなかったのでしょうか？
MoGoが黒番の序盤３手は（岡崎さんによれば）黒が勝てない形なので，
これを openning book から抜いていればもっと面白い対局になったかも知れずちょっと残念．
強い人のコメントをお待ちしております (_ _)．    

19路は9子置かせて、45分切れ負け、という条件で対戦しました。
結果は、人間のカタリン5段(プロ)が中押し勝ち。
最後、コウになって右辺の白石が生還しては勝負ありでした。

MoGoは30台以上のPCクラスタで動いていたそうです。
(1台に8コアのXeon、PCは超高速インターフェイスのInfiniBand Gen2で接続されているそうです）
単純には240個以上のcoreで動いていたことになります。

棋譜はこちらから落とせます。
http://www.gokgs.com/gameArchives.jsp?user=IaGoChall

(;GM[1]FF[4]RU[Chinese]SZ[19]HA[9]KM[0.50]TM[2700]
GN[Ia-Go Challenge]
PW[Catalin Taranu]
PB[MoGoBot]
WR[5p]DT[2008-03-23]EV[Exhibition 19-19 game]RE[W+Resign]
;B[dd];B[dj];B[dp];B[pd];B[pj];B[pp];B[jd];B[jp];B[jj];W[fc]
;B[jg];W[cf];B[gp];W[ee];B[nl];W[md];B[mg];W[qf];B[pf];W[pg]
;B[of];W[qd];B[qc];W[qe];B[gj];W[pc];B[oc];W[pb];B[od];W[qb]
;B[og];W[lq];B[mo];W[lo];B[ln];W[ko];B[jn];W[kn];B[km];W[jo]
;B[io];W[mp];B[no];W[lm];B[jm];W[mn];B[nn];W[ll];B[qq];W[jk]
;B[kk];W[kl];B[jl];W[ik];B[hl];W[ip];B[ho];W[iq];B[gg];W[ok]
;B[nk];W[oj];B[oi];W[nj];B[mj];W[ni];B[qg];W[pk];B[qk];W[mk]
;B[qj];W[om];B[nm];W[kj];B[li];W[cp];B[ki];W[do];B[cq];W[bq]
;B[bp];W[co];B[br];W[dq];B[cr];W[ep];B[np];W[lk];B[em];W[bo]
;B[ap];W[ji];B[ij];W[hj];B[ii];W[hk];B[gk];W[hi];B[ih];W[hm]
;B[jq];W[jr];B[hq];W[hr];B[fq];W[dr];B[gm];W[il];B[gn];W[cl]
;B[cm];W[dl];B[dm];W[bm];B[gi];W[gl];B[fl];W[ek];B[ir];W[is]
;B[fk];W[ej];B[ei];W[di];B[dh];W[ci];B[hh];W[ch];B[rc];W[rb]
;B[ec];W[fb];B[fd];W[ed];B[db];W[gd];B[fe];W[ef];B[hd];W[ge]
;B[ff];W[cc];B[eg];W[ce];B[gc];W[hc];B[ic];W[gb];B[hb];W[gc]
;B[jb];W[ie];B[he];W[hf];B[cb];W[bb];B[bc];W[bd];B[id];W[gf]
;B[fg];W[if];B[je];W[ha];B[ib];W[rg];B[qh];W[nb];B[ob];W[oa]
;B[eb];W[ca];B[ba];W[aa];B[ac];W[ea];B[fa];W[ga];B[cd];W[de]
;B[pa];W[qa];B[nc];W[mb];B[mc];W[lc];B[na];W[ma];B[lb];W[kb]
;B[kc];W[la];B[ld];W[nr];B[mq];W[mr];B[lp];W[kp];B[rh];W[pr]
;B[oq];W[or];B[ka];W[ja];B[ia];W[qr];B[rr];W[nq];B[ka];W[pq]
;B[rp];W[op];B[oo];W[po];B[oq];W[ds];B[kq];W[mp];B[cs];W[op]
;B[qp];W[pn];B[oq];W[ao];B[aq];W[op];B[ol];W[pl];B[oq];W[ar]
;B[as];W[op];B[qm];W[pm];B[oq];W[ql];B[rl];W[op];B[rd];W[re]
;B[oq];W[rm];B[sf];W[rk];B[qn];W[rn];B[qo];W[op];B[sl];W[oq]
;B[sk];W[nh];B[se];W[sd];B[dc];W[da];B[bl];W[bk];B[bn];W[al]
;B[ab];W[cc];B[sc];W[sb])    

Bao Yun 7dan とMoGoが9路でさらにエキシビジョンをこれからするそうです。

Bao Yunさんは中国の強いアマチュアの方のようです。
http://gobase.org/information/players/?pp=Bao%20Yun
KGSでは unknownplr というIDで打っていてKGSの中でTop3に入る！9dの方のようです。

鮮やかに白番のMoGoが半目勝ちしました。
MoGoは9路の白番では2連勝です。

(;GM[1]SZ[9]
PB[Bao Yun 7dan]
PW[MoGoBot1]
RE[W+0.5]
DT[2008-03-23]KM[7.5]TM[1800]RU[Chinese]
;B[fd];W[de];B[ff];W[eg];B[ef];W[df];B[dg];W[cg];B[dh];W[ch]
;B[eh];W[ec];B[cc];W[ed];B[be];W[bf];B[ce];W[cf];B[db];W[eb]
;B[bb];W[hd];B[ee];W[dd];B[gc];W[ge];B[fe];W[gg];B[fg];W[gh]
;B[fh];W[gb];B[hb];W[da];B[ca];W[ea];B[ga];W[dc];B[cb];W[ac]
;B[bd];W[ab];B[aa];W[bh];B[hh];W[gf];B[gi];W[hi];B[ii];W[ae]
;B[bc];W[ba];B[fb];W[ad];B[fc];W[ci];B[di];W[cd];B[fa];W[ih]
;B[ig];W[ic];B[hg];W[ca];B[tt];W[tt])    

山下さん、修正譜ありがとうございました。

結局、１・３局はカタリン５段の楽勝譜だったようですね。
２局目はカタリン５段に油断があったのかもしれません。

しかし、７ｄの人にも白番半目勝ちの譜面を見ると左上の
黒大石をしとめてしまうなど鮮やかな打ちっぷりであり、
９路では相当な実力であることは間違いないのでしょう。

それに比べて１９路ではまだまだ力が不十分ですね。
まだ１９路は背伸びし過ぎと思うので、将棋と探索空間が
同じくらいの１３路盤でやって欲しいような気がしました。    

　来る4月6日（日）の午後に、コンピュータ将棋オープン戦を開催いたします。
　参加希望の方は電子メールで　applyxcomputer-shogi.org （担当：香山 健太郎）まで
参加希望の旨お送りください。
　今回も、当日の飛び入り参加・途中までの参加も受け付けます
（各試合の15分前までにお申し込みください）。

※指し手を決定するのは人間でも構いません。その場合はインタフェースとして
　 http://www.junichi-takada.jp/sficp/ のJava Applet などをご利用ください。

※自作のプログラムであれば、同時に複数のバージョンを参加させても構いません。

※当日は中継のテストも行います。参加されない方もぜひご観戦ください。

　今年の選手権参加予定で、CSAサーバを使った対局経験のない方は
このオープン戦や前日夜の通信テスト時間をご活用ください。

　なお、大会の詳細は下のURIをご覧ください。 
http://www.computer-shogi.org/open/open9.html
   

先ほど終了した April 2008 KGS bot tournament の13路で AyaMC2 が優勝しました．おめでとうございます．
なお，9路の勝者は KGS 初登場，Computer Olypiad Amsterdam の 9路の金メダリスト， Steenvreter でした．
http://www.gokgs.com/tournList.jsp    

ありがとうございます。
あのstyていうのはSteenVreterだったんですか。
最近9路では強いのがたくさん出てくるのでその一つかと思っていました。

13路は8CPUで動かしてたのですが、ハッシュをロックするところで丸ごと
ロックするのをやめてエントリー1個ずつでロックするようにしたら、
4スレッド以上だと少し効率が上がったようです。

RemiさんがMLで話していたLocklessハッシュは少し調べたのですが
なんだか面倒そうだったので実装してません。

[computer-go] Lockless hash table and other parallel search ideas
http://www.mail-archive.com/computer-goxcomputer-go.org/msg07611.html

Binary Hackに書いてる中村実さんの話 cmpxchg、などのLock命令はやはり遅い。
出来るかぎりsfenceなどのメモリバリアで済ますべし
http://www.nminoru.jp/~nminoru/data/b2con2006_nminoru.ppt

関係ないんですがBinary Hackの表紙は囲碁なんですよね。
思わず衝動買いしたんですが中身はかなり難解でした。

Binary Hacks ―ハッカー秘伝のテクニック100選
http://www.amazon.co.jp/dp/4873112885    

>あのstyていうのはSteenVreterだったんですか
ふむ，老眼が進行してるようで (失礼!)，styではなくstvです．
作者のErik君，去年のタイトルを守るために北京に行きたいと言ってましたが．．．
>4スレッド以上だと少し効率が上がったようです
私がGPWで発表した，UCTパートを独立させる方式ならロックは要りませんから，並列度が高い時はお奨め（読み違えてたらご免なさい)．
>cmpxchg、などのLock命令はやはり遅い
ですね．Lockless〜はシステム空間に切り替えるオーバヘッドを無くすだけ（バカにはなりませんが)．共有メモリ限定だし．
>Binary Hackの表紙は囲碁
この局面はどちらが優勢かという質問がどこぞに投稿されてた様で（笑．山下さんの見立ては如何？
>中身はかなり難解でした
立ち読みしただけですが，ハードウェアにかなり詳しくないとキツイ？    

あ，そうそう．
>最近9路では強いのがたくさん出てくるので
CGOSのTroisgro辺りですね．あれは誰のなのかな？　明らかにMoGoより強いし，
中手等もちゃんと処理してるみたいだし．フランス名だからフランス人？
何にせよいよいよ戦国時代突入かも．    

> ふむ，老眼が進行してるようで (失礼!)，styではなくstvです．

でした。なんか変な名前だな、と思ってました・・・。

> UCTパートを独立させる方式ならロックは要りませんから

ご指摘の通り探索木を共有させてる方式です。
加藤さんのクライアント・サーバ型の方が8coreでは効率がよさそうですね。
ただ、UCTも書き込みと読み込みだと読み込む回数の方が
かなり多いので、Lockの回数を減らしたRemiの方法もかなり優秀だと思います。

> この局面はどちらが優勢か

誰かプロの棋譜の一部ではないんでしょうか？形勢はさっぱり分かりません。    

山下さん、優勝おめでとうございます。

『Binary Hacks』の表紙の局面全面は、手元にある古碁や日中台韓のプロ棋戦、
KGSなどでのアマ高段者の棋譜(計約11万局)にはマッチしませんでした。

見つけた中で一番広い領域で石形がマッチしたのは、表紙局面左上隅の8x8で、
第13期竜星戦本戦Eブロックの青木喜久代-高尾紳路戦でした。

切り貼りっぽくないので、表紙用にどなたかが打った局なのかも。
# 次は白番ですね。    

安原さん、ありがとうございます。

＞ 表紙局面左上隅の8x8で

これだけの範囲で一致する、ということは多分アマの高段者の方が打たれた
棋譜なんでしょうね。    

並列探索よりも、指し手、局面更新、探索を分類して直列読みした方が効率が良いと思います
例えば、ある局面に到達したときに、既に指し手が生成されていて、次の局面へ進めたときには
盤面の更新が済んでいるという様にします
探索法はもともと探索数を減らす為なのに、ルートで並列読みすると効率が悪いと思います    

指し手についてですが、人間が生成方法を分類するより、機械に生成を任せた方が強い気がします
攻める手(あたりを掛けて駒を取る手など)は、同一駒を先手・先手と動かせば生成出来ますし
守る手(かわす手、合駒する手など)は、先手・後手と動かせば生成出来ます
あと1CPUと同じ探索方法で、2CPUの並列読みをすると、速度は2倍速以下と思いますが
読もうとする局面の、指し手生成と局面更新が既に済んでいるとすれば、2倍速以上出る気がします
同じようなプログラム、考えの方はいますか?

上のようにすると、指し手を選ぶには最低でも2手先を読まないと駄目ですが
手を進めた瞬間に局面更新が済んでいるようにするには、3手先までの局面を
求めておかなければならずCPUを増やしたとしても処理が追いつきそうに無いですね
常に先読みが出来ていれば速度は∞ともいえると思うのですが…
進みそうな所から局面展開すれば良いかもしれないですが…

あと評価値についてですが、1位の手と次の手の得点が僅差ならば、
相手番に必然手が無いような局面へ誘導したほうが良いと思います
必然手がない局面ならば相手に思考時間をつかわせることができて
後手の必然手と思った手に上手い切り返しがあって読みが外れた場合に不利になりにくいためです    

既製のコンピュータ将棋を使ってYahooで打ってみたのですが、
レイティング2000位でも五分五分の勝率と思いますが、
ときどき圧倒的に強い人がいて、いくら思考しても追いつきそうに無いです
相手もコンピュータでより高スペックなのかもしれませんが、
まだアマトップを超えてはいないんでしょうか?    

ネット対局で相手に断り無くソフトを使うのは迷惑だから やめなさい    

囲碁のモンテカルロ法ですが、19*19の配置を、7*7や、9*9や、11*11などで近似して、
およその打ち手を決定してから、その周囲を詳細に調べると良いと思います
囲い方は、大きいマスでも小さいマスでもほぼ同じになると思うからです
以前にも似た書き込みした気がします…    

19x19を9x9で近似するということは大雑把に言えば2x2を1で近似することになります．
どう近似すれば良いか，またそうするとどうなるかは，当然検討されたものと思いますので，
その辺りを具体的に書いて頂ければ建設的な議論ができるのではないかと思いますが．    

画像をリサイズするのと同じようにしたいのですが…
あまりに小さくすれば例えば日本地図も地球も一点になってしまいます
コンピュータで計算可能で、(19*19の) 概形が保てるサイズが良いのですが…
5*5 =　25マスには入れられないと思います　最低でも9*9は無いと駄目と思います    

その様な抽象的な話はここでは無用，具体的にお願いします．
例えば，白石4個のパターンをw4，白石3個黒石1個はw3b1（もちろん実際には個数だけでは分類として不十分）として，それらにどういう演算/処理を行い，それで何が求まると考えているのか，「具体的に」書いて下さい．
でないと建設的な議論にならないので．    

2色のビットマップでサイズ19*19のやつを11*11　(や9*9)　に変換するって事です
元の情報を減らす為、リサイズは一意的に決まりません
不可逆な音楽フォーマットが沢山あるのと同じです
サイズが大きいほど大きな囲いを目指して打つのが困難になると思いますが
小さいマスで作戦を立てておけばやりやすいって事です
通じませんか?    

>元の情報を減らす為、
ポイントはここです．誰でも思いつくアイデアにも関わらず誰もやってない理由はここにあります．
勢力の様な比較的シンプルなものでも，その形が（例えば）団子かポン抜き（四つ目）かで評価は大きく変わります（変えなければなりません)．
この辺りをちゃんと処理できる圧縮方法でなければ役に立たたないのです．
何か上手い方法を思いついたらまた書き込んで下さい (_ _)．    

指し手は、2回動かして評価値順に並べるのはコストがかかりすぎでした
受ける手を生成するのは難易度高いので、初手と後手の手を全幅にしようと思いました
初手、2手目と無意味な指し手をして、3手目でコストのかかる生成をやると非常にまずいです
あと良くなることは直ぐには判らない手ってどうやって生成したら良いんですか?
たとえば雀指しで、駒交換まで手数がかかるけどゆくゆくは好手になるような場合です
一筋だけではなくほかの筋でも似たような展開の場合には定跡使えません    

モンテカルロ法は、評価値を勝率、指し手の深さ(確率)を試行回数に置き換えただけで
通常の探索の特別なケースとして扱うことが出来ると思います。
勝率計算は時間食う為、終盤(末端など)では、評価関数=勝率だけではなく、
評価関数=(勝率+)静的評価にするといいと思います。
α-β法、MTD法の特別なケースとみなせば、将棋やオセロで使われていた
テクニックをそのまま流用できると思います。
9路や11路で最善手の列を求めておけば、19路で試行するときにその求めておいた周囲に
着手するようにすれば無駄が減らせると思います。    

>評価関数=(勝率+)静的評価にするといいと
囲碁ソフトが長い間停滞していた大きな理由が，良い静的評価関数が作れないからだと言うことをご存じないのでしょうか？　それを（ある程度）克服したのがモンテカルロ法なのです．
>9路や11路で最善手の列を求めて
最善手の列をどうやって求めるか，その方法は考えていらっしゃいますか？　まだ7路さえ解けていませんが．
>無駄が減らせると
残念ですが9路と19路は，ルールは同じでも非常に異なるゲームであると高段の方はおっしゃってます．

いい加減思いつきを投稿する段階は卒業して，実際にプログラムをお作りになったら如何ですか？　そうすればもっと建設的な投稿ができ，皆の役にも立つと思いますが．    

開発する気はあります。近いうちに将棋を完成させる気です。
実現確率が低い末端で試行するのは効率が良くないと思います。
圧倒的な勝ちが決定している末端局面を正しく判定できればそれを返す方が時間は掛からないですし、
もし間違っていたとしても元々おこる確率が低いので、なるべく正確ならそれで良いと思います。
そうしてルートに近いほどランダム試行をして、末端は静的評価という考えになります。

たとえば、各局面で20手に絞れて、初めの試行回数を1000回とします。
均等に試行回数を50回ずつに分配して、試行回数が1回を切った所で
静的関数を用いて上位局面の勝率を計算します。
こんどは、試行回数を1500回などにして、勝率に応じて試行回数を分配します。
前回の試行回数を記録しておき、既に十分な試行が済んでいる所へは進めないようにします。

と書いてみて、これだとランダムな部分が全くないことに気づきました。
通常のMax,Min値を返す所を平均値を返すように変更したようなものです。

あと初手さえある程度いい手が選択できていれば、2手以降の探索がどんなに変だったとしても
問題はないとおもうのでミニチュア版での実験には意味があると思っています。    

MC法の将棋はまだやってる人も少ないようなので期待しています．    

日本に帰ってきました。
プログラムの方は、全然強くならないと言うか、逆に弱くなったかも。
ただ、ねばりだけは出てきています。
ただ、対コンピュータ将棋には調子が悪く、持っていったSPEAR,Bonanza,K-Shogiには全敗モードです。    

去年の選手権で、ちらっとデモをやっていた
Shotestのリアルな3D将棋版のソフトが5月16日に発売されるとのことです。
私が知ってる限りでは、今までで一番きれいな3D将棋だと思います。

3D将棋
http://www.unbalance.co.jp/honkaku/shogi3d/    

いよいよですね
皆さんがんばってください    

順位予想して下さい。    

おはようございます。

最近の傾向としては、順位は毎年同じような順位になる。
これは、各プログラム、同じソースに多少の修正を加え対局してる為で同じような結果になりやすい。
極端に強いソフトがあらわれば別だが、おそらく去年と同じような結果になると予想するのが妥当だろう。
上位は、あまり差がないのでこの中から優勝ソフトがあらわれるけど、どれがになると確率はほぼ同じくらい。
北朝鮮が出てないのは、残念。    

こんばんは。
各チームのPCのスペックを知りたいんですが、どこかに一覧のような者ってありますでしょうか？    

CSAのページに一覧が公開されています。
ただ、アクセスが多いのか、少し繋がりににくいです。
http://www.computer-shogi.org/wcsc18/team.html    

初の決勝進出を果たした奈良さんの奈良将棋ですが
二次予選の大槻将棋戦では大槻将棋が頓死筋を見落として勝つ、という将棋がありました。

下の局面で大槻将棋は▲53香と打ったのですが△同金▲同角成の局面には
△６七銀▲８八玉△７九銀▲同　玉△７八金▲同　飛△４六角、
以下の35手詰があります。
△78金と放り込んでからの△46角が限定打のようで相当難解です。

実戦は頓死に気づいた大槻将棋が▲53同角成の代わりに▲42金と王手をして
負けたのですが、YSSにも解かせてみたら▲53香と打って負けてしまいました。
詰は東大8のdfpnで9万ノード、YSSのpnも10万ノードかかるもので、
内部で読ませるには手ごわいです。

▲64桂や▲72香と打てば勝ちだったようです。

後手：奈良将棋
後手の持駒：角　金　銀二　歩五
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香 ・ ・ ・v玉 ・ 角v桂 ・|一
| ・v飛 ・ ・ ・ ・ ・ 銀 杏|二
| ・ ・v桂 と ・v金 ・ ・ ・|三
| ・ ・v歩 ・v歩 ・v銀v歩 ・|四
|v歩v歩 ・ ・ ・ 歩v歩 ・ ・|五
| ・ ・ 歩v歩 歩 ・ ・ ・ ・|六
| 歩 歩 ・ ・ ・ ・ ・ ・ ・|七
| ・ ・ 玉 ・ ・ ・ ・ 飛 ・|八
| 香 桂 ・ ・ ・ 金 ・ ・ ・|九
+---------------------------+
先手：大槻将棋
先手の持駒：金　桂　香
手数＝92  △４三金  まで
http://homepage.mac.com/junichi_takada/wcsc18/kifu/WCSC18_U3_OTK_NAR.html    

さすがに各チームものすごいPCで参加されていますね。
未定となっていますがおそらく棚瀬将棋とYSSも同じレベルのなんでしょう。

シード組が昼の時点で無敗。
午後のぶつかり合いが楽しみです。皆さんがんばってください！    

努力が報われましたね。
コンピュータ世界一は疑うことなく棚瀬将棋です。
来年は朝起きたときに汗だくにはならないのではないでしょうか。
早く商品化してください。    

歴史的瞬間を生で見れた　感謝！
一寸寂しいけど    

選手権参加、運営の皆さん、お疲れ様でした。

山下さん＞
下記局面、取り上げていただいてありがとうございます。

もし（53香、同金、）同角成、と進んだとしたら私の負けだったようです。
というのも私の詰将棋ルーチン(pn)では６０万ノード必要であり、
ルートでは３０万ノードしか呼び出していないからです。
また、通常探索させると、王手ラッシュが６７歩成から始まります。

後手としては、頓死に気づいてしまっても予定変更せず、
５３角成と指すべきなんでしょうね。（４２金は負けと分かっているはずなので）。

また先手も６７歩成が負けと分かったなら、
詰将棋をノード数上限無しに呼び出したほうが
良いのかもしれません（６７歩成は負けと分かった後は）。
人間の対局だと、普通そうします。

この大槻戦と、最終戦の習甦戦を（ほとんど不戦勝のように）勝てたのはラッキーでした。
習甦さんには来年は確実に負かされそうです。    

実現確率悶値のMTD法が良いと思うのですが・・・
飛車取りなどの確率をほぼ1にすることで静止探索をなくせてかつ重要な手順は深く読める為です。
実現確率のMTD法のアルゴリズムは次の様で良いのでしょうか?
全部を完成しないと動くかどうかわからないので質問しました。

f 目標値、r　探索する確率、　-1 <= α、β<= 1

MTD ( f, r ) {
if(　rがほとんど0　)　{α、βに評価値を入れる　return (α、β)}
g = -f

for(λ全ての次局面) {
(α、β)=MTD ( g, r * λの確率)
if(  β< g ) return (-β, 1) }

if (少なくとも一つのβλが1ではない) return ( -min(βλ), 1)
else return (-1, min(αλ))
}

残り確率に応じて指し手を制限する部分や、
探索での得点に応じて実現確率を変更していく部分をうまくやれば
詰め将棋なしでもなかなかいくはずとおもっています。

あと質問なんですが、探索で再帰を使っている人はいるんですか?
再帰は、どのデータをコンピュータが管理しているのかはっきりしないし、
一般的に深く再帰すると不安定になり、速度もでないですよね?    

皆様お疲れ様でした。特に運営の方々には感謝感謝です。
年々進歩する中継手法は、私の周りでも大好評だったようです。

掲題の件ですが、
ご指摘の通り、大槻将棋の評価は
93手目▲53香の局面では、2283点
しかし、94手目▽53金とされた時点で、頓死筋に気付き(約27万ノード)、以下
95手目▲42金の局面で-613点、97手目▲53桂の局面で-3989点と急転直下していきます。
しかし、「▲42金では負け」(この手ではジリ貧)と判断するのは私のソフトでは難しく、実装は難しいように思います。

強い方のお話だと、▲53香は駒を渡すので怖いので、人間なら▲64桂から入るのが普通とのことでした。実際香を渡さなければ詰まないようです。
どちらでも勝ちの場合に、できるだけリスクの低い手を選ぶ、という方針ならば実装可能かもしれません。    

2回目以降の探索の確率は、どうやって決めますか?
１回目の探索で、たとえば、王手やそれをかわす手、飛車取りやそれをかわす手などは
高い確率にするのは当然と思いますが、2回目は得点に応じて確率を割り振りますか?
しかし、得点比率で割り振ると飛車が逃げる手が10通りあってどれもがほぼ同点だと
重要な手なのに、割り振る値は小さくなってしまいます。
かわす場合は特別で、一手であるかの様に扱うとかわしてすぐに取られてしまう手にも
高確率を与えてしまう事になります。
あと初期の確率は、完全に無視して、得点だけにするかどうかもはっきりしません。

かわす手はその時点で、一番高い一手のみを採用して、あとは無いものとして扱って
確率を分配すれば良さそうですね。その手を使って不利にならなければそのままで良いし
無視したほかの手より得点が下がればそちらを採用すればいいので。    

>どうやって決めますか?
MC将棋はまだやってる人も少なく，囲碁の様な二強もおらず，確立された手法は未だありません．つまり教わる相手はいないのです．
今必要なのは，自分の頭で色々な手法を考えて実験し，その結果を報告・比較・検討するという地道な作業です．これができない，あるいはしたくないなら新しい手法に挑戦してはいけません．＃実はこの段階が一番面白いので，できるだけ多くの人に挑戦して貰いたいのですが．    

大会に参加している人は C/C++ が多いですね。
みんな Intel C + VTune で作成しているのでしょうか？
VS2005/VS2008 とは大分違いそうですよね!?    

Intel Cを使ってる人はあまり聞かないです。
VSかgccが多いと思います。    

2008年6月21日(土),22日(日)にCGF特別例会（コンピュータ囲碁大会）が開催されます。
CGFの会員以外の方も参加できます。

9路盤（中国ルール）、19路盤（日本ルール）
の2つが開催されます。
詳しくは下記をご覧ください。

CGF特別例会のページ
http://hp.vector.co.jp/authors/VA012620/    

皆さんお久しぶりです。大変お世話になった荒木です。
CGF特別例会の情報ありがとうございます。>山下さん
ぜひ参加したいのですが、間に合うかどうか…。正直、仕事(まだ研修)が始まってから開発が進んでいません。現在高速化のため、全部書き直している最中なのですが…。    

ありがとうございます。

私の作成している解析ソフトでは Intel C に変えただけで　３割早くなったりしたもので；    

荒木さん、
間に合えばぜひ参加をお願いします。
9路は今回は結構厳しい対戦になりそうな気がしてます。    

             激指 棚瀬 Bona YSS  備後 大槻 奈良 柿木  勝敗引  SB MD DH 順位

激指            ○   ×   ○   ○   ○   ○   ○    6-1-0  18        1
棚瀬将棋   ×        ○   ○   ○   ○   ○   ○    6-1-0  16        2
Bonanza    ○   ×        ○   ×   ×   ○   ○    4-3-0  11        3
YSS        ×   ×   ×        ○   ○   ○   ○    4-3-0   8  4  1  4
備後将棋   ×   ×   ○   ×        ○   ○   ○    4-3-0   8  4     5
大槻将棋   ×   ×   ○   ×   ×        ○   ○    3-4-0            6
奈良将棋   ×   ×   ×   ×   ×   ×        ○    1-6-0            7
柿木将棋   ×   ×   ×   ×   ×   ×   ×         0-7-0            8


順位順の星取表を作ってみました。
激指、棚瀬将棋が少し抜けていて3位から6位までは僅差、という感じです。
棚瀬さんは2年連続の6-1での準優勝、とかなり不運な結果でした。

5位までは去年と同じメンツです。
備後さんとYSSはSB(負かした相手の勝数),MD(SBの最大、最小を除く)まで
一緒で、DH(直接対決)で決まっていたんですね。

と、今、規約を見直したら

> 五 第一号から第四号までで同順位の者同士の対戦のみについて、DB(勝ち数-負け数)の多い者を上位とする。

少し変わっていたようです。    

中村さん，

> 解析ソフト

Intel Compilers は浮動小数点演算や mmx, see 等を使用する
ベクトル化が得意な印象があります．また，blas や fft を含む
Intel Math Kernel Library も優秀です．科学計算は Intel
Compilers が gcc や Microsoft C/C++ Compiler より良いよう
です．Linux では無料で使えるのも魅力です．

しかし，将棋では Microsoft C/C++ Compiler がよいようです．
Windows で無料で使えます．(笑)


山下さん，

Bonanza が Yss にコンピュータ将棋選手権で「初めて」勝ちました！
フフフフフ．．．    

bonanzaと対戦していて次のような局面になりました。
先手玉は受け無しなのにbonanzaの評価はなぜか先手優勢になっていました。
しかも29歩とか49歩とか意味のない受けの手を読んでいます。
これは地平線効果なのだと思いますが、他のソフトでも
先手優勢になるのでしょか。
後手勝勢になるソフトがありましたら教えていただきたいです。


後手：私
後手の持駒：金　香　歩
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香v桂 銀 ・ ・ ・ ・ ・ 龍|一
|v玉 ・v銀v金 ・ ・ ・ ・ ・|二
| ・v歩 ・v金 ・ ・ ・ ・v歩|三
|v歩 ・ ・v歩v歩 ・ 馬 ・ ・|四
| ・ ・ 歩 ・ ・ ・ ・v歩 ・|五
|v桂 ・ ・ ・ 歩 銀 歩 ・ ・|六
| ・ 歩 香 歩 銀 ・ 金 ・ 歩|七
| 玉 ・ ・ ・ ・ ・ ・ ・ ・|八
| ・ ・ ・ ・ ・ ・ ・ ・v龍|九
+---------------------------+
先手：bonanza
先手の持駒：角　桂二　香　歩五
手数＝92  ▽９六桂  まで    

我らのAI将棋の検討の読みをご参考に。(数秒の読みで終了まで検討はさせていません。)
なお、私はAI将棋の回し者ではありませんので、ご了承の程を……(^^;

最善手 後手勝ち -24999 ▲８二銀成 △同玉
次善手? 後手勝ち -25000 ▲８八角 負け △同桂成
3番目? 後手勝ち -25000 ▲１二龍 負け △７九龍▲８九香△７八龍▲９七玉
4番目? 後手勝ち -25000 ▲８五桂 負け △２八龍▲４八歩△８八金▲９七玉△８四歩
5番目? 後手勝ち -25000 ▲７四歩 負け △７九龍▲９七玉△９五金▲６六銀
6番目? 後手勝ち -25000 ▲４四馬 負け △５三金上▲３三馬△パス▲パス△８八金
7番目? 後手勝ち -25000 ▲２二龍 負け △７九龍▲８九香△７八龍▲９七玉
8番目? 後手勝ち -25000 ▲４七金 負け △７九龍▲９七玉△９五金▲６六銀
9番目? 後手勝ち -25000 ▲６八銀 負け △２八龍▲６九香△８八金▲９七玉△９五歩
10番目? 後手勝ち -25000 ▲７四桂 負け △２八龍▲４八歩△８八金▲９七玉△６一金    

今回の大槻将棋では、Intel Compiler のiccを使いました。
大会マシンの計測では、並列化なしの場合gcc-3.4より12%程度高速に探索できるようです。
(gcc-4.2はgcc-3.4より多少早いもののiccには及ばないようです)さらにiccのプロファイラ結果を用いる最適化オプション(-prof_gen と-prof_use)を使うと、gcc-3.4より18%程度早くなるという結果が得られましたが、並列化した場合にはなぜかうまく動きませんでした。Windowsでのコンパイルは実行したことがないので、iccとどちらが早いのかは分かりません。    

皆さん、選手権お疲れ様でした。
激指、優勝おめでとうございます。
圧倒的な強さを見せていただきました。 実はこの冒頭は私の2005年 5月11日文の引用になります。(歴史は繰り返す?)(^^;

今年は特にコンピュータ将棋界にとって、将棋ソフトファンにとっても、衝撃の年に成ったのではないでしょうか……。

私は、今年 1月 6日に、過去(6年前)の2002年 8月 3日に、ここの掲示板に書き込んだ「将棋プログラム強化法　（100倍強くなる法 ) 」文を引用し、
「2008年はコンピュータ将棋のターニングポイントの年であります! (私がかってに決めた　(^^; 」と再度、書き込みをしました。
ターニングポイント［turning point］とは、転換点，転換期，転機，変わりめの意味です。
しかし、この時点で、これが何を意味し、何を指すのか、はまだ誰にも知られてはいませんでした。神と私以外は……。（ほんまかいなー)　(^^A

そしてこれは、選手権後の名物であるエキジビションでの激指と棚瀬将棋によるトップアマ高段者に連勝によって的中したものと勝手に自負しています。(そーなるんかなー)(^^;
また、好き勝手な予想として、今年の選手権において優勝するプログラムは、コンピュータ将棋界に新たな、転換点，転換期，転機をもたらすだろうと断言し、
その快進撃するプログラムが、learning programである事も予想し、それを見事に的中させました。（すごいなぁー私ってー)　(^^;
つまり、言うなれば2002年からここの掲示板で発せられた私の「tの妄想」とは、2008年のこのターニングポイントの実現への到達点をしっかりと幻視し、
それを予言した壮大な妄想計図だったのである。（ほんまかいなー)　(^^A

私は、過去の2005年 5月11日にここの掲示板で選手権において全勝優勝した激指を私の妄想する「Aルーチン・プログラム」に特別認定しました。
そして、その数ヶ月後、激指はアマ竜王戦ベスト１６の快挙を成し遂げました。

今回、更なる強化と更なる期待を込め、トップアマ高段者に連勝した、 激指と棚瀬将棋、両者の実績を独断と偏見で評価し、
私の妄想する「Bルーチン・プログラム」に特別認定させていただきます。
(Bルーチンの強さは女流棋士に楽勝! あまりの強さに泣き出す者、おもらしする女流棋士が出るでしょう?  と過去に私が予測した)
ちなみに「Bルーチン」特別認定は、将棋ソフト初です。(なんの、こっちゃー)(^^A
もちろん、景品は、前回同様になんも出ません(セコイかいなー）が、その礼にも及びません。(なんぢゃ、そりゃー)(^^A

実際、私がここ数年前に高く評価したプログラムがいまだ選手権上位に君臨し、コンピュータ将棋史に残る快挙を成し遂げるのをとても嬉しく思っています。

コンピュータ将棋の実力は、プロに対座する権利を得ました。その認識はすでに私だけの妄想では無いでしょう。
最後に、Bonanzaと対局した事もある渡辺竜王の識文を勝手に引用して置きます。

http://blog.goo.ne.jp/kishi-akira/
>アマトップの方々は奨励会で言えばプロ手前の二段〜三段の力はあるので、そこに２連勝というのは衝撃的。
>まぐれということもあるのでなんとも言えませんが、来年も同じような結果になれば、次はプロが出て行くしかありません。
>僕が再び戦う日も遠くないかも(笑)って笑い事じゃないです。


プロ棋士も対局を拒否するかも?　と言われ恐れられる、Cルーチンの実現に期待しています。
---------------------------------------------------------------------------------------------------- ------------
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Cルーチンの実現を夢見て記す　 tss    

Bonanza は、Intel C を使っていると聞いたことがあるんですが、違ってたんですね。

昨年12月に、５五将棋で VS2005 と Intel C の速度を比較し、ＣＳＡ例会で発表しました。
また、１年〜２年前くらい（？）にこの掲示板でも比較結果を書いたはずです。

５五将棋　初形で11手探索

Core2 Extreme QX6700 2.8GHz(Over Clock)
Windows 32bit

VS2005      2280 ms
VS2005 PGO  1873 ms
Intel C     2132 ms
Intel C PGO 1831 ms

*PGO: Profile-Guided Optimization

Intel Cの方が少し速い結果でした。
それより、PGOの効果が大きいです。    

> Bonanza は、Intel C を使っている

Linux で走らせる場合は Intel C，Windows で走らせる場合は Microsoft C です．

Boanza の場合，前に Intel Core 上で Windows 32bit 版の Intel C Compiler 10.1 と Microsoft C/C++ Compiler 15.00 で比較したのですが MS C の方が速かったです．

PGO の有効性は Bonanza のバージョンによって異なりました．更に，64 ビット版 OS では x64 実行形式にするか 32bit 実行形式にするかでも速度が違うようです．．．

いろいろな組み合わせがある上に，結果がバージョンに依存するので，どれがベストなのかよく分かりません．    

Grimbergen さんが今年も選手権のレポートを書いています。 
http://gamelab.yz.yamagata-u.ac.jp/SHOGI/CSA2008/18csa.html
   

今日の毎日新聞の夕刊に、興味深い記事がありました。
選手権の会場にいた中川七段が４日後の公式戦で
棚瀬将棋-加藤戦と同形（棚瀬将棋側）を採用し勝った話が載っています。 
http://gamelab.yz.yamagata-u.ac.jp/SHOGI/CSA2008/18csa.html
   

できれば、元記事を読みたい･･･    

小宮さんが元記事を掲載してくださいました。
http://d.hatena.ne.jp/mkomiya/20080523    

すごい記事ですね。
とうとうコンピュータが定跡を作った？初の出来事でしょうか。    

あの戦型は、プロの対局で見た記憶があって、棚瀬君のプログラムにプロの定跡がある程度入っていると思う。
ただ、全く同一かどうかはわからない。（特に玉の位置）
北島君がコンピュータ将棋かつ持ち時間が短い等の理由で局面を軽視していたのだろう。
中川君は居飛車等であの種の戦型は好んで指す傾向があるので、興味があって過去のプロの棋譜等を調べてみたのだろう。
ただ、一度使った新手というのは、プロは研究してくるのでこの変化がプロの実戦で現れるのは極めて少なくなるだろう。
コンピュータ将棋と人間については、もう少し持ち時間を増やして対局すべきと思う。
また、アマ側もコンピュータの弱点を突くべきで早い段階で定跡を外し、駒組みの構想力のない弱点を突くのをお奨めする。    

2chの「激指総合スレッド」を読んで気になったのですが、現在市販されているコンピュータ将棋ソフトは大駒の不成は全く読んでいないものが多数派だと言うのは本当でしょうか？
また、その理由は大駒不成を読む事が有効な局面が実戦ではほとんど現れないにも関わらず、探索量は結構増えるので総合的な勝率は読まない方が高くなると言う理解で正しいでしょうか？    

先ほど書き込みした事が正しいとして、大駒不成による探索に意味があるのは打ち歩詰めを回避したい状況だけだと思いますが正しいでしょうか？
もし、そうであるとすれば現局面から探索する途中で大駒が成るか成らないかを選択する局面をキャッシュ？に登録しておいて、そこからは普通に成る方のみを探索し、末端局面で打ち歩詰めが現れた場合はそのフラグを立て、先ほどキャッシュした局面まで戻ったところで改めて不成の方を探索するというのはどうでしょうか？
それでも滅多に現れない状況のために探索量が増えるので、手間の割に総合的な勝率はかえって下がるのかも知れませんが、商品版ソフトの手の自然さとか、検討モードの充実にはいくらか役立つのでは無いかと考えますが如何でしょう？    

打歩詰がある場合のみ大駒の不成を読むのは、10年以上前から多くのソフトが実施しています。
出版されたものとしては、1996年出版の「コンピュータ将棋の進歩」の中で、既に使われている方法として紹介されています。    

基本的な質問ですみません。

「詰将棋カレンダー２００９」に応募しようとしています。
柿木９の発売はいつごろになりますか。
柿木８の発売より３年経過しているのでソフトも進歩したと思います。
柿木８だけ更新しない。

すでに柿木５は持っております。
したがって、「余詰」の検査は不完全ですができます。    

ここは特定ソフトの発売時期を質問する掲示板ではありません。    

参考までに実戦で生じた大駒不成の詰将棋は、過去に一局知っていて、谷川浩司・大山康晴戦で生じている。
谷川先生が角不成で大山玉を詰めた。
なんで、角不成にしたかと言うとこれも打歩詰が関係していたと記憶してる。
局面は、忘れたが大山康晴か谷川浩司全集に大きなタイトルで紹介してあったので、全集を持っている人は見つけやすいと思う。
大山先生の棋譜は、全局並べたがこれだけだったと記憶してる。
人の一生で１回生じるかどうかだし、このあとも生じた記事を見た事ないので、極めてまれな実戦詰将棋と言える。    

ひさしぶりにSPEARの部屋をのぞいてみたら、デザインが変わっていて、New VersionのSPEARがリリースされています。(゜o゜)
しかも、日付は今日になってました。
ダウンロードは、まだしてません。    

攻方が打ち歩詰を回避するための大駒不成だけでなく
玉方が打ち歩詰に誘致するための大駒不成も実戦例があります。
成ってしまうと歩が取れるので打ち歩詰に成らないが、不成なら打ち歩詰に成るというものです。
将棋世界毎年6月号の勝又プロ編の妙手珍手集の付録の何年か前の号に載っていました。    

荒木です。
Remi CoulomさんがComputer OlympiadのReminderをcomputer-goのメーリングリストに流していました。というわけでここでもReminderとして書き込みます。
ところで、Computer Olympiadのページを見たのですが、細かい日程(囲碁の大会が9/28-10/5のいつ行われるか等)はまだ公開されていないのでしょうか?見つからなくて…。    

>細かい日程はまだ公開されていないのでしょうか?
Remi に訊くのが一番確実ですが，early registration が終わらないうちは
おおよその参加人数も決まらないので，難しいのではないかと．    

なるほど、それもそうですね。
(会社勤めの身だし、今回は不参加にしておいたほうが無難かなぁ。)    

対局時間等は変わってないので，前回と同じ（9路が前半，19路が後半）だとは思いますが．
既に就職してた Sylvain 君は金曜の夜来ました（9路は代打ち)．金曜日からの人は結構いたようです．
>今回は不参加にしておいたほうが無難かなぁ。
今回は Handtalk の陳先生も参加するそうだし，25ユーロ（４千円位）だし，珍しく近場だし，とりあえず登録しとけば？    

>金曜日からの人は結構いたようです。
なるほど。
>とりあえず登録しとけば?
うーん、そうですね。(プログラムのレベルを考えると)9路のみしか参加できないかも知れないとか、代打ち頼む相手もいないとかいろいろ不安はありますが、とりあえず登録します。
さっさと開発したいのですが、技量不足と、仕事でのストレスで、なかなか進みませんね。駄目人間です。
ところで、加藤さんはCGF特別例会には参加されないんですか?    

>9路のみしか参加できないかも
私も前回は9路だけでした（後半は見物)．
>代打ち頼む相手もいない
代打ちは主催者側のスタッフに頼めるはず.
>CGF特別例会には参加されないんですか?
現在コーディングの真っ最中（爆.    

9月28日から北京で開かれるComputer Olympiadの申し込み期限は今日、6月15日までです。
（ヨーロッパ時間なので明日の朝ぐらいでも大丈夫でしょうけど）

参加費は賞金なしの割りには少し高いのですが

アマチュア 25ユーロ  4125円
セミプロ  100ユーロ 16500円
プロ      250ユーロ 41250円

プロは参加するソフトの名前で市販ソフトを出している場合で
セミプロは市販してるけど名前が違う場合、アマチュアはそれ以外です（数年前までは確か）

今日を過ぎると参加費が倍になる、とのことです。

http://www.grappa.univ-lille3.fr/icga/event_info.php?id=18    

6月21日、22日に秋葉原で開催されるCGF特別例会（コンピュータ囲碁大会）
の申し込み締め切りは明日、16日までです。

現在、9路、19路、それぞれで合計11人の参加予定者となっています。
希望される方はぜひお気軽にお申し込みください。
http://hp.vector.co.jp/authors/VA012620/    

補足しておくと，この料金は一種目分なので 9路碁と19路碁両方参加する時は 2倍になります．    

4月に引き続き今月もAyaMCが優勝しました．おめでとうございます!
http://www.gokgs.com/tournEntrants.jsp?sort=s&id=390
9路はまたまた初顔のStoneGridが優勝．Steenvreter同様，死活の処理が入ってるそうです．CGOS9x9での総合レートは2262とかなり強い．
http://www.gokgs.com/tournEntrants.jsp?sort=s&id=391
ついでに，4月のスレッドで触れたTroisgroの正体はクラスタ版MoGoでした．こちらの総合レートは2728!
http://cgos.boardspace.net/9x9/allTime.html    

盤面をハッシュを CRC の結果で持つようになるのでしょうか？
現在のソフトウェアでの計算のスピードにもよりますが・・    

2008年6月21日(土)、22日(日)にかけて東京、秋葉原でCGF特別例会が開催されました。

9路は10チームが参加して7回戦を行い彩が7戦全勝で優勝しました。
2位は同順位で5勝2敗の勝也、不動碁、GNU Goでした。

19路は8チームが参加して総当りを行い7戦全勝で彩が優勝しました。
2位は6勝1敗の勝也、3位は不動碁でした。

対局の様子がNHK-BSの囲碁将棋ジャーナル(7月5日(土))で放映される予定、とのことです。
その関係で向井芳織プロ初段もいらしていました。

彩はXeon 2.66GHz x8 コア のマシンを使い、9路では6コア、19路では8コアを
使っていました。

9路盤 15分切負 コミ7目半、中国ルール  2008/06/21 秋葉原 ダイビル13F

               彩  勝  ca  GN  く  DM  To  Bo  不  MC  勝敗 順位
彩                 ○          ○  ○  ○  ○  ○  ○  7-0   1
勝也           ×          ×  ○  ○  ○  ○  ○      5-2   2
caren                      ×  ○  XX  ×  ○      ×  2-5   8
GNU Go             ○  ○      ○  ○  ×      ×  ○  5-2   2
くろねこにゃ   ×  ×  ×  ×      ×      ○      ×  1-6   9
Drunken Master ×  ×  OO  ×  ○              ×      3-4   6
Tombo          ×  ×      ○  ○          ○  ×  ○  4-3   5
Boozer         ×  ×  ×      ×      ×      ×  ×  0-7  10
不動碁         ×  ×      ○      ○  ○  ○      ○  5-2   2
MC_ark         ×      ○  ×  ○      ×  ○  ×      3-4   6

1. 総当りの予定だったが時間切迫のため最後の7回戦のみ、成績が
   近いもの同士を対戦。そのためもあり、caren − Drunken Masterは
   白黒入れ替えて2局行っている。
2. GnuGo は3.7.12を利用。モンテカルロを利用していないもの
3. 対局は手入力

19路盤 30分切負 コミ6目半、日本ルール 2008/06/21-22 秋葉原 ダイビル13F

            彩  勝  不  ca  GO  き  ig  迷  勝敗 順位
彩              ○  ○  ○  ○  ○  ○  ○  7-0   1
勝也        ×      ○  ○  ○  ○  ○  ○  6-1   2
不動碁      ×  ×      ○  ○  ○  ○  ○  5-2   3
caren       ×  ×  ×      ×  ○  ○  ○  3-4   4
GOGATAKI    ×  ×  ×  ○      ×  ○  ○  3-4   4
きのあ囲碁  ×  ×  ×  ×  ○      ○  ○  3-4   4
igoist      ×  ×  ×  ×  ×  ×      ○  1-6   7
迷ぃ子      ×  ×  ×  ×  ×  ×  ×      0-7   8

1. GOGATAKI - きのあ囲碁はGOGATAKIの時間切れ負け
2. 対局はnngsサーバ経由

棋譜
http://hp.vector.co.jp/authors/VA012620/cgf2008/cgf2008.zip

1日目の写真
http://yssaya.web.fc2.com/photo/20080622cgf/20080621/index01.html
2日目
http://yssaya.web.fc2.com/photo/20080622cgf/20080622/index01.html
CGF特別例会のページ
http://hp.vector.co.jp/authors/VA012620/    

2008年コンピュータ将棋選手権準優勝記
http://platz.jp/~tanase/    

後手・先手・後手と指したときに同一局面になる場合ですが、
2手目の先手の手が複数ある場合は、普通に(2手目はmin、1手目は和)計算するしかないですよね?
先手の手が一手のみの場合はそれほど多くはおこらないと思います。
2手目が2手以上の場合にも拡張出来ますか?

2手目も3手目も一手のみという特殊なケースしか、纏められない気がしてます。
それを検出するコストよりも、無視してしまった方が良く速くなったりしないですか?
稀に、2倍、3倍の得点になったとしても、ルートに近い位置なら、その効果はあると思うんですけど
すべてで検出すると遅いと思います。    

あまり専門ではなく、何年か前のことなので記憶があいまいですが・・・

玉が２回続けて逃げて同一局面になった場合のみ、カウントを半分にするようにしています。そのロジック有無での結果は５パタンしかありませんが・・・

　　　　　　　　　　　　無　　　　　　有
（１）２５手詰め　　０．２３４　　０．２３４　（秒）
（２）２７手詰め　　１．９５０　　１．７９４
（３）２７手詰め　　５．１１７　　７．５５０
（４）４３手詰め　　３．７１３　　３．２６０
（５）４７手詰め　　２．５１２　　２．４９６

３問で効果があったのですが、１問で逆効果がでていました。
私の結論としては、問題によって効果が異なるが、とりあえずロジックを入れておくというものです。
詳しい方の見解をお伺いしたいところです。    

Rybka 3 は MC シミュレーションを使ってる様です．
http://www.chessbase.com/newsdetail.asp?newsid=4772    

8月7日の13:00(日本時間8月8日の05:00)からアメリカのオレゴン州で開かれる
US Go Congressのイベントで、MoGoと韓国のプロ棋士 Kim MyungWan 8段が
対戦するそうです。MoGoはオランダのアムステルダムにあるPCクラスタを
利用する予定、とのこと。
対局はKGSのコンピュータ囲碁の部屋で中継される予定、とのことです。

最初に5局の短時間の対局をして、その後、適切な置石で1局、普通の時間の対局を
行う予定、とのことです。

US Go Congress
http://www.gocongress08.org/
Kim MyungWan （韓国語）
http://www.baduk.or.kr/information/info_player_profile_7dan.asp?gno=1092&ntn=1&gdiv=2    

スウェーデンで開催中のEuropean Go Congressのイベントの一環で
コンピュータ囲碁大会も開かれています。

参加8チームで現在KGSのComputer Goの部屋で対戦されています。
3回戦まで進行中で現在CrazyStoneが3連勝。MFGのMC版やLeelaが2-1で追っています。

全員が同じコンピュータ(1.86GHz Core2Duo)を使っています。
優勝には300ユーロの賞金がでるそうです。

対戦結果
http://www.gokgs.com/tournEntrants.jsp?id=407
ヨーロッパ囲碁大会
http://www.computer-go.info/egc2008/    

韓国のプロ棋士 Kim MyungWan 8段とMoGoの対戦は
4回対局して、最後は持ち時間1時間の9子でMoGoが勝っています。
MoGoは800コアのPCクラスタで動いてたようです。

9子。                  10分切れ負け。 MoGoの負け
http://files.gokgs.com/games/2008/8/7/MyungWan-MoGoTiTan.sgf
11子（9子からパス2回)。15分切れ負け。 MoGoの負け。
http://files.gokgs.com/games/2008/8/7/MyungWan-MoGoTiTan-2.sgf
12子（9子からパス3回)。15分切れ負け。 MoGoの3目半勝ち。
http://files.gokgs.com/games/2008/8/7/MyungWan-MoGoTiTan-3.sgf
9子                    1時間切れ負け。MoGoの1目半勝ち。
http://files.gokgs.com/games/2008/8/7/MyungWan-MoGoTiTan-4.sgf

棋譜一覧
http://www.gokgs.com/gameArchives.jsp?user=MogoTitan    

囲碁女流九路棋戦「妙花」
http://www.igoamigo.com/igofes/myoka/
http://blog.goo.ne.jp/myo-ka/e/42fcd66a7579d25dd782b57af6dec06e    

皆さんお久しぶりです。荒木です。

ComputerOlympiadに向けてプログラムの高速化を行っています。その報告です。現在9路盤で1300playout/秒くらい(1コア2.4GHz)です。以前に比べると大分速くなりました(3〜4倍くらい)。
一時はC++からCに書き換えるしかないかと思いつめていたのですが、C++に詳しい友人からアドバイスをもらい、C++のままで高速化できました。
CrazyStoneよりも素性を追加しているためもあってか、一手15秒くらいにすると私(KGS2d)より強いかもしれません。
これでもComputerOlympiad9x9囲碁部門で最下位になってしまうのでしょうか。どなたか目安を教えていただけると(精神的に)うれしいです。
ただ、素性を追加しているといっても、CrazyStoneや彩を見ていると、あと3倍くらいは速く出来るのではないかと思っています。

なんにせよ、ここの掲示板の皆様には本当にお世話になりました。今までありがとうございました。これからもよろしくお願いします。    

>これでもComputerOlympiad9x9囲碁部門で最下位になってしまうのでしょうか
自分のプログラムの客観的な強さを知るには，CGOSかKGSのトーナメントに参加するのが確実だし簡単です．詳細は http://cgos.boardspace.net/ をご覧下さい．尚，トーナメントでは時間制御も重要です．
Olympiad は参加することに意義があるので，成績を気にする必要はありませんが，CGOS のレートで 1800 あれば多分，2000 あればほぼ確実に，最下位になることはないと思います．
＃参加者リストに MC じゃないプログラムもあったし，心配無用．
＃＃題名は具体的に．これじゃ情報量ゼロ．    

昼休みにemoneから書き込み。
題名についてはすいません。うっかりしていました。
CGOSも考えたのですが、今家には安定な回線が無い(emobileのみ。emobileは突然切れることがある)なのでまだやっていないのです…    

>安定な回線が無い
ならば手元で CGOS 9x9 と同じ条件（コミ7目半，5分切れ負け）で GNU Go と対戦させてレーティングを求める手もあります．GoGui+twogtp 辺りを使って．    

GNUGo3.6のLevel10相手に9路盤で勝率を計ってみました。
100局打たせて41勝59敗です。100局じゃ標準偏差が大きくて(±5%くらい)あまりはっきりしたことは言えませんが、GNUGoより少し弱いようです。これは最下位かも…。
ちなみに、時間制御を実装していないので、1手5000po固定で打たせました。大体1手4〜5秒です。
時間制御の実装+並列化を頑張ればGNUGoと同じくらいにはなるかなと思っていますが…。
ただ、北京には実験用マシンを持っていかない(レンタルor予備のノートPC)ので、レンタルマシンで動かなかったり性能がいまいちだったりした場合はノートPCで打つことになります。その場合1.83GHzのDualCoreなので速度は期待できませんね…。    

Gnuに5割くらいだとOlympiadでは厳しいかもしれませんね。
とはいっても上はプロにも勝ってしまうぐらい強いので、欲を言い出すと
きりがないのですが・・・。

私も9路は弱いので、playoutを繰り返すと少し正確に打てるようになるように
いろいろいじっています。

オープンソースでは現在9路では最強？の
カナダのアルバータ大学のFuegoのソースが公開されてるので
これを見ると少し高速化の秘密？が分かるのかもしれません。
（まだ見ていないのですが）
http://fuego.sourceforge.net/    

今月号の情報処理学会誌の「情報処理」に再度コンピュータ将棋の
特集が組まれています。

■コンピュータ将棋は止まらない（Vol.49 No.8）

0. 編集にあたって--Xデーは近い--（松原　仁）
1. 第18回世界コンピュータ将棋選手権報告（伊藤毅志）
2. 恐るべし，コンピュータ将棋（中川大輔）
3. 女流棋士として見たコンピュータ将棋（安食総子）
4. 最近のコンピュータ将棋の技術背景と激指（鶴岡慶雅）
5. 棚瀬将棋の技術背景（棚瀬　寧）


棚瀬さんの記事はかなり密度の濃い内容となっています。
・Bonanzaは、王、盤上の任意の味方の駒1、盤上の任意の味方の駒2、の3つの駒の関係を学習させている。
・連続する3手の組み合わせで延長を行い、その確率はプロの棋譜から求めている。
・1手で消費する読みの深さを0〜3に制限している。
・評価関数の特徴量は約3万
・駒をただで捨てる、などの深い読みが必要な手は学習させてない
などです。

こちらのリンクから、それぞれの記事の1ページ目だけは立ち読みできます。
http://fw8.bookpark.ne.jp/cm/ipsj/mokuji.asp?category1=Magazine&vol=49&no=8
値段もそれなりなので、情報処理学会誌を扱っている大学などの大きな図書館を
探すのがいいかもしれません。    

大学の図書のほか、情報系の職場の書庫にも情処学会誌が置かれている可能性が高いのではないかと思います。

エキシビションの棚瀬将棋の指し手を中川七段が真似た、という話は将棋ファンの間でも知られていると思いますが、当のご本人によってそのいきさつをが書かれており、将棋ファンにも読んで欲しい内容になっています。
学会誌に専門棋士お二人の原稿が掲載されること自体が異例ですね。

CSAブログでは近日中に触れる予定。    

9路でGNUより弱いのはちと苦しいかなぁ．
ソースコードなら私の (http://www.gggo.jp/) も忘れないで下さい :-)．
RAVEを実装したv2もCGF特別例会で使った例のバグ有り版で良ければいつでも公開します．    

過去ログが見れなくなっているようですが、どこに行ってしまったのでしょうか?? 
http://vivio.blog.shinobi.jp
   

私はComputerOlympiadではマシンレンタルを申し込んでいるのですが、他にもそういう方はいらっしゃいますか?
いらっしゃったら、レンタルマシンのスペックが公開されているかどうか、教えてください。
ComputerOlympiadのページにはそれらしい記述がなかったもので…。
もし公開されていないのでしたら、メールで問い合わせます。
まあしかしさすがにどの道、あのでかい自作マシンを持っていくわけには行かないでしょうけど…。    

慌てなくても決まったら主催者から連絡があると思いますよ，Internetが使えるか否かも含めて．こちらが使えればKGS経由で家のPCを使うことができます．
推測ですが，Remi辺りはMacProを持ってくるんじゃないかなぁ，もしInternetが使えなければ．
将棋ですが去年TACOSチームはサーバを別途送った様です．山下さんもこの手かな？
DualCoreのノートという手もあります．今は10万位で買えるし．清さんは1コアのノートでしょう．    

たった今連絡がありました…。どうもお騒がせしました。
DualCoreのノートは持っているんですが(CoreDuo1.83GHz)、1.83GHzといっても実際に動かしてみると遅くて…。
ちなみにレンタルマシンは以下のスペックだそうです。
Processor

Intel Pentium Dual-Core E4500(2.2GHz)/E4600(2.4GHz)/E4300(1.8GHz)

Operating System

Windows XP Simplified Chinese Service Pack 2 Edition

Memory

1GB/2GB

Display/Monitor

20" CRT

Hard Drive

160GB

Optical Device

CD/DVD ROM    

明日、慶應義塾大学 湘南藤沢キャンパスで開催される
FIT2008の企画で13:00から青葉かおり四段とCrazyStoneの
19路盤での九子局が対戦される予定です。
https://secure1.gakkai-web.net/gakkai/fit/program/html/event/event.html#6    

FIT2008の対戦は1手30秒の条件で対戦してCrazyStoneが勝ちました。
CrazyStoneは去年のUEC杯よりはかなり（2子程度は）強くなっている印象でした。

対局後、9路で王 銘エン9段がコミ0.5の白で9路で対局したのですが
これもCrazy Stoneが勝ちました。
CrazyStoneは8コアのマシンで走っていたとのことです。

(;GM[1]SZ[19]
PB[Crazy Stone]
PW[Aoba Kaori]
DT[2008-09-04]
RE[B+R]
HA[8]KM[0.5]
RU[Japanese]PC[Keio University, Shonan-Fujisawa, Kanagawa Japan]EV[FIT2008]
AB[dd][jd][pd][dj][pj][dp][jp][pp]
;W[dm];B[gk];W[gp];B[gn];W[eo];B[ep];W[fo];B[jn];W[dg];B[fg]
;W[cd];B[cc];W[de];B[ce];W[bd];B[ee];W[df];B[ec];W[bc];B[nd]
;W[qn];B[on];W[om];B[nm];W[ol];B[nl];W[ok];B[mi];W[nk];B[mk]
;W[nn];B[pn];W[mj];B[lj];W[ml];B[nj];W[mm];B[np];W[oj];B[oi]
;W[pi];B[ph];W[qi];B[qm];W[oh];B[ni];W[pg];B[qj];W[qh];B[ng]
;W[ql];B[qo];W[fd];B[fe];W[ed];B[dc];W[fc];B[hd];W[eb];B[bo]
;W[do];B[cp];W[fq];B[cl];W[dr];B[cm];W[iq];B[jq];W[jr];B[kr]
;W[ir];B[rl];W[qk];B[kl];W[ge];B[hg];W[qc];B[qd];W[pb];B[pc]
;W[rb];B[rc];W[qb];B[cr];W[lr];B[rk];W[rj];B[gf];W[nb];B[nc]
;W[mb];B[lc];W[kq];B[er];W[rn];B[rm];W[qq];B[ro];W[or];B[nr]
;W[pr];B[gd];W[gb];B[gc];W[fb];B[kp];W[lq];B[oq];W[rr];B[ch]
;W[dh];B[di];W[eh];B[bg];W[gi];B[hi];W[jm];B[km];W[hh];B[gh]
;W[hj];B[ih];W[gj];B[fi];W[fj];B[ij];W[hk];B[dl];W[ik];B[jk]
;W[jj];B[ii];W[mc];B[md];W[kc];B[ld];W[lb];B[be];W[cg];B[bh]
;W[kd];B[ke];W[jc];B[ic];W[je];B[id];W[hm];B[fk];W[in];B[jl]
;W[fm];B[im];W[hn];B[ob];W[oa];B[hl];W[ei];B[ej];W[fh];B[ib]
;W[rd];B[re];W[sc];B[kb];W[nh];B[mh];W[nf];B[og];W[qe];B[pf]
;W[qf];B[il];W[fi];B[sj];W[ri];B[ph];W[oh];B[gm])    

荒木@「MC_arkは2コアだと9路でGNUに5割ちょっとの勝率」です。
棋譜を見ましたが、確かに昨年のUEC杯のCrazyStoneよりは強そうですね。読みもしっかりしているし、着手に一貫性も見られます。
ただ気になるのが、部分的にぬるい手、損な手を結構打っていることですね。8子でモンテカルロらしく安全勝ちをしに行くとそんなものなのかもしれませんが、級位者のころに置き碁で「もっと積極的に厳しく戦わないと勝てないよ」と教わった身としては不自然に感じてしまいます。    

>部分的にぬるい手、損な手を結構打っている
あれで人間はだまされるんですよ．まるで急に別人になったかの様な打ち様ですから．
今回の碁は終始 Crazy Stone がリードしていた（と思われる）ので，
あれが実力かどうかは怪しい．もっと置き石を減らした対局が見たいものです．
そう言えば，MoGoTitan と金9段が 9/20 に Cotsen Open で再戦するそうで，
置き石を 7子に減らすとか．持ち時間も 90分を希望しているそうです．    

>金9段
8段でしたね，失礼．    

持ち時間は19路は1手30秒で9路は10分切れ負けでした。

写真です。
http://www.yss-aya.com/photo/20080904fit/index01.html

下は9路の棋譜。対局を見ながら入力したので、22手目あたりや、
左側のダメを詰める手順あたりが間違ってるかもしれません。

※やはり間違っていました。メイエン事件簿、の棋譜から作り直しました。
石塔放り込みと最後のヨセの部分の手がなかったので追加しています。

(;
GM[1]SZ[9]
PB[Crazy Stone]
PW[O Meien]
DT[2008-09-04]
RE[B+2.5]
KM[0.5]TM[600]RU[Japanese]
;B[ee];W[eg];B[ec];W[ge];B[df];W[dg];B[cg];W[cf];B[ce];W[bf]
;B[ch];W[be];B[ff];W[fg];B[gf];W[gg];B[cc];W[bd];B[hf];W[ef]
;B[de];W[fe];B[hg];W[hh];B[ih];W[he];B[gh];W[hi];B[gi];W[if]
;B[ii];W[hh];B[hi];W[ie];B[eh];W[ig];B[dh];W[hh];B[bc];W[bg]
;B[bh];W[fh];B[ah];W[fb];B[fc];W[gc];B[eb];W[ei];B[gb];W[hb]
;B[fa];W[di];B[ad];W[ci];B[ae];W[bi];B[cd];W[fd];B[af];W[ha]
;B[hc];W[gd];B[ib];W[hd];B[ga];W[ic];B[ed];W[fi];B[ag];W[ai])    

FIT2008で解説と9路で対戦してくださった王銘エン9段が
毎日コミュニケーションズの対局サイトで連載されている
「メイエン事件簿」で今回の対戦を取り上げられています。

第30話　 かんぱいモンテカルロ
http://taisen.mycom.co.jp/taisen/contents/igo/meien/meien_30.htm

毎日コミュニケーションズの対局サイト（囲碁のページにあります）
http://taisen.mycom.co.jp/taisen/    

コンピュータ将棋に関する記事や選手権の棋譜のショート解説なども載せてくれていた近代将棋誌
が本年６月号を持ち休刊ということで大変残念に思ってましたがそれに関する記事が出てました。

関連記事

廃刊でなく休刊なので復活の可能性は少しはあるのかもしれません。
しかし、昭和２５年の創刊以来、５９年も続いてきた雑誌が突然休刊とは驚きました。    

>そう言えば，MoGoTitan と金9段が 9/20 に Cotsen Open で再戦するそうで，
>置き石を 7子に減らすとか．持ち時間も 90分を希望しているそうです．

持ち時間15分と90分の２回やり、金8段の２連勝だったそうです。

http://computer-go.org/pipermail/computer-go/2008-September/016293.html    

"a loose-ladder catastrophy" は笑ってしまいましたが、これはシチョウ対策が仇になって罠に落ちた、ということでしょうか？
「九子では勝ち目なし、八子でも苦しい」と言っていたわりには、45分でも七子でMoGoがかなりひどくやられていますね。
金八段の対策の賜物でしょうか？    

女流棋士による９路盤棋戦「妙花」の解説が公開されています。
青葉四段ＶＳ万波四段（解説王唯任四段）

そこで
「初手は天元の一路横に打つのが良い、天元はあまりいい結果につながらない」
ということが研究で判っているようなことが解説されています。

私は９路盤は普段全く打たないのでそんなことは全く知りませんでした！

先日のcrazystoneと王銘えん九段戦ではcrazystoneは初手天元に打っています。
crazystoneの作者はそのことを知らなかったのか？あるいは知っているけど、
あえて自由に打たせているのか？気になるところです。    

FIT2008で青葉さんの解説では9路では初手天元に打つのは「2目損」だそうで
コミ6.5目の勝負ではあまり打たれないそうです。
ただ、メイエンさんとの勝負ではコミなしでしたし、その状況では
あまり関係ないかも、とのことでした。

個人的な感想ではCrazyStoneの作者は知らなかったか、知ってたとしても
定石ファイルがたまたま初手天元を選んでしまった、のではないかと思います。

  ＡＢＣＤＥＦＧＨＪ
１┌┬┬┬┬┬┬┬┐
２├┼┼┼☆┼┼┼┤
３├┼┼┼●┼┼┼┤　解説では黒が天元に打った場合、
４├┼┼┼┼┼┼┼┤　4手目に白がここに犠打を放つのが好手、とのことでした。
５├┼┼┼●┼┼┼┤
６├┼┼┼┼┼┼┼┤
７├┼┼┼○┼┼┼┤
８├┼┼┼┼┼┼┼┤
９└┴┴┴┴┴┴┴┘

「妙花」万波佳奈4段−青葉かおり4段 戦
http://www.igoamigo.com/igofes/myoka/result/game/20080909.html
http://www.igoamigo.com/igofes/myoka/index.html    

Computer-go MLでつい先日、「九路では初手E5がベストだよね」という発言があり、誰も反論してませんでした。みんな（含むRemiさん）そう信じてるのではないでしょうか？
（誰か教えてあげた方がいいかも…）    

信じているのではなく，何人かの実験※で E5 がベストだったので定着しています．
※初手を長時間考えさせるだけ
彼らはプロ棋士の発言と言えども客観的な裏付けが無い限り信じないようです．
山下さんが書いた手順や二目損の話は私が紹介してますが，マトモに取り合って貰えてません．
まぁ，コミもルールも違いますし．    

荒木@北京でへたっている　です。
初手の情報ですが、これだけ9路碁プログラムが強くなっているなら、CGOSの上位陣の棋譜をたくさんあつめて、初手と勝率の関係を調べればよいのではないかと思います。誰かやってそうですけどね。

ところで加藤さんか山下さん、ここをご覧になっているなら、Computer Olympiadでの通信対戦について教えてください。公式のドキュメントには詳しくは書いていなかったのですが、GTPに対応していれば大丈夫だろう程度に考えて来てしまいました。Goguiをうまく使えばNNGSサーバーが無くても通信対戦できるようですが、まだ試していないので自信がありません。明日、テストに協力していただけませんか?    

>公式のドキュメントには
今回の rules は見てませんが，前回は両者が合意すれば OK だったので
例えば GoGui に付属してる server と client を使えばいいのでは？
僕のは単独の PC ではないのでちょっと手間が掛かるかも知れませんが
それで良ければいつでも協力します＃部屋番号（＝電話番号）は 2814 です    

とりあえず、勝也のＧＴＰ対応を済ませたのですが…
　＞清さん、ダウンロードして置いてください。

GoGuiに付属のserverとclientの使い方が結局分からなかったまま、
清さんを北京へと送り出したので、うまく通信できるようなら、清さんに
方法を伝授してくださいませ。よろしくお願いいたします。
　＞加藤(gg)様　＆　荒木(ark)様    

MC_arkの荒木です。
散々な成績だった上に、最終ラウンドは打てずに帰国することになりました。
UEC杯までにはもっと強くしたいですね。

さて、通信対戦ですが、私は9路盤ではすべて手入力で対戦したので、通信対戦の方法は分かりません。KGS経由で対戦している人は何組かいましたが、直接GTPでと言う人はいなかったように思います…。    

直接GTPと言うのは不可能なはずなので…
（GTPでは、標準入出力を使うから、同じマシンで実行しないといけなくなってしまう）
KGSを使うなら、GMPを使えばいい「はず」で、KGSからダウンロード出来る
クライアントにGTP対応していたものがあると思うので、
それを使えばいい、ということになるのでしょうかね…。

きっと現地で山下さんや加藤ggさんが清さんに協力してくれる…と思うので、
よろしくお願いいたしますvv。

以下、業務連絡 to 清さん

・GTP対応勝也をGTP対応した状態で立ち上げるには、
　勝也の起動時のオプションに、 -gtpを付けて下さい。
・GTPの全機能を実装しているわけではないので、終了時の判定が自動で出来ません。
　勝也のGUIが立ち上がっているので、終局したら、勝也の『形勢判断』ボタンをクリックして、
　それで勝敗判定を行うか、勝也が死に石と判断している死に石の除去を、GoGuiのGUI上で、
　手で行うなどで対処して下さい。    

荒木さん、お疲れ様でした。
昨日までで終了のはずが1日伸ばして対戦、とは不合理ですね。

通信対戦をしてる人はKGS経由がほとんどだったと思います。
下の方法を使えばKGS経由でなくともLANに繋がってさえいれば対戦は可能です。
(最新版では twogto.jar は別の名前 two_gtp.jar とかだったと思います）

ただ、ネットワークの接続が非常に不安定なので（DHCPサーバでおかしいのか
たくさん繋ぎ過ぎてるのか、IPが突然割りあてられなくなったりします）
直接IPを指定して繋いでも対戦はやっぱり不安定かもしれませんけど。

2つの囲碁プログラムをLAN経由で対戦させる方法
http://www.yss-aya.com/bbs_log/bk2006-4.html#bbs231    

北京で開催されているComputer Olympiadの囲碁部門ですが
9路はMany Faces of Goが15勝3敗で優勝しました。
http://www.grappa.univ-lille3.fr/icga/tournament.php?id=180

本命と見られていたMoGoは最終戦でYoGo相手に1勝1敗で星を落として
Leelaとの2位決定戦にまわっています(1勝1敗で明後日ぐらいに再戦予定)

上位はほとんどInternet経由で自国にあるサーバに接続して対戦する、
というスタイルでMFGは32コア、MoGoは160コア〜36コア、Leelaは4コア、
後は大多数が8コアを使っていました。

その中でも5位に入っているYoGoは普通の非力なノートPCで光っています。
YoGoの作者は中国のプロ棋士6段とのことで、複雑なパターンを
自分でかなり入力していてあまり考えずにきれいな強い手を打っていました。
去年行われた中国の大会では19路でも優勝して中国では最強とのことです。

会場のLANが不安定なこともありサーバに接続できずに30分、1時間、と
開始が遅れるのはざらで、ネット経由の不安定さがかなり問題でした。

昨日から19路の対戦が行われています。
参加者は欠席が相次ぎ13チームと少し寂しい数になってます。
MFGがMoGoを倒して19路でも優勝しそうな勢いです。
http://www.grappa.univ-lille3.fr/icga/tournament.php?id=181
大会は10月5日まで行われます。

本命と見られていたCrazyStoneが9路、19路とも不参加なのは残念です。    

山下さん、加藤さん、清さんはまだまだ戦いが続きますね。お疲れ様です。

最終局が不戦敗になってしまったのは残念でした。

会社へのお土産は結局食べ物(名前は知らない)にしたのですが、北京のお土産が食べ物というのは何人かの人に笑われましたね。粉ミルクが良かったという人もいました(笑)。
ちなみに会社の人たちはもっといい成績を期待していたらしいです…。

YogoがノートPCで強かったのは確かにすごいと思いました。9路は序盤で決まってしまうことが多いので、序盤のデータベースが優れていればそれだけでかなり強くなるのでしょうけど。

私もUEC杯までには絶対19路でまともに打てるくらいに改良します。来年のComputer Olympiadは19路で出たいと思います。

それでは。    

今　13th International Computer Games Championshipのサイト覗いて見ますと、
１９路の碁で山下さんのAyaが４位でアジア勢でトップですね！！！お見事でした！！
（１位はMany Faces of Go）

しかし欧米勢は強いですね！アジア勢が強い人間の世界戦とは好対照です。

１位のMany Faces of GoはCombination of a strong traditional knowledge based go program with monte carlo search.

という事でこれはハイブリッド方式とでも言うのでしょうかねぇ？自作ソフトもこの路線にしようかと考え中です。    

善勝寺さんありがとうございます。
個人的にはモンテカルロ以前の囲碁プログラムの代表であるMFGが
さくっと切り替えてこれだけの成績を残したことに敬意を表したいです。

古い囲碁プログラムの手法をモンテカルロに利用する（手を絞ったり
playoutの確率を変動させるのに利用）というのは彩もやってはいるのですが
以前からより正しい評価が出来ていたMFGに一日の長がある感じはしました。

アジア勢では韓国が参加していないのが少し寂しい感じもします。    

北京での大会の写真をここに置きました。
http://yssaya.web.fc2.com/photo/beijing2008/beijing2008.html    

ゲームプログラミングワークショップのナイトイベントの一つ，GPW杯コンピュータ囲碁大会の実施要項が決まりました．皆様の積極的な参加をお願いします (_ _)．
※ゲームプログラミングワークショップ http://sig-gi.c.u-tokyo.ac.jp/gpw/2008/

方式: 先後交代総当たり
持ち時間: 15分切れ負け
ルール: 中国ルール
コミ: 6目半
その他: 機器は持ち込み．人間の参加も可．代理操作は止むを得ない場合以外認めない．
※会場に Internet 環境はありません．

但し，参加チーム数が大幅に増えるなど，状況によっては方式を変更する可能性もあります．    

台南と北京のコンピュータ囲碁大会で使った不動碁のソースを公開しました．
http://www.geocities.jp/hideki_katoh/programs/fudo-v3.tar.bz2
あまり強くありませんが，MITライセンスになってますから自由に利用して下さい．
v3 ではネットワーク並列 MCTS が実装されました．    

Bonanzaが2年ぶりに公開されています。
http://www.geocities.jp/bonanza_shogi/    

　来る10月19日（日）の午後に、コンピュータ将棋オープン戦を開催いたします。
　参加希望の方は電子メールで　applyxcomputer-shogi.org （担当：香山 健太郎）まで
参加希望の旨お送りください。
　今回も、当日の飛び入り参加・途中までの参加も受け付けます
（各試合の15分前までにお申し込みください）。

※指し手を決定するのは人間でも構いません。その場合はインタフェースとして
　 http://www.junichi-takada.jp/sficp/ のJava Applet などをご利用ください。

※自作のプログラムであれば、同時に複数のバージョンを参加させても構いません。

※当日は中継のテストも行います。参加されない方もぜひご観戦ください。

　なお、大会の詳細は下のURIをご覧ください。 
http://www.computer-shogi.org/open/open10.html
   

12月13(土),14日(日)に調布の電通大で開催される
第2回UEC杯のホームページができています。

2日目にはメイコウさんの解説と、優勝ソフトと青葉かおり4段との
エキシビジョン対戦が予定されているそうです。
http://jsb.cs.uec.ac.jp/~igo/2008/    

１２月７日（日）に５五将棋大会が開催されます。
ＨＰがようやく形になりましたので、御連絡します。
参加申し込みの募集も始まりました。

ＣＯＭ部門、人間部門、ＫＩＤＳ部門、それぞれありますので、
大勢の参加を期待しております。
http://minerva.cs.uec.ac.jp/~uec55-kousiki/uec55_2008/index.html    

floodgate に激指し・東大将棋はでない。    

GPW08でお会いした皆様、大変お世話になりました。
会場で一部の方にお配りしました「必至がかかるか問題集」につきまして、
下記ページに問題等を置いておりますので（出題意図など加筆しました）
よろしければご覧ください。 
http://www.geocities.jp/problem_extra/hisshi.html
   

11月8日に箱根のGPWの会場でひっそりと？行われていた
加藤さん、清水上さんと棚瀬将棋、激指のリベンジマッチは

○加藤   幸男 − 棚瀬将棋×
×清水上 徹   − 激指    ○

と人間側の1勝1敗でした。持ち時間は1時間1分

将棋パイナップルに棋譜が出ています。
http://shogi-pineapple.com/bbs/mibbs.cgi?mo=p&fo=pc&tn=0002&rn=30

今朝の読売新聞にも記事が出ていました。

元アマ竜王２人、１勝１敗…コンピューターとの将棋対局
http://www.yomiuri.co.jp/national/culture/news/20081108-OYT1T00473.htm
GPW2008
http://sig-gi.c.u-tokyo.ac.jp/gpw/2008/schedule.html    

12月13(土),14日(日)に電通大で開催される第2回UEC杯ですが
ネットワーク経由で出場することは可能でしょうか？？
できれば大学の大型並列計算器を使用して参加したいのですが
当然持っていくことができないので、可能かどうかわかる方がいれば教えて頂ければ幸いです    

ネットワーク経由で出場することは可能ですが、いくつか条件があります。

http://jsb.cs.uec.ac.jp/~igo/2008/sankayouken.html

の１−２、１−４、２−２を参照してみて下さい。
（事前に許可が必要だったり、条件があります。）

それから、マシンをリモートに置くのは可能ですが、操作する人間が必ず一人以上会場にいないとならないのでご注意下さい。    

インターネット経由でサーバと通信して対戦する場合は、
規約を読む限り、原則手入力となってしまうようです。
入力時間を含んで切れ負けなので19路では厳しいかもしれません。

運営の方に詳細を聞いてみるのが一番確実だと思います。    

ご丁寧にありがとうがとうございます。
運営の方にお聞きしたところやはり手入力だと言われました。

今回は無理せず8coreでの出場を検討します。
(対局中ずっと画面を凝視しているのは辛い)    

表記資料とソースコードを公開しました。
http://www.geocities.jp/shogi_depot/　の「資料」
ご興味ある方はご参考下さい。    

MC_arkを19路で打たせるべく改良していますが、現状ではGNUGolevel0にたまにしか勝てませんね。    

今月号の将棋世界にコンピュータ将棋第一人者の山下さん、棚瀬さんの両巨匠による熱き対談が掲載されておりますね。
中でも、コンピュータ将棋がプロ棋士を負かすのはいつなのか? の編集者からの質問に対して、
棚瀬さんが２年後と答えられており、これに対して、いいかげんやなーと思われる方、頼もしいなぁーと思われる方、
いろいろいるんじゃないかと思います。
先日のリベンジマッチでは加藤氏が勝利されており、
私観では、やはり研究されてはまだコンピュータ将棋に分が悪い感じですね。

また、負けたくないソフトとして棚瀬さんは激指とBONANZAを挙げ、Yssはどうも眼中には無いのでしょうかね? (^^;
山下さんもムッとされたのか、棚瀬将棋には負けたくない、と闘志をあらわにしている様子…(^^A

しかし、棚瀬将棋と激指は私が勝手に公認した『Bルーチン』プログラムゆえに生半可な気持ちでは、
到底勝てませんよ、と思っていますが。(^^;　(ほんまかいなー)

来年の選手権では明暗別れるところ、今から両者の激戦に期待しています。    

ここにもいろいろとありました 
http://www.maruden.net/shogi/computer_shogi.htm
   

何らかの方法で手の静的評価をしない限り 19路で GNU Go を超えるのは無理でしょう．
この「何らかの方法」が色々あるところで，棋譜から学習 (Crazy Stone)，自己対戦で (MoGo), 以前のプログラム開発で蓄えた知識 (Many Faces of Go) 辺りが現時点での代表例でしょうか．    

Crazy Stoneのまねはしているのですが、作りこんでいないうえ、シミュレーションが遅いので、やはり弱いですね…。予選通過できると良いのですが…。    

BT はバグってても分かり難いのが難点 :-). 山下さんみたいに頻度だけでやるのも一法かも．この場合は他にも色々な手法を併用する必要がありますが．
実行速度に関しては，パターンをハッシュで表現する手法を使えばかなり改善されると思います（Remi の参考文献)．と言うか，少なくともシミュレーション中はこれを使わないとかなりきついでしょう．まぁ一部サボる手もありますが．    

私は最大エントロピー法と、頻度を組み合わせて使っています。ただ、何にせよ持ち時間40分だと、19路でplayoutが1手あたり4000(1000*4コア)くらいしか出来ないというのがなんとも情けない限りで…。
パターンのハッシュ化はやっています。というか、Remiさんの参考文献に載っている私の論文でもやっています。小さいパターンだと、ハッシュではなくパターンとindexを一対一対応させて、配列アクセスでスコアを出しています。
一応高速化にも取り組みました。progressive wideningを入れる前に9路で速度測定した時は、1コアで2000playout/秒くらいにはなっていました(olympiadの時の1.5倍くらい?)。まあ、それでもかなり遅いですが…。その上、並列化の効率が悪いらしく、またprogressive wideningの入れ方も悪かったらしく、今の速度になってしまいました。    

シミュレーション中は 3x3 だけでしょうけど，これもハッシュでインクリメンタルに計算した方が高速になりませんか？
ただ，ローカルなパターンだけでは汎化能力が不足するのではないかと思います．つまり頻度の最尤推定だけでは足りなくて特徴抽出まで含めた学習が必要なのではないかと．
Remi はかなりテクニックを駆使して特徴抽出を高速化している様で，簡単には真似できないでしょう．
実装速度で勝てないならそれを上回る，とてつもなく重いシミュレーションは？と言いたいところですが，どうも現状は，探索側を重くしてシミュレーションは高速に，という方向が成功しているようです．    

indexもインクリメンタル計算です。
>実装速度で勝てないならそれを上回る，とてつもなく重いシミュレーションは？と言いたいところですが，どうも現状は，探索側を重くしてシミュレーションは高速に，という方向が成功しているようです．
そういう方向で頑張るのも面白いとは思っています。人とは違う方向を試すのも結構好きです。が、今はひとまずUEC杯に向けて頑張ります。    

>>>小さいパターンだと、ハッシュではなくパターンとindexを一対一対応させて、配列アクセスでスコアを出しています。
これを受けて
>>これもハッシュでインクリメンタルに計算した方が高速になりませんか？
と，質問したわけですが，
>indexもインクリメンタル計算です。
私が何か勘違いしてるんでしょうか？
>今はひとまずUEC杯に向けて頑張ります。
ですね．    

加藤さんが「ハッシュ」とおっしゃっているのはZobrist Hashingのことですね?
Zobrist Hashingだと、3*3のパターンなら以下のような乱数テーブルを用意して、各マスの対応する色の乱数をすべてxorしてハッシュ値を求めます。
[黒テーブル]
r_b00 r_b01 r_b02
r_b10 r_b11 r_b12
r_b20 r_b21 r_b22

[白テーブル]
r_w00 r_w01 r_w02
r_w10 r_w11 r_w12
r_w20 r_w21 r_w22

(他に空点用のテーブルと、盤外にはみ出ている場合のテーブル)

私も大きなパターンに対してはこのZobristHashingを使っています。64bit数です。しかし、ハッシュよりも配列アクセスの方が速いので、小さなパターンに対しては以下のように配列indexを計算しています。

(1)以下のようなテーブルを用意
4^0 4^1 4^2
4^3 4^4 4^5
4^6 4^7 4^8

また、黒=0、白=1、空点=2、盤外=3と対応付ける。

(2)パターン中の各マス目において、その色とテーブル中の値を掛け算したものの和を求める。
例えば、以下のようなパターンだと
黒 白 黒
空 白 黒
外 外 外
以下のように計算します。
4^0 * 0 + 4^1 * 1 + 4^2 * 0 + 4^3 * 2 + 4^4 * 1 + 4^5 * 0 + 4^6 * 3 + 4^7 * 3 + 4^8 * 3
足し算と引き算により、インクリメンタルな更新もできます。

言葉足らずですいませんでした。