Playing abstract strategy games in general

Strategy.scala

/** Game rules for state space S and players in P */
trait GameRules[S, P] {
    /** Score a position relative to a player. That is, a better
        position should have a bigger score than a worse one. */
    def children(position: S): List[S]
    def turn(position: S): P // Whose turn is it on some position?
}

/** Scores positions for a Strategy. R should have a total ordering (see the
  * signature of pickMove below) and should be positive if the given player has
  * an advantage.
  */
trait GameOracle[S, R, P] {
    def score(player: P, position: S): R
}

sealed trait NonEmptyList[A] {
    def fold[R](singleton: A => R, cons: (A, R) => R): R
    def map[B](f: A => B): NonEmptyList[B] = fold(head => Singleton[B](f(head)),
        (head: A, tail: NonEmptyList[B]) => Cons[B](f(head), tail))
    def maxBy[B](f: A => B)(implicit ord: Ordering[B]): A =
        map[(A, B)](x => (x, f(x))).fold[(A, B)](x => x, {
            case ((a1, b1), (a2, b2)) => if(ord.compare(b1, b2) > 0) (a1, b1) else (a2, b2)
        })._1

}

object NonEmptyListUtils {
    def fromList[A](l: List[A]): Option[NonEmptyList[A]] =
        l.foldRight[Option[NonEmptyList[A]]](None)({
            case (head, None) => Some(Singleton(head))
            case (head, Some(tail)) => Some(Cons(head, tail))
        })
}

case class Singleton[A](head: A) extends NonEmptyList[A] {
    def fold[R](singleton: A => R, cons: (A, R) => R): R = singleton(head)
}
case class Cons[A](head: A, tail: NonEmptyList[A]) extends NonEmptyList[A] {
    def fold[R](singleton: A => R, cons: (A, R) => R): R =
        cons(head, tail.fold(singleton, cons))
}

/** Strategy over a state space S with scores in R and players in P */
trait Strategy[S, R, P] {
    /** Universally quantified in M, so that the only possible return
      * values are elements of the candidates list */
    def pickMove[M](rules: GameRules[S, P], oracle: GameOracle[S, R, P],
                    ord: Ordering[R], position: S, update: M => S,
                    candidates: NonEmptyList[M]): M
}

object TicTacToe {
    sealed trait Player
    case object Nought extends Player
    case object Cross  extends Player

    sealed trait Cell
    case object Empty extends Cell
    case class Full(p: Player) extends Cell

    case class State(arr: Array[Cell], player: Player)

    object TicTacToeRules extends GameRules[State, Player] {
        def toIndex(row: Int, col: Int) = 3 * row + col
        private def toggle(p: Player): Player = p match {
            case Cross => Nought
            case Nought => Cross
        }

        private val coords = 0 until 3

        def hasWon(p: Player, position: State): Boolean =
            coords.exists(row =>
                coords.forall(col =>
                    position.arr(toIndex(row, col)) == Full(p))) ||
            coords.exists(col =>
                coords.forall(row =>
                    position.arr(toIndex(row, col)) == Full(p))) ||
            coords.forall(row =>
                position.arr(toIndex(row, row)) == Full(p)) ||
            coords.forall(row =>
                position.arr(toIndex(row, 2 - row)) == Full(p))

        def legalMoves(position: State): List[(Int, Int)] = {
            if(hasWon(Nought, position) || hasWon(Cross, position)) List()
            else {
                val coordPairs = coords.flatMap(row =>
                        coords.flatMap(col => List((row, col)))).toList

                coordPairs.filter({
                    case (row, col) => position.arr(toIndex(row, col)) == Empty
                })
            }
        }

        def children(position: State): List[State] =
            legalMoves(position).map(update(_)(position))

        /**
          * Updates a game state with a move in a potentially unsafe way.
          * This should only be called on one of the outputs of legalMoves
          */
        def update(move: (Int, Int))(position: State): State = {
            val newArr = position.arr.clone()
            val (i, j) = move
            newArr(toIndex(i, j)) = Full(position.player)
            State(newArr, toggle(position.player))
        }

        def turn(position: State): Player = position match {
            case State(_, p) => p
        }
    }

    object TicTacToeOracle extends GameOracle[State, Int, Player] {
        def score(player: Player, position: State): Int = {
             val noughtWon = TicTacToeRules.hasWon(Nought, position)
             val crossWon  = TicTacToeRules.hasWon(Cross, position)

             player match {
                case Nought if noughtWon => 1
                case Nought if crossWon => -1
                case Cross if noughtWon => -1
                case Cross if crossWon => 1
                case _ => 0
             }
        }
    }

    object Util {
        def printState(state: State) {
            val State(arr, _) = state
            val coords = 0 until 3
            coords.foreach(i => {
                coords.foreach(j =>
                    print(arr(TicTacToeRules.toIndex(i, j)) match {
                        case Full(Cross) => "X"
                        case Full(Nought) => "O"
                        case Empty => "_"
                    }))

                println()
            })
        }
    }
}

case class MinimaxStrategy[S, R, P](searchDepth: Int) extends Strategy[S, R, P] {
    def pickMove[M](rules: GameRules[S, P], oracle: GameOracle[S, R, P],
                    ord: Ordering[R], position: S, translate: M => S,
                    candidates: NonEmptyList[M]): M = {
        val me = rules.turn(position)
        implicit val ordering = ord
        
        def scoreByDepth(pos: S, depth: Int): R =
            if(depth < 1) oracle.score(me, pos)
            else {
                val subscores = rules.children(pos).map(scoreByDepth(_, depth - 1))
                // If there are no legal moves from here, return the score
                // as it stands
                if(subscores.isEmpty) oracle.score(me, pos)
                // If it's my turn, I will choose the subtree that maximizes my score
                else if(rules.turn(pos) == me) subscores.maxBy[R](x => x)
                // If it's their turn, they will choose the subtree that minimizes my score
                else subscores.minBy[R](x => x)
            }
        
        val scoredMoves = candidates.map(move => (move, scoreByDepth(translate(move), searchDepth - 1)))

        scoredMoves.maxBy[R]({case (move, score) => score})._1
    }
}

/**
  * Demonstrates perfect play for a game of Tic-Tac-Toe
  */
object TicTacToeExample {
    def play(state: TicTacToe.State) {
        val strategy = MinimaxStrategy[TicTacToe.State, Int, TicTacToe.Player](9)

        object IntOrdering extends Ordering[Int] {
            def compare(a: Int, b: Int): Int = a - b
        }

        TicTacToe.Util.printState(state)
        println("-------------------")

        NonEmptyListUtils.fromList(TicTacToe.TicTacToeRules.legalMoves(state)) match {
            case Some(candidates) => {
                val move = strategy.pickMove(TicTacToe.TicTacToeRules,
                                  TicTacToe.TicTacToeOracle,
                                  IntOrdering,
                                  state,
                                  TicTacToe.TicTacToeRules.update(_: (Int, Int))(state),
                                  candidates)
                play(TicTacToe.TicTacToeRules.update(move)(state))
            }
            case _ => {}
        }
    }

    def main(args: Array[String]) {
        // Upcast the empty value to avoid an error when we try to use
        // an Array[Empty] as an Array[Cell].
        val empty = TicTacToe.Empty.asInstanceOf[TicTacToe.Cell]
        val nought = TicTacToe.Full(TicTacToe.Nought)
        val cross = TicTacToe.Full(TicTacToe.Cross)

        val array = Array(empty, empty, empty,
                          empty, empty, empty,
                          empty, empty, empty)

        val state = TicTacToe.State(array, TicTacToe.Cross)
        play(state)
    }
}