Крестики - Нолики

Постановка задачи

Гомоку (пять в ряд), или рендзю - это разновидности игры в крестики - нолики на поле размером 15 на 15 (или более), где нужно построить 5 (или более, в зависимости от правил) в ряд, чтобы выиграть. Основной режим игры - человек против компьютера.

Решение

Решение будем выполнять на языке C++

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

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

История развития

Первая версия, основанная на рекурсивном поиске, вышла в 2000 году. Проект основывался на Borland C++ Builder, ныне давно канувшим в лету.

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

Основная доработка версии 2.1 - это хэширование дерева, что позволяет отбросить некоторые дубликатные узлы. А именно, игровые позиции полученные одинаковыми ходами, но в другом порядке. Для получения хэша, каждой игровой клетке присваивается простое число. Числа для клеток, занимаемых крестиками перемножаются. То же самое и для ноликов. Таким образом, получаем пару чисел, образующих хэш. Дерево, в результате хэширования, превращается в DAG.

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

Версия 2.2. была доработана так, чтобы полностью отбросить и дерево и DAG, и перейти к чистой хэш-таблице. Что дало некоторую экономию памяти, что было важно при использованиии старого доброго режима 32-разрядной компиляции :) Максимальное количество возможных игровых позиций которое она могла хранить, возросло с примерно 42 миллионов до примерно 64 миллиона

Текущее состояние

Исходный код версии 2.2 можно посмотреть тут
На той же странице, внизу, изображён основной скелетон программы, иерархия из шести основных классов. А в скобочках, у каждого класса указаны его основные методы. Помимо этих, есть ещё несколько дополнительных, утилитарных классов, например, класс реализующий простые числа или класс хэш таблицы. Некоторые части кода сохранились нетронутыми с далёкого 2000 года, поэтому неудивительно что некоторые "перлы" сохранились и поныне. Например simply numbers необходимо переименовать в primary numbers, setka - в grid т т.п.

Для сборки требуется Borland C++ verion 6.

Собранную версию скачать можно тут

Проект Xgo

Находится тут

Основная цель - предоставить современный процесс сборки, желательно совместимый с любой операционной системой.

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

Требуемые доработки

Помимо уже означенной проблемы с юзерским интерфейсом для Xgo, есть также ещё одна, более застарелая, алгоритмическая и касающаяся обоих версий. Функция Builder::chooseNodeToExpand() выбирает узел, в направлении которого дерево будет наращиваться, но делает это неоптимальным образом, подразумевая что в каждом направлении размер поддерева пропорционален квадрату рейтинга. Однако, оптимальнее было бы использовать экспоненциальную функцию, а именно, сделать так, чтобы наилучшему по рейтингу варианту отдавалось 1/2 от общего количества ресурсов, следующему - 1/2, третьему - 1/8 и так далее.

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