minimax algorithm with alpha-beta pruning

SimpleMinimax.scala

package fr.greweb.ai

import scala.annotation.tailrec

object SimpleMinimax {

  type Score = Double

  // First impl of minimax, no track of the path
  trait Node {

    def getChildren: Iterable[Node] // All possible next states
    def isLeaf: Boolean // when game is finished
    def maximizing: Boolean // true for the player, false for opponents

    def utility: Score // The ultimate score for the leaf (you just need to score if you win or lose)
    def eval: Score // An estimation of the score when pruning
    def cutoff(depth: Int): Boolean // A function which says if we should continue to explore for a given depth

    // Compute the score value according to minimax algorithm
    def score: Score = value(0, Double.MinValue, Double.MaxValue)

    // first call: value(0, -inf, +inf)
    // alpha: best value for MAX
    // beta: best value for MIN
    def value (depth: Int, alpha: Score, beta: Score): Score = {
      if (isLeaf)
        utility
      else if (cutoff(depth))
        eval
      else if (maximizing)
        maxValue(depth, alpha, beta)
      else
        minValue(depth, alpha, beta)
    }

    def maxValue (depth: Int, alpha: Score, beta: Score): Score = {
      @tailrec
      def rec (list: Iterable[Node], alpha: Score): Score = {
        if (list.isEmpty) alpha
        else {
          val alph = math.max(alpha, list.head.value(depth+1, alpha, beta))
          if (beta <= alph) alph
          else rec(list.tail, alph)
        }
      }
      rec(getChildren, alpha)
    }

    def minValue (depth: Int, alpha: Score, beta: Score): Score = {
      @tailrec
      def rec (list: Iterable[Node], beta: Score): Score = {
        if (list.isEmpty) beta
        else {
          val bet = math.min(beta, list.head.value(depth+1, alpha, beta))
          if (bet <= alpha) bet
          else rec(list.tail, bet)
        }
      }
      rec(getChildren, beta)
    }
  }
}