Python. Напишем игру в спички с хардкорным ИИ

Возможно многие из вас играли в детстве в игру "спички" или "палочки" где игроки по очереди убирают с поля от 1 до 3 спичек. Проигравшим считается тот кто возьмет последнюю спичку. Игра достаточно примитивная, поэтому меня заинтересовала возможность написать для нее ИИ. Ну и соответственно саму игру в довесок :)

Про ИИ будет абзац чуть ниже, а сейчас приступим к написанию самой игры.

Заранее хочу отметить, что данный код не претендует на эталонность, наверное поэтому я не разработчик. Тут можно много чего доработать и улучшить. Это факт.

Ну и для начала: игра будет консольной, поэтому и поле и надписи будут выводиться символами. Итак, из чего будет состоять наше приложение? Ну во-первых какие-то базовые параметры самой игры: величина поля (т.е. кол-во спичек на столе), минимальное и максимальное число спичек которые игрок может потянуть. Еще игра должна помнить чей сейчас ход. Кроме того в самой игре участвуют два игрока, значит нам нужна также сущность «игрок». Ну и не забываем про поле. Это конечно громко сказано, ведь у нас по сути просто спички лежащие в ряд, но пусть это будет «полем» или «картой» игры. Поехали!

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

class Game(object): def __init__(self, length, min_turn, max_turn): self.min_turn = min_turn self.max_turn = max_turn self.game_map = Map(length) self.ai_map = [False for _ in range(self.game_map.length)] self.players_list = [] self.current_player = None #self.fill_ai_map()

Класс игрока. Что нам нужно знать про игрока? Его имя (name). Он человек или ИИ (is_ai), а так же как-то различать на игровом поле какие палочки он взял, т.е. нужен цвет (color):

class Player(object): def __init__(self, name, is_ai, color): self.name = name self.is_ai = is_ai self.color = color

Ну и класс поле или же «карта». Определим какими символами будут обозначаться сыгранные спички и несыгранные. Так же помним: у поля есть длина. Добавим переменную left где будем записывать сколько спичек осталось разыграть. А список filed для начала заполним не сыгранными спичками (он и будет основной игровой картой):

class Map(object): unplayed_cell = ' I ' played_cell = ' i ' def __init__(self, length): self.length = length self.left = length self.field = [self.unplayed_cell for _ in range(self.length)]

Функции это те или иные действия которые может выполнять объект.

Игра должна запрашивать ввод данных. В нашем случае количество спичек. Я решил разделить реализацию ввода игрока и ИИ на две функции: get_player_input и get_ai_input в зависимости от того текущий игрок ИИ (current_player.is_ai) или нет. Тут же опишем функцию совевршения хода. Игра запросит ввод и потом применит его на карту:

def get_input(self): return self.get_ai_input() if self.current_player.is_ai else self.get_player_input() def make_turn(self): turn = self.get_input() self.game_map.apply_turn(turn, self.current_player.color)

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

Для человека игра будет вежливо просить ввести кол-во спичек. Далее защита от дурака если пользователь ввел не число. И далее еще пару проверок на допустимость значения после прохождения которых игра примет ход (return player_input):

def get_player_input(self): while True: try: print( '{}, Ваш ход! От {} до {}: ' .format(self.current_player.get_name_with_color(), self.min_turn, self.max_turn)) player_input = int(input()) except ValueError: print('Ошибка: введите число!') continue if self.min_turn > player_input: print('Ход меньше допустимого!') continue if player_input > self.max_turn: print('Ход больше допутимого!') continue if player_input > self.get_matches_left(): print('Ход больше оставшегося числа спичек!') continue break return player_input

Для игрока-ии всё будет немного по-другому. Это опишем чуть позже. Пока просто pass:

def get_ai_input(self): pass

Продолжаем с функциями которые должна поддерживать игра.

При запуске игры должна выводиться какая-то вступительная информация и первый игрок по списку становится текущим. Можно сделать рандом. Это уже по желанию. Создадим на это отдельную функцию:

def start_game(self): self.current_player = self.players_list[0] game.clear_screen() print('\nПоле:\t\t{} спичек'.format(self.game_map.length)) print('Ход:\t\tOт {} до {} спичек'.format(self.min_turn, self.max_turn)) print('Правила:\tИгрок взявший последнюю спичку - проиграл') print('\n\nN E W G A M E')

Нам нужна функция на добавление игроков:

def add_player_to_game(self, player): if type(player) == Player and len(self.players_list) < 2: self.players_list.append(player)

Также добавим функцию которая будет очищать экран перед каждым новым ходом. Здесь небольшой финт ушами т.к. в зависимости от операционной системы очистка экрана консоли происходит с помощью cls или clear:

@staticmethod def clear_screen(): os.system('cls') if os.name == 'nt' else os.system('clear')

Ну и наконец функция которая меняет активного игрока:

def switch_to_next_player(self): self.current_player = self.players_list[0] if self.current_player is self.players_list[1] else \ self.players_list[1]

Что мы еще забыли?

Каждый ход проверять можно ли играть дальше. Если спичек на поле осталось меньше чем минимальный ход или совсем не осталось — игра окончена.
Так же докинем сюда функцию draw которая по факту просто вызывает отрисовку карты
функцию которая возвращает количесвто оставшихся спичек

def is_game_over(self): return True if self.get_matches_left() <= self.min_turn or self.get_matches_left() == 0 else False def draw(self): self.game_map.draw() def get_matches_left(self): return self.game_map.left

Разобрались с функциями игры. Переходим к функциям карты. Их буквально пара штук. Отрисовка карты и заполненине поля после хода игрока. Заполняем определенное количество цветом текущего игрока который получаем при вызове функции:

def draw(self): sys.stdout.write('\n[') for _ in range(self.length): sys.stdout.write(self.field[_]) sys.stdout.write(']')

У класса игрока только одна функция которая возвращает его имя в цвете. Просто чтобы комфортнее потом работать со строками:

def get_name_with_color(self): return '{}{}{}'.format(self.color, self.name, reset_color)

Ну и основной цикл конечно. Здесь многа букав но смысл в целом прост. Мы создаём саму игру с полем 20 и заданными величинами хода. Далее добавляем пару игроков. Стартуем игру. Ну и погнали в бесконечном цикле while True: рисуем поле, пишем инфу сколько спичек осталось, проверяем вдруг игра завершилась. Если так — значит текущий игрок проиграл (вспоминаем как проверяли is_game_over). Если игра еще не закончена — делаем ход. Всё. Можно стирать экран и передавать управление другому игроку (game.switch_to_next_player()). Здесь небольшой костылёк на проверку остались ли еще ходы. Т.к. если ходов не осталось (в случае если игрок совсем странный и решил лично взять последнюю спичку) то ход передавать уже не нужно, а в начале следующего цикла он уже будет считаться проигравшим. Ну и как мы видим из бесконечного цилка игры есть только один выход — is_game_over после которого идёт break — выход из цикла. В конце делаем input('G A M E O V E R ') чтобы приложение не сразу закрылось, а подождало любого ввода.

if __name__ == '__main__': game = Game(length=20, min_turn=1, max_turn=3) game.add_player_to_game(Player(name='Ромуальд', is_ai=False, color=color_blue)) game.add_player_to_game(Player(name='ЦПУ', is_ai=True, color=color_green)) game.start_game() while True: game.draw() #game.draw_ai_map() print('\n Спичек осталось: {}'.format(game.get_matches_left())) if game.is_game_over(): print('\nИгрок {} проиграл!'.format(game.current_player.get_name_with_color())) game.switch_to_next_player() print('Поздравляю, {}, вы выиграли!'.format(game.current_player.get_name_with_color())) break game.make_turn() game.clear_screen() if game.get_matches_left() > 0: game.switch_to_next_player() input('\nG A M E O V E R ')

Акей. Фух. Разобрались с самой игрой. Уже можно играть вдвоём. Нужно только поменять второму игроку параметр is_ai на False. Теперь перейдем ко второй части.

Это конечно громко сказано) Но давайте по порядку. Самый простой способ сделать ИИ это просто выбирать в качестве хода случайное число в диапазоне от min_turn до max_turn. И если на первых ходах это еще хоть как-то оправдано (на самом деле нет), то под конец игры хотелось бы какой-то осмысленности в действиях ИИ. И вот я сел и стал раскручивать логику победы от конца игры в начало. Взял стандартные условия: от 1 до 3 спичек за ход. Будем рассматривать варианты когда игроки не поддаются друг-другу и не тупят. В таком случае победа гарантируется только если своим ходом ты берёшь предпоследнюю спичку. Последняя спичка остается следующему игроку и у него минимальный ход эта самая спичка. Вы красавчик! Пришли к выводу что победа сводится к взятию предпоследней спички:

[ I I I I I I I I I I I I I I I I I I I I ] [ ^ ]

Что же надо сделать чтобы ее взять? Мы можем брать от 1 до 3 спичек. Берем по максимуму. Как итог понимаем с какой спички должен ходить предыдущий игрок чтобы мы следующим ходом наверняка взяли предпоследнюю спичку:

[ I I I I I I I I I I I I I I I x I I I I ] [ ^ ]

А раз мы хотим чтобы он ходил именно с этой спички нам нужно обязательно взять предыдущую. Выходит мы нашли новую спичку взяв которую мы наверняка победим:

[ I I I I I I I I I I I I I I I x I I I I ] [ ^ ^ ]

Так можно повторять пока не дойдём до начала. Тем самым отметив для себя выигрышные спички.

Наверное в покере это называется считать карты и в приличных заведениях за такое бьют в щи. Но мы же пишем «ультимативный ИИ» :)

Результат подсчета выигрышных спичек например для 25 с ходом в 1-3 спички:

[ I I I I I I I I I I I I I I I I I I I I I I I I I ] [ ^ ^ ^ ^ ^ ^ ]

Заметили магию? Магия заключается в том что если оба игрока играют идеально — первый полюбому проиграл т.к. одним ходом не сможет дотянуться до первой выигрышной спички. Если бы поле было 20 спичек ситуация была бы противоположной: первый игрок сразу берет 3 спички и игра в кармане.

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

Собственно вот мы и изобрели алгоритм поведения ИИ:

Определяем выигрышные спички на столе
Проверяем ближайшую выигрышную спичку
Если длины хода хватает чтобы ее взять — так и ходим до нее
Если длины хода не хватает — берем случайную величину хода

Осталось только чтобы в начале игры ИИ посчитал для себя выигрышные позиции. Для этого методом проб и ошибок была написана вот такая функция, которая учитывая минимальную и максимальную величину хода. Если в кратце, то мы пробегаем по всем спичкам от начала до конца вычисляем для каждой спички порядковый номер, считая с предпоследней (всегда выигрышной), и проверяем остаток от деления этого номера на сумму min_turn и max_turn. Если он в диапазоне от 0 до min_trun — спичка победная.

def fill_ai_map(self): for cell_index in range(self.game_map.length): cell = self.game_map.length - cell_index - 1 if 0 < cell_index % (self.min_turn + self.max_turn) <= self.min_turn: self.ai_map[cell] = True

Эту функцию мы поместим в класс Game и будем вызывать сразу при инициализации. Выше она была закомменчена в коде

Ну и давайте вернёмся к функции get_cpu_input которую мы пропустили:

def get_ai_input(self): start_cell = self.game_map.length - self.get_matches_left() - 1 for x in range(start_cell, self.game_map.length): if self.ai_map[x] and self.min_turn <= x - start_cell <= self.max_turn: return x - start_cell if x - start_cell > self.max_turn: return rand(self.min_turn, self.max_turn)

Тут все просто: ИИ пробегается по спичкам от первой незанятой в текущем ходу пытаясь найти следующую выигрышную и сразу проверяет входит ли она в допустимую величину хода. Если выигрышной спички в ходовой доступности нет — просто возвращает случайное допустимое значение хода.

Собственно всё. Победить такой ИИ можно только ни разу не ошибившись.