Крестики-Нолики (Tic Tac Toe) с компьютером на Python. Часть 2: шаг к ML

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

Хотел бы присоединиться к какому-то проекту на границе практической медицины и машинного обучения. Для этого решил публиковать оригинальные статьи, чтобы как-то начать IT портфолио в дополнение к аналогичному "из операционной".

В первой части статьи рассказывалось о новом программном алгоритме игры человека с компьютером в качестве «Х» или «О» игрока, избегая классического «дерева для конечного числа ходов». Цель - ситуационный анализ только текущего поля и выбор "лучшего следующего хода".

Во второй части "лучший ход" будет взят на основе нейросети из базового файла .csv с результатами 50000 случайных игр компьютера с самим собой. Причем все последующие игры пользователя и машины будут также продолжать вноситься в файл, если ранее их там не было. Этот принцип я взял из ML шахматных движков, основанных на записи в DB результатов игр профессионалов за полтора века. Контроль качества провел, сыграв 100 игр с web Tic-Tac-Toe от Google, выбрав роль посредника между ним и моей программой на Python. 

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

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

1. Важные технические детали.

2. Запись игр в файл.

3. Тренировка компьютера с самим собой.

4. Поиск «лучшего хода» в DB.

5. Это ли нейросеть и ML? Выводы.

6. Финальный код проектов.

Заранее отмечу, что всеми силами пытался упростить текст и донести свою логику читателям. Задача непростая, поэтому код максимально наполнил комментариями.

Важные технические детали

1. В одной игре до победы "Крестиков" возможно провести 5, 7 или 9 ходов (стадий игры), а для победы "Ноликов" 6 или 8. Ничья ("Draw") - это всегда 9-й ход.

2. В одной игре возможно от 5 до 9 стадий (поочередных ходов Х и О).

3. Текущее поле записывается в виде одномерного списка TTT[ ] (см. часть 1).

4. По формуле записи в нём легко определить, чей ход следующий.

5. Такой список из 9 цифр (=9 клеток поля) позволяет быстро найти такие же в DB.

6. База данных составлена из 50000 игр с использованием программного алгоритма (см. часть 1) для "лучшего следующего хода" при совпадении в одной линии ХХ_ (Х_Х) или ОО_ (О_О), если таковой не был определен, то ход был случайным. Итерация максимально возможных 9! ходов не проводилась для "чистоты эксперимента".

7. Все игры записаны "постадийно" (от 5 до 9), каждое текущее поле в виде списка из 10-и элементов вносилось на новую строчку файла (см. ниже).

Запись игр в файл

Основные задачи:

1. Составить алгоритм (нейросеть), оценить веса (W_n) и варианты настройки.

2. Добавить элемент "Следующий ход" в один список с текущим полем (TTT[ ]), сохраняя свой знак ("-" для Х, "+" для О). Цель - при анализе списка функция видит в DB и поле и какой ход был сделан на данной стадии игры.

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

4. Максимально ускорить работу с DB, удалить все дублирующие строчки из файла после самообучения, в дальнейшем вносить только уникальные.

Добавленные функции:

for_file(). Вносит на выходе все стадии одной игры в список game_save[ ] вплоть до последней, которая не будет использоваться в анализе. Осуществляется путем разделения списков на предыдущий - TTT2 = copy.deepcopy(TTT) и текущий (TTT). Для удобства в файл элемент "Следующий ход" записывается в предыдущую стадию в виде -9...-1 (для "Х") и 1...9 (для "О") (вместо 0...8 в соответствии с номером клетки поля как указано в части 1).

def for_file(): # save all stages of one game to game_save=[] list with formula
    global TTT, game_save, move
    if TTT2.count(0)<=8:
        TTT2.append((move + 1) * XO)  # add future move to the 9th position in TTT old field & XO gives its sign (+/-)
                                      # so nums[9]=-5 is X's move, nums[9]=2 is O's move
                                      # To simplify the check inside the DB file, we display the move number in the DB
                                      # from the 1st (1...9), and not from the 0th as in the list (0...8)
        TTT3 = copy.deepcopy(TTT2)  # to avoid changing inside temporary store game_save when TTT2.pop()
        game_save.append(TTT3)  # add protected from any changing TTT3
        TTT2.pop()  # clear last (move's) number from working field list

game_save_length(). Дополняет все стадии одной игры (списки) в game_save[ ] одним и тем же элементом "Когда и как завершилась игра".

def game_save_length(): # number of stages in one won game (game_save[...,9-next move, 10-number of moves before winning]
    # Consciously counting starts from the 2nd move.
    # Therefore, the O's victory always ends in an odd (5, 7), and X's - even (4, 6, 8) move.
    # Draw always ends 9 move and is saved in nums[10] position.
    # The last (9th) stage of each game is not in game_save[], because we don't need it for comparing and choose smth.
    global game_save, XO
    for item in game_save:
        if draw is True: # we must divide X's win and Draw situations. Let's Draw is 9 moves totally.
            item.append(9)  # or len(game_save)+1 = 9 (constantly)
        else:
            item.append(len(game_save)) # each stage will be added [10] position (4 ... 8)

into_file(). Непосредственно записывает в базу данных (файл data.csv) в каждую новую строчку результат двух предыдущих функций: "текущее поле" + "следующий ход" + "когда и как завершилась эта игра".

Поскольку файл один и тот же, пришлось разделить действие на две фазы: чтение и удаление из game_save[ ] дублирующих списков, а потом запись оставшихся. Учитывая, что одна строка (собственно список) содержит 10 цифр, то "построчный" перебор базы данных проходит быстро.

def into_file(): # saving all games with all stages in file with formula (but without duplicates!)
    global game_save
    game_save_length() # creating final version of game_save[]
    # We must divide using the same file only step by step

    filename = "data.csv"
    with open(filename, "r") as file: # opening and reading only
        reader = csv.reader(file)
        for row_file in reader: # reading all the lines apart
            nums = list(map(int, row_file)) # one line is writing to a variable nums
            for item in game_save: # iterate through all nested lists
                if item==nums:
                    game_save.remove(item) # we need only unique lists = lines in DB file
    file.close() # preparing move to next step

    with open(filename, "a", newline="") as file:
        writer = csv.writer(file)
        for item in game_save:
            writer.writerow(item)  # save in DB only unique lists (lines)
    file.close()
    game_save.clear()  # clearing list after stored in file

Фрагмент итогового файла на Рис.1. Желтым выделено описание поля в какой-то стадии ранее сыгранной игры (фактически TTT[ ]). В ячейке J - следующий ход для "Х" (-1), а в ячейке K - эта игра закончилась победой "О" на 7й стадии (фактически 8й ход). Аналогично и в зеленой строке, но для хода "О", при победе "Х".

Тренировка компьютера с самим собой

На этом этапе в цикле из нужного числа случайных игр (gm<=50000) за 3,5 часа сгенерировалось около 372 т. строчек. После удаления дублирующих друг друга строк осталось около 20000. После раздумий и оптимизации в базе осталось примерно 10000 только перспективных ходов.

К слову, я не сразу добавил цикл записи только уникальных строк, решив изучить их все. Прогонял несколько раз с разными критериями 20...100 т. игр - это около 762 т. стр. и до 7 ночных часов. В начале анализа дубликаты удалял примитивным образом в Excel (выделить все, Data, Remove Duplicates), а иногда и переписывал в новый файл кодом, старый удалял. Цель итераций была выяснить, хватит ли трех описанных критериев, или нужно больше для выбора "лучшего следующего хода", какой вес W_n и настройки сетки (см. Рис. 2).

def comp_training(): # computer trains itself using random choice, checking algorithm and saves all unique moves to DB
    global TTT, TTT2, XO, move, winner, draw, gm
    while gm<=50000:  # run the game loop forever for specific numbers of games (gm)
        for event in pg.event.get():
            if event.type == QUIT:
                pg.quit()
                sys.exit()

        if winner is None:
            TTT2 = copy.deepcopy(TTT)  # store the last TTT field
            check_moves()  # check for XX, X_X, OO, O_O
            if move is None:
                while True:
                    move = random.randint(0, 8)
                    if TTT[move] == 0:
                        break
            # additional conditions for computer training - it were turned off for current DB
                    # if XO==1 and 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()

Поиск «лучшего хода» в DB

from_file(). Функция выбирает "лучший ход" по алгоритму на Рис.2. Изображен в виде нейросети с указанием весов W_n между 4-мя этапами.

1. Текущее поле в игре входит в виде списка TTT=[ ].

2. В файле с ранее записанными стадиями игр выбирается копия полей (вес W₁ = 1), сравнивая со списком nums[:9], которых до 4-го хода всегда большое количество. Соответствующий элемент "Как завершилась игра" (nums[10]) добавляется в список stage[ ], а какой был при этом "Следующий ход" (nums[9]) - в список move_stage[ ] на ту же позицию.

3. Из всех вариантов успешнее была та игра, которая завершилась победой и на более ранней стадии. Таким образом в списке stage[ ] интересно только одно минимальное значение на позиции q (вес W₂ = 1).

4. Соответствующие данному полю и минимальной стадии варианты ходов из move_stage[ ] сохраняются во временном списке moves[ ], а затем оттуда выбираются случайным образом. Интересно, что на ранних стадиях (до 4й) выборка до 8 значений, и чем выше стадия, тем выбор "Следующего хода" сводится к одному. Поэтому я обозначил вес как плавающий (W₃ = 0,125...1).

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

def from_file(): # taking "best next move" from DB (2nd step in ALGORYTHM of machine learning)
    global TTT, move, XO
    filename = "data.csv"  # main DB file
    with open(filename, "r") as file:
        reader = csv.reader(file)
        for row_file in reader:
            nums = list(map(int, row_file))  # one line is one list with description of one game's stage
            if nums[:9] == TTT and nums[10]!=9:  # if current field (TTT[]) is equal with the same in DB (nums[:9])
                stage.append(nums[10])  # list with all numbers of stages in DB which is fitted current field (TTT[])
                move_stage.append(abs(nums[9])) # list with "next move" in DB which is fitted (TTT[]) and stage
                               # Valuables' position in the both lists is the same. For example, stage[2] fits with move_stage[2]

        if len(stage)==0: # if X and O lists are empty (because "DRAW"), lists fills out from nums[10]==9
            for row_file in reader:
                nums = list(map(int, row_file))
                if nums[:9] == TTT and nums[10]==9:
                    stage.append(nums[10])
                    move_stage.append(abs(nums[9]))

        for q in range(0, len(stage), 1):
            if stage[q] == min(stage): # find the minimum value of stage [q] because it gives the best "next move"
                moves.append(move_stage[q]) # the best "next move" fills out moves[] with move_stage[q] (it fits)
        
        if len(moves)==0: # if empty (didn't find best move)
            move = None # way for random cell in the field
        elif len(moves)==1:
            move = moves[0]-1
        else: # if there are several the best "next moves", then the machine chooses one of them randomly
            while True:
                move = moves[random.randint(0, len(moves)-1)]-1
                if TTT[move] == 0:  # insurance of busy but it's not nessary
                    break
        stage.clear()
        move_stage.clear()
        moves.clear()

Это ли нейросеть и ML? Выводы.

1. С академической точки зрения все классические структуры нейросети присутствуют. Однако настройка "обратного распространения" фактически прошла вручную. Случайный выбор (W₃ = 0,125...1) в середине игры (шаг 4 на Рис.2) нужного хода из нескольких не даст "засушить" игру и внесет разнообразие при совпадении положения "Крестиков" и "Ноликов" на поле в любую из стадий любой игры.

2. Обучение компьютером самого себя и внесение строк в файл базы данных в дальнейшем - это ML.

3. Контроль качества проверял, сыграв 100 игр с web Tic-Tac-Toe от Google в роли посредника между ним и этой программой. Результат - примерное равное число побед и поражений и при игре за "Х" и за "О".

4. Очевидно, что первый программный алгоритм (см. часть 1) - имеет защитную тактику, выполняя дебютные ходы (до 4-го) случайно. А функция нейросети предлагает более интересные варианты, при этом ничья встречается реже в 3 раза.

5. Возможно, что эту модель стоит добавить четвертый критерий, например, частоту встречаемости той или иной стадии на прогонке 100 т. случайных игр, улучшив вес W₃ и добавив "нейронности" и "лернинговости" велосипеду.

Финальный код проектов

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

Благодарю за прочтение и дельные советы. Всем удачи!