Сайт посвящён игре пять в ряд.
Игра gomoku, известна у нас как пять в ряд.
Правила у игры такие же как в игре крестики-нолики, только
надо собрать линию из пяти крестиков или ноликов. Крестики делают первый ход.
Текущую альфа версию можно скачать здесь
Предупреждение!!! Проверяйте файлы в архиве. Хотя я на 99% уверен, что архив не содержит вирусов, дать 100% гарантии не могу :(
Gomoku появилась в японии, и играется на доске 15x15. Перебором доказано, что в общем случае крестики выигрывают.
Поэтому японцы придумали целую систему ограничений, какие ходы может делать крестик, а какие нет.
Например, крестики не могут выигрывать комбинацией 6 в ряд.
По моему мнению, поле размером 15x15 само по себе является большим ограничением.
Более общий подход, считать поле неограниченным. Хотя считается, что для неограниченного
поля также существует выигрышная стратегия, на данный момент для меня это не так очевидно.
Например, тяжело доказать, что не существует такой стратегии для ноликов, при которой игра будет
продолжаться бесконечно долго.
В игру удобно играть на тетрадном листке в клеточку. Чем мы собственно и занимались, во время лекций в институте :)
Что умеет текущая версия
Текущая версия проверяет на 3 хода вперёд + 2 хода анализ вилок.
На данном этапе программа работает довольно медленно, что не позволяет увеличить глубину рекурсии.
Но даже в таком виде, выиграть у неё довольно тяжело.
Сейчас для меня важен поиск логических ошибок, при которых программа проигрывает даже в пределах своей
глубины рекурсии.
Пришлите пожалуйста игру, если вы считает что программа работает неправильно(неоптимально) в рамках
указанных выше ограничений. Игру можно сохранить в XML файл (Options/Save game...)
Отсылать на five-in-line собака narod точка ru. Пожалуйста указывайте в теме письма gomoku, чтобы я отличал ваши письма от спама.
Почему пять в ряд?
Лень двигатель прогресса. Меня всегда раздражало, что я проигрываю из-за банальной невнимательности. Я решил, что легче написать игру,
которая «сделает» всех моих соперников раз и навсегда.
Игра имеет очень простые правила. Но очень непросто реализовать эффективный по скорости алгоритм. Вместе с тем именно простота правил,
позволяет производить глубокий анализ и применять мощные оптимизационные методы поиска решений.
Судя по количеству реализаций этой игры в интернете, не одного меня вдохновляет эта игра.
Как работает эта программа?
Многие реализации логических игр, основываются на переборе. Тупой перебор имеет сложность
O*n*deep. Где n – к-во возможных ходов, deep глубина перебора. Хоть это и не NP-полная задача(как например Задача комивояжёра), но уже при
deep=3 алгоритм работает очень медленно, а deep>5 практически не осуществим на современных процессорах.
Для оптимизации перебора используется Анализ альфа-бета отсечений, который применяется, наверное во всех логических играх. Для уменьшения перебора метод оперирует
«лучшим текущим выигравшем» и «худшем текущим выиграем». В общем случае у Gomoku нет «весомости» выигрыша. Нам всё равно через сколько ходов и как мы выиграем. Мы либо
выиграем, либо проиграем. Но в качестве такой функции, можно принять «количество ходов до выигрыша». Чем меньше ходов надо сделать, тем больше выигрыш. Самые примитивные реализации оценивают не терминальный ход по длине открытой линии. Вобщем-то такая оценка ничего не даёт, потому что длинна открытой линии никак не гарантирует выигрыш. Лучшие реализации основываются на вилках. Их недостаток в том, что производиться анализ не всех равнозначных вилок. Обычно анализ основывается на «личном опыте» программиста. Как результат существуют ситуации, при которых программа проигрывает, при любом уровне рекурсии.
Сейчас я считаю, что можно найти все выигрышные ситуации за (N ходов) путём комбинирования выигрышных ситуаций (N-1,[1..N-1]). Первый уровень - «выигрыш за один ход» легко заменой в линии из 5 «крестиков» одной пустой клеткой. По каждому уровню для быстрого поиска строится специальный индекс ввиде дерева. Именно по такому принципу работает текущая реализация. Проблема такого подхода, в том что размер индекса и время его построения очень быстро растут с глубиной. Индекс на глубину «2 хода» занимает уже 600КБ.
Что планируется сделать ?
Сейчас производиться очень много повторных вычислений при оценке разных ходов.
Неплохо было бы применить динамическое программирование для уменьшения площади анализа.
Можно, наверное, сэкономить на угрожающих ходах. Если нет собственных выигрышных ходов, а у противника будет вилка, то имеет смысл делать ход только на клетки, разрушающие эту вилку.
Память на сыгранные партии. Если построить дерево всех партий, то можно с какой-то вероятностью утверждать что такой ход приведёт к выигрышу. Можно легко производить анализ веток, которые приводят к гарантированному выигрышу.
Моя цель – программа, которая не оставляет человеку шансов на выигрыш :)