gistfile1.txt

object icm {
  // Types
  type Player          = Int
  type Chips           = Double
  type Stacks          = Map[Player, Chips]

  type Rank            = Int
  type Money           = Double
  type Payouts         = Map[Rank, Money]

  type Probability     = Double
  type Result          = Map[Player, Map[Rank, Probability]]

  type Ev              = Map[Player, Money]

  // API
  def calculate(stacks : Stacks, payouts : Payouts, algo : Algorithm) : Ev =
    algo(stacks) mapValues (dist => (dist foldLeft 0.0) {
      case (acc, (rank, prob)) =>
        acc + (payouts get rank getOrElse 0.0) * prob
    })

  // Trees
  type Depth = Int

  case class Node(
    player   : Player,
    prob     : Probability = 1.0,
    children : List[Node]  = Nil
  ) {
    def isLeaf = children.isEmpty

    def pp(n : Int) : Unit = {
      println(" " * n + s"${player}: ${prob} ==>")
      children foreach (_ pp (n + 2))
    }

    def depth : Depth =
      if (isLeaf) 1
      else        1 + children.head.depth //balanced
  }

  object Node {
    def run(
      stacks : Stacks,
      dist   : Stacks => Player => Probability,
      update : Stacks => Player => Stacks,
      rank   : Depth  => Rank
    ) : Result =
      tree(stacks, dist, update) |> (equity(_, rank))

    def tree(
      stacks : Stacks,
      dist   : Stacks => Player => Probability,
      update : Stacks => Player => Stacks
    ) : List[Node] =
      if (stacks.size == 1) List(Node(stacks.head._1))
      else {
        val probs = dist(stacks)
        stacks.keys.toList map { player =>
          Node(player, probs(player), tree(update(stacks)(player), dist, update))
        }
      }

    def equity(
      ns   : List[Node],
      rank : Depth => Rank
    ) : Map[Player, Map[Rank, Probability]] =
      equity1(ns, rank) groupBy (_._1) mapValues { xs =>
        xs groupBy (_._3) mapValues { xs =>
          (xs foldLeft 0.0) { _ + _._2 }
        }
      }

    def equity1(
      ns   : List[Node],
      rank : Depth => Rank
    ) : List[(Player, Probability, Rank)] =
      ns flatMap { n =>
        List((n.player, n.prob, rank(n.depth))) ++
        (if (n.isLeaf) Nil
         else equity1(n.children, rank) map (x => (x._1, x._2 * n.prob, x._3)))
      }
  }


  sealed trait Algorithm extends (Stacks => Result)


  case object MalmuthHarville extends Algorithm {
    def apply(s : Stacks) : Result =
      Node.run(
        s,
        stacks => player => stacks(player) / stacks.values.sum,
        stacks => player => stacks - player,
        depth  => s.size - depth + 1
      )
  }


  case object MalmuthWeitzman extends Algorithm {
    def apply(s : Stacks) : Result =
      Node.run(
        s,
        stacks => player => (1/stacks(player)) / (stacks map (1/_._2)).sum,
        redist,
        depth => depth
      )

    def redist(stacks0 : Map[Int, Double])(idx : Int) = {
      val stk     = stacks0(idx)
      val stacks  = stacks0 - idx
      stacks map { case (k, v) => (k, v + stk/stacks.size) }
    }

  }


  case object BenRoberts extends Algorithm {
    def apply(s : Stacks) : Result =
      Node.run(
        s,
        nextElim,
        redistribute,
        depth => depth
      )
  }


  def gcd(a : Double, b : Double) : Double = if (b == 0.0) a else gcd(b, a % b)
  def lcm(a : Double, b : Double) : Double = math.abs(a * b) / gcd(a, b)

  def nextElim(xs : Map[Int, Double]) =
    (xs map {
      case (i, xi) => (i, ((xs foldLeft 0.0) {
        case (acc, (j, xj)) => if (j != i) acc + 1.0/xj else acc
      }, math.pow(xi, 2)))
    }) |> simplify


  def simplify : Map[Int, (Double, Double)] => Map[Int, Double] = { nds =>
    val x1::x2::xs = nds.values map (_._2)
    val lcd        = (xs foldLeft lcm(x1, x2)) { case (lcd, x) => lcm(lcd, x) }
    val nums       = nds.values map { case (num, denom) => num * lcd/denom }
    val denom      = nums.sum
    nds map { case (k, (n, d)) => (k, (n * lcd/d) / denom) }
  }


  def redistribute(stacks0 : Map[Int, Double])(idx : Int) = {
    val stk     = stacks0(idx)
    val stacks  = stacks0 - idx
    val denom   = (stacks foldLeft 0.0) { case (acc, (_, stk)) => acc + 1.0/stk }
    stacks map { case (k, v) => (k, v + ((1.0/v) / denom) * stk) }
  }





} //icm




object Test {

  val stacks = Map() ++ List(
    2000, 4000, 3000, 6000, 5000
  ).zipWithIndex map { case (v, k) => (k, v.toDouble) }

  val payouts = Map(1 -> 500.0, 2 -> 300.0, 3 -> 200.0)


}