独習 Scalaz: 1日目

in

お世話になっております。更新された html5版があるので、よろしくお願いします。

これまでいくつのプログラミング言語が羊の衣を着た Lisp に喩えられただろうか? Java は馴染み親しんだ C++ のような文法に GC を持ち込んだ。それまで他にも GC を載せた言語はあったけども、現実的に C++ の代替となりうる言語に GC が載ったことは 1996年には画期的に思われた。やがて時は経ち、人々は自分でメモリ管理をしないことに慣れていった。JavaScript と Ruby の両言語もその第一級関数 (first-class function) やブロック構文を持つことから羊の衣を着た Lisp と呼ばれたことがある。S式の同図像性がマクロに適することから Lisp系の言語はまだ面白いと思う。

絵で見るモナド

John Wiegley さんの "Monads in Pictures" を翻訳しました。翻訳の公開は本人より許諾済みです。翻訳の間違い等があれば遠慮なくご指摘ください。

2012年8月20日 John Wiegley 著
2012年8月21日 e.e d3si9n 訳

これはモナドのチュートリアルではないし、ここには数学用語も出てこない。本稿は、既にモナドを一応使えるぐらいには習った人を対象とする。視覚化することで、何のために何をやっているかが明らかになるはずだ。

関数

モナドに対する直感を得る一つの方法として関数からモナドへの抽象化をたどるというものがある。関数が何をやっているのかを簡単な絵で表してみよう。Haskell の関数の呼び出しの構文を上に、同じ演算を視覚化したものを下に置いた:

Scala で書く tetrix: 12日目

昨日はエージェントとプレーヤが対戦できように 2つのステージアクターを作った。より面白くするために相手にゴミブロックを送る攻撃機能も実装した。

不公平な強み

これまでの所エージェントはいかに多くのラインを消せるかということを念頭において調整されてきた。しかし昨日になって突然 2行以上を消さないと有効にならない攻撃機能が導入された。この情報を知っている人間サイドに不公平な強みができたことになる。何とかできないか少し見てみる。

まず、アクションで一度に消されたライン数を管理しよう:

case class GameState(blocks: Seq[Block], gridSize: (Int, Int),

Scala で書く tetrix: 11日目

昨日はヒューリスティック関数の色々な部分を調整するためにゲームをスクリプトから自動化するテストハーネスを書いた。最終的にはパフォーマンスを 7 +/- 2 ラインから 34 +/- 8 ラインまで約5倍引き上げることができた。

HAL 的な瞬間

スクリプトテストばっかりだったので、swing UI のゲームを最後まで見ることにした。ラインを次々と消しながらブロックを低めに押さえていて、ゲームのクオリティーが向上してきたことは初めから感じられた。だいたい 60 ラインぐらいを超えた所でいくつかのミスでブロックが 10 段ぐらいまで積まれてきたが、扱いきれないというほどでは無いと思った。ところが突然のようにピースをドロップし始めた。一つづつ次々と。

エージェントはゲームを放棄したかのようにみえた。後になって気付いたのはアクターのどこかでタイムアウトが生じたせいだろうということだった。

可変長思考サイクル

エージェントに定期的に思考するように命令するのではなく、好きなだけ考えさせてあげることにする。人の反射速度と比べてフェアなように取れるアクションは秒あたり 3つぐらいに制限する。

 

Scala で書く tetrix: 10日目

昨日は tetrix を解くエージェントの探索木を 2つ目のピースに拡張した。手筋は確かに向上したけど、まだ調整の余地がある。

スクリプティング

自分で書いたエージェントがゲームをプレイするのを眺めているは確かに楽しいけれども、時間がかかり、主観的なプロセスだ。今日まず取り組むべきなのはプリセットされたゲームを UI無しのシングルスレッド上で実行するテストハーネスだ。エージェントに絶え間なく最良のアクションを計算させて即時に実行していく。

既に PieceKind.apply(x: Int) があるから、PieceKind にそれぞれ toInt を実装しよう:

sealed trait PieceKind { def toInt: Int }
case object IKind extends PieceKind { def toInt = 0 }
case object JKind extends PieceKind { def toInt = 1 }
case object LKind extends PieceKind { def toInt = 2 }

Scala で書く tetrix: 9日目

昨日はヒューリスティック関数を直し、また現在のピースの 36 通りの可能な位置と向きを評価することで tetrix を解くエージェントが少しはましなゲームをプレイできるようにした。

ストップウォッチ

あるコードの一部にかかる時間を測定するための関数を書いてみよう:

  private[this] def stopWatch[A](name: String)(arg: => A): A = {
    val t0 = System.currentTimeMillis
    val retval: A = arg
    val t1 = System.currentTimeMillis
    println(name + " took " + (t1 - t0).toString + " ms")
    retval
  }

これは以下のように使える:

    stopWatch("bestMove") {
      // do something
    } // stopWatch

出力はこうなる:

Scala で書く tetrix: 8日目

昨日は tetrix を解くエージェントをアクターに組み込んでゲームを操作させた。これまでのゲームの手さばきは合理的だとも知的だとも言い難い。ヒューリスティックのペナルティが何度も 0.0 と評価されているのを見て 2つの疑惑が頭をもたげた。

第一に、Drop はいかなる場合でも良い選択ではないということだ。特に探索木が浅い状況では Drop を選択するのは早計だと思う。どうせ重力による Tick が下向きに動かしてくれるので、エージェントが Drop が最良の動作だと思った場合は無視することにした:

  def receive = {
    case BestMove(s: GameState) =>
      val message = agent.bestMove(s)
      if (message != Drop) stageActor ! message
  }

バギーなペナルティ

第二の疑惑はペナルティの計算が何かおかしいということだ。テストを加えてみよう:

 

Scala で書く tetrix: 7日目

昨日から tetrix を解く AI という新たな問題に取り組みはじめた。Russell と Norvig は合理的なエージェントの構造がステートマシン、効用関数、木探索アルゴリズムから構成できるという洞察を与えてくれた。僕らにあるのは最初の 2つと失敗しているテストだ:

[info] Solver should
[info] + pick MoveLeft for s1
[error] x pick Drop for s3
[error]    'MoveLeft' is not equal to 'Drop' (AgentSpec.scala:13)

まず既に知っていること、つまり可能な動きとそれに対応した状態遷移関数を書きだしておく必要がある。

  private[this] val possibleMoves: Seq[StageMessage] =
    Seq(MoveLeft, MoveRight, RotateCW, Tick, Drop)

Scala で書く tetrix: 6日目

昨日は 2つ目のアクターを導入することでゲームの状態へのアクセスの並行処理を改善した。並行処理を司る強力なツールを手に僕達は新しい旅に出ることができる。例えば人類の制覇だ。tetrix プレーヤーひとりづつ。

Russell と Norvig

Syndicate content