Пишем AI для roshambo на питоне

Игра RoShamBo(камень-ножницы-бумага) - имеет равновесие Нэша. Чтобы не проиграть, достаточно выбирать ходы(камень, ножницы или бумага) случайным образом. Выиграть у такого игрока на бесконечной дистанции невозможно.

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

Создадим бота, который может играть на http://www.rpscontest.com. Поиграть с ним, будучи человеком, можно здесь а полный исходный код доступен тут.

API у сайта достаточно прост - предыдущий ход соперника получаем через переменную input, свой отдаем через переменную output в виде 'R', 'P' или 'S'. Если input равен ''(пустой строке) - это первый раунд, его можно использовать для инициализации наших алгоритмов и структур, а в остальных случаях - играем.

Таким образом, в глобальном скопе имеем следующий код:

    if input == '':
        tp = treePredictor()
        output = tp.predict()    
    else:
        tp.store(input)
        output = tp.predict()

Будем считать, что ход соперника неслучайным образом зависит от результата его предыдущего хода. Например, если он сыграл 'R'(камень) и проиграл бумаге - следующий раз он сыграет ножницы, а если выиграл - повторит камень. Или, возможно, он наоборот, склонен менять ход после победы, и ходить так же, после ничьей.

Для удобства подсчета статистики, введем понятие roll(поворот). Поворот на величину 0 делает из камня-камень, из ножниц-ножницы итп. На 1 - из камня - ножницы, из ножниц- бумагу, из бумаги - камень. На 2 - из камня - бумагу, из бумаги - ножницы, из ножниц - камень.

Таким образом, для записи статистики ходов соперника нам нужна матрица 3*3(3 результата - победа, ничья и поражение, на 3 поворота - 0, 1 и 2). Далее после каждого хода мы увеличиваем соответствующий счетчик матрицы и получаем статистику, после чего можем предсказать ход соперника и сделать свой ход, который его побьет.

Метод store, записывающий статистику, выглядит так:

    def store(self, c):

        i1 = self.choices.index(c)

        if not (self.prevchoice is None or self.prevres is None):
            roll = self.getRollbyInd(self.prevchoice, i1)
            for i in range(3):
                for j in range(3):
                    self.dataarr[i][j]*=0.9
            self.dataarr[self.prevres][roll]+=1


        self.prevchoice = i1
        self.prevres = self.gameRes(c,self.prevmove)

self.dataarr - это наш массив статистики, в виде матрицы 3*3. Обратите внимание, что на каждой итерации предыдущая статистика умножается на 0.9 - это сделано для того, чтобы если соперник сменит стратегию, мы быстрее к ней адаптировались.

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

    def predict(self):
        if self.prevchoice is None or self.prevres is None:
            ret= self.choices[randint(0,2)]
            self.prevmove = ret
            return ret
        arr=self.dataarr[self.prevres]

        predictedroll = weighted_choice([0,1,2], arr)
        predictedchoice = self.rollInd(self.prevchoice, predictedroll)

        choice = self.beatMat[predictedchoice]

        self.prevmove = self.choices[choice]
        return self.choices[choice]

На данный момент, бот неплохо идет в турнире с винрейтом около 70%, а я сам его обыграть не могу. Что важно, в случае, если соперник делает свои ходы достаточно случайно - бот, фактически играет тоже случайным образом, таким образом статистически имея ничью. Обыграть его можно, регулярно меняя свою стратегию с подходящей периодичностью, но это сложно подсчитывать в уме. Впрочем, в турнире есть боты, которым он проигрывает.