象歩将棋

466 shu 2008/05/18 22:14 id: 3BVR6NRi4pQ prob: 0.0%: 流鏑馬二番が解けない
これは持ち駒情報を持っていないため。
(久しぶりに試してます;;)

20〜24ビットに丸めたハッシュキーのコンフリクトは探索局面の 0.1% くらいなのに対し、
同一盤面(局面の持ち駒を考慮しない)のヒットは探索局面の半分くらいに発生する。
持ち駒はハッシュキーに含める方法もあるけど、
同一盤面であることの情報も欲しいので、キーには入れず値の方に持つことにする。

持ち駒は32ビットで十分表現できる。(現実には玉Kは不要)
?.....P...L...N...S...G..B..R..K
00000000000000000000000000000000
引き算が必要になる場合は、引かれる方の各先頭ビットを立てれば良いだろう。
01000001000100010001000100100100

参考サイト:
http://ameblo.jp/professionalhearts/entry-10003663090.html
http://www.emit.jp/prog/prog_b.html

465 shu 2008/05/03 23:13 id: 3BVR6NRi4pQ prob: 0.1%: そろそろインタフェースの準備
python の ctypes モジュールを使うと楽できそう。
http://blog.goo.ne.jp/anoydevl/e/a1193ca3cafed036c8c232ac4a1...
http://ymasuda.jp/python/ctypes/tutorial_jp.html

C++ クラスの wrapper 関数をこしらえた後、
$ python2.5
>>> import ctypes
>>> so=ctypes.CDLL("./libCShogi.so")
>>> ob=so.cshogi_create()
CShogi:: new
>>> so.cshogi_hello(ob)
CShogi:: Hello, CShogi!
>>> so.cshogi_delete(ob)
CShogi:: del
>>>
簡単だぁ (^^;

464 shu 2008/05/02 23:07 id: 3BVR6NRi4pQ prob: 1.2%: > 再帰探索処理をデータ保存クラスと探索処理クラスに分離
探索モジュールをじっと見る
すると脳内で再帰処理のシミュレーションが始まる。
しだいに脳が再帰処理と同化して行くのが分かる。
たとえば処理の一部を変更しただけですべてが変わる。
まさかフェルンデクライス・メソッドとかに通じるものがあったりするのだろうか。
http://lightson.dip.jp/blog/seko/1610

正確に処理を記述するには状態遷移表とかを書くのが定跡なのだろうが、
今回は紙と鉛筆を禁止してるので、しばらくは脳内で遊ぶことにしよう。

463 shu 2008/04/30 21:49 id: 3BVR6NRi4pQ prob: 0.4%: 亀の歩み
再帰探索処理をデータ保存クラスと探索処理クラスに分離、
ツリーの三色塗り分け問題にまでは到達できた。
反復深化法での処理を組み込み中。
4,716行

462 shu 2008/04/24 21:55 id: 3BVR6NRi4pQ prob: 0.0%: 盤面の圧縮値
今回のプログラムは盤面のビットマップを常に保持してるので、安直にそれを再利用。
手順のハッシュと局面のハッシュは交差するのではないかと云う願望です。
# 実はそれらは同じものだったなんて結論。ってことはなかった。

駒の配置は9x9x2ビット空間に収めてあるので、OR演算で四つ折りに畳み込んで5x5=25ビット。
今のところ良く働いてるみたい。だけど下位8ビットだけ取り出しても結果に変化は無いようです;;
Zobrist ハッシュキーの方が良くできてるので、盤面値の出来はあまり関係無いのかも。
わたしゃ数学的評価はできめるせんぬ;;

Zobrist キーを利用した探索では異なる局面を同一と判断する可能性が(わずかでも)常にあるので、
詰め手順を求めた後に検算するとか、うまい方法を考えないといけないのであろう。
ここにも「手の発見」と「手の評価」と云うテーマが現れる。

461 shu 2008/04/24 20:55 id: 3BVR6NRi4pQ prob: 0.1%: > 459 なんかハッシュの効率悪そう。
Zobrist キーは高効率でした;;
単純な同一局面判定処理を追加して試したところ判明。
嘘ついてごめんなさい m(.".)m

たとえば、以下は「無双一番」を13手まで馬鹿読みした結果。
探索局面総数: 28,483,070
未解決局面数: 12,088,478
ハッシュ配列のサイズ: 16,777,216
ハッシュ配列の利用数: 7,585,301 (45.21%)
同一索引・同一局面数: 20,896,372
同一索引・相違局面数: 1,397

ハッシュキーの配列が50%近く埋まってきてもコンフリクトする確率は小さい。
そして重複局面が多いのは千日手模様の繰り返しからなる局面が原因らしい。
とすると、そろそろノードの判定値を保存して反復深化処理を試してみても良さそう。
現在のソースは 4,496 行。

460 shu 2008/04/23 21:21 id: 3BVR6NRi4pQ prob: 0.0%: 局面ハッシュも必要かな
指し手のハッシュキーはかなり重複があります。
11手詰めくらいでも約半分重なっています。
本当の恩恵を授かるのはまだ先のことなのでしょう。

局面ハッシュ併用した場合、キーの重複はかなり減るか?
それならば残ったものは探索処理を利用して同一局面判定すれば良いと思う。
心配なのは本来同一局面は頻発するものではないかと云うこと。
この辺は試してみないと私には解りません。

無駄な合駒処理のためには、持ち駒情報も必要になりそうです。
とりあえず正攻法で考えてるつもり。

459 shu 2008/04/22 22:22 id: 3BVR6NRi4pQ prob: 7.3%: なんかハッシュの効率悪そう。
ツリー探索自体はまあ高速にできるので、注目すべきは同一局面の判定かなー
あーだこーだと夜もふける。
考え処ですね;; 長考宣言...

458 shu 2008/04/20 22:43 id: 3BVR6NRi4pQ prob: 0.0%: だんだん解って来たかも
乱数は駒移動じゃなく、ある位置の駒の追加/消滅で作るのだろう。
それなら同一局面で同じハッシュキーになりそう。
{局面が同じ=>ハッシュ値が同じ} ならロジックを作れる。

一方、局面のインデクスは情報を落とさないで45バイトで実装した。
局面←→索引の変換は、とりあえずそれで良しとしよう。
この辺は性能に影響するので下手な圧縮はできない。(アイディアが無いとも云う)

しばらくはハッシュ値の評価をしてみようと思う。

457 shu 2008/04/17 22:31 id: 3BVR6NRi4pQ prob: 0.5%: > 充分コストするはず
とりあえず局面情報作成からかな。
普通のhashクラスを作り、試しに局面を文字列化したものを登録してみた。
"無双第一番"で11手目まで探索すると、
探索局面数: 4,057,922
重複登録数: 2,173,987
やはり探索の途中でも半分は重複局面。

てことで、
1) 局面→索引→圧縮キー
2) 探索ノード→ノード空間管理クラス
3) ノード探索処理
まで実装すれば全幅探索ができる。後はその結果を見て考えることにしよう。
また、この辺は丁寧にこしらえて損は無いところ。

> あと20年もあれば、美しさを堪能できるのですが
かの大国の大統領は現世で美を堪能なされてるようです;;