tetrix in Scala
This is compiled from a blog series I originally wrote in August 2012. The all code and tools were updated to the latest in September 2013.
Every now and then I get an urge to explore a new platform, new ways of thinking, even a new programming language. The first thing I try to implement is always the same: a clone of the famous falling block game. I’ve implemented them in I think eight languages, Palm V that I borrowed, and on Android. Probably the first Scala program I wrote was Tetrix too. Some had network capability so two players could play against each other, and C# one had AI that kept playing on its own.
I feel like writing Tetrix again. It’s non-trivial enough that it lends itself well as an example application. The looping and similar-but-different operations allows languages to showcase lambda or point-free style. The UI and event handling may reveal lack of native support for basic things.
day 0
sbt
I want to eventually target Android, but initially I’ll code using scala swing. The core logic should be in a separate jar. So the first thing I do is to create a multi-project build using sbt:
+- build.sbt
+- library/
| +- src/
| +- main/
| +- scala/
+- project/
| +- build.properties
+- swing/
+- src/
+- main/
+- scala/
Here’s project/build.properties:
sbt.version=0.13.0
Here’s 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
Now let’s write 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)
}
}
}
I did glance a bit of The scala.swing package, but I took most of the above from my first Tetrix implemention.
scala swing implements a bunch of setter methods (x_=) so we can write x = "foo" strait in class body. It’s almost refershing to see how proudly mutable this framework is, and I think it works here since UI is one big side effect anyway.
abstract UI
I don’t want to be tied to swing, but there aren’t much difference among the platforms. Mostly you have some screen and input to move blocks around. So, the player or the timer takes actions that changes the state of the game, and the result is displayed on the screen. For now, let’s approximate the state using a 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
}
We can hook this up to the swing UI as follows:
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)
}
So now, we have an exciting game that displays "left" when you hit left arrow key.
I think this is good enough for the first day.
To run this on your machine,
$ git clone https://github.com/eed3si9n/tetrix.scala.git
$ cd tetrix.scala
$ git co day0v2 -b try/day0
$ sbt swing/run
day1
Yesterday, we approximated the game state using String. Let’s see how we can improve this.
modeling the game
On screen there should be a 10x20 grid. I only want the current piece to be rendered in different color. We’ll deal with the next piece window later. The different kinds of pieces can be represented using case objects:
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
Individual blocks can be represented using a case class:
case class Block(pos: (Int, Int), kind: PieceKind)
Both the current piece and the grid can be presented using Seq[Block].
case class GameView(blocks: Seq[Block], gridSize: (Int, Int), current: Seq[Block])
Now we can change the AbstractUI to return an instance of 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)))
drawing the game
This is enough information to start drawing the game better.
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
}
Now that we have a way to visualize the game state, we should implement some moves.
stage
We need a better way of representing the current piece besides a sequence of blocks. A Piece class should keep the current position in (Double, Double) and calculate the current from the local coordinate system.
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)))
}
}
This allows us to define Stage which enforces the physics within the game world.
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)
}
To move the current piece, it is unloaded from the grid, moved to a new position, and then reloaded back in.
Here’s the moveBy for Piece class:
def moveBy(delta: (Double, Double)): Piece =
copy(pos = (pos._1 + delta._1, pos._2 + delta._2))
and here’s the unloading and loading:
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
}
wiring it up
Let’s wire the stage up to the abstract 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
}
You should be able run swing UI and see the piece move.
specs2
Before we go any further we better have some specs. Testing UI-based games are not easy, but we’ve defined inputs and outputs in terms of data structure, so it’s not that hard.
Add the latest specs2 to library project:
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
)
Here’s the specs for moving the current piece:
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
Now that we have a spec, let’s try some “test first” coding. Given that the initial coordinate for the piece is (5, 17), it takes four moveLefts to hit the wall. The subsequent moveLeft should be ignored.
Here’s the spec for hitting the left wall:
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
As expected, this test fails:
[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)
We’ll get back to this tomorrow.
$ git fetch origin
$ git co day1v2 -b try/day1
$ sbt swing/run
day 2
We have a failing test from yesterday, which is a cool way to end a day for a hobby project.
[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)
Sometimes it takes five minutes just to catch yourself up to where you last left off and what needs to be done next. A failing test case is a way to tell your future self “hey, work on this next!”
validation
Let’s see the current implementation of 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
}
All we need here is a validation of moved by checking that all blocks in moved.current are within the bounds. Scala collection library has forall method that does exactly that. No need for looping if statements:
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)
This should pass the test:
[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
rotation
Now that the piece can move, we should try rotation. Given the hard-coded initial state of having T piece at (5, 17) and a block at (0, 0), here’s the spec:
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
This shouldn’t even compile because Stage class doesn’t have rotateCW() method yet.
[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
Stub it out:
def rotateCW() = this
and we’re back to a failing test case.
First, we implement the rotation at the piece level:
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)
}
And then we copy-paste (!) the moveBy method and make it into 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
}
This now passes the test:
[info] Rotating the current piece should
[info] + change the blocks in the view.
refactoring
Red, green, and refactor. Let’s fix the copy-pasted rotateBy. We can extract out common parts by simply accepting a function Piece => Piece:
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
}
This gets rid of the moveBy and rotateBy in a single shot! Run the tests again to make sure we didn’t break anything.
[info] Passed: : Total 4, Failed 0, Errors 0, Passed 4, Skipped 0
functional refactoring
Stage class is shaping up to be a nice class, but I really don’t like the fact that it has two vars in it. Let’s kick out the states into its own class so we can make Stage stateless.
case class GameState(blocks: Seq[Block], gridSize: (Int, Int), currentPiece: Piece) {
def view: GameView = GameView(blocks, gridSize, currentPiece.current)
}
Let’s define a newState method to start a new state:
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)
}
We can now think of each “moves” as transition from one state to another instead of calling methods on an object. We can tweak the transformPiece to generate transition functions:
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
}
This feels more functional style. The type signature makes sure that transit does in fact return a state transition function. Now that Stage is stateless, we can turn it into a singleton object.
The specs needs a few modification:
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
The mutable implementation of moveLeft returned this so we were able to chain them. How should we handle leftWall1? Instead of methods, we now have pure functions. These can be composed using 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 takes a Seq[A => A] and turns it into an A => A function. We are essentially treating a tiny part of the code as data.
collision detection
For 3D games, you could write a whole book on real-time collision detection. Using Scala collection, we can write one for Tetrix in one line. Let’s describe the scenario in specs:
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
This fails as expected:
[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)
Here’s the updated validate method:
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
}
tick
We have moveLeft and moveRight, but no moveDown. This is because downward movement needs to do more. Once it detects collision agaist the floor or another block, the current piece freezes at its place and a new piece gets dropped in.
First, the movement:
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
To get this test passed we can implement tick as using moveBy:
val tick = transit { _.moveBy(0.0, -1.0) }
Next, the new piece:
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
The transit method already knows the validity of the modified state. Currently it’s just returning the old state using getOrElse. All we have to do is put some actions in there.
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)}
Unless onFail is passed in, it uses identity function. Here’s the 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)
}
Let’s see if this passes the test:
[info] Ticking the current piece should
[info] + change the blocks in the view,
[info] + or spawn a new piece when it hits something
timer
Let’s hook tick up to the down arrow key and a timer in the abstract UI:
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)
}
This will move the current piece on its own. But since the swing UI doesn’t know about it, so it won’t get rendered. We can add another timer to repaint the mainPanel 10 fps to fix this issue:
val timer = new SwingTimer(100, new AbstractAction() {
def actionPerformed(e: java.awt.event.ActionEvent) { repaint }
})
timer.start
bottom line
The obvious issue here is that the bottom row is not clearing. Here’s a spec that should test this:
s2"""
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(exactly(
(5, 0), (4, 17), (5, 17), (6, 17), (5, 18)
)).inOrder
We’ll get back to this tomorrow.
$ git fetch origin
$ git co day2v2 -b try/day2
$ sbt swing/run
day 3
Today’s goal is to finish up the basic feature of Tetrix so it’s playable.
REPL
A few people in the community is coming up with best practices in Scala.
- Effective Scala talk at Scala Days 2011 by Bill Venners and Dick Wall
- Effective Scala talk at NEScala 2012 by Josh Suereth
- Scala in Depth book by Josh Suereth
- Effective Scala page by Marius Eriksen at Twitter
As you would expect all of them mention to “Favor Immutability” and “Use None instead of null” like Programming in Scala book. Some of the notable ones are “Know Your Collections” and “Consider Always Providing Return Types on Functions and Methods” by Venners/Wall, and more recently “Experiment in the REPL” by Josh.
Experiment-driven development is where you, the developer, first spend some time experimenting with a live interpreter or REPL before writing tests or production code.
From the sbt shell, you can run console to get into the RELP which automatically loads your code into the classpath. Let’s try to create the setup for clearing the bottom row:
> 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))))
clearing rows
To clear all full rows, let’s first figure out if a given row is full.
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))
We can filter to just row 0. We can count the size of the returned sequence to see if it’s full.
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
Next let’s figure out how to clear out the row. We can first split the s.blocks into parts above and below the current row.
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))
Next, we need to shift all the blocks down for ones above the cleared row.
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))
Here’s an implementation of 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)
}
It puts together what we experimented in the REPL and wraps it in a tail recursive function. Here’s the updated tick function to incorporate this:
val tick = transit(_.moveBy(0.0, -1.0),
Function.chain(clearFullRow :: spawn :: Nil) )
We can now run the tests to check:
[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.
Now that the rows clear, we can take some break by playing the game.
stream of pieces
It’s fun, but the game is somewhat predictable because it keeps giving us Ts. The first impulse may be to generate pieces randomly. But randomness introduces side-effect, which makes it hard to test. We don’t want mutability in Stage or GameState. One way to work around this is by keeping an infinite sequence of pieces in the game state. During the testing we can pass in a hard-coded Seq[PieceKind].
Here are the updated GameState and 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)
}
Here’s the spec:
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)
We’ll pick the next piece using s.kinds.head, and we’ll use the previously picked nextPiece as the 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)
}
Running the test reveals another problem:
> 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)
...
A Piece can’t be initialized for OKind because we only implemented match for TKind. We just have to provide more local coordinates:
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))
})
}
After fixing the specs by passing in a list of TKinds to states, all the tests pass. Here’s the random stream for swing UI:
private[this] def randomStream(random: util.Random): Stream[PieceKind] =
PieceKind(random.nextInt % 7) #:: randomStream(random)
next piece
We can now work on exposing the next piece to the UI via view.
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 is extracted version of what was originally in onPaint.
drop
To speed up the game, the user should be able to drop the current piece until it hits something.
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
One way to implement this is to call transit {_.moveBy(0.0, -1.0)} 20 times, and then call tick at the end. The extra transit calls after hitting something would just be ignored.
val drop: GameState => GameState = (s0: GameState) =>
Function.chain((Nil padTo (s0.gridSize._2, transit {_.moveBy(0.0, -1.0)})) ++
List(tick))(s0)
This passes the test:
[info] Dropping the current piece should
[info] + tick the piece until it hits something.
summary
The current piece now moves, rotates, and drops. The full rows are cleared, and the next pieces are visible. I say the goal of finishing up the basic feature is met.
As always, the code’s up on github:
$ git fetch origin
$ git co day3v2 -b try/day3
$ sbt swing/run
day 4
In the last few days, we implemented tetrix from the ground up. In the beginning I mentioned that I use this game to explore new ways of thinking. Since I had already implemented tetrix once in Scala, Scala alone really isn’t anything new for me. The actual topic I wanted to think about using tetrix is the handling of concurrency.
concurrency
To quote Goetz’s Java Concurrency in Practice,
Writing thread-safe code is, at its core, about managing access to state, and in particular to shared, mutable state.
Conveniently we have refactored the inner working of tetrix so each operation is written as transition function from one GameState to another. Here’s a simplified version of 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
}
The timer modifies state by calling tick(state), and the player can also modify it by calling moveLeft(state) or moveRight(state). This is a textbook example of a thread-unsafe code. Here’s an unlucky run of the timer thread and swing’s event dispatch thread:
timer thread: reads shared state. current piece at (5, 18)
event thread: reads shared state. current piece at (5, 18)
timer thread: calls tick() function
timer thread: tick() returns a new state whose current piece is at (5, 17)
event thread: calls moveLeft() function
event thread: moveLeft() returns a new state whose current piece is at (4, 18)
event thread: writes the new state into shared state. current piece at (4, 18)
timer thread: writes the new state into shared state. current piece at (5, 17)
When the player sees this, either it would look like the left move was completely ignored, or witness the piece jumping diagnally from (4, 18) to (5, 17). This is a race condition.
synchronized
In this case, because each tasks are short-lived, and because the mutability is simple, we probably could get away with synchronizing on 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)
}
}
}
Using the synchronized clause, reading of state and writing of state is now guaranteed to happen atomically. This approach may not be practical if mutability is spread out more widely, or if background execution of tasks are required.
akka
Another way of managing concurrency is to use message passing framework like Akka actor. See Getting Started Tutorial (Scala): First Chapter for an intro to actors. We can follow the steps in the tutorial.
First, add "akka-actor" to 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
)
Next, create actors.scala and define message types.
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
Then create StageActor to handle the messages.
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
}
}
We can now rewire the abstract UI to use an Akka actor internally:
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)
}
The mutation is now wrapped inside playerActor, which is guaranteed to handle messages one at a time. Also, note that the timer is replaced with a schedule. Overall, the message passing allows us to reason about concurrent behavior in a resonable way.
game status
Let’s implement a small feature too. During the spawning process collision against existing blocks are not checked. If the new piece collides, it should end the game. Here’s the spec:
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
Let’s define GameStatus trait:
sealed trait GameStatus
case object ActiveStatus extends GameStatus
case object GameOver extends GameStatus
The test fails as expected after adding it to the 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)
Current implementation of spawn is loading nextPiece without checking for collision:
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)
}
All we have to do is validate the piece before loading it in.
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)
}
}
Next, reject state transition during GameOver status:
private[this] def transit(trans: Piece => Piece,
onFail: GameState => GameState = identity): GameState => GameState =
(s: GameState) => s.status match {
case ActiveStatus =>
// do transition
case _ => s
}
Let’s rub it into the player.
view.status match {
case GameOver =>
g setColor bluishSilver
g drawString ("game over",
12 * (blockSize + blockMargin), 7 * (blockSize + blockMargin))
case _ => // do nothing
}
As always, the code’s up on github:
$ git fetch origin
$ git co day4v2 -b try/day4
$ sbt swing/run
day 5
Yesterday we put in an Akka actor to manage concurrent access to the game state. Let’s look at the abstract UI again:
package com.eed3si9n.tetrix
class AbstractUI {
// skipping imports...
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)
}
too much locking
Looking back, the above implementation does not look good. I’ve turned the program into embarrassingly serial one. In the previous implementation using synchronized the swing UI was able to query for a view 10 times a second. It continues to do so with this implementation, but because it’s now in the same mailbox as other messages, it could flood the mailbox if any operation takes longer than 100 milisecond.
Ideally, the game state should not be locked until the very moment the new state is being written to it. Because the user operation and the scheduled ticking is never compatible, processing one of them at a time I think is ok for now.
Let’s design the second actor by defining the message types:
sealed trait StateMessage
case object GetState extends StateMessage
case case SetState(s: GameState) extends StateMessage
case object GetView extends StateMessage
The actor implementation should be straight forward:
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
}
}
Next we need to rewrite the StageActor based on 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)
}
}
We need to update the abstract UI slightly to create 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)
}
The concurrency of timer ticking and the player moving the current piece left continues to be protected using playerActor. However, now the swing UI can access the view frequently without waiting on the others.
size of the grid
After playing a few times, I noticed that the effective size of the grid is much smaller than 10x20 because how low the spawning point is. To work around this, we should expand the grid size vertically, but display only the lower 20 rows at least for the swing UI. I’ll keep the specs to be 10x20 so I don’t have to change all the numbers. newState should accept gridSize`:
def newState(blocks: Seq[Block], gridSize: (Int, Int),
kinds: Seq[PieceKind]): GameState = ...
Now, mostly the change is at swing UI. Pass in chopped off gridSize for rendering:
drawBoard(g, (0, 0), (10, 20), view.blocks, view.current)
drawBoard(g, (12 * (blockSize + blockMargin), 0),
view.miniGridSize, view.next, Nil)
Next, filter to only the blocks within the range:
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) }
}
Now the newly spawned piece creeps from the top edge of the grid.
As always, the code’s up on github:
$ git fetch origin
$ git co day5v2 -b try/day5
$ sbt swing/run
day 6
Yesterday we improved the concurrent access of the game state by introducing a second actor. Now that we have a powerful tool to manage concurrency, we can venture out to somewhere new. Like taking over the mankind. One tetrix player at a time.
Russell and Norvig
One of the reasons I picked CS major at my college was to learn about AI. It was quite disappointing that in the first few years none of my classes covered anything like AI. So during a summer co-op (internship) I decided to wake up early, go to Starbucks, and read a textbook smart colleges were using to teach AI. That’s how I found Russell and Norvig’s Artificial Intelligence: A Modern Approach (AIMA).
The book was shocking. Instead of trying to create a human-like robot, it introduces a concept called agent, which does something rational.
An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.
One of the structures of rational agent is a model-based, utility-based agent.
+-agent-------------------+ +-environment-+
| Sensors <===== |
| State <----+ | | |
| | | | |
| What if I do action A? | | |
| | | | |
| How happy will I be? | | |
| | | | |
| Utility <----+ | | |
| | | | |
| What should I do next? | | |
| | | | |
| Actuators =====> |
+-------------------------+ +-------------+
A utility function maps a state (or a sequence of states) onto a real number, which describes the associated degree of happiness.
Blows your mind, right? Using this structure, we can make a program that appears intelligent by constructing a state machine (done!), a utility function, and a tree searching algorithm. The data structure and graph theory can be useful after all.
utility function
For a utility-based agent, construction of the utility function is the key. We will probably be tweak this going forward, but let’s start with something simple. For now, I define that the happiness is not being dead, and the deleted lines. As passive as it sounds, tetrix is a game of not losing. On one-on-one tetrix, there isn’t a clear definition of winning. You win by default when the opponent loses.
Let’s describe this in a new spec:
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
}
Next we start Agent class and stub the utility method:
package com.eed3si9n.tetrix
class Agent {
def utility(state: GameState): Double = 0.0
}
This fails the second example as expected:
[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)
Let’s fix this:
def utility(state: GameState): Double =
if (state.status == GameOver) -1000.0
else 0.0
All green. Nothing to refactor here.
lines
Since my agent’s happiness is defined by the lines it has deleted, we need to track that number. This goes into 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)
Here’s GameState with 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)
}
The test fails as expected:
[info] Deleting a full row should
[error] x increment the line count.
[error] '0' is not equal to '1' (StageSpec.scala:91)
In Stage class, the only place full rows are deleted is in clearFullRow function called by tick:
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)
}
It kind of looks scary, but we just have to realize that the line deletion is done using s.copy(blocks = ...). We just need to add lineCount right afterwards:
s.copy(blocks = ...,
lineCount = s.lineCount + 1)
This passes the test.
[info] Deleting a full row should
[info] + increment the line count.
We now need to incorporate this into the utility function.
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
}
This again fails as expected:
[error] x evaluate an active state by lineCount
[error] '0.0' is not equal to '1.0' (AgentSpec.scala:9)
This is easy:
def utility(state: GameState): Double =
if (state.status == GameOver) -1000.0
else state.lineCount.toDouble
solving problems by searching
Now that our agent can find out how happy it is, it can turn an abtract issue of “not losing tetrix to a human” problem into tree searching problem. At any point in time, the agent and the scheduled timer can take one of the five actions we have been looking at:
def receive = {
case MoveLeft => updateState {moveLeft}
case MoveRight => updateState {moveRight}
case RotateCW => updateState {rotateCW}
case Tick => updateState {tick}
case Drop => updateState {drop}
}
In other words, bestMove is a GameState => StageMessage function. What’s with the tree? At the initial state s0 (at time=0), the agent can take five actions: MoveLeft, MoveRight etc. The actions result in five states s1, s2, s3, s4, s5 (at time=1). Each of the states then can branch into five more s11, s12, …, s55. Draw this out, and we have a tree structure.
s0
|
+--------------------+--------------------+-------...
s1 s2 s3
| | |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
s11 s12 s13 s14 s15 s21 s22 s23 s24 s25 s31 s32 s33 s34 s35
The number of the nodes grows exponentially. 1 + 5 + 5^2. For now, let’s just start with one level.
Here’s how we can contruct a test. Make a state named s3, which is one Drop action away from deleting a line. We tell the agent to pick a move, and it should select Drop. As a negative control, we also need some other state s1, which the agent can pick whatever action:
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
And here’s a stub:
def bestMove(state: GameState): StageMessage = MoveLeft
This fails the test as expected.
[info] Solver should
[info] + pick MoveLeft for s1
[info] x pick Drop for s3
[error] 'MoveLeft' is not equal to 'Drop' (AgentSpec.scala:32)
We’ll get back to this tomorrow.
$ git fetch origin
$ git co day6v2 -b try/day6
$ sbt swing/run
day 7
Yesterday we started on a new challange of building tetrix-solving AI. Russell and Norvig give insight into how a rational agent can be structured using a state machine , a utility function, and a tree searching algorithm. We have the first two, and a failing test:
[info] Solver should
[info] + pick MoveLeft for s1
[info] x pick Drop for s3
[error] 'MoveLeft' is not equal to 'Drop' (AgentSpec.scala:32)
First we need to lay out the things we know, which is the possible moves and corresponding state transition function:
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
}
To implement “What if I do action A?”, use possibleMoves, toTrans, and the given state s0 to emulate the next state. We can then use utility function to calculate the happiness and pick the move that maximizes the 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
}
The implementation looks imperative, but it’s fine as long as it’s within the method. We now have the first version of the solver. To prevent the agent from cheating, we need to create a GameMasterActor, which issues BestMove(s) message to the agent actor:
sealed trait AgentMessage
case class BestMove(s: GameState) extends AgentMessage
Here are the actor implementations:
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)
}
}
This surprisingly simple yet powerful. Since the whole point of calculating the best move is to make the move, the agent actor can send it out to a stageActor directly. Let’s hook these up:
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)
it’s alive!
Running the swing UI, the agent actually takes over the game and starts solving 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
...
And it’s so dumb!
Because the search tree is too shallow it never actually reach a point where utility actually kicks in. By default it’s picking MoveLeft. The first option is to deepen the search tree to more moves. We need eventually need that, but ultimately it’s not going to solve the entire problem. First, remember, the number of nodes grows exponentially. Second, we only know about two pieces for sure.
heuristic function
Plan B is to introduce a heuristic function.
h(n) = estimated cost of cheapest path from node n to a goal node.
Technically speaking we don’t have a goal node, so the term may not apply here, but the idea is to approximate the situation to nudge tree searching to a right direction. In our case, we can think of it as having some penalty for bad shapes. For example, let’s add penalty for having more than one height difference between the columns. We should square the gaps to make the penalty harsher.
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
}
The test fails as expected:
[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)
Let’s use the REPL to figure this one out. Type console from sbt.
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)))
This is not good. We have the current piece loaded in s.blocks. But the unload is currently a private method within Stage object. We can refactor it out to GameState class as follows:
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)
}
With minor changes to Stage object, all tests run expect for the current one. Now REPL again:
... the same thing as above ...
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
I did a lot more typos and experiments than above. But you get the idea. We can incrementally construct expression using the REPL by chaining one operation after another. When we get the answer, copy-past it into the editor:
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
}
The tests pass.
[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
There’s another problem with the current solver. Except for Drop the current piece is hovering midair, so it cannot be part of the evaluation. To solve this, we can simply append Drop unless it’s already dropped. I am going to change the implementation and see which test would fail:
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
}
Composing the transition function with Function.chain again. Now let’s run the test.
[info] Solver should
[info] + pick MoveLeft for s1
[error] x pick Drop for s3
[error] 'Tick' is not equal to 'Drop' (AgentSpec.scala:14)
This is not surprising. Since we added Drop at the end, there’s no difference between Tick and Drop anymore.
We can fix this by relaxing the spec:
def solver2 =
agent.bestMove(s3) must beOneOf(Drop, Tick)
Now the agent started to pick moves other than MoveLeft, but it’s preferring the left side of the grid a lot more.
Deepening the search tree should hopefully make things better. We’ll get back to this tomorrow.
$ git fetch origin
$ git co day7v2 -b try/day7
$ sbt swing/run
day 8
Yesterday we hooked up our tetrix-solving agent to an actor to take control of the game. Thus far the way it handled the game looked neither rational nor intelligent. After seeing many of the moves evaluated to 0.0 score including the heuristic penalties, I had two sneaking suspicions.
First, Drop was never a good choice. Especially given the shallow search tree, selecting Drop seemed premature. Since the gravitational tick is going to take care of the downard movement anyway, I decided to ignore it when the agent thinks the best move is Drop:
def receive = {
case BestMove(s: GameState) =>
val message = agent.bestMove(s)
if (message != Drop) stageActor ! message
}
buggy penalty
Second suspicion was that there was something wrong with the penalty calculation. Let’s add more test:
"""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
}
And it fails.
[error] x penalize having gaps between the columns
[error] '-4.0' is not equal to '-13.0' (AgentSpec.scala:35)
Before we go into the REPL, we can save some typing by adding the following to build.sbt:
initialCommands in console := """import com.eed3si9n.tetrix._
|import Stage._""".stripMargin,
After reloading, type in console from sbt shell and open the 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 // hit tab key
moveLeft moveRight
Yes, the tab key completion works in the 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 error! Did you catch this? The lowest coordinate is 0, yet I am returning 0 as the default.
Also I am throwing out the negative numbers. The correct gap should be:
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)
I didn’t catch this because my hand calculated value of -36.0 was also incorrect, which should have been -49.0. Now all tests pass:
[info] + penalize having gaps between the columns
It feels more logical now, but the penalty isn’t nudging the game to actual scoring or creating the right set up. First, I want to separate the reward component and penalty component of the utility function so it’s easier to test. Second, instead of the gaps, let’s try penalizing the heights in general.
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
}
Here’s the new 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
}
Another thing I want to tweak is the balance between the reward and penalty. Currently the incentive of deleting the line is too little compared to avoiding the penalty.
def utility(state: GameState): Double =
if (state.status == GameOver) minUtility
else reward(state) - penalty(state) / 10.0
This at least made the agent delete a line in the following game:
pruning the search tree
Pruning allows us to ignore portion of the search tree that make no difference to the final choice.
This concept applies here because without control the search tree grows exponentially.
- We can reduce the branching factor from five to tree by omitting
DropandTick. We already pretend that the current pieces gets dropped. All we have to do is to evaluates0withDrop. - Next, we can eliminate
RotateCWby pre-branching for all four orientations of the current piece. In most casesRotateCW :: MoveLeft :: RotateCW :: Drop :: NilandRotateCW :: RotateCW :: MoveLeft :: Drop :: Nilbrings us to the same state. - We can get rid of
MoveLeftby moving the current piece as left as it can upfront.
Potentially a piece can have four orientations and nine x-position. Thus, exponential tree search tree can now be approximated by a constant size 36.
First, we can list out the possible orientations based on the 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
}
Next, given a state calculate how many times can the agent hit left or right using the 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
Make the same one for right, and we have sideLimit method:
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))
}
These should be enough to build 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
}
Stub it out:
def actionSeqs(s0: GameState): Seq[Seq[StageMessage]] = Nil
The test fails as expected:
[info] ActionSeqs function should
[error] x list out potential action sequences
[error] '0' is not equal to '32' (AgentSpec.scala:15)
Here’s the implementation:
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
}
We can see the output using 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),...
Note one of the action sequences is List(), which evaluates the current state. All tests pass too:
[info] ActionSeqs function should
[info] + list out potential action sequences
We can now rewrite bestMove using actionSeqs:
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}
}
Now let’s add more spec. How about having a single gap open at (0, 8) such that it requires several rotations and a bunch of MoveRights? This is something our agent would have not solved before.
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
All green. Now let’s run the swing UI to see how it looks:
[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
It is rather short-sighted in its moves, but I am starting to see the glimpse of rationality. We’ll pick it up from here tomorrow.
$ git fetch origin
$ git co day8v2 -b try/day8
$ sbt swing/run
day 9
Yesterday we got the tetrix-solving agent to play a better game by fixing the heuristic function and evaluating 36 possible positions of the current piece.
stop watch
Let’s start by creating a function to measure the time it takes to run a segment of code:
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
}
This can be called as follows:
stopWatch("bestMove") {
// do something
} // stopWatch
This outputs as follows:
[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
There’s the initial wind down as JIT compiler kicks in, and it eventually settles around 10 ms. This gives us roughly what kind of time frame we are dealing with.
second level
If we expanded the search tree to the second piece, it should roughly increase 36x fold. 360 ms is not bad. Let’s try this:
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}
}
Now it is starting to play much better. The thinking time ranged from 12 ms to 727 ms, but mostly they were around 100 or 200 ms.
I am now comfortable enough to letting it drop the pieces again:
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
}
}
line number
Let’s display the number of deleted lines on the swing UI.
val unit = blockSize + blockMargin
g drawString ("lines: " + view.lineCount.toString, 12 * unit, 7 * unit)
Having this should help us track if our changes are improving the performance of the agent or not.
cavity
One thing I’ve been noticing as the agent plays the game is that it is happy to make cavities. A cavity is created when one or more block exists above an unfilled spot.
-fig 1----
xxxx
xxxx x xxx
x x xxxxxx
----------
Likely to avoid the height penalty, it would for example lay out the I bar flat on top of uneven surface instead of dropping it upright. To minimize the cavity, I’d like it to play:
-fig 2-----
x
x xxxx
x x xxx
x xxxxxxxx
----------
Let’s cauculate the height penalties from the first four columns.
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
As predicted, fig1 will incur lower penalty. We can create additional penalty for all blocks covering another block using its height * height. Then the new penalty becomes as follows:
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
This time, fig2 is preferred. Let’s write this in spec:
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)
}
The test fails as expected:
[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)
Let’s implement this using the 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)
Here’s the resulting 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)
}
This passes the test:
[info] Penalty function should
[info] + penalize having blocks stacked up high
[info] + penalize having blocks covering other blocks
Let’s see how it plays:
The cavity avoidance is working, but almost too well. Maybe we should reinstate the gap penalty tomorrow.
$ git fetch origin
$ git co day9v2 -b try/day9
$ sbt swing/run
day 10
Yesterday we expanded the search tree of the tetrix-solving agent into second piece. Although the quality of the game it is able to play has improved, there are some more room for tweaking.
scripting
As much as it is fun watching our not-so-intelligent agent play the game on its own, it’s a time-consuming and subjective process. The first thing we should do is to create a test harness that runs a preset game on a single thread with no UI. We will continuously let the agent suggest the best actions and execute them immediately.
We already have PieceKind.apply(x: Int), so let’s implement toInt on each PieceKind:
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 }
Now we can generate 1000 random numbers and print it on sbt shell:
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
}
Let’s run it:
library> run generate
[info] Running com.eed3si9n.tetrix.Scripter generate
41561156662214336116013264661323530534344000435311202344311644...
Copy-paste the output into script/0.txt. Run it four more times to create 1.txt, .., 4.txt. Next we want to script a game using the file.
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)
}
I had to modify Agent’s bestMove method to bestMoves, and let it return Seq[StageMessage].
We can now run from sbt shell:
library> run test
[info] Compiling 1 Scala source to /Users/eed3si9n/work/tetrix.scala/library/target/scala-2.10/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
In 61 seconds we ran five games all resulting 7 +/- 2 lines. No matter how many times we run them the results will be the same. I am now interested in how the grid looked when the agent lost these games.
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("")
}
Here’s one of the outputs:
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
----------
The entire 10th column is empty except for the bottom row. Let’s call these crevasses.
crevasse
Any gaps with one width really creates problems. For crevasses of depth 2, only J or L, or I can be used to rescue it. For crevasses of depth 3 and 4, I would work.
----------
x
x
x
x
xx
----------
The current penalty for the above figure is:
scala> val fig = math.sqrt(List(1, 5) map { x => x * x } sum)
fig: Double = 5.0990195135927845
Any crevasse deeper than 2 should be penalized using 4 height height:
scala> val fig = math.sqrt(List(1, 5, 10) map { x => x * x } sum)
fig: Double = 11.224972160321824
Spec this out:
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)
}
The test fails as expected:
[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)
To the 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)
Here’s the modified 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 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)
}
This passes the tests:
[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
Let’s run the scripter tests again. I am going to use more concise output:
lines: Vector(9, 11, 8, 17, 12)
It is now 11 +/- 6 lines, so that’s better than 7 +/- 2 lines.
A parameter I want to try is the balance of penalty and reward, which is 1:10 now:
def utility(state: GameState): Double =
if (state.status == GameOver) minUtility
else reward(state) - penalty(state) / 10.0
Since we have been putting more and more weights into the penalty, I wonder if the incentive to delete lines have been diminishing. Let’s make it 1:100 and see what happens.
lines: Vector(9, 11, 8, 17, 12)
The result is identical. I wouldn’t have guessed this without having the scripter.
How about the penalty of the crevasses? Is 4 height height too harsh? Let’s try height * height instead.
lines: Vector(6, 8, 8, 14, 12)
This is 8 +/- 6 lines. Overall degradation compared to 11 +/- 6 lines of 4 height height. Let’s define the square root of the constant to be 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 and 4 came out to be the same, so likely there’s no point in increasing beyond 3.
other parameters
This got me thinking what if I change the balance between other penalties like height?
val heightWeight = 2
val weightedHeights = heights.values map {heightWeight * _}
Here are the results:
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
This is 20 +/- 23 lines and 26 +/- 13! With h4 both the min and the max performer has degraded, but the median has increased. I like h3 because it has the largest minimum.
The only parameter we haven’t tested now is coverupsWeight. We’ll denote this as v1, v2, etc:
h3:c3:v1 = lines: Vector(20, 20, 20, 18, 43) // 20 +/- 23
h3:c3:v2 = lines: Vector(11, 13, 12, 14, 17) // 13 +/- 4
This is 13 +/- 4 lines, so clearly not a good idea. How about we eliminate it from penalty altogether?
h3:c3:v0 = lines: Vector(35, 34, 22, 27, 33) // 33 +/- 11
The data does not lie. 33 +/- 11 lines. The cavitiy analysis was useless. Here are the results from tweaking the balance of heightWeight and 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
If we choose using median, h11:c10:v0 is the winner. Here’s the modified 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)
}
The good old swing UI still works, and it plays nicely:
We’ll continue from here tomorrow. As always, the code is up on github.
$ git fetch origin
$ git co day10v2 -b try/day10
$ sbt library/run
$ sbt swing/run
day 11
Yesterday we’ve written a test harness to automate scripted games to tune various components of the heuristic function. The overall performance improved from 7 +/- 2 lines to 34 +/- 18, almost 5x improvement.
HAL moment
I decided to watch a game through on the swing UI, since I had been script testing mostly. From the beginning I could feel the improvement of the game quality as it was able to manage the blocks lows, and kept deleting the lines. After it went past 60 lines, it made a few mistakes and the blocks started to stack up to maybe 10th row, but nothing unmanagable. Then, all of a sudden, the agent started droping the piece. One after another.
It was as if the agent suddently gave up the game. Later during the day I realized that likely it had reached a timeout in one of the actors.
variable thinking cycle
Instead of telling the agent to think at a regular interval, let’s let it think as long as it wants to. To be fair to human response time, let’s throttle an action to around 3 per second.
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)
}
}
In order to slow down the game a bit, let’s substitute Drop for a Tick also:
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
}
}
To prevent the agent from taking too long time to think, let’s cap it to 1000 ms.
val maxThinkTime = 1000
val t0 = System.currentTimeMillis
...
nodes foreach { node =>
if (System.currentTimeMillis - t0 < maxThinkTime)
actionSeqs(node.state) foreach { seq =>
...
}
else ()
}
man vs machine
Now that the agent is tuned, the next logical step is to play against the human. Let’s set up two stage actors with identical initial state. One controlled by the player, and the other controlled by the agent.
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 }
Currently view returns only one view. We should modify this to return a pair.
def views: (GameView, GameView) =
(Await.result((stateActor1 ? GetView).mapTo[GameView], timeout.duration),
Await.result((stateActor2 ? GetView).mapTo[GameView], timeout.duration))
Next, the swing UI need to render both the views.
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)
}
Since drawBoard was refactored out, this was simple.
We can let GameMasterActor be the referee and determine the winner if the other loses.
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)
}
}
We need to display the status on the UI:
case Victory =>
g drawString ("you win!", offset._1, offset._2 + 8 * unit)
And this is how it looks:
attacks
Currently two players are just playing side by side. Let’s introduce attacks. Whenever a player deletes two or more lines in an action, some of the blocks should show up at the bottom of the opponent’s grid on the next spawn cycle.
Let’s spec the stage first:
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)
)
Stub it out:
val notifyAttack: GameState => GameState = (s0: GameState) => s0
The test fails as expected:
[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)
Here’s the first part:
val notifyAttack: GameState => GameState = (s0: GameState) =>
s0.copy(pendingAttacks = s0.pendingAttacks + 1)
The second attack function looks similar to 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)
}
This is added to ticking process as follows:
val tick = transit(_.moveBy(0.0, -1.0),
Function.chain(clearFullRow :: attack :: spawn :: Nil) )
All tests pass:
[info] Attacks should
[info] + increment the pending attack count,
[info] + and change the blocks in the view on spawn.
Next, we’ll use StageActors to notify each other’s attacks. We can let the stage report the number of lines deleted in the last tick as 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) {...}
Add a new message type Attack and implement notificaton in 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
}
}
}
This creates attacks when 2 or more lines are deleted. Here’s an example:
The I bar is going to eliminate bottom 4 rows, creating 3 attacks.
We’ll pick it up from here tomorrow.
$ git fetch origin
$ git co day11v2 -b try/day11
$ sbt swing/run
day 12
Yesterday we created two stage actors so the agent can play against the player. To make things more interesting, attacking was implemented which sends junk blocks to the opponent.
unfair advantage
Thus far, the agent has been tuned to delete as many lines as it can. But yesterday we introduced attacking, which only kicks in after deleting two or more rows. This gives human side, who are aware of this change, an unfair advantage. Let’s see what we can do.
Let’s track line counts by the lines deleted in an action:
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
...
}
Here’s modified 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))
}
Now modify the scripting test a bit to print out the attack count:
println(file.getName + ": " +
s.lineCount.toString + " lines; " +
s.attackCount.toString + " attacks")
(s.lineCount, s.attackCount)
Here are the results:
lines : Vector(34, 34, 32, 52, 29)
attacks: Vector(4, 3, 3, 3, 1)
I can see how crevasse penalty can work against attacking, so let’s increase the height penalty ratio from current 11:10 to 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
The median actually dropped to 1. To apply the pressure to keep blocks as a chunk, we should bring back the cavity analysis:
h11:c10:v1 = lines : Vector(27, 30, 24, 31, 34) // 30 +/- 4
h11:c10:v1 = attacks: Vector(0, 3, 2, 3, 1) // 3 +/- 3
Maybe the problem with the cavity analysis is the the penalty calculation was too harsh in comparison with the others. Instead of piling up penalties for each block covering a cavity, why not just use height * height like crevasse:
val coverupWeight = 1
val coverups = groupedByX flatMap { case (k, vs) =>
if (vs.size < heights(k)) Some(coverupWeight * heights(k))
else None
}
We’ll denote this as w1, w2 for the amount of coverupWeight.
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
Another possibility may be to further weaken the penalty by using a constant instead of height, which we will use 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
In terms of the attacks per lines h11:c10:k1 is looking good, so we’ll use this for now.
Android
It would be cool if we can show this game off on a cellphone, so let’s port this to Android. First install Android SDK or update to the latest SDK if you can’t remember the last time you updated it by launching android tool from command line:
$ android
As of September 2013, the latest SDK is Android 4.3 (API 18), but I’m going to also download Android 4.1.2 (API 16) that’s the oldest Jelly Bean. Next, create an Android Virtual Device (AVD) using API 16.
pfn/android-plugin
Next we need pfn/android-sdk-plugin for sbt.
Create project/android.sbt and add the following:
addSbtPlugin("com.hanhuy.sbt" % "android-sdk-plugin" % "1.0.6")
Make the following changes to 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)
After reloading sbt and navigating to droid project, devices, device, and android:run tasks are going to be available.
hello world
An Android apps consists mainly of activities, views, and threads. For tetrix, we just need to get a handle to the Canvas object to draw things, so activities and views become fairly simple. I will stuff most of the logic in a thread, which I am not sure is the right approach.
First, create android/src/main/AndroidManifest.xml. This forces landscape orientation:
<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>
Here’s the activity class:
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)
}
}
The layout file is android/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>
This points to 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)
})
}
}
Finally, in order to manage my own repaint, I am going to run a thread in an infinite loop:
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)
}
}
}
The above would print out “hello world” at 10 frames per second. The rest is just the matter of hooking things up.
UI for Android
Android has its own library for widgets and graphics. They are all well-documented, and not that much different from any other UI platforms. I was able to port drawBoard etc from swing with only a few modification.
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 is a loan pattern that ensures that the canvas gets unlocked. The only thing is that there’s no keyboard on newer phones. Here’s how we can translate gesture angles into actions:
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
}
}
loading on device
To load it on the emulator, select the device and 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...
It did showed up on the emulator.
To really get the feeling on how it works, let’s load on a phone. Here’s tetrix running on my htc one:
The agent is playing, but it keeps picking really bad moves.
We’ll pick it up from here tomorrow.
$ git fetch origin
$ git co day12v2 -b try/day12
$ sbt swing/run
day 13
Yesterday we created Android app and loaded it on the phone. But for some reason, the agent kept picking bad moves.
println debugging
To find out what’s going on, uncomment some of the println statements in the library.
Then run adb -e shell from $ANDROID_HOME/platform-tools/ to start an adb shell session in the emulator. See Android Debug Bridge for more details. Then from the adb shell:
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
This will stream println calls within the app to the screen.
It’s taking 10 seconds to calculate the best move, which is significantly longer than the pace at which the request is coming in. The best move information could be quite stale if it’s using old state, and that’s likely a horrible move recommendation for the current state. The work around would be to block on the best move loop within 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
}
}
If we use ./adb -d shell, we can start an adb shell session in the connected phone.
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
Much better calculation, but it still takes quite a long time on the phone.
think once, move twice
Thus far the agent has been calculating a sequence of actions, and then threw everything out but the first move, to calculate the best move. In the next thinking cycle it does the same thing again, which seemed ok on a normal machine. In the phone environment the calculation is taking 10x more time. So the waste is costly in terms of game performance, since the human player and the gravity will keep moving.
We can modify the agent actor to calculate the best sequence of moves, and actually execute them instead.
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 ! ()
}
}
This worked. Now the agent can sustain the game for a while.
config
Next I refactored configuration values that are driving this logic.
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 ! ()
}
}
This way I can tweak the game blance depending on the platform. With the following setting, swing UI is quick:
val config = Config(minActionTime = 151,
maxThinkTime = 1500,
onDrop = Some(Tick))
val ui = new AbstractUI(config)
For Android I’m using different settings to compensate for the slower CPU:
val config = Config(
minActionTime = 51,
maxThinkTime = 1000,
onDrop = None)
ui = Some(new AbstractUI(config))
survival of the fittest
We’ve tuned the penalty parameters yesterday to increase attack counts, but it still feels conservative.
h11:c10:k1 = lines : Vector(34, 34, 32, 38, 29) // 34 +/- 5
h11:c10:k1 = attacks: Vector(4, 3, 3, 5, 1) // 3 +/- 2
I wonder if rid of the reward for deleting a single line would improve this.
def reward(s: GameState): Double =
if (s.lastDeleted < 2) 0
else s.lastDeleted
Here are the results:
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
The minimum value of the line count decreased to 24, and the minimum value of the attack count didn’t change. Because it’s not constantly clearing out single lines, it probably became less stable player.
cavity again
To bring in the structure, we try making the cavity stronger again.
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
Interestingly, the median of the attack count went down to 1, but the max of line count increased to 51. Here’s the result from 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
----------
crevasse depth
Next, I decided to penalize crevasses only if it’s deeper than 3 to increase the opportunity of attacks.
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
This has stablized the game a bit. The Android version is playable, but swing version with this aggressive tuneup is getting furious.
The agent has more line count racked up.
thanks!
Anyway, this is going to be the end of our tetrix in Scala series. Thanks for the comments and retweets. I’d like to hear what you think. Also, if you are up for the challenge, send me a pull request of a smarter agent-actor that can beat human!