アルゴリズムの中でビームサーチA、ACOにおいては、
開発環境がMicrosoft Visual Studio Enterprise 2015、使用言語はc++です。
動かなかったらNugetでVS用のboost入れてください。
あと、サーバに自動で解答を送る場合はcurlいれてパスを通してください。
makefile作っていたのですが、途中でlinux環境から切り替えてしまったため、
追従できていません！ ごめんなさい！
ビームサーチB、問題・解答管理サーバではD言語とdubを入れるだけ。簡単！ みんなもD言語始めよう！
（呉高専の方、来年も期待しています）
当日はPC3台の他にスイッチングハブ1つとLANケーブル3つ、必要に応じてUSB-Etherのケーブルを用意しました。
D言語PCにビームサーチアルゴリズムBと問題・解答管理サーバを担当していただき、
問題の取得、スコアが更新されたときのみの提出を行っていただきました。
他2台のPCでそれぞれ別のアルゴリズムを走らせ、D言語PCに問題寄こせだ提出だをした構成です。
- 概要
ビームサーチです。ただ、少し工夫して解にランダム性を持たせています。 評価関数の仕様により、障害物が多い問題に対して非常に強く、逆に障害物の少ない問題 （例.準決勝2問目のサイコロや、練習場の41番(初心)）に対して非常に弱いです。 参考までに、準決勝第3試合2問目のサイコロのスコアは70程度でした。
- 工夫した点
敷地を状態として、石を順番に置く遷移を行うのですが、状態を格納する優先度付キューをA、Bの2つ用意しています。 ある状態に対して、石をどこかに置いた場合キューAに格納されます。 石を置かなかった場合、キューBに格納されます。 また、キューAでは評価値の良い順に解が選ばれますが、キューBでは解の選択を完全にランダムに行っています。 これにより、石をパスする解が出現しやすくなっています。
敷地は32bit*32bitのビットマップで保持しています。 ビット演算を用いることにより、その場所に石が置けるかどうか、既に置かれた石に接しているかの 判定が高速に行えるようになっています。 また評価値もビット演算とpopcnt命令を使用して高速に計算しています。
評価値は、石があるマスと無いマスの境界線の長さの総和を使用しています。
- 開発者からのコメント
今回の競技では、アルゴリズムによって問題の得意・不得意がはっきり出ていたと感じました。 得意な問題のタイプが異なるアルゴリズムを複数用意しておくと、有利に戦えたのではないかと思います。
- 概要
現状態から3手先まで石を適用した場合のヒューリスティックスコアを集め、ルーレット選択します。その中で最終的に良いスコアをとったルートに多くフェロモンが付加されるようにしていきます。次回以降、フェロモンがある方のルートを選択しやすくなります。その繰り返しで探索空間を狭めていきます。簡単、たぶん。GAより。
当該アルゴリズムに直接関係する部分はAlgorithm/Ritalgo, Algorithm/detail/Ritalgo, Rita/main.cppになっています。
Rita.exe [D言語PCのIPアドレス]で本番環境と同様になります。引数なしで実行すると、問題のテキストを標準入力で受け付ける状態になります。
- 工夫した点
よいヒューリスティックを探していました。最終的には↑のアルゴリズムの作成者（@foldori）のヒューリスティック情報を参考にさせていただきました。
- 開発者からのコメント
ACOは貪欲である程度のスコアが出せるときに、さらなる最適化が期待できます。初めて聞いたという方もいるのではないでしょうか。ながめていてかわいいアルゴリズムなので、ぜひ実装してみてね。まあ本番では一番スコアが悪かったのだけれどもね。馬鹿と鋏は使いよう、皆さんが実装すると良いスコアになるかも。
- 概要
D言語で書きました。
アルゴリズムはビームサーチですが、かなりヘボいです。
1週間しか開発期間なかったし仕方ないね！！
得意な問題はありません。
- 工夫した点
D言語で書いた、ということ以外に工夫はしてないです (工夫できてたらもう少しいい成績残せてはずですし…)。
- 開発者からのコメント
D言語で書きました。
変なライブラリは特に使ってないので、コンパイラ(DMD)とDUBさえ入れれば、WindowsでもMacでもLinuxでも動くと思います、多分。
ビルド+実行は、DMDとDUBを入れた後dlangディレクトリ上でdubでOKです。
- 概要
最後に提出した有効解答がそのチームの結果になる、という今回のルール上、複数台のPCで解く場合には何らかの制御が必要です。
dserverは、複数のPCからの解答を集約し、その時点の最良解答のみを提出するHTTPサーバです。
D言語で、vibe.dというライブラリを使用して書きました。
エンドポイントは以下のようになっています。
-
/helloサーバが正常に起動しているかをWebブラウザで確認するためのものです。
GETです。
アクセスするとhello, world!が返ってきます。 -
/problemクライアントが問題を欲しい場合にGETしに行きます。
管理サーバ側は、初回は競技サーバに問題を取りに行って、2回目以降はキャッシュしてあるものをクライアントに返します。 -
/updateクライアントが管理サーバに解答を投げつけます。
POSTです。
管理サーバは、投げつけられた解答が今までで最良であれば、競技サーバへ提出します。
また、直前1秒以内に別の解答をすでに提出していた場合、競技サーバへの提出を1秒延期したり、すでに延期されている状態でさらに良い解が出た場合には延期している解答を新しいものにすり替えます。
- 工夫した点
工夫はしてないです。
あえて工夫をした点を挙げるとすれば、やっぱり「D言語 + vibe.dで書いた」ということですかね。
- 開発者からのコメント
突如前日に急いで作ることになりました。
vibe.dの使い方がわからなくて死んでましたが、なんとかなりました。
本番でちゃんと動作するのかヒヤヒヤでしたが、正常に動作していたようです。
これも変なライブラリは特に使ってないので、コンパイラ(DMD)とDUBさえ入れれば、WindowsでもMacでもLinuxでも動くと思います、多分。
ビルド+実行は、DMDとDUBを入れた後dserverディレクトリ上でdubでOKです。