## Tuesday, January 26, 2010

### 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 representationabstract 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 representationabstract 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 Gameclass 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-Loopimport java.io.InputStreamReaderobject 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).

#### 1 comment:

1. your game is not fucking working