Как создать крестики нолики в python

Крестики-нолики

Очень полезно в целях изучения языка программирования написать на нем несколько простых программ. Здесь мы представим игру крестики-нолики, которая написана на Python 3 с графическим интерфейсом.

О программе

В этой игре можно помериться силами с компьютером. Первый ход за игроком. Но победить искусственный интеллект в этом противостоянии будет не так уж и просто. Компьютер не делает «зевков» и если у него есть шанс победить, он непременно им воспользуется.

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

Игрок ставит крестики, а компьютер нолики. Как всегда, побеждает тот, кто первый составит линию из своих символов: по горизонтали, вертикали или диагонали.

Библиотеки и объявление переменных

Для отображения графики будем использовать стандартную библиотеку Tkinter, которая устанавливается вместе с Python. Так же нам потребуется библиотека random для того, чтобы получать случайные числа, благодаря которым ходы компьютера будут неожиданными.

Это также стандартная библиотека Python. Так что ничего дополнительно устанавливать не надо. Просто подключаем их с помощью import . Создаем окно root , устанавливаем ему заголовок и объявляем необходимые переменные:

• game_run – в эту переменную будем записывать False при завершении игры, чтобы запретить делать ходы когда уже выявлен победитель.
• field – это будет двумерный список, в котором будут храниться кнопки игрового поля. Ходом будет изменение надписи на кнопке на символ «X» или «O».
• cross_count в этой переменной мы будем отслеживать количество крестиков на поле. Чтобы по выставлению пятого крестика, в случае если никто не выиграл фиксировать ничью.

from tkinter import * import random root = Tk() root.title('Criss-cross') game_run = True field = [] cross_count = 0

Обработка нажатия кнопок

Функция new_game будет вызываться при нажатии кнопки начала новой игры. На поле убираются все крестики и нолики. Цвет кнопок делаем бледно-лиловым. Устанавливаем глобальные переменные game_run и cross_count в начальные значения. Это глобальные переменные к которым пытаемся обратиться из функции. Поэтому перед попыткой изменить их значение, в Python надо использовать ключевое слово global .

def new_game(): for row in range(3): for col in range(3): field[row][col]['text'] = ' ' field[row][col]['background'] = 'lavender' global game_run game_run = True global cross_count cross_count = 0

Функция click будет вызываться после нажатия на поле, то есть при попытки поставить крестик. Если игра еще не завершена, то крестик ставится. После этого увеличиваем счетчик количества выставленных крестиков.

Потом проверяем с помощью функции check_win , не победили ли мы этим ходом. Если еще не выявлен победитель и есть еще ходы, то выполняет ход компьютер функцией computer_move , и также после хода идет проверка выигрыша.

def click(row, col): if game_run and field[row][col]['text'] == ' ': field[row][col]['text'] = 'X' global cross_count cross_count += 1 check_win('X') if game_run and cross_count < 5: computer_move() check_win('O')

Проверка победы

Функция check_win осуществляет проверку выигрыша. Она перебирает все возможные комбинации полей, образующих линию и вызывает с ними функцию check_line . Переменная smb – это символ «X» или «O», то есть крестики или нолики. Если задан «O», то проверяется: не победил ли компьютер.

Если зафиксирован выигрыш, то меняем цвет фона кнопок, составляющих линию на розовый. А также записываем в game_run значение False .

def check_win(smb): for n in range(3): check_line(field[n][0], field[n][1], field[n][2], smb) check_line(field[0][n], field[1][n], field[2][n], smb) check_line(field[0][0], field[1][1], field[2][2], smb) check_line(field[2][0], field[1][1], field[0][2], smb) def check_line(a1,a2,a3,smb): if a1['text'] == smb and a2['text'] == smb and a3['text'] == smb: a1['background'] = a2['background'] = a3['background'] = 'pink' global game_run game_run = False

Проверяем все возможные варианты, так как теоретически можно одним ходом составить сразу 2 линии.

Действия компьютера

Ход компьютера рассчитывается в функции computer_move . Алгоритм его действий следующий:

1. Проверка возможности победы. Если компьютеру представился шанс победы – он не должен его упустить. Сразу же делает победу.
2. Проверка возможной победы противника за один ход. Если игрок выставил два крестика в ряд, компьютер пытается разрушить планы игрока.
3. Случайный ход. Так как победить нет возможности и нет угрозы проигрыша, то выбирается случайное свободное поле. В бесконечном цикле wile перебираются случайные числа, пока они не выпадут на не занятое поле.

def can_win(a1,a2,a3,smb): res = False if a1['text'] == smb and a2['text'] == smb and a3['text'] == ' ': a3['text'] = 'O' res = True if a1['text'] == smb and a2['text'] == ' ' and a3['text'] == smb: a2['text'] = 'O' res = True if a1['text'] == ' ' and a2['text'] == smb and a3['text'] == smb: a1['text'] = 'O' res = True return res def computer_move(): for n in range(3): if can_win(field[n][0], field[n][1], field[n][2], 'O'): return if can_win(field[0][n], field[1][n], field[2][n], 'O'): return if can_win(field[0][0], field[1][1], field[2][2], 'O'): return if can_win(field[2][0], field[1][1], field[0][2], 'O'): return for n in range(3): if can_win(field[n][0], field[n][1], field[n][2], 'X'): return if can_win(field[0][n], field[1][n], field[2][n], 'X'): return if can_win(field[0][0], field[1][1], field[2][2], 'X'): return if can_win(field[2][0], field[1][1], field[0][2], 'X'): return while True: row = random.randint(0, 2) col = random.randint(0, 2) if field[row][col]['text'] == ' ': field[row][col]['text'] = 'O' break

Графический интерфейс

Все элементы графического интерфейса мы будем размещать с помощью упаковщика grid . В цикле добавим кнопки игрового поля. Они будут храниться в двумерном список. В языке программирования Python добавляют элементы в список с помощью метода append .

Свойство colorspan у кнопки начала игры выставляем в 3, чтобы он занимал всю ширину таблицы

for row in range(3): line = [] for col in range(3): button = Button(root, text=' ', width=4, height=2, font=('Verdana', 20, 'bold'), background='lavender', command=lambda row=row, col=col: click(row,col)) button.grid(row=row, column=col, sticky='nsew') line.append(button) field.append(line) new_button = Button(root, text='new game', command=new_game) new_button.grid(row=3, column=0, columnspan=3, sticky='nsew') root.mainloop()

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

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

Пишем игру крестики-нолики на Python на двоих и против компьютера

Если вы учитесь программировать, то программирование игр — это очень хороший способ освоить алгоритмы и структуры данных. В этом уроке мы разберем запрограммируем игру крестики нолики на Python. Полный код программы с искусственным интеллектом для игрока-компьютера занимает всего 140 строк. В варианте игры где человек играет против человека — раза в два меньше.

Игра крестики-нолики хороша тем, что ее правила знакомы всем с детства и понятны каждому. Это даст вам возможность сосредоточиться именно на процессе программирования, а не на анализе правил игры. В процессе работы над игрой крестики-нолики мы будем использовать только стандартные функции языка Python без подключения каких либо сторонних библиотек.

Шаг 1. Подбор структуры данных

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

В языке программирования Python наилучшим выбором будет список из 9 значений. Назовем его maps. Первоначально этот список будет заполнен цифрами от 1 до 9. Это сделано для удобства организации диалога с пользователем. Пользователю будет достаточно ввести символ от 1 до 9, что бы мы смогли понять куда он сделал ход. После того как ход сделан, цифру мы заменим на символ нолика или крестика. (Можно было заполнить цифрами от 0 до 8. В этом случает было бы удобнее работать — цифра и есть индекс элемента в списке, но первый нолик будет смущать игроков).

Еще мы создадим второй список victories в котором будем хранить информацию обо всех выигрышных комбинациях. И нам будет нужно создать функцию print_maps, которая будет выводить содержимое нашего списка maps на экран.

# Инициализация карты maps = [1,2,3, 4,5,6, 7,8,9] # Инициализация победных линий victories = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]] # Вывод карты на экран def print_maps(): print(maps[0], end = " ") print(maps[1], end = " ") print(maps[2]) print(maps[3], end = " ") print(maps[4], end = " ") print(maps[5]) print(maps[6], end = " ") print(maps[7], end = " ") print(maps[8])

Со структурами данных разобрались.

Шаг 2. Выполнение очередного хода и проверка на выигрыш

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

Первая функция будет рисовать на поле крестик или нолик, в зависимости от того что в нее передали. Позицию в нее так же нужно будет передавать. Вставлять переданный элемент мы будем по индексу. Индекс определим функцией index (если бы мы пронумеровали от 0 до 8 элементы в maps, то переданное значение и было бы индексом. Можете попробовать — будет на одну строчку кода меньше.)

# Сделать ход в ячейку def step_maps(step,symbol): ind = maps.index(step) maps[ind] = symbol

После каждого ходы мы должны проверять — не победил ли кто то из игроков. Для этого переберем все победные линии из списка victories и проверим нет ли там комбинации из трех крестиков или трех ноликов.

# Получить текущий результат игры def get_result(): win = "" for i in victories: if maps[i[0]] == "X" and maps[i[1]] == "X" and maps[i[2]] == "X": win = "X" if maps[i[0]] == "O" and maps[i[1]] == "O" and maps[i[2]] == "O": win = "O" return win

Эта функция вернет «X» в случае победы крестиков и «O» в случае победы ноликов.

Шаг 3. Основный игровой цикл

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

# Основная программа game_over = False player1 = True while game_over == False: # 1. Показываем карту print_maps() # 2. Спросим у играющего куда делать ход if player1 == True: symbol = "X" step = int(input("Человек 1, ваш ход: ")) else: symbol = "O" step = int(input("Человек 2, ваш ход: ")) step_maps(step,symbol) # делаем ход в указанную ячейку win = get_result() # определим победителя if win != "": game_over = True else: game_over = False player1 = not(player1) # Игра окончена. Покажем карту. Объявим победителя. print_maps() print("Победил", win)

Вот полный код программы крестики-нолики на Python для двух игроков:

# Инициализация карты maps = [1,2,3, 4,5,6, 7,8,9] # Инициализация победных линий victories = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]] # Вывод карты на экран def print_maps(): print(maps[0], end = " ") print(maps[1], end = " ") print(maps[2]) print(maps[3], end = " ") print(maps[4], end = " ") print(maps[5]) print(maps[6], end = " ") print(maps[7], end = " ") print(maps[8]) # Сделать ход в ячейку def step_maps(step,symbol): ind = maps.index(step) maps[ind] = symbol # Получить текущий результат игры def get_result(): win = "" for i in victories: if maps[i[0]] == "X" and maps[i[1]] == "X" and maps[i[2]] == "X": win = "X" if maps[i[0]] == "O" and maps[i[1]] == "O" and maps[i[2]] == "O": win = "O" return win # Основная программа game_over = False player1 = True while game_over == False: # 1. Показываем карту print_maps() # 2. Спросим у играющего куда делать ход if player1 == True: symbol = "X" step = int(input("Человек 1, ваш ход: ")) else: symbol = "O" step = int(input("Человек 2, ваш ход: ")) step_maps(step,symbol) # делаем ход в указанную ячейку win = get_result() # определим победителя if win != "": game_over = True else: game_over = False player1 = not(player1) # Игра окончена. Покажем карту. Объявим победителя. print_maps() print("Победил", win)

Вот так выглядит процесс игры в крестики-нолики для 2 игроков:

1 2 3 4 5 6 7 8 9 Человек 1, ваш ход: 5 1 2 3 4 X 6 7 8 9 Человек 2, ваш ход: 1 O 2 3 4 X 6 7 8 9 Человек 1, ваш ход: 6 O 2 3 4 X X 7 8 9 Человек 2, ваш ход: 4 O 2 3 O X X 7 8 9 Человек 1, ваш ход: 3 O 2 X O X X 7 8 9 Человек 2, ваш ход: 7 O 2 X O X X O 8 9 Победил O

Шаг 4. Добавление алгоритма для искусственного интеллекта в игре крестики-нолики

А вот теперь мы подобрались к самому интересному моменту в программировании. Нам нужно создать искусственный интеллект, который всегда будет выигрывать или сводить игру к ничьей. На самом деле в игре крестики-нолики такой алгоритм написать совсем не сложно.

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

#Искусственный интеллект: поиск линии с нужным количеством X и O на победных линиях def check_line(sum_O,sum_X): step = "" for line in victories: o = 0 x = 0 for j in range(0,3): if maps[line[j]] == "O": o = o + 1 if maps[line[j]] == "X": x = x + 1 if o == sum_O and x == sum_X: for j in range(0,3): if maps[line[j]] != "O" and maps[line[j]] != "X": step = maps[line[j]] return step

А сейчас мы напишем функцию для поиска очередного лучшего хода для искусственного интеллекта. Запрограммируем такой алгоритм для каждого хода (компьютер играет ноликами):

1. Если этим ходом можем выиграть — выигрываем (уже 2 нолика стоят на одной из линий). Иначе идем к шагу 2.
2. Если можем помешать выиграть человеку — мешаем ( у человека уже 2 крестика на линии — ставим на нее нолик). Иначе идем к шагу 3.
3. Если на линии одна наша фигура — ставим вторую. Если пока ни одной нашей фигуры — идем к шагу 4.
4. Ставим нолик в центр. Если центр занят идем к шагу 5.
5. Ставим в левый верхний угол.

А вот так все это выглядит в программе на Python:

#Искусственный интеллект: выбор хода def AI(): step = "" # 1) если на какой либо из победных линий 2 свои фигуры и 0 чужих - ставим step = check_line(2,0) # 2) если на какой либо из победных линий 2 чужие фигуры и 0 своих - ставим if step == "": step = check_line(0,2) # 3) если 1 фигура своя и 0 чужих - ставим if step == "": step = check_line(1,0) # 4) центр пуст, то занимаем центр if step == "": if maps[4] != "X" and maps[4] != "O": step = 5 # 5) если центр занят, то занимаем первую ячейку if step == "": if maps[0] != "X" and maps[0] != "O": step = 1 return step

Немного перепишем и основной цикл игры. Теперь вместо человека 2 ход будет делать компьютер. Компьютер каждый раз будет говорить куда делает ход. Если компьютер не дает ответ, значит наметилась ничья — завершаем партию и объявляем ничью. Вот таким станет основной цикл игры, когда мы перепишем программу крестики-нолики под игру против компьютера:

# Основная программа game_over = False human = True while game_over == False: # 1. Показываем карту print_maps() # 2. Спросим у играющего куда делать ход if human == True: symbol = "X" step = int(input("Человек, ваш ход: ")) else: print("Компьютер делает ход: ") symbol = "O" step = AI() # 3. Если компьютер нашел куда сделать ход, то играем. Если нет, то ничья. if step != "": step_maps(step,symbol) # делаем ход в указанную ячейку win = get_result() # определим победителя if win != "": game_over = True else: game_over = False else: print("Ничья!") game_over = True win = "дружба" human = not(human) # Игра окончена. Покажем карту. Объявим победителя. print_maps() print("Победил", win)

Готовая программа для игры в крестики нолики против компьютера на Python

Вот готовая программа для для игры против искусственного интеллекта.

# Инициализация карты maps = [1,2,3, 4,5,6, 7,8,9] # Инициализация победных линий victories = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]] # Вывод карты на экран def print_maps(): print(maps[0], end = " ") print(maps[1], end = " ") print(maps[2]) print(maps[3], end = " ") print(maps[4], end = " ") print(maps[5]) print(maps[6], end = " ") print(maps[7], end = " ") print(maps[8]) # Сделать ход в ячейку def step_maps(step,symbol): ind = maps.index(step) maps[ind] = symbol # Получить текущий результат игры def get_result(): win = "" for i in victories: if maps[i[0]] == "X" and maps[i[1]] == "X" and maps[i[2]] == "X": win = "X" if maps[i[0]] == "O" and maps[i[1]] == "O" and maps[i[2]] == "O": win = "O" return win #Искусственный интеллект: поиск линии с нужным количеством X и O на победных линиях def check_line(sum_O,sum_X): step = "" for line in victories: o = 0 x = 0 for j in range(0,3): if maps[line[j]] == "O": o = o + 1 if maps[line[j]] == "X": x = x + 1 if o == sum_O and x == sum_X: for j in range(0,3): if maps[line[j]] != "O" and maps[line[j]] != "X": step = maps[line[j]] return step #Искусственный интеллект: выбор хода def AI(): step = "" # 1) если на какой либо из победных линий 2 свои фигуры и 0 чужих - ставим step = check_line(2,0) # 2) если на какой либо из победных линий 2 чужие фигуры и 0 своих - ставим if step == "": step = check_line(0,2) # 3) если 1 фигура своя и 0 чужих - ставим if step == "": step = check_line(1,0) # 4) центр пуст, то занимаем центр if step == "": if maps[4] != "X" and maps[4] != "O": step = 5 # 5) если центр занят, то занимаем первую ячейку if step == "": if maps[0] != "X" and maps[0] != "O": step = 1 return step # Основная программа game_over = False human = True while game_over == False: # 1. Показываем карту print_maps() # 2. Спросим у играющего куда делать ход if human == True: symbol = "X" step = int(input("Человек, ваш ход: ")) else: print("Компьютер делает ход: ") symbol = "O" step = AI() # 3. Если компьютер нашел куда сделать ход, то играем. Если нет, то ничья. if step != "": step_maps(step,symbol) # делаем ход в указанную ячейку win = get_result() # определим победителя if win != "": game_over = True else: game_over = False else: print("Ничья!") game_over = True win = "дружба" human = not(human) # Игра окончена. Покажем карту. Объявим победителя. print_maps() print("Победил", win)

Вот пример игрового процессе. В этой игре победил компьютер:

1 2 3 4 5 6 7 8 9 Человек, ваш ход: 1 X 2 3 4 5 6 7 8 9 Компьютер делает ход: X 2 3 4 O 6 7 8 9 Человек, ваш ход: 2 X X 3 4 O 6 7 8 9 Компьютер делает ход: X X O 4 O 6 7 8 9 Человек, ваш ход: 4 X X O X O 6 7 8 9 Компьютер делает ход: X X O X O 6 O 8 9 Победил O

Вы можете прямо сейчас поиграть в крестики нолики против компьютера или друг против друга. Просто скопируйте текст программы на этой странице и вставьте его в поле программы в этом онлайн эмуляторе Python: https://replit.com/languages/python3 или тут https://www.onlinegdb.com/online_python_compiler

Домашнее задание

У нас получилась довольно беспощадная программа. Ее искусственный интеллект победить не возможно. Человек либо проигрывает, либо играет в ничью. Подумайте как можно дать человеку иногда выигрывать? Возможно вы захотите создать несколько уровней. Например в первом искусственный интеллект очень слаб, дальше он умнет. Или у вас будет на выбор несколько режимов игры на выбор: слабый ИИ, средний и непобедимый.

В общем ваша задача немного ослабить искусственный интеллект в нашей игре крестики-нолики. Сделать его чуть более человечным.

ushchent / Tic tac toe in Jupyter Notebook

Clone via HTTPS Clone with Git or checkout with SVN using the repository’s web address.

Learn more about clone URLs

Крестики-нолики на питоне

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

# Простейшее и наименее совершенное решение игры в крестики-нолики

# по заданию Milestone Project 1 из Complete Python Bootcamp,

# см. https://github.com/jmportilla/Complete-Python-Bootcamp

game_matrix = [[None, None, None], [None, None, None], [None, None, None]]

game_is_on = True

while game_is_on:

# Крестик - латинская буква X, нолик - латинская буква O

# Ходы принимаются в формате [0][0] = "X" или [2][1] = "О"

move = input()

exec("game_matrix" + move)

for row in game_matrix:

print(row)

reference_matrix = [

game_matrix[0],

game_matrix[1],

game_matrix[2],

[i[0] for i in game_matrix],

[i[1] for i in game_matrix],

[i[2] for i in game_matrix],

[game_matrix[0][0], game_matrix[1][1], game_matrix[2][2]],

[game_matrix[0][2], game_matrix[1][1], game_matrix[2][0]]

]

for item in reference_matrix:

result = list(set(item))

if len(result) == 1 and result[0] != None:

print("Game over!")

game_is_on = False

break

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

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

1. Следующий вариант, если в одну клетку сходятся две победные комбинации игрока Х, при этом ход игрока О (ХО=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):

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)

1. Вне зависимости какой игрок (Х или О): любое значение с модулем 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()

1. Игрок О - компьютер - (ХО==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()

1. В случае чьей-то победы или ничьи - перезагрузка reset_game().
2. В главном цикле обновляется картинка на экране 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. Результаты: это ли машинное обучение?