Comments 11
Поиск в глубину предпочтительнее c точки зрения памяти, но часто уходит слишком глубоко, хотя победа находится рядом в соседней ветке.
А как же стек используемый при поиске в глубину? Он бесплатный?
Как насчет оптимизации с помощью хеширования Зобриста?
Я пытался читать, но не понял идею. Увы.
Вообще эвристик и подходов много, Z-orbice, например.
Мозга на всех, к сожалению, не хватает :(
Вообще эвристик и подходов много, Z-orbice, например.
Мозга на всех, к сожалению, не хватает :(
Я не совсем понял, цель была провести исследование методов или написать сильную программу для игры? Если второе — то такая игра отлично программируется с помощью комбинации «хорошая весовая функция + просмотр на несколько уровней вперед», победить ее будет очень сложно. Я делал ее когда-то в качестве курсовика на втором курсе.
Мне пришлось писать ИИ для этой игры в 10м классе.
Критериями оценки было обыграет ли она преподавателя (ну или насколько быстро сольёт партию) и как ИИ выступит на турнире по сравнению с работами других учащихся.
Ничего кроме качественного взвешивания не требуется.
Критериями оценки было обыграет ли она преподавателя (ну или насколько быстро сольёт партию) и как ИИ выступит на турнире по сравнению с работами других учащихся.
Ничего кроме качественного взвешивания не требуется.
Сделать не просто сильную программу, а программу которая выигрывает всегда.
Действительно от функции многое зависит. Возможно, даже существует такая функция, которая реализует победную тактику без просмотра уровней вперёд. Для крестиков-ноликов ведь она существует, теоретически может существовать и для гомоку.
Алис в своей работе упоминал, что для успешной игры против профессионалов необходимо просматривать на 15 шагов вперёд. Из-за того, что это проблематично, придумывают разные эвристики, для ограничения перебора.
Действительно от функции многое зависит. Возможно, даже существует такая функция, которая реализует победную тактику без просмотра уровней вперёд. Для крестиков-ноликов ведь она существует, теоретически может существовать и для гомоку.
Алис в своей работе упоминал, что для успешной игры против профессионалов необходимо просматривать на 15 шагов вперёд. Из-за того, что это проблематично, придумывают разные эвристики, для ограничения перебора.
Огромное спасибо за статью, очень ценная, достаточно подробная.
Очень люблю крестики-нолики, и когда взял себе телефон на андроиде, сразу же начал искать эту игру на него. Перепробовал несколько программ, и остановился на Tito gomoku (https://play.google.com/store/apps/details?id=com.partizansoft.TitoGomoku&hl=ru) — очень сильная, 9 уровней сложности ИИ, и уже второй по сложности мне даётся с трудом. Ходит почти мгновенно.
Присоединяюсь к предыдущему вопросу Dimmerg — ваша первоначальная задача написания ИИ для игры переросла во что-то большее? Или вы хотите найти «идеальную стратегию» со 100% выигрышем?
P.S. Сам сейчас пишу игрушку на мобильные. И так как это первая моя игра, то взял эту тему — крестики-нолики. Так что ваша статья очень вовремя, спасибо Хабру!
Очень люблю крестики-нолики, и когда взял себе телефон на андроиде, сразу же начал искать эту игру на него. Перепробовал несколько программ, и остановился на Tito gomoku (https://play.google.com/store/apps/details?id=com.partizansoft.TitoGomoku&hl=ru) — очень сильная, 9 уровней сложности ИИ, и уже второй по сложности мне даётся с трудом. Ходит почти мгновенно.
Присоединяюсь к предыдущему вопросу Dimmerg — ваша первоначальная задача написания ИИ для игры переросла во что-то большее? Или вы хотите найти «идеальную стратегию» со 100% выигрышем?
P.S. Сам сейчас пишу игрушку на мобильные. И так как это первая моя игра, то взял эту тему — крестики-нолики. Так что ваша статья очень вовремя, спасибо Хабру!
Получается переросла.
Есть отдельно игра и отдельно дерево решений.
Игра сейчас заточена больше под анализ и поиск ошибок в алгоритме. В ней нет случайных ходов, и она никак не использует информацию из дерева решений.
Цель дерева решений — доказать, что крестики всегда выигрывают. Как бонус можно получить программу, которая также всегда выигрывает крестиками, начиная со стартовой позиции.
Есть отдельно игра и отдельно дерево решений.
Игра сейчас заточена больше под анализ и поиск ошибок в алгоритме. В ней нет случайных ходов, и она никак не использует информацию из дерева решений.
Цель дерева решений — доказать, что крестики всегда выигрывают. Как бонус можно получить программу, которая также всегда выигрывает крестиками, начиная со стартовой позиции.
Первую же игру выиграл ноликами (синими)
уже после 28-го хода у крестов (красных) не было шансов. Изменение уровня сложности не нашел
уже после 28-го хода у крестов (красных) не было шансов. Изменение уровня сложности не нашел
Sign up to leave a comment.
Поиск решений в логических играх на примере гомоку