Operationalモナドをゲームに応用した話

データを処理することは、プログラミングのもっとも本質的な部分である。数値、文字列、あるいはデータの集まりなどを扱うために、数々の構造が考えられてきた。Haskellにおいては、「手順」もデータとして扱うことができる。これは、DSLを作るうえで非常に有用であり、ゲーム開発やデータベース操作……手続きがかかわるあらゆるものに応用できるだろう。

手順をデータとして扱う方法として、FreeモナドとOperationalモナドがある。ここでは、Operationalモナドをゲームのキャラクターの制御に用いた例を紹介する。Freeモナドの導入については、Andres Löh氏のHaskell eXchange 2013の講演がわかりやすく、おすすめである。

データを作る

アクションゲームの敵の動きとして、この二つを考えよう:

  • 待機
  • 接近(攻撃)
  • 索敵(プレイヤーの位置を調べる)

EnemyMというモナドがあれば、Haskellの値としてそれらを定義することができる。

wait :: EnemyM ()
move :: Position -> EnemyM ()
scout :: EnemyM Position

では、EnemyMはどうやって作るのだろうか?その答えの一つはOperationalモナドだ。

{-# LANGUAGE TemplateHaskell #-}
import Control.Monad.Operational.Mini

data EnemyI a where
    Wait :: EnemyI ()
    Move :: Position -> EnemyI ()
    Scout :: EnemyM Position

makeSingletons ''EnemyI

type EnemyM = Program EnemyI

「位置pに向かって動く」という動作は、そのままMove p :: EnemyI ()という値として表現される。EnemyIは挙動の最小単位になっている。この型にProgramをかぶせることによって、それらを合成できるようになる――Programは好きなものをモナドにしてしまう力があるのだ。具体的な構成方法については、私の過去の記事*1を参照されたい。

実装

以下は、この考えに基づき実装したコードだ。もっとも基本的な関数singletonは、命令の最小単位をProgramレベルに持ち上げる。minioperationalのmakeSingletonsを使えば、singletonを適用した命令を自動生成することも可能だが、今回は使っていない。

data Tactic x where
    Approach :: Tactic ()
    Wait :: Tactic ()
    RelativePlayer :: Tactic (Maybe (V2 Float))
    Put :: Enemy -> Tactic ()
    Get :: Tactic Enemy
    Randomly :: Random r => (r, r) -> Tactic r


type Strategy = ReifiedProgram Tactic

defaultStrategy :: Strategy ()
defaultStrategy = do
    r <- singleton RelativePlayer
    a <- use enemyAttacked
    case r of
        Just d
            | a -> attacking defaultStrategy
            | quadrance d < 160 ^ 2 -> attacking defaultStrategy
            | quadrance d > 320 ^ 2 -> enemyAttacked .= False
        _ -> singleton Wait

attacking :: Strategy a -> Strategy a
attacking cont = do
    replicateM_ 29 $ singleton Approach
    replicateM_ 33 $ singleton Wait
    cont

ここで、ReifiedProgramはProgramの変種である。CPS変換されているかどうかの違いがあるが、説明は省略する。Enemyは敵の状態を直接的に表す型である。敵の種類ごとにコンストラクタを作れば、Affine traversal*2で内部状態を読み書きできるため、とても便利だ。

独自のモナドを定義するメリットは、「同じプログラム(Strategy)でも、キャラクターごとの個性を表現できる」ということと、データであるため、合成、分解、検証が容易であるという点にある。

以下はプログラムを分解し、より具体的な動きに変換している関数の例である。敵の状態を扱うStateモナドの上で動いている。

exec cha (Approach :>>= cont) = do
    target <- lift $ use $ thePlayer . position
    pos <- use position

    case cha of
        Squirt -> do
            velocity . _x .= signum (view _x target - view _x pos)
            modify updateAnimation
        Fly -> velocity .= normalize (target - pos) * V2 3 6
    return (cont ())

exec cha (Wait :>>= cont) = do
    velocity . _x .= 0
    return (cont ())
exec _ (RelativePlayer :>>= cont) = do
    target <- lift $ use $ thePlayer . position
    pos <- use position
    return (cont (Just $ target - pos))
exec _ (Get :>>= cont) = cont <$> get
exec _ (Put s :>>= cont) = cont <$> put s
exec _ (Randomly r :>>= cont) = cont <$> liftIO (randomRIO r)

雑魚敵と飛ぶ敵で、移動の方法を変えている。また、RelativePlayerの部分の処理を変えれば、「視野」を設けるといった高度なことも可能になるだろう。

ProgramやReifiedProgramは、変換先のモナドを制限しない。そのため、ありとあらゆる環境*3にプログラムを持ち運ぶことができる。ちょうどLuaのような埋め込み言語の、さらに上位版と見てもよい*4

この実装の全体はGitHubで公開している

f:id:fumiexcel:20131111153604p:plain

その他

  • 拙作のfree-gameゲームエンジンとして使ったが、スクロールを含むマップの描画は予想していたよりも簡単に記述することができた。その理由もまた、モナドをデータとして扱っているからである。
  • 全体で約500行と、内容の貧相さの割には行数がかさんでしまった。無理してStateモナドを利用せずに、リアクティブプログラミングを取り入れたほうがよかったかもしれない。karakuriというパッケージでも、アクターの記述のよりよい方法を模索している。
  • 音声関連のライブラリはまだ十分に整備されていないのが現状である。DirectSoundも公開されたが、クロスプラットフォームかつインストールしやすくかつメンテナのいるパッケージはまだない。Haskellでゲーム開発をしていくうえで、今もっとも大きな問題だと考えている。

課題

今回は非常に単純な挙動だったが、たとえば動的計画法などを用いてマップの格子と行動にスコアを割り当て、スコアが高いところに向かって行動するなど、より高度なAIも記述できるはずだ。戦略性とアクション性を両立しやすくするアプローチとして、モナドはとても革新的なツールだと確信している。

プログラムの検証については、本研究では確実な手法を見出すことはできなかった。今後も、何か面白いアプローチができないか考えていきたい。

参考

*1: モナドとはモナドである - モナドとわたしとコモナド

*2:対象が存在しない場合があるLensの変種。Lensについてはhttp://hackage.haskell.org/package/lens-3.10/docs/Control-Lens.htmlを参照のこと

*3:型クラスによるアプローチと違い、同じモナドに対し複数の変換方法があってもよい

*4:実行時に動作を差し替えられないのが難点だが…

ミックスの仕上がりを綺麗にする(かもしれない)簡単な工夫

ミキシングはコンピュータによる楽曲制作には欠かせない。きちんとミキシングしなければ、まるで重油の浮いた泥のようなサウンドになってしまうのはご存じだろう。

ミックスにおける重要な課題の一つは、低域をすっきりさせることだ。低域をクリーンにすることは、聴きやすさと音圧の向上につながる。

そこでおすすめなのが、「全トラックにハイパスフィルタをかける」という方法だ。まず40~50Hzをカットオフ周波数とするハイパスフィルタを挿入し、全体で聴いて不自然にならない程度にカットオフと帯域幅を調整すれば、それだけでとてもすっきりするだろう。

f:id:fumiexcel:20131106154028p:plain

余裕が出来たら、ベースとキックの音をガンガン上げていこう。下手にマキシマイザーをいじるよりも、ずっと音圧が稼げるはずだ。

高専プロコン競技部門に参加した

どうも、Haskellの宣伝をしまくっていた@fumievalです。

全国高等専門学校 第24回プログラミングコンテスト競技部門に、@NKMR_YA@39moguraさんと一緒に茨城工業高等専門学校の代表チームとして出場しました。

f:id:fumiexcel:20131016123648p:plain

去年もそれを使った、ような…

競技の流れは以下の通りです。

  • 送信側m人と受信側n人(m + n = 3)に分かれる。
  • 送信側に文字列Sが配布される。
    • 木製の長方形の容器(パケット)と、 それぞれの面に1から6までの点が刻まれた立方体状の樹脂(サ イ コ ロが与えられるので、必要に応じてそれを使う。
    • 設置されたカメラにより、20秒間隔でパケットが撮影される。ただし、手などが写っていると魂を抜かれ失格。
  • 受信側は、何らかの文字列S'をサーバーに送信する。必要に応じて、送信側で撮影されたパケットの画像を利用することができる。
  • 制限時間が過ぎると終了。
    • SとS'を先頭から比較し、もっとも一致している文字数が多いチームが勝利。
    • 文字数が等しい場合、その文字列を提出するまでの秒数が少ないほうが勝利。
    • 秒数が等しい場合、いくつかのサイコロを振り、その合計が大きいほうが勝利。

それはとっても簡単だなって

去年の問題は、乱雑に置かれたサイコロの個数を数えるという高難易度…むしろ人間がやったほうが楽なものでしたが、今年の問題はある程度プログラミングを生かせると感じました。もう何も怖くない。

GUIも、CUIもあるんだよ

私がエンコーダ、デコーダを開発し、残りの二人が画像認識プログラムを作るという割り当てでした。配置を表示するプログラムも作ってしまったので、それを使うことになりました。

f:id:fumiexcel:20131016123335p:plain

写真のようにサイコロの1、2、5の目だけを使い、中央の色を調べることで画像認識を簡単にするという方針でした。

f:id:fumiexcel:20130926170951j:plain

工夫なんて、あるわけない

後述する事情により、1から6までの目を使うことになりました。エンコード方法は、サイコロ5つを2文字に割り当てるという至極単純なもの。暗号化も圧縮もありません。目の列は1行ごとに左から右に並べられます。

本番で与えられた文字列がこんな感じだったので、エントロピー符号くらいは使うべきでした…あたしって、ほんとバカ

こんなの絶対おかしいよ

本番はマウスも含め周辺機器が利用できません。これはちょっと厳しいです…本当のルールと向き合えますか?

もう誰にも頼らない

真上から撮影できるとは限らないことが判明したため、急遽私も画像認識のプログラムを開発することになりました。

10/9頃、ある程度サイコロの目を判別できるようになりました。幾度ものパラメータの調整を経て、百発百中の精度を得ました。

f:id:fumiexcel:20131016124840p:plain

アルゴリズムは、画像の中の黒い点をカウントするだけです。

この時点でシステムのすべてがHaskell製になりましたが、そこは…まあ。データ構造、線型代数、画像処理、並列化などの多少の勉強になりました。

わたしの、サイコロの友達

他の二方のおかげで、準優勝というよい結果を残すことができました。とても感謝しています。来年はその一つ上を目指すだけなので、気が楽です。来年はサイコロじゃないといいなあ。

最後に、ともに闘ってくれたチームのメンバー、本コンテストを開催した運営の方々、会場を用意していただいた旭川市民文化会館の方々、および財布を拾っていただいたホテルの方に、心より感謝を申し上げます。

リンク

型からHello world

Restricted Wordsに参加した。

"Hello World"という文字列を出力するプログラムを、文字・文字列・数値リテラル使わずに書くという問題。で、回答のコードがこちら。

import Data.Reflection -- cabal install reflection

main = putStrLn $ map toEnum [
      reflect ([] :: [D (D (D (SD (D (D (SD Z))))))])
    , reflect ([] :: [(SD (D (SD (D (D (SD (SD Z)))))))])
    , reflect ([] :: [(D (D (SD (SD (D (SD (SD Z)))))))])
    , reflect ([] :: [(D (D (SD (SD (D (SD (SD Z)))))))])
    , reflect ([] :: [(SD (SD (SD (SD (D (SD (SD Z)))))))])
    , reflect ([] :: [D (D (D (D (D (SD Z)))))])
    , reflect ([] :: [SD (SD (SD (D (SD (D (SD Z))))))])
    , reflect ([] :: [(SD (SD (SD (SD (D (SD (SD Z)))))))])
    , reflect ([] :: [D (SD (D (D (SD (SD (SD Z))))))])
    , reflect ([] :: [(D (D (SD (SD (D (SD (SD Z)))))))])
    , reflect ([] :: [D (D (SD (D (D (SD (SD Z))))))])
    ]

reflectは、型レベルにエンコードされた値を値レベルに戻す関数なのだ。

class Reifies s a | s -> a where
  -- | Recover a value inside a 'reify' context, given a proxy for its
  -- reified type.
  reflect :: proxy s -> a

通常は、なんとunsafeCoerceを駆使してインスタンスを動的に生成するという方法で、値を実行時に型にエンコードするのが普通の使い方。コワイ!だが、Reifiesにはもう一つ、Intのインスタンスもある。

data Z -- 0
data D  (n :: *) -- 2n
data SD (n :: *) -- 2n+1
data PD (n :: *) -- 2n-1

[Z]という型をreflectすると0、[D n]という型をreflectすると2 * n、[SD n]という型をreflectすると2 * n + 1になる。これを利用して、型から自然数を生み出せるのだ。

Prelude Data.Reflection> reflect ([] :: [(D (SD (D (SD (D (SD Z))))))])
42

あとはtoEnum :: Int -> Charで文字に変換して、リストを作ればOK。なんて卑怯純粋で安全な方法!

Given

give :: a -> (Given a => r) -> rという関数は、動的にGivenクラスのインスタンスを生成するgiveで与えた値は、given :: Given a => aによっていつでもどこでも取り出せる。何かと便利だ。

Lazy K 基礎文法最速マスター

Unlambda記法

適用

`FG

F、Gは任意の式。

コンビネータ計算記法

適用

(FG)

F、Gは任意の式。

Iota記法

適用

*FG

F、Gは任意の式。

Jot記法

  • 空白のコード → 恒等関数
  • X0 → X S K
  • X1 → S (K X)

Xは任意の式で、S、Kはコンビネータ

モナドとはモナドである

この記事を読む前に、絶対に理解出来ないモナドチュートリアルに一度目を通してみてほしい。モナドを理解していく上で、とても重要なことが書かれている。


改めて言おう、モナドモナド。コンテナだとかプログラマブルセミコロンだという説明では、モナドのすべてを正確に表せるとは言い難い。では、モナドを過不足なく説明できる、モナド以外の言葉はあるのか?

実は、モナドを表現し、かつモナドで表現される言葉は存在する。その一つは手続きである。手続き型言語の「手続き」だ。

手続きとは何か

手続きは結果を持つ

おおよそすべての手続きは何らかの結果を持つ。Haskellの()、C言語のvoid、PythonのNone、Rubyのnilなども結果の一種だ。結果が出ないとしたら、そのプログラムは停止しないか、途中で異常終了するだろう。

手続きには最小単位が存在する

処理系が扱っている以上、手続きが際限なく分解できるということはあり得ない。抽象的な文脈なら、「文字を出力する」のも最小単位と見てよいだろう。

「手続きAを実行した後手続きBを実行する」といったものも手続きである

当たり前だが、大事な性質だ。これによって手続きを組み合わせ、大きなプログラムを作ることができる。

「何もしない」のも手続きである

何もしなくても手続きになる。ならないと色々と困る。ただし、「結果を持つ」という性質は満たさなければならない。

さて、手続きの4つの性質を確認したが、以下のような疑問が残る。

  • 「Aを実行した後Bを実行する」とき、Aの結果はどこに行くの?

多くの手続き型言語では代入構文を使って手続きの結果を保存している。Pythonならこんな感じだ。

s = raw_input()

しかし、結果を利用するためだけに変数の仕組みを持ち出すのは美しくない。「変数なんてどの言語でも備えているだろ」と思うかもしれないが、今回はそうではないのだ。そこで、「関数」を使おう。

  • 「Aを実行し、その結果を手続きを返す関数に渡す。そして、返ってきた手続きBを実行する。」

要するに、「現在のスコープに結果がある」という条件を満たせばよい。

Haskellで手続きを表現する

以上の点を踏まえて、Haskellで手続きを表現する方法を考えてみよう。

手続きは「結果」を持つ。

結果の型をaとすると、少なくとも手続きの型はT aのようになる。単なる値と区別しないと作る意味がない。

手続きには最小単位が存在する

とりあえず、以下のものを最小単位としてみよう。

Helloworld :: T () -- Hello, worldを表示する。
GetLine :: T String -- 文字列を入力する。
PutStrLn :: String -> T () -- 文字列を引数に取り、その文字列を表示するという手続きを返す。

ちょっと待った!HelloworldやMyGetLineはコンストラクタなのに(コンストラクタは大文字で始まる)、自由に型を指定することができるのか?

できる、そう、GADTならね。GHCのGADTs拡張を使うと、コンストラクタとその型を列挙して代数的データ型を定義できる。

{-# LANGUAGE GADTs #-}

data T x where
    Helloworld :: T () -- Hello, worldを表示する。
    GetLine :: T String -- 文字列を入力する。
    PutStrLn :: String -> T () -- 文字列を引数に取り、その文字列を表示するという手続きを返す。

GADTはとても便利な機能だ。以降の性質も、GADTを使って表現しよう。

「Aを実行し、その結果を手続きを返す関数に渡す。そして、返ってきた手続きBを実行する。」

これを実現するには、手続きAと、結果を受け取る関数がコンストラクタの引数に含まれていればよい。

infixl 1 :>>=
data T x where
    Helloworld :: T ()
    GetLine :: T String
    PutStrLn :: String -> T ()

    (:>>=) :: T r -> (r -> T a) -> T a

(:>>=)という演算子はなにかに似ている気がするが、今は考えないでほしい。

「何もしない」のも手続きである

ただ結果を保持するだけのコンストラクタを追加する。

data T x where
    Helloworld :: T ()
    GetLine :: T String
    PutStrLn :: String -> T ()

    (:>>=) :: T r -> (r -> T a) -> T a
    Return :: a -> T a

これで、文字を入出力するという操作ができる、手続きの枠組みができた。では、使ってみよう。

Return 42 :: T Int -- 42を返す
Helloworld :>>= \_ -> Return 42 -- Hello, world!した後42を返す
GetLine :>>= PutStrLn -- 入力した文字列をそのまま返す
GetLine :>>= PutStrLn . reverse -- 入力した文字列を逆転させて返す

確かに表現力はある。実は、これがモナドだ。

正体

モナドは、上で定義した4つの性質のうち、「結果を持つ」「合成できる」「何もしない」が保証される構造だ。

Haskellの強力な仕組みである型クラスを使うと、このように表現できる。

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

上で定義したTは、直接Monadインスタンスにできる。

instance Monad T where
    return = Return
    (>>=) = (:>>=)

Monadインスタンスにすると、これから出てくる様々なモナドを、returnと(>>=)という二つの関数で統一的に扱える。しかも、do記法というHaskellの非常に便利な機能を使えるようになる。

do記法を用いると、さながら手続き型言語のように手続きを記述することができる。いや、do自体が手続き型言語であると言った方が良いだろう。

echoReversed = do
    s <- GetLine
    PutStrLn (reverse s)

もっと様々な手続きを書きたければ、Tに新たなコンストラクタを追加すればよい。モナドは、実はとても簡単に作れるものなのだ。

もっと簡単に

(:>>=)とReturnはモナドに必ず必要なため、この部分だけを切り出した構造を作れば、より簡単にモナドを作れそうだ。

data Program x where
    (:>>=) :: Program r -> (r -> Program a) -> Program a
    Return :: a -> Program a

ところが、これだけだと手続きの最小単位がないため意味がない。手続きの最小単位のための型を別に作るようにしてみよう。

data Program t x where
    Unit :: t a -> Program t a
    (:>>=) :: Program t r -> (r -> Program t a) -> Program t a
    Return :: a -> Program t a

data MyActions x where
    Helloworld :: MyActions ()
    GetLine :: MyActions String
    PutStrLn :: String -> MyActions ()

type T = Program MyActions x

こうして得られたTもやはりモナドになる。機能を拡張したいときは、Programを変えずに、MyActionsを変更すれば大丈夫。

このような、機能の最小単位の集まりからモナドを作る仕組みは、Operationalモナドと呼ばれている。これからのHaskellプログラミングで、非常に大きな役割を果たすだろう。

IOの世界

今までモナドを自作してきたが、HaskellではIOモナドという非常に重要なモナドがあらかじめ定義されている。なんと、IOモナドは、処理系がモナドを分解して、現実世界に対する副作用に変換できるのだ!

IOモナドとして表現される手続きをmainとして定義すると、処理系がそれを解釈してコンピュータに副作用を発生させる。これにより、Haskellのプログラムは使えるようになる。

main = putStrLn "Hello, world!"

これを実行すれば、あなたのターミナルにはHello, world!と表示されるだろう。神秘的だ…

IOモナドの中身をプログラムが把握することはできないが、Operationalモナドの中身を把握することは可能だ。これは、処理系が現実世界の中身を把握できなくても、IOモナドの中身を把握できるのと似ている。ということは、Operationalモナドを解釈してIOに影響を及ぼす処理系を作れるのではないだろうか?……作れる。

toIO :: Program MyActions a -> IO a

toIO (Unit HelloWorld) = putStrLn "Hello, world!"
toIO (Unit (PutStrLn str)) = putStrLn str
toIO (Unit GetLine) = getLine

toIO (Return a) = return a
toIO (m :>>= k) = toIO m >>= toIO . k

そう、まさに言語と処理系の関係。Operationalモナドは、一つの手続き型言語を、命令の一覧から自動生成してしまうモナドなのだ。しかも、IOなどの特定の環境に依存しない(クロスプラットフォーム)。処理系がプログラミング言語の挙動をエミュレートする――メタ世界の住人が我々をエミュレートする――という関係が、言語の中に出てきただけなのだ。

ここで作ったOperationalモナドは、より洗練された実装がある。実用する際はこちらを使おう。

ここで紹介した以外にも、Haskellの世界には様々なモナドがある。モナドの六つの系統モナドのすべてを参考に、様々なモナドを使って、そして作ってみてほしい。

まとめ

  • 手続きモナド
  • モナド手続きであり、それ自体が一つの言語
  • モナドは沢山あり、それらを変換する処理系を作ることができる
  • すべてのモナドはOperationalに通ず