ZK finder
- 1. ? @tkhrotn ? 石川高専卒 ? 第14回課題部門，第15回競技部門に出場 ? 高専カンファレンスにも参加 （最近は出れてないけど…） Zero blanK finder 全国高等専門学校プログラミングコンテスト OB戦 #procon26 #procon26ob #kosenconf
- 2. 実行画面
- 3. ソルバの構成 ? データ構造 ? ビットボード ? 64bit整数型の変数で石を表現 ? 64bit整数型6×6の配列で盤面を表現 ? 衝突判定などの基本的な処理を全てビット演算で行う ? 探索アルゴリズム ? ビーム探索 ? 貪欲法（プレイアウト）による状態評価 ? スコアの下界計算による枝刈り ? 空白マス数と石の集合で構成される部分和問題を動的計画 法で解く ? 孤立マス (3マス以下で作られる空白マス) を残りの小石でいく つ埋められるか計算
- 4. ビットボード表現 ? 1つの石を64bit符号なし整数型で表現 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 ??? 0 64bit 8 8
- 5. ビット演算による各計算 ? 障害物との衝突判定 ? 配置済みの石との接触判定 ? 石を配置するときの接触辺数の計算 ? 空白マス数（スコア）の計算 ? 孤立マス数の計算 この2つの高速化が 特に重要！ 1マス 2マス 3マスL形 3マスI形
- 6. 探索アルゴリズム ? ビーム探索 ? 最良優先探索のキュー容量を制限したもの ? キューに入りきらないノードは枝刈り ? 貪欲法（プレイアウト）による状態評価 ? 接触辺が多い＆孤立マスが少ない配置を選択 ? 両者の優先度を変えることで探索傾向を調整 ? 計算量が大きいので，1手先の評価で予め枝刈り ? スコアの下界計算による枝刈り ? 空白マス数と石の集合で構成される部分和問題を動的 計画法で解く ? 孤立マス (3マス以下で作られる空白マス) を残りの小 石でいくつ埋められるか計算
- 7. 並列処理 ? プレイアウトの傾向が異なるビーム探索をマルチ スレッドで実行 1. 接触辺数の多さを優先 2. 孤立マスの少なさを優先 3. 枝刈りせず全ノードをプレイアウトで評価 (接触辺数を優先) ? 各スレッド間で最良解の情報を共有
- 8. 開発環境と実行環境 ? 開発環境 ? Cygwin on Windows 7/8.1 ? g++ ? gprof ? gdb ? Sublime Text 3 ? SourceTree (Git) ? コード行数：2000行ぐらい ? 本番環境 ? CPU: Intel Core i7-3517U (2core HT) Mem: 8GB ? Ubuntu 14.04 LTS ? bash ? cURL