読者です 読者をやめる 読者になる 読者になる

ICFPC2011 マルチスレッド版LTGモナド

未だにICFP programming contest 2011の余韻から抜け出せないでいます。打ち上げでもいろんなプログラマーやジャッジ側と交流ができて楽しかったです。

さて、その打ち上げ当時から「1ターンで殺してゾンビ化して次弾Getまで出来るよね」「それで浮いたターンで殴れば最強じゃね?」とかいうアイデアがよく出ていましたが、いざ作るとなると断片的な浮いたターンで呪文を組み立てるとかとても難しそうです。ところが週末にそれを可能にするフレームワークの発想が降ってきたので矢も盾もたまらず実装していました。

ありがたいことに、id:tanakhさんから「こういうきれいな抽象化を書かれると悔しい><」「世界が嫉妬するコード」「これはやばいし、Haskellじゃないともはやこのレベルのコードはここまで綺麗にかけないだろう」「これコードシンプルすぎるし、他の言語だと多分これ実装するの死ぬのじゃないか?」との言葉を頂きましたので、Haskellの宣伝のために紹介してみようと思います。ちなみに僕はHaskellだけが特別な言語だとかあまり思いこまないようにしようとしているし例えばRubyだってThreadもQueueもあるんだから似たようなことはできるんじゃないかなと思います!

LTGモナドのマルチスレッド化

runLTG :: LTG a -> IO ()
runLTGs :: [(LTG Bool, LTG ())] -> IO ()

僕らのチームではLTGモナドというのを作ってAIの戦略を組み立てています。runLTGは1つのLTGモナドを実行に移す関数です。今回作ったrunLTGsは、[(ある戦略を実行すべきかどうかの判定,実行すべき戦略)のリスト]を受け取り、毎ターン、リストの中で最初にTrueになった戦略を一ステップだけ進行させます。このマルチスレッド機構の実装は主にMonad.hsの --coroutine-- とコメントされている部分です。それを使って書かれたAIの例もあります。

基本的な発想は、LTGモナドを並列に実行したいんだったら、その数だけHaskellのスレッドを立てて並列に走らせておいて、適切なところでタスク切り替えしてやれ、というものです。

type LTG = StateT (ThreadAttr, Simulator) IO

data ThreadAttr = SingleThread |
                MultiThread (TVar Scheduler) Int{-tid-}

data Scheduler
  = Scheduler
    { mailbox :: Vector(TMVar Simulator),
      condition :: Vector(LTG Bool) }

まず、LTGモナドはSimulatorの情報(現時点でのゲーム状態の全て)に加えてThreadAttrを持つように改造されています。ThreadAttrはMultiThread実行の場合、マルチスレッド実行全体を司るSchedulerへの参照と、自分のスレッドIDを含んでいます。Schedulerがスレッドの並列実行を管理しており、これには各スレッドのmailboxと実行判定が格納されています。TMVarは「空になることが出来るSTM変数」であり、空の状態のものを読もうとすると、中身が入るまでブロックします。mailboxでシミュレーションの状態をまるごとやりとりすることで、複数のスレッドが一貫して1つのゲームを進行できるようにします。Schedulerは後述するように、ゲーム中でconditionが変化するなど更新されることがあるので、その更新が全てのスレッドで共有されるよう、ThreadAttrはSchedulerをTVarにくるんで持つようにしています。

基本的に、runLTGsは渡された戦略LTGモナドの数だけのワーカースレッドと、タスク切り替えを制御する1つのマスタースレッドを起動します。シミュレーションは、マスタースレッドのメールボックスに初期状態のシミュレータが入り、他のスレッドのメールボックスは空である状態でスタートします。

  mailbox0 <- newSimulator >>= newTMVarIO
  mailboxes <- replicateM n newEmptyTMVarIO
  . . .
      schdr = Scheduler
              { mailbox = Vector.fromList $ mailbox0 : mailboxes
              , condition = Vector.fromList $ return False : map fst ltgs
              }
  tvs <- newTVarIO schdr

各スレッドは実行されると、実行すべきタスクltgを実行する前に、いきなりwaitWakeで待ちに入ります。

runLTGThread tvs tid ltg = do
  flip evalStateT (MultiThread tvs tid , error "undefined state") $ do
                     waitWake
                     er <- E.try ltg

waitWake = do . . .
             sim <- atomicalift $ takeTMVar (mailbox schdr ! tid)
             putSimulator sim

waitWakeでは、自分のメールボックスに状態が届くまで待ち、届いたら、それが最新のゲームの状態なので、自身のシミュレーターを上書きしてしまいます。waitWakeを抜けると実際の戦略ltgが実行され始めるわけですが、自分の手を打ち、相手の手を読み取ってシミュレーションを進めた直後に、yieldします。yieldでは自分のシミュレータをマスタースレッドのメールボックスに投函し、自分は待ちに入ります。

getHand = do
  h <- liftIO readHand
  s <- getSimulator
  (ns, msg) <- liftIO $ execStep h s
  putSimulator ns
  . . .
  yield

yield = do . . .
             sim <- getSimulator
             atomicalift $ putTMVar (mailbox schdr ! masterTID) sim
             waitWake

マスタースレッドはというと、シミュレーション状態を受け取って上書きしたら、その文脈で各スレッドのconditionを評価して、最初にTrueを返したスレッドのメールボックスにシミュレーション状態を投函します。

masterThread = forever $ do . . .
                 conds <- Vector.mapM id (condition schdr)
                 let f = Vector.findIndex id conds
                 case f of . . . 
                   Just tid -> do
                       sim <- getSimulator
                       atomicalift $ putTMVar (mailbox schdr ! tid) sim
                       waitWake

マルチスレッド機構の概要は以上です。他にも、スレッド内の戦略が例外で抜けた場合は実行条件をreturn Falseにしてやるとか、conditionが全ての場合を尽くしていない(または、例外終了により尽くさなくなった)場合に備え優先順位最低の何もしないtailWorkerを挿入するなど、いくつかの工夫がしてあります。

最初はマルチスレッド化するのに継続とか必要なんじゃないか、じゃあモナド計算の継続ってどうやって取り出すの、というところで詰まっていました。関数型言語でマルチタスクな戦略を記述というと、どうしても各戦略の継続を取った上で並列実行の全てを管轄するような方向に発想が行きがちでした(できもしないのに^^;)。でもそんなことはなく、スレッド立てたいだけ立てて走らせ始めてしまい、後から必要な箇所で「情報を送って停止、情報が来たら上書きして再開」という、泥縄的なメカニズムで適切に動作したのには驚きました。この泥縄式で上手く行った背景には、Stateモナドを使って状態のある計算を明示的に記述しているために、状態をすり替えることの意味がはっきりしていること、さらにStateT IOになっているために中でIOが使えること、そこでSoftware Transactional Memoryを道具に使ってどんな物でも手軽にやりとりできることなどがあり、そのへんは書いていて有り難く感じました。

並列計算の実行を始めてしまったあとでも、その実行を自在に制御できると言う面で、Haskellの強みが出せたかと思います。

並列計算というと、とかくマルチコアを使い倒して速度を出すという方向性が強調されますが、今回のように「やりかけのタスクを沢山抱えたうえで適切な順序で実行していく」というアルゴリズムを書くにも、並列計算のビルディングブロックは有効なのだなということが体験できました。

戦略

このマルチスレッド版LTGモナドを使って実装した戦略がMamisanKawaii.hsです。名前が紛らわしいですが、書いているうちに何故かマミさんの魅力をコードで表現したようなものになっていったので、ほかに適切な名前が思いつきませんでしたご容赦ください。

コードはこんな感じです。

main :: IO ()
main = runLTGs
       [(isOpening                   , openingMove ),
        (mamitta                     , bikunbikun  ),
        (isAlive False 0             , discipline  ),
        (enemyWeak                   , madanNoButou),
        ((<55000) <$> getVital True 0, pumpUp      ),
        (return True                 , shoot       ) ]

本当に、実行条件とやりたいことの優先順位つきリストを与えるだけでマルチタスクな戦略が書けちゃうんです。美しい。

序盤の定跡がmamittaらbikunbikunするほかなく、無力化されますが、そこさえ通ればこっちのもの。相手のrevive 0を見逃さず即座にDecで叩き落としつつも、それに乱されることなく魔法を唱え上げ発動する隙のない華麗な戦闘シーンを見ることができます。デビュー時点での戦績はこんなもんです。ああもうマミさん美人だし強いしかわいいな。ティロフィナーレはほんとはattackループにしたかったのですが、書けるだけのSKI言語力が僕にはまだありませんでした・・・

まあこいつ自身が0番スロット使用者に対するメタみたいなもんではありますが、あっと言わせる新戦術で出し抜いていただけるよう、これからもYet Another Unofficial Judge for ICFP Contest 2011ではみなさんの挑戦をお待ちしております。例えば林崎さんのN0Y2CAtkQbは、途中から全く0番スロットを使わないで動作するそうです。