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

修正したものをアップしてみました。『修正しました』を左クリックしてダウンロードしてみてください。

俺さん、自分では飛車・角で王手を掛けるとちゃんと（移動）合駒ｏｒ逃げるのですが、どのような状態でそうなるのか教えていただけないでしょうか？（小駒による王手？） 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

玉の後ろから王手すると逃げない事が多い。(大駒だけじゃなくて銀、金でも)

下の図で金は通常飛車によりピンされてるので横にしか動けないが銀を取る。
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
| ・v玉v金・ ・ ・ ・ 飛 ・|一
| ・ ・ ・ 銀 ・ ・ ・ ・ ・|二
| ・ ・ ・ ・ ・ ・ ・ ・ ・|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| ・ ・ ・ ・ ・ ・ ・ ・ ・|七
| ・ ・ ・ ・ ・ ・ ・ ・ ・|八
| ・ ・ ・ ・ ・ ・ ・ ・ ・|九
+---------------------------+    

なるほど！ピンの概念はまだ入れてなかったです。
次の課題はこれにします。 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

の投稿に関してです．コンピュータ将棋の進歩で解説されているのは df-pn 探索アルゴリズムだったと思うのですが，ひとまず証明数探索の方で説明します．

> あとはDnをもとめてとりあえずPnとDnが分かったとして、
> これでは意味が無いと思います。
> なぜならAはすでに展開してしまったからです。
これ自体は正しいです．ルートノード(この場合はノード A)の証明数や反証数自体は証明数を使った探索では使いません．

下の例で説明すると，次に展開するべきノードの候補は末端ノード G, H, I, J, K, L, M のどれか一つになります．

AND 　　　　　　　　　　A
　　　　　　　　　　 ／   ＼
OR                  B         C
                 ／   ＼        ＼
AND            D         E         F
            ／   ＼    ／｜＼    ／ ＼
OR         G       H  I  J   K  L     M

次に展開すべきノードを選ぶのに，A から見ていきます．
A には二つ子ノード B と C があります． A は AND ノードなので，このうち反証数が小さい方を辿る候補として選びます．
ここでは Dn(B) = 3, Dn(C) = 2 なので， C が辿られることになります．

次に C は OR ノードなので，本来は証明数が小さいノードを辿る候補にするべきところなのですが，C には子ノードが F しかないので F を辿ります．

その次の F は AND ノードで，二つの子ノード L と M があります．これらは両方反証数が 1 なので，(証明数探索としては)どちらを次に展開しても良いことになります．そこで，例えば L を展開したら子ノードが二つあったとします：

AND 　　　　　　　　　　A
　　　　　　　　　　 ／   ＼
OR                  B         C
                 ／   ＼        ＼
AND            D         E         F
            ／   ＼    ／｜＼    ／ ＼
OR         G       H  I  J   K  L     M
        　　　　　　　　　　  ／＼
AND                          N    O

同じような手順をふむと，次は M が展開の候補となります．

ココロとしては，OR ノードでは証明しやすそうな子ノードを，AND ノードでは反証しやすそうな子ノードを辿っていき，一番証明・反証に「ききそう」な末端ノードを選んで展開する，というのが証明数探索です．    

なんか，色々盛り上がっていますね〜．

ありがとう。それでプログラムしてみます。    

修正したものをアップしました。『Ｖｅｒ０．３』からダウンロードできます。
下からの攻撃をー１５（左下）、−１６（真下）、−１７（右下）として計算していたのですが、マイナスなのを認識させていませんでした。ピンの概念はまだいれていません。

あまのさん、面白いプログラムですね。ホームページをもっていらっしゃるなら相互リンクをお願いしようと思ったのですが、ちょっと変わったホームページらしい（個人では無く法人らしい）のでどうしましょうか？
現在は将棋プログラムの開発は為されていないのでしょうか。 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

＞木口さん
ありがとうございます。

ただプログラムの方は一時的に置いているだけで
すぐにでも消すつもりなので（というかついでに今消しました。。。）
申し訳ありませんがリンクの方はご遠慮いただけますでしょうか。
すいません。。。

ちなみにＢＡＳＩＣ系で最強の将棋ソフトは
きっと椿原将棋さんになるんでしょうね。    

>あまのさん
了解しました。 
http://www.k4.dion.ne.jp/~basic/
   

さっそくaya586をダウンロードしました。
が、Win9X系では「内部エラーで停止しました」の表示で、
起動できません。(--;

私だけの環境だけなのかも、知れませんけど・・・。

ほんまかいなー(^^A    

メモリが128MB以下だとメモリ確保に失敗してエラーになるようになっていました。
近いうちに修正します。    

>メモリが128MB以下だとメモリ確保に失敗してエラーになるようになっていました。
>近いうちに修正します。

128MB以上での動作確認はしています。

しかし、修正するのは、どうなんでしょうか。
修正する事によって、128MB以上と以下での棋力(勝率)はどのくらい変わるものなのでしょうか?

それにより、128MB以下の利用者からの批評(実際の棋力以下)は面白くないでしょうから。
aya586は、メモリ128MB以上を動作条件とし、
旧ayaをメモリ128MB以下用に公開するのも手かもしれません。

「内部エラーで停止しました」を「メモリ確保に失敗しました」に、
修正する必要はあるけどねー(^^;    

囲碁はあまり興味ないですがyssと違ってaya586はビックリするほど弱いように感じますが？(適当に大きく囲めば勝てる)    

持ち駒の香車が打てないバグを修正しました。
ちょっと掲示板を荒らしてしまったようで申し訳ないです。
編集、削除ができるんですね。
後は、池泰弘『コンピュータ将棋のアルゴリズム』ｐ１３５の金銀・成り駒の価値について相手の玉の位置関係、自分の玉との位置関係によって、評価点を調整する手法を取り入れれば、０手読み版は完成です。 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

コンピュータ碁のメーリングリストで話題になってますが、
CrazyStoneとかのモンテカルロ法ベースのプログラムを7路盤で動かすと
かなり強いそうです。
http://computer-go.org/pipermail/computer-go/2006-October/006890.html

Akebonoの美添さんもそんなことをおっしゃてましたし、
Valkyriaの作者（Vikingのモンテカルロ版）も、序盤の定跡を
少し追加すればほとんどパーフェクトにプレイできるのでは、
とかチャットで言ってました。
CrazyStoneはKGSで5段の人と互角、とのこと。

MLによるとコミは7.5目では明らかに小さくて9目ぐらいだろう、とのことです。
ちなみに人間による解析では黒９目勝ちです（日本ルールで）    

>序盤の定跡を

本題と関係がないのですが、素朴なツッコミを入れさせてください:-)

http://gogen-allguide.com/si/jyouseki.html

多分、これは山下さんなら百も承知でしょう。ですので変換ミスであることは
こちらも百も承知の上です。ですが、山下さんだからこそ安易に誤った使い方を
されると他への影響が大きいと思いますので、敢えて。    

ですね。
失礼しました。

余談ですが、MoGoは9路ではGnuGo3.6相手に9割以上、13路でも25%は勝つそうです。
囲碁知識を使って、手を枝刈すると、13路でも50%近く勝つそうです。
ただし、19路では一回も勝てない、とのこと。（ちょっと安心ですが）

彩も13路で全幅探索のαβを試してみたら、意外にも出入り計算よりも勝率が
上がりました。（といっても2割が3割ですが）
13路ぐらいまでは全幅探索が優位に立ちそうな気がします。    

池泰弘『コンピュータ将棋のアルゴリズム』ｐ１３５の金銀・成り駒の価値について相手の玉の位置関係、自分の玉との位置関係によって、評価点を調整する手法を取り入れました。
０手読み版はひとます完成です。 
http://www.k4.dion.ne.jp/~basic/shougi.htm

いかがでしょうか？ 
http://www.k4.dion.ne.jp/~basic/shougi.htm

22日の朝日新聞の日曜版のbeにコンピュータ将棋関係の記事が載る予定、とのことです。    

ネットで記事が読めます。

プロにもびびらず
http://www.be.asahi.com/be_s/20061022/20061006TSUN0001A.html    

GTPに対応している囲碁プログラム同士をWindows上でLAN経由で対戦させる場合です。
まずgoguiをインストールします。Java1.4以上の環境が必要です。
http://gogui.sourceforge.net/

DOSプロンプトを起動して、解凍した gogui-0.9.1\lib\ の下に移動します。

取り合えず、彩とgnugoを同一マシンで対戦させる場合は、
下のようにします。10試合を白黒交互に。棋譜の名前は ayagnugo で。
java -jar twogtp.jar -black "c:\aya\release\aya.exe --mode gtp" -white "c:\go\gnugo\gnugo.exe --mode gtp" -games 10 -size 9 -alternate -sgffile ayagnugo -auto

別のマシンで立ち上げたプログラムと対戦させるときは、
まず、片方のマシンでGTP対応のプログラムを gtpserver を使って起動させます。
java -jar gtpserver.jar "c:\aya\release\aya --mode gtp" -port 5555

次に、もう片方のマシンで対戦相手を起動します。（ここでは同一のマシンのIPを指定してます）
java -jar twogtp.jar -black "java -jar netgtp.jar 127.0.0.1 5555" -white "c:\go\gnugo\gnugo.exe --mode gtp" -games 10 -size 9 -alternate -sgffile ayagnugo -auto

しかし、これだと対戦中の画面を見ることが出来ません。
そこで下の内容の twolan.bat というバッチファイルを作って起動します。
------------------------------------------------------------------------------------
REM 2つのプログラムをLAN経由で対戦
set TWOGTP=java -jar twogtp.jar -black """java -jar netgtp.jar 127.0.0.1 5555""" -white """c:\go\gnugo\gnugo.exe --mode gtp""" -games 10 -size 9 -alternate -sgffile ayagnugo
java -jar gogui.jar -size 9 -program "%TWOGTP%" -computer-both -auto
------------------------------------------------------------------------------------

単に同じマシン上で対戦させる場合はこうなります。
------------------------------------------------------------------------------------
REM 2つのプログラムを同じマシンで対戦。goguiで観戦。
set TWOGTP=java -jar twogtp.jar -black """c:\aya\release\aya.exe --mode gtp""" -white """c:\go\gnugo\gnugo.exe --mode gtp""" -games 10 -size 9 -alternate -sgffile ayagnugo
java -jar gogui.jar -size 9 -program "%TWOGTP%" -computer-both -auto
------------------------------------------------------------------------------------

DOSプロンプトで引用符(ダブルクォーテーション)の中で引用符を使う場合は
3つ付けないと動かない、というのが難解でした。(OSはWindowsXPでのみ確認）    

証明数/反証数を使うプログラムができたのでとりあえず下の問題を解かせてみた。
特に同一局面のチェックや証明駒の概念はいれていない。単純に証明数/反証数が小さい値を検索するだけのプログラム。
結果からゆうと解けず。

  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
| ・ ・ ・ ・ ・v金v角v桂v香|一
| ・ ・ ・ ・ 角v金v玉・ ・|二
| ・ ・ ・ ・ ・ ・ ・ ・ ・|三
| ・ ・ ・ ・ ・v歩v桂v歩v歩|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| ・ ・ ・ ・ ・ ・ ・ ・ ・|七
| ・ ・ ・ ・ ・ ・ ・ ・ ・|八
| ・ ・ ・ ・ ・ ・ ・ ・ ・|九
+---------------------------+

持駒 飛 銀 桂　　問題:聖美堂出版 新しい詰将棋(著者 高橋道雄)

バグかと思って下の問題をやらせたところ第１問が4秒、第二問が2秒ほどで解けた。もともと各種の関数が遅いようなので一瞬とまではいかないようだ。
ttp://www.shogitown.com/book/consi/soft/09geki2_tume-2.html

普通にやれば図の問題も数秒で解けるものですか?    

>普通にやれば図の問題も数秒で解けるものですか?

このくらいの手数の詰物は、現行のプロセッサなら一千分の数秒、
即ち数ミリ秒で解けるのが普通だと思います。付け加えて、ＰＮを
使って効果が出るのは、長手数の詰物に対してでしょう。
余談ですが、

>問題:聖美堂出版 新しい詰将棋(著者 高橋道雄)

この詰棋本は、55番（作意は13手詰）、89番（作意は19手詰）の２問が
不詰物なので、プログラムの試験用には使われない方がよいでしょう。    

２手先（コンピュータ→プレイヤー→コンピュータ）まで読めるようになりました。
池泰弘『コンピュータ将棋のアルゴリズム』のＰ８５まで来たことになります。
だいぶ将棋らしくなってきた（？）と思います。しかし、これ以上はどうしたらよいのやら・・・。ハッシュなんてＢａｓｉｃで出来るかな？ 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

GPWで電通大の矢野さんによる碁盤に置ける連の最大数、という
発表があったのですが、
その局面を手持ちの囲碁ソフトに読み込ませてみると、見事なほどに！
全てのソフトが落ちました。
棋譜を読み込ませた瞬間に落ちたり、思考させた瞬間に落ちる、などです。

試したソフトは
GnuGo、銀星囲碁5(KCC)、AI囲碁2004(MFG)、はるか、お父さんの強い囲碁4(Go4++)、
手談対局3(Handtalk)、FunGo、
の７つです。
ちなみに私の彩も落ちました。256あれば十分かと思ってたのですが甘かったですね。

最大の局面は下で、連が277個あります。

  ＡＢＣＤＥＦＧＨＪＫＬＭＮＯＰＱＲＳＴ
１○┬○●○┬○●○┬○●○┬○●○┬○
２●○●┼●○●┼●○●┼●○●┼●○●
３├●○●○┼○●┼●○●○┼○●○●┤
４●○┼○●┼●○●○┼○●○●○┼○●
５○●┼●○●○┼○●○●┼●┼●○●┤
６├○●○┼○●○●┼●○●○●┼●○●
７○●○┼○●┼●○●○┼○┼○●○┼○
８●┼●○●○●○┼○●○●┼●○●┼●
９○●○●┼┼○●○●┼●○●○┼○●○
10├○┼○●○●┼●○●○┼○●○●○┤
11○●○●┼●○●○┼○●○●┼●┼●○
12●┼●○●○┼○●○●┼●○●○┼○●
13○●○┼○●○●┼●○●○┼○●○●┤
14├○●○●┼●○●○┼○●○●┼●○●
15○●┼●○●○┼○●○●┼●○●○┼○
16●○┼○┼○●○●┼●○●○┼○┼○●
17├●○●○●┼●○●○┼┼●○●○●┤
18●○●┼●○●○┼○●○●○●┼●○●
19○┴○●○┴○●┴●┴●○┴○●○┴○

(;GM[1]SZ[19]
;B[da];W[aa];B[ha];W[ca];B[la];W[ea];B[pa];W[ga];B[ab];W[ia];B[cb];W[ka]
;B[eb];W[ma];B[gb];W[oa];B[ib];W[qa];B[kb];W[sa];B[mb];W[bb];B[ob];W[fb]
;B[qb];W[jb];B[sb];W[nb];B[bc];W[rb];B[dc];W[cc];B[hc];W[ec];B[jc];W[gc]
;B[lc];W[kc];B[pc];W[mc];B[rc];W[oc];B[ad];W[qc];B[ed];W[bd];B[gd];W[dd]
;B[id];W[hd];B[md];W[jd];B[od];W[ld];B[sd];W[nd];B[be];W[pd];B[de];W[rd]
;B[fe];W[ae];B[je];W[ee];B[le];W[ge];B[ne];W[ie];B[pe];W[ke];B[re];W[qe]
;B[cf];W[bf];B[gf];W[df];B[if];W[ff];B[kf];W[hf];B[mf];W[lf];B[of];W[nf]
;B[qf];W[rf];B[sf];W[ag];B[bg];W[cg];B[fg];W[eg];B[hg];W[ig];B[jg];W[kg]
;B[pg];W[mg];B[ah];W[og];B[ch];W[qg];B[eh];W[sg];B[gh];W[dh];B[kh];W[fh]
;B[mh];W[hh];B[oh];W[jh];B[qh];W[lh];B[sh];W[ph];B[bi];W[ai];B[di];W[ci]
;B[hi];W[gi];B[ji];W[ii];B[li];W[mi];B[ni];W[oi];B[ri];W[qi];B[ej];W[si]
;B[gj];W[bj];B[ij];W[dj];B[kj];W[fj];B[oj];W[jj];B[qj];W[lj];B[bk];W[nj]
;B[dk];W[pj];B[fk];W[rj];B[hk];W[ak];B[lk];W[ck];B[nk];W[gk];B[pk];W[ik]
;B[rk];W[kk];B[al];W[mk];B[cl];W[sk];B[el];W[dl];B[il];W[fl];B[kl];W[hl]
;B[ml];W[jl];B[ol];W[nl];B[sl];W[pl];B[bm];W[rl];B[fm];W[am];B[hm];W[cm]
;B[jm];W[em];B[lm];W[gm];B[pm];W[km];B[rm];W[mm];B[cn];W[om];B[en];W[qm]
;B[gn];W[bn];B[in];W[dn];B[mn];W[hn];B[on];W[jn];B[qn];W[ln];B[sn];W[nn]
;B[bo];W[rn];B[do];W[ao];B[fo];W[eo];B[jo];W[go];B[lo];W[io];B[no];W[ko]
;B[po];W[oo];B[ap];W[qo];B[gp];W[so];B[ip];W[bp];B[kp];W[dp];B[mp];W[fp]
;B[sp];W[hp];B[bq];W[lp];B[dq];W[np];B[fq];W[pp];B[hq];W[rp];B[jq];W[cq]
;B[nq];W[eq];B[pq];W[iq];B[rq];W[kq];B[ar];W[oq];B[cr];W[qq];B[er];W[br]
;B[gr];W[fr];B[kr];W[hr];B[mr];W[jr];B[or];W[lr];B[qr];W[nr];B[sr];W[rr]
;B[ds];W[as];B[hs];W[cs];B[js];W[es];B[ls];W[gs];B[ps];W[ms];B[tt];W[os]
;B[tt];W[qs];B[tt];W[ss])    

> 最大の局面は下で、連が277個あります。

すごいですね！！これは新発見かと思います。
(うちのプログラムもあえなく落ちました)    

お世話になっています。
「CgfGoban」のソースを参考に、自作プログラムの中にPipe経由のGTP通信で「GunGo」、「彩」と自動対戦ができるようになりました。感激です。どうも有難うございます。

それで、自作プログラムにもGTPクライアント機能を加えたいと思いますが、普通のウインドウありのWindows-GUIアプリですので、コンソール入出力へのアクセスはうまく行きません。これは ::AllocConsole() を使うのでしょうか？

「CgfGoban」では関連ソースがコメントアウトされて、GTPクライアント機能を持たせていないようですね。
宜しくお願い致します。    

GPWの写真を下に置きました。
http://www.yss-aya.com/photo/20061112gpw/gpw2006.html    

GTPで他のGUIで動かす場合にも
同じようにWindowsのAPIでパイプを作ります。
詳しくは下をご覧下さい。
http://www32.ocn.ne.jp/~yss/cgf_gtp.lzh    

Bonanzaの保木さんのページでGPWで使われた資料が公開されています。
http://www.geocities.jp/bonanza_shogi/
http://www.geocities.jp/bonanza_shogi/gpw2006.pdf    

早速 cgf_gtp.cpp を参考にしてテストし、自作プログラムがパイプ経由のGTP対戦が出来たのを確認しました！チョー嬉しい！(^^;

GetStdHandle() してから、fgets()とWriteFile()を使うわけですね。目からうろこです。

本当にどうもありがとうございました。    

　おおっ、Ｍｙソフトは黒Ｓ１９、３子ポン抜きと打ち返してきました！
低級ソフトが高級ソフトに勝つ局面もあるんやなぁと笑わせて
頂きました（＾＾）

　ところで正着はどこなんでしょう？    

Quad CoreのCPUって、もう発売されたんですね。
来年の選手権は下のQuadのDualで8CPU、で参戦することになりそうです。

x86初のクアッドコアCPU、Core 2 Extreme QX6700が発売される、デモも開始
http://www.watch.impress.co.jp/akiba/hotline/20061118/etc_qx67.html

クアッドコア×デュアルCPUで“8コア環境”を実現する「Xeon 5300」
http://pc.watch.impress.co.jp/docs/2006/1115/tawada90.htm    

やはりプログラムは間違っていました。(変数iが1になっていた)
図の問題も約1.3秒でといた。
あとは千日手のチェックと６４手以上は読まないようにして(配列オーバー)
その他諸々で完成です。
ちなみにハッシュは１１手詰めで大体１７０００くらいしか使ってないので１００万個は多すぎでした。    

GPWでの保木さんの発表、興味深く拝見させていただきました。

ところで、評価値はプロの棋譜などから学習させるということで、
同じような手法でプログラムを開発する場合多くの棋譜が必要だと思いますが、
たくさんのプロの棋譜が電子データでおさめられたような文献やサイトはあるのでしょうか？
将棋の世界をあまり知らず、ご迷惑な質問かもしれませんが教えていただけると幸いです。    

> おおっ、Ｍｙソフトは黒Ｓ１９、３子ポン抜きと打ち返してきました！低級ソフトが高級ソフトに勝つ局面もあるんやなぁと笑わせて頂きました（＾＾）

おおお！落ちずにイイ手を打ち返せるのはすごい！
容量一定の配列の代わりに、std:vector等を使われたでしょうね。先見の明がありますね。そういえば一局の手数が５百手を超えた場合、ウチのヤツも落ちるのです。(|\|)
囲碁ソフトに固定の配列を使うのは拙い設計ですね。

> ところで正着はどこなんでしょう？

盤上アタリだらけで、正着は複数あるかと思います。
でも空点は未だ８４個もありますから、シラミツブシで正解を出すのは至難のワザですね。    

>たくさんのプロの棋譜が電子データでおさめられたような文献やサイトはあるのでしょうか？ 
http://www.geocities.jp/rysyy913/
   

連盟のページによると、
来年4月から「大和証券杯ネット将棋棋戦」が開催されて、そのオープニングイベントとして
渡辺竜王−Bonanza戦（平手）が行われるそうです。

2007年3月21日 品川プリンスホテル、持時間2時間、秒読み1分。

http://www.shogi.or.jp/osirase/061117_daiwa.pdf    

本日、午後2時から、近将道場で清水上
Bonanzaが清水上徹さん、加藤幸男さんと対局します。

近将道場でネット観戦できるとのことです。
http://www.kinsho.net/dojo/

近代将棋のページ「ボナンザ新発売イベント」
http://www.kinsho.net/dojo/event/bonanza.htm

マグノリアのページ
http://www.magnolia.co.jp/bonanza.html
http://www.magnolia.co.jp/bona/Bonanza_release.pdf    

結果はややBonanzaにとっては不出来の2連敗でした。
写真を下に置いておきます。
http://www.yss-aya.com/photo/20061118bona/index01.html    

PC Watchで詳しく紹介されています。

http://pc.watch.impress.co.jp/docs/2006/1120/bonanza.htm

一時、Impress Watchのトップニュースにもなっていました。
インプレスの人も取材に来ていたのですね。

PC情報のサイトに将棋の対局の内容が詳しく載っているのが驚きです。
会場では、2局ともあまりにBonanzaがいいところなく負けたのでは、
との声も聞かれましたが、勝又先生の解説つきで紹介されるインパクトの
前では些細なことと思います。    

GPWでLines of Actionの発表でちらっと言ってたような気がするのですが
RankCutという手法があって、Craftyでは結構効果的だったとのことです。
http://www.comp.nus.edu.sg/~leews/publications/AAAI06-161.pdf

RankCutを実装したCraftyが通常版に比べて62%勝ち越した、とことでかなりの
高勝率です。
(124試合で40勝10敗74引、引分を0.5勝扱いで40+37=77勝 10+37=47敗、勝率0.62）

ただ、これは自己対戦の結果で、Fruitと対戦させた場合は
通常版  11勝39敗14引 勝率 28.1%
RankCut 15勝40敗 9引 勝率 30.5%
とほとんど差異はありません。対局数がちょっと少ないのですが。

手法は、読む順番が後の手ほど、最善手を更新する確率は低い、
という現象を使ったものです。

例えばrootでは、1番目に読む手は取り合えずの最善手となり、
2番目に読む手が最善手になるのはそれほど多くありません。
3番目に読む手が最善手になるのは少なく、25番目とかはめったにありません。

そこで、前もって、n 番目の手が最善手になった回数、を
自己対戦で統計を取っておいて、最善手になる確率が0.75%以下の場合は
読む深さを1手浅くして探索する、という手法です。

実際はHashの手、駒取りの手、Killer手、などを読んだ後のHistoryの手から
適応させています。
また統計を取る条件も手の順番の他に、
探索深さ、王手されてるか、最善手が入れ替わった回数、現在の値とα値との差（7段階）
とかの条件を使ってます。

int RankCut(int alpha, int beta, int depth)
{
    if ( depth == 0 ) return Evaluation();
    bool fPruneRest = false;    // 残りの手を短い深さで読むか？
    while ( 次の手があるなら ) {
        int r = 0;      // 短く読む深さ。0なら通常の深さで読む。
        Compute(Fi);    // i 番目の手の手の特徴を調べる。後何手読むか、とか王手かどうかなど。
        if ( fPruneRest || Π(Fi) < t ) {    // 最善手になる確率が低い(0.75%以下)なら浅く読む
            r = DepthReduction();            // 浅く読む深さ。実験では r=1
            fPruneRest = true;
        }
        int score = -RankCut(-beta, -alpha, depth-1-r);
        if ( socre > alpha ) {
            fPruneRest = false;        // 最善手が更新されたのでリセット
            alpha = score;
        }
        if ( score >= beta ) return score;
    }
    return score;        // ？、alpha の間違いと思われる
}

他にデバッグツールの発表で、MultiCutというのがちらっと出てたのですが、
これはCG98(Computer and Games 1998)に出ている手法で、
Null Window探索のCUTノードでだけ2手読みを浅くして読み、最初の10手を調べて
3手以上枝刈されるなら枝刈、という手法ですが、自己対戦でも52%ぐらいの勝率で
あまり効果はなさそうでした。    

BIGLOBEストリーム「将棋ニュースプラス」で当日の様子が見られます。
http://broadband.biglobe.ne.jp/program/index_shougi.html

将棋ニュースプラスでコンピュータ将棋も取り上げてほしい、と
かねてから要望していましたが、応えていただいたということでしょうか。    

現在、人間の世界チャンピオンのKramnikと強豪ソフトFritzの対戦が行われています。
１試合目はドロー、２試合目はドローが確実と見られた局面で、なんとKramnikが将棋で言うと頭金のような１手詰を見逃して敗北しました。 
http://www.sanspo.com/sokuho/0825sokuho048.html
   

クッキーのせいで関係のないリンクが張られてしまいました。 
http://www.chessbase.com/newsdetail.asp?newsid=3509

クイーンが入っての1手詰の見逃しですか。
これはひどいですね。
Fritzのマシンは何を使ってるか分からなかったのですが、毎秒900万局面を
読む、とのことです。
2002年のクラムニクとの対戦の時で、Xeon900MHz x 8で600万局面を
読んでいたそうですから、そんなに速くなってないですね。

しかし、最強じゃないFritzが対戦するのは少し違和感があるのですが。    

こんにちは。
あれから自作プログラムにPipeGtp、Sgmp、Nngsをそれぞれ実装し、自動通信対戦ができるようになりました。どうもありがとうございます。「彩」の多彩な通信対戦機能は素晴らしいです！

ところでその中のTCP経由の通信対戦についてですが、これはGTPで通信しているでしょうか？
またそのTCP接続について、nngs_tryソース中のTCP関連コードを使えば出来そうでしょうか？

宜しくお願いいたします。    

参考にしていただいてありがとうございます。
彩についているTCP経由の通信、というのは完全な独自仕様で、
SGMPで流している内容をそのままLANに流しているものです。
対局ごとにサーバになったりクライアントになったりする
仕様になっていています。

彩同士の自動対戦でしか使ってないので、あまり対応されるメリットはないかと思います。
一応、関連ソースはこちらです。
http://www.yss-aya.com/Aya_wsk.lzh    

ネット上の無料囲碁対局サーバのKGSで彩を走らせて見ました。
棋力は9k（9級）で落ち着いたようです。
GnuGoは6k（6級）なので3級差あります。彩のGnuGoに対する勝率は1割程度なので
こんなものでしょう。
日本の段級位はこれより2,3級甘いので、日本の級に直すと彩は7級程度なのかも
しれません。

彩の棋譜
http://www.gokgs.com/gameArchives.jsp?user=AyaBot
彩のレーティングの推移
http://www.gokgs.com/graphPage.jsp?user=AyaBot
GnuGoのレーティングの推移
http://www.gokgs.com/graphPage.jsp?user=GNU    

さっそくソース付きで教えて頂きまして、ありがとうございます。

サーバ・クライアント方式でSGMPを使って、後着の人がサーバになって対局待ちするいう仕様なんですね。面白そうでこれからトライして見ます。

> 彩同士の自動対戦でしか使ってないので、あまり対応されるメリットはないかと思います。

通常のSGMPは２台のPCを近距離にしてケーブルで繋ぐ必要がありますし、NNGSはネットに接続して、特定のサーバ(NNGS)に従って、通信する必要があります。「彩」発明のTCP対局はLANさえあれば手軽に対局できて、中の通信規格はSGMPにしてもGTPにしても簡単に変更できますので、将来の標準対戦形式になるのを予想します。(敬服)    

詰将棋パラダイス12月号に、『新桃花源』の結果発表が行われています。
私がGPWで話題にした通り、1,205手詰でした（一番難しい変化は読んでませんでしたが(笑)）。
結果発表によると、「パソコンでは解けない」そうです。
これは、本格的な証明数2重計上対策を備えた市販ソフトがない、ということなんでしょうか？
そのことを除けば、コンピュータにとって難しい要素はなさそうに思われますので。

http://www005.upp.so-net.ne.jp/tsumepara/contents/6info/info.htm

不完全の指摘もありませんでしたので、晴れて史上2位の長手数詰将棋の誕生ということになります。
詰将棋を解くアルゴリズムを研究されている方はチェックをよろしく。    

問題図はWebでは見れませんか？    

近いうちにこちらに載ると思います。
http://www.ne.jp/asahi/tetsu/toybox/kenkyu/cholist.htm

ここに載せても多分怒られないとは思いますが、一応最新号コンテンツですので、前の投稿に掲載した詰パラへのリンクからご注文を、と宣伝しておきます。

1月のCSA例会で個人的にお見せしますよ。    

http://www.itmedia.co.jp/news/articles/0612/06/news068.html
チェス名人、コンピュータに敗北

将棋はもうすこしかかりますね。。    

人工知能VSプロ棋士の闘いを描いたSF小説が出た。
http://www.yuzuki.biz-web.jp/
２チャンの将棋板でも作品を公開してるよ。
http://game9.2ch.net/test/read.cgi/bgame/1165706999/    

KGSで行われていたソフト同士の大会で、モンテカルロ法を利用した
MoGoがGnuGo、slugGoを押さえて4勝1敗で優勝しました。

この大会は1局に1日（双方の持時間は12時間）を使い、5日間で5局を
行うというもので、8ソフトが参加し、18日から22日までネット上の囲碁サーバ
であるKGSで行われていました。

最終戦で、MoGoBot19がslugGoを破った１局が印象的でした。
MoGoBot19とslogGoの棋譜
http://files.gokgs.com/games/2006/12/21/MoGoBot19-slugGo.sgf

slugGoは22台のマシンを使って、GnuGoの候補手を直線的に読む、というもので
GnuGoよりは若干強いとされています。
モンテカルロ法のプログラムがGnuGoを19路で倒したのは初めてのことです。

優勝したMoGoBot19は1手に5分ほどかけています。
同じく、MoGoBotというソフトも参加していますが、
違いは、MoGoBot19は局所的にだけ探索し、MoGoBotは盤面全体を探索するそうです。
(MoGoBotは手抜きができるのが特徴だそうです)

MoGoの詳細はこちらのページでPDFで読めます。
http://hal.inria.fr/inria-00117266
特徴は局面評価に使う乱数対局では、完全にランダムに手を選ぶのでではなく、
直前に打たれた手がアタリなら逃げる手しか読まない。
アタリじゃなければ、ハネ、キリ、などの3x3の好形があればそのなかから、
といった感じで、囲碁っぽい手順を読んでいく工夫をしています。

探索にはUCT(Upper Confidence bound extended for Trees)
と呼ばれる手法を使っています。
これは手の選択を、その局面の点数（平均値）と、乱数対局を行った回数、とで
選ぶ手法です。対局が少ないうちは点数の低い手が選ばれやすく、対局が増えるにほど
点数の高い手が選ばれるようになります。

雰囲気は、１０台のスロットマシーンがあって、どれが一番出やすいか、
を調べるのに、何度か、それぞれのマシンを試してみる。で、一番出そうなのが
分かったら、それだけを集中して試す、というのに似ています。
これを各深さで行うわけです。
http://senseis.xmp.net/?UCT
Bandit based Monte-Carlo Planning
http://zaphod.aml.sztaki.hu/papers/ecml06.pdf

ちなみに彩も参加したのですが5戦全敗で最下位でした。(1勝は終局判定のミスです)

大会結果
http://www.gokgs.com/tournEntrants.jsp?sort=s&id=255    

>MoGoの詳細はこちらのページでPDFで読めます。
>http://hal.inria.fr/inria-00117266
これは < http://hal.archives-ouvertes.fr/view_by_stamp.php?label=INRIA&action_todo=view&langue=en&id=inria-00117266&version=1# >にあるMoGoReport.pdfの改訂版で，ミスの修正とデータの更新が主なようです．
初版の翻訳がほぼ完了したところをまるで計ったかの様に改訂版を出すとは中々．．．
まぁ大きな変更は無い様なので，改訂版の方の和訳をまもなく公開できるものと思います．
試合の方は，持ち時間がとんでもないのとGNUとの直接対決が無かったのでまだ何とも．．．
＃いずれにせよKCCには勝てないでしょうねぇ．．．    

> 近いうちにこちらに載ると思います。
載りました。
http://toybox.tea-nifty.com/memo/2006/07/post_9839.html

これがコンピュータで解けた、との報告をお待ちしたいと思います。
たとえば、GPW2005にて岡部文洋さんが発表されたBNSであれば、解けるのではないかと思います。
岡部さんは超難解作のページですでに大活躍されていますね。
http://toybox.tea-nifty.com/memo/2005/05/post_3535.html#nankai    

　来年のコンピュータ将棋選手権の参加者募集を開始しました。
皆様、よろしくお願いいたします。


　　　第17回世界コンピュータ将棋選手権　参加者募集のお知らせ


　最強を競う将棋プログラム同士による「第17回世界コンピュータ将棋選手権」を
下記のように開催いたします。主催のＣＳＡは非営利団体であり、この大会はコン
ピュータ将棋の進歩を目的としたものです。
　参加者を募集しますので、ふるってご応募下さい。

１．日程　2007年5月3日（木）〜5日（土）
２．場所　〒292-0812 千葉県木更津市かずさ鎌足2-3-9
　　　　　かずさアーク http://www.kap.co.jp/
３．主催　コンピュータ将棋協会（ＣＳＡ）
          http://www.computer-shogi.org/
４．協力　社団法人日本将棋連盟（予定）     http://www.shogi.or.jp/
５．協賛　日本ＡＭＤ株式会社（予定）　　　 http://www.amd.com/jp-ja/
　　　　　株式会社毎日コミュニケーションズ（予定） http://www.mycom.co.jp/
　　　　　株式会社アイフォー（予定）       http://www.ifour.co.jp/
　　　　　富士通株式会社（予定）           http://jp.fujitsu.com/
６．後援  経済産業省（予定）               http://www.meti.go.jp/
          社団法人情報処理学会（予定）     http://www.ipsj.or.jp/
７．賞品　優勝副賞：ノートパソコン（予定）
８．主な参加資格
　　　　　自作のプログラム１つ。機種は問わない（原則として持ち込み）。
　　　　　思考部にはオリジナリティがあること。
　　　　　（詳細はCSAのWebサイトに掲載されている大会ルールをご覧ください）
９．参加費　１万円（申し込み時、郵便振替）
　　　　　送金後、不参加となっても返金しませんのでご注意ください。
　　　　　送金方法は申込時の通知メールをご覧ください。
１０．申し込み、問い合わせ
　・申し込み期限　2007年1月31日（水）
　・申し込み先
　　　　　次のURIにアクセスし、まずID登録をしてそのIDでログインしてください。
　　　　　その画面で参加申込を行ってください。
          https://www.computer-shogi.org/cgi-bin/wcsc17/apply.cgi
          https://www.computer-shogi.org/cgi-bin/wcsc17/apply-e.cgi (English)

  ・問い合わせ先
          電子メールで
　　　　　　　　　applyxcomputer-shogi.org （担当：香山 健太郎）まで
　　　　　　　　　（ここでは申込は受け付けません）

　CSAのサイトにて、大会ルール・実施要項や過去の選手権の結果・棋譜を掲載しています。
        http://www.computer-shogi.org/

-------------------------------------------------------------------------------- 
http://www.computer-shogi.org/wcsc17/
   

反復深化を入れると、FreeBasicでは画面が表示されないバグが出るので、ＶＢ６．０に移植してみました。反復深化を入れても２手読むのがせいいっぱいです。 
http://www.k4.dion.ne.jp/~basic/shougi.htm
   

盤上に置ける石の最大はいくつか、という話がGPWであったのですが、
その後、Computer GoのMLで報告があり、John Tromp とGunnar Farneback が
専用のプログラムを書いて23路まで解けたそうです。

1   1 -   1 = 0
2   4 -   2 = 2
3   9 -   3 = 6
4  16 -   4= 12
5  25 -   7= 18
6  36 -  10= 26
7  49 -  12= 37
8  64 -  16= 48
9  81 -  20= 61
10 100 -  24= 76
11 121 -  29= 92
12 144 -  35=109
13 169 -  40=129
14 196 -  47=149
15 225 -  53=172
16 256 -  60=196
17 289 -  68=221
18 324 -  76=248
19 361 -  84=277
20 400 -  92=308
21 441 - 101=340
22 484 - 111=373
23 529 - 121=408 (1.4GHzのOpteron、13GBのメモリで1週間かかったそうです）
http://computer-go.org/pipermail/computer-go/2006-December/007398.html

最大数は盤サイズを n として、 floor(4n(n-1)/5+4) という式になるそうです。
floorは小数点以下は切り捨て、という意味です。