Minimax.Connect4

Реализация minimax-алгоритма для игры "4 в ряд"

Результат

При игре с алгоритмом Ярика всегда играет в ничью.

Параллельность

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

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

Множество копий игровой доски приводит к повышенному потреблению оперативной памяти (до 200 КБ) в угоду значительно меньшему времени работы алгоритма, что позволяет алгоритму быстро выдавать результаты на больших глубинах (~800 мс при глубине 9, ~5 сек на глубине 11, ~30 сек на глубине 12):

Оптимизация

Использует максимально оптимизированные операции и подходы, среди них:

• Jagged-массивы вместо многомерных массивов ([][] вместо [,], работает значительно быстрее в контексте задачи);
• Клонирование досок и их заполнение через Span;
• Использует кэширование текущего победителя чтобы исключить повторные вычисления.

Использование

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