AI-альгоритм на основе матрицы Gomoku?

Question

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

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

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

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

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

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

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

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

Это вообще звонит в колокол? У кого -нибудь есть что -нибудь, что поможет?

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Но это, конечно, очень тривиальный алгоритм. Победная стратегия уже была найдена. Смотрите эту статью: Л. Виктор Аллис, HJ Van Den Herik, MPH Huntjens. Go-Moku и поиск пространства угроз. Анкет Это очень помогло мне, когда я писал свою собственную программу. Таким образом, вы сможете писать программу, которая очень хороша в атаке противника и поиске победных комбинаций.

Answer 4

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

Answer 5

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

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

Answer 6

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

Ударь меня, если заинтересован в присоединении!

https://github.com/kigster/kigomoku