AI стратегия для гомоку (вариация крестики-нолики)
Я пишу игру, это вариант Гомоку. В основном, крестики-нолики на огромной доске.
Хотите знать, если кто-нибудь знает хорошую стратегию ИИ для игры. Моя текущая реализация очень глупая и занимает много времени (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];
}
РЕДАКТИРОВАТЬ: Спасибо всем за отзыв! Я опробую ваши ответы и сообщу вам, если я смогу сделать какие-либо улучшения.
5 ответов
Для гомоку выигрышная стратегия уже найдена. Смотрите эту статью: Л. Виктор Аллис, Х.Дж. ван ден Херик, магистр здравоохранения Хантженс. Go-Moku и Threat-Space Search. Это мне очень помогло, когда я писал свою собственную программу. Таким образом, вы сможете написать программу, которая очень хороша в атаке противника и нахождении выигрышных комбинаций.
Традиционной и довольно эффективной стратегией написания ИИ для таких игр является типичная древовидная стратегия поиска. То есть каждое состояние платы формирует узел на графике, и направленный край помещается между каждым узлом и состояниями, которые могут быть получены одним движением. Таким образом, дерево строится так, что корневая плата является пустым узлом. Затем пройдитесь по дереву каким-нибудь умным способом, чтобы найти то, что выглядит как "хорошее" состояние. "Хорошее" состояние обычно измеряется оценочной функцией, которая использует некоторую умную эвристику. Очевидно, вы не хотите посещать все узлы в дереве - это было бы много работы! Вы просто хотите что-то умное.
Вы можете добавить предварительно рассчитанную раннюю игру и конечную игру, чтобы ускорить эти сценарии, а затем полагаться на хорошо оптимизированную эвристику обхода дерева для середины игры.
Фактическим названием таких алгоритмов обхода дерева является алгоритм "Минимакс". Ищите это в Википедии, и вы увидите много довольно приличного материала. Есть несколько способов повысить эффективность алгоритма, наиболее заметный из которых - альфа-бета-обрезка, поэтому обязательно посмотрите на это. Возможно, вы захотите взглянуть на эвристику connect-four и решить, как вы можете применить их к своей игре. Например, вероятной хорошей эвристикой для оценки состояний доски будет подсчет количества продолжительных 2-х, 3-х и 4-х серий и взвешивание их в балл. (например, каждый 2-й пробег будет стоить 1 очко, каждый 3-й пробег будет стоить 10 очков, а каждый 4-й пробег будет стоить 1000 очков)
Другой стратегией оптимизации является разработка эвристики, которая устанавливает приоритеты, где минимаксный алгоритм должен искать больше - обычно путем оценки некоторой определенности функции оценки доски.
С помощью этой стратегии вы сможете получить не такой глупый ИИ за то же время. Тем не менее, действительно, действительно хороший ИИ требует много усилий для создания, даже в такого рода "простых" играх, и все же может потребоваться более 10 секунд или больше, чтобы убрать умные ходы. С другой стороны, есть некоторые хитрые уловки программирования, такие как предварительные вычисления обходов по дереву, когда оппонент занят мышлением. Эй, люди думают, а компьютер думает. Ярмарка честна!
Надеюсь, мне помогли. Удачи! Это веселый проект.
Гомоку решается, но не решается, когда играется с открытой позицией и ограниченными ресурсами.
Я являюсь автором программы Hewer gomoku и организатора Gomocup, и я могу вам сказать, что вам нужно очень много времени, чтобы написать хороший AI Gomoku. Рэндзю намного сложнее. Вы можете упростить свою работу с помощью интерфейса Gomocup и написать "только" AI.
Я уже некоторое время пытаюсь создать алгоритм для той же программы.
Вы, конечно, правы в том, что первое, что должна сделать Ваша программа, это проверить, есть ли способ сформировать 5 и выиграть. А если нет, то следует проверить, может ли ваш оппонент сделать это, и если да, то защита.
Сколько ты сам играл в гомоку? Насколько хорошо вы понимаете основы?
Хорошо, следующий шаг - подумать: как мы можем добраться до позиций, где мы можем победить? Очевидно, что для победы у нас должно быть четыре подряд. Но мы просто формируем четыре подряд, как это:
__________
____XOOOO_
__________
Тогда противник может закрыть его.
Но если мы сформируем "открытую четверку", вот так:
__________
____OOOO__
__________
Тогда противник не может закрыть обе стороны, и Вы можете выиграть. Таким образом, формирование открытой четверки - это один из способов выиграть. Теперь возникает вопрос: как мы можем сформировать открытую четверку? Конечно, если мы сформируем "открытую тройку", вот так:
__________
____OOO___
__________
Тогда противник может заблокировать нас:
___________
____XOOO___
___________
и мы вернулись к началу.
Чтобы выиграть, мы можем сформировать две открытые тройки одновременно:
____________
____OOO_____
_____O______
____O_______
Теперь, если противник блокирует одну из них, мы можем использовать другую, чтобы сформировать открытую четверку:
____________
_______O____
___XOOO_____
_____O______
____O_______
____________
и выиграть:
________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________
В терминах гомоку это называется 3х3, если вы делаете две открытые тройки одновременно.
Обратите внимание, что обе тройки должны быть открыты: вы понимаете, почему?
Есть и другие способы выиграть:
4x3: Вы видите выигрышный ход и почему он выигрывает?
____________
__XOOO______
__XXXO______
____OX______
____________
4x4: Видишь выигрышный ход?
____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________
Это только основы игры. Знание тактики помогает вам думать, как построить ИИ, и вы можете жестко программировать принципы.
Естественно, это только начало. Буду признателен, если Вы попытаетесь реализовать это, а затем дать мне обратную связь.
Я пытался написать программу на Java. Хотели бы вы увидеть код, который я сделал, чтобы вы могли играть в тест? Это еще не очень хорошо, но Вы можете получить новые идеи оттуда. Хотя комментарии и имена переменных написаны на эстонском языке... это может быть очень трудно понять.:(
Я создал игрока гомоку один раз, и это было довольно успешно, используя альфа-бета-обрезку и давая каждой позиции оценку в зависимости от того, сколько полуоткрытых и полностью открытых 2, 3 и 4 каждого игрока было.
Расчет это не п ^3. Вы просто проверяете, закрывает ли последний ход какие-либо линии ваших оппонентов, и если он расширяет некоторые из ваших линий, то измените счет соответственно.
Если вам нужно, чтобы игра была еще лучше, я бы изучил некоторые приемы с шахматных компьютеров. Например, попытка "убийственных ходов" (запоминание того, какие ходы дали высокий балл или сразу выиграли в других позициях) сначала при поиске значительно повысит эффективность поиска по дереву. Важно сначала попробовать предполагаемые лучшие ходы в альфа-бета-обрезке.
Когда у вас есть игрок, вы должны попытаться выяснить, какая оценка различных элементов (2 с, 3 с, 4 с, открытый и полуоткрытый и т. Д.) Лучше всего, играя разные версии друг против друга.
Я немного опоздал с написанием, но вопрос остается открытым, поэтому я добавлю свой опыт работы с ИИ-плеером Гомоку. Может кому пригодится...
Я тоже создал своего игрока в гомоку. Он не идеален, но играет вполне прилично и, безусловно, лучше меня. Во всяком случае, я обнаружил, что:
- Если игрок будет использовать поиск по глубине, поиск правильного хода должен быть ограничен определенными позициями на доске. Наивным способом было бы искать только соседние с камнями позиции. Другой способ - включить только те ходы, которые создают "угрозу", например, открытые двойки, открытые тройки и другие. Затем включите только защитные движения, которые блокируют атакующие. Эта эвристика значительно сокращает количество узлов для поиска. Если я правильно понимаю, аналогичный подход к уменьшению пространства поиска был использован для решения Гомоку.
- Тем не менее, коэффициент ветвления гомоку высок, и если игрок не находит выигрышную последовательность, он должен выбрать "лучший" из возможных ходов. Эвристика для определения того, что является "лучшим", очень важна для работы ИИ-игрока.
Итак, мой игрок в гомоку оценивает все позиции доски без поиска глубины. Он разделяет горизонтальные, вертикальные и диагональные линии доски на строки. Затем ищет в таблице шаблоны в этих строках. Вот некоторые из схем для черного игрока:
- xxxxx: 10000000000 баллов
- -xxxx-: 9999999
- -xxx-: 50
- -xx-: 500
- ооооо: -100000000
- -oooo-: -99999999
- -ooo--: -999999
- -oo-: -2000
X отмечает камни черных игроков, O отмечает белые камни игроков и "-" отмечает пустые позиции. Игрок суммирует все найденные закономерности и делает ход с наибольшим количеством найденных очков.