Musterlösung Patternmatching

Bei vielen Scala-Lernenden scheint es drei Phasen beim Umgang mit Patternmatching zu geben: Skepsis, Hype und Normalität. Zuerst begegnen viele OO-Vorbelastete diesem Feature mit Skepsis. Martin Odersky beschreibt diese Ressentiments sehr schön in seinem Artikel “In Defense of Pattern Matching”. Nachdem man die Nützlichkeit (und die Ungültigkeit der Gegenargumente) verstanden hat, wird sinnlos alles gematcht, was einem vor die Flinte kommt. Schließlich findet man früher oder später das rechte Maß, wobei Denkanstöße wie Tony Morris’ Option Cheat Sheet zeigen, dass Patternmatching eben nicht immer die beste Lösung ist.

Heute wollen wir einmal ganz systematisch verschiedene Details des Patternmatching beleuchten. Prinzipiell ähnelt Patternmatching einem switch-Statement in Java, und kann auch so benutzt werden. Die drei Hauptunterschiede sind, dass kein “Durchfallen” zum nächsten Fall möglich ist (was in Java mit break verhindert werden muss), dass match im Gegensatz zu Javas switch einen Wert zurückliefert, und dass ein MatchError ausgelöst wird, wenn keines der Muster passt. Statt default schreibt man case _. Die Muster werden wie in Java von oben nach unten abgearbeitet, und das erste passende “gewinnt” (selbst wenn noch weitere passen würden):

def test(ch: Char) = ch match {
  case 'a' => "Vokal a"
  case 'e' => "Vokal e"
  case 'i' => "Vokal i"
  case 'o' => "Vokal o"
  case 'u' => "Vokal u"
  case _ => "Konsonant"
}
//--> test: (Char)java.lang.String

println(test('u'))
//--> Vokal u
println(test('v'))
//--> Konsonant

Soll ein Fall für mehrere Muster gelten, kann man diese mit | (was ja sonst auch “oder” bedeutet) verknüpfen:

def test(ch: Char) = ch match {
  case 'a' | 'e' | 'i' | 'o' | 'u'=> "Vokal"
  case _ => "Konsonant"
}

Mit Patternmatching hat man auch ein sicheres und bequemes Äquivalent zu Javas berüchtigten instanceof-Kaskaden. Dazu gibt man als Muster eine Variable an und hinter dem Doppelpunkt ihren Typ. Lässt man den Typ weg, passt die Variable auf alle ankommenden Werte. Interressiert nur der Typ, aber nicht der Wert, kann man _ : Typ schreiben:

def test(any: Any) = any match {
  case s: String => "String " + s
  case i: Int => "Int " + i
  case l: List[_] => "List of length " + l.size
  case _: BigInt => "BigInt" 
  case x => "Something else: " + x
}
//--> test: (Any)java.lang.String

test("hallo")
//--> res4: java.lang.String = String hallo
test(42)
//--> res5: java.lang.String = Int 42
test(List(2,3,4))
//--> res6: java.lang.String = List of length 3
println(test(BigInt(123)))
//--> BigInt
println(test(42L))
//--> Something else: 42

Hier lauert allerdings schon die erste kleinere Falle: Dies ist meines Wissens die einzige Stelle in Scala, bei der Groß- und Kleinschreibung eine Rolle spielt: Obiges Schema funktioniert nur, wenn die zu belegenden Variablen (also hier s, i, l und x) klein geschrieben werden.

Kann man in den Mustern eigentlich auch auf bereits definierte Variablen im Sichtbarkeitsbereich zugreifen? Man kann, muss diese aber in Backticks einschließen. Dieses eher selten gebrauchten Zeichen befinden sich auf einer deutschen Tastatur zwischen ß und Backspace, man muss Shift und diese Taste drücken, und danach die Leertaste. Ein etwas an den Haaren herbeigezogenes Beispiel:

def test(x: String, y: String, value: String) = {
  val xy = x + y
  val yx = y + x 
  value match {
    case `xy` => "XY"
    case `yx` => "YX"
    case _ => "nothing"
  }
}
//--> test: (String,String,String)java.lang.String

test("der", "Spargel", "Spargelder")
//--> res8: java.lang.String = YX

Ein weitere nützliche Hilfe sind Guards (oder “Wächter”), mit denen man zusätzliche Bedingungen an einen bestimmten Fall stellen kann. Diese werden mit if eingeleitet, man braucht aber keine Klammern wie beim normalen if:

def test(value: Int) = value match {
  case 2 | 3 | 5 => "Primzahl"
  case i if i%2==0 || i%3==0 || i%5==0 => "zusammengesetzte Zahl"
  case _ => "da muss ich genauer ueberlegen"
}
//--> test: (Int)java.lang.String

println(test(135))
//--> zusammengesetzte Zahl
println(test(121))
//--> da muss ich genauer ueberlegen

Nun kommen wir zum Patternmatching mit Fallklassen. Ist eine Klasse als Fallklasse definiert worden, kann man sie direkt als Muster verwenden und dabei Variablen für ihre Einzelteile vergeben. Typische Beispiele dafür sind Tupel und die Unterklassen von List (:: und Nil), Option (Some und None) und Either (Left und Right). Sogar geschachtelte Kombinationen sind erlaubt:

def test(list: List[Option[String]]) = list match {
  case Some(x) :: Some(y) :: _ => x + y
  case Some(x) :: None :: _ => x 
  case None :: Some(y) :: _ => y
  case head :: Nil => "List with one element: " + head
  case Nil => "empty list"
}
//--> test: (List[Option[String]])java.lang.String

println(test(List(Some("a"),Some("b"))))
//--> ab
println(test(List(None,Some("c"))))
//--> c
println(test(List(Some("x"))))
//--> List with one element: Some(x)
println(test(List()))
//--> empty list

Das Verhalten von Fallklassen in Mustern ist nichts magisches. In gewöhnlichen Klassen kann man den gleichen Effekt erreichen, indem man eine geeignete unapply()-Methode implementiert. Gottseidank brauche ich das nicht auch noch aufzuschreiben, denn das habe ich schon einmal erklärt.

Hat eine Fallklasse eine variable Anzahl Parameter, kann man “den Rest” mit _* überspringen, denn _ würde sich ja nur auf ein einzelnes Element beziehen. Man beachte, dass dieser Rest auch “leer” sein kann:

 
def test(list: List[String]) = list match {
  case List("1","2", _*) => "one, two ..."
  case _ => "dunno"
}
//-->test: (List[String])java.lang.String

println(test(List("1","2")))
//--> one, two ...
println(test(List("1","2","3","4")))
//--> one, two ...

Ein Feature, das ich selbst noch nicht benutzt habe, ist das “Variable Binding”. Damit kann man bei geschachtelten Fallklassen einen Teilausdruck sowohl an eine Varible binden, als auch gleichzeitig weiter zerlegen (eventuell mit weiteren Variablen-Bindungen). Klingt komplizierter als es ist. Im folgenden Beispiel suchen wir in einer Liste von Listen eine, deren erste Unterliste als erstes Element ein “x” enthält, und wollen sowohl die gesamte Unterliste wie auch deren zweites Element jeweils an eine Variable gebunden haben. Dazu schreibt man zuerst die Variable für den gesamten Teilausdruck, und hinter einem @ die weitere Zerlegung entsprechend einem vorgegebenen Muster:

def test(list: List[List[String]]) = list match {
  case (sublist @ List("x", second, _*)) :: _ => "" + sublist + " | " + second
  case _ => "nothing"
}
//--> test: (List[List[String]])java.lang.String

println(test(List(List("x","y","z"))))
//--> List(x, y, z) | y
println(test(List(List("w","x","y","z"))))
//--> nothing

Natürlich lassen sich alle hier vorgestellten Möglichkeiten beliebig miteinander kombinieren. Aber nur weil man es kann heißt das noch lange nicht, dass man es auch muss. Patternmatching ist ein tolles Werkzeug – wer beispielsweise jemals in Java das Visitor Pattern implementieren musste, wird es sicher zu schätzen wissen. Ich rate aber aus eigener Erfahrung dazu, ein wenig Augenmaß zu bewahren, denn wie heißt es so schön: “Wenn das einzige Werkzeug, was man hat, ein Hammer ist, sieht jedes Problem aus wie ein Nagel.”

Auch wenn ich nicht ins Detail gegangen bin, hoffe ich, einen einigermaßen vollständigen und verständlichen Überblick über dieses wichtige Teilgebiet der Scala-Syntax gegeben zu haben.

Scala 2.8.0 RC1

Kaum schaue ich mal nicht hin, passieren interessante Sachen hinter meinem Rücken: Scala 2.8.0 RC1 ist schon ein paar Tage verfügbar.

Vier gewinnt – Künstliche Intelligenz

Ich denke, es ist höchste Zeit, endlich wieder etwas substanzielleres als Lebenszeichen und Hinweise auf Links abzuliefern. Wer sich noch daran erinnert: Ich hatte zwei Artikel über “Vier gewinnt” geschrieben, und dabei angedeutet, dass ich auch noch einen Computerspieler abliefern wollte. Nun muss ich gestehen, dass mein Code etwas vermurkst ist, und ich selber nicht genau weiss, ob das nun ordentliches Alpha-Beta-Pruning ist. Das Bemerkenswerte ist aber, dass diese kurze, aber verwirrende Implementierung funktioniert, und zwar so gut, dass ich ziemliche Mühe habe zu gewinnen. Deshalb – und weil ich immer noch auf Geschäftsreise bin – poste ich einfach meinen Frankenstein-Code, hoffe auf ruhigere Zeiten und bete zu den isländischen Vulkangöttern, dass sie mich nächstes Wochenende wieder über den großen Teich nach hause lassen.

case class AI(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = {
    Some(board.move(bestMove(board, coin, 5)._1, coin))
  }

  def bestMove(board: Board, coin: Coin, depth: Int): (Int, Int) = {
    val moveList =  List(3,4,2,5,1,6,0).filter(board(_, 0) == None)
    moveList.foreach(m => if (board.move(m, coin).winner == Some(coin)) return (m,1000000))
    val moves = moveList.sortBy(m => -eval(board.move(m, coin), coin))
    if (moves.isEmpty) (-1,-1000000)
    else if (depth > 0) moves.take(3).map(m => (m, bestMove(board.move(m,coin),
       coin.opposite, depth-1)._2)).sortBy(_._2).head
    else (moves.head, eval(board.move(moves.head, coin), coin))
  }

  def eval(board: Board, coin: Coin):Int = if (coin == Cross) eval(board) else -eval(board)

  def eval(board: Board):Int =
    countPattern(board, Cross).map(evalTable(_)).sum -
    countPattern(board, Naught).map(evalTable(_)).sum

  def evalTable(value: Int) = value match {
    case 4 => 100000
    case 3 => 500
    case 2 => 1
    case _ => 0
  }

  def countPattern(board: Board, coin: Coin) = {
    val rows = for(y <- 0 to 5; x <- 0 to 3) yield List(board(x, y), board(x+1,y), board(x+2,y), board(x+3,y))
    val cols = for(x <- 0 to 6; y <- 0 to 2) yield List(board(x, y), board(x,y+1), board(x,y+2), board(x,y+3))
    val dia1 = for(x <- 0 to 3; y <- 0 to 2) yield List(board(x, y), board(x+1,y+1), board(x+2,y+2), board(x+3,y+3))
    val dia2 = for(x <- 3 to 6; y <- 0 to 2) yield List(board(x, y), board(x-1,y+1), board(x-2,y+2), board(x-3,y+3))
    (rows ++ cols ++ dia1 ++ dia2).map(
      list => if(list.contains(Some(coin.opposite))) 0
              else list.count(_ == Some(coin)))
  }
}

Alle gängigen Algorithmen für solche Spiele beinhalten zwei Funktionen: Eine zum Bewerten einer gegebenen Stellung, und eine zum Vorausberechnung des Stellungsbaums, die dabei auf die erste Funktion zurückgreift. Dabei unterscheiden sich die verschiedenen Versionen darin, welche Züge in welcher Reihenfolge und in welcher Tiefe weiterverfolgt werden, aber das Grundprinzip ist immer gleich: Suche deinen besten Zug unter der Annahme, dass auch dein Gegner immer seinen besten Zug macht.

Bei mir heißt die Bewertungsfunktion eval. Ich habe sie extrem simpel gehalten: Sie zählt einfach, wie oft Muster mit zwei bis vier Steinen eines Spielers (natürlich ohne störende Steine des Gegners) vorkommen und bewertet sie dann. Ein Dreier-Muster ist viel mehr wert als ein Zweier-Muster, und ein Vierer hat einen astronomisch hohen Wert, schließlich gewinnt dieser das Spiel. Das Zählen der Muster wird in countPattern vorgenommen. Natürlich könnten bessere Bewertungs-Faktoren oder eine Einbeziehung der Position des Musters das Programm sicher stark verbessern. Aber gie Güte der Bewertungsfunktion ist eigentlich gar nicht so furchtbar entscheidend, sondern ihre Schnelligkeit: Je schneller eine Stellung bewertet werden kann, um so mehr Züge kann ich untersuchen.

Die Methode bestMove übernimmt die Suche. Zuerst suche ich alle gültigen Züge. Die seltsame Folge 3,4,2… soll dabei bewirken, dass ganz am Anfang die mittleren Felder ein wenig bevorzugt werden. Dann schaue ich nach, ob ich mit einem Zug gewinnen kann. Falls nicht, ordne ich alle Züge mit der Bewertungsfunktion und untersuche nur die “vorläufig besten” drei (nach Meinung von eval) weiter, und nehme den, der dann beim “Tieferbohren” durch rekursiven Aufruf von bestMove den besten Wert erhält. Natürlich muss die Rekursion irgenwann abbrechen: In diesem Fall nehme ich einfach den vorläufig besten. Alle Werte habe ich pi-mal-Daumen genommen, schließlich soll man auch eine Gewinn-Chance haben.

An den anderen Dateien habe ich auch etwas gebastelt. Dummerweise kann ich hier keine Archiv-Dateien anhängen, deshalb poste ich den gesamten Code am Stück. Ich weiß, dass das keine so tolle Lösung ist, aber anders geht es momentan leider nicht.

package connectfour

sealed abstract class Coin(override val toString: String) {
   def opposite = this match {
     case Naught => Cross
     case Cross => Naught
   }
}
case object Naught extends Coin("O")
case object Cross extends Coin("X")

class Board private(data: Map[(Int, Int), Coin]) {

  //HashMap wirft in SwingIO völlig unerklärlich eine Exception, 
  //deshalb habe ich hier eine TreeMap genommen
  def this() = this(scala.collection.immutable.TreeMap[(Int,Int), Coin]())

  def move(x: Int, coin: Coin) = {
    val y = (5 to 0 by -1).find(apply(x, _) == None).getOrElse(error("full"))
    new Board(data + ((x,y) -> coin))
  }

  def apply(x: Int, y: Int): Option[Coin] = data.get((x,y))

  override def toString = {
    val sb = new StringBuilder
    for(y <- 0 to 5; x <- 0 to 6)
      sb.append(apply(x, y).getOrElse(".")).append(if (x == 6) "\n" else "|")
    sb.append("0 1 2 3 4 5 6\n").toString
  }

  lazy val isFull = (0 to 6).forall(apply(_, 0) != None)

  lazy val winner: Option[Coin] = {
    val rows = for(y <- 0 to 5) yield for(x <- 0 to 6) yield apply(x, y)
    val cols = for(x <- 0 to 6) yield for(y <- 0 to 5) yield apply(x, y)
    val dia1 = for(x <- -2 to 3) yield for(y <- 0 to 5) yield apply(x+y, y)
    val dia2 = for(x <- 3 to 8 ) yield for(y <- 0 to 5) yield apply(x-y, y)
    val list = rows ++ cols ++ dia1 ++ dia2
    List(Cross, Naught).find{ c =>
      val slice = List.fill(4)(Some(c))
      list.exists(_.containsSlice(slice))
    }
  }
}

object ConnectFour {

  def apply(io:IO) {
    def loop(players: Option[(Player, Player)]) {
      val (player1, player2) = players.getOrElse(io.askForPlayers)
      round(player1, player2, io)
      if(io.askKeepPlaying) {
        loop(if (io.askKeepPlayers) Some(player2, player1) else None)
      } else {
        io.exit()
      }
    }
    loop(None)
  }

  def round(player1: Player, player2: Player, io:IO) {

    def play(board: Board, player: Player) {
      val coin = if (player == player1) Cross else Naught
      io.showBoard(board)
      if(board.winner != None) io.announceWinner(
        if (board.winner.get == Cross) player1 else player2, board.winner.get)
      else if (board.isFull) io.announceDraw()
      else {
        io.announceMove(player, coin)
        player.move(board, coin, io) match {
          case None => io.announceResign(player, coin)
          case Some(b) => play(b, if(player == player1) player2 else player1)
        }
      }
    }

    play(new Board(), player1)
  }
}

trait IO {
  def showBoard(board: Board): Unit
  def announceWinner(player: Player, coin: Coin): Unit
  def announceDraw(): Unit
  def announceResign(player: Player, coin: Coin): Unit
  def announceMove(player: Player, coin: Coin): Unit
  def askForHumanMove(board: Board): Option[Int]
  def askForPlayers: (Player, Player)
  def askKeepPlaying: Boolean
  def askKeepPlayers: Boolean
  def exit(): Unit
}

case object ConsoleIO extends IO {

  import Console._

  def showBoard(board: Board) {
    println(board)
    println
  }
  def announceWinner(player: Player, coin: Coin) {
    println("The winner is " + player + " (" + coin + ")")
  }
  def announceDraw() {
    println("Board is full, draw.")
  }
  def announceResign(player: Player, coin: Coin) {
    println("Player " + player + " (" + coin + ") gives up.")
  }
  def announceMove(player: Player, coin: Coin) {
    println(player + "'s move (" + coin + ")")
  }

  private val scanner = new java.util.Scanner(System.in)

  def askForHumanMove(board: Board): Option[Int] = {
    var m = -1
    var giveup = false
    do {
      println("Your move ('q' for resign)?")
      try {
        val s = scanner.next
        if(s == "q") giveup = true else m = Integer.parseInt(s)
      } catch {
        case _ =>
      }
    } while(!giveup && (m < 0 || m >= 7 || board(m, 0) != None))
    if(giveup) None else Some(m)
  }

  def askKeepPlaying = {
    var s = ""
    do {
      println("Play again (y/n)?")
      s = scanner.next.toLowerCase
    } while(s != "y" && s != "n")
    s == "y"
  }

  def askKeepPlayers = {
    var s = ""
    do {
      println("Keep players (y/n)?")
      s = scanner.next.toLowerCase
    } while(s != "y" && s != "n")
    s == "y"
  }

  def askForPlayers: (Player, Player) = {
    def ask(number: String): Player = {
      var s = ""
      do {
        println("Is the " + number + " player human or computer (h/c)?")
        s = scanner.next.toLowerCase
      } while(s != "h" && s != "c")
      if(s == "c") {
        println("Please enter the name of the " + number + " player:")
        AI(scanner.next)
      } else {
        println("Please enter the name of the " + number + " player:")
        Human(scanner.next)
      }
    }
    return (ask("first"), ask("second"))
  }

  def exit() { /* do nothing */ }
}

case object SwingIO extends IO {

  import scala.swing._
  import scala.swing.event._
  import scala.swing.Swing._

  val frame = new MainFrame {
    title = "Connect Four"
    size = new java.awt.Dimension(500, 400)
    location = new java.awt.Point(50, 50)
    visible = true

    val messageLabel = new Label("Welcome to Connect Four!")
    val connectFourPanel =   new GridPanel(6,7) {
      var board = new Board()
      for(y <- 0 to 5; x <- 0 to 6) contents += new CoinComp(x, y)

      class CoinComp(x: Int, y: Int) extends Component {
        preferredSize = new Dimension(80, 80)

        import java.awt.Color._
        border = LineBorder(BLACK)
        override def paintComponent(g: Graphics2D) {
          g.setRenderingHint(java.awt.RenderingHints.KEY_ANTIALIASING,
                             java.awt.RenderingHints.VALUE_ANTIALIAS_ON)
          g.setColor(GRAY)
          g.fillRect(0, 0, size.width - 1, size.height - 1)
          g.setColor{board(x, y) match {
              case None => WHITE.darker
              case Some(Naught) => ORANGE
              case Some(Cross) => RED.darker
            }}
          val delta = size.width / 7
          g.fillOval(delta, delta, size.width - 2*delta, size.height - 2*delta)
          g.setColor(BLACK)
          g.drawOval(delta, delta, size.width - 2*delta, size.height - 2*delta)
        }
      }
    }
    val moveButtons = (1 to 7).map(n => new Button(n.toString){ enabled = false }).toList
    moveButtons.foreach(listenTo(_))
    val resignButton = new Button("Resign"){ enabled = false }
    listenTo(resignButton)

    val mainPanel = new BorderPanel {
      import BorderPanel.Position._
      layout += new BoxPanel(scala.swing.Orientation.Horizontal){
        contents += HStrut(5)
        contents += messageLabel
        contents += HGlue
        contents += resignButton
      } -> North
      layout += connectFourPanel -> Center
      layout += new GridPanel(1,7) { moveButtons.foreach(contents += _) } ->  South
    }
    contents = mainPanel

    val clickedButton = new scala.concurrent.SyncVar[AbstractButton]

    reactions += {
      case ButtonClicked(b) => clickedButton.set(b)
    }

    def updateBoard(board :Board) {
      connectFourPanel.board = board
      connectFourPanel.repaint
    }

    def setButtonsEnabled(value: Boolean):Unit = {
      moveButtons.foreach(_.enabled = value)
      resignButton.enabled = value
    }
  }

  private def coinToColor(coin: Coin) = if(coin == Cross) "red" else "yellow"

  def showBoard(board: Board) { frame.updateBoard(board) }

  def announceWinner(player: Player, coin: Coin) {
    frame.messageLabel.text = "The winner is " + player
    Dialog.showMessage(frame.mainPanel , "The winner is " + player + " (" +
                       coinToColor(coin) + ")!", "Congratulations", Dialog.Message.Info)
  }
  def announceDraw() {
    frame.messageLabel.text = "Board is full, draw."
  }
  def announceResign(player: Player, coin: Coin) {
    frame.messageLabel.text = "Player " + player + " gives up."
    Dialog.showMessage(frame.mainPanel , "Player " + player + " (" +
                       coinToColor(coin) + ") gives up.", "Resign", Dialog.Message.Info)
  }
  def announceMove(player: Player, coin: Coin) {
    frame.messageLabel.text = player + "'s move (" + coinToColor(coin) + ")"
  }

  def askForHumanMove(board: Board): Option[Int] = {
    frame.setButtonsEnabled(true)
    var r = Int.MinValue
    do {
      val button = frame.clickedButton.take
      if(button == frame.resignButton) r = Int.MaxValue else {
        val i = frame.moveButtons.indexOf(button)
        if (board(i, 0) == None) r = i
      }
    } while (r == Int.MinValue)
    frame.setButtonsEnabled(false)
    if(r == Int.MaxValue) None else Some(r)
  }

  def askKeepPlaying = Dialog.Result.Yes == Dialog.showConfirmation(
    frame.mainPanel, "Play again?", "Question", Dialog.Options.YesNo, Dialog.Message.Question)

  def askKeepPlayers = Dialog.Result.Yes == Dialog.showConfirmation(
    frame.mainPanel, "Keep players?", "Question", Dialog.Options.YesNo, Dialog.Message.Question)

  def askForPlayers: (Player, Player) = {
    val panel = new BoxPanel(Orientation.Vertical) {
      val name1 = new TextField("Adam")
      val human1 = new CheckBox("human")
      human1.selected = true
      val name2 = new TextField("Eve")
      val human2 = new CheckBox("human")
      human2.selected = true
      contents += new Label("Player 1:")
      contents += name1
      contents += human1
      contents += VStrut(10)
      contents += new Label("Player 2:")
      contents += name2
      contents += human2
    }
    Dialog.showMessage(frame.mainPanel , panel.peer, "Select Players", Dialog.Message.Plain)
    val player1 = if(panel.human1.selected) Human(if(panel.name1.text == "") "Adam" else panel.name1.text)
    else AI((if(panel.name1.text == "") "HAL" else panel.name1.text))
    val player2 = if(panel.human2.selected) Human(if(panel.name2.text == "") "Eve" else panel.name2.text)
    else AI((if(panel.name2.text == "") "R2D2" else panel.name2.text))
    return (player1, player2)
  }

  def exit() {
    frame.close()
    System.exit(0)
  }
}

trait Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board]
}

case class Human(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = 
    io.askForHumanMove(board).map(board.move(_, coin))
}

case class AI(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = {
    Some(board.move(bestMove(board, coin, 5)._1, coin))
  }

  def bestMove(board: Board, coin: Coin, depth: Int): (Int, Int) = {
    val moveList =  List(3,4,2,5,1,6,0).filter(board(_, 0) == None)
    moveList.foreach(m => if (board.move(m, coin).winner == Some(coin)) return (m,1000000))
    val moves = moveList.sortBy(m => -eval(board.move(m, coin), coin))
    if (moves.isEmpty) (-1,-1000000)
    else if (depth > 0) moves.take(3).map(m => (m, bestMove(board.move(m,coin),
       coin.opposite, depth-1)._2)).sortBy(_._2).head
    else (moves.head, eval(board.move(moves.head, coin), coin))
  }

  def eval(board: Board, coin: Coin):Int = if (coin == Cross) eval(board) else -eval(board)

  def eval(board: Board):Int =
    countPattern(board, Cross).map(evalTable(_)).sum -
    countPattern(board, Naught).map(evalTable(_)).sum

  def evalTable(value: Int) = value match {
    case 4 => 100000
    case 3 => 500
    case 2 => 1
    case _ => 0
  }

  def countPattern(board: Board, coin: Coin) = {
    val rows = for(y <- 0 to 5; x <- 0 to 3) yield List(board(x, y), board(x+1,y), board(x+2,y), board(x+3,y))
    val cols = for(x <- 0 to 6; y <- 0 to 2) yield List(board(x, y), board(x,y+1), board(x,y+2), board(x,y+3))
    val dia1 = for(x <- 0 to 3; y <- 0 to 2) yield List(board(x, y), board(x+1,y+1), board(x+2,y+2), board(x+3,y+3))
    val dia2 = for(x <- 3 to 6; y <- 0 to 2) yield List(board(x, y), board(x-1,y+1), board(x-2,y+2), board(x-3,y+3))
    (rows ++ cols ++ dia1 ++ dia2).map(
      list => if(list.contains(Some(coin.opposite))) 0
              else list.count(_ == Some(coin)))
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    ConnectFour(SwingIO)
  }
}

So, das wars für heute. Drückt mir bitte die Daumen für einen vulkanaschewolkenverzögerungsfreien Rückflug!

RC2 für Netbeans-Plugin

Der Release Candidate 2 für das Netbeans Scala Plugin ist da, und funktioniert bei mir bisher prima. Dankeschön an Christian für die Info, und natürlich an den fleißigen Plugin-Autor Caoyuan!

Bin schon wieder weg…

… und zwar für die nächsten zwei Wochen, diesmal beruflich. Zur Überbrückung empfehle ich Daily Scala.

Interview with Matt Hicks

So, I’m back from my vacation, and I’m really happy to see that the blog traffic didn’t drop below zero.

Don’t panic, escalation will stay a German language blog, today is just a little exception. The reason is that Matt Hicks was so kind to give me an interview about his Sgine project, a 3D game engine written in Scala.

Matt (a.k.a. darkfrog) initiated a lot of other interesting open source projects, e.g. Java Game Networking and jSeamless”, and is a long time contributor to the popular jMonkeyEngine (written in Java). Here is the interview (all links except to TestImage were inserted by me):

What are the main reasons for starting the Sgine project, instead of contributing e.g. to JME 2 or 3? What are the differences concerning design and features?

There are several reasons. I was a developer on jME and jME-Physics for years and have used Xith, Java3D, and others but never have really been happy with the architecture of the engine. Simple things are either overly complicated, or hide too much complexity by “SimpleXxx” wrappers. The barrier to entry and internal knowledge requirement of both OpenGL and the scenegraph itself is quite overwhelming and complicated. I wanted to create an elegant architecture that supported multi-threading and is easy and logical to use for simple and complex development. For example, I recently spent some time playing with Ardor3D which is arguably the best 3D engine for Java from a classical design perspective available. To just create a simple test class that renders a quad to the screen with a picture on it to 130 lines of code. That’s a pretty significant effort in order to just get an image to display. Now, sgine is still early in development, but a similar display of just an image on the screen takes a total of 22 lines of code (only six of those actual logic): TestImage.scala

How important is the Scala language for the project? If Scala wouldn’t exist, do you think you would have started a similar project in Java instead?

Long before I even knew about Scala I began to become discontent with the limitations Java imposed upon me and began creating extensions like MagicBeans (provided field binding, change listening, etc.), Delegates (a reflection-based functional programming concept), and Properties (abstraction from getters/setters) to name a few. When I first began learning Scala it was like a breath of fresh air. It opened the doors to many things I have been trying to accomplish in Java and many more that I hadn’t even considered. The deeper I get into the development of sgine the more I realize how powerful a language Scala is for this chosen task.

I had started a less ambitious project called jSeamless a few years ago. The sgine project is the successor to that. While jSeamless sought specifically to solve user-interface needs sgine has expanded greatly in order to provide a complete graphical engine may encompass a great deal more. To answer your question, yes I would still have the desire to complete this task without Scala, but I doubt I would really have the ability.

Which role plays Scala’s functional side? Is the functional part just “nice to have” or is it a crucial part of the engine design?

Though the functional model is extremely beneficial I would not go so far as to say sgine would be a failure without it. I will say that I heavily rely on functional coding where it makes sense though and believe the engine is the better for it.

Are you satisfied with the current development speed? When do you you expect version 1.0?

For the past few months development has slowed considerably, but over the past week the project has picked up speed drastically. For quite a while I’ve been trying different rendering methods and was ultimately dissatisfied with each route I had taken. Finally I have settled on a path to move forward and move forward I have done at a considerable pace since that decision was reached.

How was the feedback so far? How is the community developing?

Well, the tact I generally take with a new project is to sort of stay under the radar until I’m really ready to show it off. To that extent the exposure has been quite minimal. I was invited to speak at Scala Days but the cost for (coming from America to Switzerland) and limited audience I decided against it. I would love additional support, but apart from a couple people helping I’ve pretty much run this show alone so far. It is a really hard sell to convince good developers to join a project that hasn’t got a lot to show for itself yet. Additionally, finding decent programmers that know both Scala and OpenGL is quite difficult I am finding.

As far as I know Sgine is the first 3D game engine written in Scala. Do you expect other Scala 3D engine projects soon?

I expect that there will be more coming on the scene within the next year, but hopefully if sgine fulfills its potential I hope most people will just choose to join and help out with it.

Which of Scala features were the most useful ones so far? And which feature currently missing in Scala would be the most useful?

I have been a huge advocate of Java for years, but Scala has turned me against it. I love Scala and regret every line of code I still have to write in Java. However, there are still many things that need to be done in the Scala language. Two main things I’m dealing with right now are Enumerations and disparation between Function and Method (specifically in equality).

While Scala isn’t “slow”, careless programming can lead easily to bottelnecks. How were your experiences with Scala performance so far?

This is definitely something I have learned a lot about in sgine. I constantly turn on verbose:gc to verify I’m not creating lots of garbage in tight loops. Specifically anonymous functions are so easy to create it’s easy to inject them into a place that just causes millions of tiny objects to be created per second. I had a lot of problems with this early on, but have learned many ways to avoid garbage creation while maintaining good functional coding.

What contributions from the community would you like to see?

While I’ve got a lot of experience architecting good frameworks and have a lot of great ideas and good programming knowledge I still need a great deal of help in the area specific to OpenGL and complex math. The project would do well to have a few seasoned professional OpenGL programmers on board, but at the moment I wouldn’t complain for any assistance I can get. The task of sgine is a daunting one for a single developer to try to manage.

Where do you see Java, Scala and Sgine in 5 years?

I see Java as a language decreasing significantly and Scala increasing for serious developers. I don’t really know where sgine will be, but I truly hope it catches on. I believe in the idea of the project, but an open-source project has little hope of success in the long-term if only its creator believes in it.

In game development Java got never as popular as in many other areas. Do you think Scala could do much better there?

I think so. Java has very little market-share even though there are significant benefits to using it over a language like C++. Those benefits are increased several fold with Scala and I believe that serious developers will hopefully agree.

Is there a good question I forgot to ask?

I don’t think so.

Thank you for the very interesting interview!