「ヒューリスティック探索入門」のメモ
「ヒューリスティック探索入門」というPDFの1章、2章、4章の一部の学習メモです。
特に、「状態空間問題」といった問題設定や用語について認識できたこと、A*法の理論などについてとても勉強になりました。
(PDF) https://jinnaiyuu.github.io/pdf/textbook.pdf
(Github) https://github.com/jinnaiyuu/search-ja
できる限り元のテキストに沿っているつもりで、私の意見や考えは青字としています。誤りなどありましたら教えて下さい。
1章 イントロダクション
このPDFの主な対象は、状態空間問題
(state-space problem)。
特に、状態空間問題のうち完全情報
かつ決定論的
モデル
状態空間問題
とは、与えられたゴールに到達するための行動の列(=プラン) を発見する問題完全情報
とは、エージェントが世界の状態を全て観察できるモデル
不完全情報
とは、エージェントは世界の状態を知ることはできないが、観察して世界の状態の一部を知ることができるモデル決定論的
とは、エージェントの行動によって世界の状態がどのように遷移するかが一意に定まること
非決定論的
とは、一意に定まらないこと
(行動に応じて状態の候補のいずれかに確率的に遷移する場合や、別のエージェントがいてその意思決定が状態遷移に影響を与える場合など)
参考文献
Judea Pearl の Heuristic
https://www.amazon.com/exec/obidos/ASIN/0201055945/acmorg-20
Stefan Edelkamp and Stefan Schrodl の Heuristic Search Theory and Application
https://www.amazon.co.jp/dp/B0058NBJCW
Stuart Russell and Peter Norvig の Artificial Intelligence
https://www.amazon.co.jp/dp/B01HEY2P66
Malik Ghallab, Dana Nau, and Paolo TraversoのAutomated Planning and Acting https://www.amazon.co.jp/dp/B01JGMDWRA/
2章 状態空間問題
状態空間問題
状態空間問題
とは、以下の問題である。
以下が与えられ、
状態
の集合初期状態
ゴール状態
の集合アクション
の集合。アクション
は、ある状態を別の状態に変換するものコスト関数
。コスト関数
は、アクションごとのコストを表す関数で、コストは実数。
(なお、コスト関数が定数である場合の問題は、ユニットコスト状態空間問題という。)
以下を解として返す。
- 初期状態からゴール状態へ遷移させるアクションの配列
ここで、アクションの配列のコストは、各アクションのコストの和である
なお、状態空間問題は、グラフの形で考えることができる。(というか、解くにあたってはグラフで考えるしかないような気がする)
状態空間グラフ
(=状態空間問題を表すグラフ)は、各状態を頂点、アクションを辺、コスト関数を辺の重みとしたもの- 状態空間グラフにおいて、アクションの配列は経路、アクションの配列のコストは経路の辺の重みの和となる。
- 探索する際に、状態空間グラフのノード・エッジ全てを保持する必要はなく、またメモリなどの制約から全てを保持できない場合もある。全てのノード・エッジを保持している場合を
明示的状態空間グラフ
、ルールなどの関数で表す場合を非明示的状態空間グラフ
という
状態空間問題の問題例
- グリッド経路探索
Web上のデモ:http://qiao.github.io/PathFinding.js/visual/ - スライディングタイル
15パズルなど - 多重整列問題
- 倉庫番
- 巡回セールスパーソン問題
問題の性質・難しさ
問題の難しさを左右する要素は以下のとおり:
- 状態空間の大きさ
- 分枝度
- デッドエンド
- 解の存在
関連する問題
以下のような関連する問題がある:
マルコフ過程問題
(Markov Decision Process Problem) (MDP)部分観測マルコフ過程問題
(partially observable Markov decision process problem) (POMDP)- MDPからさらに不完全情報問題に拡張したもの
- 多くの場合厳密計算は困難なので、モンテカルロ木探索などの近似手法が用いられる
敵対するエージェントがいる問題
4章 ヒューリスティック探索
ヒューリスティック関数とその性質
ヒューリスティック関数
(h値
)完璧なヒューリスティック
許容的なヒューリスティック
- すべてのノードについて、h値が正しい最短コストh*以下である場合、許容的であるという
- 緩和問題を解くことで許容的なヒューリスティックが得られる。 緩和問題とは、元の問題の解を含む問題をいう。( 例えば、元の問題では存在しない辺を加えたものなど)
無矛盾なヒューリスティック
- 全てのノードのペアについて、$h(u) <= h(v) + k(u, v) $ が成り立つ場合、無矛盾なヒューリスティックという
ここで、$k$は$u$から$v$への最小コスト - つまり、出発するノード$u$のh値から経路$u \rightarrow v$のコストを引いたものより、到達するノード$v$のh値が同じか大きい場合無矛盾
- 逆に、出発するノード$u$のh値から経路$u \rightarrow v$のコストを引いたものより、到達するノード$v$のh値が小さい場合、経路を進むとh値が消えてしまい矛盾しているような感じか
- ゴールノードのh値が0である無矛盾なヒューリスティックは許容的なヒューリスティックである。(PDF内の定理2)
- 全てのノードのペアについて、$h(u) <= h(v) + k(u, v) $ が成り立つ場合、無矛盾なヒューリスティックという
単調なヒューリスティック
A*法
A*法のアルゴリズムは以下のとおり:
g値
は、初期状態からそのノードまでの既知の最短経路コストh値
は、何らかのヒューリスティック関数によるそのノードからゴール状態までの最短経路の見積もりf値
は、g値
とh値
の和A*法
は、f値
が小さいノードから順に探索していくアルゴリズム
A*法には以下のような性質がある:
- グラフに経路コストが0以下のサイクルが存在しない場合、A*は完全である(PDF内の定理4)
完全とは、解が存在するときに有限時間内に解を返すこと - ヒューリスティックが許容的であるとき、A*は最適解を返す(PDF内の定理5)
無矛盾なヒューリスティックを用いたA*探索はノードの再展開を生じない(PDF内の定理6)
許容的で無矛盾なヒューリスティックであるなら、解析的に良い性質を満たしているといえるが、経験的に速いと知られているヒューリスティック関数の中にはこれらの性質を満たしていないものも多い
A*法とヒューリスティックの情報
- ヒューリスティックの情報
ヒューリスティック関数h1とh2が両方許容的であり、ゴールでない$s \in S$ に対してh2(s) > h1(s)であるとき、h2(s)はh1(s)よりも情報があるという - ノード展開の必要条件(PDF内の定理7)
A*探索で展開されるノードのf値はすべて最適解のコスト以下である - ノード展開の十分条件(PDF内の定理8)
f値が最適解のコスト未満であるノードは全てA*展開で探索される - h1とh2の探索範囲(PDF内の定理9)
h2はh1よりも情報がある場合、h2を使ったA*探索で展開されるノードはh1を使ったA* 探索でも展開される。つまり、h2の探索範囲はh1よりも小さくなる。 - ヒューリスティックの合成(PDF内の定理10)
ヒューリスティック関数の例
- グリッド探索での、障害物を無視した最短距離(マンハッタン距離)
- スライディングタイルでの、現在の位置とゴール状態の位置の差の総和
- スライディングタイルでの、部分問題の最適解のコスト
- 巡回セールスパーソン問題での、最小全域木のコスト
非最適解の探索
最適解でなくて良いので、解を探索する方法には以下がある:
Unityでゲームを作ってみた
Unityで練習としてゲームを作ってみました。Unity周りのさまざまな仕組みは結構独特で面白いと思ったので、まとめておきます。
なぜUnityか
作ったもの
(ブログ貼付用) pic.twitter.com/PUgjkVrw3C
— threecourse (@threecourse) 2020年4月12日
以下で遊べます:
Topdown Defense | フリーゲーム投稿サイト unityroom
敵が画面下に到着しないようにプレイヤーキャラクターを攻撃させます。
タワーディフェンスを、タワーじゃなくてプレイヤーが攻撃するようにしたゲームです。
最小限の工数でゲームをとりあえず完成させようと思ったのですが、それでもいろいろ大変でした。
Unityによるゲームの作り方のメモ
参考資料
5年ぶり3回目くらいの挑戦ですが、主に以下を参考にしました。
Unityの教科書 Unity 2019完全対応版 2D&3Dスマートフォンゲーム入門講座
https://www.amazon.co.jp/dp/B07TNNTTYVUnityマニュアル
Unity ユーザーマニュアル - Unity マニュアル
開発画面
開発画面は以下のような感じで、主なウィンドウは以下のとおりです:
- プロジェクト(Project)
プロジェクトのファイルを管理するウィンドウ - ヒエラルキー(Hierarchy)
GameObjectの論理的な配置を行うウィンドウ - シーン(Scene)
GameObjectの空間的な配置を行うウィンドウ - インスペクタ(Inspector)
GameObjectのコンポーネントを操作するウィンドウ - ゲーム
ゲーム画面を表すウィンドウ
Unity - マニュアル: インターフェースについての学習
GameObject
Unityでは、GameObjectというものを配置してゲームを作っていきます。
- キャラクター・アイテムからライト・カメラなど、すべてがGameObjectである。
GameObjectに各種コンポーネントを付加することで、それぞれの役割になる。 - GameObjectには、C#などで記述したScriptを付加することもできる。
- GameObjectを階層構造を持たせて配置したり、グループ化して扱うこともできる。
Prefab
Prefabは、GameObjectのテンプレートのようなもので、アクションゲームのザコ敵など、同じようなオブジェクトを作成したい場合にはPrefabを作成します。PrefabをScriptからインスタンス化することで、動的に何個も作成することができます。
Script
ゲームロジックはC#などでScriptに記述します。GameObjectにScriptを付加して使用します。
- MonoBeheviorというクラスがあり、このクラスはUpdate関数を持つ。Update関数は一定間隔で呼び出され、ここに一定間隔ごとに行う処理を記述することで、ゲームの流れを作ることができる。
- キャラクタを表すGameObject、ゲームを管理するマネージャー的なGameObjectのどちらの場合でも、基本的にはMonoBeheviorを継承したクラスを持たせる。
- ユーティリティ関数などを持つ静的クラスを記述することもできる。 この場合、特にGameObjectに付加しなくても、プロジェクト内に含めておけばその静的クラスを他から呼び出せるようになる。
オブジェクト間の連携
ゲームのさまざまな処理を行うには、GameObject間で情報を伝達し、その情報に応じて反応させることが必要である。
GameObject間で情報を伝達するには、以下の方法がある:
- イベントの仕組みを利用し、イベント時に呼ばれる他のGameObjectのメソッドを登録する形にする
- 他のGameObjectのメソッドを直接叩く
いずれにしても、他のGameObjectを参照する方法が必要となる。以下の方法がある:
- インスペクタで他のGameObjectを指定して参照する
- Script内で名前や親子関係を指定して他のGameObjectを参照する
- 後述のシングルトンを利用してマネージャーのGameObjectを参照する
ゲームの枠組み
大枠としては、以下でゲームが構成される。実際には、UIとかカメラとか特殊効果とかもろもろやることがありますが・・
- ゲームの全体を管理するGameObjectを配置する
このGameObjectのScriptに全体的な流れや判定を記述する - キャラクターや建物のGameObjectを配置する
キャラクターを動かしたり、何かに反応させたい場合には、このScriptに記述する。 - ザコ敵などのPrefabを作成する。
他のScriptから呼び出されてこれらのPrefabがインスタンス化される。
その他開発まわり
UniRxというライブラリを利用し、リアクティブプログラミングというものを行うことができる。うまく使うと各クラスの処理を綺麗に分離できる。
- (参考) UniRx完全に理解した
- (参考) UniRx - GitHub - neuecc/UniRx: Reactive Extensions for Unity
UIで表示されるステータスを内部の値の変化に応じて変える場合にも、リアクティブプログラミングが便利。特に、UniRxのReactivePropertyを使うと、Vue.jsでバインドするような感じで書ける。
- 3DゲームでのUIは、3D画面とは別にUI用の2D画面を作成し、プレイ時にはその画面を重ねて表示する。
- マネージャーなどのクラスはあちこちから呼び出されるので、いちいちインスペクタで指定するのは面倒。ここで、シングルトンを利用することで、簡単に呼び出せるようになる。
(参考) Unityでよく使うデザインパターン - KAYAC engineers' blog - Script内でできるだけ処理を書くような開発も、Unityのヒエラルキーやインスペクタウィンドウを主にした開発もどちらもできる
アセットストアの利用
- Unityの魅力として、アセットストアからキャラクターのモデル、サウンド、エフェクトなどを購入できることがある
- 自分で一から作るのに比べて大幅に時間を削減することができそう。Unityは課金ゲー(?)
- 後述するTopDown Engineのように、半完成品みたいなアセットも販売されている。これらの中身を見て、コードの記述の仕方を学ぶのも有効。
Meshtint Studioのアセットを使ったのですが、他にもいろいろ種類があって使いやすそう assetstore.unity.com
slay the spire風のゲームを作れるアセットもある。ちょっと試してみたい assetstore.unity.com
ファイル管理
- ファイル名の変更や移動は、Unityのプロジェクトウィンドウ内で行う必要がある。そうしないと、保持されているメタデータの関係性が壊れてしまう。
- Gitで管理することができる。そのまま使うと、画像ファイルなどの重いファイルが管理されて大変なことになっていまうので、Git LFSを使うのが一般的らしい。
(参考) https://www.slideshare.net/kamera25/unity-git-lfs - アセットストアで購入したアセットはわりと好き勝手なパスにインポートされる。
デフォルトのパスの下に_MyAssetのようなフォルダを作っておき、その下に自作のAssetやScriptを入れるのが良さそう。
Topdown Engine
今回はこのアセットをベースに作成した。Corgi Engineなどのアセットを開発したMore Mountains作の、見下ろし型アクションゲームの半完成品のアセットです。
assetstore.unity.com非常に良く作られていて、ソースコードを読むのも勉強になる
結局、ライブラリの枠をはみ出ることをしようとすると、ライブラリをよく理解して、適宜修正して使わなくてはいけない。ボスを作ったときに、プレイヤーがボスの下に潜り込んでしまい、プレイヤーが移動床と判定されて計算がバグってボスが吹っ飛ぶという事象が発生した。ライブラリを読み込んでコードを修正しつつ、どこが悪さをしているかを探っていくことが必要だった。
キャラクターの移動は物理演算ではなく、内部的に与えられた力などを保持しておき、計算で求めている様子。確かに、物理演算に頼ると細かな処理が難しいかも。
Topdown Engineに同梱されているMMFeedbackというライブラリが本質ではないかと思った。攻撃をしたとき、敵に当たったとき、敵を倒したときにアニメーションや効果音、カメラへの衝撃などの形でフィードバックが与えられるかどうかで面白さがだいぶ違うように感じた。
Cython何もわからない
Cythonで何ができる?
拡張子.pyxファイルに、pythonの文法を基本としつつ一部をcythonの文法で型付けすることで、高速に処理を行うことができる。
呼び出すときはimport pyximport; pyximport.install()
を付加すると、あとは通常のimportが可能。(setup.pyを書いて明示的に一度コンパイルする方法もある。)
以下のようなことができる。
- python関数(def)のまま、一部の変数の型を指定する
- cの関数(cpdef, cdef)を書く
- 引数としてnumpy.ndarrayを渡して、集計したり書き換える
- pythonクラス(class)を通常どおり書いて、高速化したい一部の関数だけを書き換える
pythonクラスのクラス変数にcの型をつけることはできない(おそらく)が、それぞれの関数において一時変数に型をつけ、一旦そこに代入して処理を行えば良い。 - cのようなクラス(cdef class)を書く
- c++で記述した関数やクラスを読み込む
pythonと型付けで十分高速化される場合も多く、cの関数やクラスをわざわざ書くのは、パフォーマンスを追求する場合やcで書かれている関数を呼び出す場合など。
多くの場合は、ボトルネックになっている関数を切り出してそこだけCython化するのが分かりやすそう。 探索などを書いているとインスタンス生成がボトルネックになることがあるが、そういった場合はもう少し手を入れないといけないように思える。
サンプルコード
文法が良くわからなくなるので、上記のパターンをまとめてみました。
以前作成した、GBDTをCythonで高速化する例も参考になると思います。
参考文献
この辺りのQiitaは参考になった。
公式ドキュメントはあまり分からないような
オライリーのCython本は参考になったけど、何ができるかベースにもうちょっと落とし込んでほしいような
フロントエンド何もわからない(その2)
フロントエンド何もわからない のあとに少し研究を進めて、Vue.jsで三目並べを作ってみました。
Vue.jsは分かりやすく宣言的に書け、またSVGも図形の色などを修正しやすそうだったので、tornado + Vue.js + 描画はSVGというのはわりと良い解かもしれません。
vueでできた pic.twitter.com/v0cWcZjGZL
— threecourse (@threecourse) 2019年12月30日
フロントエンドなにもわからない
某所の勉強会用のゆるめの資料で、ヴィジュアライザを作ろうとしたときの話です。
何かのためのネタができた pic.twitter.com/4Vnae8qFQ8
— threecourse (@threecourse) December 21, 2019
GUIを使うためのdocker設定
モチベーション
書籍のgithubリポジトリやライブラリを動かすときに、それぞれ依存するライブラリが違うので、dockerを使いたいです。 ただ、強化学習などGUIが使われている場合、通常のdockerの設定では上手くいかないことも多いので、その辺を記述してみました。
dockerなどは素人なので、誤り、セキュリティ上の懸念などがあれば教えて下さい。
GUI用の設定
下記のQiitaおよび参照先が参考になりました。
上記の方法では、rootでなくユーザーでdockerに入ります。
ユーザーで入ると、dockerで作成したファイルのownerがrootになってしまう問題が解決されるメリットもあります。
ただし、/home/$USERの権限が無いと、jupyter notebookなど上手く起動してくれないプログラムがあります。
(--allow-rootで起動する方法もあるが、作成ファイルのownerがrootとなってしまうので良くない)
そのため、上記の方法では/home/$USERをマウントしていますが、この方法だとhostの~/.bashrcなどを読んでしまうし、/home/$USERに書き込まれる可能性もあります。 これを解決するには、コンテナで$USERをownerとして/home/$USER を作れば良いです。 というわけで、dockerfileに以下のようなコマンドを書きました。
# docker build時に以下のように引数を指定する # --build-arg USER=$USER --build-arg UID=$(id -u) --build-arg GID=$(id -g) ARG USER ARG UID ARG GID RUN mkdir /home/$USER && chown $UID:$GID /home/$USER
「Pythonで学ぶ強化学習 -入門から実践まで(https://www.amazon.co.jp/dp/4065172519)」
を動かすためのdockerfile等をgistに置いています。OpenGLの対応に結構苦戦しました。
その他感想・メモ
- dockerだと気兼ねなく環境を壊せるので気分が良い
- 私が試したときはnvidia container toolkitではOpenGLに対応できず、nvidia-docker2を使用している
- docker-composeを使う方法もあるが、とりあえずdocker runでやっている
- githubに置いてあるrequirements.txtをそのまま実行するか、anacondaから始めて足りないものだけinstallするか
gpuでないtensorflowを入れられることもあるので、いずれにしてもrequirements.txtは確認したほうが良いかもしれない
参考資料
Kaggle Days TokyoでのGBDT実装の話
先日行われたKaggle Days Tokyoで発表した資料になります。
前半は主に外国の方向けのKaggle本の紹介、後半はGBDTをスクラッチ実装する話です。
拙い英語ですが、雰囲気で読んで下さい。ちょっと説明に優しさが足りない気もしますね。直前にKaggle Santaコンペをやっていたのが良くない。。
コードはこちらです。Cython版でxgboostの1/4くらいの速度でまぁまぁな速さです。
sklearnやxgboostのコードを読むと、抽象化やいろいろなケースに対応するためのコードがあってアルゴリズムを理解するのに苦労するのですが、
シンプルにアルゴリズム部分が分かりやすいような書き方にしたつもりです。
www.kaggle.com
www.kaggle.com
他にも、@nyker_gotoさんの実装を教えて頂いたのでご紹介します。
C++でも200~300行ほどでGBDT(XGBoost)実装できるけど、ライブラリの1/10ぐらいのスピードしか出ないんだよな…。多分、実装面で相当の工夫があるのだと思っている。 #kaggledaystokyo
— Jack (@sakata_ryuji) 2019年12月11日
帰りにJackさんと少し話したのですが、私が気づいたxgboostの工夫は以下です。
- ノードごとにデータを走査すると、計算量がO(ノード)になってしまう。
深さごとにデータを走査し、データの属するノードに応じて処理を行うようにすると、計算量をO(深さ)にできる。 - SortedCSCPageという構造を使い、データを疎に保持するようにしている。
欠損値が多い場合などはその分スキップできるので速くなる。