AI стратегия для гомоку (вариация крестики-нолики)

Question

Я пишу игру, которая является вариантом Gomoku .В основном это крестики-нолики на огромной доске.

Интересно, знает ли кто-нибудь хорошую стратегию ИИ для игры.Моя текущая реализация очень глупая и занимает много времени (O (n ^ 3), примерно 1-2 секунды, чтобы сделать ход):

-(void) moveAI {
    //check if the enemy is trying to make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkEnemies];

    //check if we can make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkIfWeCanMakeALine];

    //otherwise just put the piece randomly
    [self put randomly];
}

EDIT: Спасибо всем за отзыв!Я опробую ваши ответы и сообщу вам, если я смогу сделать какие-либо улучшения.

Answer 1

Для гомоку победная стратегия уже найдена.Смотрите эту статью: L.Виктор Аллис, Х.Дж. ван ден Херик, магистр естественных наук Хантенс.Go-Moku и Threat-Space Search .Это мне очень помогло, когда я писал свою собственную программу.Таким образом, вы сможете написать программу, которая очень хороша для атаки противника и нахождения выигрышных комбинаций.

Answer 2

Традиционной и довольно эффективной стратегией написания ИИ для таких игр является типичная древовидная стратегия поиска.То есть каждое состояние платы формирует узел на графике, и направленный край помещается между каждым узлом и состояниями, которые могут быть получены одним движением.Таким образом, дерево строится так, что корневая плата является пустым узлом.Затем пройдитесь по дереву каким-нибудь умным способом, чтобы найти то, что выглядит как «хорошее» состояние.«Хорошее» состояние обычно измеряется оценочной функцией, которая использует некоторую умную эвристику.Очевидно, вы не хотите посещать все узлы в дереве - это было бы много работы!Вам просто нужно что-то умное.

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

Фактическим названием таких алгоритмов обхода дерева является алгоритм "Минимакс".Ищите это в Википедии, и вы увидите много довольно приличного материала.Есть несколько способов повысить эффективность алгоритма, наиболее заметный из которых - альфа-бета-обрезка, поэтому обязательно посмотрите на это.Возможно, вы захотите взглянуть на эвристику connect-four и решить, как вы можете применить их к своей игре.Например, вероятной хорошей эвристикой для оценки состояний доски будет подсчет количества продолжительных 2-х, 3-х и 4-х серий и взвешивание их в балл.(например, каждый 2-й прогон будет стоить 1 балл, каждый 3-й прогон будет стоить 10 баллов, а каждый 4-й прогон будет стоить 1000 баллов)

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

С помощью этой стратегии вы сможете получить не такой уж и глупый ИИ за то же время.Однако, действительно, действительно хороший ИИ требует много усилий для создания, даже в таких «простых» играх, и все же может потребоваться более 10 секунд или больше, чтобы убрать умные ходы.С другой стороны, есть некоторые хитрые уловки программирования, такие как предварительные вычисления обходов по дереву, пока оппонент занят мышлением.Эй, люди думают, а компьютер думает.Ярмарка - это честно!

Надеюсь, мне помогли.Удачи!Это веселый проект.

Answer 3

Я уже некоторое время пытаюсь создать алгоритм для той же программы.

Вы, конечно, правы в том, что первое, что ваша программа должна сделать, это проверить, есть ли способ сформировать5 и победа.А если нет, то следует проверить, может ли ваш оппонент сделать это, и если да, то защита.

Сколько Вы играли в гомоку?Насколько хорошо вы понимаете основы?

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

__________
____XOOOO_
__________

Тогда противник может закрыть его.

Но если мы сформируем «открытую четверку», вот так:

__________
____OOOO__
__________

Тогда противник не может закрыть обе стороны, и Вы можете выиграть.Таким образом, формирование открытой четверки - это один из способов выиграть.Теперь возникает вопрос: как мы можем сформировать открытую четверку?Конечно, если мы сформируем «открытую тройку», как это:

__________
____OOO___
__________

Тогда противник может заблокировать нас:

___________
____XOOO___
___________

и мы вернемся к началу.

Чтобы выиграть, мы можем сформировать две открытые тройки одновременно:

____________
____OOO_____
_____O______
____O_______

Теперь, если противник блокирует одну из них, мы можем использовать другую, чтобы сформировать открытую четверку:

____________
_______O____
___XOOO_____
_____O______
____O_______
____________

и выигрыш:

________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________

В терминах гомоку это называется 3x3, если Вы делаете две открытые тройки одновременно.

Обратите внимание, что обе тройки должны быть открыты: можете ли ВыВы понимаете, почему?

Есть и другие способы выиграть:

4x3: Видите ли вы выигрышный ход и почему он выигрывает?

____________
__XOOO______
__XXXO______
____OX______
____________

4x4: Смотритевыигрышный ход?

____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________

Это только основы игры.Знание тактики помогает вам думать, как построить ИИ, и вы можете жестко программировать принципы.

Естественно, это только начало.Буду признателен, если Вы попытаетесь реализовать это, а затем дать мне обратную связь.

Я пытался написать программу на Java.Хотели бы вы увидеть код, который я сделал, чтобы Вы могли играть?Это не очень хорошо, но Вы можете получить новые идеи оттуда.Хотя комментарии и имена переменных написаны на эстонском языке ... это может быть очень трудно понять.(

Answer 4

Гомоку решается, но не решается, когда в него играют с открытой позицией и ограниченными ресурсами.

Я являюсь автором Hewer gomoku программы и Gomocup организатора, и я могу вам сказать, что вам понадобится очень много времени, чтобы написать хороший AI Gomoku. Рэндзю намного сложнее. Вы можете упростить свою работу, используя интерфейс Gomocup и писать «только» AI.

Answer 5

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

Расчет это не п ^ 3. Вы просто проверяете, закрывает ли последний ход какую-либо из линий ваших оппонентов и расширяет ли она некоторые из ваших линий, затем измените счет соответствующим образом.

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

Когда у вас есть игрок, вы должны попытаться выяснить, какая оценка различных элементов (2, 3, 4, открытая и полуоткрытая и т. Д.) Лучше всего, играя разные версии друг против друга.