Scala で書く tetrix
これは 2012年8月に書かれたブログシリーズをもとに、2013年9月に使われたツール群とコードを一新して編纂された。
時折新しいプラットフォームや、新しい考え方、新しいプログラミング言語を探索してみたくなる衝動にかられる。僕が最初に実装してみるのはいつも同じだ。ブロックが落ちてくる某ゲームのクローン。今まで多分 8つの言語、ひとに借りた Palm V、それから Android でも実装した。多分最初に Scala で書いたプログラムも Tetrix だったはずだ。そのうちのいくつかはネットワーク機能があってプレーヤー同士が対戦できた。C# で書いたのには勝手にプレイし続ける AI があった。
最近また Tetrix が書きたくなってきた。Tetrix は難しくは無いけど例題アプリケーションとしては手頃な複雑さがある。例えば、ループや似て異なる演算がいくつかあるため、言語によってはラムダ式やポイントフリースタイルを自慢できる。逆に、UI やイベント処理は基本的な事に対するネイティブなサポートが欠けている事を露見させるかもしれない。
0日目
sbt
後ほど Android 向けに書くつもりだけど、最初は scala swing を使う。コアとなるロジックは別の jar に入れよう。取り敢えず sbt でマルチプロジェクトのビルドを作る:
+- build.sbt
+- library/
| +- src/
| +- main/
| +- scala/
+- project/
| +- build.properties
+- swing/
+- src/
+- main/
+- scala/
これが project/build.properties:
sbt.version=0.13.0
これが build.sbt:
lazy val buildSettings = Seq(
version := "0.2.0-SNAPSHOT",
organization := "com.eed3si9n",
homepage := Some(url("http://eed3si9n.com")),
licenses := Seq("MIT License" -> url("http://opensource.org/licenses/mit-license.php/")),
scalaVersion := "2.10.2",
scalacOptions := Seq("-deprecation", "-unchecked"),
resolvers += Resolver.sonatypeRepo("public")
)
lazy val swingDependencies = Def.setting {
"org.scala-lang" % "scala-swing" % scalaVersion.value
}
lazy val root = (project in file(".")).
settings(buildSettings: _*).
settings(name := "tetrix.scala")
lazy val library = (project in file("library")).
settings(buildSettings: _*)
lazy val swing = (project in file("swing")).
settings(buildSettings: _*).
settings(
fork in run := true,
libraryDependencies += swingDependencies.value
).
dependsOn(library)
swing
次に swing を書く。Scala 逆引きレシピだと、「165: GUIアプリケーションを作りたい」が一応参考になるけど、ある程度 Java Swing を一緒に勉強する必要があると思う。
package com.tetrix.swing
import swing._
import event._
object Main extends SimpleSwingApplication {
import event.Key._
import java.awt.{Dimension, Graphics2D, Graphics, Image, Rectangle}
import java.awt.{Color => AWTColor}
val bluishGray = new AWTColor(48, 99, 99)
val bluishSilver = new AWTColor(210, 255, 255)
def onKeyPress(keyCode: Value) = keyCode match {
case _ => // do something
}
def onPaint(g: Graphics2D) {
// paint something
}
def top = new MainFrame {
title = "tetrix"
contents = mainPanel
}
def mainPanel = new Panel {
preferredSize = new Dimension(700, 400)
focusable = true
listenTo(keys)
reactions += {
case KeyPressed(_, key, _, _) =>
onKeyPress(key)
repaint
}
override def paint(g: Graphics2D) {
g setColor bluishGray
g fillRect (0, 0, size.width, size.height)
onPaint(g)
}
}
}
The scala.swing package もちらっと見たけど、上はだいたい前に書いた Tetrix の実装からもらってきた。
scala swing はセッターメソッド (x_=) をいくつも定義しているため、クラスの本体に直接 x = "foo" のように書くことができる。すがすがしいぐらいに可変 (mutable) なフレームワークだ。UI は全部副作用なので、これはうまくいっていると思う。
抽象 UI
あまり swing に縛られたくないが、特にプラットフォーム間で違いがあるわけでもない。だいたい画面があって、ブロックを動かすインプットがある。プレーヤーかタイマーがゲームがアクションを実行し、ゲームの状態が変わり、結果が画面に表示される。今のところは、ゲームの状態を String の var で代用しよう。
package com.eed3si9n.tetrix
class AbstractUI {
private[this] var lastKey: String = ""
def left() {
lastKey = "left"
}
def right() {
lastKey = "right"
}
def up() {
lastKey = "up"
}
def down() {
lastKey = "down"
}
def space() {
lastKey = "space"
}
def last: String = lastKey
}
以下のようにして swing UI につなぐ:
import com.eed3si9n.tetrix._
val ui = new AbstractUI
def onKeyPress(keyCode: Value) = keyCode match {
case Left => ui.left()
case Right => ui.right()
case Up => ui.up()
case Down => ui.down()
case Space => ui.space()
case _ =>
}
def onPaint(g: Graphics2D) {
g setColor bluishSilver
g drawString (ui.last, 20, 20)
}
これで、左矢印を押すと "left" と表示される面白いゲームができた。
初日はこんなものでいいんじゃないかな。
自分のマシンで試してみる手順:
$ git clone https://github.com/eed3si9n/tetrix.scala.git
$ cd tetrix.scala
$ git co day0v2 -b try/day0
$ sbt swing/run
1日目
昨日はゲームの状態を String で近似化したけど、これを改善しよう。
ゲームのモデル化
画面には 10x20 のグリッドがほしい。現在のピースのみが異なる色で表示されてほしい。次のピースを表示するウィンドウについては後で考える。ピースの種類は case object で表現できる:
sealed trait PieceKind
case object IKind extends PieceKind
case object JKind extends PieceKind
case object LKind extends PieceKind
case object OKind extends PieceKind
case object SKind extends PieceKind
case object TKind extends PieceKind
case object ZKind extends PieceKind
それぞれのブロックは case class で表せる:
case class Block(pos: (Int, Int), kind: PieceKind)
現在のピースとグリッドの両方とも Seq[Block] で表現できる。
case class GameView(blocks: Seq[Block], gridSize: (Int, Int), current: Seq[Block])
これで AbstractUI が GameView のインスタンスを返すように変更できる。
def view: GameView =
GameView(
Seq(Block((5, 5), TKind), Block((6, 5), TKind), Block((7, 5), TKind), Block((6, 6), TKind), Block((0, 0), TKind)),
(10, 20),
Seq(Block((5, 5), TKind), Block((6, 5), TKind), Block((7, 5), TKind), Block((6, 6), TKind)))
ゲームの描画
これはゲームの描画を改善するのに十分な情報だ。
def onPaint(g: Graphics2D) {
val view = ui.view
def buildRect(pos: (Int, Int)): Rectangle =
new Rectangle(pos._1 * (blockSize + blockMargin),
(view.gridSize._2 - pos._2 - 1) * (blockSize + blockMargin),
blockSize, blockSize)
def drawEmptyGrid {
g setColor bluishLigherGray
for {
x <- 0 to view.gridSize._1 - 1
y <- 0 to view.gridSize._2 - 2
val pos = (x, y)
} g draw buildRect(pos)
}
def drawBlocks {
g setColor bluishEvenLigher
view.blocks foreach { b => g fill buildRect(b.pos) }
}
def drawCurrent {
g setColor bluishSilver
view.current foreach { b => g fill buildRect(b.pos) }
}
drawEmptyGrid
drawBlocks
drawCurrent
}
ゲームの状態が可視化できたところで、次は振る舞いも実装してみよう。
ステージ
現在のピースを表すのにブロックの列よりもいい方法が必要だ。Piece クラスは現在位置を (Double, Double) で保持して current をローカル座標系から算出する。
case class Piece(pos: (Double, Double), kind: PieceKind, locals: Seq[(Double, Double)]) {
def current: Seq[Block] =
locals map { case (x, y) =>
Block((math.floor(x + pos._1).toInt, math.floor(y + pos._2).toInt), kind)
}
}
case object Piece {
def apply(pos: (Double, Double), kind: PieceKind): Piece =
kind match {
case TKind => Piece(pos, kind, Seq((-1.0, 0.0), (0.0, 0.0), (1.0, 0.0), (0.0, 1.0)))
}
}
これを使ってゲームの世界の物理系を司る Stage を定義できる。
package com.eed3si9n.tetrix
class Stage(size: (Int, Int)) {
private[this] def dropOffPos = (size._1 / 2.0, size._2 - 3.0)
private[this] var currentPiece = Piece(dropOffPos, TKind)
private[this] var blocks = Block((0, 0), TKind) +: currentPiece.current
def view: GameView = GameView(blocks, size, currentPiece.current)
}
現在のピースを移動させるには、まずそれをグリッドから外に出して (unload)、新しい位置に移動し、グリッドに再読み込みする。
Piece クラスの moveBy はこうなる:
def moveBy(delta: (Double, Double)): Piece =
copy(pos = (pos._1 + delta._1, pos._2 + delta._2))
これが unload と load だ:
class Stage(size: (Int, Int)) {
...
def moveLeft() = moveBy(-1.0, 0.0)
def moveRight() = moveBy(1.0, 0.0)
private[this] def moveBy(delta: (Double, Double)): this.type = {
val unloaded = unload(currentPiece, blocks)
val moved = currentPiece.moveBy(delta)
blocks = load(moved, unloaded)
currentPiece = moved
this
}
private[this] def unload(p: Piece, bs: Seq[Block]): Seq[Block] = {
val currentPoss = p.current map {_.pos}
bs filterNot { currentPoss contains _.pos }
}
private[this] def load(p: Piece, bs: Seq[Block]): Seq[Block] =
bs ++ p.current
}
つなげる
ステージを抽象UI につなげてみよう:
package com.eed3si9n.tetrix
class AbstractUI {
private[this] val stage = new Stage((10, 20))
def left() {
stage.moveLeft()
}
def right() {
stage.moveRight()
}
def up() {
}
def down() {
}
def space() {
}
def view: GameView = stage.view
}
これで swing UI を起動するとピースが移動するのが確認できるはずだ。
specs2
先に進む前に、そろそろスペックが必要だ。UI を使ったゲームをテストするのは容易じゃないけど、出入力をデータ構造として定義したので、それほど難しくない。Scala 逆引きレシピだと、「221: Specs2でテストケースを記述したい」と「222: Specs2で実行結果を検証したい」が参考になる。
最新の spec2 を library プロジェクトに追加する:
lazy val specs2version = "2.2.2"
lazy val libDeps = Def.setting {
"org.specs2" %% "specs2" % specs2version % "test"
}
lazy val library = (project in file("library")).
settings(buildSettings: _*).
settings(
libraryDependencies += libDeps.value
)
以下が現在のピースを移動するスペック:
import org.specs2._
class StageSpec extends Specification { def is = s2"""
This is a specification to check Stage
Moving to the left the current piece should
change the blocks in the view. $left1
Moving to the right the current piece should
change the blocks in the view. $right1
"""
import com.eed3si9n.tetrix._
def stage = new Stage((10, 20))
def left1 =
stage.moveLeft().view.blocks map {_.pos} must contain(allOf(
(0, 0), (3, 17), (4, 17), (5, 17), (4, 18)
)).inOrder
def right1 =
stage.moveRight().view.blocks map {_.pos} must contain(allOf(
(0, 0), (5, 17), (6, 17), (7, 17), (6, 18)
)).inOrder
}
bdd
スペックができたところで「テストファースト」のコーディングも試そう。ピースの初期座標が (5, 17) のとき、moveLeft を 4回呼ぶと壁に当たるはずだ。後続の moveLeft は無視するべきだ。
以下が左壁に当てるスペック:
s2"""
Moving to the left the current piece should
change the blocks in the view $left1
as long as it doesn't hit the wall. $leftWall1
"""
...
def leftWall1 =
stage.moveLeft().moveLeft().moveLeft().moveLeft().moveLeft().
view.blocks map {_.pos} must contain(allOf(
(0, 0), (0, 17), (1, 17), (2, 17), (1, 18)
)).inOrder
期待通り、テストは失敗した:
[info] Moving to the left the current piece should
[info] + change the blocks in the view
[info] x as long as it doesn't hit the wall.
[error] List((0,0), (-1,17), (0,17), (1,17), (0,18)) does not contain (2,17), (1,18) and must not contain '(-1,17)' is equal to '(0,17)', '(0,18)' is equal to '(2,17)' in order (StageSpec.scala:22)
続きはまた明日。
$ git fetch origin
$ git co day1v2 -b try/day1
$ sbt swing/run
2日目
今日は、昨日からの続きで失敗しているテストがある。これは、趣味のプロジェクトの場合は一日の作業を終えるのに便利な方法だ。
[info] Moving to the left the current piece should
[info] + change the blocks in the view
[info] x as long as it doesn't hit the wall.
[error] List((0,0), (-1,17), (0,17), (1,17), (0,18)) does not contain (2,17), (1,18) and must not contain '(-1,17)' is equal to '(0,17)', '(0,18)' is equal to '(2,17)' in order (StageSpec.scala:22)
最後に自分が何をやっていて、次に何をするべきなのかを探るのに 5分以上かかってしまうこともある。失敗しているテストは未来の自分へ「次にやるのはこれ!」とメッセージを残しておくようなものだ。
検証
まず現行の moveBy の実装をみてみよう:
private[this] def moveBy(delta: (Double, Double)): this.type = {
val unloaded = unload(currentPiece, blocks)
val moved = currentPiece.moveBy(delta)
blocks = load(moved, unloaded)
currentPiece = moved
this
}
moved を検証して moved.current内の全てのブロックが範囲内に収まってるかをチェックするだけでいい。Scala コレクションライブラリ にある forall メソッドが正にこの用途にあっている。Scala 逆引きレシピだと、「118: List の要素が条件を満たすか調べたい」が参考になる。if 文をループさせるようなことはここでは必要ない:
private[this] def moveBy(delta: (Double, Double)): this.type = {
validate(
currentPiece.moveBy(delta),
unload(currentPiece, blocks)) map { case (moved, unloaded) =>
blocks = load(moved, unloaded)
currentPiece = moved
}
this
}
private[this] def validate(p: Piece, bs: Seq[Block]): Option[(Piece, Seq[Block])] =
if (p.current map {_.pos} forall inBounds) Some(p, bs)
else None
private[this] def inBounds(pos: (Int, Int)): Boolean =
(pos._1 >= 0) && (pos._1 < size._1) && (pos._2 >= 0) && (pos._2 < size._2)
これでテストはパスするはずだ:
[info] Moving to the left the current piece should
[info] + change the blocks in the view,
[info] + as long as it doesn't hit the wall
回転
ピースが動くようになった所で、回転もやってみよう。初期位置 (5, 17) にある T字のピースと (0, 0) にあるブロックというハードコードされた初期状態を仮定すると、以下のようなスペックとなる:
s2"""
Rotating the current piece should
change the blocks in the view. $rotate1
"""
...
def rotate1 =
rotateCW(s1).blocks map {_.pos} must contain(exactly(
(0, 0), (5, 18), (5, 17), (5, 16), (6, 17)
)).inOrder
Stage クラスには rorateCW() メソッドがまだないため、これはコンパイルさえしないはずだ。
[error] /Users/eed3si9n/work/tetrix.scala/library/src/test/scala/StageSpec.scala:33: value rorateCCW is not a member of com.eed3si9n.tetrix.Stage
[error] stage.rotateCW().view.blocks map {_.pos} must contain(
[error] ^
[error] one error found
[error] (library/test:compile) Compilation failed
最低限コンパイルは通るようにスタブを作る:
def rotateCW() = this
これでまたテストが失敗するようになった。
まず、ピースの回転を実装する:
def rotateBy(theta: Double): Piece = {
val c = math.cos(theta)
val s = math.sin(theta)
def roundToHalf(v: (Double, Double)): (Double, Double) =
(math.round(v._1 * 2.0) * 0.5, math.round(v._2 * 2.0) * 0.5)
copy(locals = locals map { case(x, y) => (x * c - y * s, x * s + y * c) } map roundToHalf)
}
次に、moveBy メソッドをコピペ (!) して rotateBy に変える:
def rotateCW() = rotateBy(-math.Pi / 2.0)
private[this] def rotateBy(theta: Double): this.type = {
validate(
currentPiece.rotateBy(theta),
unload(currentPiece, blocks)) map { case (moved, unloaded) =>
blocks = load(moved, unloaded)
currentPiece = moved
}
this
}
テストは通過した:
[info] Rotating the current piece should
[info] + change the blocks in the view.
リファクタリング
レッド、グリーン、リファクター。コピペした rotateBy を直そう。Piece => Piece の関数を受け取れば二つのメソッドの共通部分を抽出することができる。Scala 逆引きレシピだと、「053: 関数を定義したい」、「054: 関数を引数として渡したい」が参考になる:
def moveLeft() = transformPiece(_.moveBy(-1.0, 0.0))
def moveRight() = transformPiece(_.moveBy(1.0, 0.0))
def rotateCW() = transformPiece(_.rotateBy(-math.Pi / 2.0))
private[this] def transformPiece(trans: Piece => Piece): this.type = {
validate(
trans(currentPiece),
unload(currentPiece, blocks)) map { case (moved, unloaded) =>
blocks = load(moved, unloaded)
currentPiece = moved
}
this
}
これで一発で moveBy と rotateBy を無くすことができた! テストを再び実行して何も壊れなかったかを確認する。
[info] Passed: : Total 4, Failed 0, Errors 0, Passed 4, Skipped 0
関数型へのリファクタリング
Stage クラスはだんだんいい形に仕上がってきてるが、二つの var があるのが気に入らない。状態はそれを保持する独自のクラスに追い出して Stage はステートレスにしよう。
case class GameState(blocks: Seq[Block], gridSize: (Int, Int), currentPiece: Piece) {
def view: GameView = GameView(blocks, gridSize, currentPiece.current)
}
新しい状態を作るための newState メソッドを定義する:
def newState(blocks: Seq[Block]): GameState = {
val size = (10, 20)
def dropOffPos = (size._1 / 2.0, size._2 - 3.0)
val p = Piece(dropOffPos, TKind)
GameState(blocks ++ p.current, size, p)
}
それぞれの「動作」をオブジェクトへのメソッドの呼び出しと考える代わりに、一つの状態から別の状態への遷移だと考えることができる。transformPiece に一工夫して遷移関数を生成してみよう:
val moveLeft = transit { _.moveBy(-1.0, 0.0) }
val moveRight = transit { _.moveBy(1.0, 0.0) }
val rotateCW = transit { _.rotateBy(-math.Pi / 2.0) }
private[this] def transit(trans: Piece => Piece): GameState => GameState =
(s: GameState) => validate(s.copy(
blocks = unload(s.currentPiece, s.blocks),
currentPiece = trans(s.currentPiece))) map { case x =>
x.copy(blocks = load(x.currentPiece, x.blocks))
} getOrElse {s}
private[this] def validate(s: GameState): Option[GameState] = {
val size = s.gridSize
def inBounds(pos: (Int, Int)): Boolean =
(pos._1 >= 0) && (pos._1 < size._1) && (pos._2 >= 0) && (pos._2 < size._2)
if (s.currentPiece.current map {_.pos} forall inBounds) Some(s)
else None
}
これで少し関数型な感じがするようになった。transit か実際に状態遷移関数を返しているかは型シグネチャが保証する。Stage がステートレスになったところで、これをシングルトンオブジェクトに変えることができる。
合わせてスペックも変更する:
import com.eed3si9n.tetrix._
import Stage._
val s1 = newState(Block((0, 0), TKind) :: Nil)
def left1 =
moveLeft(s1).blocks map {_.pos} must contain(exactly(
(0, 0), (3, 17), (4, 17), (5, 17), (4, 18)
)).inOrder
def leftWall1 = sys.error("hmmm")
// stage.moveLeft().moveLeft().moveLeft().moveLeft().moveLeft().
// view.blocks map {_.pos} must contain(exactly(
// (0, 0), (0, 17), (1, 17), (2, 17), (1, 18)
// )).inOrder
def right1 =
moveRight(s1).blocks map {_.pos} must contain(exactly(
(0, 0), (5, 17), (6, 17), (7, 17), (6, 18)
)).inOrder
def rotate1 =
rotateCW(s1).blocks map {_.pos} must contain(excactly(
(0, 0), (5, 18), (5, 17), (5, 16), (6, 17)
)).inOrder
可変実装の moveLeft は this を返したため連鎖 (chain) させることができた。新しい実装ではどうやって leftWall1 を処理すればいいだろう? メソッドの代わりに純粋関数がある。これらは Function.chain を使って合成できる:
def leftWall1 =
Function.chain(moveLeft :: moveLeft :: moveLeft :: moveLeft :: moveLeft :: Nil)(s1).
blocks map {_.pos} must contain(exactly(
(0, 0), (0, 17), (1, 17), (2, 17), (1, 18)
)).inOrder
Function.chain は Seq[A => A] を受け取って A => A の関数に変える。僕達は、この小さい部分だけだけど、コードの一部をデータ扱いしていると考えることができる。
当たり判定
3D ゲームだとリアルタイムでの当たり判定だけで本が一冊書ける。2D の落ちゲーの場合は Scala コレクションを使うと一行で書ける。シナリオをスペックで記述してみよう:
val s2 = newState(Block((3, 17), TKind) :: Nil)
def leftHit1 =
moveLeft(s2).blocks map {_.pos} must contain(
(3, 17), (4, 17), (5, 17), (6, 17), (5, 18)
).only.inOrder
これは期待通り失敗してくれる:
[error] x or another block in the grid.
[error] '(3,17), (3,17), (4,17), (5,17), (4,18)' doesn't contain in order '(3,17), (4,17), (5,17), (6,17), (5,18)' (StageSpec.scala:9)
これが当たり判定を加えた validate メソッドだ:
private[this] def validate(s: GameState): Option[GameState] = {
val size = s.gridSize
def inBounds(pos: (Int, Int)): Boolean =
(pos._1 >= 0) && (pos._1 < size._1) && (pos._2 >= 0) && (pos._2 < size._2)
val currentPoss = s.currentPiece.current map {_.pos}
if ((currentPoss forall inBounds) &&
(s.blocks map {_.pos} intersect currentPoss).isEmpty) Some(s)
else None
}
時計
moveLeft と moveRight があるが、moveDown が無い。これは下向きの動きが他にもすることがあるからだ。床か別のブロックに当たり判定が出た場合は、現在のピースが固まって、新しいピースが送り込まれる。
まずは、動きから:
s2"""
Ticking the current piece should
change the blocks in the view, $tick1
"""
...
def tick1 =
tick(s1).blocks map {_.pos} must contain(exactly(
(0, 0), (4, 16), (5, 16), (6, 16), (5, 17)
)).inOrder
取り敢えずテストが通過するように moveBy を使って tick を実装する:
val tick = transit { _.moveBy(0.0, -1.0) }
次に、新しいピースの転送:
s2"""
or spawn a new piece when it hits something. $tick2
"""
...
def tick2 =
Function.chain(Nil padTo (18, tick))(s1).
blocks map {_.pos} must contain(exactly(
(0, 0), (4, 0), (5, 0), (6, 0), (5, 1),
(4, 17), (5, 17), (6, 17), (5, 18)
)).inOrder
transit メソッドは既に変更された状態の妥当性を知ってる。現在は getOrElse を使って古い状態を返しているだけだけど、そこで別のアクションを実行すればいい。
private[this] def transit(trans: Piece => Piece,
onFail: GameState => GameState = identity): GameState => GameState =
(s: GameState) => validate(s.copy(
blocks = unload(s.currentPiece, s.blocks),
currentPiece = trans(s.currentPiece))) map { case x =>
x.copy(blocks = load(x.currentPiece, x.blocks))
} getOrElse {onFail(s)}
onFail が渡されなければ identity 関数が用いられる。以下が tick だ:
val tick = transit(_.moveBy(0.0, -1.0), spawn)
private[this] def spawn(s: GameState): GameState = {
def dropOffPos = (s.gridSize._1 / 2.0, s.gridSize._2 - 3.0)
val p = Piece(dropOffPos, TKind)
s.copy(blocks = s.blocks ++ p.current,
currentPiece = p)
}
テストを通過したか確認する:
[info] Ticking the current piece should
[info] + change the blocks in the view,
[info] + or spawn a new piece when it hits something
タイマー
抽象UI の中で tick を下矢印キーとタイマーに配線しよう:
import java.{util => ju}
private[this] val timer = new ju.Timer
timer.scheduleAtFixedRate(new ju.TimerTask {
def run { state = tick(state) }
}, 0, 1000)
...
def down() {
state = tick(state)
}
これで現在のピースが勝手に動くようになったけど、swing UI はそのことを知らないので描画はされない。mainPanel を 10 fps で再描画するタイマーを加えてこの問題を直す:
val timer = new SwingTimer(100, new AbstractAction() {
def actionPerformed(e: java.awt.event.ActionEvent) { repaint }
})
timer.start
一番下の列
明らかな問題は一番下の列が消えていないことだ。以下のスペックでテストできると思う:
"""It should also clear out full rows.""" ! tick3^
...
val s3 = newState(Seq(
(0, 0), (1, 0), (2, 0), (3, 0), (7, 0), (8, 0), (9, 0))
map { Block(_, TKind) })
def tick3 =
Function.chain(Nil padTo (18, tick))(s3).
blocks map {_.pos} must contain(
(5, 0), (4, 17), (5, 17), (6, 17), (5, 18)
).only.inOrder
続きはまた明日。
$ git fetch origin
$ git co day2v2 -b try/day2
$ sbt swing/run
3日目
今日のゴールは tetrix の基本機能を仕上げて取り敢えずプレイ可能な状態に持っていくことだ。
REPL
コミュニティー内に Scala でのベスト・プラクティスを提唱している人たちがいる。
- Bill Venners と Dick Wall による Scala Days 2011 での講演 Effective Scala
- Josh Suereth による NEScala 2011 での講演 Effective Scala
- Josh Suereth による本 Scala in Depth
- Twitter社の Marius Eriksen によるページ Effective Scala
コップ本にも書いてあるような「不変性を推奨する」とか「null の代わりに None を使おう」というのは、予想される通り全員が言及している。中でも記憶に残ったのは Venners/Wall の「コレクションを知れ」と「関数やメソッドの戻り値型を常につけてみることを検討しよう」、そして最近だと Josh の「REPL で実験せよ」というものだ。
実験駆動開発 (experiment-driven development) では開発者である君が、テストやプロダクションのコードを書く前に、まずインタープリターや REPL で実験をする。
sbt シェルから console を実行することでプロジェクトのコードがクラスパスに追加された REPL に入ることができる。一番下の列を消去できるようにセットアップしてみよう:
> console
Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import com.eed3si9n.tetrix._
import com.eed3si9n.tetrix._
scala> import Stage._
import Stage._
scala> val s3 = newState(Seq(
| (0, 0), (1, 0), (2, 0), (3, 0), (7, 0), (8, 0), (9, 0))
| map { Block(_, TKind) })
s3: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind), Block((1,0),TKind), Block((2,0),TKind), Block((3,0),TKind), Block((7,0),TKind), Block((8,0),TKind), Block((9,0),TKind), Block((4,17),TKind), Block((5,17),TKind), Block((6,17),TKind), Block((5,18),TKind)),(10,20),Piece((5.0,17.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))))
scala> val s = Function.chain(Nil padTo (17, tick))(s3)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind), Block((1,0),TKind), Block((2,0),TKind), Block((3,0),TKind), Block((7,0),TKind), Block((8,0),TKind), Block((9,0),TKind), Block((4,0),TKind), Block((5,0),TKind), Block((6,0),TKind), Block((5,1),TKind)),(10,20),Piece((5.0,0.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))))
列の消去
埋まった列を全てを消去するために、まず与えられた列のブロックが全て埋まっているかを判定する必要がある。
scala> s.blocks filter {_.pos._2 == 0}
res1: Seq[com.eed3si9n.tetrix.Block] = List(Block((0,0),TKind), Block((1,0),TKind), Block((2,0),TKind), Block((3,0),TKind), Block((7,0),TKind), Block((8,0),TKind), Block((9,0),TKind), Block((4,0),TKind), Block((5,0),TKind), Block((6,0),TKind))
filter を使って列0 だけ取り出せる。戻ってきた列のサイズを見れば全て埋まっているかが分かる。
scala> def isFullRow(i: Int, s: GameState): Boolean =
| (s.blocks filter {_.pos._2 == 0} size) == s.gridSize._1
isFullRow: (i: Int, s: com.eed3si9n.tetrix.GameState)Boolean
scala> isFullRow(0, s)
res2: Boolean = true
次に、列の消去を考える。まず、s.blocks を現在の列の上と下に分ける。
scala> s.blocks filter {_.pos._2 < 0}
res3: Seq[com.eed3si9n.tetrix.Block] = List()
scala> s.blocks filter {_.pos._2 > 0}
res4: Seq[com.eed3si9n.tetrix.Block] = List(Block((5,1),TKind))
それから、消去される列の上のブロックをずらす必要がある。
scala> s.blocks filter {_.pos._2 > 0} map { b =>
| b.copy(pos = (b.pos._1, b.pos._2 - 1)) }
res5: Seq[com.eed3si9n.tetrix.Block] = List(Block((5,0),TKind))
以下は clearFullRow の実装の一例だ:
import scala.annotation.tailrec
private[this] lazy val clearFullRow: GameState => GameState =
(s0: GameState) => {
def isFullRow(i: Int, s: GameState): Boolean =
(s.blocks filter {_.pos._2 == i} size) == s.gridSize._1
@tailrec def tryRow(i: Int, s: GameState): GameState =
if (i < 0) s
else if (isFullRow(i, s))
tryRow(i - 1, s.copy(blocks = (s.blocks filter {_.pos._2 < i}) ++
(s.blocks filter {_.pos._2 > i} map { b =>
b.copy(pos = (b.pos._1, b.pos._2 - 1)) })))
else tryRow(i - 1, s)
tryRow(s0.gridSize._2 - 1, s0)
}
REPL で実験したことをまとめて末尾再帰の関数に入れた。tick を更新してこれを取り込む。
val tick = transit(_.moveBy(0.0, -1.0),
Function.chain(clearFullRow :: spawn :: Nil) )
テストを走らせて確認する:
[info] Ticking the current piece should
[info] + change the blocks in the view,
[info] + or spawn a new piece when it hits something.
[info] + It should also clear out full rows.
列が消えるようになったので、ちょっと一息ついてゲームで遊んでみよう。
ピースのストリーム
面白いが、T字のピースしか出てこないので少し単調だ。ピースをランダムに生成すればいいと反射的に考えるかもしれない。だけど、ランダム性は副作用を導入し、テストを難しくする。Stage や GameState に可変性を持ち込むのは避けたい。これを回避できる方法としてはゲームの状態にピースの無限列を置くことがある。テストの最中はハードコードされた GameState and GameView を入れておけばいい。
以下がが更新された GameState と GameView だ:
case class GameView(blocks: Seq[Block], gridSize: (Int, Int),
current: Seq[Block], next: Seq[Block])
case class GameState(blocks: Seq[Block], gridSize: (Int, Int),
currentPiece: Piece, nextPiece: Piece, kinds: Seq[PieceKind]) {
def view: GameView = GameView(blocks, gridSize,
currentPiece.current, nextPiece.current)
}
以下がスペックだ:
s2"""
The current piece should
be initialized to the first element in the state. $init1
"""
...
val s4 = newState(Nil, OKind :: Nil)
def init1 =
(s4.currentPiece.kind must_== OKind) and
(s4.blocks map {_.pos} must contain(exactly(
(4, 18), (5, 18), (4, 17), (5, 17)
)).inOrder)
次のピースを s.kinds.head を用いて選び、以前に選択した nextPiece を currentPiece として使う。
private[this] lazy val spawn: GameState => GameState =
(s: GameState) => {
def dropOffPos = (s.gridSize._1 / 2.0, s.gridSize._2 - 3.0)
val next = Piece((2, 1), s.kinds.head)
val p = s.nextPiece.copy(pos = dropOffPos)
s.copy(blocks = s.blocks ++ p.current,
currentPiece = p, nextPiece = next, kinds = s.kinds.tail)
}
テストを実行すると別の問題が明らかになる:
> test
[info] Compiling 1 Scala source to /Users/eed3si9n/work/tetrix.scala/library/target/scala-2.9.2/classes...
[error] Could not create an instance of StageSpec
[error] caused by scala.MatchError: OKind (of class com.eed3si9n.tetrix.OKind$)
[error] com.eed3si9n.tetrix.Piece$.apply(pieces.scala:38)
...
TKind に対するマッチしか実装しなかったため、Piece を OKind で初期化することができない。ローカル座標をもっと提供するだけでいい:
case object PieceKind {
def apply(x: Int): PieceKind = x match {
case 0 => IKind
case 1 => JKind
case 2 => LKind
case 3 => OKind
case 4 => SKind
case 5 => TKind
case _ => ZKind
}
}
...
case object Piece {
def apply(pos: (Double, Double), kind: PieceKind): Piece =
Piece(pos, kind, kind match {
case IKind => Seq((-1.5, 0.0), (-0.5, 0.0), (0.5, 0.0), (1.5, 0.0))
case JKind => Seq((-1.0, 0.5), (0.0, 0.5), (1.0, 0.5), (1.0, -0.5))
case LKind => Seq((-1.0, 0.5), (0.0, 0.5), (1.0, 0.5), (-1.0, -0.5))
case OKind => Seq((-0.5, 0.5), (0.5, 0.5), (-0.5, -0.5), (0.5, -0.5))
case SKind => Seq((0.0, 0.5), (1.0, 0.5), (-1.0, -0.5), (0.0, -0.5))
case TKind => Seq((-1.0, 0.0), (0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
case ZKind => Seq((-1.0, 0.5), (0.0, 0.5), (0.0, -0.5), (1.0, -0.5))
})
}
状態に TKind のリストを渡してスペックを直すことで全てのテストが成功するようになっった。以下が swing UI 向けのストリームとなる:
private[this] def randomStream(random: util.Random): Stream[PieceKind] =
PieceKind(random.nextInt % 7) #:: randomStream(random)
次のピース
ビューを使って次のピースを UI に公開できるようになった。
def onPaint(g: Graphics2D) {
val view = ui.view
drawBoard(g, (0, 0), view.gridSize, view.blocks, view.current)
drawBoard(g, (12 * (blockSize + blockMargin), 0),
view.miniGridSize, view.next, Nil)
}
drawBoard は元の onPaint を抽出したものだ。
落下
ゲームを早めるのに現在のピースを他の何かに当たるまで落とせる機能がほしい。
s2"""
Dropping the current piece should
tick the piece until it hits something. $drop1
"""
...
def drop1 =
drop(s1).blocks map {_.pos} must contain(exactly(
(0, 0), (4, 0), (5, 0), (6, 0), (5, 1),
(4, 18), (5, 18), (6, 18), (5, 19)
)).inOrder
これを実装する手軽な方法に transit {_.moveBy(0.0, -1.0)} を 20回呼び出して最後に tick を呼ぶというものがある。余分な transit の呼び出しは当たり判定後は無視される。
val drop: GameState => GameState = (s0: GameState) =>
Function.chain((Nil padTo (s0.gridSize._2, transit {_.moveBy(0.0, -1.0)})) ++
List(tick))(s0)
テストは通過する:
[info] Dropping the current piece should
[info] + tick the piece until it hits something.
まとめ
これで現在のピースを動かし、回転させ、落下できるようになった。埋まった列は消去され、次に出てくるピースも見えるようになった。基本機能を仕上げるという目標は一応達成したと思う。
いつもどおり、コードは github にある:
$ git fetch origin
$ git co day3v2 -b try/day3
$ sbt swing/run
4日目
ここ数日かけて tetrix をゼロから実装してきた。初めに僕はこのゲームを使って新しい考え方とかを試してみるという話をした。既に Scala で tetrix は一度書いたことがあるから Scala だけじゃ僕にとっては目新しいものではない。今回 tetrix を使って考えてみたかったのは並行処理 (concurrency) の取り扱いだ。
並行処理
Goetz の Java Concurrency in Practice (Java並行処理プログラミング) を引用すると:
スレッドセーフなコードを書くということは、その本質において、状態、特に共有された可変状態へのアクセスを管理することにある。
調度良いことに、僕達は既に tetrix の中身をリファクタリングして、それぞれの操作はある GameState から別の状態への遷移関数であるように書き換えた。以下に簡易化した AbstractUI を見てみる:
package com.eed3si9n.tetrix
class AbstractUI {
import Stage._
import java.{util => ju}
private[this] var state = newState(...)
private[this] val timer = new ju.Timer
timer.scheduleAtFixedRate(new ju.TimerTask {
def run { state = tick(state) }
}, 0, 1000)
def left() {
state = moveLeft(state)
}
def right() {
state = moveRight(state)
}
def view: GameView = state.view
}
タイマーは tick(state) を呼び出して state を変更し、プレーヤーもまた moveLeft(state) や moveRight(state) を呼び出して state を変更することができる。これは教科書に出てくるようなスレッド・アンセーフな例だ。以下にタイマースレッドと swing のイベントディスパッチスレッドの不幸な実行例を見てみる:
タイマースレッド: 共有された state を読み込む。現在のピースは (5, 18) にある
イベントスレッド: 共有された state を読み込む。現在のピースは (5, 18) にある
タイマースレッド: tick() 関数を呼び出す
タイマースレッド: tick() は現在のピースが (5, 17) にある新しい状態を返す
イベントスレッド: moveLeft() 関数を呼び出す
イベントスレッド: moveLeft() は現在のピースが (4, 18) にある新しい状態を返す
イベントスレッド: 新しい状態を共有された state に書き込む。現在のピースは (4, 18) にある
タイマースレッド: 新しい状態を共有された state に書き込む。現在のピースは (5, 17) にある
プレーヤーから見ると、左への動きが完全に無視されたか、もしくはピースが一瞬 (4, 18) から (5, 17) へ斜めへジャンプしたように見える。これが競合状態だ。
synchronized
この場合、各タスクが短命で、かつシンプルな可変性のため、state に同期をかけるだけでうまくいくかもしれない。
package com.eed3si9n.tetrix
class AbstractUI {
import Stage._
import java.{util => ju}
private[this] var state = newState(...)
private[this] val timer = new ju.Timer
timer.scheduleAtFixedRate(new ju.TimerTask {
def run { updateState {tick} }
}, 0, 1000)
def left() = updateState {moveLeft}
def right() = updateState {moveRight}
def view: GameView = state.view
private[this] def updateState(trans: GameState => GameState) {
synchronized {
state = trans(state)
}
}
}
synchronized 節を用いることで、state の読み込みと書き込みが atomic に行われることが保証される。この方法はもし可変性が広範囲に渡っていたり、バックグラウンドでの長期のタスクが必要な場合は実用的じゃないかもしれない。
akka
並行性を管理するもう一つの方法は Akka アクターのようなメッセージパッシングフレームワークを用いることだ。アクターの入門としては英語だと Getting Started Tutorial (Scala): First Chapterのチュートリアルをたどっていくだけでアクターが書けるようになる。日本語だと Scala 逆引きレシピの第9章「175: Akkaで並行処理を行いたい」などが参考になる。
まず "akka-actor" を sbt に追加する:
resolvers ++= Seq(
Resolver.sonatypeRepo("public"),
Resolver.typesafeRepo("releases")
)
...
lazy val specs2version = "2.2.2"
lazy val akkaVersion = "2.2.1"
lazy val libDeps = Def.setting { Seq(
"org.specs2" %% "specs2" % specs2version % "test",
"com.typesafe.akka" %% "akka-actor" % akkaVersion
)}
lazy val library = (project in file("library")).
settings(buildSettings: _*).
settings(
libraryDependencies ++= libDeps.value
)
次に actors.scala を始めて、メッセージ型を定義する。
sealed trait StageMessage
case object MoveLeft extends StageMessage
case object MoveRight extends StageMessage
case object RotateCW extends StageMessage
case object Tick extends StageMessage
case object Drop extends StageMessage
case object View extends StageMessage
メッセージを処理するための StageActor を定義する。
class StageActor(s0: GameState) extends Actor {
import Stage._
private[this] var state: GameState = s0
def receive = {
case MoveLeft => state = moveLeft(state)
case MoveRight => state = moveRight(state)
case RotateCW => state = rotateCW(state)
case Tick => state = tick(state)
case Drop => state = drop(state)
case View => sender ! state.view
}
}
これで抽象UI を再配線して内部で Akka アクターを使うように書き換えることができる:
package com.eed3si9n.tetrix
class AbstractUI {
import akka.actor._
import akka.pattern.ask
import scala.concurrent.duration._
import akka.util.Timeout
import scala.concurrent._
implicit val timeout = Timeout(1 second)
import ExecutionContext.Implicits.global
private[this] val initialState = Stage.newState(Block((0, 0), TKind) :: Nil,
randomStream(new scala.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(
0 millisecond, 1000 millisecond, playerActor, Tick)
private[this] def randomStream(random: scala.util.Random): Stream[PieceKind] =
PieceKind(random.nextInt % 7) #:: randomStream(random)
def left() { playerActor ! MoveLeft }
def right() { playerActor ! MoveRight }
def up() { playerActor ! RotateCW }
def down() { playerActor ! Tick }
def space() { playerActor ! Drop }
def view: GameView =
Await.result((playerActor ? View).mapTo[GameView], timeout.duration)
}
これで可変性は playerActor で保護され、これは一度に一つづつのメッセージを取り扱うことが保証されている。また、タイマーがスケジュールに置き換えられたことにも注意してほしい。全般的に、メッセージパッシングを使うことで並行処理における振る舞いをより手軽に推論できるようになったと思う。
ゲームステータス
小さくてもいいから何か機能も追加しよう。新しいピースの転送処理の時に既存のブロックに対する当たり判定が行われていない。もし新しいピースに当たりが検知された場合はゲームは終了するべきだ。以下がスペックになる:
s2"""
Spawning a new piece should
end the game it hits something. $spawn1
"""
...
def spawn1 =
Function.chain(Nil padTo (10, drop))(s1).status must_==
GameOver
コンパイルが通るように GameStatus トレイトから定義していく:
sealed trait GameStatus
case object ActiveStatus extends GameStatus
case object GameOver extends GameStatus
これを GameStatus に追加すると期待通りテストが失敗するようになった:
[info] Spawning a new piece should
[error] x end the game it hits something.
[error] 'ActiveStatus' is not equal to 'GameOver' (StageSpec.scala:29)
spawn の現行の実装は nextPiece を当たり判定無しで取り込んでいる:
private[this] lazy val spawn: GameState => GameState =
(s: GameState) => {
def dropOffPos = (s.gridSize._1 / 2.0, s.gridSize._2 - 2.0)
val next = Piece((2, 1), s.kinds.head)
val p = s.nextPiece.copy(pos = dropOffPos)
s.copy(blocks = s.blocks ++ p.current,
currentPiece = p, nextPiece = next, kinds = s.kinds.tail)
}
ピースを取り込む前に検証に通そう。
private[this] lazy val spawn: GameState => GameState =
(s: GameState) => {
def dropOffPos = (s.gridSize._1 / 2.0, s.gridSize._2 - 2.0)
val s1 = s.copy(blocks = s.blocks,
currentPiece = s.nextPiece.copy(pos = dropOffPos),
nextPiece = Piece((2, 1), s.kinds.head),
kinds = s.kinds.tail)
validate(s1) map { case x =>
x.copy(blocks = load(x.currentPiece, x.blocks))
} getOrElse {
s1.copy(blocks = load(s1.currentPiece, s1.blocks), status = GameOver)
}
}
次に、ステータスが GameOver のときは状態遷移を禁止する:
private[this] def transit(trans: Piece => Piece,
onFail: GameState => GameState = identity): GameState => GameState =
(s: GameState) => s.status match {
case ActiveStatus =>
// do transition
case _ => s
}
プレーヤにも一言言っておく。
view.status match {
case GameOver =>
g setColor bluishSilver
g drawString ("game over",
12 * (blockSize + blockMargin), 7 * (blockSize + blockMargin))
case _ => // do nothing
}
いつもどおり、コードは github にある:
$ git fetch origin
$ git co day4v2 -b try/day4
$ sbt swing/run
5日目
昨日はゲームの状態への並行処理を管理するために 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(
0 millisecond, 1000 millisecond, playerActor, Tick)
private[this] def randomStream(random: util.Random): Stream[PieceKind] =
PieceKind(random.nextInt % 7) #:: randomStream(random)
def left() { playerActor ! MoveLeft }
def right() { playerActor ! MoveRight }
def up() { playerActor ! RotateCW }
def down() { playerActor ! Tick }
def space() { playerActor ! Drop }
def view: GameView =
Await.result((playerActor ? View).mapTo[GameView], timeout.duration)
}
ロックしすぎ
振り返ってみると上の実装は良いものとは言えない。プログラムが「恥ずかしいほど直列」なものになってしまっているからだ。以前の synchronized を使った実装では swing UI がビューを一秒間に 10回問い合わせることができた。この実装でも同じことが行われているけど、他のメッセージと同じメールボックスに入ったため、一つでも演算が 100 ミリ秒以上かかるとメールボックスが溢れてしまう可能性がある。
理想的にはゲームの状態は、新しい状態が上書きされるその瞬間まではロックをかけるべきではない。プレーヤーによる操作とスケジュールされた時計は常に非互換であるので、今のところはこれらを一つづつ処理するのは理にかなっていると思う。
2つ目のアクターのメッセージ型を定義しよう:
sealed trait StateMessage
case object GetState extends StateMessage
case case SetState(s: GameState) extends StateMessage
case object GetView extends StateMessage
このアクターの実装は単純なものだ:
class StateActor(s0: GameState) extends Actor {
private[this] var state: GameState = s0
def receive = {
case GetState => sender ! state
case SetState(s) => state = s
case GetView => sender ! state.view
}
}
次に、StageActor を StateActor に基いて書き換える必要がある。
class StageActor(stateActor: ActorRef) extends Actor {
import Stage._
def receive = {
case MoveLeft => updateState {moveLeft}
case MoveRight => updateState {moveRight}
case RotateCW => updateState {rotateCW}
case Tick => updateState {tick}
case Drop => updateState {drop}
}
private[this] def updateState(trans: GameState => GameState) {
val future = (stateActor ? GetState)(1 second).mapTo[GameState]
val s1 = Await.result(future, 1 second)
val s2 = trans(s1)
stateActor ! SetState(s2)
}
}
最後に抽象UI を少し変えて stateActor を作成する:
package com.eed3si9n.tetrix
class AbstractUI {
// skipping imports...
implicit val timeout = Timeout(100 millisecond)
private[this] val initialState = Stage.newState(Block((0, 0), TKind) :: Nil,
(10, 23), randomStream(new scala.util.Random))
private[this] val system = ActorSystem("TetrixSystem")
private[this] val stateActor = system.actorOf(Props(new StateActor(
initialState)), name = "stateActor")
private[this] val playerActor = system.actorOf(Props(new StageActor(
stateActor)), name = "playerActor")
private[this] val timer = system.scheduler.schedule(
0 millisecond, 700 millisecond, playerActor, Tick)
private[this] def randomStream(random: scala.util.Random): Stream[PieceKind] =
PieceKind(random.nextInt % 7) #:: randomStream(random)
def left() { playerActor ! MoveLeft }
def right() { playerActor ! MoveRight }
def up() { playerActor ! RotateCW }
def down() { playerActor ! Tick }
def space() { playerActor ! Drop }
def view: GameView =
Await.result((stateActor ? GetView).mapTo[GameView], timeout.duration)
}
タイマーの時計とプレーヤーのによるピースの移動の並行処理は引き続き playerActor によって保護される。しかし、これで swing UI は他の処理を待たずに好きなだけビューを読み込めるようになった。
グリッドのサイズ
何度かプレイしてみると、新しいピースの転送ポイントが低いため実質のサイズが 10x20 よりもずっと小さくなっていることに気付いた。これを回避するにはグリッドのサイズを上に伸ばして、下の 20行だけ swing UI で表示するようにすればいいと思う。数字を変えたくないのでスペックでは 10x20 のままとする。newState が gridSize を受け取るようにする:
def newState(blocks: Seq[Block], gridSize: (Int, Int),
kinds: Seq[PieceKind]): GameState = ...
あとの変更は swing UI だ。表示用に短くした gridSize を渡す:
drawBoard(g, (0, 0), (10, 20), view.blocks, view.current)
drawBoard(g, (12 * (blockSize + blockMargin), 0),
view.miniGridSize, view.next, Nil)
次に範囲内のブロックだけに filter をかける:
def drawBlocks {
g setColor bluishEvenLigher
blocks filter {_.pos._2 < gridSize._2} foreach { b =>
g fill buildRect(b.pos) }
}
def drawCurrent {
g setColor bluishSilver
current filter {_.pos._2 < gridSize._2} foreach { b =>
g fill buildRect(b.pos) }
}
これで新しく転送されたピースはグリッドの上端から忍び寄ってくる。
いつもどおり、コードは github にある:
$ git fetch origin
$ git co day5v2 -b try/day5
$ sbt swing/run
6日目
昨日は 2つ目のアクターを導入することでゲームの状態へのアクセスの並行処理を改善した。並行処理を司る強力なツールを手に僕達は新しい旅に出ることができる。例えば人類の制覇だ。tetrix プレーヤーひとりづつ。
Russell と Norvig
大学で計算機科学を専攻に選んだ理由の一つが AI について習うことだった。しかし、実際始まってみると最初の数年間の講義では一切 AI のようなものが出て来なかったのでかなりガッカリした。そこである夏の産学連携 (co-op) インターンシップのときに早起きしてスターバックスに行き、頭の良さそうな大学で AI を教えるのに使っている教科書を読んでみることに決めた。そうして見つけたのが Russell と Norvig の Artificial Intelligence: A Modern Approach (AIMA)だ (邦訳はエージェントアプローチ人工知能 第2版)。
衝撃的な本だった。人間のようなロボットを作ろうとするのではなく、合理的に行動するエージェントという概念を導入した。
エージェントとは、センサを用いてその環境を認識し、アクチュエータを用いて環境に対して行動を取ることができる全てのものだ。
合理的エージェントの構造の一つにモデルベース、効用ベースエージェントというものがある。
+-エージェント--------------+ +-環境-+
| センサ <===== |
| 状態 <----+ | | |
| | | | |
| アクションAを実行すると | | |
| どうなるだろう? | | |
| | | | |
| どれだけ幸せになれるだろう? | | |
| | | | |
| 効用 <----+ | | |
| | | | |
| 次に何をするべきだろう? | | |
| | | | |
| アクチュエータ =====> |
+-------------------------+ +-----+
効用関数 (utility function) は状態 (もしくは一連の状態の列) を関連する幸せさの度合いを表す実数に投射する。
ガツンと来ない? この構造によれば知的にみえるプログラムを構築するのに必要なものはステートマシン (できた!)、効用関数、それから木探索アルゴリズムだけだ。結局データ構造やグラフ理論の講義が役に立つということだ。
効用関数
効用ベースのエージェントの場合は、効用関数の作り方が鍵となる。多分今後いじっていく事になるけどまずはシンプルなものから始めよう。今のところは、幸せさは死んでいないことと、消したラインだと定義する。消極的に聞こえるかもしれないけど、tetrix は負けない事を競うゲームだ。1対1 の tetrix では明確な勝利の定義は無い。対戦相手が負けることでデフォルトとして勝者が決まる。
新しいスペックを作ってこれを記述してみよう:
import org.specs2._
class AgentSpec extends Specification with StateExample { def is = s2"""
This is a specification to check Agent
Utility function should
evaluate initial state as 0.0, $utility1
evaluate GameOver as -1000.0, $utility2
"""
import com.eed3si9n.tetrix._
import Stage._
val agent = new Agent
def utility1 =
agent.utility(s1) must_== 0.0
def utility2 =
agent.utility(gameOverState) must_== -1000.0
}
次に Agent クラスを始めて utility メソッドをスタブする:
package com.eed3si9n.tetrix
class Agent {
def utility(state: GameState): Double = 0.0
}
期待通り 2つ目の例で失敗する:
[info] Utility function should
[info] + evaluate initial state as 0.0,
[error] x evaluate GameOver as -1000.0.
[error] '0.0' is not equal to '-1000.0' (AgentSpec.scala:8)
直そう:
def utility(state: GameState): Double =
if (state.status == GameOver) -1000.0
else 0.0
オールグリーン。特にリファクタリングするものも無い。
ライン
僕らのエージェントの幸せさは消したラインだと定義されているため、その数を覚えておく必要がある。これは StageSpec に入る:
s2"""
Deleting a full row should
increment the line count. $line1
"""
...
def line1 =
(s3.lineCount must_== 0) and
(Function.chain(Nil padTo (19, tick))(s3).
lineCount must_== 1)
GameState に lineCount を加えたもの:
case class GameState(blocks: Seq[Block], gridSize: (Int, Int),
currentPiece: Piece, nextPiece: Piece, kinds: Seq[PieceKind],
status: GameStatus, lineCount: Int) {
def view: GameView = GameView(blocks, gridSize,
currentPiece.current, (4, 4), nextPiece.current,
status, lineCount)
}
期待通りテストは失敗:
[info] Deleting a full row should
[error] x increment the line count.
[error] '0' is not equal to '1' (StageSpec.scala:91)
Stage クラスにおいて、埋まった行が消されているのは tick から呼ばれている clearFullRow 関数のみだ:
private[this] lazy val clearFullRow: GameState => GameState =
(s0: GameState) => {
def isFullRow(i: Int, s: GameState): Boolean =
(s.blocks filter {_.pos._2 == i} size) == s.gridSize._1
@tailrec def tryRow(i: Int, s: GameState): GameState =
if (i < 0) s
else if (isFullRow(i, s))
tryRow(i - 1, s.copy(blocks = (s.blocks filter {_.pos._2 < i}) ++
(s.blocks filter {_.pos._2 > i} map { b =>
b.copy(pos = (b.pos._1, b.pos._2 - 1)) })))
else tryRow(i - 1, s)
tryRow(s0.gridSize._2 - 1, s0)
}
ちょっと見た目が怖いけど、実際のラインの消去が行われいるのが s.copy(blocks = ...) だと気づくだけでいい。その直後に lineCount を付けるだけだ:
s.copy(blocks = ...,
lineCount = s.lineCount + 1)
これでテストは通った:
[info] Deleting a full row should
[info] + increment the line count.
これを効用関数に組み込む。
s2"""
evaluate an active state by lineCount $utility3
"""
...
def utility3 = {
val s = Function.chain(Nil padTo (19, tick))(s3)
agent.utility(s) must_== 1.0
}
再び期待通りテストが失敗する:
[error] x evaluate an active state by lineCount
[error] '0.0' is not equal to '1.0' (AgentSpec.scala:9)
これは簡単だ:
def utility(state: GameState): Double =
if (state.status == GameOver) -1000.0
else state.lineCount.toDouble
探索による問題解決
僕らのエージェントがどれだけ幸せかが分かるようになった所で、「人間だけには tetrix に負けない」という抽象的な問題を木の探索という問題に変えることができた。どの時点においても、エージェントとスケジュールされたタイマーは今まで何度も見た 5つのうち 1つのアクションを取ることができる:
def receive = {
case MoveLeft => updateState {moveLeft}
case MoveRight => updateState {moveRight}
case RotateCW => updateState {rotateCW}
case Tick => updateState {tick}
case Drop => updateState {drop}
}
言い換えると、bestMove とは GameState => StageMessage の関数だ。これが木とどう関係あるって? 初期状態 s0 (time=0 とする) において、エージェントは 5つのアクションを取れる: MoveLeft, MoveRight, etc。これらのアクションは 5つの状態 s1, s2, s3, s4, s5 (time=1 とする) を生み出す。さらに、それぞれの状態はまた 5つに s11, s12, …, s55 と分岐する。これを絵に描くと木構造が見えてくる。
s0
|
+--------------------+--------------------+-------...
s1 s2 s3
| | |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
s11 s12 s13 s14 s15 s21 s22 s23 s24 s25 s31 s32 s33 s34 s35
ノード数は指数関数的に増える。1 + 5 + 5^2。まずは 1段階から始めよう。
テストは以下のように構築する。まず s3 という名前の Drop アクションをするだけでラインが一つ消える状態を用意する。エージェントにアクションを選ばせると Drop を選択するべきだ。陰性対照として、もう一つ別の状態 s1 を用意する。これは特にどのアクションを選んでもいい:
s2"""
Solver should
pick MoveLeft for s1 $solver1
pick Drop for s3 $solver2
"""
...
def solver1 =
agent.bestMove(s1) must_== MoveLeft
def solver2 =
agent.bestMove(s3) must_== Drop
以下がスタブだ:
def bestMove(state: GameState): StageMessage = MoveLeft
期待通りテストは失敗する。
[info] Solver should
[info] + pick MoveLeft for s1
[info] x pick Drop for s3
[error] 'MoveLeft' is not equal to 'Drop' (AgentSpec.scala:32)
続きはまた明日。
$ git fetch origin
$ git co day6v2 -b try/day6
$ sbt swing/run
7日目
昨日から tetrix を解く AI という新たな問題に取り組みはじめた。Russell と Norvig は合理的なエージェントの構造がステートマシン、効用関数、木探索アルゴリズムから構成できるという洞察を与えてくれた。僕らにあるのは最初の 2つと失敗しているテストだ:
[info] Solver should
[info] + pick MoveLeft for s1
[info] x pick Drop for s3
[error] 'MoveLeft' is not equal to 'Drop' (AgentSpec.scala:32)
まず既に知っていること、つまり可能な動きとそれに対応した状態遷移関数を書きだしておく必要がある。
private[this] val possibleMoves: Seq[StageMessage] =
Seq(MoveLeft, MoveRight, RotateCW, Tick, Drop)
private[this] def toTrans(message: StageMessage): GameState => GameState =
message match {
case MoveLeft => moveLeft
case MoveRight => moveRight
case RotateCW => rotateCW
case Tick => tick
case Drop => drop
}
「アクションAを実行するとどうなるだろう?」を実装するためには、possibleMoves, toTrans, それと渡された s0 を使って次の状態をシミュレートする。utility 関数を使って幸せさを計算して、効用を最大化する動きを選べばいい。
def bestMove(s0: GameState): StageMessage = {
var retval: StageMessage = MoveLeft
var current: Double = minUtility
possibleMoves foreach { move =>
val u = utility(toTrans(move)(s0))
if (u > current) {
current = u
retval = move
} // if
}
retval
}
実装が手続き型になったしまったが、メソッドの中なので問題ない。これでソルバーの最初のバージョンができた。エージェントがズルをするのを防ぐため、エージェントアクターに BestMove(s) メッセージを送る GameMasterActor を作る必要がある:
sealed trait AgentMessage
case class BestMove(s: GameState) extends AgentMessage
これがアクターの実装だ:
class AgentActor(stageActor: ActorRef) extends Actor {
private[this] val agent = new Agent
def receive = {
case BestMove(s: GameState) =>
val message = agent.bestMove(s)
println("selected " + message)
stageActor ! message
}
}
class GameMasterActor(stateActor: ActorRef, agentActor: ActorRef) extends Actor {
def receive = {
case Tick =>
val s = getState
if (s.status != GameOver) {
agentActor ! BestMove(getState)
}
}
private[this] def getState: GameState = {
val future = (stateActor ? GetState)(1 second).mapTo[GameState]
Await.result(future, 1 second)
}
}
これは意外なほどシンプルだが強力だ。最良の動きを計算する理由は実際にその動きをすることなので、エージェントアクターは stageActor に直接送信している。組み立ててみよう:
private[this] val system = ActorSystem("TetrixSystem")
private[this] val stateActor = system.actorOf(Props(new StateActor(
initialState)), name = "stateActor")
private[this] val playerActor = system.actorOf(Props(new StageActor(
stateActor)), name = "playerActor")
private[this] val agentActor = system.actorOf(Props(new AgentActor(
playerActor)), name = "agentActor")
private[this] val masterActor = system.actorOf(Props(new GameMasterActor(
stateActor, agentActor)), name = "masterActor")
private[this] val tickTimer = system.scheduler.schedule(
0 millisecond, 700 millisecond, playerActor, Tick)
private[this] val masterTickTimer = system.scheduler.schedule(
0 millisecond, 700 millisecond, masterActor, Tick)
動いた!
swing UI を起動すると、エージェントがゲームを乗っ取って tetrix を解きはじめる!:
[info] Running com.tetrix.swing.Main
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
[info] selected MoveLeft
...
頭が悪すぎる!
探索木が浅すぎるため効用関数の違いが出てくる所まで到達していないからだ。デフォルトで MoveLeft を選択している。最初のオプションは探索木を深くしてより多くの動作をみることだ。いずれは取り組む必要があるけど、結局は問題全般の解決にはならない。第一に、ノード数は指数関数的に増えることを思い出してほしい。第二に、確実に分かっているピースが 2つしかないという問題がある。
ヒューリスティック関数
作戦B はヒューリスティック関数を導入することだ。
h(n) = ノード n からゴールのノードまでの最も安価なコースにかかるコストの見積り
正確には僕らにはゴールとなるノードが無いため、この用語は当てはまらないかもしれないけど、概要としては現状を近似化して木探索を正しい方向につついてやることだ。この場合は、悪い陣形に対するペナルティを作ると考えることができる。例えば、列と列の間に 2つ以上の高さの差があることに対してペナルティを加えよう。差を自乗してペナルティが段階的に厳しくなっていくようにする。
s2"""
penalize having gaps between the columns $utility4
"""
...
def utility4 = {
val s = newState(Seq(
(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
agent.utility(s) must_== -36.0
}
期待通りテストは失敗する:
[info] Utility function should
[info] + evaluate initial state as 0.0,
[info] + evaluate GameOver as -1000.0,
[info] + evaluate an active state by lineCount
[error] x penalize having gaps between the columns
[error] '0.0' is not equal to '-36.0' (AgentSpec.scala:10)
これは REPL を使って解いてみよう。sbt から console と打ち込む。
Welcome to Scala version 2.10.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_51).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import com.eed3si9n.tetrix._
import com.eed3si9n.tetrix._
scala> import Stage._
import Stage._
scala> val s = newState(Seq(
(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind), Block((0,1),TKind),
Block((0,2),TKind), Block((0,3),TKind), Block((0,4),TKind), Block((0,5),TKind),
Block((0,6),TKind), Block((4,18),TKind), Block((5,18),TKind), Block((6,18),TKind),
Block((5,19),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
List(),ActiveStatus,0)
scala> s.blocks map {_.pos} groupBy {_._1}
res0: scala.collection.immutable.Map[Int,Seq[(Int, Int)]] = Map(
5 -> List((5,18), (5,19)), 4 -> List((4,18)), 6 -> List((6,18)),
0 -> List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6)))
これはまずい。現在のピースが s.blocks に入り込んでいる。unload は Stage オブジェクト内のプレイベートなメソッドだ。GameState クラスにリファクタリングしてみる:
case class GameState(blocks: Seq[Block], gridSize: (Int, Int),
currentPiece: Piece, nextPiece: Piece, kinds: Seq[PieceKind],
status: GameStatus, lineCount: Int) {
def view: GameView = ...
def unload(p: Piece): GameState = {
val currentPoss = p.current map {_.pos}
this.copy(blocks = blocks filterNot { currentPoss contains _.pos })
}
def load(p: Piece): GameState =
this.copy(blocks = blocks ++ p.current)
}
Stage を調整すると今のテスト意外は全て通過した。REPL に戻ろう:
... 上に同じ ...
scala> s.unload(s.currentPiece)
res0: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind),
Block((0,1),TKind), Block((0,2),TKind), Block((0,3),TKind), Block((0,4),TKind),
Block((0,5),TKind), Block((0,6),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
scala> s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
res1: scala.collection.immutable.Map[Int,Seq[(Int, Int)]] = Map(
0 -> List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6)))
scala> val heights = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1} map {
case (k, v) => (k, v.map({_._2}).max) }
heights: scala.collection.immutable.Map[Int,Int] = Map(0 -> 6)
scala> heights.getOrElse(1, 0)
res6: Int = 0
scala> (0 to s.gridSize._1 - 2)
res7: scala.collection.immutable.Range.Inclusive = Range(0, 1, 2, 3, 4, 5, 6, 7, 8)
scala> val gaps = (0 to s.gridSize._1 - 2).toSeq map { x =>
heights.getOrElse(x, 0) - heights.getOrElse(x + 1, 0) }
gaps: scala.collection.immutable.IndexedSeq[Int] = Vector(6, 0, 0, 0, 0, 0, 0, 0, 0)
scala> val gaps = (0 to s.gridSize._1 - 2).toSeq map { x =>
heights.getOrElse(x, 0) - heights.getOrElse(x + 1, 0) } filter {_ > 1}
gaps: scala.collection.immutable.IndexedSeq[Int] = Vector(6)
scala> gaps map {x => x * x} sum
res5: Int = 36
実際には上にあるよりも多くの打ち間違いや実験を行った。だけど、何をやってるかは分ってもらえると思う。REPL を使って段階的に演算をつなげていくことで式を構築することができる。答が得られたらそれをエディタにコピペすればいい:
def utility(state: GameState): Double =
if (state.status == GameOver) minUtility
else state.lineCount.toDouble - penalty(state)
private[this] def penalty(s: GameState): Double = {
val heights = s.unload(s.currentPiece).blocks map {_.pos} groupBy {
_._1} map { case (k, v) => (k, v.size) }
val gaps = (0 to s.gridSize._1 - 2).toSeq map { x =>
heights.getOrElse(x, 0) - heights.getOrElse(x + 1, 0) } filter {_ > 1}
gaps map {x => x * x} sum
}
テストは通過するようになった。
[info] Utility function should
[info] + evaluate initial state as 0.0,
[info] + evaluate GameOver as -1000.0,
[info] + evaluate an active state by lineCount
[info] + penalize having gaps between the columns
現在のソルバーにはもう一つ問題がある。Drop 以外は現在のピースが空中に浮かんでいるため評価の対象にならないということだ。これを解決するには既に落ちていなければ Drop を後ろに追加すればいい。これはまず実装を変えてみてどのテストが失敗するかみてみよう:
def bestMove(s0: GameState): StageMessage = {
var retval: StageMessage = MoveLeft
var current: Double = minUtility
possibleMoves foreach { move =>
val ms =
if (move == Drop) move :: Nil
else move :: Drop :: Nil
val u = utility(Function.chain(ms map {toTrans})(s0))
if (u > current) {
current = u
retval = move
} // if
}
retval
}
Function.chain を使った遷移関数の合成が再び出てきた。じゃあ、テストを走らせてみよう。
[info] Solver should
[info] + pick MoveLeft for s1
[error] x pick Drop for s3
[error] 'Tick' is not equal to 'Drop' (AgentSpec.scala:14)
これは驚くことではない。Drop を最後に追加したため、Tick と Drop の違いが無くなったというだけだ。スペックを緩和して直す:
def solver2 =
agent.bestMove(s3) must beOneOf(Drop, Tick)
これでエージェントは MoveLeft 以外の動作も選びはじめたけども、まだグリッドの左にかなり偏っている。
探索木を深くすればましになってくれると思う。続きはまた明日。
$ git fetch origin
$ git co day7v2 -b try/day7
$ sbt swing/run
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
}
バギーなペナルティ
第二の疑惑はペナルティの計算が何かおかしいということだ。テストを加えてみよう:
"""penalize having gaps between the columns""" ! utility4^
...
def utility4 = {
val s = newState(Seq(
(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
agent.utility(s) must_== -36.0
} and {
val s = newState(Seq((1, 0), (1, 1), (2, 1), (2, 2))
map { Block(_, ZKind) }, (10, 20), TKind :: TKind :: Nil)
agent.utility(s) must_== -13.0
}
思った通り失敗する。
[error] x penalize having gaps between the columns
[error] '-4.0' is not equal to '-13.0' (AgentSpec.scala:35)
REPL に入る前に、何度も同じ事を打ち込まなくてもいいように以下を build.scala に加える:
initialCommands in console := """import com.eed3si9n.tetrix._
|import Stage._""".stripMargin,
再読み込みした後で sbt シェルから console と打って REPL を起動する:
[info]
import com.eed3si9n.tetrix._
import Stage._
Welcome to Scala version 2.10.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_51).
Type in expressions to have them evaluated.
Type :help for more information.
scala> move // タブキーを押す
moveLeft moveRight
そう、REPL からはタブ補完まで使える。
scala> val s = newState(Seq((1, 0), (1, 1), (2, 1), (2, 2))
map { Block(_, ZKind) }, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((1,0),ZKind), Block((1,1),ZKind),
Block((2,1),ZKind), Block((2,2),ZKind), Block((4,18),TKind), Block((5,18),TKind),
Block((6,18),TKind), Block((5,19),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
scala> val heights = s.unload(s.currentPiece).blocks map {
_.pos} groupBy {_._1} map { case (k, v) => (k, v.map({_._2}).max) }
heights: scala.collection.immutable.Map[Int,Int] = Map(1 -> 1, 2 -> 2)
scala> val gaps = (0 to s.gridSize._1 - 2).toSeq map { x =>
heights.getOrElse(x, 0) - heights.getOrElse(x + 1, 0) } filter {_ > 1}
gaps: scala.collection.immutable.IndexedSeq[Int] = Vector(2)
Off-by-one エラーだ! 気付いたかな? 一番下の座標が 0 なのにデフォルトで 0 を返している。
あとそれから負の数もフィルター漏れしている。正しい gap はこれだ:
scala> val gaps = (0 to s.gridSize._1 - 2).toSeq map { x =>
heights.getOrElse(x, -1) - heights.getOrElse(x + 1, -1) } filter {math.abs(_) > 1}
gaps: scala.collection.immutable.IndexedSeq[Int] = Vector(-2, 3)
手で計算した -36.0 まで間違っていたためこのバグに気付かなかった。これで全てのテストが通るようになった:
[info] + penalize having gaps between the columns
少しは論理的になったけど、ペナルティは実際のゲームをスコアや正しいセットアップに導いていない気がする。まず、効用関数の報酬部分とペナルティ部分を分けてテストしやすいようにする。次に、高低差の代わりに高さそのものにペナルティを課してみよう。
s2"""
Penalty function should
penalize having blocks stacked up high $penalty1
"""
...
def penalty1 = {
val s = newState(Seq(
(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
agent.penalty(s) must_== 49.0
} and {
val s = newState(Seq((1, 0))
map { Block(_, ZKind) }, (10, 20), TKind :: TKind :: Nil)
agent.penalty(s) must_== 1.0
}
これが新しい penalty だ:
def penalty(s: GameState): Double = {
val heights = s.unload(s.currentPiece).blocks map {
_.pos} groupBy {_._1} map { case (k, v) => v.map({_._2 + 1}).max }
heights map { x => x * x } sum
}
報酬とペナルティのバランスも調整したい。現在はペナルティの回避に比べてラインを消すインセンティブが少なすぎる。
def utility(state: GameState): Double =
if (state.status == GameOver) minUtility
else reward(state) - penalty(state) / 10.0
以下のゲームではやっと一つのラインを消すことができた:
探索木の刈り込み
刈り込み (pruning) を用いることで最終的な選択肢に違いの出ない探索木の部分を無視することができる。
制御無しでは探索木は指数関数的に大きくなっていくため、この概念はここでも当てはまる。
DropとTickを抜くことで分岐数を 5 から 3 に減らせる。既に現在のピースを落とすことを仮定しているため、あとはs0もDrop付きで評価すればいいだけだ。- 次に、現在のピースの 4つの全ての向きを事前に分岐させることで
RotateCWも消える。ほとんどの場合はRotateCW :: MoveLeft :: RotateCW :: Drop :: NilとRotateCW :: RotateCW :: MoveLeft :: Drop :: Nilは同じ状態に到達する。 - 現在のピースを可能なかぎり左に寄せることで
MoveLeftも抜くことができる。
ピースは 4つの向きと 9つの x位置を取ることができる。つまり、指数関数的な木の探索はこれで 36 という定数サイズで近似化できる。
PieceKind に基いて可能な向きの数を列挙する:
private[this] def orientation(kind: PieceKind): Int = {
case IKind => 2
case JKind => 4
case LKind => 4
case OKind => 1
case SKind => 2
case TKind => 4
case ZKind => 2
}
次に、REPL を使って、ある状態からエージェントが何回右か左かに動かせるかを計算する。
scala> val s = newState(Nil, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(
Block((4,18),TKind), Block((5,18),TKind), Block((6,18),TKind), Block((5,19),TKind)),
(10,20),Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
scala> import scala.annotation.tailrec
import scala.annotation.tailrec
scala> @tailrec def leftLimit(n: Int, s: GameState): Int = {
val next = moveLeft(s)
if (next.currentPiece.pos == s.currentPiece.pos) n
else leftLimit(n + 1, next)
}
leftLimit: (n: Int, s: com.eed3si9n.tetrix.GameState)Int
scala> leftLimit(0, s)
res1: Int = 4
右の分も同じに作って、sideLimit メソッドの完成だ:
private[this] def sideLimit(s0: GameState): (Int, Int) = {
@tailrec def leftLimit(n: Int, s: GameState): Int = {
val next = moveLeft(s)
if (next.currentPiece.pos == s.currentPiece.pos) n
else leftLimit(n + 1, next)
}
@tailrec def rightLimit(n: Int, s: GameState): Int = {
val next = moveRight(s)
if (next.currentPiece.pos == s.currentPiece.pos) n
else rightLimit(n + 1, next)
}
(leftLimit(0, s0), rightLimit(0, s0))
}
これで actionSeqs を作る準備が整った:
s2"""
ActionSeqs function should
list out potential action sequences $actionSeqs1
"""
...
def actionSeqs1 = {
val s = newState(Nil, (10, 20), TKind :: TKind :: Nil)
val seqs = agent.actionSeqs(s)
seqs.size must_== 32
}
スタブする:
def actionSeqs(s0: GameState): Seq[Seq[StageMessage]] = Nil
予想通りテストは失敗する:
[info] ActionSeqs function should
[error] x list out potential action sequences
[error] '0' is not equal to '32' (AgentSpec.scala:15)
これが実装となる:
def actionSeqs(s0: GameState): Seq[Seq[StageMessage]] = {
val rotationSeqs: Seq[Seq[StageMessage]] =
(0 to orientation(s0.currentPiece.kind) - 1).toSeq map { x =>
Nil padTo (x, RotateCW)
}
val translationSeqs: Seq[Seq[StageMessage]] =
sideLimit(s0) match {
case (l, r) =>
((1 to l).toSeq map { x =>
Nil padTo (x, MoveLeft)
}) ++
Seq(Nil) ++
((1 to r).toSeq map { x =>
Nil padTo (x, MoveRight)
})
}
for {
r <- rotationSeqs
t <- translationSeqs
} yield r ++ t
}
REPL でアウトプットを見てみる:
scala> val s = newState(Nil, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((4,18),TKind), Block((5,18),TKind),
Block((6,18),TKind), Block((5,19),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
scala> val agent = new Agent
agent: com.eed3si9n.tetrix.Agent = com.eed3si9n.tetrix.Agent@649f7367
scala> agent.actionSeqs(s)
res0: Seq[Seq[com.eed3si9n.tetrix.StageMessage]] = Vector(List(MoveLeft),
List(MoveLeft, MoveLeft), List(MoveLeft, MoveLeft, MoveLeft),
List(MoveLeft, MoveLeft, MoveLeft, MoveLeft), List(), List(MoveRight),
List(MoveRight, MoveRight), List(MoveRight, MoveRight, MoveRight),
List(RotateCW, MoveLeft), List(RotateCW, MoveLeft, MoveLeft),
List(RotateCW, MoveLeft, MoveLeft, MoveLeft),
List(RotateCW, MoveLeft, MoveLeft, MoveLeft, MoveLeft), List(RotateCW),
List(RotateCW, MoveRight), List(RotateCW, MoveRight, MoveRight),
List(RotateCW, MoveRight, MoveRight, MoveRight), List(RotateCW, RotateCW, MoveLeft),
List(RotateCW, RotateCW, MoveLeft, MoveLeft),
List(RotateCW, RotateCW, MoveLeft, MoveLeft, MoveLeft),
List(RotateCW, RotateCW, MoveLeft, MoveLeft, MoveLeft, MoveLeft),
List(RotateCW, RotateCW),...
アクション列の一つに、現在の状態を評価する List() があることに注意してほしい。全てのテストが通る:
[info] ActionSeqs function should
[info] + list out potential action sequences
actionSeqs を使って bestMove を書き換えよう:
def bestMove(s0: GameState): StageMessage = {
var retval: Seq[StageMessage] = Nil
var current: Double = minUtility
actionSeqs(s0) foreach { seq =>
val ms = seq ++ Seq(Drop)
val u = utility(Function.chain(ms map {toTrans})(s0))
if (u > current) {
current = u
retval = seq
} // if
}
println("selected " + retval + " " + current.toString)
retval.headOption getOrElse {Tick}
}
スペックを加えよう。例えば (0, 8) にだけ一つ穴を開けておいて、解くのには回転が何回かと MoveRight が何個も必要な状態はどうだろう? 以前のエージェントだと多分解けなかったはずの問題だ。
s2"""
Solver should
pick MoveLeft for s1 $solver1
pick Drop for s3 $solver2
pick RotateCW for s5 $solver3
"""
...
def s5 = newState(Seq(
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0),
(7, 0), (9, 0))
map { Block(_, TKind) }, (10, 20), ttt)
def solver3 =
agent.bestMove(s5) must_== RotateCW
オールグリーン。次に、swing UI を走らせてみよう。
[info] selected List(RotateCW, MoveLeft, MoveLeft, MoveLeft, MoveLeft) 1.4316304877998318
[info] selected List(MoveLeft, MoveLeft, MoveLeft, MoveLeft) 1.4316304877998318
[info] selected List(MoveLeft, MoveLeft, MoveLeft) 1.4316304877998318
[info] selected List(MoveLeft, MoveLeft) 1.4316304877998318
[info] selected List() 1.4108824377664941
動作がまだ近視眼的だけど、合理性の鱗片が見えてきたと思う。続きはまた明日。
$ git fetch origin
$ git co day8v2 -b try/day8
$ sbt swing/run
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
出力はこうなる:
[info] Running com.tetrix.swing.Main
[info] bestMove took 84 ms
[info] selected List(MoveLeft, MoveLeft, MoveLeft, MoveLeft) -0.3
[info] bestMove took 43 ms
[info] selected List(MoveLeft, MoveLeft, MoveLeft) -0.3
[info] bestMove took 24 ms
[info] selected List(MoveLeft, MoveLeft) -0.3
[info] bestMove took 22 ms
[info] selected List(MoveLeft) -0.3
[info] bestMove took 26 ms
[info] selected List() -0.3
[info] bestMove took 17 ms
[info] selected List() -0.3
[info] bestMove took 10 ms
[info] selected List() -0.3
[info] bestMove took 8 ms
[info] selected List() -0.3
[info] bestMove took 11 ms
[info] selected List() -0.3
[info] bestMove took 13 ms
[info] selected List() -0.3
JIT コンパイラが効いてくる初期は時間が短縮していって、あとはだいたい 10ミリ秒ぐらいに落ち着く。これでだいたいどれぐらいの時間を扱っているのかが分かった。
第二段階
探索木を 2つ目のピースに拡張すると大まかに 36倍の時間がかかることになる。360ミリ秒は悪くない。やってみよう:
def bestMove(s0: GameState): StageMessage = {
var retval: Seq[StageMessage] = Nil
var current: Double = minUtility
stopWatch("bestMove") {
val nodes = actionSeqs(s0) map { seq =>
val ms = seq ++ Seq(Drop)
val s1 = Function.chain(ms map {toTrans})(s0)
val u = utility(s1)
if (u > current) {
current = u
retval = seq
} // if
SearchNode(s1, ms, u)
}
nodes foreach { node =>
actionSeqs(node.state) foreach { seq =>
val ms = seq ++ Seq(Drop)
val s2 = Function.chain(ms map {toTrans})(node.state)
val u = utility(s2)
if (u > current) {
current = u
retval = node.actions ++ seq
} // if
}
}
} // stopWatch
println("selected " + retval + " " + current.toString)
retval.headOption getOrElse {Tick}
}
手筋が良くなってきている。思考時間は 12ミリ秒から 727ミリ秒ぐらいまで範囲があるけど、100 から 200ミリ秒ぐらいにだいたい収まっている。
腕が上がってきたのでピースを落とさせてあげることにする:
class AgentActor(stageActor: ActorRef) extends Actor {
private[this] val agent = new Agent
def receive = {
case BestMove(s: GameState) =>
val message = agent.bestMove(s)
stageActor ! message
}
}
ライン数
消したライン数を swing UI に表示しよう。
val unit = blockSize + blockMargin
g drawString ("lines: " + view.lineCount.toString, 12 * unit, 7 * unit)
これでエージェントに加える変更が性能の向上につながっているかを追跡しやすくなる。
虫歯
エージェントがゲームをプレイするのを見てて思うのが、虫歯を作るのを何とも思っていないということだ。埋まってないスポットの上に 1つまたは複数のブロックがある状態のことを虫歯と呼んでいる。
-fig 1----
xxxx
xxxx x xxx
x x xxxxxx
----------
高さによるペナルティを回避するために、例えば凸凹の表面に I字のバーを垂直に落とすのではなく、平らに寝かせたりする。僕としては虫歯を最小化して以下のようにプレイしてほしい:
-fig 2-----
x
x xxxx
x x xxx
x xxxxxxxx
----------
最初の 4列に注目して高さによるペナルティを計算してみよう。
scala> val fig1 = math.sqrt(List(2, 2, 2, 2) map { x => x * x } sum)
fig1: Double = 4.0
scala> val fig2 = math.sqrt(List(1, 0, 4, 1) map { x => x * x } sum)
fig2: Double = 4.242640687119285
予想通り fig1 の方がペナルティが低くなる。別のブロックを覆っている全てのブロックに対しても、高さ*高さのべナルティを課そう。新しいペナルティは以下のとおり:
scala> val fig1b = math.sqrt(List(2, 2, 2, 2, 2, 2) map { x => x * x } sum)
fig1b: Double = 4.898979485566356
scala> val fig2b = math.sqrt(List(1, 0, 4, 1) map { x => x * x } sum)
fig2b: Double = 4.242640687119285
今回は fig2 の方が優先される。スペックに書いてみよう:
s2"""
Penalty function should
penalize having blocks stacked up high $penalty1
penalize having blocks covering other blocks $penalty2
"""
...
def penalty2 = {
val s = newState(Seq(
(0, 0), (2, 0), (0, 1), (1, 1), (2, 1), (3, 1))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
agent.penalty(s) must beCloseTo(4.89, 0.01)
}
期待通りテストは失敗する:
[info] Penalty function should
[info] + penalize having blocks stacked up high
[error] x penalize having blocks covering other blocks
[error] 4.0 is not close to 4.89 +/- 0.01 (AgentSpec.scala:13)
REPL を使って実装する:
scala> val s = newState(Seq(
(0, 0), (2, 0), (0, 1), (1, 1), (2, 1), (3, 1))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind), Block((2,0),TKind),
Block((0,1),TKind), Block((1,1),TKind), Block((2,1),TKind), Block((3,1),TKind),
Block((4,18),TKind), Block((5,18),TKind), Block((6,18),TKind), Block((5,19),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
scala> val groupedByX = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
groupedByX: scala.collection.immutable.Map[Int,Seq[(Int, Int)]] = Map(
3 -> List((3,1)), 1 -> List((1,1)), 2 -> List((2,0), (2,1)), 0 -> List((0,0), (0,1)))
scala> groupedByX map { case (k, vs) => vs.map(_._2).sorted.zipWithIndex }
res14: scala.collection.immutable.Iterable[Seq[(Int, Int)]] = List(
List((1,0)), List((1,0)), List((0,0), (1,1)), List((0,0), (1,1)))
scala> groupedByX map { case (k, vs) =>
vs.map(_._2).sorted.zipWithIndex.dropWhile(x => x._1 == x._2) }
res15: scala.collection.immutable.Iterable[Seq[(Int, Int)]] = List(
List((1,0)), List((1,0)), List(), List())
scala> val coverups = groupedByX flatMap { case (k, vs) =>
vs.map(_._2).sorted.zipWithIndex.dropWhile(x => x._1 == x._2).map(_._1 + 1) }
coverups: scala.collection.immutable.Iterable[Int] = List(2, 2)
できあがった penalty だ:
def penalty(s: GameState): Double = {
val groupedByX = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
val heights = groupedByX map { case (k, v) => v.map({_._2 + 1}).max }
val coverups = groupedByX flatMap { case (k, vs) =>
vs.map(_._2).sorted.zipWithIndex.dropWhile(x => x._1 == x._2).map(_._1 + 1) }
math.sqrt( (heights ++ coverups) map { x => x * x } sum)
}
これでテストが通る:
[info] Penalty function should
[info] + penalize having blocks stacked up high
[info] + penalize having blocks covering other blocks
ゲームをプレイさせてみよう:
虫歯の回避はうまくいったが、効きすぎているかもしれない。明日に段差のペナルティを再び導入する必要があるかもしれない。
$ git fetch origin
$ git co day9v2 -b try/day9
$ sbt swing/run
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 }
case object OKind extends PieceKind { def toInt = 3 }
case object SKind extends PieceKind { def toInt = 4 }
case object TKind extends PieceKind { def toInt = 5 }
case object ZKind extends PieceKind { def toInt = 6 }
これで 1000個のランダムな整数を生成して sbt シェルに表示できる:
package com.eed3si9n.tetrix
object Scripter {
import Stage._
def main(args: Array[String]) {
args.toList match {
case "generate" :: Nil => println(generateScript)
case _ =>
println("> run generate")
}
}
def generateScript: String =
(Stage.randomStream(new util.Random) map {
_.toInt.toString} take {1000}) mkString
}
実行してみよう:
library> run generate
[info] Running com.eed3si9n.tetrix.Scripter generate
41561156662214336116013264661323530534344000435311202344311644...
表示されたアウトプットを script/0.txt というファイルにコピペする。あと四回実行してそれぞれ 1.txt、..、4.txt に保存する。次にファイルを使ってゲームをスクリプト化する。
def main(args: Array[String]) {
args.toList match {
case "generate" :: Nil => println(generateScript)
case "test" :: Nil => testAll
case _ =>
println("> run test")
println("> run generate")
}
}
def testAll {
val scriptDir = new java.io.File("script")
for (i <- 0 to 4)
test(new java.io.File(scriptDir, i.toString + ".txt"))
}
def test(file: java.io.File) {
val pieces = io.Source.fromFile(file).seq map { c =>
PieceKind(c.toString.toInt)
}
val s0 = newState(Nil, (10, 23), pieces.toSeq)
var s: GameState = s0
val agent = new Agent
while (s.status != GameOver) {
val ms = agent.bestMoves(s)
s = Function.chain(ms map {toTrans})(s)
}
println(file.getName + ": " + s.lineCount.toString)
}
Agent の bestMove に手を加えて Seq[StageMessage] を返す bestMoves にした。
これで sbt シェルから実行できる:
library> run test
[info] Compiling 1 Scala source to /Users/eed3si9n/work/tetrix.scala/library/target/scala-2.9.2/classes...
[info] Running com.eed3si9n.tetrix.Scripter test
0.txt: 7 lines
1.txt: 5 lines
2.txt: 7 lines
3.txt: 9 lines
4.txt: 7 lines
[success] Total time: 61 s, completed Aug 17, 2012 10:17:14 PM
61秒間で 5つのゲームを実行して 7 +/- 2 ラインという結果となった。何回実行してもこれは同じ結果を返す。エージェントがゲームに負けた時のグリッドの様子を見てみよう。
def printState(s: GameState) {
val poss = s.blocks map {_.pos}
(0 to s.gridSize._2 - 1).reverse foreach { y =>
(0 to s.gridSize._1 - 1) foreach { x =>
if (poss contains (x, y)) print("x")
else print(" ")
}
println("")
if (y == 0) (0 to s.gridSize._1 - 1) foreach { x =>
print("-") }
}
println("")
}
アウトプットの例だ:
xxxxxxx
xx xx x
xxx x x
xx xxxxx
xx xxxx
xxxxxxxx
xxx x xx
xxx x xx
xxxxx xx
xxx x xx
xxxxx xx
xxxxxxxx
xxx xxxx
xxxxxxxx
xxxxxxxx
xxx x xx
xxxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
----------
最下行以外の全ての 10番目の列が空になっている。これらをクレバスと呼ぼう。
クレバス
幅が 1 の段差は問題が多い。深さ 2 のクレバスは J、L、もしくは I を使って救う必要がある。深さ 3 と 4 は I だけだ。
----------
x
x
x
x
xx
----------
上の図の現行のペナルティを計算しよう:
scala> val fig = math.sqrt(List(1, 5) map { x => x * x } sum)
fig: Double = 5.0990195135927845
深さ3以上のクレバスは 4 高さ 高さのペナルティを課すべきだ:
scala> val fig = math.sqrt(List(1, 5, 10) map { x => x * x } sum)
fig: Double = 11.224972160321824
スペックにしてみる:
s2"""
penalize having blocks creating deep crevasses $penalty3
"""
...
def penalty3 = {
val s = newState(Seq(
(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
agent.penalty(s) must beCloseTo(11.22, 0.01)
}
期待通りテストは失敗する:
[info] Penalty function should
[info] + penalize having blocks stacked up high
[info] + penalize having blocks covering other blocks
[error] x penalize having blocks creating deep crevasses
[error] 5.0990195135927845 is not close to 11.22 +/- 0.01 (AgentSpec.scala:14)
REPL へ:
scala> val s = newState(Seq(
(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4))
map { Block(_, TKind) }, (10, 20), TKind :: TKind :: Nil)
s: com.eed3si9n.tetrix.GameState = GameState(List(Block((0,0),TKind),
Block((1,0),TKind), Block((1,1),TKind), Block((1,2),TKind), Block((1,3),TKind),
Block((1,4),TKind), Block((4,18),TKind), Block((5,18),TKind), Block((6,18),TKind),
Block((5,19),TKind)),(10,20),
Piece((5.0,18.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),
Piece((2.0,1.0),TKind,List((-1.0,0.0), (0.0,0.0), (1.0,0.0), (0.0,1.0))),List(),ActiveStatus,0)
val groupedByX = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
scala> val heights = groupedByX map { case (k, v) => (k, v.map({_._2 + 1}).max) }
heights: scala.collection.immutable.Map[Int,Int] = Map(1 -> 5, 0 -> 1)
scala> val hWithDefault = heights withDefault { x =>
if (x < 0 || x > s.gridSize._1 - 1) s.gridSize._2
else 0
}
hWithDefault: scala.collection.immutable.Map[Int,Int] = Map(1 -> 5, 0 -> 1)
scala> (-1 to s.gridSize._1 - 1) map { x => hWithDefault(x + 1) - hWithDefault(x) }
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(-19, 4, -5, 0, 0, 0, 0, 0, 0, 0, 20)
scala> (-1 to s.gridSize._1 - 2) map { x =>
val down = hWithDefault(x + 1) - hWithDefault(x)
val up = hWithDefault(x + 2) - hWithDefault(x + 1)
if (down < -2 && up > 2) math.min(hWithDefault(x), hWithDefault(x + 2))
else 0
}
res3: scala.collection.immutable.IndexedSeq[Int] = Vector(5, 0, 0, 0, 0, 0, 0, 0, 0, 0)
これが変更されたペナルティだ:
def penalty(s: GameState): Double = {
val groupedByX = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
val heights = groupedByX map { case (k, v) => (k, v.map({_._2 + 1}).max) }
val hWithDefault = heights withDefault { x =>
if (x < 0 || x > s.gridSize._1 - 1) s.gridSize._2
else 0
}
val crevasses = (-1 to s.gridSize._1 - 2) flatMap { x =>
val down = hWithDefault(x + 1) - hWithDefault(x)
val up = hWithDefault(x + 2) - hWithDefault(x + 1)
if (down < -2 && up > 2) Some(math.min(2 * hWithDefault(x), 2 * hWithDefault(x + 2)))
else None
}
val coverups = groupedByX flatMap { case (k, vs) =>
vs.map(_._2).sorted.zipWithIndex.dropWhile(x => x._1 == x._2).map(_._1 + 1) }
math.sqrt( (heights.values ++ coverups ++ crevasses) map { x => x * x } sum)
}
これでテストが通る:
[info] Penalty function should
[info] + penalize having blocks stacked up high
[info] + penalize having blocks covering other blocks
[info] + penalize having blocks creating deep crevasses
スクリプトテストをもう一回実行してみよう。消されたラインの結果だけの簡易的なアウトプットだけを書く:
lines: Vector(9, 11, 8, 17, 12)
これは 11 +/- 6 ラインだから、7 +/- 2 ラインよりも向上したと言える。
実験してみたいパラメータの一つに現在 1:10 の報酬とペナルティの比率がある。
def utility(state: GameState): Double =
if (state.status == GameOver) minUtility
else reward(state) - penalty(state) / 10.0
ペナルティばかり書いているので、ラインを消すインセンティブが減っているのじゃないかと思っている。1:100 に変更してみよう。
lines: Vector(9, 11, 8, 17, 12)
全く同じ結果となった。スクリプトテストが無ければ予想できなかったことだ。
では、クレバスに対するペナルティに関してはどうだろう? 4 高さ 高さは厳しすぎるだろうか? 高さ * 高さを試そう:
lines: Vector(6, 8, 8, 14, 12)
これは 8 +/- 6 ラインだ。4 高さ 高さの 11 +/- 6 ラインに比べると全般的な劣化と言える。この定数の平方根を crevasseWeight と定義する:
c1 = lines: Vector(6, 8, 8, 14, 12) // 8 +/- 6
c2 = lines: Vector(9, 11, 8, 17, 12) // 11 +/- 6
c3 = lines: Vector(9, 16, 8, 15, 12) // 12 +/- 4
c4 = lines: Vector(9, 16, 8, 15, 12) // 12 +/- 4
3 と 4 が同じ結果となったので、3 以上に増加させる意味はないだろう。
他のパラメータ
高さなどの他のペナルティとのバランスを変えたらどうなるかということが気になる結果となった。
val heightWeight = 2
val weightedHeights = heights.values map {heightWeight * _}
これが結果だ:
h1:c3 = lines: Vector(9, 16, 8, 15, 12) // 12 +/- 4
h2:c3 = lines: Vector(13, 19, 9, 16, 12) // 13 +/- 6
h3:c3 = lines: Vector(20, 20, 20, 18, 43) // 20 +/- 23
h4:c3 = lines: Vector(26, 39, 11, 22, 35) // 26 +/- 13
h5:c3 = lines: Vector(22, 25, 11, 19, 16) // 19 +/- 8
20 +/- 23 ラインと 26 +/- 13 ラインという結果が出てきた! h4 は最小値と最大値が両方とも劣化したけど、中間値は増加した。僕の好みは最小値が大きい h3 だ。
まだテストしていないパラメータは coverupsWeight だ。これは v1、v2、と表記する:
h3:c3:v1 = lines: Vector(20, 20, 20, 18, 43) // 20 +/- 23
h3:c3:v2 = lines: Vector(11, 13, 12, 14, 17) // 13 +/- 4
13 +/- 4 ラインに劣化したので良いアイディアとは言えない。このペナルティごと無くしてしまったらどうだろう?
h3:c3:v0 = lines: Vector(35, 34, 22, 27, 33) // 33 +/- 11
データは嘘をつかない。33 +/- 11 ラインだ。虫歯解析は無駄だったということだ。以下が heightWeight と crevasseWeight のバランスを調整した結果だ:
h0:c1:v0 = lines: Vector(0, 0, 0, 1, 0) // 0 +/- 1
h1:c2:v0 = lines: Vector(35, 21, 19, 27, 21) // 21 +/- 14
h1:c1:v0 = lines: Vector(35, 34, 22, 27, 33) // 33 +/- 11
h12:c11:v0 = lines: Vector(32, 36, 23, 46, 29) // 32 +/- 14
h11:c10:v0 = lines: Vector(34, 34, 23, 52, 29) // 34 +/- 18
h10:c9:v0 = lines: Vector(31, 34, 23, 50, 29) // 31 +/- 19
h9:c8:v0 = lines: Vector(31, 34, 24, 50, 29) // 31 +/- 19
h8:c7:v0 = lines: Vector(31, 34, 24, 50, 29) // 31 +/- 19
h7:c6:v0 = lines: Vector(31, 26, 25, 50, 29) // 29 +/- 21
h6:c5:v0 = lines: Vector(31, 26, 25, 50, 29) // 29 +/- 21
h5:c4:v0 = lines: Vector(31, 25, 14, 49, 32) // 32 +/- 18
h4:c3:v0 = lines: Vector(31, 37, 13, 44, 27) // 31 +/- 18
h3:c2:v0 = lines: Vector(40, 36, 13, 31, 20) // 31 +/- 18
h2:c1:v0 = lines: Vector(29, 29, 16, 24, 17) // 24 +/- 8
h1:c0:v0 = lines: Vector(8, 6, 8, 11, 8) // 8 +/- 3
中間値によれば h11:c10:v0 が勝者だ。以下が変更された penalty:
def penalty(s: GameState): Double = {
val groupedByX = s.unload(s.currentPiece).blocks map {_.pos} groupBy {_._1}
val heights = groupedByX map { case (k, v) => (k, v.map({_._2 + 1}).max) }
val heightWeight = 11
val weightedHeights = heights.values map {heightWeight * _}
val hWithDefault = heights withDefault { x =>
if (x < 0 || x > s.gridSize._1 - 1) s.gridSize._2
else 0
}
val crevassesWeight = 10
val crevasses = (-1 to s.gridSize._1 - 2) flatMap { x =>
val down = hWithDefault(x + 1) - hWithDefault(x)
val up = hWithDefault(x + 2) - hWithDefault(x + 1)
if (down < -2 && up > 2) Some(math.min(crevassesWeight * hWithDefault(x), crevassesWeight * hWithDefault(x + 2)))
else None
}
math.sqrt((weightedHeights ++ crevasses) map { x => x * x } sum)
}
swing UI も健在で、なかなか良いゲームを見せてくれるようになった:
また明日ここから続けよう。いつもどおりコードは github に置いてある。
$ git fetch origin
$ git co day10v2 -b try/day10
$ sbt library/run
$ sbt swing/run
11日目
昨日はヒューリスティック関数の色々な部分を調整するためにゲームをスクリプトから自動化するテストハーネスを書いた。最終的にはパフォーマンスを 7 +/- 2 ラインから 34 +/- 8 ラインまで約5倍引き上げることができた。
HAL 的な瞬間
スクリプトテストばっかりだったので、swing UI のゲームを最後まで見ることにした。ラインを次々と消しながらブロックを低めに押さえていて、ゲームのクオリティーが向上してきたことは初めから感じられた。だいたい 60 ラインぐらいを超えた所でいくつかのミスでブロックが 10 段ぐらいまで積まれてきたが、扱いきれないというほどでは無いと思った。ところが突然のようにピースをドロップし始めた。一つづつ次々と。
エージェントはゲームを放棄したかのようにみえた。後になって気付いたのはアクターのどこかでタイムアウトが生じたせいだろうということだった。
可変長思考サイクル
エージェントに定期的に思考するように命令するのではなく、好きなだけ考えさせてあげることにする。人の反射速度と比べてフェアなように取れるアクションは秒あたり 3つぐらいに制限する。
sealed trait GameMasterMessage
case object Start
class GameMasterActor(stateActor: ActorRef, agentActor: ActorRef) extends Actor {
def receive = {
case Start => loop
}
private[this] def loop {
val minActionTime = 337
var s = getState
while (s.status != GameOver) {
val t0 = System.currentTimeMillis
agentActor ! BestMove(getState)
val t1 = System.currentTimeMillis
if (t1 - t0 < minActionTime) Thread.sleep(minActionTime - (t1 - t0))
s = getState
}
}
private[this] def getState: GameState = {
val future = (stateActor ? GetState)(1 second).mapTo[GameState]
Await.result(future, 1 second)
}
}
ゲームのペースを抑えるため、Drop は Tick に置換する:
class AgentActor(stageActor: ActorRef) extends Actor {
private[this] val agent = new Agent
def receive = {
case BestMove(s: GameState) =>
val message = agent.bestMove(s)
if (message == Drop) stageActor ! Tick
else stageActor ! message
}
}
あまりに長考するとエージェントに損なので 1000 ms ぐらいで止めておく:
val maxThinkTime = 1000
val t0 = System.currentTimeMillis
...
nodes foreach { node =>
if (System.currentTimeMillis - t0 < maxThinkTime)
actionSeqs(node.state) foreach { seq =>
...
}
else ()
}
人対マシン
エージェントの調整ができたので、当然次のステップは人間相手にプレイすることだ。同一の初期状態から 2つのステージアクターを用意しよう。一つはプレーヤにより制御され、もう一つはエージェントにより制御される。
private[this] val initialState = Stage.newState(Nil,
(10, 23), Stage.randomStream(new util.Random))
private[this] val system = ActorSystem("TetrixSystem")
private[this] val stateActor1 = system.actorOf(Props(new StateActor(
initialState)), name = "stateActor1")
private[this] val stageActor1 = system.actorOf(Props(new StageActor(
stateActor1)), name = "stageActor1")
private[this] val stateActor2 = system.actorOf(Props(new StateActor(
initialState)), name = "stateActor2")
private[this] val stageActor2 = system.actorOf(Props(new StageActor(
stateActor2)), name = "stageActor2")
private[this] val agentActor = system.actorOf(Props(new AgentActor(
stageActor2)), name = "agentActor")
private[this] val masterActor = system.actorOf(Props(new GameMasterActor(
stateActor2, agentActor)), name = "masterActor")
private[this] val tickTimer1 = system.scheduler.schedule(
0 millisecond, 701 millisecond, stageActor1, Tick)
private[this] val tickTimer2 = system.scheduler.schedule(
0 millisecond, 701 millisecond, stageActor2, Tick)
masterActor ! Start
def left() { stageActor1 ! MoveLeft }
def right() { stageActor1 ! MoveRight }
def up() { stageActor1 ! RotateCW }
def down() { stageActor1 ! Tick }
def space() { stageActor1 ! Drop }
現在の view は 1つのビューしか返さないため、ペアを返すように変更する。
def views: (GameView, GameView) =
(Await.result((stateActor1 ? GetView).mapTo[GameView], timeout.duration),
Await.result((stateActor2 ? GetView).mapTo[GameView], timeout.duration))
次に swing UI が両方のビューを描画できるようにする。
def onPaint(g: Graphics2D) {
val (view1, view2) = ui.views
val unit = blockSize + blockMargin
val xOffset = mainPanelSize.width / 2
drawBoard(g, (0, 0), (10, 20), view1.blocks, view1.current)
drawBoard(g, (12 * unit, 0), view1.miniGridSize, view1.next, Nil)
drawStatus(g, (12 * unit, 0), view1)
drawBoard(g, (xOffset, 0), (10, 20), view2.blocks, view2.current)
drawBoard(g, (12 * unit + xOffset, 0), view2.miniGridSize, view2.next, Nil)
drawStatus(g, (12 * unit + xOffset, 0), view2)
}
def drawStatus(g: Graphics2D, offset: (Int, Int), view: GameView) {
val unit = blockSize + blockMargin
g setColor bluishSilver
view.status match {
case GameOver =>
g drawString ("game over", offset._1, offset._2 + 8 * unit)
case _ => // do nothing
}
g drawString ("lines: " + view.lineCount.toString, offset._1, offset._2 + 7 * unit)
}
既に drawBoard がリファクタ済みだったため、思ったより簡単だった。
GameMasterActor にレフェリーになってもらってどちらかが負けた時点で勝者も決定するようにする。
case object Victory extends GameStatus
...
class GameMasterActor(stateActor1: ActorRef, stateActor2: ActorRef,
agentActor: ActorRef) extends Actor {
...
private[this] def getStatesAndJudge: (GameState, GameState) = {
var s1 = getState1
var s2 = getState2
if (s1.status == GameOver && s2.status != Victory) {
stateActor2 ! SetState(s2.copy(status = Victory))
s2 = getState2
}
if (s1.status != Victory && s2.status == GameOver) {
stateActor1 ! SetState(s1.copy(status = Victory))
s1 = getState1
}
(s1, s2)
}
}
ステータスを UI に表示しよう:
case Victory =>
g drawString ("you win!", offset._1, offset._2 + 8 * unit)
こんな感じになる:
攻撃
今は二人のプレーヤが隣あってゲームをしているのと変りない。攻撃を導入しよう。どちらかのプレーヤが 2つ以上のラインを消した場合は、相手の次の転送サイクルの時点でグリッドの最下行にいくつかのブロックを加える。
ステージのスペックに記述しよう:
s2"""
Attacks should
increment the pending attack count, $attack1
and change the blocks in the view on spawn. $attack2
"""
...
def attack1 =
notifyAttack(s1).pendingAttacks must_== 1
def attack2 =
Function.chain(notifyAttack :: drop :: Nil)(s1).blocks map {_.pos} must contain(
(0, 1), (4, 1), (5, 1), (6, 1), (5, 2),
(4, 18), (5, 18), (6, 18), (5, 19)
)
スタブする:
val notifyAttack: GameState => GameState = (s0: GameState) => s0
期待通りテストは失敗する:
[info] Attacks should
[error] x increment the pending attack count,
[error] '0' is not equal to '1' (StageSpec.scala:35)
[error] x and change the blocks in the view on a tick.
[error] '(0,0), (4,17), (5,17), (6,17), (5,18)' doesn't contain in order
'(1,0), (4,17), (5,17), (6,17), (5,18)' (StageSpec.scala:36)
これが最初の部分:
val notifyAttack: GameState => GameState = (s0: GameState) =>
s0.copy(pendingAttacks = s0.pendingAttacks + 1)
attack 関数は clearFullRow に似た形になる:
val attackRandom = new util.Random(0L)
private[this] lazy val attack: GameState => GameState =
(s0: GameState) => {
def attackRow(s: GameState): Seq[Block] =
(0 to s.gridSize._1 - 1).toSeq flatMap { x =>
if (attackRandom.nextBoolean) Some(Block((x, 0), TKind))
else None
}
@tailrec def tryAttack(s: GameState): GameState =
if (s.pendingAttacks < 1) s
else tryAttack(s.copy(
blocks = (s.blocks map { b => b.copy(pos = (b.pos._1, b.pos._2 + 1)) } filter {
_.pos._2 < s.gridSize._2 }) ++ attackRow(s),
pendingAttacks = s.pendingAttacks - 1
))
tryAttack(s0)
}
これは以下のように tick に組み込まれる:
val tick = transit(_.moveBy(0.0, -1.0),
Function.chain(clearFullRow :: attack :: spawn :: Nil) )
これでテストは通るようになった:
[info] Attacks should
[info] + increment the pending attack count,
[info] + and change the blocks in the view on spawn.
次に StageActor を使ってお互いの攻撃を通知する。最後の tick で何行のラインが消されたかを lastDeleted として報告する:
case class GameState(blocks: Seq[Block], gridSize: (Int, Int),
currentPiece: Piece, nextPiece: Piece, kinds: Seq[PieceKind],
status: GameStatus = ActiveStatus,
lineCount: Int = 0, lastDeleted: Int = 0,
pendingAttacks: Int = 0) {...}
新しいメッセージ型の Attack を加えて、StageActor で通知を実装しよう:
case object Attack extends StageMessage
class StageActor(stateActor: ActorRef) extends Actor {
import Stage._
def receive = {
case MoveLeft => updateState {moveLeft}
case MoveRight => updateState {moveRight}
case RotateCW => updateState {rotateCW}
case Tick => updateState {tick}
case Drop => updateState {drop}
case Attack => updateState {notifyAttack}
}
private[this] def opponent: ActorRef =
if (self.path.name == "stageActor1") context.actorFor("/stageActor2")
else context.actorFor("/stageActor1")
private[this] def updateState(trans: GameState => GameState) {
val future = (stateActor ? GetState)(1 second).mapTo[GameState]
val s1 = Await.result(future, 1 second)
val s2 = trans(s1)
stateActor ! SetState(s2)
(0 to s2.lastDeleted - 2) foreach { i =>
opponent ! Attack
}
}
}
これで 2行以上のラインが消されると攻撃が行われるようになった。以下に例を見てみる:
I字のバーが下の 4行を消して、3回の攻撃を行う。
続きはまた明日。
$ git fetch origin
$ git co day11v2 -b try/day11
$ sbt swing/run
12日目
昨日はエージェントとプレーヤが対戦できように 2つのステージアクターを作った。より面白くするために相手にゴミブロックを送る攻撃機能も実装した。
不公平な強み
これまでの所エージェントはいかに多くのラインを消せるかということを念頭において調整されてきた。しかし昨日になって突然 2行以上を消さないと有効にならない攻撃機能が導入された。この情報を知っている人間サイドに不公平な強みができたことになる。何とかできないか少し見てみる。
まず、アクションで一度に消されたライン数を管理しよう:
case class GameState(blocks: Seq[Block], gridSize: (Int, Int),
currentPiece: Piece, nextPiece: Piece, kinds: Seq[PieceKind],
status: GameStatus = ActiveStatus,
lineCounts: Seq[Int] = Seq(0, 0, 0, 0, 0),
lastDeleted: Int = 0, pendingAttacks: Int = 0) {
def lineCount: Int =
lineCounts.zipWithIndex map { case (n, i) => n * i } sum
def attackCount: Int =
lineCounts.drop(1).zipWithIndex map { case (n, i) => n * i } sum
...
}
変更された clearFullRow はこうなる:
private[this] lazy val clearFullRow: GameState => GameState =
(s0: GameState) => {
....
val s1 = tryRow(s0.gridSize._2 - 1, s0)
if (s1.lastDeleted == 0) s1
else s1.copy(lineCounts = s1.lineCounts updated
(s1.lastDeleted, s1.lineCounts(s1.lastDeleted) + 1))
}
スクリプティングテストにも手を加えて攻撃カウントを表示するようにする:
println(file.getName + ": " +
s.lineCount.toString + " lines; " +
s.attackCount.toString + " attacks")
(s.lineCount, s.attackCount)
これがその結果だ:
lines : Vector(34, 34, 32, 52, 29)
attacks: Vector(4, 3, 3, 3, 1)
クレバスによるペナルティが攻撃の妨げになっているかもしれないので、高さによるペナルティの比率を現在の 11:10 から 6:5 に引き上げよう。
h11:c10:v0 = lines : Vector(34, 34, 32, 52, 29) // 34 +/- 18
h11:c10:v0 = attacks: Vector(4, 3, 3, 3, 1) // 3 +/- 2
h6:c5:v0 = lines : Vector(31, 26, 25, 50, 29) // 29 +/- 21
h6:c5:v0 = attacks: Vector(4, 1, 0, 5, 1) // 1 +/- 4
中間値が 1 まで落ちてしまった。ブロックが塊になるようにプレッシャーをかけるには虫歯解析を再び導入するべきだ:
h11:c10:v1 = lines : Vector(27, 30, 24, 31, 34) // 30 +/- 4
h11:c10:v1 = attacks: Vector(0, 3, 2, 3, 1) // 3 +/- 3
虫歯解析の問題はもしかしたら他のペナルティと比較して厳しすぎることにあるんじゃないだろうか。虫歯の上にあるブロック一つ一つに対してペナルティを課すのではなく、クレバスのペナルティのように高さ * 高さを使ってみよう:
val coverupWeight = 1
val coverups = groupedByX flatMap { case (k, vs) =>
if (vs.size < heights(k)) Some(coverupWeight * heights(k))
else None
}
coverupWeight の変動は w1、w2 と表記する。
h1:c1:w1 = lines : Vector(21, 14, 16, 23, 12) // 16 +/- 7
h1:c1:w1 = attacks: Vector(2, 0, 2, 2, 1) // 2 +/- 2
h11:c10:w2 = lines : Vector(22, 24, 28, 50, 37) // 28 +/- 22
h11:c10:w2 = attacks: Vector(1, 0, 2, 7, 1) // 1 +/- 6
h11:c10:w1 = lines : Vector(39, 24, 20, 51, 34) // 34 +/- 17
h11:c10:w1 = attacks: Vector(2, 1, 1, 7, 1) // 1 +/- 6
h22:c20:w1 = lines : Vector(39, 24, 24, 50, 34) // 34 +/- 17
h22:c20:w1 = attacks: Vector(2, 1, 3, 7, 1) // 3 +/- 4
h11:c10:w0 = lines : Vector(34, 34, 32, 52, 29) // 34 +/- 18
h11:c10:w0 = attacks: Vector(4, 3, 3, 3, 1) // 3 +/- 2
h2:c1:w1 = lines : Vector(16, 10, 6, 18, 14) // 14 +/- 8
h2:c1:w1 = attacks: Vector(1, 0, 0, 1, 0) // 0 +/- 1
もう一つの可能性としては、ペナルティを高さのかわりにに定数にしてしまうことでさらに弱めるということができる。これは k1、k2 と書く:
h11:c10:k2 = lines : Vector(34, 34, 32, 38, 29) // 34 +/- 5
h11:c10:k2 = attacks: Vector(4, 3, 3, 5, 1) // 3 +/- 2
h11:c10:k1 = lines : Vector(34, 34, 32, 38, 29) // 34 +/- 5
h11:c10:k1 = attacks: Vector(4, 3, 3, 5, 1) // 3 +/- 2
h11:c10:k0 = lines : Vector(34, 34, 32, 52, 29) // 34 +/- 18
h11:c10:k0 = attacks: Vector(4, 3, 3, 3, 1) // 3 +/- 2
ライン当たりの攻撃数では h11:c10:k1 がいい感じなので、これを採用しよう。
Android
このゲームを携帯に載せて友達に見せたら面白そうなので、Android に移植する。まず Android SDK をインストールするか、最後にいつアップデートしたか覚えてないようならばコマンドラインから android を起動して最新の SDK にアップデートする:
$ android
2013年9月現在のところ最新の SDK は Android 4.3 (API 18) だけども、一番古い Jelly Bean である Android 4.1.2 (API 16) もダウンロードする。API 16 を使って Android Virtual Device (AVD) を作る。
pfn/android-plugin
次は sbt の pfn/android-sdk-plugin だ。
project/android.sbt を作って以下を書く:
addSbtPlugin("com.hanhuy.sbt" % "android-sdk-plugin" % "1.0.6")
そして以下の変更を build.sbt に加える:
import android.Keys._
...
lazy val library = (project in file("library")).
settings(buildSettings: _*).
settings(
name := "tetrix_library",
libraryDependencies ++= libDeps.value,
exportJars := true
)
...
lazy val droid = (project in file("android")).
settings(buildSettings: _*).
settings(androidBuild: _*).
settings(
name := "tetrix_droid",
platformTarget in Android := "android-16",
proguardOptions in Android ++= Seq("-dontwarn sun.misc.Unsafe",
"""-keep class akka.** {
| public <methods>;
|}""".stripMargin)
).
dependsOn(library)
sbt を再読み込みして droid プロジェクトへ行くと、devices、device、android:run などのタスクが利用可能になっている。
hello world
Android のアプリは主にアクティビティ、ビュー、スレッドから構成される。tetrix では描画のために Canvas オブジェクトさえ手に入ればいいので、アクティビティもビューもかなりシンプルなものだ。ほとんどのロジックはスレッドに詰め込んでしまったが、これが正しい方法なのかは僕もよく分かっていない。
まずは android/src/main/AndroidManifest.xml を作る。これは画面を横持ちに強制する:
<manifest package="com.eed3si9n.tetrix.droid" xmlns:android="http://schemas.android.com/apk/res/android">
<uses-sdk android:minSdkVersion="16"></uses-sdk>
<application android:label="@string/app_name">
<activity
android:label="@string/app_name"
android:name=".MainActivity"
android:launchMode="singleTop"
android:configChanges="orientation|keyboardHidden"
android:screenOrientation="landscape">
<intent-filter>
<action android:name="android.intent.action.MAIN"></action>
<category android:name="android.intent.category.LAUNCHER"></category>
</intent-filter>
</activity>
</application>
</manifest>
これがアクティビティのクラス:
package com.eed3si9n.tetrix.droid
import android.app.Activity
import android.os.Bundle
class MainActivity extends Activity {
override def onCreate(savedInstanceState: Bundle ) {
super.onCreate(savedInstanceState)
setContentView(R.layout.main)
}
}
レイアウトファイルは droid/src/main/res/layout/main.xml:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="horizontal"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
>
<com.eed3si9n.tetrix.droid.MainView android:id="@+id/main_view"
android:layout_height="fill_parent"
android:layout_width="fill_parent"
/>
</LinearLayout>
これは MainView を参照している:
package com.eed3si9n.tetrix.droid
import android.content.Context
import android.util.AttributeSet
import android.view.{View, SurfaceView, SurfaceHolder, GestureDetector, MotionEvent}
class MainView(context: Context, attrs: AttributeSet) extends SurfaceView(context, attrs) {
val holder = getHolder
val thread = new MainThread(holder, context)
holder addCallback (new SurfaceHolder.Callback {
def surfaceCreated(holder: SurfaceHolder) {
thread.start()
}
def surfaceChanged(holder: SurfaceHolder, format: Int, width: Int, height: Int) {
thread.setCanvasSize(width, height)
}
def surfaceDestroyed(holder: SurfaceHolder) {}
})
setFocusable(true)
setLongClickable(true)
setGesture()
def setGesture() {
val gd = new GestureDetector(new GestureDetector.SimpleOnGestureListener() {
override def onFling(e1: MotionEvent, e2: MotionEvent,
velocityX: Float, velocityY: Float): Boolean = {
thread.addFling(velocityX, velocityY)
true
}
})
setOnTouchListener(new View.OnTouchListener() {
def onTouch(v: View, e: MotionEvent): Boolean = gd.onTouchEvent(e)
})
}
}
最後に再描画のタイミングを管理するためにスレッドの中で無限ループを回す:
package com.eed3si9n.tetrix.droid
import com.eed3si9n.tetrix._
import android.content.Context
import android.view.{SurfaceHolder}
import android.graphics.{Canvas, Paint, Rect}
class MainThread(holder: SurfaceHolder, context: Context) extends Thread {
val quantum = 100
var canvasWidth: Int = _
var canvasHeight: Int = _
val bluishSilver = new Paint
bluishSilver.setARGB(255, 210, 255, 255)
override def run {
var isRunning: Boolean = true
while (isRunning) {
val t0 = System.currentTimeMillis
withCanvas { g =>
g drawText ("hello world", 10, 10, bluishSilver)
}
val t1 = System.currentTimeMillis
if (t1 - t0 < quantum) Thread.sleep(quantum - (t1 - t0))
else ()
}
}
def setCanvasSize(w: Int, h: Int) {
canvasWidth = w
canvasHeight = h
}
def addFling(vx: Float, vy: Float) {
val theta = math.toDegrees(math.atan2(vy, vx)).toInt match {
case x if x < 0 => x + 360
case x => x
}
// do something
}
def withCanvas(f: Canvas => Unit) {
val canvas = holder.lockCanvas(null)
try {
f(canvas)
} finally {
holder.unlockCanvasAndPost(canvas)
}
}
}
上記のコードは “hello world” を秒間10フレームで表示する。残りは組み立てだけだ。
Android の UI
Android にはウィジェットやグラッフィクなどに独自のライブラリがある。これらはドキュメントが整っており、他の UI プラットフォームと特に変わらない。drawBoard などを swing からいくつかの変更を加えるだけで移植することができた。
var blockSize: Int = 18
var ui: Option[AbstractUI] = None
override def run {
ui = Some(new AbstractUI)
var isRunning: Boolean = true
while (isRunning) {
val t0 = System.currentTimeMillis
val (view1, view2) = ui.get.views
synchronized {
drawViews(view1, view2)
}
val t1 = System.currentTimeMillis
if (t1 - t0 < quantum) Thread.sleep(quantum - (t1 - t0))
else ()
}
}
def drawViews(view1: GameView, view2: GameView) =
withCanvas { g =>
blockSize = canvasHeight / 22
bluishSilver.setTextSize(blockSize)
g drawRect (0, 0, canvasWidth, canvasHeight, bluishGray)
val unit = blockSize + blockMargin
val xOffset = canvasWidth / 2
drawBoard(g, (0, 0), (10, 20), view1.blocks, view1.current)
drawBoard(g, (12 * unit, 0), view1.miniGridSize, view1.next, Nil)
drawStatus(g, (12 * unit, 0), view1)
drawBoard(g, (xOffset, 0), (10, 20), view2.blocks, view2.current)
drawBoard(g, (12 * unit + xOffset, 0), view2.miniGridSize, view2.next, Nil)
drawStatus(g, (12 * unit + xOffset, 0), view2)
}
withCanvas はキャンバスが解放されることを保証する loan パターンだ。問題は最近のケータイにはキーボードがついていないということだ。ここにジェスチャーの角度をアクションに変換する例を示す:
def addFling(vx: Float, vy: Float) {
val theta = math.toDegrees(math.atan2(vy, vx)).toInt match {
case x if x < 0 => x + 360
case x => x
}
theta match {
case t if t < 45 || t >= 315 => ui map {_.right()}
case t if t >= 45 && t < 135 => ui map {_.space()}
case t if t >= 135 && t < 225 => ui map {_.left()}
case t if t >= 225 && t < 315 => ui map {_.up()}
case _ => // do nothing
}
}
デバイスへの読み込み
エミュレータに読み込むためには、device を選択して android:run を実行する:
tetrix_droid> devices
[info] Connected devices:
[info] emulator-5554 test_galaxynexus
tetrix_droid> device emulator-5554
[info] default device: emulator-5554
tetrix_droid> android:run
[info] Generating R.java
[info] [debug] cache hit, skipping proguard!
[info] classes.dex is up-to-date
[info] Debug package does not need signing: tetrix_droid-debug-unaligned.apk
[info] zipaligned: tetrix_droid-debug.apk
[info] Installing...
エミュレータに表示された。
実際の動作を確認するために実機に載せてみよう。これは僕の htc one で実行された tetrix だ:
エージェントは動いてはいるが、すごい悪手ばかり選んでくる。
続きはまた明日。
$ git fetch origin
$ git co day12v2 -b try/day12
$ sbt swing/run
13日目
昨日は Android アプリを作って携帯に読み込ませた。しかし、エージェントは悪手ばっかり選んできた。
println デバッグ
何が起こっているのか調査するために、library の中の println文をいくつかアンコメントしてみる。
次に $ANDROID_HOME/platform-tools/ から adb -e shell を実行してエミュレータ内で adb シェルのセッションを開始する。詳細は Android Debug Bridge を参照。次に adb シェル内から:
root@android:/ # logcat System.out:D *:S
I/System.out( 873): bestMove took 13464 ms
I/System.out( 873): selected List(MoveLeft, Drop) -0.03301514803843836
I/System.out( 873): bestMove took 12045 ms
I/System.out( 873): selected List(MoveLeft, Drop) -0.03301514803843836
I/System.out( 873): bestMove took 10781 ms
I/System.out( 873): selected List(MoveLeft, Drop) -0.03301514803843836
これでアプリ内の println の呼び出しが画面にストリームされるようになった。
次の一手を計算するのに 10秒以上かかっていて、これは現在計算の要請を行っているペースをかなり下回っている。これだけ遅れると次の一手は古い状態に基いて計算されることになり、最新の状態に対しては酷い一手の推論となる。これを回避するには次の一手の計算を GameMasterActor のループ内でブロックさせることだ:
def receive = {
case Start => loop
}
private[this] def loop {
var s = getStatesAndJudge._2
while (s.status == ActiveStatus) {
val t0 = System.currentTimeMillis
val future = (agentActor ? BestMove(getState2, maxThinkTime))(60 second)
Await.result(future, 60 second)
val t1 = System.currentTimeMillis
if (t1 - t0 < minActionTime) Thread.sleep(minActionTime - (t1 - t0))
s = getStatesAndJudge._2
}
}
./adb -d shell を用いて接続された携帯内での adb シェルセッションを開始する。
I/System.out(32611): bestMove took 1582 ms
I/System.out(32611): selected List(Drop) 0.9113095270054331
I/System.out(32611): bestMove took 2025 ms
I/System.out(32611): selected List(Drop) 0.9113095270054331
I/System.out(32611): bestMove took 1416 ms
I/System.out(32611): selected List(RotateCW, MoveLeft, MoveLeft, MoveLeft, MoveLeft, Drop) 0.8973939572929547
I/System.out(32611): bestMove took 1483 ms
I/System.out(32611): selected List(MoveRight, MoveRight, MoveRight, MoveRight, Drop) 0.9022247475073575
まともな計算結果になってきたけど、携帯でも結構時間がかかっている。
一考二行
これまでエージェントはアクションの列を計算して、初手だけを次の一手として取り出してあとは捨てていた。次の思考サイクルでもこれが繰り返される。普通のマシンの速さだとこれでも大丈夫そうだった。携帯だとこの計算に約10倍の時間がかかる。それでも人間プレーヤも重力もお構いなしなので、この無駄がゲーム性能に響いてくる。
エージェントアクターを改良して最良のアクションの列を計算させて、それを逐次実行するようにできる。
case class BestMoves(s: GameState, minActionTime: Long, maxThinkTime: Long) extends AgentMessage
class AgentActor(stageActor: ActorRef) extends Actor {
private[this] val agent = new Agent
def receive = {
case BestMoves(s, minActionTime, maxThinkTime) =>
agent.bestMoves(s, maxThinkTime) match {
case Seq(Tick) => // do nothing
case Seq(Drop) => stageActor ! Tick
case ms =>
ms foreach { _ match {
case Tick | Drop => // do nothing
case m =>
stageActor ! m
Thread.sleep(minActionTime)
}}
}
sender ! ()
}
}
これはうまくいった。これでエージェントがしばらくゲームを続けられるようになった。
設定
このロジックの設定部分を Config にリファクタリングする。
case class Config(
minActionTime: Long,
maxThinkTime: Long,
onDrop: Option[StageMessage])
sealed trait AgentMessage
case class BestMoves(s: GameState, config: Config) extends AgentMessage
class AgentActor(stageActor: ActorRef) extends Actor {
private[this] val agent = new Agent
def receive = {
case BestMoves(s, config) =>
agent.bestMoves(s, config.maxThinkTime) match {
case Seq(Tick) => // do nothing
case Seq(Drop) => config.onDrop map { stageActor ! _ }
case ms =>
ms foreach { _ match {
case Tick | Drop => // do nothing
case m =>
stageActor ! m
Thread.sleep(config.minActionTime)
}}
}
sender ! ()
}
}
これでプラットフォームに応じてゲームバランスを調整できるようになった。swing UI は以下の設定:
val config = Config(minActionTime = 151,
maxThinkTime = 1500,
onDrop = Some(Tick))
val ui = new AbstractUI(config)
Android 版は遅めの CPU に合わせる形で設定を変える:
val config = Config(
minActionTime = 51,
maxThinkTime = 1000,
onDrop = None)
ui = Some(new AbstractUI(config))
適者生存
昨日、攻撃数を上げるためにペナルティのパラメータを調整したけど、まだ少しおとなし目な気がする。
h11:c10:k1 = lines : Vector(34, 34, 32, 38, 29) // 34 +/- 5
h11:c10:k1 = attacks: Vector(4, 3, 3, 5, 1) // 3 +/- 2
一行しか消去しなかったときの賞与を無くせば改善するんじゃないだろうか。
def reward(s: GameState): Double =
if (s.lastDeleted < 2) 0
else s.lastDeleted
これが結果だ:
h11:c10:k1:s0 = lines : Vector(25, 34, 24, 38, 39) // 34 +/- 5
h11:c10:k1:s0 = attacks: Vector(2, 3, 1, 5, 0) // 2 +/- 3
ライン数の最小値は 24 に減少、攻撃数の最小値は変わらなかった。常にラインを消し続けているタイプのプレーヤーではなくなったので、不安定になった感じだ。
虫歯、再び
厳しさを増すために、虫歯のペナルティーを再び増やしてみる。
h11:c10:w1:s0 = lines : Vector(39, 24, 20, 51, 34) // 34 +/- 17
h11:c10:w1:s0 = attacks: Vector(2, 1, 1, 7, 1) // 1 +/- 6
興味深いことに攻撃数の中間値は 1 まで減少したけど、ライン数の最大値は 51 にもなった。1.txt の結果はこうなっている:
xx
xxx
xxx
xxx x
xxxxxx
xx xxxxxx
x xxxxxxxx
xxxxx xxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxx x
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
----------
クレバスの深さ
次に、攻撃のチャンスを作るために、クレバスの深さが 4 以上じゃなければ罰しないことにした。
h11:c'10:w1:s0 = lines : Vector(39, 39, 18, 52, 25) // 39 +/- 21
h11:c'10:w1:s0 = attacks: Vector(3, 5, 2, 6, 0) // 3 +/- 3
これでゲームが少し安定してきた。Android 版はそこそこ遊べるようになった。一方 swing は今回のアグレッシブな調整を経てアツくなってきてる。
ライン数だけ見るとエージェントの方が優っている。
謝辞
さて、Scala で書く tetrix もこれで最終回だ。コメントやリツイートありがとう。意見や至らない所があれば是非聞かせてほしい。それから、腕に自信がある人は人間を倒せるぐらい頭の良いエージェントアクターを pull request で送ってほしい!