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.scala3. Play the game by running command
$scala PlayHave Fun :-)
****************************
I've played it with Scala version 2.7.6.final (Java HotSpot(TM) Server VM, Java 1.6.0_14).
