第28回高専プロコン競技部門に出場しました

タグ
スライド概要

第28回高専プロコン競技部門に出場した話を沖縄高専ICT委員会のLTで話したときのスライド

profile-image

kurokoji

@2859534286

作者について:

Twitter: https://twitter.com/kur0k0ji

スライド一覧
シェア
埋め込む

作成日

2021-03-16 19:31:38

各ページのテキスト

1. 第28回高専プロコン 競技部門に出場しました Shu Kakihana(4-mi)

2. 結果

3. 一回戦1位通過🤣(イェーイ)

4. 準決勝15位敗退😭(カナシイ)

5. 今年の競技部門はどんなやつ(簡単に) • A4サイズくらいの木の板のわくが与えられる • わくにピースを埋める • ピースやわくの頂点情報などはQRコードによる ヒントとして使用できるが,減点される • 全てのピースを埋めれば100点,ヒントを使うと そこから減点される(形状情報: -10, 位置情報: -20) • 全てのピースを埋めることが出来なければ0点

6. 開発する必要があるもの • • • パズルソルバ • その名の通りパズルを解くためのプログラム • C++で実装 GUI • 最終的にパズルを組むのは人間 • 人間にわかりやすいようにピースやわくを表示 • Javaで実装 QRコード読取機 • ヒントであるQRコードを使うため • C++で実装

7. パズルをプログラムで解く • どんなアプローチ? • わくの各頂点の角度に合うピースを探す • 埋める • ピースとわくをマージして次のわくとする を繰り返す • 普通の全探索だと状態数多すぎて死ぬ • いい感じの評価関数でビームサーチやれば割りと短時間 で解けそう(本番ではChokudaiSearchを使用)

8. パズルをプログラムで解く • 幾何パートやりたくない… • つよいC++ライブラリ,Boostで解決 • 図形のマージ,面積計算,交差判定とか諸々

9. 枝刈り • わくにおいて任意の辺の長さが4グリッドより小さい辺 • 全てのピースの最小角より小さい角 が出たらそのノード以降の探索打ち切り

10. 評価関数 • 評価関数 • 探索していく上で今の状態を評価し数値化 • 埋めた頂点に接する辺が一致していたら 評価を上げる評価 • フレームの凸包面積が小さければ評価を上げる

11.

12. 試しにサンプルでやってみる

13.

14. だめだ〜〜〜〜〜😫😫😫😫

15. 1回戦前日夜までこの状態

16. 必死になってバグを探す • ピースを反転したときの座標が反時計回りになっていた • • boost::geometry::correct()で直す それでもうまくいかない • Boostの都合上,辺と辺で囲まれた角の角度を求める とき,一方の辺の座標を反転をしないといけなかっ たっぽい • 座標反転は自前で実装

17.

18. Yeah~~~~~~👍 👍 👍 👍

19. 10秒くらいで完全解が出てビビる • 完全解が出た瞬間はめっちゃ嬉しかった • ここから少しパラメータをいじったりして寝た

20. 1回戦に臨む • 意外にいいところまでいけるかもと思いながら会場に 向う • 何故か1位を取れてしまう • ぼくら以外のチームは位置情報を使っていて減点されて いた

21.

22. プログラム上で完全解は出なかった • 残りの部分は人力で埋められるレベルだった • なぜうまくいかなかったかわからなかった • • ホテルに帰って考察しているとpureが問題点を指摘 • 180°が出来てしまったときに探索が止まるっぽい なるほど〜と思いながら修正しようと思ったが 実装がわからなくなって結局あきらめて寝た

23. 準決勝 • 案の定そのケースにぶち当たってデタラメな結果が帰っ てきた • 仕方がないので諦めてヒントを全部開け人力で埋めた • 15位

24. 改善法 • 都立品川の解法的なのを盗み聞きすると • 90°がなるべく出ないようにすると割りと良い解が でるらしい • マルチスレッド化 • 最初にピースを置く場所を変えて複数のスレッドで 走らせればよかった

25. 感想 • 解けると,楽しい • C++の理解が深まった • Boostは強い • 一人で全てを抱えるとしんどいのでタスクを振ろう • 競技部門やりたい人があまりいなさそうなので 興味ある人はぼくに話しかけてください