MMLightinig2018にっき
問題のリンク
TopCoder
問題を見る。
あれ~なんかアルゴっぽい問題だなぁ...?
いきなり何もわからなくなる(´・ω・`)
なんか見たことありそうな内容なのでとりあえずググってみる
彩色問題とかいう割と有名な問題らしい。これ初心者には厳しい問題では?
論文を読んでみるとグラフを作ってグラフの次数が大きいところから色を塗っていけばいいらしい(Welsh-Powell)それで実装してみる。
塗り替えマスの最小化は簡単そうなので最終日にやればええやろ。
うまくいったのでこれが第一投。
その論文にはこの方法を改善する方法が書かれていたが書き方が非常に悪く(人のせいにするな)分からなかったのでパス
第二投
色の塗る順番をいろいろ工夫してみる。
適当に2つの順番を入れ替える→全然よくならない
近接する2つを入れ替える→割とよくなる
同じ次数の頂点同志のを入れ替える→割とよくなる
Poolを作って解を複数保持する→よくならない
これらの情報から状態空間を観る。
えー、ちょっと悪くなったところからはいいところに行きつきにくく、状態空間は乱拓でよくなるような感じではない、狭い谷がある感じなんだろうか?
これは焼きなましは厳しいのではという感覚を得る。
しかし私は焼きなまししか知らないんだよ!!!!
以前のコンテストでもなんとかうまく焼きなましに落とし込めている人が強かったので
なんとかうまく焼きなませないか考える。
彩色数をそのままスコアにしてしまうとあまりよくないのではという感覚になる
とりあえずスコア関数というかエネルギー関数を工夫しよう。
ハミルトニアンHを
とする。
ここで
Qは隣合う色に同じ色があればHを大きくしようとする行列で
は色の大きさでindexの大きい色でぬろうとするとHが大きくなる。
つまり小さいindexだけを使って色を塗ろうというわけで
近傍はある場所の色を別の色にして作成する。
近傍も小さく状態に制限がない
これはを焼きなましで最小化すれば彩色は出るはずだが
これがちゃんと隣り合う色は別の色でないといけない制約をみたしてくれるかどうかは分からないがとりあえず楽観的に焼いてみる
しかし制約をみたす解が現れてくれない上に第一投の方法で作った階以上に良い彩色が得られない...
近傍をいろいろ試したが全然ダメ。
というか 状態空間を観ようとしてこれは焼きなましは厳しいのではという感覚を得たのに焼いてるのホントダメ。
これはアルゴ的に考えないといけなさそうだな。
ここで論文を読み漁る。
RLF法というのを試してみるが
遅すぎる。
遅くともスコアが良くなるのなら高速化するがスコアが良くなってないので没
Ant SystemとTabu Search とGAに行き当たる。
何とかこれらの方法でうまくいかないだろうか?
時間がないとりあえずAntSystemを論文を読みながら実装するが
論文では補グラフにフェロモンをつけろと書いてあったが、それではちゃんと順番を得られないと思ったので独自の方法でフェロモンをつけることにする
いいフェロモンのつけ方がわからん.....
バグってたのかもしれないがさっぱりよくならん....
「 塗り替えマスの最小化は簡単そうなので最終日にやればええやろ 」と最初に思ったがもう最終日になってしまっている....
今回あんまりやる気が出なかったのでダラダラしてしまっていた...
塗り替えマスの最小化は色を塗ったグラフのPoolを作ってそこから一つ取り出して山登り
以上。何もできない何もわからなかった。
悔しみが深い
ーーーーーーーーーーーー感想戦ーーーーーーーーーーーーーーー
(毎回終了後にやってる教授と感想戦)
私:ハミルトニアンHをとしてみましたがうまくいかなかったですねぇ。
教授:時間が経つにつれてTを下げるのではなくそのQの値を大きくしていくのは量子アニーリングでよくやられてる方法なんだけどやってみた?
私:なるほど....
電車に乗ったからマラソンツイートをしよう。とりあえず暫定3位。方針は2つあるけどおおよそは焼きなまし。各頂点の色を状態として、1つの頂点の色を変える遷移をするだけ。特徴があるとすれば、「色が被った状態を許容して、ペナルティスコアつけて表現すること」くらい?約2億ループします。
— chokudai(高橋 直大) (@chokudai) 2018年5月8日
ペナルティは徐々に上げると良い感じ。具体的には、Cをoldcolorの色数、tを0~1の温度として、120HWt/(C+1)みたいな感じで、tに対して線形で上げてる。
— chokudai(高橋 直大) (@chokudai) 2018年5月8日
ちょくだいさんが同じことをやっていて笑う。
しかしこれをやってみてうまくいかなかったという人が私のほかにもいてるみたいで
ここの調整はすごく難しいんだろうなぁ
アイディアは似てると思っても実際の実装を見ると「レベル高すぎww全然似てねぇわww」ってなるやつですね
TCO18 Marathon Poland Lightning Round おつかれさまでした。必ずしも色数を最小にするのが良いわけではない、というところは引っかけでしたね
— 2018年こそ夏バテにならない (@tomerun) 2018年5月8日
MMお疲れ様でした
— hoshi524 (@hoshi524) 2018年5月8日
やったことは彩色可能な色数が最小の頂点から貪欲に彩色しただけ
反省は
焼きなまし思いつかなかった(前回と同じ・・・)
raw scoreが最終スコアではないケース初めてで無駄にしたから、Scoringの項目はちゃんと読もう
明後日、Round1開始早い!
7色から8色に色増やしてもrepaintを7/8にすればスコア同じだから最小を目指さなくてもいいのかなと思った(思っただけ)
— hirokazu (@hirokazu1020) 2018年5月8日
というかスコアの計算方法ちゃんと把握してなかったの痛いですね...気を付けないと...
焼き鈍しと呼んでいいのは分からないんですが、基本どこかを塗り替えて改善したら採用の山登りをしつつ、遷移しない状況が続いたら徐々に温度を上げて改悪方向にも遷移するようにするやつをやりました
— iwashi31 (@iwashi31) 2018年5月8日
6 色で塗れた後は 6! 通りの permutation を試して塗り替え数最小を探した後全部ぶっ壊して再焼き鈍しへ
— iwashi31 (@iwashi31) 2018年5月8日
iwashiさんマジで頭いい....
色の数は固定して、「色が衝突する領域のペアを常に保持しながら、衝突する領域の色を一つ変える近傍で、そのペアの数を目的関数に焼きなましの条件式に基づいて遷移しvalidな解を見つける 」までを一回の遷移とする焼きなましをしました。
— ATS (@ats5515) 2018年5月8日
色は基本的に6色で、一定時間内に見つからなかったら7色で探すようにした(ほとんどのケースで6色解が見つかった)。領域数が多くもともと使われている色が多いケースでは6色でできても7色でやったほうが良いことがあった。
— ATS (@ats5515) 2018年5月8日
なるほど...
そういえば始まる前に書いたテストケース並列実行のためのスクリプトなぜかエラーが出て動かなかったんだった。
直したいが進捗発表がね...
Bitboardの作り方
以前RotatedBitboardとはどんなものなのかということについては述べたので、
daruma3940.hatenablog.com
初心者向けに具体的にどう作るかについて書いていこうじぇ。
ここから下に出てくるコードは
GPLで公開されているプログラム(Stockfish)を改変したり、自らのプログラムの一部として組み込んだ場合など、派生的・二次的な著作物を作成した場合には、これにもGPLを適用して公開しなければならないらしいので
GPLライセンスになり、使うのは注意なのじぇ。
今回のbitboardは縦型bitboardにするのじぇ。
とりあえず最初に縦型bitboard[81]のとあるマス(index)が
90度,±45度の回転を受けたときにrotated90bitbord[81],rotated±45bitboard[81]
のどのindexになるのかの対応を記したテーブルをつくろうじぇ?
これが縦型bitboardの升(index)の並び
これが反時計回り90度回転bitboardの升の並び
これのindexとマスを対応づけようとすると以下のようになるw
/* bitboardは縦型bitboardで[0]が44bit迄使用 bitboard 90のレイアウト 0 1 2 3 4 5 6 7 8 91011121314151617 181920212223242526 272829303132333435 363738394041424344 454647484950515253 545556575859606162 636465666768697071 727374757677787980 */ //sqのindexをsq90のインデックスに変換するために使うテーブル const int sq2sq90[SQ_NUM] = { 72,63,54,45,36,27,18,9,0, 73,64,55,46,37,28,19,10,1, 74,65,56,47,38,29,20,11,2, 75,66,57,48,39,30,21,12,3, 76,67,58,49,40,31,22,13,4, 77,68,59,50,41,32,23,14,5, 78,69,60,51,42,33,24,15,6, 79,70,61,52,43,34,25,16,7, 80,71,62,53,44,35,26,17,8, };
ちょっとわかりにくいかもしれないけど、
sq2sq90[0]=72
sq2sq90[1]=63
は
0番目のindexが72番目のindexに移り
1番目のindexが63番目のindexに移り
ということなので
追いかけてみるとさっきのレイアウトと一致していることがわかるはずw
同様にしてプラスマイナス45度回転bitboardの升との対応表もつくろうじぇ
/* bitboard_plus45 1 2 3 4 5 6 7 8 0 11121314151617 910 212223242526181920 313233343527282930 414243444737383940 515253454647484950 616254555657585960 716364656667686970 727374757677787980 */ const int sq2sqplus45[SQ_NUM] = { 0,72,63,54,45,36,27,18, 9,10,//9 1,73,64,55,46,37,28,19,20,11,//19 /*20*/2,/*21*/74,/*22*/65,/*23*/56,/*24*/47,/*25*/38,/*26*/29,/*27*/30,/*28*/21,/*29*/12, /*30*/3,/*31*/75,/*32*/66,/*33*/57,/*34*/48,/*35*/39,/*36*/40,/*37*/31,/*38*/22,/*39*/13, /*40*/4,/*41*/76,/*42*/67,/*43*/58,/*44*/49,/*45*/50,/*46*/41,/*47*/32,/*48*/23,/*49*/14, /*50*/5,/*51*/77,/*52*/68,/*53*/59,/*54*/60,/*55*/51,/*56*/42,/*57*/33,/*58*/24,/*59*/15, /*60*/6,/*61*/78,/*62*/69,/*63*/70,/*64*/61,/*65*/52,/*66*/43,/*67*/34,/*68*/25,/*69*/16, /*70*/7,/*71*/79,/*72*/80,/*73*/71,/*74*/62,/*75*/53,/*76*/44,/*77*/35,/*78*/26,/*79*/17, /*80*/8, }; /* bitboard minus 45 7 6 5 4 3 2 1 0 8 151413121110 91716 237221201918262524 313029282735343332 393837364443424140 474645535251504948 555462616059585756 637170696867666564 807978777675747372 */ const int sq2sqminus45[SQ_NUM] = { /*0*/9,18,27,36,45,54,63,72,/*8*/0, /*9*/19,28,37,46,55,64,/*15*/73,/*16*/1,/*17*/10, /*18*/29,38,47,56,65,74,/*24*/2,/*25*/11,/*26*/20, /*27*/39,48,57,66,/*31*/75,/*32*/3,12,21,/*35*/30, /*36*/49,58,67,/*39*/76,/*40*/4,13,22,31,/*44*/40, /*45*/59,68,77,/*48*/5,14,23,32,41,/*53*/50, /*54*/69,78,/*56*/6,15,24,33,42,51,/*62*/60, /*63*/79,7,16,25,34,43,52,61,/*71*/70, /*72*/8,17,26,35,44,53,62,71,80, };
次はシフトとマスクでindexを作成するときに
どれだけシフトすればよいのか、int64 bb[2]のうちどちらに対してシフトをすればよいのかということについて記述したテーブルをつくろうじぇ?
ちなみに私のソフトのbitboardは縦型bitboardでbb[0]がマス番号44迄使用して(マス番号44とは盤の右半分のちょうどいいとこ。自玉の位置)それ以降はbb[1]に格納しているのに注意なのじぇ
ちなみにマスクは7bit固定なのじぇ。
const int effectmask = (0b1111111);//7bitが立っている。
なぜ7bitかというと邪魔ゴマとして考慮しないといけいないのは7つで十分だからなのじぇ。9*9=81なので9bit何じゃないかと思うかもしれないけど9bitは別に要らないのじぇ
daruma3940.hatenablog.com
まずは無回転bitboardにたいしてなのじぇ。
/* 利きを求めるために何ビットシフトさせないといけないか */ extern int shift_table_tate[SQ_NUM];//何bit shiftさせるか extern int index_table_tate[SQ_NUM];//bb[0]かbb[1]のどちらを見るのか inline void make_shifttate() { for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) { shift_table_tate[sq]= int(1 + 9 * (sqtofile(sq) % 5)); } } inline void make_indextate() { for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) { sq > 44 ? index_table_tate[sq] = 1 : index_table_tate[sq] = 0; } }
次は反時計回り90度
extern int shift_table_yoko[SQ_NUM]; extern int index_table_yoko[SQ_NUM]; inline void make_shiftyoko() { for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) { Rank r = sqtorank(sq); //File f = sqtofile(sq); if (RankA <= r&&r <= RankD) { shift_table_yoko[sq]= (1 + (9 * (3 - r))); } else { shift_table_yoko[sq] = (1 + (9 * (8 - r))); } } } inline void make_indexyoko() { for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) { File f = sqtofile(sq); (9 * (int)f <= (int)sq&& (int)sq <= 9 * (int)f + 3) ? index_table_yoko[sq]= 1 : index_table_yoko[sq]= 0; } }
ナナメ+45度
extern int indexPlus45[SQ_NUM]; extern int shiftPlus45[SQ_NUM]; void make_indexplus45() { for (Square sq = SQ1A; sq < SQ_NUM; sq++) { int s = sq % 10; if (s == 0 || s == 9 || s == 8 || s == 7 || s == 6 || sq == 5 || sq == 15 || sq == 25 || sq == 35) { indexPlus45[sq] = 0; } else { indexPlus45[sq] = 1; } } } int shiftPlus45[SQ_NUM]; void make_shiftplus45() { for (Square sq = SQ1A; sq < SQ_NUM; sq++) { //10で割ったあまりの値で大体は区別できる int s = sq % 10; if (s==0) { shiftPlus45[sq] = 1; } else if(s==9){ shiftPlus45[sq] = 2 + 9 * 1; } else if (s == 8) { //これは端っこであるのでどのようなobstacleであろうが機器の数はゼロ if (sq == 8) { shiftPlus45[sq] = 9 * 1; } else { shiftPlus45[sq] = 3 + 9 * 2; } } else if (s == 7) { if (sq <= 17) { shiftPlus45[sq] = 9 * 2; } else { shiftPlus45[sq] = 4 + 9 * 3; } } else if (s == 6) { if (sq <= 26) { shiftPlus45[sq] = 1 + 9 * 3; } else { shiftPlus45[sq] = 5 + 9 * 4; } } else if (s == 5) { if (sq <= 35) { shiftPlus45[sq] = 1 + 9 * 4; } else { shiftPlus45[sq]= 6; } } else if (s == 4) { if (sq <= 44) { shiftPlus45[sq] = 1; } else { shiftPlus45[sq] = 7 + 9 * 1; } } else if (s == 3) { shiftPlus45[sq] = 1 + 9 * 1; //63 73の場合は別に場合分けする必要はない } else if (s == 2) { //72の場合も考えられるが72は一番端っこであるため利きはゼロに成るので無視していい shiftPlus45[sq] = 1 + 9 * 2; } else if (s == 1) { shiftPlus45[sq] = 1 + 9 * 3; } } }
ナナメ-45度
extern int indexMinus45[SQ_NUM]; extern int shiftMinus45[SQ_NUM]; int indexMinus45[SQ_NUM] = { 0,0,0,0,1,1,1,1,0,//8 0,0,0,1,1,1,1,0,0,//17 0,0,1,1,1,1,0,0,0,//26 0,1,1,1,1,0,0,0,0,//35 1,1,1,1,0,0,0,0,0,//44 1,1,1,0,0,0,0,0,1,//53 1,1,0,0,0,0,0,1,1,//62 1,0,0,0,0,0,1,1,1,//71 0,0,0,0,0,1,1,1,1, }; void make_shiftMinus45() { for (Square sq = SQ1A; sq < SQ_NUM; sq++) { int s = sq % 8; if (s == 0) { if (sq == 0) { shiftMinus45[sq] = 0; } else if (sq == 80) { shiftMinus45[sq] = 0; } else { shiftMinus45[sq] = 1; } } if (s == 1) { if (sq <= 9) { shiftMinus45[sq] = 0; } else { shiftMinus45[sq] = 2 + 9 * 1; } } if (s == 2) { if (sq <= 18) { shiftMinus45[sq] = 1 + 9 * 3; } else { shiftMinus45[sq] = 3 + 9 * 2; } } if (s == 3) { if (sq <= 27) { shiftMinus45[sq] = 1 + 9 * 4; } else { shiftMinus45[sq] = 4 + 9 * 3; } } if (s == 4) { if (sq <= 36) { shiftMinus45[sq] = 1; } else { shiftMinus45[sq] = 5 + 9 * 4; } } if (s == 5) { if (sq <= 45) { shiftMinus45[sq] = 1 + 9 * 1; } else { shiftMinus45[sq] = 6; } } if (s == 6) { if (sq <= 54) { shiftMinus45[sq] = 1 + 9 * 2; } else { shiftMinus45[sq] = 7 + 9 * 1; } } if (s == 7) { if (sq <= 63) { shiftMinus45[sq] = 1 + 9 * 3; } else { shiftMinus45[sq] = 0; } } } }
きったないソースコード恥ずかしくないの??
恥ずかしい...
この辺bonanzaとかshogi686とかはもっときれいに作ってるのでみんなそっちを参考にしようね!
ここからが邪魔ゴマを考慮したとび効きの作り方なのじぇ
(やばいもう飽きてきてしまった....)
/* 追加シフト三角行列 */ int additional_plus45(Square sq) { File f = sqtofile(sq); Rank r = sqtorank(sq); return std::max(int(f - r), 0); } int additional_minus45(Square sq) { File f = sqtofile(sq); Rank r = sqtorank(sq); return std::max(int(f+r-8), 0); } //LongEffect for (Square sq = SQ1A; sq < SQ_NUM; sq++) { for (int obstacle = 0; obstacle < 128; obstacle++) { int obstacle2 = obstacle<<1;//一つシフトしてやらないといけない!!! int direc_rook_yoko[2] = { 9,-9 }; File tofile; for (int i = 0; i < 2; i++) { to = sq; do { to += Square(direc_rook_yoko[i]); tofile = sqtofile(to); if (is_ok(to)&&(to != sq)) { LongRookEffect_yoko[sq][obstacle] ^= SquareBB[to]; } //横や縦の関係であればこの方法は使えるけど斜めでは通用しないぞ...(縦横に射影すればいいだけ) } while ((!(obstacle2&(1 << tofile))) && is_ok(to)); } } } //縦。下端が上手くいっていないなぜだろう?解決済み for (Square sq = SQ1A; sq < SQ_NUM; sq++) { File sqfile = sqtofile(sq); for (int obstacle = 0; obstacle < 128; obstacle++) { int direc_rook_yoko[2] = { 1,-1 }; int obstacle2 = obstacle<<1;//一つシフトしてやらないといけない!!! Rank torank; File tofile; for (int i = 0; i < 2; i++) { to = sq; do { to += Square(direc_rook_yoko[i]); torank = sqtorank(to); tofile = sqtofile(to); if (is_ok(to) && (to != sq) && (tofile == sqfile)) { LongRookEffect_tate[sq][obstacle] ^= SquareBB[to]; } //横や縦の関係であればこの方法は使えるけど斜めでは通用しないぞ...(射影すればいいだけ) } while ((!(obstacle2&(1 << torank))) && is_ok(to)&&(tofile==sqfile));//縦の場合はfileが同じかどうかも調べなければならない。 } } } //香車の効きテーブルの作成 for (Color c = BLACK; c < ColorALL; c++) { for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) { for (int obstacle = 0; obstacle < 128; obstacle++) { LanceEffect[c][sq][obstacle] = (LongRookEffect_tate[sq][obstacle] & InFront_BB[c][sqtorank(sq)]); //cout << LanceEffect[c][sq][obstacle] << endl; } } } /* よく考えると斜めもrankに射影してしまえば横と同じように処理できるか(´・ω・`) 横のほうが処理が簡単なので横で計算する。 */ //斜めプラス45度 //この方法では上から角の効きが伸びてきてしまうということが起こりうる!!(解決済み) for (Square sq = SQ1A; sq < SQ_NUM; sq++) { /*File sqfile = sqtofile(sq); Rank sqrank = sqtorank(sq);*/ for (int obstacle = 0; obstacle < 128; obstacle++) { int direc_bishop_p45[2] = { -10, + 10 }; int obstacle2 = obstacle << (1+additional_plus45(sq));//シフトさせる。 Rank torank; File tofile;//横方向への射影。 Square oldto; Rank oldrank; for (int i = 0; i < 2; i++) { to = sq; //tofile = sqtofile(to); do { /* oldtoを保持してoldtoとnewtoのrankが2つ以上離れないようにする。 */ oldto = to; oldrank = sqtorank(oldto); to += Square(direc_bishop_p45[i]); torank = sqtorank(to); tofile = sqtofile(to); if (is_ok(to) && (to != sq)&&(abs(torank-oldrank)<2)) { LongBishopEffect_plus45[sq][obstacle] ^= SquareBB[to]; } } while (!(obstacle2&(1 << (tofile))) && is_ok(to) && (abs(torank - oldrank)<2)); } } } //斜め-45度 for (Square sq = SQ1A; sq < SQ_NUM; sq++) { /*File sqfile = sqtofile(sq); Rank sqrank = sqtorank(sq);*/ for (int obstacle = 0; obstacle < 128; obstacle++) { //int obstacle_ = change_indian(obstacle); int direc_bishop_m45[2] = { -8, +8 }; int obstacle2 = obstacle << (1+additional_minus45(sq));// Rank torank; File tofile;//横方向への射影。 Square oldto; Rank oldrank; for (int i = 0; i < 2; i++) { to = sq; //tofile = sqtofile(to); do { /* oldtoを保持してoldtoとnewtoのrankが2つ以上離れないようにする。 */ oldto = to; oldrank = sqtorank(oldto); to += Square(direc_bishop_m45[i]); torank = sqtorank(to); tofile = sqtofile(to); if (is_ok(to) && (to != sq) && (abs(torank - oldrank)<2)) { //obstacleのbitを1を7に7を1にというように入れ替えなければならない。 LongBishopEffect_minus45[sq][(obstacle)] ^= SquareBB[to]; } } while ((!( obstacle2&(1 << (tofile)))) && is_ok(to) && (abs(torank - oldrank)<2)); } } }
そして使い方はこんな感じ
Bitboard long_effect(const Occ_256 & occ, const Color c, const Piece pt, const Square sq) { uint8_t obstacle_tate; uint8_t obstacle_yoko; uint8_t obstacle_plus45; uint8_t obstacle_Minus45; switch (pt) { case LANCE: obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask; return LanceEffect[c][sq][obstacle_tate]; break; case BISHOP: obstacle_plus45 = (occ.b64(2) >> occ256_shift_table_p45[sq])&effectmask; obstacle_Minus45 = (occ.b64(3) >> occ256_shift_table_m45[sq])&effectmask; return LongBishopEffect_plus45[sq][obstacle_plus45] | LongBishopEffect_minus45[sq][obstacle_Minus45]; break; case ROOK: obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask; obstacle_yoko = (occ.b64(1) >> occ256_shift_table_yoko[sq])&effectmask; return LongRookEffect_tate[sq][obstacle_tate] | LongRookEffect_yoko[sq][obstacle_yoko]; break; case UNICORN://馬のこと obstacle_plus45 = (occ.b64(2) >> occ256_shift_table_p45[sq])&effectmask; obstacle_Minus45 = (occ.b64(3) >> occ256_shift_table_m45[sq])&effectmask; return LongBishopEffect_plus45[sq][obstacle_plus45] | LongBishopEffect_minus45[sq][obstacle_Minus45]| StepEffect[BLACK][KING][sq]; break; case DRAGON: obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask; obstacle_yoko = (occ.b64(1) >> occ256_shift_table_yoko[sq])&effectmask; return LongRookEffect_tate[sq][obstacle_tate] | LongRookEffect_yoko[sq][obstacle_yoko]|StepEffect[BLACK][KING][sq]; break; default: UNREACHABLE; return ALLBB; break; } }
縦方向の効きは1段目9段目に邪魔ゴマがあっても1段目9段目に効きを作ることができるので縦方向occupiedbitboardは1段目9段目を表すbitを除いて7*9=63bitあればよく
横方向も1筋目9筋目のbitはいらないので7*9=63bit
斜めはそれぞれ7*7=49bitあればよいので
実はoccupiedbitboardはすべて256bitに収めることができ
これによって駒が動いた時のoccupiedbitboardのこうしんの処理はSIMD演算を使えば一気に処理できる
という工夫を使っているのでocc_256とかocc.b64(1)とかが出てきていて説明した内容とはちょっと異なるけど基本こんな感じでシフトしてマスク取ってindexを作って
そのindexを用いてテーブル引きをしているだけなのじぇ(飽きたのでおしまい)
mm100にっき
問題のリンク↓
TopCoder
とりあえず問題を見る。
これは厄介そうだな〜〜というのが第一印象。
特に斜め方向であっても矩形領域に別の色が挟まっていなければそれを取り除けるというのが一番厄介でここをどう処理するかがポイントになる気がする。
この処理の計算に時間を使いそうなので毎回は斜めを考慮することは出来ないだろう。これの計算のオーダーを下げるいい方法がないか考えてみるがあまりいい方法は思いつかない。
とりあえずナイーブな方法を取ればいいかと開き直ることにした。
マスの取り除き方は結構いろいろあるので焼きなまし的なことが出来ないかを考える。
しかしmove列のどこかを別のmoveに差し替えると次のmoveに影響が出てしまうため単純には出来ない。
探索を考える。しかし最終状態まで探索をしないと行けないのは結構きつそうなのでボツ。
典型には落とし込めなさそうだなぁと思う。
とりあえず方眼ノートと色鉛筆を用意する。実際に手を動かしてよさ気なアルゴリズムを探そう。
いくつか思いついた方法で手を動かしてみる
手を動かしていると
違う色のタイルが密集しているとそれを取り除くのはかなり大変になる。
あと真ん中のあたりのタイルは矩形領域を作るときに邪魔になりやすい。端っこは邪魔になりにくい。
という知見が得られた。
そして思いついた方法の中で一番よさげだったのは「一つの色について取り除けるところを全部取り除いてから次の色に移る」という方法だった。
そしてこれをどのように実装していくか考える。
とりあえず最初は斜めを考えずに、右上のますから上下左右で取り除けるマスを列挙していき、ランダムにマスを取り除いていくことにする。
そして斜めを考えずに取り除けるマスがなくなってしまった時斜めに取り除けるマスをすべて取り除く、そしたらもう一度上下左右で取り除けるマスを列挙していき取り除いていくことにした。
これが完全に取り除けるマスがなくなるまで繰り返す。
この一連の操作にどれだけの時間がかかるかと思ったがH,Wが小さいケースではそんなに時間がかからなかったのでこれを何回か繰り返してベストとなるmove列を見つける。
ここでmove列の評価はどれだけマスを取り除けたかで評価するが、どれだけmove列が長いかを見ればそれがわかるので全マスループを回さなくてもSZ(move)で済む。
これがちゃんと提出したののうちの第一投目。
ここで焼きなまし的なことを思いつく10s中最初の5sはランダムに探して次の5sは今のところの最善のmove列の前半n個を取り出して来てその続きをランダムに決める。
これを最初のランダムに施行する時間を調整しながら試してみたところ最初の1回だけランダムで後は最善から作ったほうがスコアが良くなったのでこれを提出。
seed 3がTLEするようになって非常に苦しんだがとりあえずスコアは伸びた。
ここでH,Wが小さいケースでは1iterationにそんなに時間がかからなかったとあるが、
むしろ逆にH,Wが大きいケースまたは斜めをたくさん考えないと行けないケースではiterationの時間が非常に大きく数回しかiterationを回せていないということがザラだったのをなんとかしたい。
またこれとは別に最善のmove列から前半n個を取り出すところにおいてどれぐらいのnを取れば効率的なのか知りたいということが出てきたので、
nを適当に変えてみてその時のmove列の長さをプロットしてみる。
H,Wが小さい時はnが小さい時もスコアがコロコロ変わるがnが大きいとスコアが変わるのはnがかなり大きい時だということに気がついた。
まあnが大きいと後半をちょろっと変えるだけなのでもともとの長さがそこまで変わらないのでそれはそうだ。
後半をちょろっと変えるだけならH,Wが大きくてiterationに時間がかかる時でも大した時間をかけずに更新できる。
これでが第3投目。
nを適当に変えるところで最初はnを小さくとり、前のほうから変化させ、だんだん前のほうを固定する方法を考えるが
さっき取ったデータからこれはあんまり意味がないかと考える。
今完全ランダムにしてるところをもうちょっとまともにしたい。
違う色のタイルが密集しているとそれを取り除くのはかなり大変になる。
あと真ん中のあたりのタイルは矩形領域を作るときに邪魔になりやすい。端っこは邪魔になりにくい。
これを優先的に取り除くためにマスのペアにスコアをつけてそのようなマスを優先して取り除くことにする。
しかし全然ダメ。この方法には可能性を感じていたというかこれはスコアが上がらないとおかしいと思ったので結構いろいろ試したのだがスコアは全然伸びないむしろ下がっている。
まあ一回失敗してしまってもアイディアをもう一歩深化させることを考え続けるがスコアは全く伸びず下がる一方である。
ここで蟻本を読んでみてアイディアが降ってくるのを待つ。するとマッチング問題を思い出した。
色のペアを作るのをマッチング問題の要領で見つけ出すことは出来ないだろうか???
今回は一般マッチングっぽいので一般マッチングについて調べてみる....簡単には出来なさそうだ...
簡単にはできなさそうだがアイディアは活かせるのではないかと思ってアイディアを盗むため一般マッチングについてのスライドを読んでみるがどう生かせばいいのかさっぱりわからないし
内容もさっぱりなのであきらめる。
こういうのに嵌ってしまうと良くない。
できることをするしかない。
しかし前回はそんなの出来ないだろと最初に諦めてしまった方法を他の人は使っていて、出来なさそうに見えても考えることは大事かもしれないが....
出てくるアイディアがどんどん雑になってくる。
全く根拠のない「これでうまく行くはずだ!」が増えてきて根拠がないにもかかわらず失敗したら落ち込んでいる。
もっと1日目のような丁寧な考察をしないといけない。
5分後に私は天才になってるはずだと思いながら根気よく取り組む。
アイデアを出して褒めまくるフェーズと
アイデアの実装方法を考えるフェーズと
アイデアを否定するフェーズに意識的に分けているのは前回の反省から。
またアイディアがうまく行かなくてもそれをもう一歩深化させることを心がけているのも前回の反省から。
順位表,Twitterを見るのを意識的に遠ざけて余計な煽りを受けないようにする。戦っているのはその人たちとではなく自分となのだから。(これも前回の反省から)
わりとしについて考える。
わりとしというと割と死にたいのことだと思うかもしれないがこれは罠で
虚無と交わり歳を取りたい
わりとC言語好きだよ
ひまわりとしんのすけ
くるみ割りと詩人
のどれかのことだ(いいえ)
ここで情報を詳しく書き出すことにする。
そうするとiteraionが大きく下がっていることに気がつく。
う〜〜んやはりどれだけiterationを回せるかのゲームなのか....?????
しかしCOM将でも強くなる時は遅くなる時ということばがあるように(meromさんがそう言っていただけのことをコンピューター将棋界にそういう言葉があるように言うのは主語を広げすぎ)
iterationが低くなっても強くなる方法はあるはずで他の人はそれに気がつけていると思うんだが.....
まあ2コマ関係から3コマ関係に変えた途端弱くなるソフトの作成者なのでこのあたり本当に苦手だ....
とりあえず速度を落とさず良くなるのではないかという方針として今は山登り的に命令列を計算しているので焼きなまし的にしてみる。しかしうまく行かない。
ちょっとパラメーターをいじってると以前と同程度(ちょっと低い)のスコアが出るプログラムが出来た。
これを提出する。思いっきり下がった。泣きそう。わりとし。
ナナメを最後に考えてるのがよくないのかもしれない。
色のついたマスが少なくなってきたらナナメも同時に考えるようにしたが結局iterationが下がってスコアは伸びない。
もう高速化して細かいスコアを手に入れるしかないのではと思い、とりあえずメルセンヌ・ツイスタを使っていたところをxor128で書き換える。
するとseed19が思いっきり下がった。ほんとにseed19,14,4が厄介で厄介で仕方ない。
というか擬似乱数生成器をちょっと変えただけで爆下がりしてるんだからこれほんと今のスコアoverfittingでしかないでしょ。
笑うしかない。システムテストで大幅下落する未来しか見えない死死s死
精も根も尽きた。まだ精は尽きていないのではないかと思ってとりあえず致そうとしてみるが駄目だった。精も尽きていた。
ーーーーー感想戦ーーーーー
工事中....
疲れていて他の人の方法を読む気力が残っていない....
疲れがひどいが無理矢理読んでいく。
hakomof.hatenablog.com
終了後焼き鈍しを使ったというツイートを見てもどのようにして焼き鈍したのかさっぱりわからんかったがこれを読んだらわかった。
すごいなこれ。
解となる操作列をそのまま焼き鈍したのでは順序関係が壊れてしまって焼なませない。
そこで消すペアと消す順番を分けて考える。
とりあえずこのマスとこのマスを消したい!というペアを消せるか消せないかにかかわらず作っておいて
この消すペアの集合を焼きなましの状態として、スコアはペアを貪欲をして消していった時にどれだけペアを消せるかになる。なるほど。
焼き鈍し方はよくわかったけどいかんせんアルゴのちからがないので依存グラフやトポロジカルソート、バイナリ空間分割の話はわからなかった。
SAT充足可能性問題。そんなのがあるんですか。
こちらも有効性判定述語とかよくわからないので途中で読むの投げてしまった。
MM100
— iwashi31 (@iwashi31) 2018年4月26日
・乱択
・消えにくいセル優先
・後半はラスト50~200手のみ繰り返す
・高速化を頑張る
そうか「消えにくいセルの性質はこうだ!」みたいな感じで優先条件を考えてたけど何回も試せるんだから試してみることでもっといい消えにくいセルの情報が手に入るのか。
終盤は盤面が疎になるので非空セルの情報を Dancing Links で保持してあげると割と速くなった
— iwashi31 (@iwashi31) 2018年4月26日
知識不足なのでわからんがそういうデータ構造があるんですか。
TopCoder Forums
bestmove列以外のmove列もpoolに保持しておく方法ですか。
これMM97の時にやったことがあって、その時にスコアがちょっと伸びたんだけど結局ほかの人がしていた多点焼きなましに比べて弱かったのであんまりよくないと思ってしまっていた。
やはり問題によってあんまりよくなかった方法が有効になったりする感じですかね。
う~~ん
今回は失敗してもその失敗から知見を得て次の方針を得るということが出来なかったように思う。
次はそれを心掛けていこうな。
あとマラソンのシステムとかビジュアライザとかを整えていきたい感が強い。
名前が付いてないテクニックを人は天才以外お断り要素だと言ってしまいがちだけど、そんなことはなく典型化できる要素なんだよなぁ。これは「ゲーム系は後ろから」みたいな考え方のテクニックに多い。
— ꑄ꒖ꐇꌅꏂ (@snuke_) 2018年5月1日
解けなかった問題からこういう名前の付いてないテクニックを吸収するコツは、「どういう風に考えれば思いつけたのか」っていう研究を「解法を忘れた状態から考え直して解法に辿り着ける」ようになったとなと満足できるまでやること。
— ꑄ꒖ꐇꌅꏂ (@snuke_) 2018年5月1日
■
東方紅魔郷 エクストラクリアできました
www.nicovideo.jp
いやーーーうれしいですね。今日一日ひたすら興奮してました。
東方紅魔郷買ったのは高校生の時なんですが、そのときからずっとエクストラクリアできずに投げ出してしまっていたんですよ。
安定したチャートを組み、ちゃんと弾幕のパターンを認識し、避けなければならないところを確実に避け、アイテムを使うところはちゃんと使うということができればクリアできるもんですね(´・ω・`)
おまけ
www.nicovideo.jp
感想戦
〜〜〜僕の感想~~~
問題文を読んだ瞬間「どう見ても多腕バンディット問題です。本当にありがとうございました。」だったのでucbとかsoftmaxとかを考えた。
とりあえずnotePlayはせずにucbまたはsoftmaxだけを使ってプレイしてみて探りを入れる。
ばらけさせ方が小さいとあんまりよくないのをひたすら回してしまい、ばらけさせ方が大きくなると一番いいのがわかったぐらいで残り時間が無くなってしまうということが言いたげなデータが得られた(まあそれはそう)。
ここでnotePlayの出番だなということを察する。
最初に何回かnotePlayをすべてのマシンについて回してからucbやsoftmaxを使ってプレイさせてみる。全然よくならない。
パラメータが悪いのだろうか?それともnotePlayによる事前期待値から実際のプレイによる儲けの期待値に移行するのがうまくできてないんだろうか?と考えていろいろやってみる。しかし全然よくならない。
sofxmaxの温度項を多点焼きなましっぽくして探索と活用のバランスを取ろうとしてみる。しかし良くならない。
ucbやsoftmaxに囚われすぎている気がしたので方針を変えてみる。
{全台について何回かnotePlayをした後、一番期待値が高いのを実際にQuickPlayをする}を数回繰り返して、そこから先は一番実際にプレイしたときに出が良かったスロットをひたすら回すことにした。
単純すぎる方法だけどこれが一番スコアが高くなった。(こんなクソ方法に勝てないのは非常にツライ。)
kaggleでちょっとpandas触ったので、pandas使ってデータをプロットして可視化ということをしてみたが
そういうことよりも数個の環境における時系列的な結果をしっかり追って行って何が起こっているのか見たほうがよさそうだったのでデータサイエンティスト気取りはやめた。
時系列データを眺めてみると一番期待値の高いスロットに気が付けているが探索を続けてしまっているということが起こっているので
探索打ち切りの条件を入れてみたが、うまい条件を考えられず結局スコアは落ちる。ここからもいろいろ考えて改良を加えたり、多腕バンディットについてググってやってみるも下がる一方だった。
スコアが下がる一方だったのと手元またはExampleテストではスコアが上がるがフルサブでは下がるというのが繰り返されモチベーションが死んでしまい虚無になった。
きったねぇlogファイルを眺めてても時系列的にどうなってるか理解は深まらずストレスしかたまらん。もっと見やすくためにビジュアライザを作ればよかったという後悔が残るがビジュアライザわからん..みんなやっぱJavaで作ってるんだろうか...
〜〜〜他の人の解法を読んで〜〜〜
作成中
ローカルでの評価,期待値最良台の期待値を e として理論値を coins + max(0, e - 1) * maxTime で計算してそれとの割合を出していた
— ㅤ (@my316g) 2018年3月23日
ローカルでは実際のスコアではなく∑(各スロットの回した回数×真の期待値)、で評価してた。最終サブミットで、上限(期待値最大にquick全ブッパ or なにもせず終了)に対して94%とかだったはず
— yowa (@yowa) 2018年3月23日
ただスコアそのものしか見ていなかった....(´・ω・`)
やったこと
— つっつ (@threepipes_s) 2018年3月23日
前半noteplayしてリール期待値出す
後半はUCB方策でquickplay
リール期待値は、焼き鈍し or bitDPでリール復元
noteplay少ないスロットにはリール生成頻度で確率補正
リールの予測、とりあえずNotePlayで見たやつを繋げて、最短になるものがベストという焼きなましにしたけど、重複した見えた部分がほんとうに2つあるのか、それとも同じ部分を見たのか、最短が必ずしも正解になるとも限らず、そうなると他のリールの長さもヒントに…とか考えると、めんどい。
— nico_shindannin (@nico_shindannin) 2018年3月23日
もうnote_play()じゃ新情報得られなそうと判断したら不明な部分を最尤で埋め。全マシン50回くらいサンプリングして推定regret出して、noteTimeとのバランス見てquickのみに切り替え
— yowa (@yowa) 2018年3月23日
note_play()して得た情報を最短でつなぎ合わせ(TSPを分枝限定法で)、不明な箇所はランダムな文字で埋めて期待値をサンプリング、最大なマシンをプレイ
— yowa (@yowa) 2018年3月23日
リール期待値、予測の出し方がプロでしょプロ。僕はただnotePlayの結果的に良さそうな感じなのを選んだだけです
あと仮想的にハリボテのスロットマシン(100%の確率で1枚払い戻される)も選択肢に入れた。実マシンが期待値1を下回るものばかりだったらこのハリボテに時間が使われる(実際には時間をたくさん余して終了する形)。期待値1超えるマシンがあるなら、ハリボテに費やした時間を最大なヤツで消費しなおし
— yowa (@yowa) 2018年3月23日
なるほど賢い
まんま Multi-armed Bandit Problem だったので Thompson sampling っぽいことをした
— yowa (@yowa) 2018年3月23日
なんか他にもトンプソンサンプリングしてる人が結構いてるなぁ。
ucbとsoftmaxがうまく行かなかったのでトンプソンもそんなにうまく行かないでしょとおもってしまったのでやらなかったのを後悔
前半は UCB 値使って notePlay、後半は一番良かったやつを quickPlayでした。
— iwashi31 (@iwashi31) 2018年3月23日
後半に移る前には一番良いスロットの wheel 情報で 10 回プレイアウトしてみて、期待値が今のコイン数以下なら後半は端折ります。
そうか前半にucbを使うのかその発想はなかった
UCB で使う各スロットの試行回数は単純に回した回数でなく、今までに得られた wheel 情報を重複排除した後ひとつなぎにして、それら 3 本の長さの積(つまり、取り得る組み合わせ数)の値を使ってみた
— iwashi31 (@iwashi31) 2018年3月23日
ただこれだと 3 本とも以前の情報と重複しちゃったときに UCB 値が変わらず回し続けるみたいなことになるので、別途スロット回した回数も式に加えるみたいな真心をした
— iwashi31 (@iwashi31) 2018年3月23日
なるほどnotePlayで得られた情報量的をこのスロットの試行回数とみなすのか 賢い
おつかれさまでした
— hakomo (@hakomof) 2018年3月23日
noteを13-40回。リールの隣接共通部分を重ねた全長が最小になるよう並び替えの山登り。それで推定したリールからtesterと同様に期待値を計算。一番良かったmachineにquick
・note回数は推定リール長*1.3とした(ある精度を出すために必要なnote回数はリール長に比例するので
— hakomo (@hakomof) 2018年3月23日
・あるmachineの期待値<現ベスト期待値*0.8になったらあるmachineのnoteを枝刈り
・推定リール長の短いものからnoteする(短いほうが期待値が暴れやすく、高めが早く出やすいので枝刈りが加速
・3回山登りして期待値が中央値のリールを推定リールとした(1回山登りや1回焼きなましより良かった)
— hakomo (@hakomof) 2018年3月23日
・左中右のリール長がずれてたら埋めるやつ、generatorの確率で埋めるのとnote結果で埋めるの両方試したけど下がった
他の人もいってるけど推定リールを求めるための焼きなましってどうするんだ...??
notePlayで得られたじょうほうからリールが繋がるように並べ替えるということか??
wheelの長さは、「本当の長さがLで note_play() をn回すると k種の異なる結果が得られる確率」みたいな式からベイズって、重み付きサンプリング or 最尤推定した。
— yowa (@yowa) 2018年3月23日
観測した文字列をつなぎ合わせる段階では、同じのをまた観測しても無視してた。確率で別箇所としてカウントしたかったけど、つなぎ合わせのTSPがけっこう重い&時間予測できない感じだったので、あんまりつなぎ合わせ処理を呼びたくなかった。
— yowa (@yowa) 2018年3月23日
最後に最尤推定するときには出現回数もつかってる
最初はquick_play()だけで、Thompson samplingしてた。多値だから Beta じゃなく Dirichlet 分布でやってたけど、事前分布はどう定めるのが通例なんだろう。各払い戻しが出る確率に比例した値で、比例定数はテストケースのスロットマシン分布から多数サンプリングして最尤になるように定めたけど
— yowa (@yowa) 2018年3月23日
あくまで Multi-armed Bandit の枠組み(探索と収穫のジレンマ)で考えてたけど、
— yowa (@yowa) 2018年3月23日
多くのケースで note_play するのは全体に対して短い期間なんだから、収穫は後の quick_play にまかせて、note_play フェイズでは報酬のことはあまり考えず少ない手数での分布特定に重きを置く方が良かったのかなあ
wheel の長さは本当は L なんだけど、重複があって最大 k 種しか観測できない確率、衝突確率を p とすると、L-k の分布がパラメータ p*L(L-1)/2 のポアソン分布で近似できて、そりゃそうだよなあとか思った
— yowa (@yowa) 2018年3月23日
確率 統計を使いこなしている感じすごいなぁ
リール推定僕も最初ちょっと考えたんだけど、いやリールの長さもわからんし難しそうだから無理でしょと思ってしまった。
ベイズを使うのも難しそうでどう使えばいいかわかんなくてトンプソンサンプリングがベイズを使ってるとの事だったからそれで満足してしまっていた。
いや〜〜〜〜他の人に見えていて私には見えていなかったものが見えてきて興奮している。楽しいですね。
しっかり復讐しよう。
■
あなたの目の前に薄汚れたメモが落ちている...
あなたは拾って読んでみることにした
毎回一つの方法に凝り固まってしまう。今回も『強い人は多分こういうことをしてるはずだから僕もそれを目指そう!』とずっと思っていたけど強い人は全然そんなことはしてなかった
その方法にずっと固執してしまってそれの調整ばかりになってしまっていた
最初に5ぐらい取れてしまって新しい方法を取ろうとしなかった。局所解にハマるのはいつも私の脳みその方だ。毎日頑張ってるつもりなんだけどイマイチ達成感が感じられないときって、一番やらなくちゃいけないことをやらないで、忙しいふりをしているから。まずは心に引っ掛かり続けてるそれを、勇気をだしてガン見するところから。それだけで1日終わったって良い。忙しいふりするよりずっと良い。
— ひらめきメモ (@shh7) 2018年2月22日
本当に改善すべき難しい問題をちゃんと見つめる勇気を持てず、些細で簡単なことばかりいじって頑張ったつもりになっていた。
私はいつも難しいことから目をそらして無駄で簡単な所ばかり弄って頑張ったつもりになっているだけなのだ。
無駄すぎる良くない努力をして自分は頑張ったと思いたいだけなのだ。僕は将棋ソフト開発を頑張ったことはありません。というかあらゆることに対して頑張ったことなし
— sako@海底 (@kaitei_shogi) 2018年2月21日
苦しんでできる程度の努力では何も成せない。
— merom686 (@merom686) 2017年12月3日
頑張ったことがないというのは無駄な努力ばかりに価値を見出してしまっている私とは全然違う。
しかし海底さんのブログを見るととても勉強されていて私の目では頑張っているように見える。
息を吸って吐くように努力ができる人なのだろう。
敵わなさを感じる。
あなたは薄汚れたメモに書かれた内容がよくわからなかったので
そっと元の場所に戻した
■
輪をかけて秘密主義とほかの人にいわれることがあったので。
確かにそんなところあるなぁ。
強くなるまでロムっておこうという小心者的な気持ちが大きい。
弱いところは見せようとしないから実力以上に見られて困ってしまうことが多いんだろうなぁ
何をしているかどんどん発信してどんどんクラスタに飛び込んでいくことも大事だと思うので
ちょっと勇気を出してみる(この勇気を出すのに数日かかっている)
研究は今は量子カオスについての研究をしてます。でも量子カオスについて詳しいというわけではないです。研究に使うことだけ。
僕の学科は半導体とかパワーエレクトロニクスとか電気回路の授業が多く、物理学科的な授業は少なかったしそこをちゃんと理解したいと思って最近はそういうことを本で勉強してます。今はJJサクライとリー群の本読んでます。
競プロは弱いですACO緑 TCO MM青です
kaggleとCodingameは登録だけ。
Unityでゲーム作ったりもしてます。難しいことは全然できません。
今は特殊能力付きリバーシを作ろうとしてます。次の案としてはフリック入力練習ゲームかな...
コンピュータ将棋ソフト開発も昔は頑張ってました。
絵の練習もちょっとずつしてます