TCO17 MM Poland > Poland Lightning Round

TCO17 MM Poland > Poland Lightning Roundに参加した感想です

ルール

S*Sのチェス盤の各セルに0~8の数字が書かれていて、
チェス盤上に複数のチェスナイトを配置して、各セルを攻撃するナイトの数ができるだけこのセルに書き込まれた数に近づくようにする

１日目

初めてのMM参加で仕様が分からず、診断人さんのTopcoderMMの記事を読んで勉強
まずはスコア計算用にシンプルなものから着手してました

• 公式ビジュアライザーの-size設定がうまく行かなったので修正 合わせて実行結果にS値も表示するように変更
• ナイトが置かれていたら取り除く、無かったら置いて スコアが悪くなったら元に戻すのが意外と強かった
• ビームサーチ実装したものの、次の世代の候補としてS^2個ストックするようなプログラムだったので失敗
• 焼きなまし法は小さいサイズに対しては強く、S>200ぐらいになるとスコアが収束する前に終わってしまった
  

2日目

• ある一点からナイト攻撃対象の8マス間で2点間のナイトスワップが効果あった
• １日目に実装した単純にナイトを置く、取り除く方法を行ってスコアが固まってきた際に↑の処理を入れることでスコア改善
• 状態を一気に変更したい!とGAを実装 スコアが良くなるけど収束するまでに時間がかかって↑のプログラムほど強くはなかった
  

3日目

• なにやってもスコア上がらない!! 　若干のリファクタリングとパラメータ調整でちょっとだけスコア伸ばす
• １日目のビームサーチを１つの親から1つの子を生成するように変更、またランダムにn個初期状態を生成して使うように、nの数はそのサイズでも100回は回せるように調整(S:50→89,100→22,150→9ぐらい)
• ↑ラストサブミット
  

感想

状態数が大きいけど偶数、奇数マスで完全別個に考えられるので考えるべき状態数は減りそう
ある程度まとめてナイトを動かす方法があったらよかったかも
スコア更新する際に、周囲8マス見ずに処理する方法考えてたけど思いつかず。。。

最終サブミットのExample scoresはこちら

Example scores:
0) 23.0
1) 598.0
2) 91443.0
3) 3692.0
4) 5228.0
5) 21143.0
6) 23753.0
7) 64220.0
8) 44322.0
9) 25304.0

GitHub

追記: TLみてると焼きなましが正解だったぽい １回試してるのでこれは完全に実装と高速化の技量が足りかなったですね。。。。