象歩将棋

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

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年もあれば、美しさを堪能できるのですが
かの大国の大統領は現世で美を堪能なされてるようです;;

456  pon  2008/04/17 12:27 id: .T8utNC06Zk  prob: 0.9%

>454
いえ、そうだと思ってました。
人類がまだパイの計算にてまどっていることを考えれば
性能の制約は充分コストするはずです。＾＾

>455
メルセンヌは確か素数で有名な人ですよね。
修ちゃんが数学を知っているとは知りませんでした。m(__)m
時間があと20年もあれば、美しさを堪能できるのですが・・・

455  shu  2008/04/16 22:57 id: 3BVR6NRi4pQ  prob: 24.6%

メルセンヌ・ツイスタ
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt64.html
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index-j...

良い乱数・悪い乱数
http://www001.upp.so-net.ne.jp/isaku/rand.html

XorShift
http://www.jstatsoft.org/v08/i14/
unsigned long xor128(){ 
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; 
    unsigned long t; 
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); 
}
#備忘録

454  shu  2008/04/16 22:43 id: 3BVR6NRi4pQ  prob: 0.4%

性能だけ考えてます(爆
申し訳無い。(>>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: .T8utNC06Zk  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: 31.9%

ハッシュキーは局面を表さないといけない。
たとえば無双一番を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: 5.0%

ツリー探索はやはり 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