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

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

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

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

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

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

Вобщем виде у нас есть два главных объекта – агент и среда. На протяжении любойиз игр у нас будет два экземпляра объекта агента, и оба они будутвзаимодействовать с одним и тем же единственным экземпляром среды. Чтобызаставить их взаимодействовать, можно создать функцию play_game, аргументами которой будут агент для игрока 1,агент для игрока 2 и объект среды.

Итак,что же должно быть внутри функции play_game? Внутри, по сути, будет один цикл, чередующийсямежду двумя игроками. На каждой итерации цикла нам необходимо сделать нескольковещей. Во-первых, нужно, чтобы текущий игрок выполнил действие, обновляющеесреду; во-вторых, нужно переключать текущих игроков, чтобы они ходили по очереди;в-третьих, нужно отслеживать, когда закончилась игра, чтобы в этом случаепрервать цикл.

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 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()

    # 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)

Каквидите, мы создали частичный API для некоторыхметодов экземпляра, которые понадобятся нашим объектам. Так, среде понадобитсяфункция game_over, возвращающаябулево значение «истина», если игра закончилась, и «ложь» – если нет. Как можнопонять, для этого понадобится просмотреть поле, чтобы проверить, есть липобедитель или доска заполнена и игра закончилась вничью. Агенту понадобитсяфункция take_action с аргументомсреды, которая обновляет среду и, следовательно, состояние. Ещё однанеобходимая агенту функция – update, обновляющаявнутреннюю оценку агента функции ценности. Именно в ней используетсяобсуждавшееся нами уравнение обновления. Функция updateтакже нуждается в аргументе среды, поскольку ей придётся запрашивать из средытекущее вознаграждение.

Иещё одна функция, которая будет для нас чрезвычайно полезной, хотя и неявляется безусловно необходимой, – функция draw_board. Она показывает, какие позиции заняты на данныймомент и какими символами.

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

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

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

Ранеея обещал, что это будет сложность O(1). Один изспособов – использовать словарь, поскольку ключами словаря могут быть любые неизменяемыеобъекты. Таким образом, мы можем представить игровое поле с помощью 2-кортежаразмером 3×3 и сохранять значения внутри в качестве элементов кортежа.Однако можно сделать так, чтобы каждое состояние отображалось в виде числа, чтопозволит хранить функцию ценности в виде массива Numpy.

Итак,как же отобразить каждое состояние в виде числа? Вспомним, как мы ранее искаливерхний предел количества состояний. Мы вычислили, что это будет 39,или 19 683, что является не таким уж и большим массивом для хранения впамяти. Обратите внимание, что это число включает и невозможные состояния,например, когда крестики стоят во всех девяти клетках, хотя для выигрышадостаточно трёх, размещённых в ряд. Но такая чрезмерность вовсе не влияет наалгоритм, поэтому беспокоиться по этому поводу мы не будем. Эти состояния влюбом случае никогда не будут доступны, поскольку при каждом повторении цикламы проверяем, не закончилась ли игра, и если закончилась, то выходим из цикла.Таким образом, эти значения никогда не будут отражены в истории состояний, азначит, их ценности никогда не будут использоваться или обновляться.

Идеяналичия девяти позиций и трёх возможных значений в каждой из них должнынапоминать двоичные числа. Как вы знаете, N бит могут хранить 2N различных целых чисел, и мы можемперечислить все эти возможные значения, отыскав все перестановки строки длиной N, в которойкаждая позиция содержит только 0 или 1. Уравнение для преобразования двоичногочисла в десятичное выглядит следующим образом:

Такимобразом, всё, что нам нужно сделать, – это поменять двойку на тройку, и вместопредставления в виде только нулей и единиц получим значения в виде 0, 1 и 2:

Вкоде это будет выглядеть примерно так:

k = 0

h = 0

for i in xrange(LENGTH):

    for j inxrange(LENGTH):

        ifself.board[i, j] == 0:

            v =0

        elifself.board[i, j] == self.x:

            v =1

        elifself.board[i, j] == self.o:

            v =2

        h +=(3**k) * v

        k += 1

return h

Обратите внимание, как мы по циклу перебираем каждую позицию на поле, что потребовало вложенного цикла for, но это связано только со структурой поля. Мы должны отслеживать степень, которая начинается с 30 и умножается на 3 в каждой следующей позиции, для чего использована переменная k. Кроме того, мы используем переменную h, чтобы накопить итоговый результат. Буква h означает здесь хэш, поскольку по сути мы хэшируем объект, возвращая в качестве ответа целое число.

Код для крестиков-ноликов. Рекурсивное перечисление состояний

Давайте поговорим о том, что нужно сделать, чтобы правильно инициировать функцию ценности.

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

Итак,нужная нам инициация выглядит следующим образом: V(s) = 1 для любого состояния, где игроквыигрывает, V(s) = 0 для любого состояния, где игрокпроигрывает или заканчивает игру вничью, и V(s) = 0,5 для всех остальных состояний. Всвязи с этим нам нужно перечислить все возможные состояния и присвоить имзначения.

Вопросдля размышлений: что лучше – создать дерево игры, где будут перечислены всевозможные последовательности ходов, или представить все 39конфигураций поля, даже если многие из них представляют невозможные игровыесостояния? Я дам вам минуту на размышления, или поставьте видео на паузу ивернитесь к нему позже.

Итак,что будет, если мы выберем вариант с деревом игры? Проблема в том, что онприводит к избыточным состояниям или, другими словами, мы будем встречать вдереве игры одно и то же состояние более одного раза. Рассмотрим, например,случай, когда крестик ставится в верхней центральной клетке, а нолик – вцентре. К точно такому же состоянию приводит случай, когда вначале ноликставится в центре, а крестик – вверху в центре. Прикинув, сколько различныхузлов дерева будет в этом дереве игры, мы увидим, что на корневом уровне у насесть девять различных вариантов хода, в лежащем ниже слое будет восемьразличных вариантов, затем семь и так далее. Таким образом, общее количествосостояний составит 9!, что приблизительно равно 360 000 – а это на порядокбольше, чем 39, что примерно равно 20 000. Таким образом,алгоритм, который нужно использовать для подсчёта всех состояний, определённо долженгенерировать перестановки.

Итак,как же нам это сделать? Вновь вспомним двоичные числа. Естественно, эторекурсивная задача, поскольку двоичное число длиной N может начинаться с 0 или 1, после чего к нему можнодобавлять все перестановки двоичного числа длиной N – 1. В виде псевдокода это можно сделать примернотак:

def generate_all_binary_numbers(N):

    results =[]

   child_results = generate_all_binary_numbers(N-1)

    for prefixin (‘0’, ‘1’):

        forsuffix in child_results:

           new_result = prefix + suffix

           results.append(new_result)

    return results

Вначалемы получаем результат рекурсии, то есть все двоичные числа длиной N – 1. Делаетсяэто вне цикла, поскольку более одного раза проводить эту операцию нет нужды. Вовнешнем цикле мы перебираем все возможные префиксы, а во внутреннем – вседочерние результаты. Внутри циклов мы создаём новые результаты, соединяяпрефикс и суффикс, и добавляем их в наш список результатов. Для простотыбазовый случай тут не указан.

Этобыл просто пример выполнения перестановок в общем случае; у нас он будетнесколько другим. Мы используем рекурсивную функцию get_state_hash_and_winner, которая будетвозвращать список кортежей. Каждый кортеж будет содержать состояние в видехэш-числа, кто является победителем (если таковой есть) и представляет лиданное состояние законченную игру. У функции будут три аргумента – env (среда, которая на самом деле нам нужна лишь дляматрицы поля) и координаты i и j для размещения следующего значения, которые могутбыть 0, крестиком (х) или ноликом (о).

Вэтой функции я покажу базовый случай. Если i= 1 и j = 2, то мы заполняем последнюю клетку на поле, аэто значит, что теперь мы должны игровое состояние – кто является победителем изакончилась ли игра.

        state =env.get_state()

        ended =env.game_over(force_recalculate=True)

        winner =env.winner

       results.append((state, winner, ended))

Обратитевнимание, что хотя речь идёт о заполненном поле, имеется в виду, что оно можетбыть заполнено и нулевым значением, представляющим собой пустое поле. Так чтоэто совсем не значит, что игра окончена. Это значит, что завершена нашаперестановка. Если же это не базовый случай, то мы рекурсивно вызываем функцию.У нас есть два числа, i и j, одно из которых мы можем увеличить на единицу, ноне оба одновременно. Если мы находимся в конце ряда, что значит, что j = 2, то переходим к следующей строке в первомстолбце, устанавливая j = 0 иувеличивая i на единицу. Если же мы не достигли конца ряда,можно просто увеличить на единицу j, оставивзначение i прежним:

      else:

        results+= get_state_hash_and_winner(env, i + 1, 0)

    else:

      #increment j, i stays the same

      results +=get_state_hash_and_winner(env, i, j + 1)

Инаконец надо отметить, что наши функции ценности для обоих игроков не будутэквивалентными. Не забывайте, что один игрок ставит крестики, а второй –нолики, поэтому если функция ценности для первого будет равна 1, то для второго– 0, и наоборот. Однако функции ценности не абсолютно противоположны, посколькуесли выходит ничья, то оба игрока получают 0. В связи с этим у нас будут двепочти противоположные друг другу функции initialV_x и initialV_o:

def initialV_x(env,state_winner_triples):

  # initializestate values as follows

  # if x wins,V(s) = 1

  # if x losesor draw, V(s) = 0

  # otherwise,V(s) = 0.5

  V =np.zeros(env.num_states)

  for state,winner, ended in state_winner_triples:

    if ended:

      if winner== env.x:

        v = 1

      else:

        v = 0

    else:

      v = 0.5

    V[state] = v

  return V

def initialV_o(env,state_winner_triples):

  # this is(almost) the opposite of initial V for player x

  # sinceeverywhere where x wins (1), o loses (0)

  # but a drawis still 0 for o

  V =np.zeros(env.num_states)

  for state,winner, ended in state_winner_triples:

    if ended:

      if winner== env.o:

        v = 1

      else:

        v = 0

    else:

      v = 0.5

    V[state] = v

  return V

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

Итак, мы постепенно собираем отдельные части для нашей игры в крестики-нолики. Как видите, многие из них нетривиальны.

Код для крестиков-ноликов. Среда

Напомню, что среда – это то, с чем взаимодействует агент. Начнём с обзора всех наших методов. Это конструктор, где мы инициируем важные переменные экземпляра; is_empty, который показывает, пустая ли данная позиция на поле; reward, возвращающий вознаграждение, когда мы ставим символ, представляющий конкретного игрока; get_state – его мы рассматривали ранее, он принимает состояние поля и возвращает число; game_over, проверяющий, закончилась ли игра путём просмотра состояний игры, и возвращающий ответ «истина» или «ложь»; и draw_board, который отрисовывает текущее поле для крестиков-ноликов – как вы понимаете, было бы довольно глупо, если бы мы не могли видеть поле игры.

Начнёмс конструктора, так как это позволит нам познакомиться со всеми интересующиминас переменными экземпляра. Первая переменная экземпляра – это поле,представляющее собой квадрат. Мы инициируем её в виде нулей, поскольку ноль –это наш символ для представления пустой клетки. Далее мы определяем символы длякрестиков и ноликов. Обратите внимание, что все они должны быть числами,поскольку мы сохраняем их в массиве Numpy. Позже выпоймёте, почему нам удобно присвоить им значения +1 и -1. Затем идёт переменнаяwinner, которой присваивается значение None, что означает, что победителя нет (или пока чтонет). Когда победитель появится, мы присвоим ей значение либо +1, либо -1.Следующей идёт булева переменная ended. Очевидно, чтоона имеет значение «ложь», а истинной становится только при окончании игры. Инаконец у нас есть переменная num_states. Она введена просто для удобства, чтобы не нужнобыло везде писать 3**(LENGHT*LENGHT):

  def __init__(self):

    self.board =np.zeros((LENGTH, LENGTH))

    self.x = -1# represents an x on the board, player 1

    self.o = 1 #represents an o on the board, player 2

    self.winner= None

    self.ended =False

   self.num_states = 3**(LENGTH*LENGTH)

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

  def is_empty(self, i, j):

    returnself.board[i,j] == 0

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

  def reward(self, sym):

    # no rewarduntil game is over

    if notself.game_over():

      return 0

    # if we gethere, game is over

    # sym willbe self.x or self.o

    return 1 ifself.winner == sym else 0

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

  def get_state(self):

    # returnsthe current state, represented as an int

    # from0…|S|-1, where S = set of all possible states

    # |S| =3^(BOARD SIZE), since each cell can have 3 possible values – empty, x, o

    # somestates are not possible, e.g. all cells are x, but we ignore that detail

    # this islike finding the integer represented by a base-3 number

    k = 0

    h = 0

    for i in xrange(LENGTH):

      for j in xrange(LENGTH):

        ifself.board[i,j] == 0:

          v = 0

        elifself.board[i,j] == self.x:

          v = 1

        elifself.board[i,j] == self.o:

          v = 2

        h +=(3**k) * v

        k += 1

    return h

Следующейу нас идёт функция game_over, и, наверное, это самая сложная функция в классе Environment. Кроме того, вероятно, вас удивит аргумент force_recalculate.

  defgame_over(self, force_recalculate=False):

    if notforce_recalculate and self.ended:

      returnself.ended

Преждевсего отметим, что game_over в скрипте вызывается несколько раз. Однако еслиигра уже закончилась, нам нет нужды выполнять эту сложную операцию снова иснова, поэтому факт окончания игры используется как краткий способ окончанияработы функции. Но если вы припомните нашу более раннюю рекурсивную функцию дляперечисления состояний, в ней мы рекурсивно заполняли каждую позицию на поле.Это включает в себя размещение символов на поле, удаление их, размещение новыхсимволов и так далее. То есть мы переходим от состояния «игра закончена» ксостоянию «игра не закончена» и обратно, что значит, что мы не можемвоспользоваться кратким способом. Аргумент force_recalculate позволяет нам гарантировать, чтооперация будет происходить в любом случае.

Следующие части функции game_over вполне ожидаемы. Мы проверяем, есть ли победитель, и если его нет, то проверяем, заполнено ли всё поле, что означает ничью. Победителя мы находим, проверяя сначала все строки, затем все столбцы, а затем – диагонали. Именно здесь присваивание крестикам и ноликам значений +1 и -1 оказывается очень полезным, поскольку если у нас три крестика в строке, то сумма будет равна -3, а если три нолика в ряду – то +3. Если победитель нашёлся, то переменной экземпляра winner присваивается соответствующее значение для выигравшего игрока, а переменной ended – значение «истина». Кроме того, мы возвращаем значение «истина», поскольку функции game_over нужна булева переменная.

    # checkrows

    for i in xrange(LENGTH):

      for playerin (self.x, self.o):

        ifself.board[i].sum() == player*LENGTH:

          self.winner = player

         self.ended = True

          returnTrue

    # checkcolumns

    for j in xrange(LENGTH):

      for playerin (self.x, self.o):

        ifself.board[:,j].sum() == player*LENGTH:

         self.winner = player

          self.ended = True

          return True

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

    # checkdiagonals

    for playerin (self.x, self.o):

      # top-left-> bottom-right diagonal

      ifself.board.trace() == player*LENGTH:

       self.winner = player

       self.ended = True

        returnTrue

      #top-right -> bottom-left diagonal

      ifnp.fliplr(self.board).trace() == player*LENGTH:

       self.winner = player

       self.ended = True

        return True

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

Наконец,если ни одно из вышеперечисленных условий не выполняется, мы возвращаемзначение «ложь»:

    # checkif draw

    ifnp.all((self.board == 0) == False):

      # winnerstays None

     self.winner = None

      self.ended= True

      return True

    # game isnot over

    self.winner =None

    return False

И последней у нас идёт функция draw_board, позволяющая наглядно отобразить игру в крестики-нолики. Действительно, довольно сложно играть в крестики-нолики, не видя поле. Функция просто перебирает каждую позицию на поле и размещает соответствующий символ на соответствующем поле.

  def draw_board(self):

    for i in xrange(LENGTH):

      print“————-“

      for j in xrange(LENGTH):

        print” “,

        ifself.board[i,j] == self.x:

          print“x”,

        elifself.board[i,j] == self.o:

          print“o”,

        else:

          print” “,

      print“”

    print “————-“

Продолжение в следующей статье!

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

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