Skip to content

Instantly share code, notes, and snippets.

@0xYUANTI
Created August 9, 2016 10:33
Show Gist options
  • Save 0xYUANTI/65e76db7bbebb5db190ae14d6418dcb2 to your computer and use it in GitHub Desktop.
Save 0xYUANTI/65e76db7bbebb5db190ae14d6418dcb2 to your computer and use it in GitHub Desktop.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment