skip-cts

This program has been disqualified.

Source code:

if input == "":
    import math
    import random

    gamma = random.gammavariate
    log = math.log
    exp = math.exp
    log_half = log(0.5)
    third = 1.0 / 3.0
    log_third = log(1.0/3.0)
    log_quarter = log(1.0/4.0)
    log_two_thirds = log(2.0/3.0)
    log_thirds = tuple([log_third] * 3)

    def to_probs(ps):
        p0 = min(ps)
        qs = [exp(p - p0) for p in ps]
        rt = 1.0 / sum(qs)
        for i, q in enumerate(qs):
            qs[i] = q * rt
        return qs

    def log_sum(xs):
        r = float("-inf")
        for x in xs:
            r = log_add(r, x)
        return r

    def log_add(x, y):
        if y > x:
            x, y = y, x
        d = y - x
        if d < -60:
            return x
        return x + log(1.0 + exp(d))

    def log_sub(x, y):
        d = y - x
        return x + log(1.0 - exp(d))

    def log_mean(x, y):
        return log_half + log_add(x, y)

    def log_mean_3(x, y, z):
        return log_third + log_add(log_add(x, y), z)

    class ContextTree:
        def __init__(self, n):
            self.p = 0.0
            if n == 3:
                self.weights = [log_quarter for _ in xrange(4)]
            elif n == 2:
                self.weights = [log_third for _ in xrange(3)]
            self.counts = [0] * 3
            self.children = [None] * 3
            self.skip = None
        def update(self, skipped, depth, alpha, beta, history, c, i=0):
            counts = self.counts
            t = sum(counts)
            cond_p_self = log((counts[c] + 1.0) / (t + 3.0))
            counts[c] += 1
            if i >= min(len(history) - 1, depth):
                self.p += cond_p_self
                return
            x = history[i]
            if self.children[x] is None:
                self.children[x] = ContextTree(2 if skipped else 3)
            cond_p_children = self.children[x].p
            self.children[x].update(skipped, depth, alpha, beta, history, c, i + 1)
            cond_p_children = self.children[x].p - cond_p_children
            if not skipped:
                if self.skip is None:
                    self.skip = ContextTree(2)
                skip = self.skip
                p_skip = skip.p
                skip.update(True, depth, alpha, beta, history, c, i + 1)
                cond_p_skip = skip.p - p_skip
                ps = (cond_p_self, log_third, cond_p_skip, cond_p_children)
            else:
                ps = (cond_p_self, log_third, cond_p_children)
            qs = tuple(w + p for w, p in zip(self.weights, ps))
            self.p = log_sum(qs)
            base = alpha + self.p
            if skipped:
                d = log_half
            else:
                d = log_third
            for i, q in enumerate(qs):
                self.weights[i] = log_add(base, beta + q) + d
        def predict(self, skipped, depth, history, ps, i=0):
            counts = self.counts
            rt = 1.0 / (sum(counts) + 3.0)
            cond_p_self = [log((n + 1.0) * rt) for n in counts]
            if i >= min(len(history) - 1, depth):
                for i, p0 in enumerate(cond_p_self):
                    ps[i] += p0 + self.p
                return
            x = history[i]
            if self.children[x] is None:
                cond_p_children = [log_third] * 3
            else:
                p = self.children[x].p
                cond_p_children = [-p] * 3
                self.children[x].predict(skipped, depth, history, cond_p_children, i + 1)
            if not skipped:
                if self.skip is None:
                    cond_p_skip = [third for _ in xrange(3)]
                else:
                    p = self.skip.p
                    cond_p_skip = [-p] * 3
                    self.skip.predict(True, depth, history, cond_p_skip, i+1)
                pss = (cond_p_self, log_thirds, cond_p_skip, cond_p_children)
            else:
                pss = (cond_p_self, log_thirds, cond_p_children)
            for i, p in enumerate(zip(*pss)):
                ps[i] += log_sum(w + p for w, p in zip(self.weights, p))

    import collections
    import random

    R, P, S = range(3)
    index = {"R": R, "P": P, "S": S}
    name = ("R", "P", "S")
    beat   = (P, S, R)
    beaten = (S, R, P)
    model = ContextTree(3)
    history = collections.deque([])
    output = random.choice(name)
    rnd = 0.0
else:

    inp = index[input]
    out = index[output]

    rnd += 1
    alpha = 1.0 / (rnd + 2)
    beta  = 1 - 2 * alpha
    alpha = log(alpha)
    beta = log(beta)

    n0 = 6

    model.update(False, n0, alpha, beta, history, inp)

    history.appendleft(inp)
    history.appendleft(out)
    ps = [0.0, 0.0, 0.0]
    model.predict(False, n0, history, ps)
    ps = to_probs(ps)
    scores = [0, 0, 0]
    t = sum(ps)
    for _ in xrange(3):
        x = 0
        r = random.uniform(0, t)
        for k, p in enumerate(ps):
            x += p
            if x >= r:
                break
        scores[beat[k]]   += 1
        scores[beaten[k]] -= 1
    m = max(scores)
    output = name[random.choice([k for k, x in enumerate(scores) if x == m])]