Крестики-Нолики (Tic Tac Toe) с компьютером на Python. Мой первый шаг к Machine Learning. Часть 1

Всем привет. Я любитель Python и совсем недолго осваиваю язык всеми доступными способами. Моя цель — понять принципы машинного обучения и его взаимосвязь с нейросетью. Никакого опыта в IT не имел, тем не менее постараюсь излагать общепринятой терминологией, не судите строго. Моя основная профессия не менее сложная, далека от IT, но для упрощения работы в нее все больше внедряются AI и ML. Мною движет лишь интерес к современным технологиям, программированию.

В первой части покажу только основные этапы создания игры, где пользователь выбирает роль (Х или О), играя с компьютером. Поиск в сети Python аналогов дал только несколько вариантов игры с рандомным ответом компьютера. Мой целью в этой части стало самостоятельно научиться оценивать текущую позицию на поле «Крестики-Нолики» и подбирать оптимальный вариант следующего хода компьютера. К слову, уже перед окончанием статьи нашел готовую web-игру в google, где уже реализован такой подход. Тем интереснее было проверить себя и поделиться «изобретением колеса, но по-своему».

Во второй части попробую прикрутить к игровой логике другой подход — машинное обучение на основе большого числа сыгранных партий компьютером с самим собой.

Кому будет полезен материал: любителям Python, логики, алгоритмов. В финальном коде все переменные, функции и действия прокомментированы на английском.

Содержание статьи:

1. Зачем Крестикам‑Ноликам машинное обучение?

2. Представление поля 3х3 в виде одномерного числового списка.

3. Коротко о функциях.

4. Карта лучших ходов и алгоритм для компьютера.

5. Функция для Игрока.

6. Недостаток алгоритма?

7. Финальный код.

8. Анонс второй части статьи

Зачем Крестикам‑Ноликам машинное обучение?

Ответ простой: шахматы и переводчики на основе ИИ. Эти популярные в жизни приложения по своей сути — сложная игра. Как мне казалось, все ходы как и переводы просчитать невероятно сложно. Однако движок на CHESS.com поражает, как и выходные результаты переведенного текста в DEEP-L. Оказывается, все профессиональные шахматные партии с XIX века внесли в базу ИИ (благо записывают их в виде шахматных формул). Затем разными алгоритмами организовали поиск оптимального хода. Выяснили, что оптимальный ход может устаревать, ведь шахматисты растут да и играет уже весь мир. А чем больше партий, тем достовернее их анализ (хоть и дольше). Придумали непрерывно пополнять шахматную базу в ИИ, снова обновлять лучшие варианты хода, расширяя критерии поиска. Так я решил, что надо подобрать какую-то простую известную игру, где машину можно обучить до идеала по этой схеме. Выбор пал Tic Tac Toe с полем 3х3. Но для начала мне нужно было еще ее создать с нуля. Обозначил себе этапы Machine Learning (тема второй части):

• пополнить ИИ уже известными результатами игр,

• придумать критерии и алгоритм для отбора оптимального хода.

Представление поля 3х3 в виде одномерного числового списка

Я решил уйти от многомерных списков list, которые здесь напрашиваются для изображения поля. Игрока «Х» обозначил как «-1», «О» как «1». Незаполненное поле останется «0». Это числовой тип данных. Наша игра — это одномерный список с 9ю аргументами на позициях от 0 до 8, значит начало: TTT=[0, 0, 0, 0, 0, 0, 0, 0, 0] (рис. 1 и 2):

Коротко о функциях

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

pygame: Выбрана простая графика и события. Библиотека осваивается за полчаса с гугл.

import pygame as pg, sys from pygame.locals import * import time, random  width = 400 height = 400 white = (255, 255, 255) RED = (255, 0, 0) BLACK = (0, 0, 0) line_color = (10, 10, 10)  # initializing pygame window pg.init() fps = 30 CLOCK = pg.time.Clock() screen = pg.display.set_mode((width, height + 100), 0, 32) pg.display.set_caption("Tic Tac Toe")  # loading the images opening = pg.image.load('tic tac opening.png') x_img = pg.image.load('x.png') o_img = pg.image.load('o.png')  # resizing images x_img = pg.transform.scale(x_img, (80, 80)) o_img = pg.transform.scale(o_img, (80, 80)) opening = pg.transform.scale(opening, (width, height + 100))

user_click(): Выбор мышкой нужного поля без изысков: координаты внутри сектора определяют его номер как на рис.1., что заложено в числовую переменную move.

def user_click(): # mouse click     global move     move = None     # get coordinates of mouse click     x, y = pg.mouse.get_pos()     # get x,y of mouse click (cell 0-8)     if (y < height / 3) and (x < width / 3):         move = 0     elif (y < height / 3) and (x < width / 3 * 2):         move = 1     elif (y < height / 3) and (x < width):         move = 2      elif (y < height / 3 * 2) and (x < width / 3):         move = 3     elif (y < height / 3 * 2) and (x < width / 3 * 2):         move = 4     elif (y < height / 3 * 2) and (x < width):         move = 5      elif (y < height) and (x < width / 3):         move = 6     elif (y < height) and (x < width / 3 * 2):         move = 7     elif (y < height) and (x < width):         move = 8

Переменные: XO — это очередь Х (-1) или О (1) оказаться в списке TTT=[ ]. Перменные ХО и move по умолчанию None, глобальные, числовые, поскольку будут использованы в разных функциях. Говорящие за себя winner и draw — победитель и ничья.

XO = None  # -1 is X-player, 1 is O-player move = None # numbers from 0 to 8 winner = None draw = False      # TicTacToe 3x3 board TTT= [0,0,0,0,0,0,0,0,0]     # game field is shared on 9 cells with determination of each one from left to right in upper,middle & lower row:     # 0,1,2 - upper row     # 3,4,5 - middle row     # 6,7,8 - lower row     # totaly = 3x3 field = 9 numbers (from 0 to 8 considering that list [TTT] starts with 0 position)

сheck_win(): Перебором комбинаций текущего поля ТТТ получаем три -1 или 1 в ряду (но и не ноль!), вертикали или диагонали. Программа рисует линию через победную комбинацию и присваивает переменной winner значение -1 (Х) или 1 (О).

def check_win(): # check winner and drawing the appropriate lines     global TTT, winner, draw      # check for winning rows     for row in range(0, 7, 3):  # jump through 3 in TTT list         if ((TTT[row] == TTT[row + 1] == TTT[row + 2]) and (TTT[row] != 0)):             # this row won             winner = TTT[row]             pg.draw.line(screen, (250, 0, 0), (0, (row/3 + 1) * height / 3 - height / 6), \                          (width, (row/3 + 1) * height / 3 - height / 6), 6)             break      # check for winning columns     for col in range(0, 3, 1):  # jump through 1 in TTT list         if (TTT[col] == TTT[col + 3] == TTT[col + 6]) and (TTT[col] != 0):             # this column won             winner = TTT[col]             # draw winning line             pg.draw.line(screen, (250, 0, 0), ((col + 1) * width / 3 - width / 6, 0), \                          ((col + 1) * width / 3 - width / 6, height), 6)             break      # check for diagonal winners     if (TTT[0] == TTT[4] == TTT[8]) and (TTT[0] != 0):         # game won diagonally left to right         winner = TTT[0]         pg.draw.line(screen, (250, 70, 70), (50, 50), (350, 350), 6)      if (TTT[2] == TTT[4] == TTT[6]) and (TTT[2] != 0):         # game won diagonally right to left         winner = TTT[2]         pg.draw.line(screen, (250, 70, 70), (350, 50), (50, 350), 6)      if TTT.count(0) == 0 and winner is None:  # all cells are filled in         draw = True      game_status()

Карта лучших ходов и алгоритм для компьютера

Собственно — это самое интересное. Я решил создать такой же список mov_map для текущего поля. Сюда аналогично на текущую позицию попадает только критически нужный последний ход для победы. Пару ключевых примеров.

1. Представим самый простой вариант (Рис.4.), когда на 7м ходу Х (ХО=-1) нужно поставить именно туда, где уже есть ХХ рядом согласно правилам (диагональ Лево-Право):

2. Однако если, например, обороняется игрок О (ХО=1), а критическое победное поле Х уже создал (Рис. 5)? Тогда приоритет для хода О как раз та же желтая клетка (mov_map[8]=-1). Результат хода это предотвращение победы Х и ничья для игрока О:

3. Следующий вариант, если в одну клетку сходятся две победные комбинации игрока Х, при этом ход игрока О (ХО=1):

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

def check_moves(): # finding the best cell for the next computer's move     global TTT, move     mov_map = [0, 0, 0, 0, 0, 0, 0, 0, 0] # map of the moves before each computer's move in current situation     move = None     # check for winning rows     # the sum of the moduli of the current value and the winning cell of the checked player, and then multiply them by the sign of the checked player     # in the most cases: zero + 1 or -1 (current player), but if the cell has two or three winners simultaneously, the module of the value must be 2 or 3 (-2 or -3)     for row in range(0, 7, 3):  # jump through 1 in TTT list         r=TTT[row] + TTT[row + 1] + TTT[row + 2]         if abs(r) == 2:             if TTT[row] == 0:                 mov = row                 mov_map[mov] = (abs(mov_map[mov])+abs(int((r) / 2)))*int((r) / 2) #the sum of winning's module both of players & multiple on the current player's sign             elif TTT[row + 1] == 0:                 mov = row + 1                 mov_map[mov] = (abs(mov_map[mov])+abs(int((r) / 2)))*int((r) / 2)             elif TTT[row + 2] == 0:                 mov = row + 2                 mov_map[mov] = (abs(mov_map[mov])+abs(int((r) / 2)))*int((r) / 2)      # check for winning columns     for col in range(0, 3, 1):  # jump through 1 in TTT list         c=TTT[col] + TTT[col + 3] + TTT[col + 6]         if abs(c) == 2:             if TTT[col] == 0:                 mov = col                 mov_map[mov] = (abs(mov_map[mov])+abs(int((c) / 2)))*int((c) / 2)             elif TTT[col + 3] == 0:                 mov = col + 3                 mov_map[mov] = (abs(mov_map[mov])+abs(int((c) / 2)))*int((c) / 2)             elif TTT[col + 6] == 0:                 mov = col + 6                 mov_map[mov] = (abs(mov_map[mov]) + abs(int((c) / 2))) * int((c) / 2)      # check for diagonal winners: L>R     d_Lr=TTT[0] + TTT[4] + TTT[8]     if abs(d_Lr) == 2:         if TTT[0] == 0:             mov = 0             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Lr) / 2)))*int((d_Lr) / 2)         elif TTT[4] == 0:             mov = 4             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Lr) / 2)))*int((d_Lr) / 2)         elif TTT[8] == 0:             mov = 8             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Lr) / 2)))*int((d_Lr) / 2)          # check for diagonal winners: R>L     d_Rl=TTT[2] + TTT[4] + TTT[6]     if abs(d_Rl) == 2:         if TTT[2] == 0:             mov = 2             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Rl) / 2)))*int((d_Rl) / 2)         elif TTT[4] == 0:             mov = 4             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Rl) / 2)))*int((d_Rl) / 2)         elif TTT[6] == 0:             mov = 6             mov_map[mov] = (abs(mov_map[mov])+abs(int((d_Rl) / 2)))*int((d_Rl) / 2)

Выбор хода после заполнения списка mov_map=[ ]:

Знак перед модулем значений в списке mov_map создает чувствительность для конкретного игрока. Разберем на примере, когда наступает ход Х (т.е. ХО=-1):

1. если в списке mov_map хотя бы единожды встречается -1, то это победный выбор.

2. если в списке mov_map -1 нет, а присутствует 1, то для Х (напомню, ХО=-1) это ход для спасения от поражения.

3. если в списке mov_map присутствуют и -1 и 1, то выбирается модуль со своим знаком для победы (т.е. -1 для ХО=-1).

# if one winner in one cell     if mov_map.count(XO) > 0 and mov_map.count(-1*XO) == 0: #current player must choose his own square if the opponent hasn't a winning cell         move = mov_map.index(XO)     if mov_map.count(-1*XO) > 0 and mov_map.count(XO) == 0: #current player must choose opponent's square if the there isn't his own winning cell         move = mov_map.index(-1*XO)     if mov_map.count(XO) > 0 and mov_map.count(-1*XO) > 0: # current player must choose his own square if the opponent has a winning cell as well         move = mov_map.index(XO)

4. Вне зависимости какой игрок (Х или О): любое значение с модулем 2 (или 3 — такое тоже возможно!) требует хода именно туда. Там сходятся или две победы одного игрока, или победа у каждого.

# if two or three winners are in one cell - the always preference goes to current player     if mov_map.count(2) > 0:         move = mov_map.index(2)     if mov_map.count(-2) > 0:         move = mov_map.index(-2)     if mov_map.count(3) > 0:         move = mov_map.index(3)     if mov_map.count(-3) > 0:         move = mov_map.index(-3)

Функция для Игрока

Раздельный способ запуска игры для Х- или О- пользователя показался более оптимальным на отладке во избежании путаницы и усложнения логики.

X_player(). Запускает главный цикл while True и обработку события выхода из игры (стандартный цикл for event… в pygame).

def X_player(): # X-player     global TTT, XO, move, winner, draw     while (True):  # run the game loop forever         for event in pg.event.get():             if event.type == QUIT:                 pg.quit()                 sys.exit()

Один ход на каждого игрока — это две ветки:

1. Игрок Х — пользователь — (ХО==-1) выбирает мышкой желаемую клетку на поле функцией user_click(), которая должна возвратить значение от 0 до 8 переменной move (согласно схеме на рис.1). Если move=None, значит ожидается повторный клик. Удобно обходиться без обработки ошибок если пользователь промахивается мимо поля, просто разместив это условие в цикле на первом месте с повтором (continue).

2. Если все же пользователь указал пустую клетку TTT[move] == 0, то запускается функция прорисовки фигуры на поле DrawXO() (см. ниже).

            if XO == -1: # X's move                 if event.type == MOUSEBUTTONDOWN:                     user_click()  # click mouse button for Х's move                     if move == None:                         continue                     else:                         if (TTT[move] == 0):                             DrawXO()

3. Игрок О — компьютер — (ХО==1):

   • Проверка наличия оптимальных ходов: check_moves(). Если их нет, то запускается локальный цикл while True:

   • Попытка поставить «О» в центр TTT[4] == 0 («защита от дурака», т.к. это ослабит большое преимущество у Х после первого хода).

   • При исключении — случайный ход «О», но только в пустое место: random.

   • Прорисовка, переход хода и проверка в DrawXO() (см. ниже).

            if XO == 1 and draw is False and winner is None: # O's move                 check_moves()  # check for XX, X_X, OO, O_O                 if move is None:                     while True:                         if TTT[4] == 0:  # protection from the fool (when a rival makes typical triangle of "X")                             move = 4                             break                         else:  # a move for good luck, gives a chance to play fair without algorithm                             move = random.randint(0, 8)                             if TTT[move] == 0:                                 break                 DrawXO()

4. В случае чьей-то победы или ничьи — перезагрузка reset_game().

5. В главном цикле обновляется картинка на экране pg.display.update().

        if (winner or draw):             reset_game()         pg.display.update()         CLOCK.tick(fps)

DrawXO(). Запускается только при имеющемся готовом значении хода move.

• Сначала вносит в список новый ход: TTT[move] = XO.

• Затем прорисовывает Х (или О) в своем поле.

• После этого XO = -1*XO дает тригер для перехода хода (от Х к О или наоборот), меняя свой знак на обратный.

• В финале проверяет все текущее поле ТТТ на победу check_win().

def DrawXO(): # drawing of X or O, and after a sign will be reversed (XO => - XO) for player changing     global TTT, XO, move     TTT[move] = XO     if move == 0:         posx = 30         posy = 30     if move == 1:         posx = width / 3 + 30         posy = 30     if move == 2:         posx = width / 3 * 2 + 30         posy = 30      if move == 3:         posx = 30         posy = height / 3 + 30     if move == 4:         posx = width / 3 + 30         posy = height / 3 + 30     if move == 5:         posx = width / 3 * 2 + 30         posy = height / 3 + 30      if move == 6:         posx = 30         posy = height / 3 * 2 + 30     if move == 7:         posx = width / 3 + 30         posy = height / 3 * 2 + 30     if move == 8:         posx = width / 3 * 2 + 30         posy = height / 3 * 2 + 30      if XO == -1:         screen.blit(x_img, (posx, posy))     else:         screen.blit(o_img, (posx, posy))     XO = -1*XO     pg.display.update()     check_win()

Один полноценный главный цикл X_player() это:

1. ход Х (пользователь), прорисовка и смена игрока, проверка на победу.

2. алгоритм поиска хода для О (компьютер), прорисовка и смена игрока, проверка на победу.

O_player(). Устроена аналогично, но зеркально наоборот.

Недостаток алгоритма?

С точки зрения пользователя — недостатки алгоритма компьютерного хода — это увеличенные шансы для победы человека. На поле 3х3 важны первые три хода, когда О-игрок мешает Х сделать вилку, т.е. одновременно появляются две клетки для безоговорочной победы Х (Рис.7).

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

Финальный код

Начальное меню и выбор пользователем роли в статье не рассматривалось, там все предельно просто и понятно.

Проект финального кода и три картинки находятся в архивном файле здесь.

Анонс второй части статьи

1. Запуск игр компьютера против самого себя.

2. Функции для записи всех игр пошагово в CSV-файл.

3. Анализ и выбор нужного хода из базы данных: какой способ оптимален?

4. Результаты: это ли машинное обучение?