Ett steg på vägen

Nu har jag uppnått ett första delmål nämligen att få programmet att spela Tetris och uppföra sig på samma sätt som C++ versionen, dock än så länge utan grafiskt gränssnitt. När jag testar köra C++ versionen på min nya bärbara dator med Intel i7-processor lägger den 23.000 bitar per sekund medan Scala-versionen endast gör 2.000 bitar per sekund, alltså mindre än 10% av C++ versionens hastighet. Den ursprungliga Java-versionen (som skrevs före C++ versionen, alltså ej den halvfärdiga Java-version som finns med i detta projekt) kom upp till 20% av C++ versionen. Scala-versionen är dessutom endast hälften så snabb som Java-versionen trots att den kör på en tio år nyare 64-bitars JVM! Detta är lite av en besvikelse, men jag utgår ifrån att det finns utrymme för optimering.

Under Pieces/sec ser man att C++ versionen kör med en hastighet av 23.803 bitar per sekund (varierar lite under körning). Jag beklagar att jag inte kan släppa en körbar version då den innehåller en grafisk komponent som inte får distribueras fritt:

För att hantera att datorn kan spela själv har jag skapat klassen Game. Då jag ville säkerställa att Scala-versionen uppför sig exakt som C++ versionen skrev jag ett test som verifierar detta, GameTest:

package net.sf.tetrisai.game

import org.junit.Test
import net.sf.tetrisai.settings.DefaultGameSettings
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.boardevaluator.JoakimTengstrandBoardEvaluator
import net.sf.tetrisai.BaseTest
import net.sf.tetrisai.piece._
import collection.mutable.Buffer
import net.sf.tetrisai.piecegenerator.PredictablePieceGenerator

class GameTest extends BaseTest {

  @Test def playFivePieces() {
    val board = Board(10,15)
    val boardEvaluator = new JoakimTengstrandBoardEvaluator(board.width, board.height)
    val pieceGenerator = new PredictablePieceGenerator(List(new PieceO, new PieceL, new PieceI, new PieceZ, new PieceT))
    val settings = new DefaultGameSettings
    val game = new Game(board, boardEvaluator, pieceGenerator, settings)
    game.play(5)

    game.linesCleared should be (1)

    board should be (Board(Buffer(
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#----------#",
      "#---------Z#",
      "#--------ZZ#",
      "#OO---TTTZL#",
      "############")))
  }
}

Den spelar fem bitar, för varje bit använder den sig av samma algoritm som i C++ för att hitta bästa alternativ att placera biten (jag kommer gå igenom algoritmen i detalj vid nästa blogginlägg). Därefter testas att korrekt antal rader rensats och att slutpositionen är den förväntade. Implementation av Game:

package net.sf.tetrisai.game

import net.sf.tetrisai.settings.GameSettings
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.boardevaluator.BoardEvaluator
import net.sf.tetrisai.piecegenerator.PieceGenerator
import net.sf.tetrisai.move.EvaluatedMoves

class Game(board: Board, boardEvaluator: BoardEvaluator, pieceGenerator: PieceGenerator, settings: GameSettings) {
  var position = new Position(board, pieceGenerator.nextPiece, settings)
  var linesCleared = 0

  def play(maxMoves: Long) {
    var moves: Long = 0
    var evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)

    while (moves < maxMoves && !evaluatedMoves.isEmpty) {
      val bestMove = evaluatedMoves reduceLeft { _ min _ }
      position.movePiece(bestMove)
      linesCleared += position.setPiece().linesCleared
      moves += 1
      position = new Position(board, pieceGenerator.nextPiece, settings)
      evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)
    }
  }
}

Det jag tror och hoppas är att jag hittat en tydlig uppdelning av ansvar för de klasser som är inblandade i att spela Tetris. Här följer en beskrivning av de klasser som används av Game, med respektive test angivet först:

För att hitta rätt värderingar av de olika alternativen att lägga en bit, behöver jag jämföra med C++ versionen:

EvaluatedMovesTest:

package net.sf.tetrisai.move

import org.junit.Test
import net.sf.tetrisai.BaseTest
import net.sf.tetrisai.boardevaluator.JoakimTengstrandBoardEvaluator
import net.sf.tetrisai.settings.DefaultGameSettings
import net.sf.tetrisai.game.Position
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.piece.{PieceS}

class EvaluatedMovesTest extends BaseTest {

  @Test def evaluatedMoves {
    val board = Board()
    val position = new Position(board, new PieceS, new DefaultGameSettings)
    val boardEvaluator = new JoakimTengstrandBoardEvaluator(board.width, board.height)
    val evaluatedMoves = new EvaluatedMoves(position, board, boardEvaluator)

    val moves = for {
      move <- evaluatedMoves.moves.sortBy{m => (m.equity)}
    } yield roundThreeDecimals(move)

    moves should be (List(
      new MoveEquity(0,7, 18, 0.000),
      new MoveEquity(1,0, 17, 0.660),
      new MoveEquity(0,0, 18, 2.291),
      new MoveEquity(0,5, 18, 3.040),
      new MoveEquity(1,8, 17, 3.437),
      new MoveEquity(0,2, 18, 3.468),
      new MoveEquity(0,3, 18, 3.546),
      new MoveEquity(0,1, 18, 3.854),
      new MoveEquity(0,4, 18, 3.955),
      new MoveEquity(0,6, 18, 4.727),
      new MoveEquity(1,2, 17, 6.931),
      new MoveEquity(1,6, 17, 7.017),
      new MoveEquity(1,4, 17, 7.144),
      new MoveEquity(1,5, 17, 7.902),
      new MoveEquity(1,7, 17, 8.127),
      new MoveEquity(1,3, 17, 8.925),
      new MoveEquity(1,1, 17, 10.717)))
  }

  private def roundThreeDecimals(move: MoveEquity) = {
    val equity = scala.math.round((move.equity - 12.43) * 1000) / 1000.0
    new MoveEquity(move.rotation, move.x, move.y, equity)
  }
}

EvaluatedMoves:

package net.sf.tetrisai.move

import net.sf.tetrisai.boardevaluator.BoardEvaluator
import net.sf.tetrisai.board.Board
import net.sf.tetrisai.game.Position

class EvaluatedMoves(position: Position, board: Board, boardEvaluator: BoardEvaluator) extends Traversable[MoveEquity] {
  val moves: List[MoveEquity] = evaluateValidMoves

  def foreach[U](f: MoveEquity => U) = {
    val iterator = moves.iterator
    while (iterator.hasNext) f(iterator.next)
  }

  /**
   * Evaluates the equity of all valid moves for a given position.
   */
  private def evaluateValidMoves: List[MoveEquity] = {
    for {
      move <- position.validMoves
    } yield new MoveEquity(move.rotation,move.x, move.y, evaluate(move))
  }

  private def evaluate(move: Move) = {
    position.movePiece(move)
    val clearedLines = position.setPiece
    val equity = boardEvaluator.evaluate(board)
    position.undoSetPiece(clearedLines)

    equity
  }
}

En bra egenskap med denna klass är att den helt döljer den interna listan moves och i stället erbjuder användaren av klassen möjlighet att stega elementen i listan genom att mixa in traitet Traversable och implementera metoden foreach. Klassen Game får då bl.a automatiskt tillgång till metoderna isEmpty (rad 17) och reduceLeft (rad 18) i Game.

Metoderna setPiece och undoSetPiece (tidigare clearPiece) har fått hantering av vilka rader som tagits bort. Detta för att kunna återställa positionen när man går igenom alla möjliga alternativ att lägga en bit, PositionTest:

...
  @Test def setPieceAndClearLine {
    val board = Board(Buffer(
      "#-----#",
      "#-----#",
      "#----x#",
      "#x-xxx#",
      "#######"))
    val piece: Piece = new PieceT
    val position = new Position(board, piece, settings)
    position.movePiece(Move(0,0,2))
    val clearedLines = position.setPiece()

    clearedLines.linesCleared should be (1)

    board should be (Board(Buffer(
      "#-----#",
      "#-----#",
      "#-----#",
      "#TTT-x#",
      "#######")))
  }

  @Test def undoSetPieceRestoreClearedLine {
    val board = Board(Buffer(
      "#-----#",
      "#-----#",
      "#-----#",
      "#TTT-O#",
      "#######"))
    val piece: Piece = new PieceT
    val position = new Position(board, piece, settings)
    position.movePiece(Move(0,0,2))
    val clearedLines = new ClearedLines(List(new ClearedLine(3, BoardLine("#LTSSZ#"))))
    position.undoSetPiece(clearedLines)

    board should be (Board(Buffer(
      "#-----#",
      "#-----#",
      "#----O#",
      "#L-SSZ#",
      "#######")))
  }

Position:

package net.sf.tetrisai.game

import net.sf.tetrisai.board.Board
import net.sf.tetrisai.settings.GameSettings
import net.sf.tetrisai.piece.Piece
import net.sf.tetrisai.move.{ValidMoves, Move}

/**
 * Responsible for moving and rotating current piece plus
 * setting and clearing that piece on the board.
 */
class Position(board: Board, val piece: Piece, settings: GameSettings) {
  val boardWidth = board.width
  val boardHeight = board.height
  var pieceMove = settings.pieceStartMove(board.width, piece)
  private val rotationDirection = settings.rotationDirection

  def setPiece(): ClearedLines = {
    piece.shape(pieceMove.rotation).dots.foreach(dot => board.set(dot + pieceMove, piece.number))
    board.clearLines(pieceMove.y, piece.height(pieceMove.rotation))
  }
  def undoSetPiece(clearedLines: ClearedLines) = {
    board.undoClearedLines(clearedLines)
    piece.shape(pieceMove.rotation).dots.foreach(dot => board.clear(dot + pieceMove))
  }
  def rotatePiece() = pieceMove = pieceMove.rotate(rotationDirection, piece.rotationModulus)
  def movePiece(move: Move) = pieceMove = move
  def validMoves = new ValidMoves(this).moves
  def isValidMove: Boolean = isValidMove(pieceMove)
  def isValidMove(move: Move): Boolean = {
    try {
      (piece.shape(move.rotation).dots.foldLeft(0) { (sum,dot) => sum + board.get(dot + move) }) == 0
    } catch {
      case e: IndexOutOfBoundsException => false
    }
  }
}

Metoden clearLines i Board har jag skrivit om tidigare och kommer därför bara att nämna en detalj kring hanteringen att lägga till rader till ClearedLines, Board:

package net.sf.tetrisai.board

import net.sf.tetrisai.Point
import scala.collection.mutable.Buffer
import net.sf.tetrisai.game.{ClearedLine, ClearedLines}

object Board {
  def apply(width: Int = 10, height: Int = 20) = {
    val boardLines = Buffer.fill(height) { BoardLine.emptyLine(width) }
    new Board(width, height, boardLines)
  }

  def apply(lines: Buffer[String]) = {
    val width = lines(0).length - 2
    val height = lines.length - 1

    require(lines(height) == bottomTextLine(width))

    val boardLines = Buffer.tabulate(height) (
      ((y) => (BoardLine(lines(y))))
    )
    new Board(width, height, boardLines)
  }

  def bottomTextLine(width: Int) = "#" * (width + 2)
}

/**
 * Represents the game board.
 * Standard size is 10x20 (width x height).
 */
class Board(
    val width: Int,
    val height: Int,
    private val lines: Buffer[BoardLine]) {
  require(height >= 4)

  def get(dot: Point) = lines(dot.y).get(dot.x)
  def set(dot: Point, number: Byte) = lines(dot.y).set(dot.x, number)
  def clear(dot: Point) = lines(dot.y).clear(dot.x)
  def emptyLine = BoardLine.emptyLine(width)
  def completedLine = BoardLine.completedLine(width)
  def bottomTextLine = Board.bottomTextLine(width)
  def countDots = lines.foldLeft(0) { (sum,line) => sum + line.countDots }

  def isFree(x: Int, y: Int) = {
    try {
      lines(y).get(x) == 0
    } catch {
      case e: IndexOutOfBoundsException => false
    }
  }

  def undoClearedLines(clearedLines: ClearedLines): Board = {
    clearedLines.lines.reverse.foreach(insertLine(_))
    this
  }

  private def insertLine(clearedLine: ClearedLine) {
    lines.remove(0)
    lines.insert(clearedLine.y, clearedLine.boardLine)
  }

  /**
   * Clears completed lines and returns which lines that was cleared.
   * This method should be called after a piece has been dropped on the board.
   *   pieceY: the y position of the piece.
   *   pieceHeight: height of the piece.
   */
  def clearLines(pieceY: Int, pieceHeight: Int): ClearedLines = {
    var clearedLines = ClearedLines()
    var y1 = pieceY + pieceHeight;

    // Find first line to clear
    do {
      y1 -= 1
      if (lines(y1).isComplete)
        clearedLines += (y1, lines(y1).copy)
    } while (clearedLines.linesCleared == 0 && y1 > pieceY)

    // Clear lines
    if (clearedLines.linesCleared > 0) {
      var y2 = y1;

      while (y1 >= 0) {
        y2 -= 1
        while (y2 >= pieceY && lines(y2).isComplete) {
          clearedLines += (y2, lines(y2).copy)
          y2 -= 1
        }
        if (y2 >= 0)
          lines(y1) = lines(y2)
        else
          lines(y1) = emptyLine

        y1 -= 1;
      }
    }
    clearedLines;
  }

  override def equals(that: Any) = that match {
    case other: Board => lines.toList == other.lines.toList
    case _ => false
  }

  override def toString = lines.map { _.toString }.mkString("\n") + "\n" + bottomTextLine
}

Rad 78 och 88 lägger till en rad till listan clearedLines. Det finns två fiffiga saker med hur detta är gjort. Det första är att jag använt mig av något som heter Tuples. Det är en konstruktion i Scala där man kan paketera ihop två eller fler värden genom att omringa dem med en parantes. Det andra är att jag implementerat operatorn + (plus) i ClearedLines genom att just ta en Tupel som inargument:

package net.sf.tetrisai.game

import net.sf.tetrisai.board.BoardLine

object ClearedLines {
  def apply() = new ClearedLines(List[ClearedLine]())
}

case class ClearedLine(val y: Int, val boardLine: BoardLine)

class ClearedLines(val lines: List[ClearedLine]) {
  def +(y: Int, boardLine: BoardLine) = new ClearedLines(new ClearedLine(y, boardLine) :: lines)

  val linesCleared = lines.size

  override def equals(that: Any) = that match {
    case other: ClearedLines => lines == other.lines
    case _ => false
  }

  override def toString = lines.toString
}

Klassen innehåller en inner case klass ClearedLine. Att jag valt att göra den som en case klass beror på att jag vill dra nytta av att case klasser automatiskt genererar bl.a metoden equals som jag behöver då jag jämför instanser av ClearedLine med varandra.

Det finns en sak till som kan vara värt att nämna. Scala (och Java) har ingen hantering av unsignade heltal. Slumptalsgeneratorn i C++ versionen använder sig just av detta, Random.h:

#ifndef __random__
#define __random__

class Random
{
 private:
  unsigned int seed;

 public:
  Random();
  Random(unsigned int seed);
  ~Random();
  void setSeed(int seed) { this->seed = seed; }
  unsigned int getRandom();
  int getRandomP();
};

#endif

Random.cpp:

#include "Random.h"

Random::Random()
{
 this->seed = 0;
}

Random::Random(unsigned int seed)
{
 this->seed = seed;
}

Random::~Random()
{
}

unsigned int Random::getRandom()
{
 seed *= (unsigned int)(1664525);
 seed += (unsigned int)(1013904223);

 return seed;
}

int Random::getRandomP()
{
 unsigned int seed = getRandom();

 return seed % 7 + 1;
}

För att emulera detta beteende har jag i Scala behövt utföra operationerna med datatypen Long och sedan maska av de 32 minst signifikanta bitarna:

package net.sf.tetrisai.piecegenerator

object DefaultPieceGenerator {
  val BitMask = 0x00000000FFFFFFFFL
}

class DefaultPieceGenerator(var seed: Long = 0) extends PieceGenerator {

  def nextPieceNumber = {
    seed = (seed * 1664525) & DefaultPieceGenerator.BitMask
    seed = (seed + 1013904223) & DefaultPieceGenerator.BitMask

    modulus7 + 1
  }

  private def modulus7 = {
    val div: Long = seed / 7;
    (seed - div * 7).toInt
  }
}

Scala (och Java) kan inte utföra modulus (%) operatorn på datatypen Long, utan vill ha en Integer. Jag skulle ha velat skriva (seed.toInt % 7) + 1 på rad 13 men detta ger inte samma resultat som metoden modulus7.

Det var allt denna gång!