chokudaiのブログ

chokudai（高橋直大）のブログです

TopCoder Open 2014 Round1 参戦ログ2

1からの続き

 4/15(6日目)

6:41

ビームサーチ、バグっていた。複数ターン進んだ状態でも、÷ステップ数で処理してしまっていた。直したら凄く楽しいことに。

nが8のケースで1割程の改善。nが9のケースで5%ほど改善。その他ボロ負け。なんぞこれ。

・・・・もしかしてこれ、サイズによってアルゴリズム変えないといけない奴？マジ？

7:08

これ評価関数の調整したら伸びる奴だ！

7:30

ビームサーチ先生舐めててすいませんでした

でもn>=15でやっぱり間に合わないんですがどうにかなりませんかねビームサーチ先生

8:12

仕方なく評価関数をガンガン削って行ったら、高速化の恩恵でスコア上がりまくって泣いてる

8:29

で、ビームサーチで5%伸びたよ。そこまではいいよ。そこからどうするかが問題だよね。C++使った高速化がどれくらい早くなるのか読めないから困ってる。

8:41

本番サーバーだと3%も伸びてない。つらぽよ。

11:18

C++に書き換えたらローカルだとむしろ遅くなってるのになんか1.5倍くらい早くなってるじゃねえか。なんだよそれ。しらねえよそんなん。ばーかばーか。

11:32

ってことはこれあれでしょ？評価関数をもっと差分ベースにしてもっと軽くして、探索速度を上げて、ってゲームでしょ？何やそれ。何やそれ。何やそれ！楽しくない！

 

13:19

高速化よくわかんない（弱

 

13:42

残してるもの

  • 2*2のブロック内にある同じ色の数ごとに対する点数 {0, 0, 300, 700}
  • 1回で消せるか否か　800
  • block3に隣接するblock3　1500
  • 消せた点　4500-5500

消しちゃったもの

  • block3に隣接するblock2 100
  • block3に隣接するblock2が同色　-400
  • Sに対する減点 -200 (2重にかかる)
  • Tに対する減点 -400
  • +に対する減点 -1600

STくらいは高速にできそうだし復活させたいなぁ

14:22

復活させたら単純にスコアが落ちた。どうなっとんねん。評価関数迷走し過ぎや。

14:23

ちょっと時間を計ってみた。ローカルで全部で14s

評価関数：　2182ms

(評価関数を含む全状態のinput部分 3828ms)

経路探索：　8134ms

どう考えても高速化するべきは経路探索部なので、そこを高速化する。ここ頑張るだけで倍くらいまでは目指せそうだ。

15:40

なんか大半のケースで、block3以外を無視した探索した方が早いことが発覚していて、がびーんってなっている。がびーん。

15:45

気のせいだった。早くなりすぎてそんな錯覚をするレベルだっただけだった

16:29

なんか高速化してテストしたら7%くらい早くなっていて、C++でがっつり高速化するの超強いなー、チートやなー、と思っている。

17:13

941kで4位まで戻した。一時期820kの9位まで落ち込んだので、まぁ何とか立て直したと言えるかな・・・。ただ1位の点数は全く削れず。これはかなり差があるなぁ。

あと、ローカルで実行したところ、3つがエラー吐いて落ちてる。なんぞこれ。

17:55

ようやくバグ発見。長さ4の経路を探すとき限定のバグだった。そんなん知るかよ・・・ｗ

19:04

バグ取りと係数調整で15000点アップ。956k

１位が986kだからあと30kなんだけど、この状況で1点も削れていないってのがもうねもうね・・・ｗ

19:37

0.3%とかの細かい評価関数の最適化をしている。この辺colunさんのプログラムとかだと自動でやってくれるんだろうなーって考えると凄く羨ましい。

Example scores:
0) 13167.0
1) 17398.0
2) 11847.0
3) 16053.0
4) 9924.0
5) 17390.0
6) 18404.0
7) 13280.0
8) 13195.0
9) 13062.0

スコアもだいぶ伸びたなぁ。最初のころと全然違う。

 

20:05

「直前に消した場所が同じ」場合を「似たようなケース」として、似たようなケースに偏ったら弾く、みたいなアルゴリズムを入れてみたけどほぼ変化なし。類似局面はないと思っていいのかな・・・。

chokudai-search使って多様性チェックするのもありだなぁ、とちょっと思ったけど、普通にbeam-search使うより絶対性能落ちるからあんまりやりたくないｗ

回数が少なすぎるから多様性とか言ってられない・・・。多くなったっていっても１ターン５つとかそのレベルだからねえ・・・。

 

20:17

color=6のケース、探索範囲を1つ長めにしていたのをカットしたら、color=6のケースだけ5%近くアップ。なんかこういう下らないの多いなぁ・・・ｗ

 

20:58

ちょっとだけ高速化入れて提出。975k。1位まであと12k。この12kが遠い。

23:09

色々早くした。多分1位は抜けるはず・・・。抜けるよね・・・・？

自信がないから27000ms -> 28500ms これはずるいなぁ・・・ｗ

23:40

やっと１位奪還。長かった・・・。　記念撮影しとくｗ

Gyazo - ee569f2dcfc4a890dec9f316a9d673e3.png

4/16(7日目)

5:38

700点抜かれてるｗ

8:38

係数調整をしよう。今回はあんまり類似局面排除をしなくても良いように感じるので、貪欲調整を使おう。

※貪欲調整とは→造語。ビームサーチなどで使う評価関数を決定する時に、実行時間で制御すると、時間がかかる上にマシンの状態に左右されたりする。それを防ぐために、「貪欲法」や「ビーム幅１のビームサーチ」などの結果を使うことにより、高速に多くのケースで性能を試すことが出来る。評価の種類によっては、類似の局面ばかり上位に来てしまうような評価になり、貪欲調整で結果が良くても、ビームサーチに適用すると評価が悪い場合もあるが、大半の場合で有効。

8:52

３以下の局面しか見ないとか、色々無理な枝刈を入れてる影響で、あんまりうまくいかないから固定調整に切り替える。

※固定調整とは→造語。貪欲調整で上手くいかない場合に使う調整法。通常より小さい定数の試行回数で調整を行う。ビームサーチの場合は、通常より小さい定数ｋをビーム幅とすることで高速に調整を行う。（自分は３でやることが多い。多様性が問題になる場合はNに依存させたり）

10:41

これ固定調整もダメな奴だわ・・・ｗ

「１つ消す」ことの価値って、取れ得る期待スコアによって変動するものなので、高速だと当然低スコアになってしまう都合上、上手いこといかない。

ついでに、なんか色数が多い場合に関しては、「良い状態」を頑張って作ろうとし過ぎちゃうせいで、そこが崩せず詰んじゃう、ということまで発生。貪欲法だとそこまで「良い状態」は作れないんだけど、ビーム幅がでかいと作れちゃう。ぐぬぬ。

ってことで調整が無駄に。そして１位とまた17k差の2位に。くー、やっぱ強いなぁ。

 19:22

3位転落したところで、どうやってスコアを上げるかについて考えるよー！１位とは17k差！

  • 大前提

ビームサーチを使う、という点においては、もう確定で良いと思う。根拠は985k程度が二人以上存在出来る事。方針が大幅に違っていたら、もっと大きな差が生まれるはず。１位になった時も3000点程度しか削れなかった、というのもポイントかな。

19:24

ビームサーチを大前提とする上で、スコアをあげる方法はいくつかある。

  • 評価関数の精度の向上

これが一番自分の好きなもの。状態に対して、最終スコアが良くなる状態を高く評価できる評価関数が出来れば出来るほど、適切な状態を選択しやすくなる。

ただ、自分はここをひたすら重視して、重厚な評価関数を作ってリードを作ることが多いのだけれども、今回は実行時間制限が無茶苦茶厳しいし、評価をまともに出来ない。

  • 高速化

これが一番解りやすい。早くなれば評価可能な状態数、探索可能な状態数が増えて、その結果点数が上がる。非常に解りやすい。ここはもうちょっと頑張りたいね。

これがちょっと解りにくい話。似たような局面は、その後の評価点の変化が似たようになるから、良い時はみんな良い、悪い時はみんな悪いになっちゃって、あんまり複数持つ意味がなくなっちゃう。どっちかが良い、どっちかが悪いから、じゃあ良い方を採用しよう、みたいな感じで、どっちかが悪くても大丈夫、みたいなリスク管理が出来たほうが、全体的な性能は伸びやすい。

そこで、似たような局面を排除することによって多様性を生み出そう、というのも、ビームサーチで結果を良くする技の１つ。

一応色々試したのだけど、何しろ１ターンにつき評価してる盤面数が５～３０程度なので、多様性とかそれ以前の問題であることが多くて、なかなか解決できていない。ぐぬぬ。「１つの盤面から採用出来るのはｋ個まで」みたいなのを入れるのはアリだと思う。

 

とりあえず高速化やるか。

20:21

速度を計るよ！制限時間は14s

評価に掛かっている時間:10360ms

探索に掛かっている時間:1504ms

OK。探索はもう十分早くした。次は評価だ。bit演算とか使って頑張って早く出来んかな。

20:50

ローカルで１割早くしたんだけど、本番環境だと3%遅くなってて闇を感じる

4/17(8日目)

8:44

評価、差分を取ってるんだけど、「未来のスコア」-「現在のスコア」を計算するわけじゃん。現在のスコア何故か毎回計算してたんだけど、よく考えると明らかに事前計算出来るじゃん。ということで事前計算を入れた。多分累積和使うともっと早くなる。

8:57

あの、なんで評価関数doubleで計算してるの。intでいいよね。アホなの？馬鹿なの？

いやまぁ、int型とdouble型で速度に大きな差があるとは思えないのだけど、TopCoder環境でどうなるか知らないからなぁ。試してみる価値はありそう。

10:41

多様性チェックが逆効果に働いてるっぽい。今採用してるのは、「同じ点数の時は同じ局面・類似局面と見做して探索しない」ってのなんだけど、いい加減過ぎる気がする。

つーことで、「同じ点数・最後に消したのが同じだったら探索しない」にしてみる。これが意外に効果的。ちょっと伸びた。

4/18(9日目)

17:04

高速化が仮に上手くいった場合として、１０倍の時間を使ってみても、１位のスコアと同程度なんだよね。これは、「高速化で負けているわけではなく、他の要素で負けている」ということを表している。

んじゃなんだ。類似局面評価、その可能性は確かにある。確かにあるが、ぶっちゃけあんまりないと思ってる。だって類似局面ないっしょこれ・・・。とりあえずchokudai-search実装してお手軽チェックしてみたけどやっぱり微妙だし。１％２％はよく変わるけど、５％差ついてたらなんか別要因って感じがする。ただまぁ10000ターンだから類似局面評価でワンチャンが刺さらないってのは普通にありそう、というのは確かに解るっちゃ解るな。

ただまぁ大本命はやっぱり評価関数や。評価が弱い。だから負けている。シンプル。かつ実力が最も出る場所！今自分の評価関数は残念過ぎるんだよ。しょぼすぎるんだよ。そこをどうにかしたい。まだこのレベルじゃYellowCoderレベルだ。

4/19(10日目)

8:43

さぁ本気出そう。

10:29

枝刈。７位→５位。評価関数を通すまでもないケースをひたすら狩る。

14sに対して評価関数11sなのだけど、盤面操作部分だけなら2sもかかってないことが分かったので、そこでガンガン切っていく。・・・とはいっても、盤面を見ずに評価とか、「消した数」くらいしか解らんので、大して切れない。

「2手以上かかったなら2連鎖しないとだめ」を入れると良くなるのはcolor=4だけ。ただcolor=4なら2%くらい良くなる、というのはちょっとすごい。評価局面が1000万→1600万くらいになってるからね。当然っちゃ当然だね。

15:03

枝刈範囲を見直して6位→5位。なんか書いてるうちに抜かれていく・・・ｗ そろそろギア上げないとあかんね。

16:17

評価関数のネタを必死で考えているが全く出てこない。何をどうすればいいのだろう。ちゃうのかな。そこじゃないのかな。とりあえず凄いせこい提出して５位まではいったけど、５位と200点差・・・・ｗ

17:26

実行時間に対する結果チェック。seed7

14s -> 19507

28s -> 19970

56s -> 20546

112s -> 20997

(140s -> 21256)

224s -> 21590

448s -> 21659

まぁ、なんか、4倍効率良くなれば1位らしい。高速化というより評価とか、そういうところの厳選だよねえ。16倍くらいになるとほぼ頭打ちになって、32倍は必要ない、って感じ。4倍早くは・・・・ならないよなぁ。なるとしたらデータ構造をまるっきり変えないとだめ。たとえばbitboardで持つとか。1つの色に対して4つの64bit整数で持てるから、これを利用することで・・・・・・・・・うーんｗ

 

23:59

これあれだよね。SSEゲーだよね。勝ち目ないやん・・・ｗ

不貞寝！

4/20(11日目)

9:09

ほんとにSSEゲーなのか？ほんとに今のデータ構造だとまずいのか？

いくつかデータ構造について考えてみる。ほんとは序盤にするべきこと。（自分の場合は、最初のコードは書きなおすの前提で組んでる部分があるので、最初にするべき、とは言わない。無駄になりやすいし）

  • ２次元配列に予め1-6を入れておく方法（現在の方法）
  • colorごとにbitboardを持つ方法。

とりあえず順番に

  • ２次元配列に予め1-6を入れておく方法

こっちは凄く素直な方法。与えられたデータをそのまま。

使い慣れてるのでこっちのが高速化しやすい。N*Nの領域を毎回初期化するわけじゃなくて、使った部分だけ処理する、みたいなことがしやすい。

ボトルネックは評価関数部分になる。みたい。修正範囲m*nに対してm*n*6くらいかけてる。(block3の数)*4*定数重め　もあるからそっちと大差ないのだけど。

  • bitboardを持つ方法。

なんとか&演算で上手いこと出来ないかな？みたいな方法。データ数256ってことは128bit整数2つで持てるわけで、SSEでbit演算するだけで求めたい形になっているポイントを見つけ出せそう。ということで多分探す部分が爆速になる。必要なデータ長も短いし。全コピーするのにlong longとして4*color個コピーすれば良いとか余裕過ぎる。

けどなんか全部SSEには出来ないし、結局遅くなりそうな気はするなぁ。

 

9:40

なんかbitboardで持つのはあんまりセンスがない気がする。そもそもbitに対してえいっってやるというよりかは、char型で16個まとめてえいっってやるもの、という認識だし。

で、char型ってことは0-15まで持てるわけじゃん。これを16個持てたらアレじゃん。１行分まるまる128bit変数で持てるってことじゃん。チートっぽい。

えー、えー、でもこれ自分の戦い方じゃないよねえ・・・。えー。えー。

でも説明はついちゃうんだよ。4倍早くなりゃ勝てるんだから。えー。えー。SSEゲーなのか？そうなのか？えー。えー。えー。やだー。やだやだー。SSEゲーやだー。

 

12:46

SSEゲーは無理や・・・マジで無理や・・・・。

 

17:22

バージョンチェックすら正しく動かせない＞＜

体調悪い！不貞寝！！！

4/21(12日目)

体調不良のためおやすみ

4/22(13日目)

12:23

とりあえず、盤面をコピーせずに頑張っていたところを、SSEで盤面コピー高速化しちゃってみて実装。だいぶ早くなってる。ボトルネックじゃない箇所なのに。なんでやねん。とりあえず+11k。Psyhoまであと53kね。

 

12:51

あれ、評価関数がボトルネックになってない・・・。3743 / 14000

削除処理入れても6004ms。なんで？

前処理部分が1800ms。これも微妙な感じ。ここがボトルネックだったらSSEかなり活躍できそうなんだけどなぁ。全体に対する操作だし。

13:46

うん。諦めよう。

自分はSSEでかっこいい評価関数がかける人間ではない。

そのことを自覚しよう。

その上で、その上でだ。現状早くすることが可能なパーツを、少しでも早くしよう。うん。それで十分だ。

19:27

ローカルでは十分に早くなった。早くなったが、本番サーバーでは早くならない。まぁそんなもんですよねー。

19:52

落ち着こう。よーく考えよう。こんな戦い方自分じゃない。こんな高速化＋最低限の評価関数で戦えるほど、自分は高速化のプロではない。

19:54

取るべき手段は２つ。

  • 評価関数をこれでもかというほど重厚なものとし、速度を犠牲に超精度の解答を引きずり出す
  • 評価関数の速度を保ったまま、新たな評価を追加する

この２つ

  • 評価関数重厚路線

探索に対して評価関数が重いときは、この路線は使いにくい事が多い。ぶっちゃけ今は、無茶苦茶軽い評価関数しか組んでいないのに、探索時間１に対して評価時間１かかっている。

これで、評価時間が２になるようなものを入れてしまうと、全体として探索数が2/3になってしまう。これは痛手。

もし探索時間が５だったら、探索数は6/7にしかならない。こっちは考えても仕方ない。

評価時間が５だったとしても、探索数は6/7にしかならない。こっちは地味に大切。

今のこの超軽量評価関数だと、探索数ががくっと落ちてしまうような問題でも、評価がむっちゃ重厚になると状況が変わる。ということで、思いついた評価を全部ぶち込む、というのは、ナシではない。

・・・・ただ、今回のケースで、「探索をたくさん行う」より有力な評価、というのを実は全く思いついていない。雑魚である。

  • 爆速評価路線

今のtriplebonusとかrensa2bonusとか捨ててもいいからなんか爆速に出来ないかな、みたいな路線。今更ながらrensaってchainにしたほうがかっこいいね。

2*2に着目するのは当然としよう。3*3とか4*4に着目するのはどうだ？

これをなぜ考えるかというと、ぶっちゃけSSEとの相性以外に理由はない。「ある程度固まってたほうが良い」をもっとふわっとさせただけ。{121, 242,121}みたいな重み付けを行った奴も使える。これが有力かは知らん。微妙。微妙だけどちょっと有力そうな気がする。+型とか半端なく強くなるけど、実際つええだろあの形。

ただまぁ、縦３連結とL字型は差別化してあげたいなぁ、とは思う。

20:20

配列で得点を与える方法ばっかり考えてたけど、２乗でうまいことする、って手もあるにはあるのね。

1,2,3,4だったら1,4,9,16になって、増分が3,5でちょうど・・・いいかなぁ。微妙だから2くらい足すと。

 20:26

違う気がしてきた。3*3とか、なんで自分はこんな対称形に拘っているのか。2*3とか3*2が範囲として適切なんじゃないのかな。2*2も別評価でもちろん入れるけれども。2*3だったら、2っていうのは殆ど意味がないし、3だったらまぁある程度有力なのかな？って感じがする。4だと、Ｔ型Ｌ型テンパイ型の3パターンしか存在しない。超強い。2*2だと2,3について評価するのに対し、2*3だと3,4を評価する感じ。・・・・・どうなのかな。

Ｔ型はまぁテンパイ２つだから嬉しいけど、Ｌ型って嬉しいのかな。２種類の動きでテンパイ型に移行できるのだから、強くはありそうなんだけど。

20:48

block2の評価点を上げたらなんかちょっと良くなるのを発見。

ななめ2 -> block2が１個分

たてorよこ2 -> block2が２個分

block3 -> block3が１個、block2が２個分

であることを考えると、3がそこまで多くなくてもいいのかな、という感じはしなくもない。ななめとたてよこ差を広げるのは大切なような気がする。block2の点数が思ったより高いのがポイントだとは思っていたけれども。

21:13

とりあえず3*3作ったから適当にやってみよう

２→こんなん無視でええやろ。０点

３→この辺から。１０点くらいかなぁ

４→この辺をふわっと評価するのが狙いになるんだろうけど、わからん

５→わからん

６→この辺はプラスなのかマイナスなのかもわからん。Ｈから１個かけた形、ドーナツから２個かけた形、Ｙみたいな形。評価しづらいっ

７→ドーナツが１個かけた形。-200くらい。triplebonusが200か300ついていて、引き算しづらい。Ｈ型みたいなのもあるのか。これだとtriplebonus４つ付いちゃうのね。そんな優秀な形じゃなさそうだけど。

８→ドーナツ型のみ。これ大幅マイナスしないといけないんだよな多分。triplebonusが4つ分で400点くらい加点されてるから-300とかでよさそう。

 

・・・ようわからん、という結論にしかならないな・・・。　ドーナツ型とかのマイナスが出来るから3*3いいかなーと思ったけど、正直微妙だった。一応回してるけどやらなくても結果が解る。これはダメや。

いや、多分「調整すればそこそこいい結果が出るんじゃないかな？」ってのは出るんだよ。出るんだけど、狙いがあやふやすぎるから、結局伸びないんだよ。解ってる。じゃあなんで作ったんだよ。希望がないからだよ。

 

22:45

2*3作ってみた。こっちはtriplebonus代替が狙い・・・なんだけど、直接性が落ちるから前より悪いよね。ダメだこりゃ。triplebonus狙いなのかT字型支援したいのか訳が分からなくなってしまう。

 

 4/23(最終日)

メモっている時間がなかった。上位数ケース以外は１手で消えるパターン以外見ないようにして爆速に。これで結構上位に行くも、現時点で４位。最終ラッシュで抜かれそう。あうあう。