An Unbeatable Tic-Tac-Toe (in Scala)

I'm reading AIMA-3e, implemented the AlphaBetaSearch from ch-5 on Adversarial Search. I thought it would be cool to create an actual game, so I wrote a TicTacToe implementation for the game and a game-loop to play it. You can find the code here. If you want to understand the implementation, you know what to read :P.

/** The *Unbeatable* Tic-Tac-Toe game implementation.
 *
 * Save this script in a file xyz.scala in a directory.
 * Compile it with scalac: $scalac xyz.scala
 * Play the game with scala: $scala Play
 * 
 * @author Himanshu Gupta
 */

/* A Search algorithm to find the best move
 * given current state of the game
 */
object AlphaBetaSearch {
  def apply[S,A](state: S, game: ZeroSumGame[S,A]): A = {
    val actionMinvalPairs = game.actions(state).map((a) => 
                                  (a,MinValue(game.result(state,a),Math.MIN_DOUBLE,Math.MAX_DOUBLE,game)))
    //sort the pairs in descending order of MinValue
    val sorted = actionMinvalPairs.sort(_._2 > _._2)
    //take the pairs with highest MinValue(they can be more than 1 also)
    val bestPairs = sorted.takeWhile(sorted.head._2 == _._2)
    //chose randomly one from the best
    bestPairs(new scala.util.Random(new java.util.Random).nextInt(bestPairs.length))._1
  }

  private def MaxValue[S,A](state: S, alpha: Double,beta: Double, game: ZeroSumGame[S,A]): Double =
    if (game.terminalTest(state)) game.utility(state)
    else {
      def loop(states: List[S], v: Double, alpha: Double): Double =
        states match {
          case s :: rest => {
            val tmp = Math.max(v,MinValue(s,alpha,beta,game))
            if(tmp >= beta) tmp
            else loop(rest, tmp, Math.max(alpha,tmp))
          }
          case Nil => v
        }

      loop(game.actions(state).map(game.result(state,_)),Math.MIN_DOUBLE,alpha)
    }

  private def MinValue[S,A](state: S, alpha: Double, beta: Double, game: ZeroSumGame[S,A]): Double =
    if (game.terminalTest(state)) game.utility(state)
    else {
      def loop(states: List[S], v: Double, beta: Double): Double =
        states match {
          case s :: rest => {
            val tmp = Math.min(v,MaxValue(s,alpha,beta,game))
            if(tmp <= alpha) tmp
            else loop(rest, tmp, Math.min(beta,tmp))
          }
          case Nil => v
        }

      loop(game.actions(state).map(game.result(state,_)),Math.MAX_DOUBLE,beta)
    }
}

//abstract game representation
abstract class Game[P,S,A] {
  def initialState: S
  def player(s: S): P
  def actions(s: S): List[A]
  def result(s: S, a: A): S
  def terminalTest(s: S): Boolean
  def utility(s: S, p: P): Double
}

//abstract Two-player game representation
abstract class ZeroSumGame[S,A] extends Game[String,S,A] {

  //In two-player, zero-sum games, the two element vector
  //can be reduced to a single value because the values
  //are always opposite
  // -- described in Section 5.2.2
  override def utility(s: S, p: String) = utility(s)
  def utility(s: S): Double
}
object ZeroSumGame {
  val Min = "MIN"
  val Max = "MAX"
}

//Tic-Tac-Toe implementation of Two-Player Game
class TicTacToeGame extends ZeroSumGame[(String,Array[Array[Char]]),(Int,Int)] {

  type Board = Array[Array[Char]]
  type State = (String,Board)
  type Action = (Int,Int)

  private val X = 'X'
  private val O = 'O'
  private val nullChar: Char = 0

  def initialState = (ZeroSumGame.Max,new Array[Array[Char]](3,3))

  def player(s: State) = s._1

  def actions(s: State) = {
    (for(x <- 0 to 2;
         y <- 0 to 2;
         if s._2(x)(y) == nullChar) yield (x,y)).toList
  }

  def result(s: State, a: Action) =
    s match {
      case (ZeroSumGame.Max, board) =>
        if(board(a._1)(a._2) == nullChar) {
          val newBoard = cloneBoard(board)
          newBoard(a._1)(a._2) = X
          (ZeroSumGame.Min, newBoard)
        }
        else throw new IllegalStateException("Box at " + a + " is already filled.")
      case (ZeroSumGame.Min, board) =>
        if(board(a._1)(a._2) == nullChar) {
          val newBoard = cloneBoard(board)
          newBoard(a._1)(a._2) = O
          (ZeroSumGame.Max, newBoard)
        }
        else throw new IllegalStateException("Box at " + a + " is already filled.")
      case _ => throw new IllegalStateException("Not a valid player " + s._1)
    }

  def terminalTest(s: State) =
    getWinner(s._2) match {
      case Some(_) => true
      case None => actions(s).length == 0
    }

  def utility(s: State): Double =
    getWinner(s._2) match {
      case Some(ZeroSumGame.Max) => 1.0
      case Some(ZeroSumGame.Min) => -1.0
      case None if actions(s).length == 0 => 0.5
      case _ => throw new IllegalStateException("Not a terminal state." + toString(s))
    }
      
  def toString(state: State) = {
    val board = state._2
    var result = ""
    for(y <- 2.until(-1,-1); x <- 0 to 2) {
      result = result + (if(board(x)(y) == nullChar) "-" else board(x)(y))
      if(x == 2) result = result + "\n"
    }
    result
  }

  //Returns the winner if game has terminated without draw,
  //None otherwise
  private def getWinner(board: Board): Option[String] = {
    (for( x <- 0 to 2; y <- 0 to 2) yield board(x)(y)).toList match {
      //the for loop results in board charaters at all the
      //co-ordinates in following order
      //((0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2))

      case X :: X :: X :: _ :: _ :: _ :: _ :: _ :: _ :: Nil => Some(ZeroSumGame.Max)
      case _ :: _ :: _ :: X :: X :: X :: _ :: _ :: _ :: Nil => Some(ZeroSumGame.Max)
      case _ :: _ :: _ :: _ :: _ :: _ :: X :: X :: X :: Nil => Some(ZeroSumGame.Max)
      case X :: _ :: _ :: X :: _ :: _ :: X :: _ :: _ :: Nil => Some(ZeroSumGame.Max)
      case _ :: X :: _ :: _ :: X :: _ :: _ :: X :: _ :: Nil => Some(ZeroSumGame.Max)
      case _ :: _ :: X :: _ :: _ :: X :: _ :: _ :: X :: Nil => Some(ZeroSumGame.Max)
      case X :: _ :: _ :: _ :: X :: _ :: _ :: _ :: X :: Nil => Some(ZeroSumGame.Max)
      case _ :: _ :: X :: _ :: X :: _ :: X :: _ :: _ :: Nil => Some(ZeroSumGame.Max)

      case O :: O :: O :: _ :: _ :: _ :: _ :: _ :: _ :: Nil => Some(ZeroSumGame.Min)
      case _ :: _ :: _ :: O :: O :: O :: _ :: _ :: _ :: Nil => Some(ZeroSumGame.Min)
      case _ :: _ :: _ :: _ :: _ :: _ :: O :: O :: O :: Nil => Some(ZeroSumGame.Min)
      case O :: _ :: _ :: O :: _ :: _ :: O :: _ :: _ :: Nil => Some(ZeroSumGame.Min)
      case _ :: O :: _ :: _ :: O :: _ :: _ :: O :: _ :: Nil => Some(ZeroSumGame.Min)
      case _ :: _ :: O :: _ :: _ :: O :: _ :: _ :: O :: Nil => Some(ZeroSumGame.Min)
      case O :: _ :: _ :: _ :: O :: _ :: _ :: _ :: O :: Nil => Some(ZeroSumGame.Min)
      case _ :: _ :: O :: _ :: O :: _ :: O :: _ :: _ :: Nil => Some(ZeroSumGame.Min)

      case _ => None
    }
  }
 
  private def cloneBoard(board: Board): Board = {
    val result = new Array[Array[Char]](3,3)
    for(x <- 0 to 2; y <- 0 to 2) {
      result(x)(y) = board(x)(y)
    }
    result
  }
}

//The-Game-Loop
import java.io.InputStreamReader
object Play {

  def main(args: Array[String]) {
    
    println("** Welcome to the *Unbeatable* Tic-Tac-Toe **")
    println("")
    println("*** How To Play ***")
    println("Place an O at the position chosen using its x-y coordinates")
    println("0 <= x,y <= 2")
    println("")
    println("** Let the Game Begin, I place the X first **")

    val game = new TicTacToeGame()
    val initState = game.initialState
    val reader = new InputStreamReader(System.in)

    def loop(state: (String,Array[Array[Char]])) {
      //display current state of the game
      println("")
      println("**************")
      println(game.toString(state))
      println("**************")
      println("")
 
     if(game.terminalTest(state)) {
        game.utility(state) match {
          case 1.0 =>
            println("You LOST the game.")            
          case 0.5 =>
            println("Its a DRAW.")
          case -1.0 =>
            println("You WON the game.")
        }
      }
      else {
        //get input
        println("** Your turn **")
        print("Type x:")
        val x = Character.getNumericValue(reader.read())
        reader.read() //ignore the new-line char
        print("Type y:")
        val y = Character.getNumericValue(reader.read())
        reader.read() //ignore another new-line char

        //validate input
        if(x >= 0 && x <= 2 && y >= 0 && y <= 2) {
          //play
          val nextSt = game.result(state,(x,y))
          loop(game.result(nextSt,AlphaBetaSearch(nextSt,game)))
        }
        else {
          println("Invalid Input, Valid Input is 0 <= x,y <= 2")
          loop(state)
      }
      }
    }

    loop(game.result(initState,AlphaBetaSearch(initState,game)))
  }
}

How to Play:
1. Save the above code in a file, let say TicTacToe.scala in a directory.
2. Compile the code by running command $scalac TicTacToe.scala
3. Play the game by running command $scala Play

Have Fun :-)

****************************
I've played it with Scala version 2.7.6.final (Java HotSpot(TM) Server VM, Java 1.6.0_14).