HOME | ドキュメント |  ブログ  |  BBS  |  瓦版  | 将棋プロジェクト |  物置小屋   

ドキュメント 象歩 Web瓦版
 BBSボード RDF
こんにちは (23)
おためし板 (321)
質問箱 (94)
テスト (0)
建築 DIY (7)
MTB (34)
(13)
節電対策 (2)
このサイトに関する話 (182)
Linux (396)
PC用ハードウェア (10)
Vine Linux 野良系 (68)
PC 工作 (31)
BBS の改良 (105)
Vine Seed (520)
Zope とプロダクト (95)
Web の利用技術 (131)
DB とファイルシステム (63)
Python と C/C++ と... (29)
Zopeプロダクト開発メモ (3)
UTF-8 化 (42)
Mail 環境 (8)
COREBlog (109)
Zope3 (51)
Windows 64bit (18)
Mac (2)
Squeak スクイーク (67)
Django ぶらり一人旅 (3)
64bits (52)
Mono 思いにふける (13)
ディスクトップ (4)
象歩将棋 (477)
将棋よもやま (207)
サイトのデザイン (31)
心配な話 (67)
うそ (22)
昔のゲストブック (20)
ボート部 (95)
鶴南六組 (2)
Web 日記 (202)
 スパム
逮捕しる (0)
スパムお溜り (6)
ごみ箱 (13)
 リンク
kiyoさんのサイト
ペンタ郎の漫漕ブログ
TIT漕艇部の練習動画 @YouTube
墨堤の雄 @FaceBook
ペンタ(五大学ミドル) @FaceBook
Facebook
Vine Seed パッケージビルド状況
Vine Linux パッケージ情報
VineLinux バグトラッキングセンタ
VineSeed 開発用 Trac
VineSeed Specs
RPMパッケージの作成方法
Linux Standard Base
Planet Vine
Vine Linux ユーザーフォーラム
Vine Users ML アーカイブ
VineSeed ML アーカイブ
twitter#VineLinux
勝手に将棋トピックス
詰将棋おもちゃ箱

象歩将棋

Webと将棋で何か具体的なもの作って行こうとしてます。


全475件 - 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
452  shu  2008/04/15 23:01 id: 3BVR6NRi4pQ  prob: 27.6%
ハッシュキーは局面を表さないといけない。
たとえば無双一番を11手探索した時点で、未解決局面が 1,747,982 個、
そのうち重複してるのが 949,725 局面ありました。
さらに深い探索をすると約半分のノードの探索は無駄ということになる。
探索局面の重複をすぐに判別できないなら意味が無い。

ハッシュキーを生成するためには、
1) ある駒を x あるいは y 方向に移動する場合のランダムな自然数 R(x), R(y) を決める。
2) x,y 同時に移動する場合は R(x,y) = R(x) ^ R(y) とする。
3) 上記乱数を(成)駒の種類と成りについて各々求める。
4) 駒を獲得する場合、XOR演算工程を1ステップ追加。
5) 駒を打つ場合も別。
かなり大雑把ですが。
451  shu  2008/04/14 23:18 id: 3BVR6NRi4pQ  prob: 3.7%
ツリー探索はやはり Zobrist 利用?
ゲーム木では定番のセオリらしい。
http://fragrieu.free.fr/zobrist.pdf
http://mm.cs.uec.ac.jp/doc/ipsj2002.pdf

大量の局面を配置するのに便利なのだろう。
前後の局面アドレスがすぐに求められるので、高速ツリー探索に使えるのだと思う。
そう言ってもまだ理解してるわけではありません。

ハッシュキーは局面を表すものでは無いので(たぶん)、
同一局面のヒットはまた別に考えないといけないのかな。
大量のメモリを消費するのが気になる。

$ python
>>> s0=0
>>> n1=1
>>> n2=2
>>> n3=4
>>> s3 = s0^n1^n2^n3
>>> s3
7
>>> n3^s3
3
>>> n2^n3^s3
1
>>> n1^n2^n3^s3
0
450  shu  2008/04/10 21:03 id: 3BVR6NRi4pQ  prob: 1.4%
作戦を継続するには一筆書きでは困難。
ノードをばらし評価関数導入することが必要になります。
処理速度は一億手/100秒くらい出てるので計算する手数を減らす戦略。

ひとつのノード {手、評価値、上位へのポインタ、局面コンテキスト} で 24byte 必要。
とすると直線的には一億手で約 2GB くらいのメモリが必要ですが。Φ
449  shu  2008/04/08 21:47 id: 3BVR6NRi4pQ  prob: 0.1%
プロローグ
詰将棋も平手将棋と同じく無限性を考慮すれば、
詰む確率、詰まない確率の評価が重要なのでしょう。

今回はビット演算を利用して実装してみましたけれど、
ロジックは C++ ソースコードの中に直書きされて居るので、発展性がありません。
とはいえ内部処理は集合演算そのものなので汎用化する道はあります。
たとえば必要な要素をプリミティブなオブジェクトなり演算子として実装し直すとか。

サンプルとして、詰みが成立する局面のことを考えてみると、
--
1) 攻め駒が一枚だけで詰みとなる場合は、
  必要条件: K ⊆ *Br
    (玉 K には攻め方の駒 Br が利いてること)
  十分条件: ?K == φ AND (K...Br] ⊄ Σ*Wi
    (玉 K は移動できない、かつ攻め方の駒 Br までの範囲に玉方の駒が利かないこと)

2) 攻め駒が二枚以上で詰みとなる場合は (1) に加え
  必要条件: K ⊆ *Bx AND Bx ⊆ *By
    (玉 K には攻め方の駒 Bx が利いてる、かつ Bx に味方の駒 By が利いていること)
  十分条件: ?K == φ AND (K...Bx] ⊄ Σ*Wi (ただし Wi は K を含まない)
    (玉 K は移動できない、かつ攻め方の駒 Bx までの範囲に玉以外の玉方の駒が利かないこと)

# K は位置、*K は利き位置の集合、?K は移動可能位置の集合を意味します。
# 正確でも厳密な記述でもありませんので、余計なことで悩まないでください。(空き王手ははぶいてるし)
448  shu  2008/04/07 21:42 id: 3BVR6NRi4pQ  prob: 1.8%
速度の比較
参考までに詰パラ二月の懸賞問題で実行してみた。
Pentium4 2.8EG:  5.30 秒
Athlon64x2 3800: 1.05 秒
Athlon64 3700+:  0.95 秒
(1,095,025 局面)
残念ながら、現在のWEB鯖 (Pen3 800EB) に乗せるのは無理みたい。
ならば当面 Athlon64 3700+ を将棋鯖に改造するしかないかの。
447  shu  2008/04/06 22:32 id: 3BVR6NRi4pQ  prob: 0.7%
たどり着いてやはり麓
先手は"詰むや"の評価が必要。
後手は"詰まざるや"の評価が必要。
今はほとんど使って無いメモリの有効利用が扉を開く鍵となるのであろうか?
たとえば、先後の候補手が 1/3 の範囲に収まるだけで極めて効率が良くなるのは想像できる。

http://www.geocities.jp/k_7ro/
http://www005.upp.so-net.ne.jp/tsumepara/contents/4appre/mc/...
その過程でミクロコスモスが解ければ嬉しいとは思うけど、
本当の敵はポン能寺なので、うまく立回らないといけない。
446  shu  2008/04/06 21:28 id: 3BVR6NRi4pQ  prob: 0.1%
二歩と打歩詰ルールを追加。
千日手や無駄な合駒は探索中に考えれば良いことだし、
そもそも正解手順には現れない(ように設定できる)。
また持将棋ルールは詰将棋に関係ない。
と云うことで必要なルールはすべて実装できたみたい。
ソースは C++ で 3,840 行。
445  shu  2008/04/05 21:36 id: 3BVR6NRi4pQ  prob: 0.3%

無双第一番が解けない。
カンニングして正解手順を6手進めたところから探索。

▲3三竜 △5二玉 (正解は同玉) ▲5三金 △同桂 ▲同角成 △4一玉
▲3二竜 △同玉 ▲3一飛 △2三玉 ▲2一飛 △3二玉
▲2四桂 △2一玉 ▲3三桂 △1一玉 ▲1二香までの17手詰め (+6手)。

100,147,641局面 / 110秒 (消費メモリは約1MB)

やはり手の優先順位の影響が大きいようです。たとえば攻め方は成る手を優先するとかはあたりまえですね;;
案の定、喜びの次の日には厚い壁が立ちはだかってましたが、これでやっと扉をさがす旅に出られます。

実装として一億手余りまでは馬鹿読みながら可能なことは確認できました (いや驚いたね;;)。
数年後には一秒で一億と四手を読むことが現実になるのだろうなぁー
444  shu  2008/04/04 21:25 id: 3BVR6NRi4pQ  prob: 0.1%
詰将棋パラダイスの作品で試してみた
三月の懸賞詰将棋 (江部健氏作)
http://www005.upp.so-net.ne.jp/tsumepara/
11手詰め: 357,723局面/0.408秒
左に逃して詰めたのはご愛嬌;;

二月の懸賞詰将棋 (岡部雄二氏作)
http://www005.upp.so-net.ne.jp/tsumepara/contents/3problem/p...
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#nank...
http://www.ne.jp/asahi/tetsu/toybox/kenkyu/cho1999-9.htm
443  shu  2008/04/03 23:10 id: 3BVR6NRi4pQ  prob: 2.0%
ツリー探索を試してみた。
題材はいつもの「流鏑馬一番」七手詰めです。
局面生成、{局面コピー、ツリー探索} を繰り返して、約 1,000 回 / 秒。

一回の探索で 1,600 局面くらい現れるので、推定 160 万局面 / 秒。
詰将棋なのでやや不満な数値ですが、初回としてはまずまずですかね;;
消費メモリ 1〜2MB、ソースコード 3,789 行。
パラレルワールドに少し期待してる。
全475件 - 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48