Estimates the Nash Equilibrium of a game. Currently only supports zero-sum games, can probably support nonzero-sum games.

payoff_matrix_estimate.py

import random
import operator
import timeit
import time

TOTAL_TRIALS = 100

p1_matrix = [
    [6, 8, -8, 6],
    [9, 10, 1, 9],
    [-10, 10, -2, 2],
    [3, 9, -9, -5],
    [2, -5, -7, -8],
    [-5, -6, 4, 1]
]


"""
p2_matrix = [
    [-2, 0, 2],
    [1, -1, -2],
    [-6, 1, -1]
]
"""

def argmin_min(values):
    value = min(values)
    return values.index(value), value

def main():
    NUM_ROWS = len(p1_matrix)
    NUM_COLS = len(p1_matrix[0])

    p2_matrix = [[-p1_matrix[j][i] for j in range(NUM_ROWS)] for i in range(NUM_COLS)]
    p1_strategy = random.randint(0, NUM_ROWS - 1)
    p1_strategies = [0] * NUM_ROWS
    p2_strategies = [0] * NUM_COLS
    p1_value = -100.0
    p2_value = -100.0
    p1_best_play_trial_count = 0
    p2_best_play_trial_count = 0
    p1_best_play_strategy_counts = [0] * NUM_ROWS
    p2_best_play_strategy_counts = [0] * NUM_COLS
    p1_weights = [0] * NUM_COLS
    p2_weights = [0] * NUM_ROWS

    output = ""

    for num_trials in range(1, TOTAL_TRIALS + 1):
        p1_strategies[p1_strategy] += 1
        row = p1_matrix[p1_strategy]
        for i, payoff in enumerate(row):
            p1_weights[i] += payoff

        p2_strategy, p2_payoff = argmin_min(p1_weights)
        cur_p1_value = p2_payoff / num_trials
        if cur_p1_value >= p1_value:
            p1_value = cur_p1_value
            p1_best_play_strategy_counts[0:NUM_ROWS] = p1_strategies[0:NUM_ROWS]
            p1_best_play_trial_count = num_trials

        output += "{: 3d}: {: 4d} |".format(num_trials, p1_strategy + 1)
        output += "".join(" {: 4d} |".format(p1_weight) for p1_weight in p1_weights)
        output += " {: .4f} || ".format(cur_p1_value)

        p2_strategies[p2_strategy] += 1
        col = p2_matrix[p2_strategy]
        for i, payoff in enumerate(col):
            p2_weights[i] += payoff

        p1_strategy, p1_payoff = argmin_min(p2_weights)
        cur_p2_value = p1_payoff / num_trials
        if cur_p2_value >= p2_value:
            p2_value = cur_p2_value
            p2_best_play_strategy_counts[0:NUM_COLS] = p2_strategies[0:NUM_COLS]
            p2_best_play_trial_count = num_trials

        output += "{: 4d} |".format(p2_strategy + 1)
        output += "".join(" {: 4d} |".format(p2_weight) for p2_weight in p2_weights)
        output += " {: .4f}\n".format(cur_p2_value)

    output += ", ".join("{}/{}".format(p1_best_play_strategy_count, p1_best_play_trial_count) for p1_best_play_strategy_count in p1_best_play_strategy_counts) + "\n"
    output += ", ".join("{}".format(p1_best_play_strategy_count / p1_best_play_trial_count) for p1_best_play_strategy_count in p1_best_play_strategy_counts) + "\n\n"

    output += ", ".join("{}/{}".format(p2_best_play_strategy_count, p2_best_play_trial_count) for p2_best_play_strategy_count in p2_best_play_strategy_counts) + "\n"
    output += ", ".join("{}".format(p2_best_play_strategy_count / p2_best_play_trial_count) for p2_best_play_strategy_count in p2_best_play_strategy_counts) + "\n"

    print(output)
    with open("payoff_matrix_estimate_out.txt", "w+") as f:
        f.write(output)

if __name__ == "__main__":
    main()