Крестики-Нолики (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):

Рис. 1. Для удобства позиция в списке равна клетке на поле 3х3. Начало игры: TTT=[0, 0, 0, 0, 0, 0, 0, 0, 0]

Рис. 2. Пример списка, описывающего текущее поле TTT=[-1, 0, 1, 0, -1, 0, 0, 0, 1].

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

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

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

Рис.3. Два примера диагональных побед и схематичный вид списка ТТТ при этом.

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) нужно поставить именно туда, где уже есть ХХ рядом согласно правилам (диагональ Лево-Право):

Рис.4. В желтую клетку просится Х для победы (список ТТТ[8]). Для этого в списке mov_map[8] появляется красный -1 (собственно желаемый будущий ход именно Х).

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

Рис.5. Для игрока О только оборона в желтую клетку, поскольку mov_map[8]=-1 (иначе следующий ход Х сюда же приведет к его победе).

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

Рис.6. Редкое совпадение, когда значение mov_map[8]=-2.

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 требует хода именно туда. Там сходятся или две победы одного игрока, или победа у каждого.

# if two winners or double one 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)

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

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

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

Рис.7. Игрок Х сделал вилку. Ход О-игрока в красную или желтую клетку приведет к победе Х.

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

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

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

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

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

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

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

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

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