tetrix.scala

去年に書いた Scala で書く tetrix を @n8han の Pamflet を使って html5 book にリビルドした。git 履歴をコミット毎にたどって使われているライブラリやツール群を 2013年時点で最先端のものに全てアップグレードした。ビルドは sbt 0.13.0 を使って build.sbt のみでマルチプロジェクトを行い、Scala は 2.10.2、全ての specs2 スペックは補間を使い、pfn/android-sdk-plugin 1.0.6 を用いて Akka 2.2.1 を Android に搭載した。

さらに Android での tetrix のデバッグと調整のために新たに 13日目を書き下ろした。

• Scala で書く tetrix

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

不公平な強み

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

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

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

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

HAL 的な瞬間

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

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

可変長思考サイクル

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

昨日は 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 }

昨日はヒューリスティック関数を直し、また現在のピースの 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

出力はこうなる:

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

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

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

バギーなペナルティ

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

昨日から 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)

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

Russell と Norvig

昨日はゲームの状態への並行処理を管理するために Akka アクターを入れた。抽象 UI を見てみよう:

package com.eed3si9n.tetrix
 
class AbstractUI {
  // skipping imports...
  implicit val timeout = Timeout(1 second)
 
  private[this] val initialState = Stage.newState(Block((0, 0), TKind) :: Nil,
    randomStream(new util.Random))
  private[this] val system = ActorSystem("TetrixSystem")
  private[this] val playerActor = system.actorOf(Props(new StageActor(
    initialState)), name = "playerActor")
  private[this] val timer = system.scheduler.schedule(

ここ数日かけて tetrix をゼロから実装してきた。初めに僕はこのゲームを使って新しい考え方とかを試してみるという話をした。既に Scala で tetrix は一度書いたことがあるから Scala だけじゃ僕にとっては目新しいものではない。今回 tetrix を使って考えてみたかったのは並行処理 (concurrency) の取り扱いだ。

並行処理

Goetz の Java Concurrency in Practice (Java並行処理プログラミング) を引用すると:

スレッドセーフなコードを書くということは、その本質において、状態、特に共有された可変状態へのアクセスを管理することにある。