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

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

(55)
Можно попробовать искать множества доступных улиц с обоих концов
Т.е.
из начальной точки выбрать доступные улицы для движения (мн1)
из конечной точки выбрать доступные улицы для движения (мн2)
—
выбрать доступные улицы для мн1
выбрать доступные улицы для мн2
—
Искать до тех пор, пока мн1 и мн2 не пересекутся или (мн1 или мн2 будуи содержать множество всех доступных улиц)
—
Это при условии, что по улице можно проехать только один раз

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

Войдите как ученик, чтобы получить доступ к материалам школы

Создание конфигураций 1С: пишем «Крестики-нолики» часть 3/3

Автор уроков и преподаватель школы: Владимир Милькин

Заключительная часть разработки Крестиков-ноликов на 1С. После четырнадцатого
шага мы создали пустую процедуру «ХодКомпьютера» и добавили её вызов сразу после нашего хода.

Если вы прерывались (закрывали конфигуратор) после предыдущей части — выполните шаг №2 (открытие конфигуратора) и шаг №3 (открытие дерева конфигурации) . В дереве конфигурации откройте обработку «КрестикиНолики»:
— найдите в ней закладку «Формы»
— откройте там элемент «Форма»
— перейдите в модуль формы (закладка «Модуль» внизу)
— уже после этого переходите к шагу №15

Шаг №15: добавляем переменную Поле для хранения состояний кнопок

Чтобы компьютер смог походить ему нужно проанализировать текущее состояние поля — какие клетки заняты, а какие свободны. Специально для хранения нашего поля заведём переменную «Поле» и расположим её в самом начале модуля:

Завести переменную — пол дела. Нужно её правильно инициализировать (присвоить начальное значение). И делать это лучше всего в самом начале выполнения программы — в обработчике открытия нашей формы.

Шаг №16: добавляем обработчик открытия формы

Чтобы попасть в этот обработчик — вернёмся в визуальное представление формы (закладка «Форма») и выделим (двойным щелчком) элемент «Форма» в окне с элементами:

В окне свойств формы (справа) промотаем полосу прокрутки вниз и найдём там событие «ПриОткрытии«. Щелкнем на кнопке с лупой:

Программа предлагает нам создать обработчик для этого события. Выберем вариант «Создать на клиенте» и нажмем кнопку «ОК»:

Мы перенеслись снова в модуль формы в новую автоматически созданную процедуру «ПриОткрытии«. Вы читаете ознакомительную версию урока, полноценные уроки находятся здесь. Весь код, написанный в этой процедуре будет выполнятся каждый раз при открытии формы обработки:

Шаг №17: в обработчике открытия формы инициализируем переменную Поле

Обработчик ПриОткрытии создан. Чем будем инициализировать переменную Поле? А давайте ещё раз вспомним, что именно мы собираемся в ней хранить. Мы собираемся хранить состояние поля. А вернее состояние его ячеек. Для хранения набора каких-то однотипных данных идеально подойдёт тип массив. Вот его мы и создадим в переменной Поле.

Наша задача вставить в процедуру ПриОткрытии код, который создаст в переменной Поле массив, который будет содержать в себе 3 элемента. Каждый из этих элементов будет также массивом на 3 элемента. Получится поле 3х3.

Чтобы вам стало понятнее, что из себя будет представлять массив «Поле» я приведу такую картинку:

Массив «Поле» это двумерная таблица, к элементам которой мы сможем обращаться по номеру строки и номеру столбца.

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

Вставим в эту процедуру следующий код:

Войдите на сайт как ученик

Авторизуйтесь, чтобы получить доступ ко всем материалам школы

Код очень простой и с подробными комментариями. Все конструкции должны быть вам хорошо знакомы по первым двум модулям обучения, в которых мы изучали встроенный язык 1С. Если это не так, пожалуйста, вернитесь к изучению внутреннего языка 1С (модуль №1 и модуль №2).

Шаг №18: переименовываем все кнопки

Следующая задача дать кнопкам на форме такие имена, чтобы мы смогли из кода легко находить имя кнопки по номеру строки и столбца на поле.

К примеру, кнопку располагающуюся в нулевой строке и нулевом столбце (отсчет будем вести с нуля) назовём «Кнопка00«, а кнопку в первой строке и втором столбце «Кнопка12» и т.д.

Для этого перейдем в визуальное представление формы (закладка «Форма») и выделим двойным щелчком кнопку с именем «НажатиеНаКнопку«:

В окне свойств этой кнопки (справа) найдём свойство «Имя» и изменим его значение на «Кнопка00»:

Изменим имена всех кнопок так, чтобы в итоге все кнопки в группах назывались следующим образом:

Шаг №19: пишем содержание процедуры ХодКомпьютера

Наконец, мы можем определить работу процедуры «ХодКомпьютера». Что будет делать эта процедура? В ней нужно будет пробежаться по каждой из ячеек массива Поле, в котором хранятся состояния ячеек (свободна, занята компьютером, занята игроком). Сравнить каждую из ячеек с пустой строкой (признак того, что она свободна и в неё можно походить) . И если такая ячейка найдётся, поставить в неё «Х» (признак того, что в неё походил компьютер) и не забыть отобразить крестик в соответствующей кнопке на форме.

Код будет таким:

Войдите на сайт как ученик

Авторизуйтесь, чтобы получить доступ ко всем материалам школы

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

Шаг №20: уже можно играться!

Запустим 1С в режиме Предприятие (меню «Отладка«->»Начать отладку«), откроем обработку («Сервис«->»Крестики нолики«) и убедимся, что, в принципе, уже можно играть:

Но вот незадача — компьютер перезатирает наши ходы! А всё дело в том, что в процедуре «НажатиеНаКнопку» мы нолик-то на кнопке отображаем, а вот в массив «Поле» этот нолик не ставим. Поэтому компьютер и не видит наши ходы.

Шаг №21: избавляемся от затирания наших ходов

Изменим процедуру «НажатиеНаКнопку» так, чтобы наш ход проставлялся не только на кнопке, но и в массиве «Поле» (добавленный код очерчен жёлтым цветом):

Войдите на сайт как ученик

Авторизуйтесь, чтобы получить доступ ко всем материалам школы

Попробуем запустить 1С в режиме Предприятие (меню «Отладка«->»Начать отладку«) вновь и поиграть с компьютером. На этот раз наши ходы не будут перезатираться компьютером.

Шаг №22: программируем логику окончания игры

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

Добавим такую проверку. Для этого напишем отдельную функцию «ИграОкончена«, которая будет возвращать Истина или Ложь в зависимости от того — присутствует ли на поле выигрышная комбинация.

Пока определим эту функцию пустой (добавьте её в конец модуля формы) , всегда возвращающей Ложь:

Далее изменим код процедуры «НажатиеНаКнопку», так чтобы после каждого хода (нашего или компьютера) делалась проверка на конец игры. Вы читаете ознакомительную версию урока, полноценные уроки находятся здесь. Будем вызывать функцию «ИграОкончена» и, если функция вернёт Истина, то будем выдавать соответствующее сообщение:

Войдите на сайт как ученик

Авторизуйтесь, чтобы получить доступ ко всем материалам школы

Разработка игры почти окончена. Нам осталось определить логику выполнения функции «ИграОкончена», которая пока что всегда возвращает «Ложь».

Ещё раз вспомним представление нашего массива «Поле»:

И сделаем элементарную проверку всех возможных выигрышных комбинаций на поле:

Снова запускаем режим 1С:Предприятие (меню «Отладка«->»Начать отладку«) и наслаждаемся игрой в Крестики-нолики против компьютера.

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

На этом разработка крестиков-ноликов окончена, давайте же перейдём к следующему проекту.

Войдите на сайт как ученик

Авторизуйтесь, чтобы получить доступ ко всем материалам школы

Для учеников

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

На вопросы учеников — отвечаю по почте, но прежде загляните в ЧАВО (ссылка) .

Реализация игры крестики-нолики

Всем привет! Пишу консольную игру крестики-нолики. В перспективе — создать бота. Реализация игры: есть пронумерованное поле 3х3 от 1 до 9, в котором игроку предлагается поставить крестик или нолик путем ввода соответствующего числа. Пока я создал черновик, где ходит только крестик. И на данный момент для меня представляется затруднительным следующее:

1. как сделать поочередный ход?
2. как установить запрет на изменение крестика на нолик и наоборот?

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

Давайте попробуем сначала. В игру крестики-нолики обычно играю два игрока, у каждого свой символ, соответственно крестик, или нолик и все это происходит на игровом поле произвольного размера.

Игровое поле:

Игрок:

Инициализация

Игровой процесс

Ходят игроки последовательно друг за другом до тех пор пока один из них не выставит свои фишки в ряд (горизонтально, вертикально, или по-диагоналям).

Ага, так, последовательно, друг за другом, пока кто-то не будет признан выигравшим после проверки очередного хода на выполненную/выигрышную комбинацию:

как сделать поочередный ход?
можно использовать переменную типа boolean , где false — первый игрок (крести), а true — второй игрок (нолик).
перед каждым ходом — проверяем кто сейчас ходит.
после каждого хода — инвертируем переменную.

как установить запрет на изменение крестика на нолик и наоборот? вариантом может быть создание второй скрытой матрицы, которая будет наполнена изначально одним значение =0.
и когда игрок делает ход, например "крестик в [1][2]", то значение в этой "скрытой" матрице меняется с 0 на 1.
соответственно перед каждый ходом надо проверять, чему равно значение в "скрытой" матрице.

доп.идея (та же суть, другая реализация).
у вас матрица [3][3], а можно сделать [3][3][1] и в последнем хранить точно так же 0 или 1.
то есть

После нескольких часов всё-таки родил своё решение:

Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.13.43308

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

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

Существует локальная версия с двумя уровнями сложности.

Также в обработке реализована сетевая версия игры (с использованием web-сервисов). Но в силу того, что к опубликованным мною веб-сервисам ни у кого нет доступа (это политика админов) вне нашей локалки, к обработке прилагается еще и конфигурация с веб-сервисами, которую вы можете развернуть у себя.

Надеюсь кому-нибудь будет полезным.

Скачать файлы

Специальные предложения

• Скопировать ссылку
• Перейти

Просмотры 8054

Загрузки 155

Рейтинг 8

Создание 11.05.10 10:17

Обновление 12.05.10 00:00

№ Публикации 70033

Конфигурация Конфигурации 1cv8

Операционная система Не имеет значения

Вид учета Не имеет значения

Доступ к файлу Абонемент ($m)

Код открыт Не указано

См. также

Заполнение контрагентов по ИНН для УТ 10.3 Промо

Заполнение контрагентов по ИНН (1С: Управление торговлей 10.3).

6 стартмани

17.05.2022 3977 32 kostyan7 19

Получение/отправка сообщений RabbitMQ через REST API

Простой пример получения и отправки сообщений в брокер сообщений RabbitMQ через REST API из 1С без сторонних компонент и middleware.

1 стартмани

23.09.2022 3393 6 NikeeNik 12

#KafkaЭтоПросто: Kafka Adapter 1С (Confluent) — отправляем сообщения

Сегодня поднимем в docker kafka с confluent’om, а в 1С, в EDT загрузим проект из репозитория, создадим обработку, в которой несколькими строчками отправим сообщение в kafka через rest proxy и в confluent control center посмотрим на него. Если коротко, то: как отправить сообщение в Kafka несколькими строчками кода без компонент, регистраций и смс.

5 стартмани

24.07.2022 5317 16 huxuxuya 25

Распознавание текста из изображений и PDF с помощью нейросетей Yandex Vision и 1С

Если вам нужно с помощью компьютерного зрения от Yandex быстро распознавать текст из документов и изображений, эта статья для вас!

5 стартмани

13.07.2022 4959 5 kiv1c 4

Конвертация любых адресов, написанных в свободной форме, к ФИАС Промо

Допустим у нас есть база с адресами клиентов, и написаны они могут быть как душе угодно. С опечатками, без индексов, без разделителей, в совершенно любом формате. Вот было бы здорово иметь функцию, которая одним нажатием кнопки преобразует любую белиберду к строгому представлению адреса по ФИАС? Восстановит индекс, исправит опечатки и вернёт на 100% валидный адрес. Для всех, кто мечтательно сказал "ДА!", выкладываю данную обработку.

2 стартмани

30.06.2020 15385 134 XilDen 19

Api идеи для начинающих

Данная обработка подойдет тем, кто только начинает знакомиться с механизмами api в 1С. В обработке представлены взаимодействия с 12 простыми сайтами на примерах. Решения не затрагивают полной документации, а носят лишь ознакомительный характер. Делал на платформе 8.3.20.

1 стартмани

16.06.2022 6368 20 user676027_svikator 5

Делаем табло в обозревателе из 1Ски с нуля за полчаса. Без бутстрапов, реактов и ангуляров. Жизнетрюки от kuzkov.info

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

1 стартмани

02.05.2022 6237 122 Steelvan 0

Обмен данными с Web-сервисами

Обработка предназначена для быстрой настройки обмена данными с Web-сервисами из пользовательского интерфейса.

10 стартмани

29.04.2022 4255 25 ns_bulatov 4

Модуль обмена с QIWI Промо

Компании, которые используют систему моментальных платежей QIWI, ценят ее за удобство по скорости выплат и для платежей по запросу. Но такие переводы сложны для учета, а при большом объеме проводимых операций отнимают много времени и превращаются в дополнительную головную боль. Мы сотрудничали с компаниями, которые отправляют большое количество платеже на QIWI, и часто слышали боль бухгалтеров о том, как им сложно работать с такими переводами. Поэтому мы автоматизировали выплаты через QIWI в 1С и создали модуль интеграции 1С c API QIWI Wallet и QIWI TopUp.

5 стартмани

25.05.2020 13735 2 Neti 10

СБП плати QR (от Сбербанка) для 1С (обычные и управляемые формы)

Внешняя обработка для реализации системы Плати QR в системе 1С.

3 стартмани

08.04.2022 11195 180 S_Morozov 100

Сервис push-уведомлений для 1С (Push Notification Service For 1C — PNS4OneS)

Сервис предназначен для передачи сообщений от сервера 1С клиентским сеансам. В простом случае полученное сообщение отображается у клиента в виде всплывающего окна (процедура 1С ПоказатьОповещениеПользователя). С использованием данного сервиса можно оповещать пользователей о новых задачах, полученных электронных письмах, менеджеров о новых заказах, загруженных с сайта и т. п. Дополнительно имеется возможность передавать произвольные данные и обрабатывать самостоятельно полученные сообщения на клиенте, что позволяет реализовать более сложные сценарии (чаты, отображение прогресса длительной операции на сервере и т. п.).

1 стартмани

02.02.2022 9513 33 ltfriend 9

Создание интерактивных обучающих курсов с помощью Vanessa Interactive

Приветствую Вас, коллеги. Сегодня Вам предлагается рассмотреть технологию создания интерактивных обучающих курсов, системы Onboarding, интерактивной справки для любых конфигураций разработанных на базе платформы 1С при работе в web клиенте. Прошу посмотреть ролик, кому неинтересно, как это работает, можно дальше не читать. Тестировалось на 1С:Предприятие 8.3 (8.3.20.1646).

1 стартмани

02.02.2022 5320 1 Viktor_Ermakov 2

BIM: взаимодействие с платформой Autodesk Forge Промо

Предлагаемый пример демонстрирует широкие возможности для взаимодействия «1С:Предприятие» с платформой Autodesk Forge и позволяет вам получить базовые представления о применения технологий информационного моделирования в строительстве. Поддерживаются все версии платформы от 8.3.12 и выше до 8.3.18.

1 стартмани

25.11.2020 72051 16 kandr 3

Создание простых сайтов на основе http сервисов — tips and tricks

Универсальный метод, html шаблоны, страницы с авторизацией и без, многоязычность, страница авторизации, etc.

1 стартмани

22.01.2022 6919 10 vl-sher1 29

1Scan. Интеграция веб-клиента 1С с устройством Android (смартфон, планшет, ТСД)

Получение из Android устройства данных сканера штрихода, камеры, GPS, широковещательных сообщений и передача в код модуля формы 1С для дальнейшей обработки.

1 стартмани

15.11.2021 7255 35 kild 33

Расширение конфигурации для Web-доступа к 1С (1С в роли back-end)

Для реализации того, чтобы 1С формировала и отдавала страницу, которую можно было бы открыть через браузер было написано расширение, которое позволяет публиковать из 1С произвольные ресурсы, будь то API, сайт или изображения / прочие файлы.

1 стартмани

01.04.2021 15708 18 SaschaG 4

Односторонний файловый обмен с сайтом по ftp (1C 2 Web) Промо

Подходит под любую конфигурацию на управляемом интерфейсе на базе БСП 2.4.4 и выше. Позволяет гибко настроить выгрузку, практически любых, данных по расписанию на сервер ftp вашего ресурса. Ведение лога процесса выгрузки также предусмотрено.

3 стартмани

09.12.2019 19350 23 LamerSoft 0

Работа с картами в 1С на примере бесплатной библиотеки Leaflet

Разработка функционала отображения и выбора пунктов доставки на карте прямо в 1С с помощью бесплатной библиотеки Leaflet. Тестирование производилось на платформе 8.3.15.1534 на тонком клиенте.

1 стартмани

31.03.2021 20536 59 Parsec1C 20

Отправка Push-уведомлений через сервис Firebase Cloud Messaging по протоколу FCM HTTP v1 API

При разработке нативного приложения Android для ТСД, в котором присутствует функционал отображения задач кладовщикам, созданных в 1С, возникла необходимость отправлять push-уведомления о появлении новых задач. Для отправки таких уведомлений было решено использовать сервис Firebase Cloud Messaging (FCM). Так как для 1С, в отличии от других языков программирования, не существует готовых библиотек, что вполне логично, то очевидным способом отправки является использование протокола HTTP. Однако, существующая информация в интернете в части 1С содержит только сведений об отправке push-уведомлений через этот сервис с использованием устаревшего протокола HTTP Firebase Cloud Messaging. Сам Google не рекомендует использовать данный протокол и настоятельно склоняет к переходу на новый протокол FCM HTTP v1 API. Что ж, пришлось разбираться самостоятельно.

1 стартмани

24.03.2021 15426 24 ltfriend 16

Самые красивые шахматы для 1С на управляемых формах

Здравствуйте, представляем Вашему вниманию классическую игру – Шахматы! Написана игра средствами 1С, на управляемых формах. Программный код представляет собой с аккуратностью составленную систему, содержащую лаконичные логические приемы и описательные имена переменных, объектов и функций. Программа полностью отлажена и многократно протестирована. Оригинальный авторский дизайн фигур, иконок и кнопок приятен глазу. Игра содержит большое количество функций, настроек и режимов игры, включая сетевую игру, тренировку с ботом или игру на двоих. Не упустите возможность найти ряд технических решений, применимых для реализации различных задач, а также поиграть в вечную игру с отличным оформлением! Желающие научиться программировать на управляемых формах могут многое почерпнуть в этой конфигурации.

5 стартмани

18.02.2021 8745 18 compmir 32

"Учет штрафов ГИБДД" с возможной загрузкой из открытых источников в интернет Расширение конфигурации 1С: Предприятие 8.3 Промо

Расширение конфигурации Бухгалтерия предприятия, редакция 3.0 (при минимальных изменениях любой типовой конфигурации), позволяющее вести историю данных по штрафам ГИБДД для справочника транспортных средств компании. Бонусом поставляется внешняя обработка, способная загружать эти данные из открытых источников в интернет.

Реализация игры крестики-нолики

Всем привет! Пишу консольную игру крестики-нолики. В перспективе — создать бота. Реализация игры: есть пронумерованное поле 3х3 от 1 до 9, в котором игроку предлагается поставить крестик или нолик путем ввода соответствующего числа. Пока я создал черновик, где ходит только крестик. И на данный момент для меня представляется затруднительным следующее:

1. как сделать поочередный ход?
2. как установить запрет на изменение крестика на нолик и наоборот?

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

Давайте попробуем сначала. В игру крестики-нолики обычно играю два игрока, у каждого свой символ, соответственно крестик, или нолик и все это происходит на игровом поле произвольного размера.

Игровое поле:

Игрок:

Инициализация

Игровой процесс

Ходят игроки последовательно друг за другом до тех пор пока один из них не выставит свои фишки в ряд (горизонтально, вертикально, или по-диагоналям).

Ага, так, последовательно, друг за другом, пока кто-то не будет признан выигравшим после проверки очередного хода на выполненную/выигрышную комбинацию:

как сделать поочередный ход?
можно использовать переменную типа boolean , где false — первый игрок (крести), а true — второй игрок (нолик).
перед каждым ходом — проверяем кто сейчас ходит.
после каждого хода — инвертируем переменную.

как установить запрет на изменение крестика на нолик и наоборот? вариантом может быть создание второй скрытой матрицы, которая будет наполнена изначально одним значение =0.
и когда игрок делает ход, например "крестик в [1][2]", то значение в этой "скрытой" матрице меняется с 0 на 1.
соответственно перед каждый ходом надо проверять, чему равно значение в "скрытой" матрице.

доп.идея (та же суть, другая реализация).
у вас матрица [3][3], а можно сделать [3][3][1] и в последнем хранить точно так же 0 или 1.
то есть

После нескольких часов всё-таки родил своё решение:

Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2022.12.16.43123

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Крестики нолики «Без границ»

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

Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:

1. Поле может быть сколь угодно большим (На сколько хватит тетради)
2. Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.

Перед тем, как начнем

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

Горячие клавиши и команды:

• D – ИИ сделает ход за вас
• T – посмотреть вес клетки
• Напишите в консоли SHOW_WEIGHTS = true, чтобы просматривать веса всех анализируемых клеток.

Начнем

Начать нужно с реализации самой игры, т.е. написать приложение для двух игроков, пока без бота. Для своих целей я решил использовать javascript + jquery + bootstrap4, хотя он там практически не используется, но его лучше оставить – или таблица поплывет. Тут рассказывать особо нечего, материала по js, jquery и bootstrap на хабре полно. Скажу лишь, что использовал MVC. Да и вообще, объяснять абсолютно весь код я не буду – материала и без того получилось много.

Итак, игровое поле было готово. Можно устанавливать фигуры в клетки. Но победа кого-либо из игроков никак не фиксировалась.

Сканирование «конца игры»

Игра заканчивается, когда один из игроков поставит 5 фигур в ряд. «Все просто!» — подумал я. И начал сканировать абсолютно все клетки поля: сначала все горизонтали, потом вертикали и, наконец, диагонали.

Это тупой способ, но он работал. Однако, его можно было значительно улучшить, что я и сделал: Большая часть клеток будет оставаться пустой на протяжении всей игры – игровое поле слишком большое, чтоб его можно было заполнить целиком. Поскольку сканировать его нужно было каждый ход, а за один ход ставится только одна фигура — то можно сосредоточиться только на этой фигуре (клетке): просканировать только одну горизонталь, вертикаль и две диагонали клетки, которым принадлежит та самая клетка.

Плюс ко всему, не нужно сканировать все клетки линий. Поскольку конец игры – это 5 фигур в ряд, то фигуры, удаленные друг от друга на 6 клеток нас не интересуют. Достаточно сканировать по пять клеток в каждую из сторон. Не понятно? Смотри анимацию ниже.

Приступим к самому боту

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

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

Терминология

Крестики и нолики – это фигуры.
Атакой будем называть несколько одинаковых фигур, стоящих рядом, на одной линии. По сути, это множество. Количество фигур в атаке – её мощность. Одна отдельная фигура – тоже атака (мощностью 1).

На соседних клетках атаки (на концах) могут быть пустые клетки или фигуры противника. Логично думать, что атаку с двумя пустыми клетками на «концах», мы можем развивать в двух направлениях, что делает ее более перспективной. Количество пустых клеток на «концах» атаки будем называть её потенциалом. Потенциал может принимать значения 0, 1 или 2.
Атаки обозначаем так: [ мощность атаки, потенциал ]. Например, атака [4:1].

Рис 1. Атака [4:1]

В ходе анализа мы будем оценивать все клетки, которые входят в определенную область. У каждой клетки будет просчитываться её вес. Он вычисляется на основе весов всех атак, на которые влияет данная клетка.

Суть анализа

Представим, что на игровом поле уже есть несколько атак одного и второго игрока. Кто-то из игроков делает ход (пускай крестики). Естественно ход он делает в пустую клетку – и тем самым он может:

1. Развить свою атаку, а может быть и не одну, увеличив ее мощность. Может начать новую атаку и т.д.
2. Препятствовать развитию атаки противника или и вовсе заблокировать ее.

Суть анализа в следующем:

1. Бот подставляет в проверяемую клетку фигуры: сначала крестик, потом нолик.
2. Далее он ищет все атаки, которые были получены такими ходами и суммирует их веса.
3. Полученная сумма – это вес клетки.
4. Подобный алгоритм выполняется для всех клеток игрового поля.

По сути, таким алгоритмом мы проверяем, что будет, если мы пойдем так… а что будет если так пойдет оппонент. Мы смотрим на один ход вперед и выбираем наиболее подходящую клетку – с наибольшим весом.

Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли SHOW_WEIGHTS = true, можно визуально прочувствовать работу алгоритма (Будут показаны веса клеток).

Веса атак

Пораскинул я мозгами и привел такое соответствие атак и весов:

Подобрано эмпирически – возможно это не оптимальный вариант.

Я добавил в массив атаки мощностью 5 с запредельно большим весом. Объяснить это можно тем, что бот анализирует игру, смотря на шаг вперед (подставляя фигуру в клетку). Пропуск такой атаки есть ни что иное, как поражение. Ну или победа… смотря для кого.

Атаки с большим потенциалом ценятся выше.

Атака [4:2] в большинстве случаев решает исход игры. Если игроку удалось создать такую атаку, то оппонент уже не сможет ее заблокировать. Однако это еще не победа. Противник может быстрее завершить игру, даже при наличие у нас на поле атаки [4:2], поэтому ее вес ниже, чем у атак мощностью 5. Смотри пример ниже.

Рис 2. Атака [4:2]

«Рваные» атаки

В этом абзаце код не представлен. Здесь мы вводим понятие делителя атаки и объясняем суть «рваных атак».

Рассмотрим такую ситуацию: при подстановке фигуры на удалении нескольких пустых клеток, но не более 5-и, расположена еще одна.

И вроде бы, две одинаковые фигуры, на одной линии… визуально это похоже на атаку, а по факту нет. Не порядок, так как такие «рваные» атаки также несут в себе потенциальную угрозу.

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

1. «Рваную» атаку представляем, как несколько обычных
2. Считаем количество пустых клеток между центральной атакой и побочной
3. За каждую пустую клетку, делитель увеличиваем на 1
4. Вес центральной атаки просчитываем как обычно, вес побочных – делим на делитель

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

Алгоритм поиска атак

Во-первых, создадим класс атаки. У атаки будет 3 атрибута, о которых я писал ранее:

И один метод, который будет возвращать вес данной атаки:

Далее. Поиск всех атак для одной клетки мы разделим на:

1. Поиск на горизонтали
2. Поиск на вертикали
3. Поиск на диагонали 45 градусов
4. Поиск на диагонали 135 градусов

Однако, нам не нужно проверять всю линию целиком. Максимальная мощность атаки, которая нас интересует – 5. Безусловно, создать атаку мощностью, скажем, 6 – возможно. Но для ИИ, который анализирует игровую ситуацию следующего хода, все равно, что 6, что 5. Перспектива получить одну из этих атак говорит о конце игры на следующем ходу. Соответственно, вес анализируемой клетки будет в обоих случаях будет одинаковым.

Здесь надо остановиться, так как может возникнуть вопрос: зачем проверять 6-ую клетку, если максимальная мощность атаки – 5. Ответ – это нужно для определения потенциала удаленной от центра атаки.

Вот пример: атака мощностью 1 на картинке находится на границе сканируемой области. Чтобы узнать потенциал этой атаки нужно «заглянуть за границу».

Рис. 3. Сканирование 6-ых клеток. Если не просканировать 6-ую клетку, можно неправильно определить потенциал атаки.

Для завершения некоторых атак может просто не хватать места. Посчитав attackplace мы заранее можем понять, какие из атак бесперспективны.

Рис. 4. Место для атаки

1) Начнем с центральной клетки. Она должна быть пустой (мы ведь собираемся сделать в нее ход, не так ли? Однако мы не забываем, что наш ИИ должен подставлять фигуры в данную клетку для анализа следующего хода. Фигура, которую мы подставляем – this.subfig – по умолчанию крестик. Поскольку центральная клетка изначально будет содержать в себе какую-либо фигуру после подстановки, то она будет принадлежать какой-то атаке this.curAttack:

• ее мощность будет не меньше 1 (фигура в центральной клетке)
• делитель – 1, т.к. речь идет о центральной атаке ( ей принадлежит сканируемая клетка);
• потенциал пока неизвестен – по умолчанию 0;

Все эти пункты мы отобразили в значениях конструктора по умолчанию – смотри код выше.

2) Далее, уменьшая итератор, перебираем 5 клеток с одной стороны от сканируемой. За это отвечает функция getAttacks( cellX, cellY, subFig, dx, dy ), где:

cellX, cellY – координаты проверяемой клетки
subFig – фигура, которую мы подставляем в проверяемую клетку
dx, dy – изменения координат x и y в циклах – так мы задаем направление поиска:

• Горизонталь ( dx = 1, dy = 0 )
• Вертикаль ( dx = 0, dy = 1 )
• Диагональ 45 ( dx = 1, dy = -1 )
• Диагональ 135 ( dx = 1, dy = 1 )

Обратите внимание, что если checkCell() что-то вернет, то выполнение цикла прекращается.

3) Проверяем фигуры данных клеток.
За это отвечает функция checkCell( x, y ):

Для начала запишем фигуру в переменную fig:
Model.Field – наше игровое поле.

Если такая фигура совпадает с фигурой центральной клетки (this.subFig), тогда продолжаем алгоритм – значит мы продолжаем сканировать атаку, все замечательно, продолжаем в том же духе. Лишняя фигура в атаке – плюс к ее мощности(this.curAttack.capability) и месту (this.attackplace).

4) Если на 5-ой клетке фигура совпадает с центральной клеткой, значит атака «уперлась» в границу и для определения потенциала атаки придется «проверить границу» ( this.checkEdge = true).

Функция checkCell – готова. Однако продолжаем работать над классом checkLine.

5) После выполнения первого цикла, надо «развернуться». Переводим итератор в центр и центральную атаку, с индексом 0, убираем из массива атак и устанавливаем как текущую.

6) Далее идем в другую сторону от текущей клетки, увеличивая итератор.
Абсолютно такая же проверка фигур. (Код уже написан – функция getAttacks)

7) Все, мы собрали все атаки, что были на линии в один массив.
На этом с классом checkLine всё… закончили.

Ну а дальше все просто – создаем объект checkLine для каждой из линий (2 диагонали, горизонталь и вертикаль) и вызываем функцию getAttacks. То есть, для каждой линии — свой объект checkLine и, соответственно, свой набор атак.

Пусть за все это отвечает функция getAllAttacks() – уже отдельно от описанных выше классов;

На выходе имеем объект со всеми атаками для проверяемой клетки

Однако вы, возможно, заметили некую функцию-фильтр. Ее задача – отсеивать «бесперспективные» атаки:

• С нулевой мощностью (мало ли такие попадут в массив)
• Атаки, которым не хватает места (attackplace < 5 )
• С нулевым потенциалом.

Брейкпоинты

Да… снова термин, простите! Так мы будем называть ситуацию в игре, когда один неправильный ход решает исход игры.

Например, атака [3:2] – это брейкпоинт. Если оппонент не заблокирует ее, поставив рядом фигуру, то следующим ходом, мы уже имеем на игровом поле атаку [4:2] – ну и исход игры решен, как ни крути (В подавляющем большинстве случаев).

Или атака [4:1]. Один зевок — и игру можно легко завершать.

Рис 5. Брейкпоинт

Тут все ясно и понятно, и тот алгоритм, о котором писалось выше уже способен учитывать брейкпоинты и своевременно их блокировать. Бот смотрит на ход вперед. Он увидит, что на следующем ходу оппонент способен создать атаку [5:1], например, вес которой 200 – значит хитрый ботяра пойдет сюда.

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

Рис 6. 2 Брейкпоинта

Все просто, при анализе клетки, при подстановке фигуры в нее, мы будем считать количество брейкпоинтов, которое мы получим на следующем ходу (бот смотрит на ход вперед, не забываем). Насчитав 2 брейкпоинта, мы увеличиваем вес клетки на 100.

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

Как понять, что атака – брейкпоинт

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

Далее, если потенциал атаки равен 2, то на блокировку такой атаки мы потратим на 1 ход больше, а значит существует брейкпоинт, мощностью 3. Но такой брейкпоинт всего один – это атака [3:2].

А далее сложнее – «рваные атаки».
Мы будем рассматривать только атаки с одной пустой клеткой посередине – не больше. Это объясняется тем, что для завершения атаки с двумя пустыми клетками посередь, нужно потратить минимум 2 хода – это явно не брейкпоинт.

Как мы помним, рваные атаки мы рассматриваем, как несколько обычных: одна центральная атака и побочные. Центральной атаке принадлежит сканируемая клетка, у побочных делитель больше 1 – об этом писалось выше.

Алгоритм нахождения брейкпоинта (можно проще – читай ниже):

1. Введем переменную score
2. Берем центральную атаку, считаем мощность
3. Берем одну из побочных, если ее делитель не больше 2х.
4. Score – сумма мощностей центральной и побочной атак
5. Если потенциалы центральной и побочной атак равны 2, то для блокировки такой атаки нужно потратить на один ход больше. Поэтому, score увеличиваем на 1
6. Если score >= 4, то это брейкпоинт
   На самом деле брейкпоинты можно было просто перечислить, их не так много, но это я понял далеко не сразу.

Да соберем, наконец, все воедино

Итак, основной ад позади — описан выше. Пора слепить из него что-то рабочее. Функция countWeight( x, y ) — принимает на вход координаты клетки, а возвращает ее вес. Что же у нее под капотом?

Во-первых, получим массив всех атак, которым клетка принадлежит. ( getAllAttacks( x, y ) ). Перебирая все линии, мы считаем количество брейкпоинтов. Если 2 брейкпоинта – вспоминаем, что такая ситуация может решить исход игры, и увеличиваем вес клетки на 100.
Однако все брейкпоинты должны принадлежать одному игроку, поэтому пришлось реализовать проверку в 2 шага: сначала крестики, потом нолики.

Поскольку в массиве весов атак ( ATTACK_WEIGHTS[] ) я не предусмотрел атаки мощностью 6 и больше, мне пришлось заменить их на атаки мощностью 5. Разницы никакой – все они приводят к концу игры.

Ну и суммируем веса атак – к этому все и шло.

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

Теперь при вызове этой функции для конкретной клетки мы получим ее вес. Проводим эту операцию для всех клеток и выбираем наилучшую (с наибольшим весом). Туда и ходим)

Остальной код вы сможете найти на github. Материала уже предостаточно, и его изложение, как я не пытался, оставляет желать лучшего. Но если ты смог дочитать до этого момента, дорогой читатель, то я тебе благодарен.

Мое мнение о полученном результате

Сойдет! Да, его можно обыграть, однако сделать это немножко проблематично лично для меня. Возможно я просто недостаточно внимателен. Попробуйте и вы свои силы.

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

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

В будущем планирую добавить анализ брейкпоитов на несколько шагов вперед, что сделает бота еще более серьезным соперником. Однако сейчас не имею четкого представления о реализации сего; лишь имею предстоящую сессию и недописанный диплом – что меня огорчает.

Реализация алгоритма Минимакс на примере игры «Крестики-Нолики»

Недавно я написал непобедимую игру "Крестики-Нолики". Это был интересный и поучительный проект, который многому меня научил. Если у вас есть желание посмотреть результат — это можно сделать здесь.

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

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

Описание «Идеальной» игры «Крестики-Нолики»

Для начала давайте опишем, что мы понимаем под "идеальной" игрой — если я играю идеально, я или побеждаю в игре, или играю вничью. В случае если я играю против другого "идеального" игрока, я всегда играю вничью.

Можно ли описать эти требования количественно? Давайте для всех возможных вариантов конечного состояния игры назначить какое-то количество очков:

• Я победил, ура! Я получаю 10 очков!
• Я проиграл, блин. Я теряю 10 очков (потому, что другой игрок получает 10 очков).
• Ничья. Я получаю ноль, и другой игрок получает ноль.

Теперь мы можем количественно оценить любое конечное состояние игры.

Давайте рассмотрим короткий пример.

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

Верхняя часть картинки показывает состояние игры, и, в зависимости от моего выбора, я могу попасть в одно из трех состояний из нижней части картинки. Очевидно, что состояние, в котором я побеждаю (снизу слева) является наилучший. Если я не сделаю этот ход, игрок "О" может легко победить, и я не хочу, чтоб он победил. Таким образом, выберу ход, который принесет мне наибольшее число очков.

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

Выбор очевиден, "О" выберит один из ходов, который приведет нас к результату -10.

Описание алгоритма Минимакс

Суть алгоритма Минимакс это поочередный перебор возможных ходов двух игроков, при котором мы считаем, что игрок "чья очередь" выберет ход, приносящий максимальное количество очков. Предположим, что мы играем за игрока "Х", тогда описание алгоритма будет примерное таким:

• Если игра закончена, вернуть количество очков для игрока «Х»
• В противном случае, получить список новых состояний игровой области для каждого возможного хода
• Оценить возможный выигрыш для каждого возможного состояния
• Для каждого из возможных состояний добавить «Минимакс» оценку текущего состояния
• Если ход игрока «Х» — вернуть ход с максимальным количеством очков
• Если ход игрока «О» — вернуть ход с минимальным количеством очков

Алгоритм является рекурсивным, и расчёт производится по очереди для каждого из игроков до тех пор, пока не рассчитан финальный выигрыш. Давайте посмотрим, как алгоритм работает с полным деревом ходов, и посмотрим, как будет выбран наилучший ход:

• В состоянии 1 — очередь ходить у игрока «Х». «Х» генерирует состояния 2, 3 и 4 и рекурсивно применяет алгоритм к сгенерированным состояниям
• Состояние 2 добавляет выигрыш в размере +10 к оценке состояния 1, потому что игра выиграна
• Состояния 3 и 4 не являются конечными состояниями, поэтому из состояния 3 генерируются состояния 5 и 6, из состояния 4 генерируются состояния 7 и 8, после чего к каждому из сгенерированных состояний применяется алгоритм Минимакс.
• Состояние 5 добавляет «проигрыш в размере -10 для состояния 3, то же самое происходит и с состоянием 7 для состояния 4.
• Состояния 6 и 8 генерируют лишь конечные выигрышные состояния, поэтому каждое из них добавляет выигрыш в размере +10 для состояний 3 и 4.
• Так как на состояниях 3 и 4 очередь ходить игрока „О“, „О“ будет искать наименьший выигрыш. Исходя из выбора в -10 и +10, оба состояния вернут -10
• Наконец, оценка выигрыша для состояний 2, 3 и 4 будет рассчитана как +10, -10 и -10 соответственно. Так как игрок „Х“ стремиться максимизировать выигрыш, будет сделан выбор в пользу состояния 2.

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

Реализация алгоритма Минимакс

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

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

А теперь собственно сам алгоритм; обратите внимания что в приведенном варианте выбор хода это просто адрес ячейки на поле, т.е. [0,2] это правая верхняя ячейка на игровом поле размером 3×3.

Когда алгоритм выполняется в классе PerfectPlayer, выбор наилучшего ходя сохраняется в переменной choice, которая впоследствии используется для того, чтобы вернуть новое состояние игры в которое мы попадаем в результате выбранного игроком хода.

Идеальный игрок-самоубийца

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

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

Давайте рассмотрим, что происходит здесь через призму возможных ходов (для простоты я удалил некоторые состояния)

• В случае если игровое поле в состоянии 1, и оба игрока играют идеально, и компьютер играет на стороне „О“, „О“ принимает решение идти в состояние 5, что ведет к немедленному проигрышу, когда игрок „Х“ переходит в состояние 9.
• Но если „О“ заблокирует ход „Х“ перейдя в состояние 3, „Х“ заблокирует потенциально победный ход „О“, как показано в состоянии 7.
• Исходя из этого очевидно, что „Х“ победит, как показано в состояниях 10 и 11, несмотря на то, какой ход выберет „О“.

В результате данных расчетов, принимая во внимание факт, что при расчёте выигрыша мы итерируемся слева направо, снизу вверх, не проводя различий между ходами, будет выбран ход, приводящий в состояние 5, так как это последний доступный ход из состояния 1.

Черт побери, что же мастер "крестиков-ноликов" должен сделать?

Даем противнику хороший бой: глубина

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

Для того чтобы достигнуть такого результата мы будем отнимать глубину рекурсии\количество ходов от конечного состояния игры. Т.е. чем больше ходов до минимального выигрыша (и чем меньше ходов до максимального) — тем лучше.

Так, каждый раз при вызове алгоритма Минимакс глубина будет увеличена на 1, и когда мы наконец рассчитаем возможный выигрыш для конкретного конечного состояния игры мы введем поправку на глубину. Давайте посмотрим, как это выглядит на примере следующего дерева ходов:

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