chokudaiのブログ

chokudai(高橋直大)のブログです

TopCoder Open 2014 Round1 参戦ログ1

問題

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=39769&rd=15938

順位表

http://community.topcoder.com/longcontest/?module=ViewStandings&rd=15938

 

 

ログ

4/10

2:34

問題を把握する。

N*Nマスのボードがあって、2*2の同じ色のマスを作ればいいらしい。

Nが8-16、colorは4-6、同じ色が出来ると、乱数で作った次の2*2のブロックに塗りつぶされる。乱数の使い方のところが読めてないけど。

出来る操作は、上下左右のswapを10000回。1ターンにかけれる時間は多くないね。

回数が少なければ先読みゲーかな?と思っていたのだけれども。

 

2:45

30秒で1万手、ってことは1手3msかぁ。

出来る事少なすぎて笑えるレベルだなぁ。どれだけ良い評価を行えるか。

ビームサーチとか出来る感じじゃないし。うーむ。

とりあえず思ったのは、とにかく勝ちづらいな、ということ。

こういう系は評価関数一発勝負な部分あるし、それをどう組んでいくか。

 

2:52

やっぱりこれは先読み勝負っぽい感じだなぁ。「どのタイミングでどのブロックを入れるか」をガンガン計算していく感じ。

10個くらい先読みして、残しが良くなるブロックが存在するのであれば、極力消さない、みたいな。

あとは運ぶ経路がそれなりに大切。結構いろいろあるし、後の状態にかなり影響与える。

 

2:59

ビームサーチが使えないかどうかの再考察。3msだろ?手数が10000でそれを保持しないといけないだろ?さすがに無理だよねえ・・・。

いや、「共通だと判明した部分は、共通部にAddして削る」みたいな特殊処理を入れてしまえば実は行けるんだけどさ。持てる状態数なんて大した数ないんだし、すぐ被る。

Nが8くらいだったらワンチャンある気がする・・・。うーん。

 

3:02

適当な貪欲解の提出が始まっている。

Gyazo - df8e134172500319800b842093676d50.png

恐らくアルゴリズムとしては、各ターンにおいて、2*2を作るための移動経路がもっとも少ないものを選ぶ、って感じの貪欲だと思う。

んー。大きな差は出ていないけれども、スコアがみんな93%程度なのが気になるね。

ルートによって7%も差が出るか。んー。もうちょっと少ない差で収まるものだとばかり思っていた。(96%くらい)

このコンテストは荒れそうだなぁ・・・。

 

3:17

まず、基本的な戦略が2つあることを意識しないといけない。

  • 「swap」を全探索して、局面を評価する
  • 「消し方」を全探索して、局面を評価する

これはだいぶ大きな違い。ここで間違えると一生勝てない。

まず、swapで評価する場合。有効な手っていうのは、N*N*2パターンしか存在しなくて、最大でおおよそ500パターン。これらに対し、評価関数で盤面を適当に評価してあげれば良い。自明な枝刈も入れないと死ぬかな。差分スコアは必須

次に、消し方を全探索する場合、消し方は、「どこで」「何色を消すか」なので、N*N*colorくらい。ただそこから、「具体的にどう消すか」を考えないといけない。これが地味に大変かもしれない。枝刈をだいぶ入れないと死ぬ。

だけど後者のが良いかな。前者だと、「先読み」要素がなくなってしまう。その実装には未来がない。となると、後者で「消し方」を全探索することによって、先読みを生かしていこう。先読みを生かすことこそが、今回のマラソンマッチで下位に差をつける秘訣だと思う。

ただ、swap全探索だと、探索範囲が軽いので、ビームサーチの可能性が残る、というのは、頭の片隅に留めておく。上位と大差をつけられた時に、振りかえれるように。

3:24

 提出を眺める。

Gyazo - 8fbd2501f844d93a26cde85c4a562cda.png

ここまで横一線になるかぁ。マジかぁ。

どっちなんだろ?swap全探索の実装の方が楽だし、みんなそっちに走ってくれてると楽だなぁ、と思うのだけれども。

とりあえず、消し方の全探索の方で実装を開始してみる。

3:36

 いやこれ実装始めていいのか・・・?

ビリが7000点くらい?

この7000点っていうのは、「初期状態から同じところしか動かさなかった場合」である。これが1%近くを取ってる。

これって、0,1,2点くらいしか取れないはずで、これがこの点数取ってるってことは、上位陣100点200点くらいしか取れてない。

ランダム解か・・・?

3:48

とりあえずランダムに移動させるだけの解出して様子見よっと。 

 Example scores:

0) 144.0
1) 364.0
2) 160.0
3) 272.0
4) 79.0
5) 294.0
6) 293.0
7) 179.0
8) 178.0
9) 161.0

なるほど。10000手ランダムでもこれくらいの点が取れるのか。もうちょい点低いかと思っていたのでこれは意外。

color=4で、ランダムに色変化させる場合、4*4*4*4 / 4で、出来る確率は64回に1回とかしかなくって、これだと150点くらい。4-6なのでもうちょい低い気がするのだけど・・・んー?

3:53

chokudai,
Your test for the problem SquareRemover has completed.
Overall score: 841248.96

Gyazo - 32d4b8879a8761a0caec84238f3d50b9.png

うん、周りの人を完全に過大評価し過ぎてたね。ランダムでほぼ1位に近いライン。これは納得。

 

3:59

とりあえず実装するものは。

  • 消す位置を全探索。ただし、同じ色を2つ以上含まないものは調べない。
  • 「消すまでに必要な移動数」の最小を、幅優先探索で全探索。
  • ただし、順番考慮せず、最初のマスに一番近い奴・・・って順番で。
  • 最初はめんどいので大回りでおっけー。

くらいの方針で。

4:19

ちょっと重い気がしてきた。

あるマスが残り1マスで揃うよ!って状態になってる確率は、実はcolor=6でも結構高い。

ということで、残り1マスの場合以外は無視しよう。そうしよう。こうすると、「他の操作で色々動かしちゃった可能性」が無視出来て凄い楽。

4:29

まともな提出がきていた。

Gyazo - f538439ad51a4b88f4a0d40163754b00.png

kawateaさんが1000000点。自分のランダムが30000点くらい。ってことはおおよそ33倍良い。・・・ってことは、「2ターンに1回くらいは消せる」ってことになるなぁ。ほんと?

本当だとしたら、経路とか考えてるの筋悪過ぎる、って感じになる。ちょっと考え直したほうがいいな。

5:06

とりあえず組んでみたのを提出

Example scores:
0) 4176.0
1) 6958.0
2) 3579.0
3) 6425.0
4) 2583.0
5) 6889.0
6) 7438.0
7) 4304.0
8) 4309.0
9) 4191.0

30倍にはなってなさそうなので、これだけだと負けてそうだなぁ、という印象。

負けてる原因は、「テンパイになってるのが無かったらランダムに動かす」という適当実装のせいだと思うので、そこだけ修正しよっと。

5:34

追加実装した。んだけどなんかバグっている

100ケースに対して3ケースだけバグっているらしい。それでサンプルに2つ出るか。

 

5:38

精査したら7つダメだった。良くないなぁ。どこでバグるんだろ。

5:45

目的のブロックを消そうと移動している最中に、違うものを消してしまうバグであった。とりあえず毎回チェックを入れることで対応。この辺は後で全部差分にしていかなければ。

ということで提出

Gyazo - 2911841e8bc5c8f12d73e11bf924cd82.png

819154。大差で負けている。やばい。これもうなんかやってる。

6:24

朝ご飯食べた。

今見えている範囲で、やるべきことって実はそんなに多くないんだよね。

  • その状態を作る経路の探索
  • 次に入るブロックの先読み

ってくらい。まぁ探索をまともにやるなら、評価関数を作らないといけない。どういうのがいいかな。

6:29

評価関数について考える。blockは2*2のマスを表す

  • 移動数が少なければ少ない程良い。
  • 残しにおけるblock内同色3が多ければ多い程良い。
  • 残しにおけるblock内同色2が多ければ多い程良い。

多分この辺を使ってくる人が無茶苦茶多いのだけど、これはちょっと筋が悪そう。

  • 移動数が少なければ少ない程良い
  • 経路を弄ることによって発生する残しが良ければ良い程良い。
  • 今回ブロックを消す行為が、後でブロックを消す行為と比べてどの程度良いか比較、「絶対的な差」ではなく「相対的な差」を使う。

要するに、「あとで良いのが来るから、今は使わない方が良い。」ってマイナスの評価を多少入れてあげないといけない。

この評価関数は加減が難しくって、

  • 今見えている消し方以外が後で発生するかもしれない
  • 今見えている消し方が、他の消し方で消滅してしまうかもしれない

とかのリスクがあるから、軽めに入れる程度がちょうどいい。消滅リスクを避ける実装ももちろん可能なのだけど、重たいから入れない方が良いと思う。究極的には入れないといけないかもしれない。

  • 7, 6, 10
  • 5, 4, 3
  • 1, 3, 2

みたいな3ターンごとの3つの消し方をする時、貪欲だと上から順番に7,4,2になるけど、順番変えると5,3,10となる、みたいなパターンがたくさんあって、これを防ぐために、近未来を予め見ておいて、最高点との差分を取る感じ。

「この色が使いたい!」って場所がたくさんあると死ぬのだけど、マラソンマッチだから近似しちゃっていいでしょう。

具体的には、「今やった時の評価」-「max(kターンやった時の評価 * 0.8 * pow(0.9, k)」とかそんな感じ。0.8や0.9の根拠はない。

6:42

実行時間どーすんの。いや全部探索しなきゃいいんだけど、こういうのcolunさんの十八番じゃないの。クロスワードパズルの時のcolunさんが最強な問題に見えてきている。

6:48

+型をどう扱うかについて考えている。「3のブロック」ってのは結構価値が高いのだけれども、+型ってそれが4つと見做されちゃうんだよね。4つ分は絶対にない。

だからと言って連結成分で云々とかはしたくないんだよね。将来的に高速化することを踏まえて差分スコアでやることを考えると、ちょっと微妙。

「ト型」に対して減点するのがいいかな。

L字型→3ボーナス*1 + ト減点*0

L字型→3ボーナス*2 + ト減点*1

L字型→3ボーナス*4 + ト減点*4

0.6で計算すると、1, 1.4, 1.6になる。上手いこといってるね。これくらいのバランスなら良いし、差分で計算しやすい。

6:58

負けてる分、「遠回りの実装」のせいじゃないかなぁとちょっと思い始めた。

L字型の左下にターゲットがあった場合、ぐるっと回って入れにいくんだけど、別にまっすぐ入るんだよね。

まぁ処理が適当過ぎる分、1.25倍くらいだったらいくらでもよくなりそう。

7:01

そもそも、L字があるのであれば、「上がりまでの手数」を評価基準にほんとは入れたいよね。良いのが思いつかないけど。

7:08

手抜きで、2blockが、両方とも1手で埋めれる状態の時以外は3を作らないようにしたら、大凡1割増。98ケースで良くなったし、これは、「2手で必ず作れる」を前提にしても良いのかもしれないなぁ、と思ったり。 

7:15

2手以下確定、でやったらだいぶ伸びて、color=6の時だけ3手以下確定、でやったらさらに伸びた。これはもうなんか、上位の人はみんな最短回数を正しく実装してるだけだね・・・。

Gyazo - db7ae134b3048798cbdb3c7d8b4fdfdc.png

ランキングも結構変わってきた。yowaさんはそんな奇抜なことを最初にやるタイプではなく、妥当に解いてくるタイプなので、指標として解りやすくて有り難い。

7:29

うーん、実装が頭の中で纏まらない。大風呂敷を広げ過ぎか?

いやでも、先読みを入れないと勝てないだろうな、って感覚は正しいと思う。

10位以内とかで良ければ、先読みなしのswap1手1手考えてく実装で行けるだろうけど。

とにかく、やるべきことは、

  • 一定数の候補を常に持つ
  • 周りの状態に対して、残しが良くなるような消し方の時だけ消す

を絶対に心がけなければならない。今みたいな、「3つ固まってるところが1箇所しかないからここから絶対消す」みたいな動きは絶対にしてはいけない。ここから卒業出来ない限り、良い解は絶対に得られない。

7:56

遠回り回避実装してみたけど、ほぼ良くならないので削除。

8:00

提出、92万点で5位。微妙だなー。 

Gyazo - bad880ac00eb3c7c1eb0699c581b28c1.png

この時点で、

Example scores:
0) 6214.0
1) 7680.0
2) 5581.0
3) 7387.0
4) 4373.0
5) 7556.0
6) 7758.0
7) 6251.0
8) 6333.0
9) 6171.0

となっているのを見ると、やっぱりほぼ1手2手先しか読まないでいいんだよねこれ多分。

適切な選び方をすればもっと減りそうだしなぁ・・・。2手以上の候補を考えないで良い、くらいは普通にあり得る。(というか今の時点でそうしている)

8:22

いや本当かなぁ・・・。テンパイ形増やすために序盤は完成を重視する必要ない気がするなぁ・・・。1手決めより、2個テンパイ増やしながら2手決め、みたいな、それくらいのが欲しい。

選択肢が増えすぎると、崩してしまう確率が高まるので、そうなるとまた別なんだけど、「1個完成」と、「1個テンパイ」は結構同価値と言っても良いくらいには価値がある。

8:35

現状、「テンパイ形は平均1,2個しか存在しない」という状態で、そこから探索を行ってるのが、「待ち」が出来なくなるため良くない、という話になりそう。

8:39

先読みは本当にいるのか?というのを考えている。今考えてるのって

  • テンパイ形は、良いのが来るまで粘る
  • 粘る間は、テンパイとなる形を量産する

って方針で、これって先読み型よりswap型の方が向いてない・・・?

気のせいかもしれない。

8:42

いやいやいや違う違う違う。「次のblock」を拾うためには、「どこかで消す」って動作が必要じゃないか。手番を回したところで次のblockには移らない。ってことは、「テンパイを増やす」なんて漠然とした操作じゃなくって、「どこを消す」っていうのを具体的に示してあげないとダメだ。

ってことは今の方針で合ってる。正しい。問題ない。こういう良くわからない錯覚は本当に危ない。

ってことで、必要なのは、「選択肢を広く持つこと」であって、「テンパイを作ってお茶を濁すこと」ではない。メリットが少ないのであれば、崩れやすいテンパイを増やすメリットなんてどこにもない。

8:48

遠回りしない運び方、2手だったら2通り、3手だったら3通り、4手だったら6通りしか存在しないんだよね。全探索行けるで!5手10通り?ほんとに普通に行けそうだね。

全部試すべきかは正直解らんけど。合計5手を超える手はさすがに無視していいんじゃないかなー、と思ってる。

となると周辺5手全探索?はちょっと筋が悪いよね。んー。

というか多分色数依存で、4色だったら3手で絶対十分、5色だったら4手で絶対十分、って感じだよね。4色と6色で結構ゲーム性違うなー。

9:04

実装考えてるけど、初日にしては重たすぎるんだよね。

30秒制限に対して、本当に30秒で処理しきれるのかな?って自信が持てないコードになってしまう。これは良くない。

Finalだったら、「そこまで時間内に書けてバグがなければ勝ち」って感じかな。15時目標で組んでみよう。

9:25

yowaさんが伸びている 

Gyazo - ca595c4198f5f146801d6ca6a8b4cfef.png

まぁでもこれくらいなら、見えてる範囲の実装でどうにでもなる。無視して問題ない範囲。

9:35

軽く実装に悩んでいる。

「k手以下の全部の着手」について考えるべきか、「最短手数の着手」のみについて考えるべきか。

9:42

いやもうちょっと冷静になろう。yowaさんのスコアを見てもうちょっと考えよう。

マラソンマッチの鉄則、とにかく相手を舐めてかかれ。開始から8時間弱、まだ大したアルゴリズムは組めないはず。

・・・・つーことは、単純なアルゴリズムであれくらいのスコアを出している可能性がある。2割。単純なアルゴリズムで+2割行けるか?

行けなくはない。ちょっとしたビームサーチを入れて、なおかつ評価関数まともに作ってあげれば行ける。もしくはランダムにいくつか採用してるだけとか。

どちらにせよ、行ける範囲ではあると思う。

10:02

冷静に考えると実装そんな難しくない気がしてきた。

11:55

厳密に最短を求めて貪欲していくアルゴリズムをとりあえず試す。デバッグモードとは言え、この時点で3秒かかってるのはちょっと気になるなぁ・・・。

どうも、厳密に最短にすると、color=6のケースで強くなって、それ以外で弱くなるみたい。もしくは前の実装がなんかバグってたかな。

12:54

差分スコアの計算方法が上手いこと浮かばない。つらぽよ。

どう実装するのが早いのかよくわからん・・・。

  • swap1回ごとに差分スコアを計算する。
  • swapを全部したあとの結果に対して、1マスずつ差分スコアを計算する
  • swapを全部した後の範囲に対して、一気に全部計算する。

最後のが楽かなーと思っているので、最後のにしようかな・・・。

13:19

とりあえず最後ので組んでみたけど・・・。

6) Score: 8520.0 Run Time: 21231 ms

うーむ・・・・・・。実行時間もうやばいとなると、得意にしてる重厚な評価関数はちょっと難しそう・・・。

13:25

提出した。 

Gyazo - d7a1a1fbe59c3c487fbf4925d37ce659.png

Overall score: 894778.96

いやいやいやちょっと待とう。これは怪しい。

評価関数調整すればさすがにyowaさんは抜けるだろうけど、方針ミスを疑うべき?

13:27

さすがに方針ミスの判断は時期尚早?

yowaさんが同じものをもう組み切ってるとは思わないし、yowaさんを舐めきってかかるなら判断ミスなんだけど、ちょっと微妙。

評価関数の調整を入れて、先読みを入れて、それで追いつかなさそうだったら考えよう。

13:40

適当に先読みを実装。3block先まで先読みするようにしてみた。

seed1で最高スコア6509から、7662に更新。これはかなり良い。

13:55

Example scores:
0) 7666.0
1) 9605.0
2) 6054.0
3) 8043.0
4) 5786.0
5) 9522.0
6) -1.0 (TLEでなければ11073)

7) 7641.0
8) 7810.0
9) 7295.0

いきなりTLEの壁にぶつかる。ちょっと珍しい。どうすっかな。

14:05

自明に悪い解(3以上遅い)を弾くようにしてみた。なんか超強い。

Example scores:
0) 8068.0
1) 9954.0
2) 6540.0
3) 8530.0
4) 5806.0
5) 9997.0
6) 11360.0
7) 8165.0
8) 8240.0
9) 7759.0

枝刈高速化しただけなのになんでスコア伸びてんの・・・。

こういう時気を付けないとなんか見落としてるから危ないよ。考察!考察!

14:23

ちょっと係数調整をしたよ

Example scores:
0) 9324.0
1) 11920.0
2) 7144.0
3) 10278.0
4) 5833.0
5) 11912.0
6) 13388.0
7) 9358.0
8) 9400.0
9) 8814.0

うん、ちょっと。11%くらい良くなったけどw しかし10000ターンで13000とか目指さないといけないゲームなのかこれ・・・・。それは見えないわ・・・w

具体的には、block3の生成が1000に対して、上がりコストが1500とかにしてたんだけど、color4,5,6に対して、8000-4000-2000にしたことでスコアが爆上がり。

4,5に関しては、ダブルを狙ってかないといけないから、ここの重みを無茶苦茶上げないといけないのね。それは気づかないわ・・・。

色々やってたのを除くと、提出出来てれば決勝で間に合ってたくらいのタイムだね。うんうん、良い感じ。

14:40

さっきの悪い解弾いて良くなったのは、評価関数まずかったからかなぁ・・・。

15:15

wleiteさんが提出してるから、結果待ちしてから提出しようと思ってるけど、どう見ても30秒フルに使ってるような実行時間。

これはビームサーチっぽい気がするなぁ。自分と方針違う感じになってる気がする。んで、swapビームサーチ相手だったらやっぱり負けちゃいけないと思う。「待ち」が出来る先読みの方が絶対に強い。

・・・とはいいつつ、30秒フルに使ってる先読みパターン、というのもあり得るので、油断はしない方向で。使うの難しいんだけどね。

15:18

うおおう、2位と15万点差の満点での1位か。すげえなwleiteさん。

Gyazo - fd41d084fc591cd54980c6b5ec86174a.png

今回の提出で単独1位を確信してたんだけど、ちょっと怪しくなってきた。

Example scores:
0) 9759.0
1) 12807.0
2) 7541.0
3) 10942.0
4) 6038.0
5) 12593.0
6) 14628.0
7) 9582.0
8) 9574.0
9) 9103.0

大分良いから多分1位だと思うんだけどなー。ちょっとTLEが心配。

6) Score: 14628.0 Run Time: 17425 ms

Example Case: 

colors = 4
N = 16
startSeed = 656773882

これが一番遅いんだけど、colorsが少なくてNが最大なケースだから、まぁこれより極端に遅いのはあんまりないんじゃないのかなぁ。

 

15:25

やっと1位。大差になると思ってたけど、直前のwleiteさんの提出があったから、2位と5万点差。98万点越えてるから、TLEケースはあっても1つ。まぁ多分ないだろう、と予想はしている。

Gyazo - 56eb7ebc5495ae97b26f85f6bc5b3e4a.png

16:03

 メタヒューリスティックの観点から考える。この問題は、どのように時間を使い切るべきか。

自分の今の実装は、「一番重たいケースに合わせて、ギリギリ間に合うような貪欲法」を採用しているので、最も軽いケースは2秒程度で終わってしまう。

こういう時によく使うのは、

  • ビームサーチ
  • 何度もスタート

あたりなんだけど、ビームサーチはこれまでの履歴たくさん持ったりするのだいぶ面倒。何度もスタートに関しては、今回の場合すぐに収束しちゃうから良くない。ビームサーチほどじゃないけど、30手ずつくらい10パターンくらい進めて、良い進行を採用する、とかいう手が優秀かなー。

実装が面倒なので、「貪欲をどれくらい頑張るか」を時間いっぱいに合わせるかも。

16:50

 考えながら評価関数弄ってるけど、トの字型対応はやっぱり強い。2%程度の改善。バグ改善も合わせて4%くらい良くなってるかな。

17:09

3blockに対して、テンパイ状態になっているかどうかで点数変えるようにしたらさらにかなり良くなった。2%程度。ガンガン伸びるなぁ・・・。初日だからまぁこんなもんだけど、そろそろ頭打ちだろーと思ったところからまだまだ伸びていく感じが凄い。

17:18 

調整してさらに2%。あんまり初日に調整し過ぎてもあれだし、そんな厳密には調整しないけど、ここまで伸びるとすごいな。

「良い形にするための重厚な評価関数を用いた貪欲」で戦うのが今回の戦い方になるのかな。

17:27

提出。

Example scores:
0) 10096.0
1) 12976.0
2) 8164.0
3) 11260.0
4) 7121.0
5) 12948.0
6) 14980.0
7) 10246.0
8) 10174.0
9) 9690.0

Gyazo - 697ef92c85d8fa6a9e5fb38a075d4a34.png

きっちり満点での1位を確保。2位との差は12万。うん、良いでしょう。

wleiteさんがどれだけ評価関数とかの係数調整とかちゃんとしてるかだよなぁ。12万は結構すぐにひっくり返る。思ったよりもそういう問題。

4/11(2日目) 

1:44

 ランキングチェック。100万点崩されてる。2位のmarek.cyganさんと16000点差。

Gyazo - 351a66aa909d96fdf62354c9a850f55d.png

つーか一晩で追いつかれてる。お前ら暇人かよ・・・。

とりあえず朝はまったり。

2:41

朝なのでまったり係数調整だけして提出

0) 10431.0
1) 13132.0
2) 8465.0
3) 11462.0
4) 7671.0
5) 13061.0
6) 15035.0
7) 10510.0
8) 10491.0
9) 10079.0

とうとう8ケースで10000越え。これ、問題見た瞬間に、平均1手で進めてくゲームだと予想できた人、どれくらいいるんだろう。自分は2手くらいだと正直思っていた。

Gyazo - fcdbdccbb866805103b6da374a225104.png

スコアボードはこんな感じ。とりあえず5万離したけど、98.7万点かぁ。どの辺で負けてるのかいまいち解らんので、ちょっと引っかかる。

ちなみにローカルだと、前の提出が96.46点、今回の提出が99.90点なので、乱数でブレている、というよりは、単純に得意苦手が出てきている、といった感じ。color=4か6だと思うんだけど、どっちなんだろ。

2:58

今一番深刻な問題は実行時間な気もする。

評価関数、なんだかんだ軽いものしか入れられていないし、もっと色々入れようとした時に、そろそろseed 7が間に合わなくなってしまう。ぐぬぬ

あと、結局「1手先」しか読んでいない超お粗末な先読みしか実装出来ていないので、そのあたりもどうにかしたいなー。

しかしTLE覚悟で5手先読みにしても0.45%増えるくらい。うーむ?

「先読み」というか「普段と比べて相対的にどれくらい良いか」を重要視していて、1個見れば十分、って感じなのかな。確かに連鎖中心な今の状態だと、先読み・待ちをしても弱いのかもしれない。

・・・・・swap+ビームサーチが怖くなってきたぞ?

3:18

あ、あれ、yowaさんのレート1600くらいだと思ってたのに1900以上あるぞ・・・?過去2000越えまであるぞ・・・? 強いやん・・・。

最初一番上にいてそっからずんずん落ちていくイメージが強かったけど強いのね。超ごめんなさい><

3:54

んー。何しようか考えてるけど全然浮かばないな。

4:08

抜かれた。10万点差。Gyazo - 7d2a16dc0b643afa0041d6479a0c9359.png

伸び率おかしいしやばいかなーとは思っていたものの、ちょっと伸び過ぎやろ・・・w

4:36

単純に抜き返したいなら、確実な手法は1つ。メタヒューリスティック勝負に持ち込むこと。

現状自分のアルゴリズムは貪欲法だけど、遅いケースが20秒程度、早いケースが3秒程度かかっている。これを28秒ギリギリいっぱいまで使うように書き換える。

「乱数を変えて何度もやる」はマラソン初心者の発想。これは結局細かい差が収束しちゃって生かし切れてない。不完全情報ゲームだったらただの貪欲ってありなんだけど、今回は完全情報なので、ただの貪欲ってのは筋が悪い。

「ビームサーチ」は悪くない発想だが、状態を複数持ってそこから複数分岐を毎回考える、というのは、今回の問題では経路のデータが最大である分、だいぶ重たい。中級者発想。

じゃあどうするのかっていうと、その中間を取ろう。10000ターンあるんだから、100ターンずつ乱数変えて貪欲、を100回繰り返す。10000ターンでは収束しちゃっても、100ターンだったらだいぶばらつきが出るよね、って話。その時に状態数を複数持つと、複数ターンを跨いだビームサーチっぽくなるんだけど、そこまですると実装が重たいので、今回は採用しない。

多分この辺勉強になるから、読み返す人がいたらこの辺読んどくといいと思うよ。 (追記:この考察嘘でした。寝ぼけてました。)

・・・ってのがまぁ手っ取り早くスコアを上げる方法ではあるんだけど、marek.cyganさんがそこまでやってると現状思えないんだよねえ。でもとりあえずスコアを貪欲に上げるかなぁ。悩むなぁ。

ぐだぐだ言っててもしゃーないから組むか。

5:18

Example scores:
0) 10812.0
1) 13894.0
2) 9135.0
3) 12370.0
4) 8192.0
5) 13833.0
6) 15351.0
7) 10885.0
8) 10858.0
9) 10342.0

ローカルだとすっごい伸びてるんだけど、やっぱ本番サーバーだと実行速度が足りない。そろそろ本気で高速化しないといけない時期なんだろうか。

・・・・・・・・・・・・・違うよなぁ。そうじゃないよなぁ。なんか見落としてるからここまでやっても足りないんだよ。何が足りないのか。

5:35

盤面サイズ最大256しかなくって、持つ必要のあるデータって、

  • 盤面(N*N)
  • 今のスコア(整数1個)
  • これまで置いてきた手(最大30000)

なので、「これまで置いてきた手の共通部分を纏める」みたいなことを上手いことすればビームサーチ可能な気がしてきた。ビームサーチ可能であればもちろんそっちのほうが強い。

・・・・・・が、やるか?だいぶ実装めんどい上、収束可能性ねえぞw

で、現状最大採用数が10程度。やる意味ないよなぁ・・・・・・。

5:38

遅いのが悪い!実行速度が遅いのが悪い!100倍になればなんでもできる!!!

5:46

Overall score: 740621.58とか言われて呆然としている。なんで!?なんで!?

6:27

時間管理のところの実装ミスでした。みょーん。かっこわるいから、2時間経ったら前の奴直したバージョンでそのまま送信しよっと。

普通にテストしてみたら、ローカル10s=本番環境27sで、どうも5%程度の伸びっぽい。さらにローカル1000sを試してみると、おおよそ1割さらに伸びる。うーん。現状辿り着ける領域だけど、時間内に到達できる気がしない、ってラインだなぁ。

6:31

ちょっとした高速化。Dictionary<int, List<List<int>>>をList<Tuple<int,List<List<int>>>>にしてみる。なにこれ混乱する。

 7:46

とりあえずスコアだけ戻す

Overall score: 927036.24 トップと7万点差。遠い・・・。

7:47

思いつかないから、とりあえずシミュレータを動かしていたのだけれども、なんか連鎖がすっごい起こってる。平然と4連鎖とかしてる。すげえ。

まぁそりゃそうか。そうじゃないと15000とか出ないか・・・。

8:06

基本中の基本を落としていた。

  • 評価値1手2000点と、4手7000点、どっちのが良いか?
  • 評価値1手2000点と、4手9000点、どっちのが良いか?

この2つ。4で割って1750と2250だから、前者、後者、ってやっちゃうわけですよ。でもこれじゃ正しい評価でない。残り3手がどんな感じか、っていうのは予想がつかないわけですよ。ということで、平均期待値Aみたいなのを用いて、2000+3Aと7000,9000の比較をしないといけない。Aが1000なら7000でも採用だし、Aが3000なら9000は悪手。

8:19

伸びない あれ?

9:03

あれー? こっちのがいいはずなんだけどな。調整の問題だと思ってたんだけど、2%程度落ちる。なんだこれは。

9:16

適当に中身を見ている 

Gyazo - c340614cb59696afc7facadb4fa4882f.png

すっげー期待通りっぽい

11:12

わからんので差し戻した。他の評価を考えよう。

ブロック内に2個同じ色がある、のパターン、斜めに2個あるより、縦に2個並んでる方が優秀だよね。

現状、連鎖が特に重要視されているので、縦連結・横連結しているところは連鎖に凄く使いやすい。これを優遇していくことで、連鎖発生率をかなり高められそう。ここの差別化たいせつ。

・・・と思ったけどこれも伸びない。

11:56

なんかやってることがちっちゃい気がする。迷走してんなぁ・・・。

なんかもっとおっきい単位でなんかないか。大きい単位で見落としはないか。

13:46

ちょっと頭冷やして冷静になった。殆どのケースで1万点を超えてる→「連鎖」をすることが大切なのに、そこに目を向けていないのが良くない。本当に良くない。

ということで、「連鎖のタネ」について考えよう。

block3に隣接する連鎖の種だけ考えよう。そうじゃないと計算量が重い。

block3のかけてる部分にだけ隣接するblock3は評価が超高くて良い。連鎖に直接的に繋がる。

block3に隣接するblock2も良いよね。かなり高評価でOK。

14:05

Gyazo - 2c951389139eb388bf5321f7bca205f3.png

5万点差。遠い。

4/12(3日目)

2:13

起床、ランキングチェック。 

Gyazo - 229ad50e0f2f007656d046f60e85961e.png

marek.cyganと72k差の2位。marek.cyganさん強すぎでは・・・。

3位のyowaさんとは11k差。4位のnikaさんとは110k差。うーむ・・・。

6位にnhzp339さんが、1回目の提出で来ている。一発目804kはさすがだなぁ・・・・。

2:52

yowaさんに抜かれた。ぐぬぬ

3:11
  • 連鎖した時のポイントを優遇
  • (連鎖数/ターン数)にpowをかけてみる
  • 次ターンの方が良い結果が出るものを大幅に減点

全部上手くいかず。

3:18

marek.cyganさんの点数、927kの自分が700くらい削ってて、965kのyowaさんが800くらい削ってるんだよね。

これが凄い異様で、yowaさんが965kもあるのに800しか削れていない、というのが、正直意味がわからない。この二人は相当似た方針取ってるんだと思う。

自分が940kだった時は8kくらい削れてたからなぁ。marek.cyganさんの穴が埋まった可能性はもちろんあるのだけれども。

・・・となるとやっぱり、方針ミスしてるよねえ。

3:30

すっげー謎だなぁと思っている事として、3に隣接する2に高得点をあげると、無茶苦茶スコアが落ちるんだよね。何が起こってるのかマジで解らない。

2*3の6ブロックのうち、5ブロックが同じ色だった時(凹型)に死ぬのかな・・・・?えーっと、4色と仮定して、rensa3pointが1500ptが2回、3がテンパイ状態なので、3のデフォルト点700と、テンパイ点800が重なって、これも2回ずつなので6000点。

対して、消した時の点数addは6000点・・・あかん、これはあかん。補正入れよ。良すぎる形は消すよりも点数が高くなってしまうの、ちょっと良くない。凹型ってそこまで良い状態でもないし!

3:51

というかテトリスの形大体過大評価だよね・・・。S型みたいなのも。_| ̄みたいなやつ。Mみたいな形になったらもう目も当てられない。

6:03

なんか変だ。マイナス点関係の評価値を全部除いても、0.4%しか変わらん。そんなだっけ?

トの字補正入れた時は1.1%くらい良くなってたはずなんだけど・・・。

10:02

Google Code Jam忘れそうだった。危ない。

 

14:06 

 凹型で1%増えるやん。細かいと思って弄らなかったけど、やっぱ弄った方がいいのね。

seed6で結果眺めてたら、凹型とか、M型S型発生しまくっていたので、ここら辺色々対策していかないとダメっぽい。

 

 4/13(4日目)

5:05

起床。1日目以外なんもやってねえ・・・

つーかぬるいプログラム書いてんな自分・・・。

 

5:40

実行時間かけても1位には届かないし、先読みほぼ使ってないからビームサーチやらない理由がわけわからない状況になってきたし、全面書き換えやなー・・・。

5:43

ビームサーチが有力でない、という仮説を立てたの、差分スコアの合計が大きいものを採用するより、単純にscoreが良い奴を採用した方が良かったから、というのも結構な理由なんだけど、ちゃんと全体でスコア計算しなおしたらそっちの方が明らかに良い(0.7%程度)し、完全にミスってるなこれ。なんかバグってる。

6:04

ビームサーチについて考察。

過去の考察で「経路のデータを持つのがもったいない」とかあるけど、探索ノード数多くないので、余裕で持てる。

「探索を始める前の候補データ」が持つべきデータっていうのは、

  • その候補に辿り着く前の手のid
  • そこからどういう手でその候補に辿り着くか(平均2手。最大5手)
  • その候補の評価値

で、「実際に使われる」ということになった瞬間に、

  • そのボードの盤面の状態(board, score)

を計算してあげて保持する。んー。初日の考察だとビームサーチだめっぽい気がしてたんだけど、なんか普通に行けるね。なんだろこれ。

6:11

 スコアの削れ方も、現在5位なのに削れる要素がある、っていうのは、メタヒューリスティック部分で負けてるなら説明がついちゃうんだよなぁ。

まず、今回時間設定がギリギリなので、ビームサーチとかで状態数が十分に確保出来ないのであれば、先読みを前提とした選択にかなり効果が出てくる。具体的には、色数6かつサイズ16みたいなケースで勝ってそうな気がする。

逆にサイズが小さいと、ビームサーチみたいに状態持った方が圧倒的に強い。100倍くらい強い。時間が100倍あったとすると自分のプログラムは5%伸びる。

 10:43

86万点に落ちている。marek.cyganが99万点。何が、何が起きている。

これはメタヒューリスティック負けとかそういうレベルではない。そういう話じゃない。根本的な何かが違う、もしくは、評価関数のもっとも大切なところを1つ、もしくは大切なものを2,3個を落としている。それくらいのレベルだ。

11:35

何を上げるべきなのか。手数を減らすために必要な手っていうのは2パターン存在する。

  • 1手で消せる形を増やす
  • 2手以下で消せる形を増やした上で、連鎖発生率を上げる

基本これだよね。これをどうやって実現するべきかに注力しよう。

1手で消せる形、っていうのは、実は1つしか存在しない。3つ含むブロックの隣に、1つのブロックが存在する形。おそらくこれしか存在しない。これに関しては、Point[]という単純な4マス中の含有色数にプラスして、TripleBonusって名前で既に実装済み。

であれば、次に考えるのは、「その形が発生しやすい形」というものである。これがどういう形か、というと、テトリスのトの字型から、中央のブロックだけ取り除いた形。これは、両側から、角の空白を交換、もしくは消して埋めることによって、作成可能となる。

この形の評価はどんなもんか。もちろん「ト」の字より高い。

現在、削除時点数が5000点ほど(色数に依存)。3ブロックが700点に、TripleBonuxが800点で、2ブロックとしても見れる箇所を3箇所*300点持っているので、即消せる形、というのは2400点ほど。消す前の状態は、消す動作をしたときの倍の点数、というのは理想の形なので、この配点は良い。消し方はもう少し種類があるので、半分の2500点より低いのもポイント。

対して、今回作ってる形は、現在2ブロックが2つで600点。2400点の手があと1個で作れるので、1200点くらい欲しいかなー、という気がする。600点の補正で発生率はそんな高くなさそう。うーん・・・。計算速度に対して評価精度を上げる効果がペイできるか、というと微妙。これはとりあえず保留。

 

んじゃ、2手以下で増やせる手を増やそう。そもそも、「2手で消せる2block」と「2手で消せない2block」って価値の差が無茶苦茶でかいわけだし、そこは考慮しても良いだろう。ただ2blockって無茶苦茶多いので、それを本当に評価するかはちょっと悩む。結構時間かかるよなぁ・・・。

ちなみに2手で消せる2blockだとしたらどれくらいの価値を持たせるか。多分700点くらいが妥当なのかな。700点で、発生確率はそこそこに高そう。チェックするマスは4つだけ、と考えると、そこまで悪くもない。ついでなので、片方は1手で埋まる、とかでポイント上げても良い。それだと200点くらい? いや、ダブルカウント確実にされるので、ここから半分にしてあげないとだめか。

これで「良い2block」と「悪い2block」の差を明確化させることによって、劇的な変化が狙えないかなぁ。3blockってやっぱり数が少ないから、2blockの差異を明確化させる方が大切な気がする。

ぶっちゃけここくらいしかないやろ・・・。ここじゃなかったら根本的な方針について考えないとあかん・・・。

12:05

現在5位から、takaptさんに負けてる状態を解除するためだけに、乱数の変化量を増やして提出。なんとかっこ悪い提出なのか。これがRedCoderの戦い方か。呆れる。

Gyazo - 33e754a8febc03e0958545c89a94b632.png

13:50

2blockは処理の重さに対して成果が出なかったのでダメでした><

えー、じゃあどうするんだよう・・・

15:11

wleiteさんに抜かれた。ふむ。

colunさんに抜かれた。colunさんはC++だしビームサーチちゃんとやってりゃあれくらいは出る。どうでもいい。

nhzp339さんに抜かれた。同上。どうでもいい。

nikaさんと9万点差。どうでもよくない。どこでそんな差がつくのか。

marek.cyganさんと12万点差。12万点。何を言っているの。12万て。

とりあえずなんか見落としている。何かを見落としているからこの点数になっている。何を見落としている?何だ?

15:14

そろそろ本気で考えよう。

ビームサーチの計算量について再度考察。今回の制限時間は30秒。

10000回のターンが存在するため、まぁ30万ステップくらいしか計算できないものと考えて良い。盤面は最大256、平均おおよそ150くらい。削除可能箇所は、見積もりが難しいけれども、まぁ結構見積もらないとだめ。block2で見積もると実は30~100とかになっちゃう。経路も全部探すと結構な数に。これに対して盤面の評価。全体見るとやっぱり150くらいかかっちゃう。差分でやっても消してる以上、影響を与えているマスは結構多い。

って考えると、どう考えてもビームサーチじゃやっぱりイテレーションの回数が全然足りない気がするんですが、なんか間違えてますかね!!!!!

計算量で何かしら落としてる可能性をやっぱり疑いたい。ちょっと現状普通にやっても届く気がしなくって、何かしら広大な探索が出来る、って前提を持たないといけない気がする。

15:21

分岐が多過ぎるので、そこをさくっと弾きたい?弾きたい。周りをちょっとだけ眺めて、なんか相性悪そうだったら弾くとか?いや別に100分岐とか正直そんな多くないんですよ。ステップ数に対して時間が足りな過ぎる。それが最大の問題。どうすんのこれ。どうすんのこれ。どうすんのこれ。

15:25

どうすんのこれ。

15:26

どうすんのこれ。

15:32 

 どうすんのこれ!!!!!

17:17

高速な探索手法あるじゃん!

前回変化したところから対して変わってなかったら、入れ替えるマスしか変わらないことを利用できるじゃないか。

・・・・出来るけどさ、出来るか?組めるか?組める気はしないぞ?しかも対して早くならない気もするぞ?

17:18

 今足りてないのは何か?判断するためのデータだ。具体的に、color, Nの条件に対して、block3はいくつあるのか?block2はいくつあるのか? そういう途中の状況を想像で語ってる時点でお話にならないわけですよ。

とりあえずデータ収集をするよ!

17:34

block2に関しては、4色なら8割超、6色でも6割くらいあった。

block3は2Nくらいある。キープ出来るだけ頑張ってキープしてる感じある。

 ・・・と思ったら、6色だと急に3の残り数が減少することがあるっぽい・・・?

19:37

色々データ取った結果何も解らんかった。不貞寝。

 

4/14(5日目)

9:20

「研究ガチ勢舐めててすいませんでしたー!」ってmarek.cyganに土下座する準備は既に出来ている!

順位表 Gyazo - 351903444b5a98ddbde295fdfc7affa2.png

9:21

さあどうやって勝とう。どうやって勝とう。

過去にやったことで、何か忘れていることはないか?

  • TCO13Final

鏡をレーザーで破壊する問題。あれもこんな感じで、ターン制で、1手1手進めてくやつだったよね。

取った戦略は貪欲。を、パラメータ変えて何度も実行したね。外部1位のtomerunさんも大差ないアルゴリズムだった。あれが貪欲で実行するのが妥当で、メタヒューリスティックを介在させる余地がなかったのはなんでだ?

・・・・・単に時間がなかっただけな気がする。ビームサーチが出来るかどうかはともかく、途中の状態から戦略変えるのは普通に有効っぽい。Final参考にするのはやめよう。

  • TCO13 Round2

これも、「終了するまで」のターン制一人ゲーム。ほぼ全員ビームサーチ。

これは普通に実装しても1ターンにつき200,300とかの状態について探索出来たから余裕だった。なんせ終了までのターン数が大抵100もなかった。であれば、調べる状態は数万だ。これは見るからにビームサーチが強い。

この時勝てたのは、「状態の評価が難しかった」からで、その際に、適切な評価関数が組めたからだ。今回の問題は、評価はぶっちゃけある程度簡単だ。そこで差をつけられる問題ではない。たぶん。致命的な評価を見落としていない限り、の話だが。

  • TCO12 Round3

ケーキ問題。この時は、「ケーキの配置を上手いこと決定する」部分を見落として負けて3位。「ランダムに変化とか、焼きなましとか、そんなんじゃダメ。明確に形を作ってあげなきゃいけない」って部分で負けた。

今回はそういうのはないか?例えば、ランダムで適当に作るんじゃなくて、なんとなく、ここは何色のゾーン、みたいなのを、明示的に決めていくことにより、連鎖発生率や良い形の作成率を上げていくようなアルゴリズム。適当に作ると、部分的に良い形と部分的に良い形が交錯しちゃうような、そういうアルゴリズムはないか?

 ・・・・・・ないと思う。多分ない。

 

逆に、それでも3位を取れた理由は、「軽い評価関数を何重にも重ねて枝刈することで、計算時間を極限まで抑えた」こと。ケーキを分けるアルゴリズムに対して、3パターンの精度のアルゴリズムを用意し、評価する価値があるもののみを評価するようにした。

今回も同じことが出来ないか?基軸となる局面数が10万、それに対して、初期分岐が100個くらい。最終的に評価すべき局面が20くらいとしよう。1000万局面に対して、軽い評価関数を通して、300局面くらいに減らせたら強い気はする?ただ既に評価関数かなーり軽いんだよね・・・。計算回数1000回もないというか、100回くらいというか。あんまり有力ではなさそう。

  •  TCO11 Round3

このコンテスト、8位だったからスルーしても良い気もする・・・。

  • TCO11 Round2

円を書く問題。結構思い入れのある問題。あれは、幾何の問題の特性上、探索の仕方が複数あって、その選び方が良かったから勝てた問題。

今回はどうだ?探索の仕方が複数あるか?あるとしたら、「1ターンずつswapに対して探索」をするパターンと、「1個のブロックを削除する消し方について探索」するパターンと、どちらかだと思う。自分は後者を選択したが、後者を選択した理由は「先読みが可能」であることであり、現在先読みを殆どのパターンで潰していることから、この考察は間違いであったことが解る。

うん、やっぱり基本に立ち返って、探索の仕方からにしよう。

swapで1手ずつ進めていくベースで解くことは可能か?妥当なプログラムが書けるか?

手抜きでやるのであれば簡単である。適当にビームサーチかなんかで、全部swapしてあげるのを調べてあげれば良い。ただこれって大した成果が出ない。だって適当だもん。

じゃあどうだ。ここの適当な部分を、評価関数で補うことが出来るか?

・・・・・微妙。わからん。解らんが、マイナス材料はいくつかある。

  • 1手ずつ進めていくので必ず10000ターン全部に対して処理しないといけない。
  • 広域な範囲に対して評価をする必要がおそらくあるので、評価関数が重くなりそう。
  • swapの選択肢はおよそ100~500くらいある。

要するに、評価関数がむっちゃ難しい。その割に、意外とメリットが少ない。だって消さないと次出てくる状態動かないんだもん。同じ状態むっちゃ出てくるし。

削除ベースだと同じ状態全然出てこないんだよね。その辺の制御もらくちん。

・・・・・・・・・・・やっぱ今のやり方であってるよねえ。

 

あー、わからん。わからん。ほんとにわからん。自分の味を何にも出せてないから勝てないのは仕方ない。仕方ないんだけどむかつく。marek.cyganは何をしている。

 

10:09

わからん。細かいネタはちょこちょこ浮かぶので、ビームサーチベースにC++で書き換えた上、そういうのをがっつり実装しまくって2位を取りに行くか・・・・・?

 今は832121点だろ?3位がcolunさんで916249点。2位がnikaさんで948085点。

うーん。うーん。うーん。2位は多分まだ予選通過ライン越えてないと思う。marek.cyganさんは予選通過ライン越えてると思う。けどやっぱりあの点数を目指さないといけない気がする。目指す上で、そんなぬるい攻め方で行けた記憶があんまりない。

ただ毎回、「とりあえずいま思いつく一番良いもの」を実装し続けて、思いつくたびにどんどん更新していくことで、何かしら良い成果は得られている、ような気もする。気もするだけかもしれない。

11:54

ぽけーっとしてる。ここ三日くらいずっとぽけーっとしてる。

12:50

とりあえず何も浮かばないのだから、ビームサーチを組んでしまえば良いのだと思うのだけど、なんかそれに踏み切れない。

現在、おおきいケースで1.5並列、小さいケースで10並列くらいで動かせてるわけだけど、まぁ平均3並列とするじゃん?3並列のビームサーチって強いの?とても強いとは思えないんだけど・・・。

んで、C++書き換えも視野に入れないとなんだけど、じゃあC++に書き換えたら早いの?確かに多次元配列使ってるし、1.3倍くらいにはなるかな?とは思ってるよ。思ってるけど、せいぜいその程度でしょ?まだまだ遅いでしょ?

どうすんねん。ほんとどうすんねん。やっぱなんか評価見落としてるか、根本的なミスにしか思えないんだよ。

12:56

評価関数に致命的な抜けはないか?確認

  1. 消したブロックの数に対する評価(1個消すと色数に応じて4000-6000点)
  2. 残っている2*2ブロックの評価(3: 700, 2:300, 1: 0)
  3. 1手で消せる3blockについての評価(800)
  4. 3blockに隣接する3blockについての評価(色数に応じて500-1500)
  5. 3blockに隣接する2blockについての評価(100)
  6. 上記状況でで、色が同じだった場合の評価(-400)
  7. 3blockに隣接する同色1個の評価(S型-100 T型-600 +型-2200)

 今入れてるのはこんなもん。こんなもんなんだけど、なんか誰でも思いつくような低俗な評価関数過ぎてもやっとする。

7番のバランスの悪さが気になる。Sが-100でTが-600な理由はない気がする。同じでいいやん。いや、カウントの仕方の違いで、Sの方は二重カウントされちゃうんだけどさ。

13:35

奇怪な現象が起こっている。

実際に進行させているおおよそ7万ステップ中、1000ステップくらいが、予想と違う消え方をしている、という衝撃の事実があるのだけれども、それを正しく反映してあげると、スコアが3%くらい下がる。なんだこれ。

バグっているのか、評価ポイントの見落としがあるのか、どっちだ。

調べている感じだと、「消えているかのチェック動作を入れる」って行為をするだけで点数が大幅に変わる。なんでや・・・。

16:28

ちょっと仕事などをしていた。

上のバグは、「チェック動作」が想定外の挙動で、それによって、「更新のあったマス」のフラグを立ててしまうので、4つ揃っているかどうか判定する範囲を正しく拾えなくなっていた。直したら0.05%くらい良くなった。はい。

S,Tのバランスについても修正したけど殆ど変らず。はい。

17:00

もうこれ評価関数でどうにかなるように思えなくって、評価関数でどうにかなるとしたら、もっと広域に対応できる評価をしないといけないと思う。広域に対応できる評価ってなんだよ・・・。2点関係とかかなぁ。

特定のマスから、そこから一定距離の特定のマスについて加点してあげる、みたいな。これはアリっぽい気がする。アリっぽい気はするが・・・どれくらいだ?

例えば距離1にある、というのは、既にblock2,3で実装されてはいるけど、超高得点だ。んじゃ距離2とか3はどうだ。現状殆ど無視されてるが。あってもいいものか。良い気はするよな。

距離3が存在するのが嬉しいか。距離1のマスっていうのは4マス。距離2のマスっていうのは8マス。距離3のマスは12マス存在する。距離3を加点対象にするかどうかは正直微妙だけれども、これくらいの評価だったら全然出来るでしょ。多分。出来るよね。

これを基軸に評価関数を完全に組みなおす、というところまであり得る。両方残す、というのももちろんある。今感覚として欠けているのは、「何となく色が集合している感じ」を作り出すことだし、これは結構な影響を与えるような気がしている。ダメかな。ダメじゃないといいな。

17:39

ダメでしたー。

19:16

強がってみたけどこの状況で潜伏なわけがあるかあああああああああ!!!!

といいつつ、15日中に1位にならないと罰ゲームになってしまったので全力を出す。とりあえず20時までにビームサーチのC#実装。様子見ながら24時までにC#への移植。

20:34

ビームサーチ組んでみたけどまともな成果は出ず。ぐぬぬ

 

続きは次の記事で