o-jill / ruversi

reversi program.
https://o-jill.github.io/ruversi/
1 stars 0 forks source link

探索の分担をなるべく均等にしたい #50

Open o-jill opened 2 years ago

o-jill commented 2 years ago

複数のスレッドで均等に処理を分担できるようにしたい。 今は、合法手が3手あると単純に分担が2:1になっちゃうので 3手それぞれを更に1手指した(a+b+c)手を2で割れば今よりは分担が均等に近くなるのでは?

o-jill commented 2 years ago

2手分指した枝を1本づつに分解して2束に分ける?

let mut nodes = Vec<Node>::new();
let mv1 = ban.genmove().unwrap();
for (x1, y1) in mv1.iter() {
  let mv2 = ban.genmove().unwrap();
  for (x2, y2) in mv2.iter() {
    let mut nd1 = Node::new(x1, y1, depth);
    let nd2 = Node::new(x2, y2, depth - 1);
    nd1.child.push(nd2);
    nodes.push(nd1);
  }
}

let n = nodes.len();
let node1 = Vec::from_iter(nodes[0..n/2].iter().clones());
let node2 = Vec::from_iter(nodes[n/2..].iter().clones());

// or

let mut twomoves = Vec<(i8, i8, i8, i8)>::new();
let mv1 = ban.genmove().unwrap();
for (x1, y1) in mv1.iter() {
  let mv2 = ban.genmove().unwrap();
  for (x2, y2) in mv2.iter() {
    twomoves.push((x1, y1, x2, y2));
  }
}
let n = twomoves.len();
let moves1 = Vec::from_iter(twomoves[0..n/2].iter().cloned());
let moves2 = Vec::from_iter(twomoves[n/2..].iter().cloned());
o-jill commented 2 years ago

均等になればなるほど real x 2 とuserが近い値になるはず。 今は80%ぐらいの能力しか出せてないようだ。

38 より再掲

計測してみた on vm on 9700k


time RUSTFLAGS="-C target-cpu=native" cargo run --release --features avx -- --duel --ev1 evaltable.txt --ev2 evaltable.txt.old

real 10m3.107s user 15m47.128s sys 0m14.146s

time RUSTFLAGS="-C target-cpu=native" cargo run --release --features bitboard -- --duel --ev1 evaltable.txt --ev2 evaltable.txt.old

real 9m46.265s user 15m48.323s sys 0m6.639s

time RUSTFLAGS="-C target-cpu=native" cargo run --release -- --duel --ev1 evaltable.txt --ev2 evaltable.txt.old

real 11m10.496s user 18m5.087s sys 0m6.649s

o-jill commented 2 years ago

合法手が4手あるなら4スレ(1+3)とかはどうか? 2コアのときに1スレより遅くなったり、αβ探索が絞れずに時間がかかったりしないか? 合法手1つのときは探索不要だから即指し手を返せばよいが、評価値を知りたいときにちょっとだけ時間を無駄にすることになりそう。

o-jill commented 2 years ago

オーダリングはどうしますか?

o-jill commented 2 years ago
o-jill commented 2 years ago
o-jill commented 2 years ago

測ってみた on 8265U。

time cargo run --release --features bitboard -- --duel --ev1 kifu015/newevaltable.txt.win --ev2 data/evaltable.txt

real    32m23.960s
user    53m27.750s
sys     0m18.222s

~18/22 : 0.82 -> 53/64 : 0.83~ ~ちょっとしか変わらん。。。?~

16/20 = 0.8 -> 53/64 = 0.83 15:48/(9:46 x 2) = 0.809 -> 53:27 / (32:23 x 2) = 0.825 ちょっとは上がった? 時間がかかるようになっているのは別件(#51 )なので気にしない。

o-jill commented 2 years ago

node.dump()が初手しか出してくれないのでどこかでbestのxyを入れ忘れてる。

どっちのスレッドでも起きる。 最善手を更新すると起きる。 ?更新2度目で起きている?

可能なら更新するときに旧最善手を解放したい。 その際にbestは手を記憶しているだけなので子ノードのリファレンスか何かをうまく保持しといて簡単に開放したい。

o-jill commented 2 years ago

node.child[idx]に同じ指し手が登録されているので違うノードに行ってしまっているのではないか? 同じ指し手を登録しない or bestの作りを変える。

o-jill commented 2 years ago

直ったぽいので計り直し。 7d2e703a3 直したことでちょっと速くなったっぽい。 それでもやっぱり思ってたよりは分担できてない。(分担の前準備が長いとか?)

time cargo run --release --features bitboard -- --duel --ev1 kifu015/newevaltable.txt.win --ev2 data/evaltable.txt

real    28m2.809s
user    46m59.951s
sys     0m8.388s

47/56 = 0.839

o-jill commented 2 years ago

棋譜生成の方もこっちを使うように変えてください。

o-jill commented 2 years ago

色々再測定 on 9700k。 別の要因もあるかも知んないけど

byteboard:
real 12m20.299s
user 17m40.431s
sys  0m42.764s
17:40 / 12:20 / 2 = 0.716

bitboard:
real 10m35.019s
user 15m32.142s
sys  0m34.958s
15:32 / 10:35 / 2 = 0.734

(new) bitboard:
real 14m33.178s
user 23m47.036s
sys  0m15.983s
23:47 / 14:33 / 2 = 0.817

(new) avx:
real 14m10.430s
user 23m34.164s
sys  0m8.562s
23:34 / 14:10 / 2 = 0.832
o-jill commented 2 years ago

分担は均等になったんだけど、αβカットに影響が出て探索局面が増えて結果的に遅くなっていないか? 今のソースでthink_ab()とthink_ab_extract2()で比較すればいいや。

vm on 9700k
(think_ab) avx:
real 19m43.445s
user 32m16.448s
sys  0m13.425s
32:16 / 19:43 / 2 = 0.818

(think_ab_extract2) avx:
real 14m10.430s
user 23m34.164s
sys  0m8.562s
23:34 / 14:10 / 2 = 0.832

一応効果ありそう。1.4倍速。

o-jill commented 2 years ago

棋譜生成とかにも反映した。 2850547e4 duel on ga 41:04 -> 28:42 1.43倍速 共にIntel(R) Xeon(R) CPU E5-2673 v4 @ 2.30GHz。 byteboardにも反映させますか?

o-jill commented 2 years ago

3手目まで展開するともっと良くなったりするん?

o-jill commented 2 years ago

3手目まで展開してみた。一応早くなった。 duelの結果がこれをやりだしてから変わっている気がするので見直したほうが良い気がする。

extract1:
real 36m46.838s
user 61m44.753s
sys  0m13.778s
61:44 / 36:46 / 2 = 0.839

extract2:
real 24m51.001s
user 43m42.008s
sys  0m9.544s
43:42 / 24:51 / 2 = 0.879

extract3:
real 22m36.470s
user 40m3.456s
sys  0m15.305s
40:03 / 22:36 / 2 = 0.886
o-jill commented 2 years ago

とりあえず読み筋がぜんぜん違うモノを出すようになった、その結果が正しいのかどうかは不明。 何となく正しくない気がしている。 duelをすると五分の別れに絶対なる。。

o-jill commented 2 years ago

αβの値の渡し方は大丈夫か?2手展開のときは少なくとも逆な気がする。

o-jill commented 2 years ago

2手展開で終盤が読みきれてない。絶対に何かを間違えている。

o-jill commented 2 years ago

もしかして親+複数子にしにとダメ? この探索結果を親がマージしていく感じ。今の方式だと1手目のAが2つのスレッドに分かれて探索されたときにおかしくなりそうな気がなんとなくしている。もしかしたら問題ないのかもしれないけど。

o-jill commented 2 years ago

2手展開で終盤が読みきれてない。絶対に何かを間違えている。

  1. αβ探索がバグってました。 #57
  2. 結果のマージが必要。マージをするときに最善と思われなかった手が最善に変わることがあるのであるスレッドで探索した最善手だけでなくそれ以外の手もそれなりに保持していく必要がありそう。
o-jill commented 2 years ago
o-jill commented 1 year ago

一部マージ作戦開始 意味はありそうな気がしている。 マージ後はmainもsubもツリーの初手のBestを再探索しないといけないっぽい。 マージ後にdump()の出力が初手しか出てこない。少なくとも2手目までは出てきてほしい。 HEAD(99453f3e0)はBestのxyが見つからないときはpanic!()せずに文字列生成をやめているだけのようなのでまずはそこから見直しかな?

o-jill commented 1 year ago

↑は読み筋をマージするやり方ですが、1つのツリーを育てる感じにできませんか? 3手先まで展開して展開された下のノードそれぞれの評価値がわかればあとはそれをたどる(全探索)するだけで良い。 メモリも今より少なくて済む。 そのためにはBoxかRcかArcかなにかが必要?

o-jill commented 1 year ago

新Nodeのchildは、 Vec<Arc<RwLock<Node>>>Vec<Box<RwLock<Node>>>か。 同じツリーにアクセスするけど、同じノードにアクセスすることはないと思われるのでRwLockが必要なのかどうか。 Arc自体はunsafeなのでRwLock(かMutex)があったほうが安心ではある。

o-jill commented 1 year ago

大きな1個のツリー作戦は別チケにしましょう。#62