СТАТУС ВЫЗОВА: ОТКРЫТ

Прокомментируй, открой пиар или иначе на меня кричи, если я скучаю по твоему боту.

Дилемма заключенного ... с тремя вариантами. Сумасшедший, а?

Вот наша матрица выплат. Игрок А слева, В сверху

A,B| C | N | D
---|---|---|---
 C |3,3|4,1|0,5
 N |1,4|2,2|3,2
 D |5,0|2,3|1,1

Матрица выплат разработана таким образом, что обоим игрокам лучше всегда сотрудничать, но вы можете получить (обычно), выбрав «Нейтральный» или «Дефект».

Вот несколько (конкурирующих) примеров ботов.

# turns out if you don't actually have to implement __init__(). TIL!

class AllC:
    def round(self, _): return "C"
class AllN:
    def round(self, _): return "N"
class AllD:
    def round(self, _): return "D"
class RandomBot:
    def round(self, _): return random.choice(["C", "N", "D"])

# Actually using an identically-behaving "FastGrudger".
class Grudger:
    def __init__(self):
        self.history = []
    def round(self, last):
        if(last):
            self.history.append(last)
            if(self.history.count("D") > 0):
                return "D"
        return "C"

class TitForTat:
    def round(self, last):
        if(last == "D"):
            return "D"
        return "C"

Ваш бот - это класс Python3. Новый экземпляр создается для каждой игры и round()вызывается каждый раунд, с выбором вашего оппонента из прошлого раунда (или None, если это первый раунд)

В награду за награду 50 представителей.

конкретика

• Каждый бот играет каждого другого бота (1 на 1), включая самого себя, в раундах [УДАЛЕНО].
• Стандартные лазейки запрещены.
• Не связывайтесь ни с чем вне вашего класса или другими закулисными махинациями.
• Вы можете отправить до пяти ботов.
• Да, вы можете реализовать рукопожатие.
• Любой ответ, кроме C, Nили Dбудет принят как молча N.
• Очки каждого бота из каждой игры, в которую они играют, будут суммироваться и сравниваться.

контроллер

Проверьте!

Другие языки

Я скину API, если кому-то это нужно.

Результаты: 2018-11-27

27 bots, 729 games.

name            | avg. score/round
----------------|-------------------
PatternFinder   | 3.152
DirichletDice2  | 3.019
EvaluaterBot    | 2.971
Ensemble        | 2.800
DirichletDice   | 2.763
Shifting        | 2.737
FastGrudger     | 2.632
Nash2           | 2.574
HistoricAverage | 2.552
LastOptimalBot  | 2.532
Number6         | 2.531
HandshakeBot    | 2.458
OldTitForTat    | 2.411
WeightedAverage | 2.403
TitForTat       | 2.328
AllD            | 2.272
Tetragram       | 2.256
Nash            | 2.193
Jade            | 2.186
Useless         | 2.140
RandomBot       | 2.018
CopyCat         | 1.902
TatForTit       | 1.891
NeverCOOP       | 1.710
AllC            | 1.565
AllN            | 1.446
Kevin           | 1.322

EvaluaterBot

class EvaluaterBot:
    def __init__(self):
        self.c2i = {"C":0, "N":1, "D":2}
        self.i2c = {0:"C", 1:"N", 2:"D"}
        self.history = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        self.last = [None, None]

    def round(self, last):
        if self.last[0] == None:
            ret = 2
        else:
            # Input the latest enemy action (the reaction to my action 2 rounds ago)
            # into the history
            self.history[self.last[0]][self.c2i[last]] += 1
            # The enemy will react to the last action I did
            prediction,_ = max(enumerate(self.history[self.last[1]]), key=lambda l:l[1])
            ret = (prediction - 1) % 3
        self.last = [self.last[1], ret]
        return self.i2c[ret]

Выигрывает против всех ранее представленных ботов, за исключением (возможно) случайного бота (но он может иметь преимущество, потому что он выбирает D при ничьей, а D должен оптимально) и играет постоянную ничью против себя.

Равновесие по Нэшу

Этот бот взял курс теории игр в колледже, но был ленив и не пошел в класс, где они освещали повторяющиеся игры. Таким образом, он играет только в смешанном равновесии Нэша. Оказывается, 1/5 2/5 2/5 - смешанный NE для выплат.

class NashEquilibrium:
    def round(self, _):
        a = random.random()
        if a <= 0.2:
            return "C"
        elif a <= 0.6:
            return "N"
        else:
            return "D" 

Постоянное злоупотребление равновесием по Нэшу

Этот бот взял один или два урока от своего ленивого брата. Проблема его ленивого брата состояла в том, что он не использовал фиксированные стратегии. Эта версия проверяет, является ли противник постоянным игроком или титфортом, и играет соответственно, иначе она играет в обычном равновесии Нэша.

Единственным недостатком является то, что в среднем он получает 2,2 очка за ход, играя против самого себя.

class NashEquilibrium2:

    def __init__(self):
        self.opphistory = [None, None, None]
        self.titfortatcounter = 0
        self.titfortatflag = 0
        self.mylast = "C"
        self.constantflag = 0
        self.myret = "C"

    def round(self, last):
        self.opphistory.pop(0)
        self.opphistory.append(last)

        # check if its a constant bot, if so exploit
        if self.opphistory.count(self.opphistory[0]) == 3:
            self.constantflag = 1
            if last == "C":
                 self.myret = "D"
            elif last == "N":
                 self.myret = "C"
            elif last == "D":
                 self.myret = "N"

        # check if its a titfortat bot, if so exploit
        # give it 2 chances to see if its titfortat as it might happen randomly
        if self.mylast == "D" and last == "D":
            self.titfortatcounter = self.titfortatcounter + 1

        if self.mylast == "D" and last!= "D":
            self.titfortatcounter = 0

        if self.titfortatcounter >= 3:
            self.titfortatflag = 1

        if self.titfortatflag == 1:
            if last == "C":
                 self.myret = "D"
            elif last == "D":
                 self.myret = "N"    
            elif last == "N":
                # tit for tat doesn't return N, we made a mistake somewhere
                 self.titfortatflag = 0
                 self.titfortatcounter = 0

        # else play the single game nash equilibrium
        if self.constantflag == 0 and self.titfortatflag == 0:
            a = random.random()
            if a <= 0.2:
                self.myret = "C"
            elif a <= 0.6:
                self.myret = "N"
            else:
                self.myret = "D"


        self.mylast = self.myret
        return self.myret

TatForTit

class TatForTit:
    def round(self, last):
        if(last == "C"):
            return "N"
        return "D"

Этот бот будет чередовать выбор DNDN, в то время как TitForTat чередует CDCD, для среднего чистого выигрыша в 3 очка за раунд, если я правильно прочитал матрицу выплат. Я думаю, что это может быть оптимальным против TitForTat. Очевидно, что это может быть улучшено, чтобы обнаружить противника без TFT и принять другие стратегии, но я просто стремился к первоначальной награде.

PatternFinder

class PatternFinder:
    def __init__(self):
        import collections
        self.size = 10
        self.moves = [None]
        self.other = []
        self.patterns = collections.defaultdict(list)
        self.counter_moves = {"C":"D", "N":"C", "D":"N"}
        self.initial_move = "D"
        self.pattern_length_exponent = 1
        self.pattern_age_exponent = 1
        self.debug = False
    def round(self, last):
        self.other.append(last)
        best_pattern_match = None
        best_pattern_score = None
        best_pattern_response = None
        self.debug and print("match so far:",tuple(zip(self.moves,self.other)))
        for turn in range(max(0,len(self.moves)-self.size),len(self.moves)):
            # record patterns ending with the move that just happened
            pattern_full = tuple(zip(self.moves[turn:],self.other[turn:]))
            if len(pattern_full) > 1:
                pattern_trunc = pattern_full[:-1]
                pattern_trunc_result = pattern_full[-1][1]
                self.patterns[pattern_trunc].append([pattern_trunc_result,len(self.moves)-1])
            if pattern_full in self.patterns:
                # we've seen this pattern at least once before
                self.debug and print("I've seen",pattern_full,"before:",self.patterns[pattern_full])
                for [response,turn_num] in self.patterns[pattern_full]:
                    score = len(pattern_full) ** self.pattern_length_exponent / (len(self.moves) - turn_num) ** self.pattern_age_exponent
                    if best_pattern_score == None or score > best_pattern_score:
                        best_pattern_match = pattern_full
                        best_pattern_score = score
                        best_pattern_response = response
                    # this could be much smarter about aggregating previous responses
        if best_pattern_response:
            move = self.counter_moves[best_pattern_response]
        else:
            # fall back to playing nice
            move = "C"
        self.moves.append(move)
        self.debug and print("I choose",move)
        return move

Этот бот просматривает предыдущие вхождения недавнего игрового состояния, чтобы увидеть, как противник отреагировал на эти вхождения, с предпочтением более длинных матчей и более недавних матчей, а затем выполняет ход, который «превзойдет» предсказанный ход оппонента. Есть много возможностей для того, чтобы он был умнее со всеми данными, которые он отслеживает, но у меня не хватило времени поработать над этим.

нефрит

class Jade:
    def __init__(self):
        self.dRate = 0.001
        self.nRate = 0.003

    def round(self, last):
        if last == 'D':
            self.dRate *= 1.1
            self.nRate *= 1.2
        elif last == 'N':
            self.dRate *= 1.03
            self.nRate *= 1.05
        self.dRate = min(self.dRate, 1)
        self.nRate = min(self.nRate, 1)

        x = random.random()
        if x > (1 - self.dRate):
            return 'D'
        elif x > (1 - self.nRate):
            return 'N'
        else:
            return 'C'

Начинается оптимистично, но становится все более и более горьким, поскольку противник отказывается сотрудничать. Множество магических констант, которые, вероятно, могут быть изменены, но это, вероятно, не будет достаточно хорошо, чтобы оправдать время.

Ансамбль

Это работает множество связанных моделей. Отдельные модели учитывают разные объемы истории и имеют возможность либо всегда выбирать ход, который оптимизирует ожидаемую разницу выплат, либо случайным образом выбирать ход пропорционально ожидаемой разнице выплат.

Затем каждый член ансамбля голосует за свой предпочтительный ход. Они получают количество голосов, равное тому, сколько они выиграли больше, чем противник (что означает, что ужасные модели получат отрицательные голоса). Какой бы ход ни выиграл, тогда выбирается голос.

(Вероятно, им следует распределить свои голоса между ходами пропорционально тому, насколько они одобряют каждый, но мне все равно, чтобы сделать это прямо сейчас.)

Он превосходит все, что опубликовано до сих пор, кроме EvaluaterBot и PatternFinder. (Один на один, он побеждает EvaluaterBot и проигрывает PatternFinder).

from collections import defaultdict
import random
class Number6:
    class Choices:
        def __init__(self, C = 0, N = 0, D = 0):
            self.C = C
            self.N = N
            self.D = D

    def __init__(self, strategy = "maxExpected", markov_order = 3):
        self.MARKOV_ORDER = markov_order;
        self.my_choices = "" 
        self.opponent = defaultdict(lambda: self.Choices())
        self.choice = None # previous choice
        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }
        self.total_payoff = 0

        # if random, will choose in proportion to payoff.
        # otherwise, will always choose argmax
        self.strategy = strategy
        # maxExpected: maximize expected relative payoff
        # random: like maxExpected, but it chooses in proportion to E[payoff]
        # argmax: always choose the option that is optimal for expected opponent choice

    def update_opponent_model(self, last):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            self.opponent[hist].C += ("C" == last)
            self.opponent[hist].N += ("N" == last)
            self.opponent[hist].D += ("D" == last)

    def normalize(self, counts):
        sum = float(counts.C + counts.N + counts.D)
        if 0 == sum:
            return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)
        return self.Choices(
            counts.C / sum, counts.N / sum, counts.D / sum)

    def get_distribution(self):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            #print "check hist = " + hist
            if hist in self.opponent:
                return self.normalize(self.opponent[hist])

        return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)

    def choose(self, dist):
        payoff = self.Choices()
        # We're interested in *beating the opponent*, not
        # maximizing our score, so we optimize the difference
        payoff.C = (3-3) * dist.C + (4-1) * dist.N + (0-5) * dist.D
        payoff.N = (1-4) * dist.C + (2-2) * dist.N + (3-2) * dist.D
        payoff.D = (5-0) * dist.C + (2-3) * dist.N + (1-1) * dist.D

        # D has slightly better payoff on uniform opponent,
        # so we select it on ties
        if self.strategy == "maxExpected":
            if payoff.C > payoff.N:
                return "C" if payoff.C > payoff.D else "D"
            return "N" if payoff.N > payoff.D else "D"
        elif self.strategy == "randomize":
            payoff = self.normalize(payoff)
            r = random.uniform(0.0, 1.0)
            if (r < payoff.C): return "C"
            return "N" if (r < payoff.N) else "D"
        elif self.strategy == "argMax":
            if dist.C > dist.N:
                return "D" if dist.C > dist.D else "N"
            return "C" if dist.N > dist.D else "N"

        assert(0) #, "I am not a number! I am a free man!")

    def update_history(self):
        self.my_choices += self.choice
        if len(self.my_choices) > self.MARKOV_ORDER:
            assert(len(self.my_choices) == self.MARKOV_ORDER + 1)
            self.my_choices = self.my_choices[1:]

    def round(self, last):
        if last: self.update_opponent_model(last)

        dist = self.get_distribution()
        self.choice = self.choose(dist)
        self.update_history()
        return self.choice

class Ensemble:
    def __init__(self):
        self.models = []
        self.votes = []
        self.prev_choice = []
        for order in range(0, 6):
            self.models.append(Number6("maxExpected", order))
            self.models.append(Number6("randomize", order))
            #self.models.append(Number6("argMax", order))
        for i in range(0, len(self.models)):
            self.votes.append(0)
            self.prev_choice.append("D")

        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }

    def round(self, last):
        if last:
            for i in range(0, len(self.models)):
                self.votes[i] += self.payoff[self.prev_choice[i]][last]

        # vote. Sufficiently terrible models get negative votes
        C = 0
        N = 0
        D = 0
        for i in range(0, len(self.models)):
            choice = self.models[i].round(last)
            if "C" == choice: C += self.votes[i]
            if "N" == choice: N += self.votes[i]
            if "D" == choice: D += self.votes[i]
            self.prev_choice[i] = choice

        if C > D and C > N: return "C"
        elif N > D: return "N"
        else: return "D"

Тестовая структура

В случае, если кто-то еще найдет это полезным, вот тестовая структура для просмотра отдельных матчей. Python2. Просто поместите всех оппонентов, которые вас интересуют, в oppents.py и измените ссылки на Ensemble на свои собственные.

import sys, inspect
import opponents
from ensemble import Ensemble

def count_payoff(label, them):
    if None == them: return
    me = choices[label]
    payoff = {
        "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
        "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
        "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
    }
    if label not in total_payoff: total_payoff[label] = 0
    total_payoff[label] += payoff[me][them]

def update_hist(label, choice):
    choices[label] = choice

opponents = [ x[1] for x 
    in inspect.getmembers(sys.modules['opponents'], inspect.isclass)]

for k in opponents:
    total_payoff = {}

    for j in range(0, 100):
        A = Ensemble()
        B = k()
        choices = {}

        aChoice = None
        bChoice = None
        for i in range(0, 100):
            count_payoff(A.__class__.__name__, bChoice)
            a = A.round(bChoice)
            update_hist(A.__class__.__name__, a)

            count_payoff(B.__class__.__name__, aChoice)
            b = B.round(aChoice)
            update_hist(B.__class__.__name__, b)

            aChoice = a
            bChoice = b
    print total_payoff

OldTitForTat

Игроку старой школы лень обновляться по новым правилам.

class OldTitForTat:
    def round(self, last):
        if(last == None)
            return "C"
        if(last == "C"):
            return "C"
        return "D"

NeverCOOP

class NeverCOOP:
    def round(self, last):
        try:
            if last in "ND":
                return "D"
            else:
                return "N"
        except:
            return "N"

Если противоположный бот имеет дефект или является нейтральным, выберите дефект. В противном случае, если это первый ход или бот противника сотрудничает, выберите нейтральный. Я не уверен, насколько хорошо это будет работать ...

LastOptimalBot

class LastOptimalBot:
    def round(self, last):
        return "N" if last == "D" else ("D" if last == "C" else "C")

Предполагается, что бот-противник всегда будет снова играть один и тот же ход, и выбирает тот, который имеет лучшую отдачу от него.

Сред:

Me   Opp
2.6  2    vs TitForTat
5    0    vs AllC
4    1    vs AllN
3    2    vs AllD
3.5  3.5  vs Random
3    2    vs Grudger
2    2    vs LastOptimalBot
1    3.5  vs TatForTit
4    1    vs NeverCOOP
1    4    vs EvaluaterBot
2.28 2.24 vs NashEquilibrium

2.91 average overall

CopyCat

class CopyCat:
    def round(self, last):
        if last:
            return last
        return "C"

Копирует последний ход противника.
Я не ожидаю, что это будет хорошо, но никто еще не реализовал эту классику.

Улучшенная игра в кости Дирихле

import random

class DirichletDice2:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 1, 'N' : 1, 'D' : 1},
                N = {'C' : 1, 'N' : 1, 'D' : 1},
                D = {'C' : 1, 'N' : 1, 'D' : 1}
        )
        self.myLast = [None, None]
        self.payoff = dict(
                C = { "C": 0, "N": 3, "D": -5 },
                N = { "C": -3, "N": 0, "D": 1 },
                D = { "C": 5, "N": -1, "D": 0 }
        )

    def DirichletDraw(self, key):
        alpha = self.alpha[key].values()
        mu = [random.gammavariate(a,1) for a in alpha]
        mu = [m / sum(mu) for m in mu]
        return mu

    def ExpectedPayoff(self, probs):
        expectedPayoff = {}
        for val in ['C','N','D']:
            payoff = sum([p * v for p,v in zip(probs, self.payoff[val].values())])
            expectedPayoff[val] = payoff
        return expectedPayoff

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #draw probs for my opponent's roll from Dirichlet distribution and then return the optimal response
        mu = self.DirichletDraw(self.myLast[0])
        expectedPayoff = self.ExpectedPayoff(mu)
        res = max(expectedPayoff, key=expectedPayoff.get)

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res    

Это улучшенная версия Dirichlet Dice. Вместо того, чтобы брать ожидаемое мультиномиальное распределение из распределения Дирихле, оно выбирает мультиномиальное распределение случайным образом из распределения Дирихле. Затем вместо того, чтобы рисовать из многочлена и давать на него оптимальный ответ, он дает оптимальный ожидаемый ответ на данный многочлен, используя точки. Таким образом, случайность существенно сместилась с многочленного тиража к тиражу Дирихле. Кроме того, приоры теперь более плоские, чтобы стимулировать исследования.

Он «улучшен», потому что теперь он учитывает систему баллов, давая наилучшее ожидаемое значение по отношению к вероятностям, в то же время сохраняя ее случайность, рисуя сами вероятности. Раньше я пытался просто получить наилучшую ожидаемую отдачу от ожидаемых вероятностей, но это плохо сработало, потому что он просто застрял и не исследовал достаточно, чтобы обновить свои кости. Также это было более предсказуемым и пригодным для использования.

Исходное представление:

Dirichlet Dice

import random

class DirichletDice:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 2, 'N' : 3, 'D' : 1},
                N = {'C' : 1, 'N' : 2, 'D' : 3},
                D = {'C' : 3, 'N' : 1, 'D' : 2}
        )

        self.Response = {'C' : 'D', 'N' : 'C', 'D' : 'N'}
        self.myLast = [None, None]

    #expected value of the dirichlet distribution given by Alpha
    def MultinomialDraw(self, key):
        alpha = list(self.alpha[key].values())
        probs = [x / sum(alpha) for x in alpha]
        outcome = random.choices(['C','N','D'], weights=probs)[0]
        return outcome

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #predict opponent's move based on my last move
        predict = self.MultinomialDraw(self.myLast[0])
        res = self.Response[predict]

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res

По сути, я предполагаю, что ответ оппонента на мой последний выходной сигнал является многочленной переменной (взвешенная игральная кость), по одной для каждого из моих выходных данных, поэтому есть игральная кость для «C», одна для «N» и одна для «D» , Так что, если мой последний бросок был, например, «N», то я бросаю «N-кубик», чтобы угадать, каким будет их ответ на мой «N». Я начинаю с предварительного Дирихле, который предполагает, что мой оппонент несколько «умен» (более вероятно, что он сыграет тот, кто лучше всех выиграл по сравнению с моим последним броском, с наименьшей вероятностью сыграет тот, кто выиграл хуже). Я генерирую «ожидаемое» мультиномиальное распределение из соответствующего предварительного Дирихле (это ожидаемое значение распределения вероятностей по весам их игральных костей). Я бросаю взвешенные кости из моего последнего выхода,

Начиная с третьего раунда, я делаю байесовское обновление соответствующего Dirichlet перед последним ответом моего оппонента на то, что я сыграл два раунда назад. Я пытаюсь итеративно узнать их веса.

Я мог бы также просто выбрать ответ с наилучшим «ожидаемым» результатом, когда генерировал кости, вместо того, чтобы просто бросать кости и отвечать на результат. Однако я хотел сохранить случайность, чтобы мой бот был менее уязвим к тем, кто пытается предсказать паттерн.

Kevin

class Kevin:
    def round(self, last):      
        return {"C":"N","N":"D","D":"C",None:"N"} [last]

Выбирает худший выбор. Худший бот сделан.

Бесполезный

import random

class Useless:
    def __init__(self):
        self.lastLast = None

    def round(self, last):
        tempLastLast = self.lastLast
        self.lastLast = last

        if(last == "D" and tempLastLast == "N"):
            return "C"
        if(last == "D" and tempLastLast == "C"):
            return "N"

        if(last == "N" and tempLastLast == "D"):
            return "C"
        if(last == "N" and tempLastLast == "C"):
            return "D"

        if(last == "C" and tempLastLast == "D"):
            return "N"
        if(last == "C" and tempLastLast == "N"):
            return "D"

        return random.choice("CND")

Он просматривает последние два хода, сделанные противником, и выбирает самое незавершенное, иначе он выбирает что-то случайное. Вероятно, есть лучший способ сделать это.

Исторический Средний

class HistoricAverage:
    PAYOFFS = {
        "C":{"C":3,"N":1,"D":5},
        "N":{"C":4,"N":2,"D":2},
        "D":{"C":0,"N":3,"D":1}}
    def __init__(self):
        self.payoffsum = {"C":0, "N":0, "D":0}
    def round(this, last):
        if(last != None):
            for x in this.payoffsum:
               this.payoffsum[x] += HistoricAverage.PAYOFFS[last][x]
        return max(this.payoffsum, key=this.payoffsum.get)

Рассматривает историю и находит действие, которое было бы лучше всего в среднем. Начинается кооператив.

Средневзвешенное

class WeightedAverageBot:
  def __init__(self):
    self.C_bias = 1/4
    self.N = self.C_bias
    self.D = self.C_bias
    self.prev_weight = 1/2
  def round(self, last):
    if last:
      if last == "C" or last == "N":
        self.D *= self.prev_weight
      if last == "C" or last == "D":
        self.N *= self.prev_weight
      if last == "N":
        self.N = 1 - ((1 - self.N) * self.prev_weight)
      if last == "D":
        self.D = 1 - ((1 - self.D) * self.prev_weight)
    if self.N <= self.C_bias and self.D <= self.C_bias:
      return "D"
    if self.N > self.D:
      return "C"
    return "N"

Поведение оппонента моделируется как прямоугольный треугольник с углами для CND в 0,0 0,1 1,0 соответственно. Каждое движение противника сдвигает точку в пределах этого треугольника к этому углу, и мы играем, чтобы побить ход, обозначенный точкой (с C, дающим регулируемо маленький срез треугольника). Теоретически я хотел, чтобы это имело более длинную память с большим весом к предыдущим ходам, но на практике текущая мета предпочитает быстро меняющихся ботов, так что это превращается в приближение LastOptimalBot против большинства врагов. Размещение для потомков; может быть, кто-то будет вдохновлен.

слово из четырех букв

import itertools

class Tetragram:
    def __init__(self):
        self.history = {x: ['C'] for x in itertools.product('CND', repeat=4)}
        self.theirs = []
        self.previous = None

    def round(self, last):
        if self.previous is not None and len(self.previous) == 4:
            self.history[self.previous].append(last)
        if last is not None:
            self.theirs = (self.theirs + [last])[-3:]

        if self.previous is not None and len(self.previous) == 4:
            expected = random.choice(self.history[self.previous])
            if expected == 'C':
                choice = 'C'
            elif expected == 'N':
                choice = 'C'
            else:
                choice = 'N'
        else:
            choice = 'C'

        self.previous = tuple(self.theirs + [choice])
        return choice

Попытайтесь найти образец в движениях противника, предполагая, что они также наблюдают наш последний ход.

Рукопожатие

class HandshakeBot:
  def __init__(self):
    self.handshake_length = 4
    self.handshake = ["N","N","C","D"]
    while len(self.handshake) < self.handshake_length:
      self.handshake *= 2
    self.handshake = self.handshake[:self.handshake_length]
    self.opp_hand = []
    self.friendly = None
  def round(self, last):
    if last:
      if self.friendly == None:
        # still trying to handshake
        self.opp_hand.append(last)
        if self.opp_hand[-1] != self.handshake[len(self.opp_hand)-1]:
          self.friendly = False
          return "D"
        if len(self.opp_hand) == len(self.handshake):
          self.friendly = True
          return "C"
        return self.handshake[len(self.opp_hand)]
      elif self.friendly == True:
        # successful handshake and continued cooperation
        if last == "C":
          return "C"
        self.friendly = False
        return "D"
      else:
        # failed handshake or abandoned cooperation
        return "N" if last == "D" else ("D" if last == "C" else "C")
    return self.handshake[0]

Признает, когда он играет против себя, а затем сотрудничает. В противном случае имитирует LastOptimalBot, который выглядит как лучшая однострочная стратегия. Работает хуже, чем LastOptimalBot, на величину, обратно пропорциональную количеству раундов. Очевидно, было бы лучше, если бы в поле было больше копий * кашель ** подмигивание *.

ShiftingOptimalBot

class ShiftingOptimalBot:
    def __init__(self):
        # wins, draws, losses
        self.history = [0,0,0]
        self.lastMove = None
        self.state = 0
    def round(self, last):
        if last == None:
            self.lastMove = "C"
            return self.lastMove
        if last == self.lastMove:
            self.history[1] += 1
        elif (last == "C" and self.lastMove == "D") or (last == "D" and self.lastMove == "N") or (last == "N" and self.lastMove == "C"):
            self.history[0] += 1
        else:
            self.history[2] += 1

        if self.history[0] + 1 < self.history[2] or self.history[2] > 5:
            self.state = (self.state + 1) % 3
            self.history = [0,0,0]
        if self.history[1] > self.history[0] + self.history[2] + 2:
            self.state = (self.state + 2) % 3
            self.history = [0,0,0]

        if self.state == 0:
            self.lastMove = "N" if last == "D" else ("D" if last == "C" else "C")
        elif self.state == 1:
            self.lastMove = last
        else:
            self.lastMove = "C" if last == "D" else ("N" if last == "C" else "D")
        return self.lastMove

Этот бот использует алгоритм LastOptimalBot, пока он выигрывает. Однако, если другой бот начинает предсказывать это, он начинает играть с того хода, который его противник сыграл последним (это ход, который превосходит ход, который побьет LastOptimalBot). Он перебирает простые транспонирования этих алгоритмов до тех пор, пока он продолжает проигрывать (или когда ему надоедает много рисовать).

Честно говоря, я удивлен, что LastOptimalBot находится на пятом месте, когда я публикую это. Я вполне уверен, что это будет лучше, если я правильно написал этот питон.

HandshakePatternMatch

from .patternfinder import PatternFinder
import collections

class HandshakePatternMatch:
    def __init__(self):
        self.moves = [None]
        self.other = []
        self.handshake = [None,"N","C","C","D","N"]
        self.friendly = None
        self.pattern = PatternFinder()
    def round(self, last):
        self.other.append(last)
        if last:
            if len(self.other) < len(self.handshake):
                # still trying to handshake
                if self.friendly == False or self.other[-1] != self.handshake[-1]:
                    self.friendly = False
                else:
                    self.friendly = True
                move = self.handshake[len(self.other)]
                self.pattern.round(last)
            elif self.friendly == True:
                # successful handshake and continued cooperation
                move = self.pattern.round(last)
                if last == "C":
                    move = "C"
                elif last == self.handshake[-1] and self.moves[-1] == self.handshake[-1]:
                    move = "C"
                else:
                    self.friendly = False
            else:
                # failed handshake or abandoned cooperation
                move = self.pattern.round(last)
        else:
            move = self.handshake[1]
            self.pattern.round(last)
        self.moves.append(move)
        return move

Почему шаблон соответствует самому себе? Рукопожатие и сотрудничество.

Запрограммированный

class Hardcoded:
    sequence = "DNCNNDDCNDDDCCDNNNNDDCNNDDCDCNNNDNDDCNNDDNDDCDNCCNNDNNDDCNNDDCDCNNNDNCDNDNDDNCNDDCDNNDCNNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNNDDNDCDNCNDDCDNNDDCCNDNNDDCNNNDCDNDDCNNNNDNDDCDNCDCNNDNNDDCDNDDCCNNNDNDDCNNNDNDCDCDNNDCNNDNDDCDNCNNDDCNDNNDDCDNNDCDNDNCDDCNNNDNDNCNDDCDNDDCCNNNNDNDDCNNDDCNNDDCDCNNDNNDDCDNDDCCNDNNDDCNNNDCDNNDNDDCCNNNDNDDNCDCDNNDCNNDNDDCNNDDCDNCNNDDCDNNDCDNDNCDDCNDNNDDCNNNDDCDNCNNDNNDDCNNDDNNDCDNCNDDCNNDCDNNDDCNNDDNCDCNNDNDNDDCDNCDCNNNDNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNDNDNCDDCDCNNNNDNDDCDNCNDDCDNNDDCNNNDNDDCDNCNNDCNNDNDDNCDCDNNNDDCNNDDCNNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDDNDDCNCDNNDCDNNNDDCNNDDCDCDNNDDCNDNCNNDNNDNDNDDCDNCDCNNNDNDDCDNCNNDDCDNNDCNNDDCNNDDCDCDNNDDCNDNCNNNDDCDNNDCDNDNCNNDNDDNNDNDCDDCCNNNDDCNDNDNCDDCDCNNNDNNDDCNDCDNDDCNNNNDNDDCCNDNNDDCDCNNNDNDDNDDCDNCCNNDNNDDCNNDDCDCNNDNNDDCNNDDNCNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDNDDCNNDDNCDCDNNDCNNDNDDCDCDNNNNDDCNNDDNDCCNNDDNDDCNCDNNDCNNDDNDDCDNCNDDCNNNNDCDNNDDCNDNDDCDNCNNDCDNNDCNNDNDDNCDCNNDNDDCDNDDCCNNNNDNDDCNNDDCDCNNDNNDDCDCDNNDDC"
    def __init__(self):
        self.round_num = -1
    def round(self,_):
        self.round_num += 1
        return Hardcoded.sequence[self.round_num % 1000]

Просто воспроизводит жестко запрограммированную последовательность ходов, оптимизированных для победы над некоторыми из лучших детерминированных ботов.