Код для крестиков-ноликов. Продолжение

Код для крестиков-ноликов. Агент

Здравствуйте и вновь добро пожаловать на занятия по теме «Искусственный интеллект: обучение с подкреплением на языке Python».

В этой лекции мы поговорим о втором главном классе файла игры в крестики-нолики – классе агента, а в заключение подведем итоги.

Мы уже знаем, что это ИИ или нечто, содержащее ИИ. В этом проявляется отличие от «обычного» машинного обучения, поскольку в данном случае мы не просто снабжаем это нечто данными. Вместо этого агент должен взаимодействовать со средой, которую только что обсуждали. Наш маленький однострочный алгоритм обучения будет очень малой частью агента и в то же время будет на 100% отвечать за его интеллект.

Начнёмс обзора всех нужных нам методов экземпляра. Первая функция – setV, позволяющая инициировать функцию ценности. Изболее раннего обсуждения вы знаете, что функция ценности должна бытьинициирована весьма специфичным образом. Далее идёт set_symbol, позволяющая присвоить агенту символ, которым онбудет играть на поле. Далее – set_verbose, принимающая логическое значение. Эта функцияделает именно то, что написано в её названии – выводит больше информации (verbose – подробный), если имеет значение«истина». Так, например, она выводит на экран поле вместе с ценностями каждогоследующего возможного хода, перед тем как агент сделает свой ход. Затем идёт reset_history. Она нужна всвязи с тем, что нам необходимо отслеживать историю состояний в каждом эпизоде,но когда эпизод заканчивается и мы завершили обучение, история его состоянийнам больше не нужна, а мы можем начинать новый эпизод. Далее идёт take_action со средой вкачестве аргумента. Данная функция проверяет поле на предмет корректных ходов иделает ход, основываясь на избранной стратегии. Как вы помните, в этой игре мыиспользуем эпсилон-жадную стратегию. Затем у нас есть update_state_history, котораядобавляет состояние в историю состояний. Это не включается в функцию take_action, поскольку тавызывается только через ход, когда ходит соответствующий игрок, тогда какисторию состояний нужно обновлять при ходе любого из игроков. И наконец, идётфункция update, у которой также аргументом является среда. Оназапрашивает у среды последнее вознаграждение, соответствующее концу эпизода,поскольку вызывается эта функция только в конце эпизода. Именно здесь ипроисходит всё обучение.

Первыепять этих функций довольно тривиальны. Конструктор инициирует значение ε, необходимое для реализацииэпсилон-жадного алгоритма, а также значение α,которое представляет коэффициент обучения для нашего уравнения обновления.Кроме того, функции verbose присваиваетсяпо умолчанию значение «ложь», а state_history, как и следует ожидать, представляетпустой список. Функция setV присваиваетсимволы для обоих игроков, а reset_history вновь сбрасывает историю до пустогосписка:

class Agent:

  def __init__(self, eps=0.1, alpha=0.5):

    self.eps =eps # probability of choosing random action instead of greedy

    self.alpha =alpha # learning rate

    self.verbose= False

   self.state_history = []

  def setV(self, V):

    self.V = V

  def set_symbol(self, sym):

    self.sym =sym

  def set_verbose(self, v):

    # if true,will print values for each position on the board

    self.verbose= v

  def reset_history(self):

   self.state_history = []

Далее у нас идёт функция take_action. Не забывайте, что у нас эпсилон-жадныйалгоритм, то есть мы выполняем случайное действие с вероятностью ε. Обратите внимание, что при значении verbose «истина» на экран выводится сообщение «Taking arandom action»(«Предпринимается случайное действие»). Однако чтобы предпринять такоедействие, необходимо составить список всех возможных ходов, что эквивалентносписку всех позиций на поле, для которых is_empty имеет значение «истина». Мы можем вызвать этуфункцию, потому что описали её в классе среды Environment.Составив список всех возможных ходов, мы с равной для всех вероятностью выбираемодин из них:

  def take_action(self, env):

    # choose anaction based on epsilon-greedy strategy

    r =np.random.rand()

    best_state =None

    if r <self.eps:

      # take arandom action

      ifself.verbose:

        print“Taking a random action”

      possible_moves= []

      for i in xrange(LENGTH):

        for j inxrange(LENGTH):

          ifenv.is_empty(i, j):

           possible_moves.append((i, j))

      idx =np.random.choice(len(possible_moves))

      next_move= possible_moves[idx]

    else:

Далееидёт «жадная» часть эпсилон-жадного алгоритма. В своём простейшем виде онаочень схожа на случайную стратегию: мы перебираем по циклу все позиции на поле,проверяем, пусты ли они, и если пусты – проверяем их ценность. Если этаценность больше, чем текущее наибольшее значение ценности, то отслеживаем этуценность и эту позицию, установив её в качестве нового наибольшего значенияценности. Сделав это, можно помещать свой символ на выбранное место. Однако«жадная» часть несколько усложняется, если учесть необходимость вывода на экранболее подробной информации. Нам нужно вывести поле со всеми значениямиценности, которые «видит» агент, поскольку именно они используются для принятиярешения. Таким образом, в первом цикле мы должны создать отображение координат(i,j) и соответствующейценности. Затем, если функция verbose имеет значение«истина», мы выводим на экран всё поле и, если позиция пуста, выводим еёценность, в противном случае – выводим символ, занимающий данную позицию поля:

    …

    else:

      pos2value= {} # for debugging

      next_move= None

      best_value= -1

      for i in xrange(LENGTH):

        for j inxrange(LENGTH):

          ifenv.is_empty(i, j):

            #what is the state if we made this move?

           env.board[i,j] = self.sym

           state = env.get_state()

           env.board[i,j] = 0 # don’t forget to change it back!

           pos2value[(i,j)] = self.V[state]

            ifself.V[state] > best_value:

             best_value = self.V[state]

             best_state = state

             next_move = (i, j)

      # ifverbose, draw the board w/ the values

      ifself.verbose:

        print“Taking a greedy action”

        for i inxrange(LENGTH):

          print“—————–“

          for jin xrange(LENGTH):

            ifenv.is_empty(i, j):

              #print the value

             print “%.2f|” % pos2value[(i,j)],

           else:

             print ” “,

              ifenv.board[i,j] == env.x:

               print “x |”,

             elif env.board[i,j] == env.o:

               print “o |”,

             else:

               print ”  |”,

          print“”

        print“—————–“

Следующей идёт функция update_state_history, весьма тривиальная. Как вы уже знаете, история состояний хранится в видесписка, поэтому мы просто должны добавлять значения в этот список. Мы могли быиспользовать класс Environment и вызватьфункцию get_state, но незабывайте, что для этого требуются вычисления, а кроме того, нам нужнообновлять историю состояний для обоих агентов на каждом ходу, поэтому быстреевычислить её один раз и вставить сюда:

  defupdate_state_history(self, s):

    # cannot putthis in take_action, because take_action only happens

    # once everyother iteration for each player

    # statehistory needs to be updated every iteration

    # s =env.get_state() # don’t want to do this twice so pass it in

    self.state_history.append(s)

Инаконец, у нас есть функция update. Напомню, чтосейчас мы используем её только в конце эпизода; это будет не так для всехпоследующих изучаемых нами алгоритмов. Это значит, что когда мы получаемвознаграждение от среды, это будет 1 при выигрыше и 0 при проигрыше или ничьей.В связи с этим обстоятельством мы должны просмотреть историю состояний вобратном порядке, поскольку обновление ценностей для текущего состояния зависитот ценности следующего состояния. Как можно видеть, первая целевая переменная вточности равна окончательному вознаграждению в игре, однако все последующиецелевые переменные являются лишь оценками ценности в надежде, что все этиоценки ценностей со временем сойдутся. После этого мы очищаем историю,поскольку она нам больше не нужна и мы не хотим, чтобы она фигурировала вбудущих вычислениях:

  def update(self, env):

    # we want toBACKTRACK over the states, so that:

    #V(prev_state) = V(prev_state) + alpha*(V(next_state) – V(prev_state))

    # whereV(next_state) = reward if it’s the most current state

    #

    # NOTE: weONLY do this at the end of an episode

    # not so forall the algorithms we will study

    reward =env.reward(self.sym)

    target =reward

    for prev in reversed(self.state_history):

      value =self.V[prev] + self.alpha*(target – self.V[prev])

     self.V[prev] = value

      target =value

    self.reset_history()

Код для крестиков-ноликов. Главный цикл и демонстрация

Теперь пройдёмся по оставшемуся коду для нашей игры в крестики-нолики. Мы уже познакомились с двумя важнейшими частями – агентом и средой, – так что нам остался лишь код, заставляющий их взаимодействовать, а также остальные разные детали.

Вначале рассмотрим класс Human. Вряд ли есть большой смысл в том, чтобы просто обучить ИИ играть в крестики-нолики и не иметь возможности проверить, насколько он хорош. Поэтому для того, чтобы можно было интуитивно прочувствовать, как думает наш ИИ, мы и создаём этот класс, чтобы иметь возможность сыграть против ИИ. При этом функции verbose присваивается значение «истина», чтобы можно было видеть ценность каждой позиции при каждом ходе ИИ. Заметьте, что, вероятно, мы делаем тоже самое, только бессознательно: мы смотрим на каждую из возможных позиций и проделываем очень быстрые вычисления, чтобы определить, какая из них лучше. Обратите также внимание, что в классе Human есть фиктивные функции. Это связано с тем, что, как вы увидите позже, функция play_game не различает тип агента и всегда вызывает одни и те же функции, для чего нам и нужны некоторые заполнители.

class Human:

  def __init__(self):

    pass

  def set_symbol(self, sym):

    self.sym =sym

  def take_action(self, env):

    while True:

      # break ifwe make a legal move

      move =raw_input(“Enter coordinates i,j for your next move (i,j=0..2): “)

      i, j =move.split(‘,’)

      i = int(i)

      j = int(j)

      ifenv.is_empty(i, j):

       env.board[i,j] = self.sym

        break

  def update(self, env):

    pass

  def update_state_history(self, s):

    pass

Теперь рассмотрим функцию play_game. У неё три обязательных аргумента, соответствующих двум игрокам и среде. Кроме того, в качестве аргумента у неё есть параметр draw, который отрисовывает поле, если имеет значение «истина». Он явно понадобится, если играет человек.

Внутрифункции мы отслеживаем текущего игрока, причём первый игрок всегда получаетзначение «игрок 1». Далее мы входим в цикл, заканчивающийся при окончании игры.Первая часть цикла позволяет нам переключаться между игроками и заставляетигрока 1 ходить первым.

def play_game(p1, p2, env, draw=False):

  # loops untilthe game is over

  current_player= None

  while notenv.game_over():

    # alternatebetween players

    # p1 alwaysstarts first

    ifcurrent_player == p1:

     current_player = p2

    else:

      current_player = p1

Посколькунам нет нужды отрисовывать поле, пока ИИ не походил, мы позволяем переменной draw принимать значения 1 и 2 – 1 для игрока 1 и 2 дляигрока 2. В этом случае доска отрисовывается только один раз на каждом ходу итолько для соответствующего игрока.

def play_game(p1, p2, env, draw=False):

  …

  while notenv.game_over():

    …

    # draw theboard before the user who wants to see it makes a move

    if draw:

      if draw ==1 and current_player == p1:

       env.draw_board()

      if draw ==2 and current_player == p2:

        env.draw_board()

Следующийэтап для агента – выполнение действия, а затем – обновление истории состоянийдля всех агентов. Когда цикл завершается, мы в последний раз прорисовываемдоску, чтобы было видно, кто выиграл. Затем обновляем функцию ценности,поскольку эпизод завершён.

def play_game(p1, p2, env, draw=False):

  Цикл…

    # currentplayer makes a move

   current_player.take_action(env)

    # updatestate histories

    state =env.get_state()

   p1.update_state_history(state)

   p2.update_state_history(state)

  if draw:

   env.draw_board()

  # do the valuefunction update

  p1.update(env)

  p2.update(env)

В разделе скрипта main мы видим, как используется функция play_game, поскольку нам необходимо запустить множество эпизодов, чтобы агент изучил игру на достаточном уровне. Вначале мы создаём два ИИ. Следующие несколько этапов целиком посвящены их инициации. Прежде всего мы инициируем их функции ценности, не забывая, что они различны для различных агентов, в зависимости от того, кто из них играет крестиками, а кто – ноликами. Мы также устанавливаем их символы.

if __name__ == ‘__main__’:

  # train theagent

  p1 = Agent()

  p2 = Agent()

  # set initialV for p1 and p2

  env =Environment()

 state_winner_triples = get_state_hash_and_winner(env)

  Vx =initialV_x(env, state_winner_triples)

  p1.setV(Vx)

  Vo =initialV_o(env, state_winner_triples)

  p2.setV(Vo)

  # give eachplayer their symbol

 p1.set_symbol(env.x)

 p2.set_symbol(env.o)

Послеэтого проводим 10 000 игр «ИИ против ИИ». Технически здесь можно было бысоздать метод для сброса среды, но я этого не делал. Вместо этого мы на каждойитерации просто создаём новую среду.

  T = 10000

  for t in xrange(T):

    if t % 200== 0:

      print t

   play_game(p1, p2, Environment())

Наконец, когда ИИ закончил обучение, можно самому с ним сыграть. Поэтому мы создаём объект Human и даём ему сыграть ноликами. Функции verbose мы даём значение «истина», чтобы можно было увидеть используемую ИИ для принятия решений функцию ценности. Здесь я выбрал в качестве игрока 1 агента, поскольку хотел увидеть, выберет ли он хорошую начальную позицию на поле для крестиков-ноликов, но вы можете поэкспериментировать и с другими конфигурациями этого скрипта.

  # playhuman vs. agent

  # do you thinkthe agent learned to play the game well?

  human =Human()

 human.set_symbol(env.o)

  while True:

    p1.set_verbose(True)

   play_game(p1, human, Environment(), draw=2)

    # I made theagent player 1 because I wanted to see if it would

    # select thecenter as its starting move. If you want the agent

    # to gosecond you can switch the human and AI.

    answer =raw_input(“Play again? [Y/n]: “)

    if answerand answer.lower()[0] == ‘n’:

      break

Атеперь запустим программу и посмотрим, что у нас получится.

Итак,мы видим, что агент для игры в крестики-нолики знает, что центр – лучшее местодля начала игры. Поставим нолик в углу с координатами (0, 2). Агент знает, каквыстроить крестики. Посмотрим, удастся ли нам выиграть. Поставим свой символ покоординатам (2, 2). Итак, ИИ также знает, как выигрывать.

Сыграемещё раз. Ставим нолик по координатам (0, 2), но теперь заблокируем агента дляигры в крестики-нолики, поставив символ по координатам (2, 1). Он вновьпытается выстроить ряд. Снова его заблокируем, поставив (1, 0). Теперь, видимо,никто не выиграет. Ничья.

Сыграем ещё раз. Походим теперь по-другому. Пусть это будут координаты (1, 2). Агент решил, что угол – лучшее место для хода. Заблокируем агента, поставив (0, 0), – и агент делает прекрасный ход, после которого мы выиграть не можем: если мы попытаемся заблокировать его в одном месте, он поставит крестик в другом и наоборот. Итак, агент весьма хорошо играет в крестики-нолики. Закончим игру. Агент весьма хорош.

Крестики-нолики. Итоги

Настало время подвести итоги всего раздела, поскольку он был крайне длинным. Удивительно, что всё, что мы сделали, – это только для того, чтобы сыграть в крестики-нолики, причём в курсе мы ещё даже не знакомились с основными алгоритмами обучения с подкреплением.

Вначалея просил вас подумать о том, как бы вы решили задачу игры в крестики-нолики,если бы были неискушённым первокурсником, изучающим программирование. Ответсостоял в том, что мы бы в конце концов создали агента из ряда условныхоператоров. Он бы не приспосабливался к среде и не ставал бы всё лучшим игрокомпо мере увеличения количества сыгранных игр. Поэтому даже если бы вначале он иказался бы умным, он никогда не смог бы повысить свой интеллект. Более того,алгоритм нельзя было бы обобщить для новых игр, он работал бы только длякрестиков-ноликов. Поэтому мы и взялись за этот курс, чтобы отыскатьдействительно «умные» алгоритмы, позволяющие ИИ решать любые задачи призаданных правильных вознаграждениях.

Далеемы внимательнее рассмотрели компоненты системы обучения с подкреплением. Мыопределили понятия агента, среды, состояния, действия и вознаграждения. Мыпоговорили о том, как конкретные структуры вознаграждений могут привести кнеудовлетворительным результатам и в связи с этим – о необходимости тщательногоих выбора. Это похоже на выбор вознаграждения для собаки, чтобы научить еёхорошо себя вести. Кроме того, мы познакомились с новыми терминами – эпизод иконечное состояние, которые нам понадобились, чтобы полностью понять алгоритм,использованный для игры в крестики-нолики.

Затеммы рассмотрели проблему присвоения коэффициентов доверия и тесно связанное сней понятие отложенного вознаграждения. Суть в том, что действие,предпринимаемое сейчас, может не вести к немедленному большому вознаграждению,но может максимизировать вознаграждение будущее, а потому необходимо иметьспособность разумно планировать. Это используется в основе идеи функцииценности. Мы видели, что на основе того, как обновляется функция ценности, еслиона правильно инициирована (например, когда ценность конечного состояния равна1 при выигрыше и 0 в противном случае), значение ценности будетраспространяться в обратном направлении по истории состояний. Мы понемногувыполняли это итерационное обновление в конце каждого эпизода так, что тольковозможные последующие состояния могли влиять на предыдущее.

Инаконец мы объединили это всё в коде, и вы убедились, что алгоритмдействительно работает и что агент для игры в крестики-нолики, обучившись игре,делает разумные ходы.

Теперь,когда у вас появился некоторый опыт в обучении с подкреплением, любопытнооглянуться назад и попытаться сравнить его с обучением с учителем. Тутвозникает очень распространённый вопрос: почему мы не можем просто создатьмодель обучения с учителем, которая напрямую бы отождествляла состояния идействия?

Перваяпроблема – как использовать метки? Как вы уже видели, пространство состоянийчрезвычайно быстро становится слишком большим, чтобы состояния можно былоперечислить. Крестики-нолики или «4 в ряд» – это, вероятно, предел. Апредставьте себе видеоигру с HD-графикой и кадровойчастотой в 60 FPS – тут у нас миллионы пикселей с сотнями значенийдля каждого из них, и таких 60 в секунду. Количество возможных состояний вподобной игре столь велико, что трудно даже представить, так что создатьнадлежащие метки не получится. Играет свою роль и то, что метки толькоуказывают, правы мы или нет; вознаграждение же более гибкое и даёт большеинформации, поскольку указывает, насколько мы правы или неправы, то естьпоказывает, насколько мы хороши.

Вознаграждениеявляется отложенным, однако информация о нём встроена в функцию ценности. Еслимы попытаемся выбрать лучшее действие для конкретного состояния (предполагая,что мы каким-то образом обошли проблему необходимости иметь метки для растущегопо экспоненте набора данных), нам всё равно необходимо выбирать лучшее действие,основываясь на всех возможных будущих вознаграждениях. Это значит, что намнужно вычислять ценность каждого состояния и выбирать лучшее действие,основываясь на этих значениях ценности. Другими словами, вместо того чтобыпозволить алгоритму так вычислять ценность, чтобы автоматически учитывалосьотложенное вознаграждение, нам придётся каким-то образом самим отслеживать всеэти величины.

Крометого, в вознаграждении может быть доля случайности, то есть иногда, переходя внекоторое состояние, мы получаем вознаграждение 1, а иногда – 0. Это как еслибы вы готовились к завтрашнему экзамену, но в экзаменационный день началасьметель и экзамен отменили. Следующие состояния также могут быть случайными.

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

Наконец, обучение с подкреплением в высшей степени оперативно: мы учимся в процессе игры. Каждый раз, когда агент для игры в крестики-нолики заканчивает эпизод, он становится лучше. Сравните это с деревом решений – оно берёт сразу все учебные данные и создаёт дерево, основанное на них. Если мы захотим включить новые данные в дерево, нам придётся вновь начинать всё сначала.

Надеюсь, всё это дало вам некоторое представление о том, почему при кажущейся возможности использовать обучение с учителем для решения задач обучения с подкреплением в действительности это невозможно.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: