Гомоку, основанный на массиве AI-алгоритм?

Question

Давным-давно (подумайте, 20 с лишним лет) я натолкнулся на исходный код игры Gomoku в журнале, который набрал для своего компьютера, и мне было очень весело.

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

То, что я помню, было то, что он в основном выделил массив, который покрывал всю доску. Затем, всякий раз, когда я или она помещали фигуру, она добавляла несколько весов ко всем местам на доске, на которые эта фигура могла бы воздействовать.

Например (обратите внимание, что веса определенно неверны, поскольку я их не помню):

1   1   1
 2  2  2
  3 3 3
   444
1234X4321
  3 3 3
 2  2  2
1   1   1

Затем он просто сканировал массив на наличие открытого местоположения с самым низким или самым высоким значением.

Вещи, на которых я неясен:

• Возможно, у него было два массива, один для меня и один для себя, и был минимальный / максимальный вес?
• Возможно, в алгоритме было что-то большее, но по своей сути это был массив и взвешенные числа

Звонит ли это кому-нибудь вообще? Кто-нибудь получил что-нибудь, что могло бы помочь?

Answer 1

Читая ваше описание и немного подумав, я думаю, что он, вероятно, работает с одним массивом, именно так, как вы описали.

Для достижения цели получения пяти в ряд вы должны (а) помешать противнику добиться успеха и (б) преуспеть самостоятельно.

Чтобы добиться успеха, вы должны поместить камни рядом с другими камнями, которые у вас уже есть на доске, поэтому имеет смысл добавить положительный счет для полей рядом с вашими камнями, которые могут участвовать в ряду. Либо линейный пример, который вы привели, либо что-то квадратичное, вероятно, будет хорошо работать.

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

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

Однако это очень простой подход, и он будет лучше, чем алгоритм поиска по дереву. В поиске Google есть статья о поиске угроз , которая, по-видимому, хорошо работает для Gomoku. Бумага находится за платой, хотя: /

Answer 2

Я видел этот алгоритм, который вы упомянули - он был довольно простым и быстрым (без возврата :-)), и он играл очень хорошо :-) У меня должен быть источник где-то, но это было много лет назад ... Были вес для ваших камней, в зависимости от того, сколько других камней было рядом, и веса камней-оппонентов. Они были ниже, поэтому алгоритм предпочел атакующую стратегию.

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

Answer 3

Я не читал статью, но из описания я думаю, что это будет форма алгоритма Минимакс

Answer 4

Вот программа, которую вы ищете FTP: //ftp.mrynet.com/USENIX/80.1/boulder/dpw/gomoku.c

Ему почти 40 лет

Answer 5

Это древняя игра - я нашел код на Исходный код планеты . Я играл в эту игру во время учебы в колледже, и через 286 дней у меня была БЕЙСИК-версия.

Answer 6

Работа над версией с открытым исходным кодом для iPhone.

Ударь меня, если хочешь присоединиться!

https://github.com/kigster/kigomoku