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