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)
スパムお溜り (0)
ごみ箱 (11)
 リンク
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 49

454  shu  2008/04/16 22:43 id: 3BVR6NRi4pQ  prob: 0.2%
性能だけ考えてます(爆
申し訳無い。(>>451, >>452) の記事は人を惑わすだけだと思いました;;
実際、今私の脳内が混乱してます(笑

[モデル-1]
局面集合を辞書 S{キー値、局面情報} で持ち、局面探索機能は一個のオブジェクトが持ちます。
XOR 演算を利用すると、ある局面 Si から次の局面に遷移するには乱数 Ri を用いて、
Si+1 = Si ^ Ri で済みます。乱数 Ri はあらかじめ計算して置くことができるので、
うまく値を設定すれば S1,2,....n が広く分散し、辞書のキーに使えるのではないかと云うこと。
つまり、Ri の選択と Si ^ Ri 演算だけで高速にノード間を渡り歩くことができると云うことらしい。

この場合、たとえばキーを 64bit 局面情報を 64bit とすると、一億局面を収めるには、
(64 + 64) * 100,000,000 = 12,800,000,000 = 12.8Gbit = 1.6GB 必要になる。
そして同一局面であることを判断するには局面情報の比較が必要となる。

[モデル-2]
ひょっとしてキーで局面も表現できるのではないかと考えました。
そうすれば局面集合は S[キー値] の配列で表現できます。

例えば玉を K11→K22 と移動するとき、K11→K12→K22 と K11→K22 を考えてみます。
ここで R(11,22) = R(11,12) ^ R(12,22) とすれば
K22 = K11 ^ R(11,12) ^ R(12,22) と K22 = K11 ^ R(11,22) は同じことです。
てことで乱数をうまく設定できるのならばキー値は局面を表すことになり、
1) 配列要素に局面情報は入れずノードの状態のみ2bitで表すとすれば一億局面25MBですむ。
2) 同一局面であることを判断するにはキー値を直接比較すれば良い。
なんて都合の良いことを妄想していました。てことで、あくまで妄想です。。。(孟宗竹は美味い^^)
453  pon  2008/04/16 12:52 id: d76s68gzUHc  prob: 2.7%
同一局面の話し(なら):性能無視のとき(勘違いしてるかも^^;)
/** 局面PGm == 局面PGn ?
 *  40 * 40 = Max1600 loop
 */
Iterator it = PGm.getPieceList().iterator();
for(it.hasNext()) {
    if(!it.next().isEqual(PGn)) {
       break;    //等しくない
   }
}
// Piece.isEqual()
protected boolean isEqual(PG target) {
//TO DO 駒の比較項目
//   手番、種類、成り有無、位置(x,y:駒台時は0,0)

}
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)

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

実装として一億手余りまでは馬鹿読みながら可能なことは確認できました (いや驚いたね;;)。
数年後には一秒で一億と四手を読むことが現実になるのだろうなぁー