⭕ Крестики-нолики ❌ Часть 0

Начался новый учебный год, а это значит, что появились новые курсачи по программированию. В этом году я выбрал тему "реализовать крестики-нолики с игрой против бота, который использует Альфа-бета-отсечение". Не дословно, конечно, конкретное ТЗ я прикрепил к репозиторию проекта.

Так вот, реализовать консольные крестики-нолики легко, займёт около 200 строчек кода. Но это вариант с двумя игроками, а тут нужно реализовать игру против бота, с этим очень прямо вообще крутым алгоритмом.

Тем более, нужно реализовать не простую версию 3х3, а чтобы размеры игрового поля регулировал пользователь.

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

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

Мне повезло, в "полезных ссылках" я нашёл целых две рабочие статьи (третья просто не загружалась). Очень простой пост на Хабре, где автор наглядно показал и реализовал альфа-бета-отсечение, а вторую я даже смотреть не стал, слишком сухо и сложно сложно сложно.

Так вот, прошло два дня с момента выбора темы для курсовой работы. Я уже реализовал версию 3х3, но без отсечения. Пока только заготовки. Саму логику буду описывать на следующей неделе. Хотя ещё не до конца всё понял.

С бинарными деревьями у меня не очень отношения (литкод не считается). Конечно, я реализовывал алгоритмы на деревьях, но сама концепция мне далась не сразу. А тут целый алгоритм для бота. Ну посмотрим что будет.

Пока что я надеюсь уложиться в один cpp'шник и 400 строк. Прошлый курсач у меня занял около 12 файлов вроде (ну в том случае так нужно было сделать по ТЗ). Надеюсь в этот раз такого не будет.

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

По поводу языка

Долго думал на чём буду писать, очень хотел на питоне, используя pyGame, но потом вспомнил, что один из плюсов С++ (извините за тавтологию) то, что код можно запускать на ардуинке. Вообще очень хочу сделать маленькую консоль на ардуино нано и загрузить туда код. Будет мини геймбой с одной игрой "крестики-нолики Dark souls style". При чём тут Dark souls? Просто выиграть у бота с этим алгоритмом практически невозможно.