速度の比較
参考までに詰パラ二月の懸賞問題で実行してみた。
Pentium4 2.8EG: 5.30 秒
Athlon64x2 3800: 1.05 秒
Athlon64 3700+: 0.95 秒
(1,095,025 局面)
残念ながら、現在のWEB鯖 (Pen3 800EB) に乗せるのは無理みたい。
ならば当面 Athlon64 3700+ を将棋鯖に改造するしかないかの。
象歩将棋
Webと将棋で何か具体的なもの作って行こうとしてます。
たどり着いてやはり麓
先手は"詰むや"の評価が必要。
後手は"詰まざるや"の評価が必要。
今はほとんど使って無いメモリの有効利用が扉を開く鍵となるのであろうか?
たとえば、先後の候補手が 1/3 の範囲に収まるだけで極めて効率が良くなるのは想像できる。
http://www.geocities.jp/k_7ro/
http://www005.upp.so-net.ne.jp/tsumepara/contents/4appre/mc/microc.htm
その過程でミクロコスモスが解ければ嬉しいとは思うけど、
本当の敵はポン能寺なので、うまく立回らないといけない。
二歩と打歩詰ルールを追加。
千日手や無駄な合駒は探索中に考えれば良いことだし、
そもそも正解手順には現れない(ように設定できる)。
また持将棋ルールは詰将棋に関係ない。
と云うことで必要なルールはすべて実装できたみたい。
ソースは C++ で 3,840 行。
無双第一番(12手詰め)が解けない。
カンニングして正解手順を６手進めたところから探索。
▲３三竜 △４二玉 (正解は同玉) ▲５三金 △同桂 ▲同角成 △４一玉
▲３二竜 △同玉 ▲３一飛 △２三玉 ▲２一飛 △３二玉
▲２四桂 △２一玉 ▲３三桂 △１一玉 ▲１二香までの１７手詰め (+６手超過)。
100,147,641局面 / 110秒 (消費メモリは約1MB)
やはり手の優先順位の影響が大きいようです。たとえば攻め方は成る手を優先するとかはあたりまえですね;;
案の定、喜びの次の日には厚い壁が立ちはだかってましたが、これでやっと扉をさがす旅に出られます。
実装として一億手余りまでは馬鹿読みながら可能なことは確認できました (いや驚いたね;;)。
数年後には一秒で一億と四手を読むことが現実になるのだろうなぁー
詰将棋パラダイスの作品で試してみた
三月の懸賞詰将棋 (江部健氏作)
http://www005.upp.so-net.ne.jp/tsumepara/
11手詰め: 357,723局面/0.408秒
左に逃して詰めたのはご愛嬌;;
二月の懸賞詰将棋 (岡部雄二氏作)
http://www005.upp.so-net.ne.jp/tsumepara/contents/3problem/pastpb/atop.htm
11手詰め: 3,697,597局面/4.412秒
サンプルコード:
...
GShogiApp g("P43P31G33p35K12P14~RBS3N4L4Pd/R42S32P23~BG3");
const CDiagram& d = g.getDiag();
GPuzzle z(d);
z.solve(11);
...
出力結果:
P2223+ K2212 G12 K1222 B34 R23 G22 K2212 S2332+ K1122 G12
合駒の優先順序が高いので;;
処理の不備は今のところ多いけど、基本的に使えると思う。
いろんな作品で試したくてワクワクしてきました。こらえ切れずに ＼(^o^)／ヤッター
http://toybox.tea-nifty.com/memo/2005/05/post_3535.html#nankai
http://www.ne.jp/asahi/tetsu/toybox/kenkyu/cho1999-9.htm
ツリー探索を試してみた。
題材はいつもの「流鏑馬一番」七手詰めです。
局面生成、{局面コピー、ツリー探索} を繰り返して、約 1,000 回 / 秒。
一回の探索で 1,600 局面くらい現れるので、推定 160 万局面 / 秒。
詰将棋なのでやや不満な数値ですが、初回としてはまずまずですかね;;
消費メモリ 1〜2MB、ソースコード 3,789 行。
パラレルワールドに少し期待してる。
リファクタリング
今は一局面をいろいろ静的に400ビットくらいで持ってます。
それとは別にツリー探索処理の途中、動的に200ビット/局面くらい消費しています。
無駄をはぶいて、なんとか100ビット以下にしてみたのだけど、なぜか不安な気がします。
別に余計なことしてるとは思わないけど、
ほんとうの私は、実はプログラマに向いて無いんじゃないかと思う?;;
空き王手
手の抽出はビット演算を利用するとロジックがとても簡単になる。
実装したところパラレルワールドなのでループ制御文がほとんど無い。
今夜あたりツリー探索を作れば、うんと速い詰将棋マシンができるだろう^^
と思ったところで、また悪魔の囁きが聞こえてきた。
やはり抽象的なモデルが必要なのではないのかな。
心の中で誰かがそう叫んでる。でんでん;;
いろんな見方を得たい時にはなるべくシンプルなモデルの方が便利。
それはまたクロスでデバッグやテストするにも都合が良いのだ。
後手番
まだツリー探索すら考えて無くて、今は地道に手の抽出処理をしてます。
図は▲６四角の局面
後手番で△４二歩打、△５三歩打、または△４二金を抽出できました。
盤面以下むりやり △４二金、▲４一銀成と進め、
その局面で探索すると無事に △４一銀のみ抽出できました。
もしかして空き王手関連はうまく処理できてるのかもしれません。
後手番の処理は以前 (PyZumeのころ) は先手の処理より一桁多くなっていましたが、
今回は先手の倍くらいですみそうな気がしてます。
空き王手の処理完了
現在2500行、次は後手番。
葛湯溶いてるみたい。始め粘って、あとはさらさら。