Поиск решений в логических играх на примере гомоку

[skiedr]

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

А как же стек используемый при поиске в глубину? Он бесплатный?

[chersanya]

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

[KvanTTT]

Как насчет оптимизации с помощью хеширования Зобриста?

[shebeko]

Я пытался читать, но не понял идею. Увы.
Вообще эвристик и подходов много, Z-orbice, например.
Мозга на всех, к сожалению, не хватает :(

[Dimmerg]

Я не совсем понял, цель была провести исследование методов или написать сильную программу для игры? Если второе — то такая игра отлично программируется с помощью комбинации «хорошая весовая функция + просмотр на несколько уровней вперед», победить ее будет очень сложно. Я делал ее когда-то в качестве курсовика на втором курсе.

[yurav]

Мне пришлось писать ИИ для этой игры в 10м классе.
Критериями оценки было обыграет ли она преподавателя (ну или насколько быстро сольёт партию) и как ИИ выступит на турнире по сравнению с работами других учащихся.
Ничего кроме качественного взвешивания не требуется.

[shebeko]

Сделать не просто сильную программу, а программу которая выигрывает всегда.

Действительно от функции многое зависит. Возможно, даже существует такая функция, которая реализует победную тактику без просмотра уровней вперёд. Для крестиков-ноликов ведь она существует, теоретически может существовать и для гомоку.

Алис в своей работе упоминал, что для успешной игры против профессионалов необходимо просматривать на 15 шагов вперёд. Из-за того, что это проблематично, придумывают разные эвристики, для ограничения перебора.

[maxipr]

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

[lexxpavlov]

Огромное спасибо за статью, очень ценная, достаточно подробная.
Очень люблю крестики-нолики, и когда взял себе телефон на андроиде, сразу же начал искать эту игру на него. Перепробовал несколько программ, и остановился на Tito gomoku (https://play.google.com/store/apps/details?id=com.partizansoft.TitoGomoku&hl=ru) — очень сильная, 9 уровней сложности ИИ, и уже второй по сложности мне даётся с трудом. Ходит почти мгновенно.
Присоединяюсь к предыдущему вопросу Dimmerg — ваша первоначальная задача написания ИИ для игры переросла во что-то большее? Или вы хотите найти «идеальную стратегию» со 100% выигрышем?
P.S. Сам сейчас пишу игрушку на мобильные. И так как это первая моя игра, то взял эту тему — крестики-нолики. Так что ваша статья очень вовремя, спасибо Хабру!

[shebeko]

Получается переросла.
Есть отдельно игра и отдельно дерево решений.

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

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

[chibiryaev]

Первую же игру выиграл ноликами (синими)

уже после 28-го хода у крестов (красных) не было шансов. Изменение уровня сложности не нашел