Крестики-Нолики (Tic Tac Toe) с компьютером на Python. Мой первый шаг к Machine Learning. Часть 1
Всем привет. Я любитель Python и совсем недолго осваиваю язык всеми доступными способами. Моя цель - понять принципы машинного обучения и его взаимосвязь с нейросетью. Никакого опыта в IT не имел, тем не менее постараюсь излагать общепринятой терминологией, не судите строго. Моя основная профессия (оперирующий травматолог, кандидат наук) не менее сложная, далека от IT, но для упрощения работы в нее все больше внедряются AI и ML. Мною движет лишь интерес к современным технологиям, программированию.
В первой части покажу только основные этапы создания игры, где пользователь выбирает роль (Х или О), играя с компьютером. Поиск в сети Python аналогов дал только несколько вариантов игры с рандомным ответом компьютера. Мой целью в этой части стало самостоятельно научиться оценивать текущую позицию на поле "Крестики-Нолики" и подбирать оптимальный вариант следующего хода компьютера. К слову, уже перед окончанием статьи нашел готовую web-игру в google, где уже реализован такой подход. Тем интереснее было проверить себя и поделиться "изобретением колеса, но по-своему".
Во второй части попробую прикрутить к игровой логике другой подход - машинное обучение на основе большого числа сыгранных партий компьютером с самим собой.
Кому будет полезен материал: любителям Python, логики, алгоритмов. В финальном коде все переменные, функции и действия прокомментированы на английском.
Содержание статьи:
Зачем Крестикам‑Ноликам машинное обучение?
Представление поля 3х3 в виде одномерного числового списка.
Коротко о функциях.
Карта лучших ходов и алгоритм для компьютера.
Функция для Игрока.
Недостаток алгоритма?
Финальный код.
Анонс второй части статьи
Зачем Крестикам‑Ноликам машинное обучение?
Ответ простой: шахматы и переводчики на основе ИИ. Эти популярные в жизни приложения по своей сути - сложная игра. Как мне казалось, все ходы как и переводы просчитать невероятно сложно. Однако движок на 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 для текущего поля. Сюда аналогично на текущую позицию попадает только критически нужный последний ход для победы. Пару ключевых примеров.
Представим самый простой вариант (Рис.4.), когда на 7м ходу Х (ХО=-1) нужно поставить именно туда, где уже есть ХХ рядом согласно правилам (диагональ Лево-Право):
Однако если, например, обороняется игрок О (ХО=1), а критическое победное поле Х уже создал (Рис. 5)? Тогда приоритет для хода О как раз та же желтая клетка (mov_map[8]=-1). Результат хода это предотвращение победы Х и ничья для игрока О:
Следующий вариант, если в одну клетку сходятся две победные комбинации игрока Х, при этом ход игрока О (ХО=1):
Комбинация, когда в одну клетку сходится и победа Х и победа О. Для того, чтобы избежать ноль после суммирования -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):
если в списке mov_map хотя бы единожды встречается -1, то это победный выбор.
если в списке mov_map -1 нет, а присутствует 1, то для Х (напомню, ХО=-1) это ход для спасения от поражения.
если в списке 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)Вне зависимости какой игрок (Х или О): любое значение с модулем 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) выбирает мышкой желаемую клетку на поле функцией user_click(), которая должна возвратить значение от 0 до 8 переменной move (согласно схеме на рис.1). Если move=None, значит ожидается повторный клик. Удобно обходиться без обработки ошибок если пользователь промахивается мимо поля, просто разместив это условие в цикле на первом месте с повтором (continue).
Если все же пользователь указал пустую клетку 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()Игрок О - компьютер - (ХО==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()В случае чьей-то победы или ничьи - перезагрузка reset_game().
В главном цикле обновляется картинка на экране 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() это:
ход Х (пользователь), прорисовка и смена игрока, проверка на победу.
алгоритм поиска хода для О (компьютер), прорисовка и смена игрока, проверка на победу.
O_player(). Устроена аналогично, но зеркально наоборот.
Недостаток алгоритма?
С точки зрения пользователя - недостатки алгоритма компьютерного хода - это увеличенные шансы для победы человека. На поле 3х3 важны первые три хода, когда О-игрок мешает Х сделать вилку, т.е. одновременно появляются две клетки для безоговорочной победы Х (Рис.7).
Таким образом, если проработать все варианты дебютов "от вилки" (их три), то алгоритм станет мощнее. Однако это окочательно "засушит" игру до постоянной ничьи. Например, у детей пропадет всякий азарт и желание сыграть (проверил на своих). Поэтому решено оставить только "защиту от дурака" в виде постановки "О" в центр, что уменьшило шансы для победы "Х", но не исключило их. Либо можно отказаться даже от этого ради азарта.
Финальный код
Начальное меню и выбор пользователем роли в статье не рассматривалось, там все предельно просто и понятно.
Проект финального кода и три картинки для скачивания находятся в архивном файле здесь.
Анонс второй части статьи
Запуск игр компьютера против самого себя.
Функции для записи всех игр пошагово в CSV-файл.
Анализ и выбор нужного хода из базы данных: какой способ оптимален?
Результаты: это ли машинное обучение?