Random Prisoner's Trilemma - Python 3 KOTH

Question

The Prisoner's Dilemma, but with 3 choices, and the payoffs are random!

Each round, your bot recieves a 3x3 grid and chooses a row to play. The grid might be this:

4  5  7
3  1  9
9  9  0

Each number in the grid is between 0 and 10 (inclusive). Your score for the round is grid[your_play][their_play], and your opponent's is grid[their_play][your_play]. You play 100(+/-10) rounds in sequence, keeping any information you wish. The winner is the bot with a higher score at the end (draws are 0.5 wins for both bots).

Example

Using the grid above:

Player 1: row 2

Player 2: row 2

Both players get 0 points.

---

Player 1: row 1

Player 2: row 0

Player 1 gets 3 points, Player 2 gets 5 points.

Winning

Each bot will play 10 games of ~100 rounds against each bot (including itself!). Your bot can win in two categories:

• Score: the total scores will be summed and the bot with the most points at the end will win.
• Wins: a 'win' is counted for the bot with the highest score after the ~100 rounds have been played.

The overall winner will be determined by combining the two tables. A winner will be accepted about 1 week after the most recent entry, but I will probably continue to update the highscore table if new entries are added.

Technical details

Write two functions in Python 3 with these signatures:

def strategize(grid: list[list[int]], store: object) -> int

def interpret(grid: list[list[int]], moves: tuple(int, int), store: dict) -> None

• strategize is called each round and should return 0, 1, or 2.
  • grid is the 3x3 grid of possible payouts.
  • store is an empty dict to store any kind of information you'd like to.
• interpret is called after every round.
  • moves is a tuple containing (your_move, opponents_move)

Put your code in the first code block in your answer so the controller can easily pull in your bot.

Example bots

'Naiive' chooses the row with the highest average payout.

def strategize(grid, store):
    sums = [(sum(x), i) for (i, x) in enumerate(grid)]
    return max(sums)[1]

def interpret(grid, moves, store):
    pass

'Random' picks a random row.

import random

def strategize(grid, store):
    return random.randint(0, 2)

def interpret(grid, moves, store):
    pass

Rules

• No cheating by interfering directly with your opponent (through global variables etc.).
• Your function should be relatively quick to execute - the quicker it is, the better.
• You may submit multiple entries.

Controller, arena

The controller is available at https://github.com/Nucaranlaeg/KOTH-random-prisoner.

This controller is largely adapted from https://github.com/jthistle/KOTH-counting.

A couple of example bots are provided along with it to demonstrate how to use it.

arena.py is what I'll be using to calculate final scores. It pits each bot against each other bot.

update.py will fetch all submitted bots from the contest page.

Using the flag --c or -constant will cause games to be played without randomizing the grid between rounds, purely for interest's sake.

Current Results

By score:
1: Blendo with 12237.8 points
2: The Student with 11791.8 points
3: Naiive with 11728.2 points
4: Analyst with 11591.9 points
5: Min-Maxer with 11155.3 points
6: Rafaam with 11041.1 points
7: Naive Variation with 10963.1 points
8: Villain with 10853.6 points
9: Gradient-Mehscent with 10809.8 points
10: Gentleman with 10715.1 points
11: WhatDoYouExpect with 10676.6 points
12: Thief with 9687.6 points
13: Minimum Maximizer with 9656.0 points
14: HermitCrab with 9654.5 points
15: crab with 9001.9 points
16: Investigator with 8698.0 points
17: Random with 8653.3 points

By wins:
1: The Student with 15.2/16 wins
2: Blendo with 14.8/16 wins
3: Rafaam with 14.1/16 wins
4: WhatDoYouExpect with 13.9/16 wins
5: Naiive with 11.3/16 wins
6: Analyst with 10.8/16 wins
7: Min-Maxer with 10.4/16 wins
8: Naive Variation with 8.1/16 wins
9: Villain with 8.1/16 wins
10: HermitCrab with 7.3/16 wins
11: crab with 6.4/16 wins
12: Thief with 5.1/16 wins
13: Minimum Maximizer with 3.9/16 wins
14: Gradient-Mehscent with 1.9/16 wins
15: Investigator with 1.6/16 wins
16: Random with 1.5/16 wins
17: Gentleman with 1.5/16 wins

Combined leaderboard (fewer pts = better):
1: Blendo  (3 pts)
1: The Student  (3 pts)
3: Naiive  (8 pts)
4: Rafaam  (9 pts)
5: Analyst  (10 pts)
6: Min-Maxer  (12 pts)
7: Naive Variation  (15 pts)
7: WhatDoYouExpect  (15 pts)
9: Villain  (17 pts)
10: Gradient-Mehscent  (23 pts)
11: Thief  (24 pts)
11: HermitCrab  (24 pts)
13: Minimum Maximizer  (26 pts)
13: crab  (26 pts)
15: Gentleman  (27 pts)
16: Investigator  (31 pts)
17: Random  (33 pts)

Answer 1

crab

crab wants everyone to die. crab is happy when everyone else is unhappy. Yes, crab is back.

def strategize(grid, store):
    aa = grid[0][0] #aa means '0-0'.
    ab = grid[1][0] #and similarly for the others.
    ac = grid[2][0]
    ba = grid[0][1]
    bb = grid[1][1] #I wish I had a macro to do this.
    bc = grid[2][1]
    ca = grid[0][2]
    cb = grid[1][2]
    cc = grid[2][2]
    a = (aa * ab * ac)/3 # a, b, and c are the respective averages.
    b = (ba * bb * bc)/3
    c = (ca * cb * cc)/3
    if a <= min(b, c):
        return 0
    if b <= min(a, c):
        return 1
    return 2

def interpret(grid, moves, store):
    pass

Specifically, it picks the value that hurts the opponent the most.

Answer 2

Blendo

Performs approximate bayesian inference over mixtures of different opponent strategies, and optimizes the chosen move with respect to the resulting prediction. Optimizes for expected score when ahead, and score difference when behind or almost equal. Also implements self-recognition. Requires NumPy.

import random
import numpy as np

def nash(grid):
    payoffs = regrets = zeros = np.zeros(3)
    strategy = np.full((3,), 1. / 3)
    for _ in range(10):
        payoffs = np.dot(grid, strategy)
        v = np.dot(strategy, payoffs)
        regrets = np.maximum(regrets + payoffs - v, zeros) + 1e-9
        strategy = regrets / regrets.sum()
    return strategy

def max_strategy(f):
    def get_strategy(grid):
        values = f(grid)
        strategy = values == np.max(values)
        return strategy / np.sum(strategy)
    return get_strategy

expected = max_strategy(lambda grid: np.sum(grid, axis=1))
maximin = max_strategy(lambda grid: np.min(grid, axis=1))
maxidiag = max_strategy(np.diag)

def strategize(grid, store):
    if not store:
        store['is_me'] = True
        store['side'] = 0
        store['means'] = np.array([0.73336847, -0.38686278, -0.48677562, 0.09995684, -0.06624643, 0.38667801, -0.55640674, -0.1005102])
        store['stds'] = np.array([1.6364209, 0.9467514, 0.79119316, 1.54119291, 1.44484517, 1.73075995, 0.8261992, 0.7124938])
        store['score_delta'] = 0
    grid = np.array(grid)
    delta_grid = grid - grid.T
    predictions = np.array([np.full(3, 1./3), nash(grid), nash(delta_grid), expected(grid), expected(delta_grid), maximin(grid), maximin(delta_grid), maxidiag(grid)]).T
    weights = np.exp(np.random.normal(store['means'], store['stds']))
    weights /= np.sum(weights)
    probabilities = np.dot(predictions, weights)
    store['predictions'] = predictions
    if store['is_me']:
        l, r = max(((i, j) for i in range(3) for j in range(i + 1)), key=lambda t: grid[t[0]][t[1]] + grid[t[1]][t[0]])
        store['sides'] = (l, r)
        if store['side'] == -1:
            return l
        if store['side'] == 1:
            return r
        return random.choice((l, r))
    if store['score_delta'] <= 5:
        grid = delta_grid
    else:
        grid = grid - 1e-9 * grid.T
    return int(np.argmax(np.dot(grid, probabilities)))

def interpret(grid, moves, store):
    predictions = store['predictions'][moves[1]]
    store['score_delta'] += grid[moves[0]][moves[1]] - grid[moves[1]][moves[0]]
    params = np.random.normal(store['means'], store['stds'], (200, 8))
    weights = np.exp(params)
    weights = weights / weights.sum(axis=1, keepdims=True)
    likelihood = np.dot(weights, predictions)
    c = 1. / np.mean(likelihood)
    store['means'] = c * (likelihood[:,None] * params).mean(axis=0)
    store['stds'] = np.sqrt(c * (likelihood[:,None] * (params - store['means'][None,:]) ** 2).mean(axis=0))
    if store['is_me']:
        l, r = store['sides']
        if moves[1] not in (l, r):
            store['is_me'] = False
        else:
            if store['side'] == 0:
                if l != r and moves[0] != moves[1]:
                    if moves[0] == l:
                        store['side'] = -1
                    else:
                        store['side'] = 1
            else:
                if store['side'] == -1 and moves[1] != r:
                    store['is_me'] = False
                elif store['side'] == 1 and moves[1] != l:
                    store['is_me'] = False

Switcheroo No longer Competing

Switches between a few different strategies based on expected performance. Also implements self-recognition to maximally cooperate with itself.

import random

def sample(distribution):
    u = random.random()
    for i, p in enumerate(distribution):
        u -= p
        if u <= 0:
            break
    return i

def nash(grid):
    grid = [[grid[i][j] for j in range(3)] for i in range(3)]
    payoffs = [0] * 3
    regrets = [0] * 3
    strategy = [1. / 3] * 3
    for i in range(10):
        for a in range(3):
            payoffs[a] = sum(p * v for p, v in zip(strategy, grid[a]))
        v = sum(p * v for p, v in zip(strategy, payoffs))
        regrets = [max(r + q - v, 0) for r, q in zip(regrets, payoffs)]
        total_regret = sum(regrets)
        if total_regret == 0:
            strategy = [1. / 3] * 3
        else:
            c = 1. / total_regret
            strategy = [r * c for r in regrets]
    return strategy

def expected(grid):
    values = [(sum(row), -sum(col)) for row, col in zip(grid, zip(*grid))]
    v_max = max(values)
    strategy = [int(v == v_max) for v in values]
    c = 1. / sum(strategy)
    return [p * c for p in strategy]

def strategize(grid, store):
    if not store:
        store['outcomes'] = [[1. / 11 for _ in range(11)] for _ in range(2)]
        store['round_number'] = 0
        store['is_me'] = True
        store['side'] = 0
    scores = [max(sum(i * n for i, n in enumerate(a)) / sum(a) for a in (a0, [random.gammavariate(n, 1) for n in a0])) for a0 in store['outcomes']]
    strategy = scores.index(max(scores))
    nash_strategy = nash(grid)
    expected_strategy = expected(grid)
    store['strategies'] = [nash_strategy, expected_strategy]
    if store['is_me']:
        l, r = max(((i, j) for i in range(3) for j in range(i + 1)), key=lambda t: grid[t[0]][t[1]] + grid[t[1]][t[0]])
        store['sides'] = (l, r)
        if store['side'] == -1:
            return l
        if store['side'] == 1:
            return r
        return random.choice((l, r))
    return sample(store['strategies'][strategy])

def interpret(grid, moves, store):
    for i, s in enumerate(store['strategies']):
        for a, p in enumerate(s):
            v = grid[a][moves[1]]
            store['outcomes'][i][v] += p
    if store['is_me']:
        l, r = store['sides']
        if moves[1] not in (l, r):
            store['is_me'] = False
        else:
            if store['side'] == 0:
                if l != r and moves[0] != moves[1]:
                    if moves[0] == l:
                        store['side'] = -1
                    else:
                        store['side'] = 1
            else:
                if store['side'] == -1 and moves[1] != r:
                    store['is_me'] = False
                elif store['side'] == 1 and moves[1] != l:
                    store['is_me'] = False
    store['round_number'] += 1

Answer 3

Analyst

def strategize(grid, store = None):
    nonzero = [a for a in range(3)]
    if len([a for a in grid if not 0 in a]):
        maximum = max(nonzero, key=lambda index: sum(grid[index]) if not 0 in grid[index] else 0)
        if max(grid[maximum]) > 5:
            return maximum
        else:
            return max(nonzero, key=lambda arr: max(grid[arr]))
    return __import__('random').randint(0, 2)
def interpret(grid, moves, store):
    pass

Try it online with sample test cases

Analyst is a bot that tries to find the highest average out of nonzero possibilities, if the maximum is not high enough, then look for the index with the highest maximum. If all sublists have zeroes, choose randomly.

Answer 4

WhatDoYouExpect

def strategize(grid, store):
    expected = [0] * 3
    for my_play in range(3):
        for opponent_play in range(3):
            expected[my_play] += grid[my_play][opponent_play] - grid[opponent_play][my_play]
    return expected.index(max(expected))

def interpret(grid, moves, store):
    pass

Try it online!

Always plays the move with the maximum expected value.

Answer 5

Investigator

Plays naive and tit-for-tat for a few rounds, then investigates opponent responses every few rounds to find any adversarial responsive strategies. Following this, it assembles the best countermoves into a graph and executes the most positive cycle. Should be good versus both naive non-responsive opponents and basic responsive adversaries.

EDIT: In retrospect, the original problem randomizes the scoring grid after each round, which breaks this solution. This would likely do well if the scoring grid isn't randomized though.

def naive(grid):
    return max((sum(grid[move][opp]-grid[opp][move] for opp in range(3)), move) for move in range(3))[1]

def strategize(grid, store):
    if not store:
        store["round"] = 0
        store["responses"] = []
        store["sequence"] = None
    if store["round"] == 0:
        return naive(grid)
    elif store["round"] < 6:
        return store["responses"][-1][1]
    else:
        return store["sequence"][store["round"]%len(store["sequence"])]

def most_common(lst):
    return max(set(lst), key=lst.count)

def recursive_evaluate(start, trail, opponent, response, depth):
    if depth == 6:
        return trail
    trail[0].append(opponent[trail[1][-1]] if len(trail[1]) > 0 else opponent[start])
    trail[1].append(response[trail[1][-1]] if len(trail[1]) > 0 else start)
    return recursive_evaluate(start, trail, opponent, response, depth+1)

def interpret(grid, moves, store):
    store["responses"].append(moves)
    if store["round"] % 6 == 6-1:
        filtered = [[store["responses"][i+1][1] for i in range(store["round"]) if store["responses"][i][0] == me] for me in range(3)]
        default = naive(grid)
        opponent = [most_common(filtered[me]) if len(filtered[me])>0 else default for me in range(3)]
        response = [max((grid[move][opponent[me]]-grid[opponent[me]][move], move) for move in range(3))[1] for me in range(3)]
        evaluate = [recursive_evaluate(start, [[], []], opponent, response, 0) for start in range(3)]
        scoring = [(sum(grid[evaluate[start][1][i]][evaluate[start][0][i]] for i in range(len(evaluate[start][1])))-sum(grid[evaluate[start][0][i]][evaluate[start][1][i]] for i in range(len(evaluate[start][1]))), evaluate[start][1]) for start in range(3)]
        store["sequence"] = max(scoring)[1]
    store["round"] += 1

Answer 6

Min-Maxer

def strategize(grid, store):
    max_best_moves = []
    max_best_move_score = float("-inf")

    for my_move in range(3):
        worst_score = min(grid[my_move])
        if worst_score == max_best_move_score: max_best_moves.append(my_move)
        elif worst_score > max_best_move_score:
            max_best_move_score = worst_score
            max_best_moves = [my_move]

    min_best_moves = []
    min_best_move_score = float("inf")

    for my_move in range(3):
        opp_best_score = max(grid[opp_move][my_move] for opp_move in range(3))
        if opp_best_score == min_best_move_score: min_best_moves.append(my_move)
        elif opp_best_score < min_best_move_score:
            min_best_move_score = opp_best_score
            min_best_moves = [my_move]

    best_of_both = [move for move in max_best_moves if move in min_best_moves]
    if best_of_both: return best_of_both[0]
    return max_best_moves[0]

def interpret(grid, moves, store): pass

Checks for moves that both maximize the worst case for itself and minimize the best case for its opponent. If there aren't any that are both at once, then it prefers moves that give itself points over sabotaging the opponent.

Answer 7

Naive Variation

Naive works well, try to fight against aggressive players by choosing rows where every value has a reasonable payout (i.e. where several means are comparable, prefer rows with lower standard deviation)

def std_dev(numbers):
    wgt = 1 / len(numbers)
    mean = sum(numbers) * wgt
    sqdiff_wgt = wgt * sum((number - mean) ** 2 for number in numbers)
    return sqdiff_wgt ** 0.5

def strategize(grid, store=None):
    bestScore = 0
    bestIdx = -1
    for ii, row in enumerate(grid):
        rowSum = sum(row)
        # Avoid numeric inflation
        std = max(std_dev(row), 1)
        score = rowSum/std
        if score > bestScore:
            bestScore = score
            bestIdx = ii

    return bestIdx


def interpret(grid, moves, store):
    pass

Answer 8

Thief

This person is a master pickpocket of credit cards that have expired.

def strategize(grid, store):
    if not store:
        store['opmove'] = 3
    if store['opmove'] == 3:
      sums = [(sum(x), i) for (i, x) in enumerate(grid)]
      return max(sums)[1]
    elif grid[store['mymove']][store['opmove']] > grid[store['opmove']][store['mymove']]:
      sums = [(sum(x), i) for (i, x) in enumerate(grid)]
      return max(sums)[1]
    else:
      return store['opmove']

def interpret(grid, moves, store):
    store['opmove'] = moves[1]
    store['mymove'] = moves[0]

The idea is that if it's the first round, it'll act like naiive, if it won the last round, it'll act like naiive, but if it lost the last round, it'll unconditionally return the opponents move. It isn't very smart. Please provide recommendations and bug fixes.

v1.0

• Initial write

v1.1

• Rewrote some to use store rather than plain global variables.

Answer 9

Gentleman

This one is kind, and assumes everyone else is too. Optimizes for the opponent being Gentleman and picks the highest scoring option along the diagonal.

def strategize(grid, store = None):
    nums = [0,1,2]
    winner = 0
    score = -1
    for i in nums:
        if grid[i][i] > score:
            winner = i
            score = grid[i][i]
    return winner

def interpret(grid, moves, store):
    pass

Answer 10

HermitCrab

Very akin to a normal crab, but never picks an option that leaves itself out in the dust if it can help it.

def strategize(grid, store = None):
    nums = [0,1,2]
    winner = 0
    opponentScores = [-1, -1, -1]
    for i in nums:
        opponentScores[i] = (grid[0][i]*grid[1][i]*grid[2][i])+(.1*(grid[0][i]+grid[1][i]+grid[2][i]))
    fear = [0]
    fearful = 10
    terror = 0
    for i in nums:
        if min(grid[i]) < fearful:
            fear = [i]
            fearful = min(grid[i])
            terror = 0
        elif min(grid[i]) == fearful:
            terror = terror + 1
            fear.append(min(grid[i]))
    mini = 100
    if terror == 2:
        fear = []
    for i in nums:
        if i not in fear:
            if opponentScores[i] < mini:
                winner = i
                mini = opponentScores[i]
    return winner

def interpret(grid, moves, store):
    pass

Answer 11

Gradient-Mehscent

It uses a terrible method of maximizing the score.

weightA = 1
weightB = 1

def strategize(grid, store):
    global weightA, weightB
    aa = grid[0][0] #aa means '0-0'.
    ab = grid[1][0] #and similarly for the others.
    ac = grid[2][0]
    ba = grid[0][1]
    bb = grid[1][1] #I wish I had a macro to do this.
    bc = grid[2][1]
    ca = grid[0][2]
    cb = grid[1][2]
    cc = grid[2][2]

    dd = grid[0][0] 
    de = grid[0][1] 
    df = grid[0][2]
    ed = grid[1][0]
    ee = grid[1][1] #autocorrect is annoying
    ef = grid[1][2]
    fd = grid[2][0]
    fe = grid[2][1]
    ff = grid[2][2]

    a = (aa + ab + ac)/3 # a, b, c, d, e, and f are the respective averages.
    b = (ba + bb + bc)/3
    c = (ca + cb + cc)/3
    d = (dd + de + df)/3
    e = (ed + ee + ef)/3
    f = (fd + fe + ff)/3
    scoreOfZero = (weightA * a + weightB * d)/2
    scoreOfOne = (weightA * b + weightB * e)/2
    scoreOfTwo = (weightA * c + weightB * f)/2
    if scoreOfZero >= max(scoreOfOne, scoreOfTwo):
      return 0
    if scoreOfOne >= max(scoreOfZero, scoreOfTwo):
      return 1
    return 2

def interpret(grid, moves, store):
    aa = grid[0][0] #aa means '0-0'.
    ab = grid[1][0] #and similarly for the others.
    ac = grid[2][0]
    ba = grid[0][1]
    bb = grid[1][1] #I wish I had a macro to do this.
    bc = grid[2][1]
    ca = grid[0][2]
    cb = grid[1][2]
    cc = grid[2][2]

    dd = grid[0][0] 
    de = grid[0][1] 
    df = grid[0][2]
    ed = grid[1][0]
    ee = grid[1][1] #autocorrect is annoying
    ef = grid[1][2]
    fd = grid[2][0]
    fe = grid[2][1]
    ff = grid[2][2]

    a = (aa + ab + ac)/3 # a, b, c, d, e, and f are the respective averages.
    b = (ba + bb + bc)/3
    c = (ca + cb + cc)/3
    d = (dd + de + df)/3
    e = (ed + ee + ef)/3
    f = (fd + fe + ff)/3
    global weightA, weightB
    simWeightA = weightA + 0.01
    simWeightB = weightB + 0.01
    simScoreOfZero = (simWeightA * a + simWeightB * d)/2
    simScoreOfOne = (simWeightA * b + simWeightB * e)/2
    simScoreOfTwo = (simWeightA * c + simWeightB * f)/2
    if simScoreOfZero >= max(simScoreOfOne, simScoreOfTwo):
      upupscore = grid[0][moves[1]]
    elif simScoreOfOne >= max(simScoreOfZero, simScoreOfTwo):
      upupscore = grid[1][moves[1]]
    else:
      upupscore = grid[2][moves[1]]
    
    simWeightA = weightA + 0.01
    simWeightB = weightB - 0.01
    simScoreOfZero = (simWeightA * a + simWeightB * d)/2
    simScoreOfOne = (simWeightA * b + simWeightB * e)/2
    simScoreOfTwo = (simWeightA * c + simWeightB * f)/2
    if simScoreOfZero >= max(simScoreOfOne, simScoreOfTwo):
      updownscore = grid[0][moves[1]]
    elif simScoreOfOne >= max(simScoreOfZero, simScoreOfTwo):
      updownscore = grid[1][moves[1]]
    else:
      updownscore = grid[2][moves[1]]
    simWeightA = weightA - 0.01
    simWeightB = weightB + 0.01
    simScoreOfZero = (simWeightA * a + simWeightB * d)/2
    simScoreOfOne = (simWeightA * b + simWeightB * e)/2
    simScoreOfTwo = (simWeightA * c + simWeightB * f)/2
    if simScoreOfZero >= max(simScoreOfOne, simScoreOfTwo):
      downupscore = grid[0][moves[1]]
    elif simScoreOfOne >= max(simScoreOfZero, simScoreOfTwo):
      downupscore = grid[1][moves[1]]
    else:
      downupscore = grid[2][moves[1]]
    simWeightA = weightA - 0.01
    simWeightB = weightB - 0.01
    simScoreOfZero = (simWeightA * a + simWeightB * d)/2
    simScoreOfOne = (simWeightA * b + simWeightB * e)/2
    simScoreOfTwo = (simWeightA * c + simWeightB * f)/2
    if simScoreOfZero >= max(simScoreOfOne, simScoreOfTwo):
      downdownscore = grid[0][moves[1]]
    elif simScoreOfOne >= max(simScoreOfZero, simScoreOfTwo):
      downdownscore = grid[1][moves[1]]
    else:
      downdownscore = grid[2][moves[1]]
    if upupscore >= max(updownscore, downupscore, downdownscore):
      weightA = weightA + 0.01
      weightB = weightB + 0.01
    elif updownscore >= max(upupscore, downupscore, downdownscore):
      weightA = weightA + 0.01
      weightB = weightB - 0.01
    elif downupscore >= max(upupscore, updownscore, downdownscore):
      weightA = weightA - 0.01
      weightB = weightB + 0.01
    else:
      weightA = weightA - 0.01
      weightB = weightB - 0.01

How It Works

It probably doesn't. However, it should slowly move weightA and weightB so the bot is more effective. It's basically a tiny AI. The real core of Mehscent is the giant interpret function, which just plays around with the weights until something good happens.

Answer 12

Minimum Maximizer

Not to be confused with the other one

def strategize(grid, store):
    a = min(grid[0])
    b = min(grid[1])
    c = min(grid[2])
    if a >= min(b, c):
      return 0
    if b >= min(a, c):
      return 1
    return 2
def interpret(grid, moves, store):
    pass

Answer 13

Rafaam

My final entry, came to me last night. Named after my favorite duplicitous multiverse-traveling villain, this optimizes its own success compared to its opponent, but sometimes acts kindly, and in doing so, determines if it's facing against itself, possibly changing from cruel to kind.

def strategize(grid, store = None):
    if not store:
        store["round"] = 0
        store["opponent"] = 0
    nums = [0,1,2]
    kind = False
    if store["opponent"] == 1:
        kind = True
    elif store["opponent"] == 0 and store["round"] == 2:
        kind = True
    if kind:
        winner = 0
        score = -1
        for i in nums:
            if grid[i][i] > score:
                winner = i
                score = grid[i][i]
        return winner
    scores = []
    for i in nums:
        row = []
        for j in nums:
            row.append((grid[i][j],(grid[i][j]/(grid[j][i]+0.01))))
        scores.append(row)
    safeRows = []
    ratios = [[col[1] for col in row] for row in scores]
    for i in nums:
        non = ratios[i][:i] + ratios[i][(i + 1):]
        if min(non) > 0.95:
            safeRows.append(i)
    
    scores = []
    for i in nums:
        scores.append((ratios[i][0]+ratios[i][1]+ratios[i][2]-ratios[i][i],i))
    sortedScores = sorted(scores, key=lambda tup:(-tup[0],tup[1]))
    for i in sortedScores:
        if i[1] in safeRows:
            return i[1]
    return sortedScores[0][1]

def interpret(grid, moves, store):
    if moves[0] != moves[1]:
        store["opponent"] = -1
    elif store["round"] == 4 and store["opponent"] == 0:
        store["opponent"] = 1
    store["round"] += 1

Answer 14

Villain

My personal approach to solving the problem

def strategize(grid, store = None):
    nums = [0,1,2]
    safe = [(a, True) if 0 not in a else (a, False) for a in grid]
    safeNums = []
    for i in nums:
        if safe[i][1]:
            safeNums.append(i)
    if len(safeNums) == 1:
        return safeNums[0]
    rudeNums = []
    for i in nums:
        rude = False
        for j in grid:
            if j[i] == 0:
                rude = True
        if rude:
            rudeNums.append(i)
    geniusNums = []
    for i in nums:
        if i in safeNums and i in rudeNums:
            geniusNums.append(i)
    if len(geniusNums) == 1:
        return geniusNums[0]
    if len(geniusNums) > 1:
        winner = geniusNums[0]
        mini = -1
        for i in geniusNums:
            newMin = min(grid[i])
            if newMin > mini:
                winner = i
                mini = newMin
        return winner
    if len(safeNums) > 1:
        winner = safeNums[0]
        mini = -1
        for i in safeNums:
            newMin = min(grid[i])
            if newMin > mini:
                winner = i
                mini = newMin
        return winner
    if len(rudeNums) == 1:
        return rudeNums[0]
    if len(rudeNums) >= 1:
        winner = rudeNums[0]
        mini = -1
        for i in rudeNums:
            newMin = grid[i][0]+grid[i][1]+grid[i][2]
            if newMin > mini:
                winner = i
                mini = newMin
        return winner
    score = 0
    winner = 0
    for i in nums:
        newScore = grid[i][0]+grid[i][1]+grid[i][2]
        if newScore > score:
            score = newScore
            winner = i
    return winner

def interpret(grid, moves, store):
    pass

Should be a fine algorithm- first prioritizes safety, then screwing over opponents, then personal score. It doesn't bother minimizing opponent score, only giving them the potential for 0s.

Answer 15

Why_do_I_have_so_many_ideas?!?!

It works. It's trash, but it works on Debian Buster with python 3.7.3

isFriendlyOne = 0
isFriendlyTwo = 0
def strategize(grid, store):
    global isFriendlyOne, isFriendlyTwo
    aa = grid[0][0] #aa means '0-0'.
    ab = grid[1][0] #and similarly for the others.
    ac = grid[2][0]
    ba = grid[0][1]
    bb = grid[1][1] #I wish I had a macro to do this.
    bc = grid[2][1]
    ca = grid[0][2]
    cb = grid[1][2]
    cc = grid[2][2]

    dd = grid[0][0] 
    de = grid[0][1] 
    df = grid[0][2]
    ed = grid[1][0]
    ee = grid[1][1] #autocorrect is annoying
    ef = grid[1][2]
    fd = grid[2][0]
    fe = grid[2][1]
    ff = grid[2][2]

    a = (aa + ab + ac)/3 # a, b, c, d, e, and f are the respective averages.
    b = (ba + bb + bc)/3
    c = (ca + cb + cc)/3
    d = (dd + de + df)/3
    e = (ed + ee + ef)/3
    f = (fd + fe + ff)/3
    scoreOfZero = (a + d)/2
    scoreOfOne = (b + e)/2
    scoreOfTwo = (c + f)/2
    if isFriendlyOne != 2:
      if scoreOfZero <= min(scoreOfOne, scoreOfTwo):
        return 0
      if scoreOfOne <= min(scoreOfZero, scoreOfTwo):
        return 1
      return 2
    elif isFriendlyTwo != 2:
      if scoreOfZero <= min(scoreOfOne, scoreOfTwo):
        return 0
      if scoreOfOne <= min(scoreOfZero, scoreOfTwo):
        return 1
      return 2
    else:
      if d >= max(e, f):
        if dd >= max(de, df):
          return 0
        if de >= max(dd, df):
          return 1
        return 2
      if e >= max(d, f):
        if ed >= max(ee, ef):
          return 0
        if ee >= max(ed, ef):
          return 1
        return 2
      if fd >= max(fe, ff):
        return 0
      if fe >= max(fd, ff):
        return 1
      return 2

def interpret(grid, moves, store):
    global isFriendlyOne, isFriendlyTwo
    if not store:
      store['wroteOne'] = False
      store['wroteTwo'] = False
      isFriendlyOne = 0
      isFriendlyTwo = 0
    if moves[0] != moves[1]:
      store['oldMatch'] = True
    if max(isFriendlyOne, isFriendlyTwo) < 1:
      if moves[1] == 0:
        if grid[0][moves[0]] >= max(grid[1][moves[0]], grid[2][moves[0]]):
          if moves[0] > 0:
            isFriendlyOne = 1
            store['wroteOne'] = True
      if moves[1] == 1:
        if grid[1][moves[0]] >= max(grid[2][moves[0]], grid[0][moves[0]]):
          if moves[0] > 1:
            isFriendlyOne = 1
            store['wroteOne'] = True
          elif moves[0] < 1:
            isFriendlyTwo = 1
            store['wroteTwo'] = True
      if moves[1] == 2:
        if grid[2][moves[0]] >= max(grid[1][moves[0]], grid[0][moves[0]]):
          if moves[0] > 2:
            isFriendlyOne = 1
            store['wroteOne'] = True
          elif moves[0] < 2:
            isFriendlyTwo = 1
            store['wroteTwo'] = True
    if store['wroteOne']:
      if isFriendlyTwo == 1:
        isFriendlyOne = 2
    if store['wroteTwo']:
      if isFriendlyOne == 1:
        isFriendlyTwo = 2

I think the new version implements self-recognition? Either this bot or Switcheroo has the most lines, although Switcheroo is vastly more complex. The entire interpret function is just for self-recognition.

Answer 16

The Student

My late entry to the competition, spawned originally out of a simple desire to beat naiive, which has been remarkably successful. Eventually it morphed into this monstrosity that attempts to predict opponent moves and tracks likelihood of a some strategies I or people I talked to thought of.

import random

def strategize(grid, store):
    possible_round_results = [
        ((0, 0), (grid[0][0], grid[0][0]), 0),
        ((0, 1), (grid[0][1], grid[1][0]), grid[0][1] - grid[1][0]),
        ((0, 2), (grid[0][2], grid[2][0]), grid[0][2] - grid[2][0]),
        ((1, 0), (grid[1][0], grid[0][1]), grid[1][0] - grid[0][1]),
        ((1, 1), (grid[1][1], grid[1][1]), 0),
        ((1, 2), (grid[1][2], grid[2][1]), grid[1][2] - grid[2][1]),
        ((2, 0), (grid[2][0], grid[0][2]), grid[2][0] - grid[0][2]),
        ((2, 1), (grid[2][1], grid[1][2]), grid[2][1] - grid[1][2]),
        ((2, 2), (grid[2][2], grid[2][2]), 0)
    ]

    # Interpret data from Store to try to determine opponent and optimize
    if('facing_self' in store and store['facing_self']):
        # Determine move combination that gives the highest total points
        max_score_result_index = max([(x[1][0] + x[1][1], i) for (i, x) in enumerate(possible_round_results)])[1]
        if(store['should_pick_low'] is None):
            random.seed()
            return possible_round_results[max_score_result_index][0][random.randrange(0,2)]
        elif(store['should_pick_low']):
            return max(possible_round_results[max_score_result_index][0])
        else:
            return min(possible_round_results[max_score_result_index][0])
    opponent_move = -1
    if('opponent_strategy_probabilities' in store):
        opponent_probabilities = [(store['opponent_strategy_probabilities'][x], x) for x in store['opponent_strategy_probabilities']]
        opponent_probabilities.remove((store['opponent_strategy_probabilities']['self'], 'self'))
        most_likely_opponent = max(opponent_probabilities)[1]
        if(most_likely_opponent == 'safe_scorer'):
            # safe_scorer
            opponent_move = 0
            safe_moves = []
            for i in range(0,9,3):
                if(min([possible_round_results[i][2], possible_round_results[i+1][2], possible_round_results[i+2][2]]) >= 0):
                    safe_moves.append((possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]))
            if(len(safe_moves) > 0):
                opponent_move = max(safe_moves)[1]
            else:
                #resort to naiive_score_differential after loosing out on safety
                opponent_move = max([(possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]) for i in range(0, 9, 3)])[1]
        elif(most_likely_opponent == 'hurtful'):
            # hurtful
            opponent_move = min([(sum(x), i) for (i, x) in enumerate(grid)])[1]
        elif(most_likely_opponent == 'cooperative'):
            # cooperative 
            opponent_move = max([(x[i], i) for (i, x) in enumerate(grid)])[1]
        elif(most_likely_opponent == 'minimize_losses'):
            # minimize_losses
            opponent_move = max([(min(x), i) for (i, x) in enumerate(grid)])[1]
        elif(most_likely_opponent == 'highest_expected_val'):
            # highest_expected_val
            opponent_move = max([(x[2], x[0][1]) for x in possible_round_results])[1]
        elif(most_likely_opponent == 'naiive_score_differential'):
            # naiive_scored_differential
            opponent_move = max([(possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]) for i in range(0, 9, 3)])[1]
        else:
            # naiive
            opponent_move = max([(sum(x), i) for (i, x) in enumerate(grid)])[1]
    else:
        #assumed naiive
        opponent_move = max([(sum(x), i) for (i, x) in enumerate(grid)])[1]
    score_margin = 10
    if('my_score' in store and store['my_score'] >= store['opponent_score'] + score_margin):
        return max([(x[opponent_move], i) for (i, x) in enumerate(grid)])[1]
    else:
        possible_moves = []
        for result in possible_round_results:
            if(result[0][1] == opponent_move):
                possible_moves.append(result)
        return max([(x[2], i) for (i, x) in enumerate(possible_moves)])[1]

def interpret(grid, moves, store):
    possible_round_results = [
        ((0, 0), (grid[0][0], grid[0][0]), 0),
        ((0, 1), (grid[0][1], grid[1][0]), grid[0][1] - grid[1][0]),
        ((0, 2), (grid[0][2], grid[2][0]), grid[0][2] - grid[2][0]),
        ((1, 0), (grid[1][0], grid[0][1]), grid[1][0] - grid[0][1]),
        ((1, 1), (grid[1][1], grid[1][1]), 0),
        ((1, 2), (grid[1][2], grid[2][1]), grid[1][2] - grid[2][1]),
        ((2, 0), (grid[2][0], grid[0][2]), grid[2][0] - grid[0][2]),
        ((2, 1), (grid[2][1], grid[1][2]), grid[2][1] - grid[1][2]),
        ((2, 2), (grid[2][2], grid[2][2]), 0)
    ]

    # Estimate probability that opponent is using a specific strategy
    naiive_move = max([(sum(x), i) for (i, x) in enumerate(grid)])[1]
    naiive_score_differnetial_move = max([(possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]) for i in range(0, 9, 3)])[1]
    cooperative_move = max([(x[i], i) for (i, x) in enumerate(grid)])[1]
    minimize_losses_move = max([(min(x), i) for (i, x) in enumerate(grid)])[1]
    highest_expected_val_move = max([(x[2], x[0][1]) for x in possible_round_results])[1]
    hurtful_move = min([(sum(x), i) for (i, x) in enumerate(grid)])[1]
    safe_scorer_move = 0
    safe_moves = []
    for i in range(0,9,3):
        if(min([possible_round_results[i][2], possible_round_results[i+1][2], possible_round_results[i+2][2]]) >= 0):
            safe_moves.append((possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]))
    if(len(safe_moves) > 0):
        safe_scorer_move = max(safe_moves)[1]
    else:
        #resort to naiive_score_differential after loosing out on safety
        safe_scorer_move = max([(possible_round_results[i][2] + possible_round_results[i+1][2] + possible_round_results[i+2][2], possible_round_results[i][0][0]) for i in range(0, 9, 3)])[1]
    self_move = None
    if(('facing_self' in store) and (store['facing_self'])):
        #find the two possibilities that might have been used, compare to move, and set to move if it matches to maintain self-facing status
        max_score_result_index = max([(x[1][0] + x[1][1], i) for (i, x) in enumerate(possible_round_results)])[1]
        possible_moves = possible_round_results[max_score_result_index][0]
        if(moves[1] == possible_moves[0] or moves[1] == possible_moves[1]):
            self_move = moves[1]
            if(moves[0] < moves[1] and store['should_pick_low'] is None):
                store['should_pick_low'] = True
            elif(moves[0] > moves[1] and store['should_pick_low'] is None):
                store['should_pick_low'] = False
        else:
            self_move = -1
    else:
        self_move = strategize(grid, store)

    # Populate default values for store
    if(not 'num_turns' in store):
        store['num_turns'] = 0
        store['my_score'] = 0
        store['opponent_score'] = 0
        store['opponent_strategy_probabilities'] = {
            'self': 0,
            'naiive': 0, # pick the row with the highest sum
            'naiive_score_differential': 0, # pick the row with the highest average point gain over opponent
            'hurtful': 0, # try to give opponent the column with lowest sum
            'cooperative': 0, # try to behave cooperatively
            'minimize_losses': 0, # pick row with highest minimum
            'highest_expected_val': 0, # pick row with highest sum of score differences
            'safe_scorer': 0 # determine rows with safety, then pick row with highest score differential
        }
        store['facing_self'] = False
        store['should_pick_low'] = None
    store['num_turns'] += 1
    store['my_score'] += grid[moves[0]][moves[1]]
    store['opponent_score'] += grid[moves[1]][moves[0]]

    # Used to tune adaptation of bot
    most_recent_weighting = 5

    if(moves[1] == naiive_move):
        store['opponent_strategy_probabilities']['naiive'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['naiive'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['naiive'] = ((store['opponent_strategy_probabilities']['naiive'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == naiive_score_differnetial_move):
        store['opponent_strategy_probabilities']['naiive_score_differential'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['naiive_score_differential'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['naiive_score_differential'] = ((store['opponent_strategy_probabilities']['naiive_score_differential'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == cooperative_move):
        store['opponent_strategy_probabilities']['cooperative'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['cooperative'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['cooperative'] = ((store['opponent_strategy_probabilities']['cooperative'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == minimize_losses_move):
        store['opponent_strategy_probabilities']['minimize_losses'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['minimize_losses'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['minimize_losses'] = ((store['opponent_strategy_probabilities']['minimize_losses'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == highest_expected_val_move):
        store['opponent_strategy_probabilities']['highest_expected_val'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['highest_expected_val'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['highest_expected_val'] = ((store['opponent_strategy_probabilities']['highest_expected_val'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == hurtful_move):
        store['opponent_strategy_probabilities']['hurtful'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['hurtful'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['hurtful'] = ((store['opponent_strategy_probabilities']['hurtful'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == safe_scorer_move):
        store['opponent_strategy_probabilities']['safe_scorer'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['safe_scorer'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['safe_scorer'] = ((store['opponent_strategy_probabilities']['safe_scorer'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(moves[1] == self_move):
        store['opponent_strategy_probabilities']['self'] = (most_recent_weighting + (store['opponent_strategy_probabilities']['self'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    else:
        store['opponent_strategy_probabilities']['self'] = ((store['opponent_strategy_probabilities']['self'] * (store['num_turns'] - 1))) / (most_recent_weighting + store['num_turns'] - 1)
    if(store['opponent_strategy_probabilities']['self'] == 1 and store['num_turns'] > 4):
        store['facing_self'] = True
    else:
        store['facing_self'] = False