Бот для шашек (часть 1)

в 19:01, , рубрики: Алгоритмы, логика, обработка изображений, Спортивное программирование, управление, шашки, метки: , , , ,

После прочтения поста на хабре «Шахматный бот», хотелось сделать свой, но так как посчитал, что шахматы сразу не получатся, то решил потренироваться на шашках (чтоб было больше мотивации взял знаменитые «Русские стрип-шашки»).
В отличии от выше упомянутого поста, где только несколько скринов и видеоролик, постараюсь рассказать подробнее…
Бот для шашек (часть 1)
Наверное больше картинок не позволила бы цензура.

Описание

Поставленная цель это программа, которая вместо нас будет играть (и желательно выигрывать) в шашки против комп'ютера (режим «Девочки») или игрока (режим «Дуэль»). В принципе можно даже запустить две программы и пусть играют.
Для начала разберемся какие функциональные части у нас будут (приведены асоциации с реальным игроком, в спойлере — конкретнее):

  • Глаза — чтобы видеть поле какие фигуры на нем есть;
    Сначала была идея реализовать распознавание поля на базе OpenCV.
    Отказались через требовательность к ресурсам, и избыточности. Теоретически можно было проверять несколько пикселей и получать более-менее верный результат.
    Но, остановились на том что разбираем поле на отдельные квадраты
    Бот для шашек (часть 1) Бот для шашек (часть 1) Бот для шашек (часть 1) Бот для шашек (часть 1) и сравниваем «сфотографированные» с этими.
    После этого, передаем всю информацию в мозг.
  • Игрок (с Мозгами) — начинает игру, смотрит какие ходы доступны (согласно правил);

    Бот для шашек (часть 1)
    Сдесь, на основе увиденной информации, ищем все доступные ходы, перебырая все шашки нашего цвета и проверяя можно ли сделать ход в соседние по-диагонали клетки.
    Если соседняя пуста — туда можно сделать ход, если она занята фигурой противника, а следующая после нее (по диагонали) свободна — значит можно сделать удар. После этого возможность этого хода записывается в список доступных, и если нужно «ударить», то этот ход отмечается как приоритетный.
  • Логика — принимает решения о выборе одного хода из списка доступных;

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

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

Результат

Бот для шашек (часть 1)
Получилась программа которая умеет играть шашки в практически любой среде: онлайн-игра в браузере, программа как на фото или что-то еще. Только перед началом ее нужно будет обучить тому как выглядят фигуры и поле. Много еще нужно добавить, например:

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

Послесловие

Программа была написана вместе с другом (ждите скоро на хабре), за 3 часа. Прошу не кидаться ботинками, так как писали после рабочего дня и «just4fun». Приветствуются коментарии, замечания, предложения…
Завтра еще добавлю видео процесса игры.
Репозиторий на GitHub

Автор: wowkin

Источник


* - обязательные к заполнению поля