Гомоку, основанный на массиве AI-алгоритм?
Давным-давно (думаю, 20 с лишним лет) я натолкнулся на исходный код игры Gomoku в журнале, который я набрал для своего компьютера, и мне было очень весело.
Игру было трудно выиграть, но основной алгоритм компьютерного ИИ был действительно простым и не содержал большого количества кода. Интересно, знает ли кто-нибудь этот алгоритм и имеет ли ссылки на какой-либо источник или теорию об этом?
То, что я помню, было то, что он в основном выделил массив, который покрывал всю доску. Затем, всякий раз, когда я или она помещали фигуру, она добавляла несколько весов ко всем местам на доске, на которые эта фигура могла бы повлиять.
Например (обратите внимание, что веса определенно неверны, так как я их не помню):
1 1 1
2 2 2
3 3 3
444
1234X4321
3 3 3
2 2 2
1 1 1
Затем он просто сканирует массив на наличие открытого местоположения с самым низким или самым высоким значением.
Вещи, на которых я неясен:
- Возможно, у него было два массива, один для меня и один для себя, и было минимальное / максимальное взвешивание?
- В алгоритме могло быть что-то большее, но по своей сути это был массив и взвешенные числа
Звонит ли это кому-нибудь вообще? Кто-нибудь получил что-нибудь, что могло бы помочь?
6 ответов
Читая ваше описание и немного подумав, я думаю, что он, вероятно, работает с одним массивом, именно так, как вы описали.
Для достижения цели получения пяти в ряд вы должны (а) помешать противнику добиться успеха и (б) преуспеть самостоятельно.
Чтобы добиться успеха, вы должны поместить камни рядом с другими камнями, которые у вас уже есть на доске, поэтому имеет смысл добавить положительный счет для полей рядом с вашими камнями, которые могут участвовать в ряду. Либо линейный пример, который вы привели, либо что-то квадратичное, вероятно, будет работать хорошо.
Чтобы помешать вашему противнику, вы должны поместить камни рядом с его / ее камнями. Это особенно хорошо, если вы ударите двух зайцев одним выстрелом, поэтому камни противника должны увеличивать ценность окружающих полей так же, как ваши - чем больше камней он уже выстроил, тем выше оценка и тем больше вероятность того, что Алгоритм будет пытаться отрезать противника.
Самым важным здесь является взвешивание различных полей и то, взвешены ли камни противника иначе, чем ваши. К сожалению, я не могу помочь с этим, но значения должны быть достаточно простыми, чтобы определить методом проб и ошибок после написания самой игры.
Тем не менее, это очень простой подход, и он превзойдет алгоритм поиска по дереву. В поиске Google есть статья о поиске угроз, которая, по-видимому, хорошо работает для Gomoku. Бумага за платной стеной, хотя: /
Я не читал статью, но из описания мое предположение было бы какой-то формой алгоритма Minimax
Я видел этот алгоритм, который вы упомянули - он был довольно простым и быстрым (без отступления:-)), и он играл очень хорошо:-) У меня должен быть источник где-то, но это было много лет назад... Были веса для ваших камней в зависимости от того, сколько других камней было рядом, и веса камней-оппонентов. Они были ниже, поэтому алгоритм предпочел атакующую стратегию.
Но это, конечно, очень тривиальный алгоритм. Выигрышная стратегия уже найдена. Смотрите эту статью: Л. Виктор Аллис, Х.Дж. ван ден Херик, магистр здравоохранения Хантженс Go-Moku и Threat-Space Search. Это мне очень помогло, когда я писал свою собственную программу. Таким образом, вы сможете написать программу, которая очень хороша в атаке противника и нахождении выигрышных комбинаций.
Вот программа, которую вы ищете ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw/gomoku.c
Ему почти 40 лет
Работа над версией с открытым исходным кодом для iPhone.
Ударь меня, если интересно присоединиться!