Minimax with Alpha-beta Pruning

AlphaBetaImperative.scala

class AlphaBetaImperative extends Evaluator {

  override def evaluate(tree: Tree): Int = alphabeta(tree, Int.MinValue, Int.MaxValue, true)

  def alphabeta(tree: Tree, alpha: Int, beta: Int, maximizing: Boolean): Int = {
    tree match {
      case leaf @ Leaf(_) => staticEval(leaf)
      case node @ Node(subs) =>
        if (maximizing) {
          var a = alpha
          for (child <- subs) {
            a = Math.max(a, alphabeta(child, a, beta, false))
            if (beta <= a)
              return a // break
          }
          return a
        } else {
          var b = beta
          for (child <- subs) {
            b = Math.min(b, alphabeta(child, alpha, b, true))
            if (b <= alpha)
              return b // break
          }
          return b
        }
    }
  }

}

AlphaBetaWhyFP.scala

class AlphaBetaWhyFP extends Evaluator {

  override def evaluate(tree: Tree): Int = maximize(tree).max

  def maximize(tree: Tree): Stream[Int] = tree match {
    case leaf @ Leaf(score) => Stream(staticEval(leaf))
    case Node(subs) => mapmin(subs.map(minimize))
  }

  def minimize(tree: Tree): Stream[Int] = tree match {
    case leaf @ Leaf(score) => Stream(staticEval(leaf))
    case Node(subs) => mapmax(subs.map(maximize))
  }

  def mapmax(numListList: Stream[Stream[Int]]): Stream[Int] = {
    val pot = numListList.head.max
    Stream.cons(pot, omit2(pot, numListList.tail))
  }

  def mapmin(numListList: Stream[Stream[Int]]): Stream[Int] = {
    val pot = numListList.head.min
    Stream.cons(pot, omit(pot, numListList.tail))
  }

  def omit(pot: Int, numListList: Stream[Stream[Int]]): Stream[Int] = {
    if (numListList.isEmpty)
      empty
    else {
      val nums = numListList.head
      if (minleq(nums, pot))
        omit(pot, numListList.tail)
      else
        Stream.cons(nums.min, omit(nums.min, numListList.tail))
    }
  }
  
  def omit2(pot: Int, numListList: Stream[Stream[Int]]): Stream[Int] = {
    if (numListList.isEmpty)
      empty
    else {
      val nums = numListList.head
      if (maxleq(nums, pot))
        omit2(pot, numListList.tail)
      else
        Stream.cons(nums.max, omit2(nums.max, numListList.tail))
    }
  }

  def minleq(nums: Stream[Int], pot: Int): Boolean = {
    !nums.dropWhile(_ > pot).isEmpty
//    if (nums.isEmpty) {
//      false
//    } else {
//      if (nums.head <= pot) {
//        true
//      } else {
//        minleq(nums.tail, pot)
//      }
//    }
  }
  def maxleq(nums: Stream[Int], pot: Int): Boolean = {
    !nums.dropWhile(_ < pot).isEmpty
//    if (nums.isEmpty) {
//      false
//    } else {
//      if (nums.head >= pot) {
//        true
//      } else {
//        maxleq(nums.tail, pot)
//      }
//    }
  }
}

Evaluator.scala

abstract class Evaluator {
  var counter = 0

  def evaluate(tree: Tree): Int

  def staticEval(leaf: Leaf): Int = {
    //println(leaf.score)
    counter += 1
    leaf.score
  }
}

Main.scala

object Main extends App {
  val m = Node(Stream(12, 11).map(Leaf(_)))
  val l = Node(Stream(9, 10).map(Leaf(_)))
  val k = Node(Stream(8, 9).map(Leaf(_)))
  val j = Leaf(8)
  val i = Node(Stream(6, 5, 7).map(Leaf(_)))
  val h = Node(Stream(10, 12, 13).map(Leaf(_)))
  val g = Node(Stream(k, l, m))
  val f = Node(Stream(13, 14).map(Leaf(_)))
  val e = Node(Stream(8, 9, 10).map(Leaf(_)))
  val d = Node(Stream(9, 12, 11).map(Leaf(_)))
  val c = Node(Stream(5, 6, 7).map(Leaf(_)))
  val b = Node(Stream(g, h, i, j))
  val a = Node(Stream(d, e, f))
  val tree = Node(Stream(a, b, c))

  test(new AlphaBetaImperative)
  test(new AlphaBetaWhyFP)

  def test(evaluator: Evaluator) {
    val score = evaluator.evaluate(tree)
    println(evaluator.getClass.getName + ": " + score)
    println("visited leaf nodes: " + evaluator.counter)
  }
}

result.txt

9
12
11
8
9
10
13
8
9
12
11
10
12
6
5
7
5
AlphaBetaImperative: 10
visited leaf nodes: 17
9
12
11
8
9
10
13
8
9
9
10
12
11
10
12
6
5
7
5
AlphaBetaWhyFP: 10
visited leaf nodes: 19

Tree.scala

abstract class Tree
case class Node(subs: Stream[Tree]) extends Tree
case class Leaf(score: Int) extends Tree