Summa sidvisningar

fredag 2 december 2011

Implicita konverteringar

Tänkte fortsätta på den inslagna vägen att förstå kod genom att titta på den dekompilerade Scala-koden, i det här fallet för att förstå implicit conversions lite bättre. Låt oss ta en titt på följande lilla program:

Exempel 6 - implicit conversions

package nu.tengstrand.scalalab.programminginscala

/**
 * Example of implicit conversion and rich wrappers.
 * Page 94, 212 in the book "Programming in Scala, 2nd edition".
 */
object Example006ImplicitConversion {

  def main(args: Array[String]) {
    println(1 to 3)
    println(4.to(6))
    println(Predef.intWrapper(7).to(9))
   }
}
Kör man programmet får man följande output:
Range(1, 2, 3)
Range(4, 5, 6)
Range(7, 8, 9)
Vi kan konstatera att raderna 10-12 gör samma sak och att de skiljer sig lite på grund av att vi skickat in lite olika argument. Rad 10 utnyttjar att man i Scala kan utelämna punkt och parenteser vid metodanrop. Rad 12 är vad anropen på de andra två raderna översätts till när koden kompileras efter att den applicerat en implicit konvertering.

Läser man raderna 10-12 uppifrån och ned är det ganska uppenbart att läsbarheten minskar för varje rad! Vi får tacka Martin Odersky (skaparen av språket) att vi kan skriva 1 to 3 i stället något annat som skulle kluttra ned koden i onödan!

Låt oss nu ta en titt på den kompilerade koden. Kompilatorn producerar klasserna Example006ImplicitConversion.class och Example006ImplicitConversion$.class, den senare ser ut så här:
// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Example006ImplicitConversion.scala

package nu.tengstrand.scalalab.programminginscala;

import scala.Predef$;
import scala.ScalaObject;
import scala.collection.immutable.Range;
import scala.runtime.RichInt;

public final class Example006ImplicitConversion$ implements ScalaObject {

 public void main(String args[]) {
  Predef$.MODULE$.println(Predef$.MODULE$.intWrapper(1).to(3));
  Predef$.MODULE$.println(Predef$.MODULE$.intWrapper(4).to(6));
  Predef$.MODULE$.println(Predef$.MODULE$.intWrapper(7).to(9));
 }

 private Example006ImplicitConversion$() {
 }

 public static final Example006ImplicitConversion$ MODULE$ = this;

 static {
  new Example006ImplicitConversion$();
 }
}

Hur hänger då detta ihop. Allt som ligger i klassen scala.Predef inkluderas när man kompilerar (på liknande sätt som java.lang.* inkluderas i Java). Klassen Predef ärver från LowPriorityImplicits som i sin tur har följande implicit deklarerad:
implicit def intWrapper(x: Int) = new runtime.RichInt(x)
När kompilatorn upptäcker att datatypen Int saknar metoden to börjar den leta efter implicita konverteringar och hittar då intWrapper som den använder för att wrappa våran Int och får då tillgång till dennes to-metod.

Det var ju inte så svårt det här!

tisdag 22 november 2011

Funktioner

I detta inlägg tänkte jag börja titta lite på hur funktioner kan användas i Scala. En trevlig sak med Scala är att det både är objektorienterat och funktionellt. I Scala och andra funktionella språk kan man skicka med en funktion som argument till en metod. Funktionen kan antingen definieras och instansieras direkt vid själva anropet (benämns function value i boken) eller först tilldelas en variabel (function literal). Låt oss testa detta, koden finns även här:

Exempel 5 - function literals

package nu.tengstrand.scalalab.programminginscala

/**
 * Example of function literals.
 * Page 148 in the book "Programming in Scala, 2nd edition".
 */
object Example005FunctionLiterals {

  def main(args: Array[String]) {
    val integers = List(1,2,3,4,5)
    val odds = integers.filter(_ % 2 == 1)
    val evenFilter = (_:Int) % 2 == 0
    println(odds) // output: List(1, 3, 5)
    println(integers.filter(evenFilter))  // output: List(2, 4)
  }
}

På rad 11 skickar vi in en funktion som argument till metoden filter som returnerar en ny lista innehållandes de ojäma värdena. På rad 12 väljer vi att först tilldela funktionen till en variabel som sedan används på rad 14 för att filtrera listan. I första fallet förstår kompilatorn att typen är Int då listan består av Int:ar medan vi i andra fallet explicit måste ange att typen är Int.

Om vi kompilerar koden ser vi att den producerar fyra klasser:
  1. Example005FunctionLiterals.class
  2. Example005FunctionLiterals$.class
  3. Example005FunctionLiterals$$anonfun$1.class
  4. Example005FunctionLiterals$$anonfun$2.class
I exemplet har vi bara ett objekt (nyckelordet object) med namnet Example005FunctionLiterals, dock ingen klass (nyckelordet class). Konventionen i Scala är att klassfilen får samma namn som klassen medan objektfilen får klassnamnet plus ett avslutande dollartecken, i det här fallet Example005FunctionLiterals$.class.

När jag tittar på källkoden kan jag konstatera att all nödvändig kod hamnat i objektfilen. Koden i klassfilen verkar inte innehålla något vettigt! Koden i de två anonyma funktionerna anonfun$1 och anonfun$2 finns även representerad i objektklassen och verkar även de vara överflödiga. De skapas möjligen för att kunna accessas utifrån. Jag blev lite konfunderad av detta beteende och skrev därför ihop ett liknande program i Java och kunde då konstatera att Java-kompilatorn uppförde sig på samma sätt.

Låt oss decompilera objektklassen till Java:
// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Example005FunctionLiterals.scala

package nu.tengstrand.scalalab.programminginscala;

import scala.*;
import scala.collection.TraversableLike;
import scala.collection.immutable.List;
import scala.collection.immutable.List$;
import scala.runtime.BoxesRunTime;

public final class Example005FunctionLiterals$ implements ScalaObject {

    public void main(String args[]) {
        List integers = List$.MODULE$.apply(Predef$.MODULE$.wrapIntArray(new int[] {
            1, 2, 3, 4, 5
        }));
        List odds = (List)integers.filter(new Serializable() {

            public final boolean apply(int i) {
                return apply$mcZI$sp(i);
            }

            public boolean apply$mcZI$sp(int v1) {
                return v1 % 2 == 1;
            }

            public final volatile Object apply(Object v1) {
                return BoxesRunTime.boxToBoolean(apply(BoxesRunTime.unboxToInt(v1)));
            }

            public static final long serialVersionUID;

            static {
                0L;
                serialVersionUID = 0L;
            }
        }
    );

    scala.Function1 evenFilter = new Serializable() {
            public final boolean apply(int i) {
                return apply$mcZI$sp(i);
            }

            public boolean apply$mcZI$sp(int v1) {
                return v1 % 2 == 0;
            }

            public final volatile Object apply(Object v1) {
                return BoxesRunTime.boxToBoolean(apply(BoxesRunTime.unboxToInt(v1)));
            }

            public static final long serialVersionUID;

            static {
                0L;
                serialVersionUID = 0L;
            }
        };
        Predef$.MODULE$.println(odds);
        Predef$.MODULE$.println(integers.filter(evenFilter));
    }

    private Example005FunctionLiterals$() {
    }

    public static final Example005FunctionLiterals$ MODULE$ = this;

    static {
        new Example005FunctionLiterals$();
    }
}
Här kan vi se att varje rad i Scala-koden har en motsvarande rad i Java-koden vilket gör den lätt att följa. På rad 20 skickas en anonym klass in som argument till metoden filter och som implementerar metoden apply(int) på rad 22, vilket är allt som behövs för att filtrera listan. På rad 43 kan vi se att våra filter hanteras av trait:et scala.Function1.

Sammantaget är inte funktioner så komplicerat i Scala!

torsdag 17 november 2011

Programming in Scala - fördjupning

Nu har jag programmerar Scala på ledig tid i ganska exakt ett år. Det har varit roligt och lärorikt och något jag kan rekommendera insnöade Java-programmerare och andra som vill testa ett elegant språk med stöd för funktionell programmering!

Jag har hittills bara läst 200-300 sidor ut boken Programming in Scala second edition men planen är nu att läsa hela boken och att samtidigt förstå språket lite mer på djupet. Sättet jag tänkt göra det på är i huvudsak genom kodexempel. Jag kommer att göra nedslag på sådant jag tycker förtjänar extra uppmärksamhet eller som är svårsmält för en icke insatt, dit jag än så länge räknar mig själv! Jag kommer att läsa boken från pärm till pärm och rapportera om mina "upptäckter". Projektet Tetris Analyzer återkommer jag till vid ett senare tillfälle.

Exempel 1 - Referera arrayer och listor


I Scala kan man referera arrayer och listor med syntaxen (t ex) minLista(0) när man vill hämta ut ett element ur listan. Kompilatorn kommer då att göra om anropet till minLista.apply(0). Detta var jag förstås tvungen att testa (all kod finns på GitHub):
package nu.tengstrand.scalalab.programminginscala

/**
 * How to build your own List/Array classes.
 * Page 39 in the book "Programming in Scala, 2nd edition".
 *
 * Author: Joakim Tengstrand
 * Repository: git@github.com:tengstrand/Scala-Lab.git
 */
object Example001ListSyntax {
  def main(args: Array[String]) {
    val myArray = new MyArray()
    println(myArray(0)) // output: 1
    println(myArray.apply(1)) // output: 2
  }
}

class MyArray {
  val array = Array(1,2,3)

  def apply(i: Int) = array(i)
}

Allt som behövs är att implementera metoden apply(Int) på rad 21 varefter vi på rad 13 hämtar första elementet i listan. Metoden apply är en helt vanlig metod, vilket demonstreras på rad 14. Scala löser denna och andra liknande uppgifter genom konventioner. Konventionen i detta fall är att kompilatorn förväntar sig finna metoden apply när den stöter på en variabel följt av parenteser, vilket i mitt tycke är ett elegant sätt att lösa problemet.

Exempel 2 - Symboler


Nästa konvention är att om ett '-tecken "enkelfnutt" föregår en variabel så kommer kompilatorn uppfatta det som en Symbol vars attribut name är själva värdet på variabeln, detta beskrivs förvisso bra i boken men jag kände mig ändå sugen på att testa:
package nu.tengstrand.scalalab.programminginscala

/**
 * Example how to use symbols.
 * Page 80 in the book "Programming in Scala, 2nd edition".
 */
object Example002Symbol {
  def main(args: Array[String]) {
    new Example().print('KalleKanin) // output: Value: KalleKanin
  }
}
g
class Example {
  def print(value: Symbol) {
    println("Value: " + value.name)
  }
}
Verkar ju fungera! KalleKanin skickas in från rad 9 och skrivs ut på rad 15.

Exempel 3 - Teckensättning


I nästa exempel tänkte jag testa hur man gör sin egen klass som hanterar teckensättning:
package nu.tengstrand.scalalab.programminginscala

/**
 * Example how to use unary operators on own classes
 * Page 83 in the book "Programming in Scala, 2nd edition".
 */
object Example003UnaryOperatorSyntax {
  def main(args: Array[String]) {
    val value = new MyType(123)
    println(-value) // output: -123
    println(+value) // output: 123
    println(value.unary_-) // output: -123
  }
}

class MyType(value: Int) {
  def unary_- = new MyType(-value)
  def unary_+ = this
  override def toString = value.toString
}

Metoden unary_- implementeras på rad 17 och anropas från rad 10, metoden unary_+ implementeras på rad 18 och anropas från rad 11. Rad 12 visar att det är en helt vanlig metod som kan anropas som vilken annan metod som helst.

Exempel 4 - Lokala funktioner


I Scala kan man definiera funktioner i andra funktioner och metoder, så kallade lokala funktioner. Detta kan vara användbart när man vill öka läsbarheten och minska kodduplicering i koden:
package nu.tengstrand.scalalab.programminginscala

/**
 * Shows how to use local functions to simplify the code.
 * Page 144 in the book "Programming in Scala, 2nd edition".
 */
object Example004LocalFunctions {

  def main(args: Array[String]) {
    println(format(1,2,3,4, 10)) // output: (13:23)(33:43)
  }

  /**
   * The outer variable 'factor' is accessible from the local method multiply.
   * This technique can be used to simplify a function/method.
   */
  def format(a1: Int, a2: Int, b1: Int, b2: Int, factor: Int) = {
    val x = 3

    def multiply(value: Int) = value * factor + x
    def concat(value1: Int, value2: Int) = "(" + multiply(value1) + ":" + multiply(value2) + ")"

    concat(a1,a2) + concat(b1,b2)
  }
}

Det fina med lokala funktioner är att de har åtkomst till variabler och argument definierade i den omslutande funktionen vilket gör att dessa inte behöver läggas till argumentlistan i den lokala funktionen. I det här exemplet har metoden multiply tillgång till variabeln x och argumentet factor.

Det var allt för denna gång!

måndag 9 maj 2011

Prestanda

Tänkte börja med att berätta att projektet nu har återtagit sitt gamla namn Tetris Analyzer och även flyttat till GitHub. Anledningen är att det under en längre tid inte gått att ändra namn på SourceForge och att jag ville gå från Subversion till GIT. Google Code var också ett intressant alternativ men saknar stöd för GIT.

Optimera koden - första försöket
Fokus har sedan förra inlägget varit att förbättra prestandan på programmet. Efter att ha optimerat den befintliga koden var det ändå långt kvar till målbilden på 10.000 bitar per sekund. Jag bestämde mig i det läget för att leta efter en bättre algoritm. Då jag skrivit ett antal olika Tetris-varianter genom åren hade jag en ganska klar bild över hur detta kunde göras. Ambitionen nu var att prestandaoptimera koden så hårt som möjligt.

Lilla optimeringsskolan
Min erfarenhet av prestandaoptimering är att om man vill uppnå maximal prestanda och har gott om tid bör man gå till väga ungefär så här:
  • Tänk förutsättningslöst och använd din fantasi, kreativitet och erfarenhet.
  • Ställ dig frågan: hur skulle den snabbaste lösningen kunna se ut? Svaret på frågan kanske inte går att implementera i praktiken men är något varifrån man kan plocka idéer.
  • Försök föreställa dig, eller mät om det går, vilka delar som tjänar mest på att optimeras. Svaret är nästan alltid innerlooparna då den koden genomlöps flest gånger.
  • Föruträkna! Att räkna ut saker på förhand är ofta en bra strategi då den kan ta bort instruktioner från innerloopar och flytta kod till block som inte genomlöps lika ofta. Inte sällan räcker det med att göra denna föruträkning en gång, och det är inte ens säkert att den behöver göras när programmer körs utan kan i vissa fall laddas in som "färdigt data" om så skulle behövas.
  • Det är ofta bra att ha nära beroenden mellan de klasser som opererar i en innerloop, vilket går emot vad man vanligtvis rekommenderar. Detta är bra då man kan hitta lösningar där klasserna kan sammarbeta och servar varandra på ett optimalt sätt. Det är bra att försöka begränsa mängden kod som är hårt optimerad då den vanligtvis är svårare att sätta sig in i och underhålla.
  • Fundera kontinuerligt på om det går att förfina befintlig eller hitta en bättre algoritm och om så är fallet och det är ekonomiskt och tidsmässigt motiverat, skriv om koden! 

Optimera koden - andra försöket
Jag började med att att försöka refaktorera den befintliga koden men insåg ganska snart att den nya klasstrukturen skilde sig så mycket från det jag hade att det gick snabbare att skriva om allt från början. Endast delar av test-suiten gick att återanvända och det var endast ett fåtal klasser vars tester i stort sett var opåverkade bl.a BoardTest och GameTest (vilket var ytterligare ett argument för att skriva om i stället för att refaktorera). En gemensam nämnare för dessa tester är att de lyckats testa beteende och inte behövt bry sig om implementationsspecifika detaljer. Detta är något att sträva efter när man skriver tester!

Den nya koden inriktade sig framför allt på dessa delar:
  • Optimera representationen av Board, bl.a genom att skippa hanteringen av färger som varken behövs vid uträkning av giltiga flytt eller vid evaluering av brädet (som utförs av TengstrandBoardEvaluator1) och dels genom att utföra bit-operationer som kan operera på fler "pluppar" åt gången (en bit består av fyra pluppar).
  • Få en tajtare koppling mellan klasserna Piece och Board där deras inre representationer kan samverka på ett bra sätt. Lösningen här blev att skapa klassen PieceMove som kan utföra alla nödvändiga operationer mot Board. Varje instans av PieceMove är föruträknad för att jobba mot en Board av en viss storlek (normalt 10x20). Den utnyttjar även att den känner till Boards interna representation så att den kan utföra snabba AND- och OR-operationer (tajt koppling). Denna lösning utnyttjar både föruträkning och hård koppling.
  • Föruträkna alla giltiga flytt och rotationer som en bit kan utföra på en tom Board av en viss storlek med givna regler (ValidPieceMovesForEmptyBoard). Regler kan t ex vara i vilken startposition biten har eller huruvida sliding* är påslagen. När denna del väl är föruträknad kan alla villkor tas bort från koden som utför förflyttning av en bit (ValidMoves).
  • Använd snabbast möjliga datatyper och kollektioner vilket i Scala visar sig ofta vara Array då de kompilerar till Java arrayer (gäller för listor som inte behöver växa dynamiskt)
(*) När sliding är påslagen kan man rotera biten fritt över hela brädet men om den är avslagen kan den endast rotera och flytta sig fritt på översta raden och måste därefter droppas rakt ned till "marken".

För att summera upp det hela ska man först koncentrera sig på innerlooparna och därefter hitta en bra algoritm som stödjer detta. Använd föruträkningar och hårda kopplingar mellan klasser i innerlooparna.

Resultat
När jag körde den optimerade koden visade det sig att den nu gjorde 6.100 bitar per sekund vilket i och för sig var en fördubbling men som tyvärr inte träffade min målbild på 10.000 bitar/sek. För att ha något att jämföra med, tog jag fram en version i Java som följde exakt samma algoritm som Scala-versionen. Vid testkörning gjorde den smått imponerande 15.800 bitar per sekund! Då båda språken kör på samma JVM låg det en hund begraven någonstans! Nu började arbetet att gräva upp och avlägsna denna objudne gäst. Steg ett var att identifiera vilka delar av koden som tog längre tid i Scala än i Java.

Jag började med att mäta tidsåtgången i de olika delarna av koden och hade hela tiden Java-versionen att jämföra med. Ganska snabbt kunde jag se att huvudproblemet låg i klassen TengstrandBoardEvaluator1. Jag använde nu Jad för att decompilera Scala-versionens bytekod till Java. Till min glädje hade all användning av Array gjorts om till "riktiga" Java-arrayer. Det som ur prestandasynpunkt inte såg lika bra ut var for-looparna. Scalas for-loopar är implementerat som en intern DSL och upplevs som en naturlig del av språket, men är inte lika "lågnivå" som i Java. Jag testade då att ersätta alla for-loopar i TengstrandBoardEvaluator1 med while-satser (som efter ändringen såg ut så här). Voala! Nu exekverar programmet plötsligt i en hastighet av 14.700 bitar per sekund! Koden blev lite fulare med while-satser i stället för for-loopar men är ändå ett billigt pris att betala denna gång. En klart godkänd förbättring från de ursprungliga 2.200 bitarna per sekund.

Här följer en sammanfattning av prestandan för de olika versionerna:

Språk Sliding på (bitar/sek) Sliding av (bitar/sek) Repository Version
Scala 2.000 2.200 SourceForge Första versionen
Scala 2.500 2.900 SourceForge Första versionen med optimerad TengstrandBoardEvaluator
Scala 2.800 6.100 GitHub En andra helt omskriven version, TengstrandBoardEvaluator1 ej optimerad
Scala 3.700 14.700 GitHub En andra helt omskriven version med optimerad TengstrandBoardEvaluator1
Java 5.000 15.800 GitHub Version i Java

Den andra varianten, den som gör 2.900 bitar per sekund, har jag lagt med för att kunna jämföra hur stor prestandaskillnad som själva omskrivningen till ny algoritm utgör. Vi kan se att programmet gått  från 2.900 till 14.700 bitar per sekund efter omskrivning till ny algoritm!

Då jag genomgående valt de snabbaste lösningarna jag hittat, har den resulterande koden inte andats så mycket Scala utan har mer sett ut som C++ eller Java. Målet framöver är att försöka höja abstraktionsnivån och få den att kännas mer som Scala!

    tisdag 22 februari 2011

    Algoritmen

    Detta inlägg kommer i huvudsak ta upp två saker. Först tänkte jag börja med att skryta om att jag skrivit världens bästa Tetris-algoritm! Därefter kommer en genomgång av hur algoritmen fungerar.

    Världens bästa Tetris AI
    Colin Fahey är vad jag vet den ende som systematiskt samlat algoritmer som spelar Tetris och genom att ha standardiserade regler också kunnat jämföra algoritmerna sinsemellan. Under sektion 10. Best one-piece Tetris-playing algorithm in the world beskrivs en algoritm som är skriven av fransmannen Pierre Dellacherie och som officiellt är den bästa kända altoritmen. Den gör ca 675.000 bitar i snitt per spel i en hastighet av 160 bitar per sekund på en 800 Mhz dator. Algoritmen som detta projekt (TetrisAi) använder sig av är något vassare och gör 1.800.000 bitar i snitt per spel i en hastighet av 15.000 bitar per sekund (C++ versionen) på en 2.8 Ghz Pentium. Den gör alltså nästan tre gånger så många bitar per spel och är ca 25 gånger så snabb om man tar hänsyn till skillnad i klockfrekvens. Har under de senaste tio åren inte hittat någon algoritm som gör fler bitar per spel (d.v.s spelar bättre) men dock en som är snabbare och det är HP's Tetris som enligt hans egna uppgifter gör 24.000 bitar per sekund på en 2.2 Ghz PC.

    Hur algoritmen fungerar
    När programmet TetrisAi ska hitta det bästa sättet att placera aktuell bit, går den igenom alla giltiga sätt att placera biten. För varje giltigt drag/placering rensas eventuellt kompletta/fulla rader varefter positionen är redo att värderas av algoritmen. Om utöver aktuell bit även nästa bit är känd och/eller sökdjupet (level) är större än antalet kända bitar, är algoritmen för vilka positioner som ska värderas något mer komplicerad vilket jag kommer beskriva då Scala-versionen får stöd för detta. Den position som har den lägsta värderingen ses av algoritmen som det bästa draget för aktuell bit. Antag att vi har följande position:


    Siffrorna i vänsterkant visar y-värdet och siffrorna i underkant visar x-värdet. Som algoritmen ser ut nu, och som den sett ut sedan C++ versionen skrevs någon gång mellan 2001-2002, är att den värderar positionen utifrån tre egenskaper som den adderar ihop för att få fram den slutliga värderingen. Värdet på positionen kallas i algoritmen för equity och är en benämning tagen från Backgammon där den används som beteckning på värdet av en position. Det finns för övrigt ganska många likheter mellan Backgammon och Tetris t ex att man inte vet vilka bitar i Tetris eller tärningsslag i Backgammon som ska komma. Följande tre egenskaper mäts:

    Konturens höjd
    Denna egenskap mäter hur högt bygget är eller rättare sagt hur hög konturen är för respektive kolumn (x-värde):

     
    Ju högre konturen är, desto större värde adderas till equity. Värdet 2,5 adderas för kolumnerna 1, 5 och 6, värdet 2,2 för kolumnerna 2, 4 och 7, värdet 1,8 för kolumnerna 0 och 3 och slutligen värdet 1,3 för kolumnerna 8 och 9. Totalt adderas 2,5*3 + 2,2*3 + 1,8*2 + 1,3*2 = 20.3 till equity. Detta exempel har en väldigt låg höjd med en storlek på 10x5 mot normalt 10x20. Hade spelplanen varit normalstor hade värdet blivit 0.1*10 = 1 i stället för 20.3, och då varit den egenskap (av tre) som påverkat värderingen av positionen minst.

    Konturens struktur
    Nästa egenskap som mäts och adderas till equity är avgränsade områden i konturen. Ett sådant område är avskilt med väggar på dess båda sidor. När spelet börjar är detta avgränsade område 10x20. Det minsta möjliga området är 1x1 likt C i bilden nedan. Ju högre området är desto större värde adderas till equity. Ju bredare desto lägre värde adderas till equity med undantag för bredden 3 som har en större konstant än bredden 2 och anses alltså vara sämre.


    För att beräkna värdet av ett område multipliceras en konstant som varierar med bredden med en annan konstant som varierar med höjden. Område A har bredden 1 vilket ger konstanten 4,25 och höjden två som ger konstanten 1,19 och produkten 5,0575. Område B har bredden 3 som ger konstanten 3.1 och höjden 1 som ger konstanten 0,42 och produkten 1,302.

    Det finns ytterligare en parameter att ta hänsyn till i denna beräkning och det är huruvida väggarna på respektive sida om området har samma höjd. Område B har samma höjd (y=2) på de väggar som avgränsar området (kolumnerna 1 och 5) till skillnad från område D där höjden på väggarna skiljer sig (kolumn 6 har y=2 och kolumn 10 har y=0). Område B anses vara något gynsammare än D:
    • A: 1x2 = 4,25*1,19 = 5.0575
    • B: 3x1 = 3,1*0,42 = 1,302
    • C: 1x1 = 4,25*0,42 = 1,785
    • D: 3x1 = 3,1*0,5 = 1,55
    • E: 2x2 = 2,39*1,19 = 2,8441
    Lägger man ihop dessa fem värden får man 12,5386 som adderas till equity.

    Det finns en felaktighet i hur områden som angränsar mot den högra väggen (kolumn 10) beräknas i C++ versionen (version 1.0). Där sätts y-värdet för kolumn 10 till 2 (lägsta y-värde på konturen) varpå område D uppfattas som ett område vars omslutande väggar har samma höjd och får därför samma värdering som område B. Detta är åtgärdat i aktuell version av algoritmen: TengstrandBoardEvaluator1 (version 1.1) och verifierat med testet TengstrandBoardEvaluator1Test.

    Håligheter
    Denna egenskap mäter håligheter i positionen. Till håligheter räknas rader där det finns hål som täcks av någon ovanliggande rad. I bilden nedan är rad 3 täckt av rad 2 i kolumn 6.

    Konstanterna i högerkant varierar beroende på antalet fyllda rutor på raden. Tre fyllda rutor (rad 2) ger konstanten 0,1, fem fyllda rutor (rad 3) ger konstanten 0,3 och sju fyllda rutor (rad 4) ger konstanten 0,5.


    För varje rad med början på den högsta konturen (y=2) t.o.m sista raden (y=4) görs en sak till förutom att beräkna nyss nämnda konstant. För varje kolumn i raden görs följande: i fallet att en ruta är tom kontrolleras det om rutan är täckt genom att se i fall konturen för kolumnen är mindre än y-värdet för raden vilket i så fall betyder att vi hittat ett hål. Därefter beräknas värdet som ska adderas till equity genom att multiplicera alla konstanter från och med raden som motsvarar konturen för den kolumn där hålet hittats till och med aktuell rad. Värdet 10 i beräkningen är positionens bredd:
    • Rad 3: (1 - 0.1*0.3)*10 = 9,7
    • Rad 4: (1 - 0,3*0,5)*10 = 8,5
    Rad 3 multiplicerar med konstanterna för rad 2 t.o.m 3 (2 då kolumn 6 är täckt av rad 2).
    Rad 4 multipliceras med konstanterna för rad 3 t.o.m 4 (3 då kolumn 4 är täckt av rad 3).

    Totalt motsvarar egenskapen håligheter värdet 9,7+8,5 = 18,2 som equity räknas upp med.

    Equity för respektive egenskap:
    • Konturens höjd: 20,3
    • Konturens struktur: 12,5386
    • Håligheter: 18,2
    Vilket ger en total equity för positionen på: 51,0386

    fredag 11 februari 2011

    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!

    torsdag 20 januari 2011

    Är det fult så är det fel!

    Vill bara börja med att redogöra lite för min viktigaste och trognaste designprincip som jag lutat mig mot ett antal år. Den lyder: Är det fult så är det fel! Den är mycket bra att använda sig av när man funderar över huruvida man behöver skriva om sin (eller annans) kod eller inte. Om svaret på frågan är det fult är ja mår åtminstone delar av koden bra av att skrivas om.

    Ett designbeslut kan kännas okej när man gör det, men hundra rader kod senare upptäcker man att det plötsligt ser fult ut. I mitt förra gjorde jag ett designbeslut att låta klassen Position hantera placering av Piece men inte hantera rotationsläget av den samma (det var gjort så i Java-versionen). När jag lade till hantering av den nya klassen Move till Position blev problemen tydliga. Move hanterar både x,y och rotation och det finns stöd för att sätta en Move direkt i Position via metoden movePiece(move: Move). Att det samtidigt gick att rotera en Piece via en instans utanför Positions kontroll ledde till extrakod som dessutom inte var helt uppenbar varför den behövdes när man tittade på den.

    Det blev helt enkelt fult och är det fult så är det fel. Jag hade i och för sig haft en känsla hela tiden att det kanske inte var så bra att låta Piece hantera sin egen rotation, men valde ändå att testa detta då det verkade bli en enklare hantering (vilket det också var till en början). Fick det även påpekat av en kollega som ställde sig undrande till min design! Problemet löste sig genom att låta Position ha hand om både bitens placering och rotationsläge. Ett annat resultat av manövern blev att koden från PieceType fick flytta in till Piece och att PieceType kunde tas bort. Position ser nu ut så här:
    package net.sf.tetrisai
    
    import move.Move
    import piece.Piece
    import settings.GameSettings
    
    class Position(board: Board, val piece: Piece, settings: GameSettings) {
      val boardWidth = board.width
      val boardHeight = board.height
      var pieceMove = settings.pieceStartMove(board.width, piece)
      val rotationDirection = settings.rotationDirection
    
      def setPiece() = piece.shape(pieceMove.rotation).dots.foreach(dot => board.set(dot + pieceMove, piece.number))
      def clearPiece() = 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 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
        }
      }
    }
    

    I metoden isValidMove på rad 18 låter jag språket självt hålla reda på om biten hamnat utanför brädets kanter genom att låta den fånga IndexOutOfBoundsException. Detta är både en presntandaoptimering och tar samtidigt bort en hel massa boundary-checks som jag annars skulle behövt lägga till.

    Klassen Move ser ut så här:
    package net.sf.tetrisai.move
    
    import net.sf.tetrisai.piece.Point
    
    object Move {
      def apply(y: Int, x: Int, rotation: Int) = new Move(y, x, rotation)
    }
    
    class Move(y: Int, x: Int, val rotation: Int) extends Point(x,y) with Ordered[Move] {
      def down = new Move(y + 1, x, rotation)
      def left = new Move(y, x - 1, rotation)
      def right = new Move(y, x + 1, rotation)
      def rotate(rotationType: RotationDirection, rotationModulus: Int) = new Move(y, x, (rotation + rotationType.direction) & rotationModulus)
    
      def compare(that: Move): Int = {
        if (y != that.y)
          y compare that.y
        else
          if (x != that.x)
            x compare that.x
          else
            rotation compare that.rotation
      }
    
      override def equals(that: Any) = that match {
        case other: Move => y == other.y && x == other.x && rotation == other.rotation
        case _ => false
      }
    
      override def toString = "Move(" + y + "," + x + "," + rotation + ")"
    }
    

    Det som kan vara värt att nämna här är att jag ärver från klassen Point och att jag gjort klassen sorterbar (mitt test vill ha en förutsägbar ordning på listor av Move). Det är en väldigt elegant syntax när man ska delegera vidare konstruktorns argument till den ärvda klassen (rad 9): extends Point(x,y). En ny instansvariabel position (rad 9) har också tillkommit vilket markeras med nyckelordet val (immutable value).

    En annan detalj som kan se konstigt ut för en Javaprogrammerare är syntaxen på rad 17 y compare that.y. Detta tolkas av Scala som y.compare(that.y) och det är en smaksak vilket man väljer!

    Vän av ordning undrar nu säkert varför Move ärver från Point. Anledningen är att Move ibland ska hanteras som en Point vilket görs av metoderna setPiece, clearPiece och isValidMove i klassen Position där vi adderar en Point med en Move (rad 13, 14 och 20).

    För att stödja olika rotationsriktningar (med- och moturs) i metoden rotate (rad 13 i klassen Move) har jag lagt till den abstrakta klassen RotationDirection:
    package net.sf.tetrisai.move
    
    abstract class RotationDirection {
      val direction: Int
    }
    

    Själva klassen är markerad som abstrakt och attributet direction är här inte satt vilket implicit gör den abstrakt. Mina två implementationer av denna klass måste därför implementera detta värde. ClockwiseRotation:
    package net.sf.tetrisai.move
    
    class ClockwiseRotation extends RotationDirection {
      val direction = 1
    }
    
    AnticlockwiseRotation:
    package net.sf.tetrisai.move
    
    class AnticlockwiseRotation extends RotationDirection {
      val direction = -1
    }
    

    Målet med detta projekt är att datorn själv ska kunna spela Tetris. Ett steg på vägen är att leta fram giltiga flytt för en viss position. Klassen ValidMoveCalculator hanterar detta, tillhörande test ser ut så här:
    package net.sf.tetrisai.move
    
    import org.junit.Test
    import net.sf.tetrisai.settings.DefaultGameSettings
    import net.sf.tetrisai.{Position, Board, BaseTest}
    import net.sf.tetrisai.piece.PieceS
    
    class ValidMoveCalculatorTest extends BaseTest {
    
      @Test def validMoves() {
        val board = Board(Array(
          "#-----#",
          "#-----#",
          "#--X--#",
          "#--X--#",
          "#######"))
        val position = new Position(board, new PieceS, new DefaultGameSettings)
        val validMoveCalculator = new ValidMoveCalculator(position)
        val moves = validMoveCalculator.validMoves.sorted[Move]
    
        moves should be (List(Move(0,1,0), Move(0,2,0), Move(0,2,1), Move(1,0,0), Move(1,0,1), Move(1,3,1)))
      }
    }
    

    Implementationen av ValidMoveCalculator:
    package net.sf.tetrisai.move
    
    import net.sf.tetrisai.Position
    
    class ValidMoveCalculator(val position: Position) {
      var moves: List[Move] = Nil
      val visitedMoves = Array.fill(position.boardHeight, position.boardWidth) { 0 }
    
      private def markAsVisited(move: Move) { visitedMoves(move.y)(move.x) |= 1 << move.rotation }
      private def isUnvisitedMove(move: Move): Boolean = {
        try {
          (visitedMoves(move.y)(move.x) & (1 << move.rotation)) == 0
        } catch {
          case e: IndexOutOfBoundsException => false
        }
      }
    
      def validMoves = {
        moves = List.empty[Move]
        calculateValidMoves
        moves
      }
    
      private def calculateValidMoves {
        while (isUnvisitedMove(position.pieceMove) && position.isValidMove) {
          val move = position.pieceMove
          markAsVisited(move)
          if (position.isValidMove(move down)) {
            position.movePiece(move down)
            calculateValidMoves
          } else {
            moves = move :: moves
          }
          position.movePiece(move left)
          calculateValidMoves
          position.movePiece(move right)
          calculateValidMoves
    
          position.movePiece(move)
          position.rotatePiece
        }
      }
    }
    

    Hanteringen att ta fram giltiga flytt var i C++ versionen rätt hårt optimerad och
    svårbegriplig. Här har jag i stället valt att göra den rekursiv. Då vi med flaggor i visitedMoves markerar vilka sökvägar som redan behandlats bör vi även får bra prestanda. Anledninge till att jag tjatar om bra prestanda är att finjusteringen av algoritmerna som väljer bästa plats för en bit kräver bra prestanda (återstår att implementera). Den låter datorn spela x antal miljoner bitar per parametersättning. Sedan görs en statistiks jämförelse mellan de olika parametersättningarna för att hitta bästa värde för respektive parameter.