象歩将棋

402 shu 2007/10/27 23:29 id: 3BVR6NRi4pQ prob: 0.3%: 王様はブランチ
詰将棋の手は王手かどうかの単純な判定なので、やはりビット演算が有力な手段だと思う。
玉側の手の広さなどを考えると、どうしてもビットマップで一括処理したくなる。
そして汎用ロジックを考える前に、詰将棋のような特殊なケースでの練習も必要。
試しに考えて見ることが役に立たないことは無いだろう。

401 shu 2007/10/26 22:41 id: 3BVR6NRi4pQ prob: 0.8%: > お疲れ
一応まとめ (備忘録ですスマソ)

下↓は現状のプロファイル出力です

  処理%  (積算%)  クラス::メソッド
A ----------------------------------------------------
  28.41% (28.41%) CMoveList::addMove(CMoveSet&)
  24.42% (52.83%) CMoveSet::getLongPath()
  22.61% (75.44%) CMoveSet::getShortPath()
B ----------------------------------------------------
   9.00% (84.44%) CMoveSet::setPiece(CPiece const*)
   7.43% (91.87%) CTraceMove::getMoveList(CMoveList&)
C ----------------------------------------------------
   8.13% (100.0%) その他
  ----------------------------------------------------

Aランクの処理はすべて移動可能手の抽出(CMoveSet)と保存処理(CMoveList)です。
現在バイト単位で可能手を判定してますが75%以上の時間を費やしています。

400 pon 2007/10/25 12:39 id: A/fyyNdvqVo prob: 0.4%: 400GET
> このへんで作業はちと一休みします
お疲れ様でした＾＾
私も正月まではここを見るだけです。

399 shu 2007/10/24 22:24 id: 3BVR6NRi4pQ prob: 0.5%: > なんとか1秒/1M局面くらいにならないかな
成りました
可能手44手リストアップするのに 0.92秒/100万
# 環境は Athlon 3700+ linux x86_64 メモリ1GB
# ソースコード 1445 行、バイナリ 237,551 バイト

王手の判定メソッドなどを作るだけで、このまま詰将棋を解くプログラムは作れるかも。
でもいろいろ事情があるので、このへんで作業はちと一休みします。ごめん。

398 shu 2007/10/23 22:39 id: 3BVR6NRi4pQ prob: 0.0%: プロファイリング
平手で少し進んだ局面。44手抽出に2秒/100万も時間を費やすので
$ gcc -p ...
結果は広く分散しちまってABC分析も使えない結果に。

いろいろ統廃合して再度測定してみると問題は数個のメソッドに収斂。
有効手を調べる処理に約70%の時間を費やしている。
盤面→駒セット変換に10%、手の保存に20%。
ちなみに、この辺のコードの改造はC++とvi環境ならそんなに苦にならない。

今はなんとか1秒/1M局面くらいにならないかなーって気分。
>397 悪い人はいません
でも食えないかも;;

397 pon 2007/10/21 20:38 id: A/fyyNdvqVo prob: 1.5%: >http://www.nminoru.jp/~nminoru/programming/bitcount.html
Version5はすばらしいですね
こういう所で心が動く人に悪い人はいません

396 shu 2007/10/16 22:57 id: 3BVR6NRi4pQ prob: 0.8%: リファクタリング
ようやく基本ルールでの可能手抽出処理を整理できました
たとえば以下のようなコードになります
---
    CPieceMoves moves(手番、局面)
    CMoveList mlist;
    const CMove* p = moves.next();
    while (p) {
        mlist.add(p);
        p = moves.next();
    }
---
後は CMove インスタンスを評価するだけ
ちなみに 15 手抽出に 0.7秒/100万 (二歩、王手関連などはまだ含まない)

とりあえず普通のロジックで済ませてます＆スレッドセーフ
まだ以下のような世界は怖いので踏み込んでいません
http://www.nminoru.jp/~nminoru/programming/bitcount.html
http://www.amazon.co.jp/gp/product/product-description/44340...

395 shu 2007/10/15 20:20 id: 3BVR6NRi4pQ prob: 0.1%: 棋譜ブラウザ 0.5.5 for Win
ftp://owa.as.wakwak.ne.jp/pub/shogi/windows/
明日から第20期竜王戦なので負担にならないように If-Modified-Since 対応版です

サイトにはもう盤駒が用意されてるようです。
http://live.shogi.or.jp/ryuoh/kifu/071016.kif
試してみたところ、二回目でちゃんと 304 Not Modified が返って来ました。

と言いながら、まあ本当の竜王戦サイトや 2ch で鑑賞された方が楽しいとは思いますけど;;
http://live.shogi.or.jp/ryuoh/
http://www2.shogi.or.jp/live/

394 shu 2007/10/13 14:53 id: 3BVR6NRi4pQ prob: 2.6%: > 木を見て森のような
うまいね^^
でも、まだツリーまで行ってませんから;;

ちなみに 96byte/局面、1,000,000局面/秒くらいは行けそうな予感
詰将棋の完全ツリー探索だと一秒以内で解けるのは 15 手詰めくらいまでかなー

> 思考を打ち切るロジックが先
御意

393 pon 2007/10/13 10:54 id: A/fyyNdvqVo prob: 1.0%: >駒一個で一手詰めは確かに存在するけど三手詰め以上・・・
>詰みが無いならロジック判定部分で少し得
さすが！
するどいですが、木を見て森のような・・
その局面にたどり着いた場面では、思考を打ち切るロジックが
先に動くことになりそうですね^^;